Reversing a linked list

Discussion in 'C Programming' started by jacob navia, Sep 16, 2011.

  1. jacob navia

    jacob navia Guest

    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 }
     
    jacob navia, Sep 16, 2011
    #1
    1. Advertising

  2. jacob navia

    jacob navia Guest

    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.
     
    jacob navia, Sep 16, 2011
    #2
    1. Advertising

  3. jacob navia <> 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.
     
    Ben Bacarisse, Sep 16, 2011
    #3
  4. jacob navia

    jacob navia Guest

    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
     
    jacob navia, Sep 16, 2011
    #4
  5. jacob navia

    jacob navia Guest

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


    OOOPS, that should be:

    > rvpFast = rvpFast->Next;


    Sorry
     
    jacob navia, Sep 16, 2011
    #5
  6. On Sep 16, 3:26 pm, jacob navia <> 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
     
    Malcolm McLean, Sep 16, 2011
    #6
  7. jacob navia

    ImpalerCore Guest

    On Sep 16, 7:51 am, Ben Bacarisse <> wrote:
    > jacob navia <> writes:


    [snip]

    > > 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.


    From my perspective, a precondition for a function is independent of
    the method used to handle its violations. This is what contrasts the
    defensive programming from the design by contract paradigm. They both
    see the same function preconditions; they respond to them differently.

    Take 'size_t strlen( const char* str )' for example.

    \code
    size_t strlen( const char* str )
    {
    const char* s;

    for ( s = str; *s != '\0'; ++s )
    ;

    return s - str;
    }
    \endcode

    If I were to list the preconditions, I would say that 'str' must
    reference a character buffer and that buffer contain a terminating
    '\0' character. Some of these preconditions are testable, others are
    not (when a memory debugger is not present). It is difficult to
    impossible to verify whether a fixed-width buffer passed to strlen
    contains a '\0' without potentially generating a memory access
    violation.

    The de-facto error-handling method of much of the standard library is
    to do nothing, which in my opinion blends the precondition with its
    implicit response (nothing) to a precondition violation. In other
    languages like C++ or Eiffel, the response to precondition violations
    may result an exception, or violate some explicit contract.

    The point is that I believe it's a faulty view to combine a function's
    preconditions with how the module responds to them. For example, I
    see GLib's abundant use of g_return_if_fail macros as a defensive
    programming response to function preconditions.

    \code
    size_t strlen( const char* str )
    {
    const char* s;

    g_return_val_if_fail( str != NULL, 0 );

    for ( s = str; *s != '\0'; ++s )
    ;

    return s - str;
    }
    \endcode

    The 'assert' function is more like the design by contract approach by
    responding to a precondition violation by aborting the program.

    size_t strlen( const char* str )
    {
    const char* s;

    assert( str != NULL );

    for ( s = str; *s != '\0'; ++s )
    ;

    return s - str;
    }
    \endcode

    Best regards,
    John D.

    [snip]
     
    ImpalerCore, Sep 16, 2011
    #7
  8. jacob navia

    jacob navia Guest

    Le 16/09/11 16:21, ImpalerCore a écrit :
    > From my perspective, a precondition for a function is independent of
    > the method used to handle its violations. This is what contrasts the
    > defensive programming from the design by contract paradigm. They both
    > see the same function preconditions; they respond to them differently.
    >


    I would agree with that. For instance, "Reverse" needs a list with no
    cycles.

    It would be hugely expensive to test this precondition (I gave the code
    for the test in an answer to Ben) since implies going through all the
    list. But you are right that all the preconditions should be explicitely
    documented, even if untested in the code.

    The other precondition is that the list must be terminated by a NULL
    pointer and all the Next pointer must be valid.

    The first part can be easily tested with:

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

    This is cheap to do because the header structure stores a pointer
    to the last element. But if there is no pointer to the last element
    we have to go through the whole list, what makes testing for that
    precondition extremely expensive.

    I will add a commentary with this content to the preconditions
    part.

    Thanks for your input.
     
    jacob navia, Sep 16, 2011
    #8
  9. On Sep 16, 5:47 pm, jacob navia <> wrote:
    > But you are right that all the preconditions should be explicitely
    > documented, even if untested in the code.
    >

    Depends on the audience. For a proposed standard library, I agree.
    However in client code you can expect users to understand that linked
    lists will be NULL-terminated and cycle free. There is a problem with
    null pointers, which may be used to represent either the empty list or
    an invalid list.
    --
    Read my review of Atlas Shrugged
    http://www.malcolmmclean.site11.com/www
     
    Malcolm McLean, Sep 16, 2011
    #9
  10. jacob navia

    ImpalerCore Guest

    On Sep 16, 10:09 am, Malcolm McLean <>
    wrote:
    > On Sep 16, 3:26 pm, jacob navia <> 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.
     
    ImpalerCore, Sep 16, 2011
    #10
  11. On Sep 16, 6:28 pm, ImpalerCore <> 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
     
    Malcolm McLean, Sep 16, 2011
    #11
  12. In article <>,
    ImpalerCore <> 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,
    http://thespamdiaries.blogspot.com/
     
    Edward A. Falk, Sep 16, 2011
    #12
  13. jacob navia

    ImpalerCore Guest

    On Sep 16, 12:28 pm, Malcolm McLean <>
    wrote:
    > On Sep 16, 6:28 pm, ImpalerCore <> 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.
     
    ImpalerCore, Sep 16, 2011
    #13
  14. jacob navia <> 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.
     
    Ben Bacarisse, Sep 16, 2011
    #14
  15. On Sep 16, 2:30 am, jacob navia <> wrote:
    > 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 }


    A recursive function is a lot more readable, plus more elegant.

    void reverse_list(ListElement *head)
    {
    if (head == NULL) return;

    __reverse_list(head->next, head);

    return;
    }

    void __reverse_list(ListElement *next, ListElement *this)
    {
    if (this == NULL) return;

    if (next->next) __reverse_list(next, next->next);

    next->next = this;
    return;
    }
     
    HENRY Eshbaugh, Sep 17, 2011
    #15
  16. jacob navia

    Ian Collins Guest

    On 09/17/11 11:56 AM, HENRY Eshbaugh wrote:
    >
    > A recursive function is a lot more readable, plus more elegant.
    >
    > void reverse_list(ListElement *head)
    > {
    > if (head == NULL) return;
    >
    > __reverse_list(head->next, head);


    You shouldn't use names starting with a double underscore, they are
    reserved for the implementation.

    > return;
    > }
    >
    > void __reverse_list(ListElement *next, ListElement *this)
    > {
    > if (this == NULL) return;
    >
    > if (next->next) __reverse_list(next, next->next);
    >
    > next->next = this;
    > return;
    > }



    --
    Ian Collins
     
    Ian Collins, Sep 17, 2011
    #16
  17. jacob navia

    Tony Guest

    "jacob navia" <> wrote in message
    news:j4uqda$dqt$...
    > 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.


    Wishful thinking? The truth is surely that C/C++ are well within the
    black hole now with no chance of escaping its mighty pull.

    [snipped "foundations of data structures and algorithms" stuff]

    How is "foundations of data structures and algorithms" (via YOUR library,
    no less) on topic? Are you not tryig to commandiere this NG to your
    personal agenda? Should all library vendors start posting examples in
    here about usage of their products? See the point?
     
    Tony, Sep 17, 2011
    #17
  18. jacob navia

    Tony Guest

    "Ben Bacarisse" <> wrote in message
    news:...
    > jacob navia <> writes:


    >> 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.


    That would be living dangerously indeed. That kind of programming went
    out in the, er, well apparently it hasn't, for you are still doing that!

    > 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.


    No it doesn't. It just means that when someone violates the precondition,
    something controlled and defined happens rather than "anything can
    happen". All arguments to public functions need to be verified*.

    *Their are techniques that can be used sometimes to ensure that arguments
    cannot be wrong and therefore need not be checked. Those functions are
    great when you find/create them and worth the effort looking for.

    > 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.


    No. (I'm not referring to B. Meyer's definitions though, but rather my
    own).

    >
    > Since this is a teaching exercise,


    Of questionable appropriateness in the NG. (Read, I questioned its
    appropriateness).
     
    Tony, Sep 17, 2011
    #18
  19. jacob navia

    Tony Guest

    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?
     
    Tony, Sep 17, 2011
    #19
  20. HENRY Eshbaugh <> writes:
    <snip>
    > A recursive function is a lot more readable, plus more elegant.
    >
    > void reverse_list(ListElement *head)
    > {
    > if (head == NULL) return;
    >
    > __reverse_list(head->next, head);
    >
    > return;
    > }
    >
    > void __reverse_list(ListElement *next, ListElement *this)
    > {
    > if (this == NULL) return;
    >
    > if (next->next) __reverse_list(next, next->next);
    >
    > next->next = this;
    > return;
    > }


    Readable, elegant, correct: pick any two!

    --
    Ben.
     
    Ben Bacarisse, Sep 17, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    511
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    501
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    542
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    701
    John Carson
    Oct 2, 2006
  5. saki

    Reversing a singly linked list

    saki, Jul 4, 2008, in forum: C Programming
    Replies:
    2
    Views:
    445
Loading...

Share This Page