Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #10309 > unrolled thread

Reversing a linked list

Back to article view | Back to comp.lang.c

Contents

  Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 08:30 +0200
    Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 08:33 +0200
    Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-16 12:51 +0100
      Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 14:18 +0200
        Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 14:26 +0200
          Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-16 07:09 -0700
            Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-16 08:28 -0700
              Re: Reversing a linked list falk@rahul.net (Edward A. Falk) - 2011-09-16 16:34 +0000
              Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-16 09:28 -0700
                Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-16 11:12 -0700
                  Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 20:01 -0500
        Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-16 21:56 +0100
          Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 20:16 -0500
            Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 02:48 +0100
              Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 22:15 -0500
                Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 07:40 +0200
                  Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 01:24 -0500
                  Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-17 15:07 +0000
                    Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 17:47 +0200
                      Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 17:54 +0200
                    Re: Reversing a linked list Michael Press <rubrum@pacbell.net> - 2011-09-27 19:21 -0700
                Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 12:00 +0100
                  Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 23:53 -0500
      Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-16 07:21 -0700
        Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 16:47 +0200
          Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-16 08:20 -0700
          Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 20:25 -0500
        Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-16 22:32 +0100
        Re: Reversing a linked list pete <pfiland@mindspring.com> - 2011-09-16 17:53 -0400
      Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 19:48 -0500
        Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 02:41 +0100
          Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 22:57 -0500
            Re: Reversing a linked list "BartC" <bc@freeuk.com> - 2011-09-17 12:48 +0100
              Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 13:55 +0200
              Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 23:39 -0500
    Re: Reversing a linked list HENRY Eshbaugh <henryeshbaugh@gmail.com> - 2011-09-16 16:56 -0700
      Re: Reversing a linked list Ian Collins <ian-news@hotmail.com> - 2011-09-17 12:09 +1200
        Re: Reversing a linked list HENRY Eshbaugh <henryeshbaugh@gmail.com> - 2011-09-16 19:53 -0700
          Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 23:00 -0500
            Re: Reversing a linked list Jonathan Leffler <jleffler@earthlink.net> - 2011-09-16 23:20 -0700
            Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-17 13:46 -0700
              Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-17 19:51 -0700
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-18 01:28 -0700
                  Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 15:39 -0700
                    Re: Reversing a linked list Kleuskes & Moos <kleuske@somewhere.else.net> - 2011-09-18 22:43 +0000
                      Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 17:54 -0700
                        Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:20 -0400
                    Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-18 17:30 -0700
                      Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 17:51 -0700
                        Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:34 -0400
                        Re: Reversing a linked list Robert Wessel <robertwessel2@yahoo.com> - 2011-09-18 21:25 -0500
                        Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-19 09:56 -0700
                          Re: Reversing a linked list gazelle@shell.xmission.com (Kenny McCormack) - 2011-09-19 17:16 +0000
                          Re: Reversing a linked list Willem <willem@toad.stack.nl> - 2011-09-19 17:25 +0000
                            Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-19 23:40 -0700
                            Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-20 17:55 -0700
                          Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-20 17:48 -0700
                            Re: Reversing a linked list Geoff <geoff@invalid.invalid> - 2011-09-20 19:12 -0700
                              Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 10:15 -0700
                                Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-22 08:43 -0700
                                  Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-23 02:45 -0700
                                    Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-23 05:38 -0700
                                      Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-23 07:58 -0700
                                        Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-23 08:15 -0700
                                          Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 18:00 +0100
                                            Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-23 10:49 -0700
                                              Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 20:05 +0100
                                            Re: Reversing a linked list pete <pfiland@mindspring.com> - 2011-09-23 18:05 -0400
                                              Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-24 00:19 +0100
                                        Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-23 09:25 -0700
                                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-22 22:49 +0300
                            Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-20 19:51 -0700
                              Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 09:51 -0700
                                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-21 11:21 -0700
                            Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-20 23:00 -0400
                              Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 09:47 -0700
                                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-23 11:22 +0300
                                  Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-23 08:20 -0700
                                    Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 18:12 +0100
                                      Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:13 -0800
                                    Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-23 23:49 +0300
                                      Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-24 08:15 -0400
                                        Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-24 20:15 +0300
                                      Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:28 -0800
                                        Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-12 01:41 +0200
                                          Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-08 09:08 -0800
                                            Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-13 17:21 +0200
                              Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:04 -0800
                            Re: Reversing a linked list Seebs <usenet-nospam@seebs.net> - 2011-09-23 01:46 +0000
                    Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:17 -0400
              Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 23:50 -0500
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-18 01:29 -0700
          Re: Reversing a linked list Seebs <usenet-nospam@seebs.net> - 2011-09-18 07:03 +0000
      Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 02:13 +0100
        Re: Reversing a linked list HENRY Eshbaugh <henryeshbaugh@gmail.com> - 2011-09-16 19:52 -0700
          Re: Reversing a linked list Willem <willem@toad.stack.nl> - 2011-09-17 08:58 +0000
            Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 15:32 -0700
              Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:36 -0400
                Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-19 05:24 +0000
                  Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-19 08:21 -0400
                    Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-19 14:28 +0000
                      Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-19 17:01 +0100
                        Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-19 16:25 +0000
                  Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 10:41 -0700
                    Re: Reversing a linked list Kleuskes & Moos <kleuske@somewhere.else.net> - 2011-09-21 17:58 +0000
                    Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-21 14:07 -0400
                    Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-21 11:15 -0700
                      Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-21 11:37 -0700
                        Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-23 11:50 +0300
                    Re: Reversing a linked list Seebs <usenet-nospam@seebs.net> - 2011-09-23 01:46 +0000
      Re: Reversing a linked list Geoff <geoff@invalid.invalid> - 2011-09-18 18:22 -0700
    Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 19:37 -0500
      Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 07:52 +0200
        Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 02:09 -0500
          Re: Reversing a linked list Ian Collins <ian-news@hotmail.com> - 2011-09-17 19:35 +1200
            Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 03:35 -0500
          Programming languages jacob navia <jacob@spamsink.net> - 2011-09-17 22:14 +0200
            Re: Programming languages "Tony" <nospamme@ever.net> - 2011-09-18 00:11 -0500
              Re: Programming languages jacob navia <jacob@spamsink.net> - 2011-09-18 08:37 +0200
              Re: Programming languages Seebs <usenet-nospam@seebs.net> - 2011-09-18 07:03 +0000
                Re: Programming languages jacob navia <jacob@spamsink.net> - 2011-09-18 09:50 +0200
                Re: Programming languages Keith Thompson <kst-u@mib.org> - 2011-09-18 01:31 -0700
                  Re: Programming languages James Kuyper <jameskuyper@verizon.net> - 2011-09-18 06:43 -0400
                    Re: Programming languages Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-09-18 07:42 -0700
                  Re: Programming languages "Tony" <nospamme@ever.net> - 2011-09-18 04:05 -0500
              Re: Programming languages Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-09-18 07:40 -0700
    Re: Reversing a linked list Gene <gene.ressler@gmail.com> - 2011-09-22 06:59 -0700

