Is this legal

Discussion in 'C Programming' started by Nick, Nov 6, 2009.

  1. Nick

    Nick Guest

    I've been wrestling with my conscience over this one for several years
    now. This is a cut down example of some code I've written to iterate
    over any linked list as long as it satisfies a particular constraint.
    But is it actually legal? - I can't make my mind up.

    Here's roughly what it looks like. I could post the full code (it's
    actually a mergesort rather than an iterator) if this has silly errors
    in or doesn't explain it properly. But here goes:

    I have a header file (list_header.h)
    that just contains:

    typedef void list_function(void *l);
    void list_iterator(void *lst);

    and a list code file like this:

    #include "list_header.h"

    struct generic_list {
    struct generic_list *next;
    };

    void list_iterator(void *lst, list_function *lf) {
    struct generic_list *p = lst;
    while(*p) {
    lf(p);
    p = p->next;
    }
    }

    Then, whenever you want to iterate over a list you do:
    #include "list_header.h"

    struct thislist {
    struct thislist *next;
    ... lots of other fields ...
    } *reallist;

    void list_callback(void *l) {
    struct thislist *lp = l;
    ... do things with all the other fields in lp ...
    }

    and then, deep in the bowels of the code, after reallist has been made
    to point to a list of items
    list_iterator(reallist,list_callback);

    Now clearly if you ever use this with structures where the first item is
    not a pointer to a list item you are heading for every type of error and
    undefined behaviour.

    But if not, is this legal? The dodgy bit is casting a pointer to one
    type of list, via void, to another type of list and then dereferencing a
    field within it and expecting it to point to another list of the second
    type when it originally pointed to one of the first.

    On the other hand, all the stuff I can read about the equivalence of
    pointer suggests it just might be (it's clearly right on the border).
    It works, has worked on various compilers and OSs, but I know that
    proves absolutely nothing!

    Thoughts?
    --
    Online waterways route planner: http://canalplan.org.uk
    development version: http://canalplan.eu
     
    Nick, Nov 6, 2009
    #1
    1. Advertising

  2. On 6 nov, 16:28, Nick <> wrote:
    > I've been wrestling with my conscience over this one for several years
    > now.  This is a cut down example of some code I've written to iterate
    > over any linked list as long as it satisfies a particular constraint.
    > But is it actually legal? - I can't make my mind up.
    >
    > Here's roughly what it looks like.  I could post the full code (it's
    > actually a mergesort rather than an iterator) if this has silly errors
    > in or doesn't explain it properly.  But here goes:
    >
    > I have a header file (list_header.h)
    > that just contains:
    >
    > typedef void list_function(void *l);
    > void list_iterator(void *lst);
    >
    > and a list code file like this:
    >
    > #include "list_header.h"
    >
    > struct generic_list {
    >   struct generic_list *next;
    >
    > };
    >
    > void list_iterator(void *lst, list_function *lf) {
    >   struct generic_list *p = lst;
    >   while(*p) {
    >     lf(p);
    >     p = p->next;
    >   }
    >
    > }
    >
    > Then, whenever you want to iterate over a list you do:
    > #include "list_header.h"
    >
    > struct thislist {
    >   struct thislist *next;
    >   ... lots of other fields ...
    >
    > } *reallist;
    >
    > void list_callback(void *l) {
    >      struct thislist *lp = l;
    >      ... do things with all the other fields in lp ...
    >
    > }
    >
    > and then, deep in the bowels of the code, after reallist has been made
    > to point to a list of items
    > list_iterator(reallist,list_callback);
    >
    > Now clearly if you ever use this with structures where the first item is
    > not a pointer to a list item you are heading for every type of error and
    > undefined behaviour.
    >
    > But if not, is this legal?  The dodgy bit is casting a pointer to one
    > type of list, via void, to another type of list and then dereferencing a
    > field within it and expecting it to point to another list of the second
    > type when it originally pointed to one of the first.
    >
    > On the other hand, all the stuff I can read about the equivalence of
    > pointer suggests it just might be (it's clearly right on the border).
    > It works, has worked on various compilers and OSs, but I know that
    > proves absolutely nothing!
    >
    > Thoughts?
    > --
    > Online waterways route planner:http://canalplan.org.uk
    >            development version:http://canalplan.eu


    you probably want to write:
    void list_iterator(void *lst, list_function *lf) {
    struct generic_list *p = lst;
    while(p) { /* <========== */
    lf(p);
    p = p->next;
    }

    }
     
    nicolas.sitbon, Nov 6, 2009
    #2
    1. Advertising

  3. Nick

    Seebs Guest

    On 2009-11-06, Nick <> wrote:
    > I've been wrestling with my conscience over this one for several years
    > now. This is a cut down example of some code I've written to iterate
    > over any linked list as long as it satisfies a particular constraint.
    > But is it actually legal? - I can't make my mind up.


    I'm not sure about "legal", I prefer "conforming" -- legal is itself a
    term of art referring to the legal system.

    > typedef void list_function(void *l);
    > void list_iterator(void *lst);


    > and a list code file like this:
    >
    > #include "list_header.h"
    >
    > struct generic_list {
    > struct generic_list *next;
    > };
    >
    > void list_iterator(void *lst, list_function *lf) {


    Presumably the prototype matches, though.

    > But if not, is this legal? The dodgy bit is casting a pointer to one
    > type of list, via void, to another type of list and then dereferencing a
    > field within it and expecting it to point to another list of the second
    > type when it originally pointed to one of the first.


    So far as I can tell, this should be covered by "all struct pointers smell
    the same". All struct pointers have the same traits, and that means that
    a "struct foo *next;" as a first member is a common initial sequence, so
    the conversion from one to the other should preserve that common initial
    sequence.

    That said, someone (I've forgotten who already) recently pointed out a
    more elegant solution, using a "struct list" which is embedded in a
    structure anywhere you want. You iterate over the list, and when you
    have the list member you want, you then grab the pointer to the containing
    structure, because you know the offset of the "struct list" within that
    structure. (Note that the member of the structure is a struct list, NOT
    a struct list *.)

    -s
    --
    Copyright 2009, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Nov 6, 2009
    #3
  4. Nick

    Nick Guest

    Seebs <> writes:

    > So far as I can tell, this should be covered by "all struct pointers smell
    > the same". All struct pointers have the same traits, and that means that
    > a "struct foo *next;" as a first member is a common initial sequence, so
    > the conversion from one to the other should preserve that common initial
    > sequence.


    That's what I thought, but it's nice to have my opinion confirmed by a
    respected authority (well, respected by a long-term lurker like me,
    anyway).
    >
    > That said, someone (I've forgotten who already) recently pointed out a
    > more elegant solution, using a "struct list" which is embedded in a
    > structure anywhere you want. You iterate over the list, and when you
    > have the list member you want, you then grab the pointer to the containing
    > structure, because you know the offset of the "struct list" within that
    > structure. (Note that the member of the structure is a struct list, NOT
    > a struct list *.)


    That sounds interesting. There's the obvious generic list container (a
    struct with a next and a void pointer in it) but we're clearly not
    talking about that.

    At first I thought you wouldn't know where to find it, but of course the
    callback function knows what structure it's expecting, so can use
    offsetof to do it.

    Checking up on offsetof (I don't believe I've ever used it) I see that
    the Wikipedia article on it is an example of just this technique. It
    involves a particularly horrible cast to avoid the compiler subtracting
    an offsetof number of sizeof(structures) rather than bytes though.

    That's really rather neat indeed. I don't think I'll be rewriting my
    code, but I'll keep it in mind in case I ever have to do it again - it's
    clearly safer than having to put the "next" field in the right place.
    --
    Online waterways route planner: http://canalplan.org.uk
    development version: http://canalplan.eu
     
    Nick, Nov 6, 2009
    #4
  5. Nick

    Phil Carmody Guest

    Nick <> writes:
    > Seebs <> writes:
    >> So far as I can tell, this should be covered by "all struct pointers smell
    >> the same". All struct pointers have the same traits, and that means that
    >> a "struct foo *next;" as a first member is a common initial sequence, so
    >> the conversion from one to the other should preserve that common initial
    >> sequence.

    >
    > That's what I thought, but it's nice to have my opinion confirmed by a
    > respected authority (well, respected by a long-term lurker like me,
    > anyway).


    Alas the respected gentleman is mistaken. Confusing sprouts with onions?

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Nov 6, 2009
    #5
  6. On Fri, 06 Nov 2009 15:28:04 +0000, Nick
    <> wrote:

    >I've been wrestling with my conscience over this one for several years
    >now. This is a cut down example of some code I've written to iterate
    >over any linked list as long as it satisfies a particular constraint.
    >But is it actually legal? - I can't make my mind up.
    >
    >Here's roughly what it looks like. I could post the full code (it's
    >actually a mergesort rather than an iterator) if this has silly errors
    >in or doesn't explain it properly. But here goes:
    >
    >I have a header file (list_header.h)
    >that just contains:
    >
    >typedef void list_function(void *l);
    >void list_iterator(void *lst);
    >
    >and a list code file like this:
    >
    >#include "list_header.h"
    >
    >struct generic_list {
    > struct generic_list *next;
    >};
    >
    >void list_iterator(void *lst, list_function *lf) {
    > struct generic_list *p = lst;
    > while(*p) {
    > lf(p);
    > p = p->next;
    > }
    >}
    >
    >Then, whenever you want to iterate over a list you do:
    >#include "list_header.h"
    >
    >struct thislist {
    > struct thislist *next;
    > ... lots of other fields ...
    >} *reallist;
    >
    >void list_callback(void *l) {
    > struct thislist *lp = l;
    > ... do things with all the other fields in lp ...
    >}
    >
    >and then, deep in the bowels of the code, after reallist has been made
    >to point to a list of items


    If you mean that reallist has been assigned a value that is the
    address of a struct thislist, then all the implicit conversions
    between pointers to void and pointers to struct appear valid. Though
    not impossible, it would be an extremely perverse implementation that
    decided a struct generic_list required a more restrictive alignment
    than a struct thislist. If that were to be the case, the
    initialization in list_iterator could invoke undefined behavior,
    depending on the value of reallist.

    Similarly, if you ever set reallist to point to a struct thatlist
    which had less restrictive alignment than struct thislist, the
    initialization in list_callback could invoke undefined behavior.

    >list_iterator(reallist,list_callback);
    >
    >Now clearly if you ever use this with structures where the first item is
    >not a pointer to a list item you are heading for every type of error and
    >undefined behaviour.
    >
    >But if not, is this legal? The dodgy bit is casting a pointer to one
    >type of list, via void, to another type of list and then dereferencing a
    >field within it and expecting it to point to another list of the second
    >type when it originally pointed to one of the first.


    But that does not appear to be the case you describe. While the
    various pointers (both the parameter pointers to void and the local
    pointers to struct) have different types, at all times the value is
    the address of the "list of items" you mention.

    >
    >On the other hand, all the stuff I can read about the equivalence of
    >pointer suggests it just might be (it's clearly right on the border).
    >It works, has worked on various compilers and OSs, but I know that
    >proves absolutely nothing!


    --
    Remove del for email
     
    Barry Schwarz, Nov 6, 2009
    #6
    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. Valentin Tihomirov

    Is this legal?

    Valentin Tihomirov, Oct 21, 2003, in forum: VHDL
    Replies:
    20
    Views:
    1,258
    Jan Decaluwe
    Oct 29, 2003
  2. Divyang M
    Replies:
    9
    Views:
    639
    Divyang M
    May 18, 2005
  3. Divyang M
    Replies:
    1
    Views:
    574
    Jerzy Gbur
    May 15, 2005
  4. Weng Tianxiang
    Replies:
    12
    Views:
    1,410
  5. =?Utf-8?B?RGF2ZQ==?=

    Legal ViewState Characters

    =?Utf-8?B?RGF2ZQ==?=, May 24, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    372
    Patrice
    May 24, 2004
Loading...

Share This Page