Page 1 of 7  [1] 2 3 4 5 6 7  Next page →

#10309 — Reversing a linked list

This group has lost many people. One of the reasons is that the
newcomers just ask a question or two, and do not see discussions
that try to explain code, teaching newcomers to the language how
a program works.

This is a second example (after hexdump.c) of commented code,
i.e. explaining step by step how a relatively simple operation
is done.

Reversing a linked list
-----------------------
This is an evergreen of data structures programming. In most classes
you will get an exercise like this:

Exercise 7: Given a list "L" reverse it without moving its contents.

The solution for this exercise is to go through the list, relinking the
"Next" pointers in the inverse order, without touching any data that
the list may hold. We will use the code of the C containers library and
study how it is done.

The library uses a simple structure "ListElement" whose definition runs
like this:

typedef struct _ListElement {
     struct _ListElement *Next;
     char Data[];
} ListElement;

We have a pointer to the next element of the list, and a chunk of data
of unspecified length. This is the basic structure that will be used
to hold the list data. Besides the list element we have a header of the
list, containing several fields not relevant to the task of our reverse
function. We will use only the following fields from that header:

o RaiseError: Pointer to the error function.
o First: The first element of the list.
o count: The number of items in the list.
o Last: A pointer to the last element of the list.
o timestamp: A counter of the modifications done to the list.

The interface of the reverse function is simple: it receives a list to
reverse as input and returns an integer result code. A negative result
means failure (with different negative numbers as error codes) and a
positive number means success.

   1 static int Reverse(List *l)
   2 {
   3     ListElement *Previous,*Current,*Next;
   4

The first thing to do in a serious program is to check the validity of
the received arguments, i.e. test the preconditions as Bertrand Meyer
would say it. We test that the list handed to us is not Null (lines
5-8) and that the list is not read-only (lines 9-12) since we are going 
to modify it.

If anything is wrong we return an error code after calling the error 
function. Note that the error function is a field either in a global 
structure
called iError (for interface Error) or is a field of the list itself. We 
use the global interface iError in the case that the list is\Null, or the
list specific error function for the read only error. This is a powerful 
feature of C called function pointers that we will discuss in more detail
later on.

   5     if (l == NULL) {
   6         iError.RaiseError("iList.Reverse",CONTAINER_ERROR_BADARG);
   7         return CONTAINER_ERROR_BADARG;
   8     }
   9     if (l->Flags & CONTAINER_READONLY) {
  10         l->RaiseError("iList.Reverse",CONTAINER_ERROR_READONLY);
  11         return CONTAINER_ERROR_READONLY;
  12     }

Then, we test for special conditions, i.e. for degenerate cases.
Obviously, reversing an empty list or a list with only one element is
very easy: we have nothing to do. We test for that (line 13) and return
success immediately if that is the case.

  13     if (l->count < 2)
  14         return 1;

Now, we setup our loop. We start with the first element (that must
exist since the list has more than one element, line 15). Since we are 
going to reverse the list, the first element will be the last and the
last will be the first. We setup the last one immediately since we know
it in line 16. And before we start there is no previous element so we 
set it to NULL.

  15     Next = l->First;
  16     l->Last = l->First;
  17     Previous = NULL;

Now we go through the whole list. We save the "Next" value, and advance
it to the next element. Then, we set the value of the current element's
pointer to the previous, i.e. our current will point to previous
reversing the direction of the list.

  18     while (Next) {
  19         Current = Next;
  20         Next = Next->Next;
  21         Current->Next = Previous;
  22         Previous = Current;
  23     }

OK, we are done. We have gone through the whole list reversing
pointers, and we arrive at the cleanup. We should first establish our
"First" pointer, then we should ensure that our last element has
the Null marker, and that our list is marked as modified. We return a
positive number meaning success.

  24     l->First = Previous;
  25     l->Last->Next = NULL;
  26     l->timestamp++;
  27     return 1;
  28 }

[toc] | [next] | [standalone]

#10310

Le 16/09/11 08:30, jacob navia a écrit :

> typedef struct _ListElement {
> struct _ListElement *Next;
> char Data[];
> } ListElement;

Should be:

typedef struct tagListElement { // <<<<<
struct tagListElement *Next; // <<<<
char Data[];
} ListElement;

Underscores should not start an identifier since those are reserved for
the implementation. Change _ListElement to tagListElement.

[toc] | [prev] | [next] | [standalone]

#10313

jacob navia <jacob@spamsink.net> writes:
<snip>
> Reversing a linked list
> -----------------------
> This is an evergreen of data structures programming. In most classes
> you will get an exercise like this:
>
> Exercise 7: Given a list "L" reverse it without moving its contents.
>
> The solution for this exercise is to go through the list, relinking the
> "Next" pointers in the inverse order, without touching any data that
> the list may hold. We will use the code of the C containers library and
> study how it is done.
>
> The library uses a simple structure "ListElement" whose definition runs
> like this:
>
> typedef struct _ListElement {
>     struct _ListElement *Next;
>     char Data[];
> } ListElement;
>
> We have a pointer to the next element of the list, and a chunk of data
> of unspecified length. This is the basic structure that will be used
> to hold the list data. Besides the list element we have a header of the
> list, containing several fields not relevant to the task of our reverse
> function. We will use only the following fields from that header:
>
> o RaiseError: Pointer to the error function.
> o First: The first element of the list.
> o count: The number of items in the list.
> o Last: A pointer to the last element of the list.
> o timestamp: A counter of the modifications done to the list.

I'd show this other structure.  This is a teaching example after all.
timestamp is an odd name for a counter.  Obviously I can see the
connection, but an update count and a time are only loosely connected.

> The interface of the reverse function is simple: it receives a list to
> reverse as input and returns an integer result code. A negative result
> means failure (with different negative numbers as error codes) and a
> positive number means success.
>
>   1 static int Reverse(List *l)
>   2 {
>   3     ListElement *Previous,*Current,*Next;
>   4
>
> The first thing to do in a serious program is to check the validity of
> the received arguments, i.e. test the preconditions as Bertrand Meyer
> would say it. We test that the list handed to us is not Null (lines
> 5-8) and that the list is not read-only (lines 9-12) since we are
> going to modify it.

This is not what I understand by the phrase "function precondition".
Maybe Meyer uses it that way but I would be surprised.  Almost by
definition, a precondition is something that you *don't* check.  It is
stated in the documentation (and probably as a comment) but as soon as
you test for it it becomes part of the defined behaviour of the function
and stops being a precondition.  You can (often during development) use
something like assert to make sure that your callers are keeping to the
implied contract of the preconditions, but as soon as this check turns
into "when l == NULL return error number XYZ" it stops being (at least
by my understanding of the term) a precondition.

Since this is a teaching exercise, you could ask the reader to state the
function's preconditions because it does have quite a few interesting
ones.

<snip>
> Then, we test for special conditions, i.e. for degenerate cases.
> Obviously, reversing an empty list or a list with only one element is
> very easy: we have nothing to do. We test for that (line 13) and return
> success immediately if that is the case.
>
>  13     if (l->count < 2)
>  14         return 1;

It's not clear why you need to do this.  There may be some tiny
performance benefit, but it suggests to the learner that these lists are
special when, in most cases, they are not.  I think the following code
can be written to handle all lists, and the change needed to do that is
simplification of the code.  In other words, I think you've turned the
empty list into a special case where it need not be one.

This test also induces another pre-condition for the function by which I
mean a pre-condition in my sense of the word (something that must be
true that the function does not test and handle as part of its defined
behaviour).  However, I can see that there is teaching value here as you
can ask about the consequences of leaving the test there and the merits
of removing it.

> Now, we setup our loop. We start with the first element (that must
> exist since the list has more than one element, line 15). Since we are
> going to reverse the list, the first element will be the last and the
> last will be the first. We setup the last one immediately since we know
> it in line 16. And before we start there is no previous element so we
> set it to NULL.
>
>  15     Next = l->First;
>  16     l->Last = l->First;
>  17     Previous = NULL;
>
> Now we go through the whole list. We save the "Next" value, and advance
> it to the next element. Then, we set the value of the current element's
> pointer to the previous, i.e. our current will point to previous
> reversing the direction of the list.
>
>  18     while (Next) {
>  19         Current = Next;
>  20         Next = Next->Next;
>  21         Current->Next = Previous;
>  22         Previous = Current;
>  23     }
>
> OK, we are done. We have gone through the whole list reversing
> pointers, and we arrive at the cleanup. We should first establish our
> "First" pointer, then we should ensure that our last element has
> the Null marker, and that our list is marked as modified. We return a
> positive number meaning success.
>
>  24     l->First = Previous;
>  25     l->Last->Next = NULL;

This is, for me, the problem line.  I don't think it's needed yet it
turns the empty list into a special case.

>  26     l->timestamp++;
>  27     return 1;
>  28 }

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#10319

Le 16/09/11 13:51, Ben Bacarisse a écrit :
>>
>>   24     l->First = Previous;
>>   25     l->Last->Next = NULL;
>
> This is, for me, the problem line.  I don't think it's needed yet it
> turns the empty list into a special case.

Bright mind Ben, you have a bright mind.

Exactly.

l->Last was modified as the first object with Previous that has
the NULL value at the start.

That line is not necessary. If we eliminate it, the empty list will
pass.

Thanks.

In the other stuff you are mostly right: timestamp is a bad name,
and I will show the whole structure header for the list.

Concerning the "preconditions" term, Betrand Meyer uses it as one of the
two parts of a function contract: The preconditions and the postconditions.

The first ones are the ones that the function requires from its caller, 
and the second ones are the ones that the function
ensures to its users. They are part of the Eiffel language that Meyer
designed.

It is true that Reverse has other preconditions not mentioned
explicitely or shown in the code:

o We assume a list that is terminated by a NULL pointer
o We assume a list without cycles

Testing for the first means

if (l->count > 0) assert(l->Last->Next == NULL);

Testing for the second needs

rvp = l->First;
rvpFast = rvp->Next;
while (rvpFast) {
     if (rvp == rvpFast) {
          iError.RaiseError("Reverse", CIRCULAR_LIST);
          return ERROR_CIRCULAR_LIST;
     }
     if (rvpFast)
         rvpFast = rvpFast->Next;
     if (rvpFast)
         rvpFast = rvpFast = rvpFast->Next;
     rvp = rvp->Next;
}
return 0;

We establish two pointers to traverse the list, one that will move
twice as fast as the first. If they are ever equal there is a circle
in the list.

I will add that to the solved exercises.

Thanks again

[toc] | [prev] | [next] | [standalone]

#10321

Le 16/09/11 14:18, jacob navia a écrit :
> if (rvpFast)
>     rvpFast = rvpFast = rvpFast->Next;

OOOPS, that should be:

 >     rvpFast = rvpFast->Next;

Sorry

[toc] | [prev] | [next] | [standalone]

#10326

On Sep 16, 3:26 pm, jacob navia <ja...@spamsink.net> wrote:
>

Ypu can cut that code down to just this

NODE *reverselinkedlist(NODE *head)
{
  NODE *prev = NULL;
  NODE *temp;

  while(head)
  {
    temp = head->next;
    head->next = prev;
    prev = head;
    head = temp;
  }
  return prev;
}

This expresses the good things and the bad things about C. The code's
only a few lines, so it's hardly worthwhile writing a function for it.
Normally you'll have a linked list consisting of a "next" member
embedded in some structure or other, and you can just modify the code
boilerplate. But it would be nicer to be able to make it generic.
Also, the code will crash if passed an invalid list, but it needs no
special conditions for the empty list or the one-member list case.
Also, you've got the annoying little dance with a temporary. It's not
possible to glance at the code and see that it is right, as you can
with the performance-insensitive solution.

NODE *inefficientreverse(NODE *head)
{
  if(head->next == 0)
   return head;
  answer = reverse(head->next);
  append(answer, head);
  return answer;
}

--
Visit my website
http://www.malcolmmclean.site11.com/www

[toc] | [prev] | [next] | [standalone]

#10334

On Sep 16, 10:09 am, Malcolm McLean <malcolm.mcle...@btinternet.com>
wrote:
> On Sep 16, 3:26 pm, jacob navia <ja...@spamsink.net> wrote:
>
>
>
> Ypu can cut that code down to just this
>
> NODE *reverselinkedlist(NODE *head)
> {
>   NODE *prev = NULL;
>   NODE *temp;
>
>   while(head)
>   {
>     temp = head->next;
>     head->next = prev;
>     prev = head;
>     head = temp;
>   }
>   return prev;
>
> }
>
> This expresses the good things and the bad things about C. The code's
> only a few lines, so it's hardly worthwhile writing a function for it.

Code compression is not the best reason for defining functions.  Code
abstraction is.  As such, I fail to see how this is a 'bad thing'
about C.  I see it as a very good thing, of any programming language
worth using.

> Normally you'll have a linked list consisting of a "next" member
> embedded in some structure or other, and you can just modify the code
> boilerplate. But it would be nicer to be able to make it generic.

It is possible to make it generic if you're willing to place the onus
on the user to be responsible for the keeping track of node's
referenced object type.  GLib has a linked list structure with a
void*, and a function like reverse can be implemented independently
from the knowledge of the list's object type.

In my opinion, having one general abstraction for a linked list using
void* is more valuable than packaging the type information in the list
node (so you don't have to cast the node's object pointer).  If the
number of types that require linked lists is one or two, or efficiency
is a high priority, then packaging a specific object type in the list
node with a struct can be better.

> Also, the code will crash if passed an invalid list,

You trade safety for efficiency.  It's a judgement call; it only looks
good/bad depending on your perspective.  The implementors of C
compiler's standard string library in <string.h> usually make a choice
for efficiency.  Again this goes back to whether you want to test for
a function's preconditions, and if tested how you respond to them:
early-exit with an error value, argument substitution, use a benign
value, set a global errno, log a message to the screen or to a file,
assert, controlled-crash (like saving user's work), let the OS deal
with it ...

> but it needs no
> special conditions for the empty list or the one-member list case.
> Also, you've got the annoying little dance with a temporary. It's not
> possible to glance at the code and see that it is right,

That's a matter of experience.  Sure, maybe the lisp people will get
it right away.  I wouldn't necessarily bet that the average C
programmer will "get it" better.  I doubt most students learning
linked lists for the first time will be able to visually inspect
either and know that it's right without sitting at a computer (I know
I sure didn't).

This is why you write functions to begin with, to reduce the
complexity into containable pieces (what I refer to as code
abstraction).  Users of the linked list reverse function shouldn't
want or need to see that it's done right.  Granted if the function is
implemented poorly, it becomes a concern, but that should be visible
with external behavior or tests, not through inspecting the source
code.  For example, if one is a Windows applications programmer, you
really don't want to dig down into the source of a Windows API call to
see if it's doing something right or wrong, do ya?

> as you can
> with the performance-insensitive solution.
>
> NODE *inefficientreverse(NODE *head)
> {
>   if(head->next == 0)
>    return head;
>   answer = reverse(head->next);
>   append(answer, head);
>   return answer;
>
> }

The real advantage of functions is that you've hidden the
implementation details, so if the 'inefficientreverse' function is not
good enough from some limitation, you can modify the function rather
than every manual linked-list reverse spread throughout your program.
When a regular posts that they'd prefer to do linked lists by hand, I
scratch my head and wonder why.  Why is the linked list seemingly
impervious in the mindset of some to improvement by abstraction?

(I know you likely already know most of this stuff, just putting my
thoughts out there)

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#10335

In article <2b78c0b7-000c-4d6d-a8c9-8f1f7a1d56b4@y21g2000yqk.googlegroups.com>,
ImpalerCore  <jadill33@gmail.com> wrote:
>>
>> You can cut that code down to just this

Thank you.  Elegant and simple.  Explains the process without
being verbose.

>Code compression is not the best reason for defining functions.  Code
>abstraction is.  As such, I fail to see how this is a 'bad thing'
>about C.  I see it as a very good thing, of any programming language
>worth using.

Totally agree.  My rule of thumb in programming is: if you find your
self writing the same code for the third time, it's time to make it
into a function.

-- 
	-Ed Falk, falk@despams.r.us.com
	http://thespamdiaries.blogspot.com/

[toc] | [prev] | [next] | [standalone]

#10336

On Sep 16, 6:28 pm, ImpalerCore <jadil...@gmail.com> wrote:
>
> When a regular posts that they'd prefer to do linked lists by hand, I
> scratch my head and wonder why.  Why is the linked list seemingly
> impervious in the mindset of some to improvement by abstraction?
>
It's the bool problem. Clever Dick writes

typedef int BOOL;

BOOL solvestoppingproblem(char *program);

The problem is now everyone who want to call solvestoppingproblem()
has got to import the typedef of BOOL. Clever Dick has no business
defining something as fundamental and atomic as a boolean type in a
high-level function file like solvestoppingproblem(). In fact the
integration problems become so severe that people just research their
own solvestoppingproblem() functions instead, because it's easier to
redo Clever Dick's work than to mess about with BOOLs and Bools and
boolean_t's all about the place.

You've got the same problem in declaring a generic linked list type.
Great if you're only writing all of only one program and you're the
configuration manager, so can insist that everyone uses it, but a
nightmare if you don't have that sort of controlled environment. Most
of the time, it's a lot easier to lay out the structures you need, and
just add a "next" member. Then you can manipulate the linked list by
hand, avoiding a dependency. That's why people are always writing new
string libraries, or linked list abstractions for C, and they never
catch on.

--
10 rules of programming
http://www.malcolmmclean.site11.com/www

[toc] | [prev] | [next] | [standalone]

#10337

On Sep 16, 12:28 pm, Malcolm McLean <malcolm.mcle...@btinternet.com>
wrote:
> On Sep 16, 6:28 pm, ImpalerCore <jadil...@gmail.com> wrote:
>
> > When a regular posts that they'd prefer to do linked lists by hand, I
> > scratch my head and wonder why.  Why is the linked list seemingly
> > impervious in the mindset of some to improvement by abstraction?
>
> It's the bool problem. Clever Dick writes
>
> typedef int BOOL;
>
> BOOL solvestoppingproblem(char *program);
>
> The problem is now everyone who want to call solvestoppingproblem()
> has got to import the typedef of BOOL. Clever Dick has no business
> defining something as fundamental and atomic as a boolean type in a
> high-level function file like solvestoppingproblem(). In fact the
> integration problems become so severe that people just research their
> own solvestoppingproblem() functions instead, because it's easier to
> redo Clever Dick's work than to mess about with BOOLs and Bools and
> boolean_t's all about the place.
>
> You've got the same problem in declaring a generic linked list type.
> Great if you're only writing all of only one program and you're the
> configuration manager, so can insist that everyone uses it, but a
> nightmare if you don't have that sort of controlled environment. Most
> of the time, it's a lot easier to lay out the structures you need, and
> just add a "next" member. Then you can manipulate the linked list by
> hand, avoiding a dependency. That's why people are always writing new
> string libraries, or linked list abstractions for C, and they never
> catch on.

Thank you, that was insightful.  To me, it seems like the only
plausible solution (which I admit is very unlikely to happen) to the
problem (abstracting a generic linked list interface) is to have some
kind of "boost" for C, have some part of the library get so popular
and use its popularity as a springboard to fight to standardize the
interface.  At least there is some evidence that the process can lead
to a positive impact on changing the C++ standard.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#10366

ImpalerCore wrote:

> Thank you, that was insightful.  To me, it seems like the only
> plausible solution (which I admit is very unlikely to happen) to the
> problem (abstracting a generic linked list interface) is to have some
> kind of "boost" for C, have some part of the library get so popular
> and use its popularity as a springboard to fight to standardize the
> interface.  At least there is some evidence that the process can lead
> to a positive impact on changing the C++ standard.
>

Of course, that soon it will be theoretically possible that ALL C users 
will be amenable to using one of those "Boost for C" things. It gets more 
realistic everyday, for there are less C users everyday. Doesn't "Boost 
for C" actually mean, "C++ is right, C is wrong"? The scenario is kind of 
like the techie who spends a great deal of his career fighting management 
and then becomes "a manager"! Resistance is futile? 

[toc] | [prev] | [next] | [standalone]

#10351

jacob navia <jacob@spamsink.net> writes:
<snip>
> Concerning the "preconditions" term, Betrand Meyer uses it as one of the
> two parts of a function contract: The preconditions and the postconditions.
>
> The first ones are the ones that the function requires from its
> caller, and the second ones are the ones that the function
> ensures to its users. They are part of the Eiffel language that Meyer
> designed.

Yes, I know a little about Eiffel.  My point it is that as soon as a
condition moves from being part of the caller's contract to part of the
function's responsibility, it stops being a precondition; it becomes
part of the defined behaviour of the function.  In C, since there is no
notation for pre-conditions, I think it's fine to use the term for
things "assert"ed at the top of the function, but I would not use it for
conditions tested in the body.

> It is true that Reverse has other preconditions not mentioned
> explicitely or shown in the code:
>
> o We assume a list that is terminated by a NULL pointer
> o We assume a list without cycles
>
> Testing for the first means
>
> if (l->count > 0) assert(l->Last->Next == NULL);

I am not sure that's enough.  First, there are pre-conditions on
l->count but even if you deal with those, the NULL might not be
reachable from l->First.  Basically all your list function will have a
precondition that the list is well-formed: no cycles, l->Last can be
reached from l->First in exactly l->count steps, etc.  If you can write
this as a predicate you could try to prove that all your list functions
preserve that predicate (provided their pre-conditions are met).  I'd
not try a formal proof (almost impossible in C) but informal ones can be
very handy at flushing out peculiar bugs.

> Testing for the second needs
>
> rvp = l->First;
> rvpFast = rvp->Next;
> while (rvpFast) {
>     if (rvp == rvpFast) {
>          iError.RaiseError("Reverse", CIRCULAR_LIST);
>          return ERROR_CIRCULAR_LIST;
>     }
>     if (rvpFast)
>         rvpFast = rvpFast->Next;
>     if (rvpFast)
>         rvpFast = rvpFast = rvpFast->Next;
>     rvp = rvp->Next;
> }
> return 0;

You've made the empty list a special case again.  Maybe it doesn't
matter if you want to test for that first but there's no need:

  rvpFast = rvp = l->First;
  while (rvpFast) {
      rvpFast = rvpFast->Next;
      if (rvp == rvpFast) {
           iError.RaiseError("Reverse", CIRCULAR_LIST);
           return ERROR_CIRCULAR_LIST;
      }
      if (rvpFast)
          rvpFast = rvpFast->Next;
      rvp = rvp->Next;
  }
  return 0;

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#10368

Ben Bacarisse wrote:
> jacob navia <jacob@spamsink.net> writes:
> <snip>
>> Concerning the "preconditions" term, Betrand Meyer uses it as one of
>> the two parts of a function contract: The preconditions and the
>> postconditions.
>>
>> The first ones are the ones that the function requires from its
>> caller, and the second ones are the ones that the function
>> ensures to its users. They are part of the Eiffel language that Meyer
>> designed.
>
> Yes, I know a little about Eiffel.  My point it is that as soon as a
> condition moves from being part of the caller's contract to part of
> the function's responsibility,
> it stops being a precondition; it
> becomes part of the defined behaviour of the function.

There is "precondition (tm)" as in Eiffel, and then there is the basic 
concept that existed way before Eiffel showed up. B. Meyer didn't invent 
the concepts, and the concepts are what is important, not the 
terminology. The responsibility for usage does not "move". Would you 
really want to use a library that didn't do its due diligence in argument 
checking? You may have made one of those "programmer error" things and 
maybe the code would still "work", i.e., not crash, but be erroneous and 
maybe you'd catch it elsewhere or maybe not.
Maybe at one time lack of argument checking could have been considered a 
"quality of implementation" issue, but today (and long has been) that is 
a difference between professional code and Programming 101 student code.

[toc] | [prev] | [next] | [standalone]

#10371

"Tony" <nospamme@ever.net> writes:

> Ben Bacarisse wrote:
>> jacob navia <jacob@spamsink.net> writes:
>> <snip>
>>> Concerning the "preconditions" term, Betrand Meyer uses it as one of
>>> the two parts of a function contract: The preconditions and the
>>> postconditions.
>>>
>>> The first ones are the ones that the function requires from its
>>> caller, and the second ones are the ones that the function
>>> ensures to its users. They are part of the Eiffel language that Meyer
>>> designed.
>>
>> Yes, I know a little about Eiffel.  My point it is that as soon as a
>> condition moves from being part of the caller's contract to part of
>> the function's responsibility,
>> it stops being a precondition; it
>> becomes part of the defined behaviour of the function.
>
> There is "precondition (tm)" as in Eiffel, and then there is the basic 
> concept that existed way before Eiffel showed up. B. Meyer didn't invent 
> the concepts, and the concepts are what is important, not the 
> terminology. The responsibility for usage does not "move". Would you 
> really want to use a library that didn't do its due diligence in argument 
> checking? You may have made one of those "programmer error" things and 
> maybe the code would still "work", i.e., not crash, but be erroneous and 
> maybe you'd catch it elsewhere or maybe not.
> Maybe at one time lack of argument checking could have been considered a 
> "quality of implementation" issue, but today (and long has been) that is 
> a difference between professional code and Programming 101 student
> code.

How do conclude, from what I said, that I am advocating a lack of due
diligence or not checking arguments?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#10374

Ben Bacarisse wrote:
> "Tony" <nospamme@ever.net> writes:
>
>> Ben Bacarisse wrote:
>>> jacob navia <jacob@spamsink.net> writes:
>>> <snip>
>>>> Concerning the "preconditions" term, Betrand Meyer uses it as one
>>>> of the two parts of a function contract: The preconditions and the
>>>> postconditions.
>>>>
>>>> The first ones are the ones that the function requires from its
>>>> caller, and the second ones are the ones that the function
>>>> ensures to its users. They are part of the Eiffel language that
>>>> Meyer designed.
>>>
>>> Yes, I know a little about Eiffel.  My point it is that as soon as a
>>> condition moves from being part of the caller's contract to part of
>>> the function's responsibility,
>>> it stops being a precondition; it
>>> becomes part of the defined behaviour of the function.
>>
>> There is "precondition (tm)" as in Eiffel, and then there is the
>> basic concept that existed way before Eiffel showed up. B. Meyer
>> didn't invent the concepts, and the concepts are what is important,
>> not the terminology. The responsibility for usage does not "move".
>> Would you really want to use a library that didn't do its due
>> diligence in argument checking? You may have made one of those
>> "programmer error" things and maybe the code would still "work",
>> i.e., not crash, but be erroneous and maybe you'd catch it elsewhere
>> or maybe not.
>> Maybe at one time lack of argument checking could have been
>> considered a "quality of implementation" issue, but today (and long
>> has been) that is a difference between professional code and
>> Programming 101 student
>> code.
>
> How do conclude, from what I said, that I am advocating a lack of due
> diligence or not checking arguments?

By suggesting that documentation can preclude doing argument checking, 
thereby "throwing the problem over the wall" making it the programmer's 
problem for not reading "the directions". 

[toc] | [prev] | [next] | [standalone]

#10380

Le 17/09/11 05:15, Tony a écrit :
>>> Maybe at one time lack of argument checking could have been
>>> considered a "quality of implementation" issue, but today (and long
>>> has been) that is a difference between professional code and
>>> Programming 101 student
>>> code.
>>
Ben wrote:

>> How do conclude, from what I said, that I am advocating a lack of due
>> diligence or not checking arguments?
>
And Tony answered:
> By suggesting that documentation can preclude doing argument checking,
> thereby "throwing the problem over the wall" making it the programmer's
> problem for not reading "the directions".
>
>

Not all preconditions can be tested. For instance I proposed a routine
to test if a list is circular. It involves examining all the list.

If a library (like the C Containers library) would do that, its
performance would be close to zero.

And please do not forget that the routine to test the circularity of a
list`has its OWN preconditions too: the "next" pointers must be valid.

There is a point where testing everything becomes such a burden that it
is practically impossible and you *HAVE* to just write it down in the
documentation only.

[toc] | [prev] | [next] | [standalone]

#10383

"jacob navia" <jacob@spamsink.net> wrote in message 
news:j51bt5$3kg$1@speranza.aioe.org...
> Le 17/09/11 05:15, Tony a écrit :
>>>> Maybe at one time lack of argument checking could have been
>>>> considered a "quality of implementation" issue, but today (and long
>>>> has been) that is a difference between professional code and
>>>> Programming 101 student
>>>> code.
>>>
> Ben wrote:
>
>>> How do conclude, from what I said, that I am advocating a lack of due
>>> diligence or not checking arguments?
>>
> And Tony answered:
>> By suggesting that documentation can preclude doing argument checking,
>> thereby "throwing the problem over the wall" making it the 
>> programmer's
>> problem for not reading "the directions".
>>
>>
>
> Not all preconditions can be tested.

It seems to be a defintions (i.e., what is a "precondition"?) problem. 
See the other posts in this thread.

>  For instance I proposed a routine
> to test if a list is circular. It involves examining all the list.

I saw that and quickly guessed you were wanting an invariant, not a 
precondition.

>
> If a library (like the C Containers library) would do that, its
> performance would be close to zero.
>
> And please do not forget that the routine to test the circularity of a
> list`has its OWN preconditions too: the "next" pointers must be valid.

Again, that's a development-time thing to work out via assertions, 
invariants, etc.

>
> There is a point where testing everything becomes such a burden that it
> is practically impossible and you *HAVE* to just write it down in the
> documentation only.
>

Well, no, this is exactly the kind of thing I was saying is inacceptable. 
Sounds like "seat of the pants programming", and there is no way that is 
ever going to work effectively. Everything you can check, you must. Else 
reanalyze/redesign something if it seems "too heavy on the checking". 
Maybe "all that checking" is hinting for the reanalysis/redesign.

Take a look at the other posts I made in response to Ben so I don't have 
to repeat everything. Note my attempt at moving some things into the 
realm of "required guarantee" to distinguish from "precondition" just to 
make it clearer. 

[toc] | [prev] | [next] | [standalone]

#10399

On Sat, 17 Sep 2011 07:40:54 +0200, jacob navia <jacob@spamsink.net>
wrote:

>Le 17/09/11 05:15, Tony a écrit :
>>>> Maybe at one time lack of argument checking could have been
>>>> considered a "quality of implementation" issue, but today (and long
>>>> has been) that is a difference between professional code and
>>>> Programming 101 student
>>>> code.
>>>
>Ben wrote:
>
>>> How do conclude, from what I said, that I am advocating a lack of due
>>> diligence or not checking arguments?
>>
>And Tony answered:
>> By suggesting that documentation can preclude doing argument checking,
>> thereby "throwing the problem over the wall" making it the programmer's
>> problem for not reading "the directions".
>>
>>
>
>Not all preconditions can be tested. For instance I proposed a routine
>to test if a list is circular. It involves examining all the list.
>
>If a library (like the C Containers library) would do that, its
>performance would be close to zero.

Well, no, it wouldn't.  The cost of checking whether a linked list
terminates in a cycle is of the same order as the cost of reversing
the list.  One could even integrate cycle checking into the reversal
code.  If one does that one could also reverse a cycle terminated
linked list by defining the new head as the node that joined the
cycle.  I don't suppose you would want to do that but it could be done
cheaply enough.

[toc] | [prev] | [next] | [standalone]

#10400

Le 17/09/11 17:07, Richard Harter a écrit :
>
> Well, no, it wouldn't.  The cost of checking whether a linked list
> terminates in a cycle is of the same order as the cost of reversing
> the list.

Yes.

>  One could even integrate cycle checking into the reversal
> code.

This is a VERY good idea, I didn't even think about that but now
that you mention it, it is obvious.

Easy since we have already one pointer that goes through the list. We
could setup a second pointer, incrementing it twice as fast. This
would cost for a list of length N:

1) A test for pointer equality (N times)
2) A conditional jump (N times)
3) A test for NULL (N / 2 times)
4) An extra pointer dereferencing. (N / 2 times)

In a modern machine with a pipeline depth of 32 instructions (say)
the 1 and 2 would cost not even a cycle since the conditional branch
would be correctly predicted. For a pipeline depth of 32 it would
cost (2/32 --> 1/16 cycle)

The same analysis for 3: also a cost of 1/16 makes 1/8 cycle for
a pipeline depth of 32.

For 4 we have the extra cost of loading a cache line when
the "next" pointer dereferences data that is not in the cache.

For the worst case when the list is too big to fit into the L1 or L2
caches (several MB) we would double the cost of loading the list into
the cache, probably doubling the running time or more.

Mmmmmm... That would be the real show stopper.

> If one does that one could also reverse a cycle terminated
> linked list by defining the new head as the node that joined the
> cycle.  I don't suppose you would want to do that but it could be done
> cheaply enough.
>

More or less, see the analysis above. But it is a very good idea. I will
integrate it into the solved exercises.


Thank you very much for this contribution.

[toc] | [prev] | [next] | [standalone]

#10401

Le 17/09/11 17:47, jacob navia a écrit :
> The same analysis for 3: also a cost of 1/16 makes 1/8 cycle for
> a pipeline depth of 32.

No, (3) is done only N / 2 times since the pointer is incremented twice
as fast. Its cost is not 1/16 but 1/32.

We would have then 1/16 + 1/32 --> 3/32 approx 1/11 --> 0.1 cycle

[toc] | [prev] | [next] | [standalone]

Page 1 of 7  [1] 2 3 4 5 6 7  Next page →

Back to top | Article view | comp.lang.c

csiph-web