Yet another binary search tree library

Discussion in 'C Programming' started by Franck Bui-Huu, Jul 1, 2010.

  1. Hello,

    I've finally made available some C code I wrote dealing about
    (balanced)
    binary search trees. It currently implements BST, AVL, Red-Black and
    Splay trees and may be useful for others developers.

    The API is slightly different from what I've seen so far and I would
    be interested to get some feedback from the C community before
    releasing anything.

    Basically I tried to make the API as simple as I can and the node
    structure sizes as small as possible.

    The README tries to explain the design, so please, have a look at it
    if
    you're interested.

    You can read the code from:

    http://github.com/fbuihuu/libtree

    or download it by using git(1):

    $ git clone git://github.com/fbuihuu/libtree.git

    Thanks
    --
    Franck
    Franck Bui-Huu, Jul 1, 2010
    #1
    1. Advertising

  2. On Thu, 1 Jul 2010, Franck Bui-Huu wrote:

    > The README tries to explain the design, so please, have a look at it if
    > you're interested.
    >
    > You can read the code from:
    >
    > http://github.com/fbuihuu/libtree


    "Nodes of the tree aims to be embedded inside your own structure. [...]
    The idea is borrowed from the Linux kernel."

    How do you link a specific object into an arbitrary number of trees?

    struct object;

    struct backref
    {
    struct avltree_node node;
    key_type key_for_this_tree;
    struct object *obj;
    };

    struct object
    {
    struct backref *refs;
    /* ... */
    }

    The tree lookup function probably returns the address of a backref object,
    which links back to the real object. Isn't that cumbersome? Or is there a
    better way?

    Furthermore, I see this example:

    struct my_struct {
    int key;
    struct avltree_node node;
    };

    The tree node is not the first member. So I think (no time to verify now,
    sorry) the special exception of casting (struct my_struct *) to (struct
    avltree_node *) and back doesn't apply. You might try to work that around
    with offsetof() and whatnot, but doesn't that break strict aliasing rules?

    Thanks,
    lacos
    Ersek, Laszlo, Jul 1, 2010
    #2
    1. Advertising

  3. On Jul 1, 5:27 pm, Franck Bui-Huu <> wrote:
    > Hello,
    >
    > I've finally made available some C code I wrote dealing about
    > (balanced)
    > binary search trees. It currently implements BST, AVL, Red-Black and
    > Splay trees and may be useful for others developers.
    >
    > The API is slightly different from what I've seen so far and I would
    > be interested to get some feedback from the C community before
    > releasing anything.
    >

    I'd make the API

    REDBLACKTREE * - opaque pointer type

    REDBLACKTREE *rbtree_constr(size_t elsize, const void *(*getkey)(const
    void *obj), int (*compfunc)(const void *key1, const void *key2), int
    capacityhint);
    void rbtree_destr(REDBLACTREE *rbt);
    int rbtree_insert(REDBLACTREE *rbt, void *data);
    int rbtree_delete(REDBLACKTREE *rbt, const void *key);
    void *rbtree_get(REDBLACKTREE *rbt, const void *key);

    Don't expose nodes to the user.

    getkey - returns a key given a data element. (usually just a utility
    to return a pointer to one of the fields of a struct).
    compfunc - qsort style key comparison function.
    capacityhint - how many elements the tree is likely to contain
    (preallocate memory for them). The tree will expand if this is
    exceeded. 0 = don't know/don't care.


    Here's a sample of how to use.

    #include <stdio.h>
    #include "libtree.h"

    typedef struct
    {
    char name[32];
    float salary;
    } EMPLOYEE;

    void *getkey(const void *obj)
    {
    EMPLOYEE *e = obj;
    return e->name;
    }

    int compfunc(const void *k1, const void *k2)
    {
    const char *s1 = k1;
    const char *s2 = k2;
    return strcmp(s1, s2);
    }

    int main(void)
    {
    EMPLOYEE e;
    REDBLACKTREE *tree;
    int i;
    EMPLOYEE *fred32;

    tree = rbtree_constr(sizeof(EMPLOYEE), getkey, compfunc, 50);
    for(i=0;i<100;i++)
    {
    sprintf(e.name, "Fred%d", i);
    e.salary = i * 100;
    err = rbtree_insert(tree, &e);
    if(err < 0)
    fprintf(stderr, "Out of memory\n");
    }
    fred32 = rbtree_get(tree, "Fred32");
    printf("%s %f\n", fred32->name, fred32->salary);
    fred32->salary = 1234567.0;
    fred32 = rbtree_get(tree, "Fred32");
    printf("%s %f\n", fred32->name, fred32->salary);
    err = rbtree_delete(tree, "Fred32");
    fred32 = rbtree_get(tree, "Fred32");
    printf("err %d %p\n", err, (void *) fred32);
    err = rbtree_delete(tree, "Fred32");
    printf("err %d (Fred is now dead)\n", err);
    rbtree_destr(tree);

    return 0;
    }
    Malcolm McLean, Jul 1, 2010
    #3
  4. On Thu, 1 Jul 2010, Malcolm McLean wrote:


    > Don't expose nodes to the user.


    [...]

    > typedef struct
    > {
    > char name[32];
    > float salary;
    > } EMPLOYEE;



    IIUC, it was important for the OP to embed nodes in user-declared structs.
    For that the node type must be complete in the user's translation units.

    lacos
    Ersek, Laszlo, Jul 1, 2010
    #4
  5. "Ersek, Laszlo" <> writes:

    > On Thu, 1 Jul 2010, Franck Bui-Huu wrote:
    >
    >> The README tries to explain the design, so please, have a look at it
    >> if you're interested.
    >>
    >> You can read the code from:
    >>
    >> http://github.com/fbuihuu/libtree

    >
    > "Nodes of the tree aims to be embedded inside your own
    > structure. [...] The idea is borrowed from the Linux kernel."
    >
    > How do you link a specific object into an arbitrary number of trees?
    >
    >
    > struct object;
    >
    > struct backref
    > {
    > struct avltree_node node;
    > key_type key_for_this_tree;
    > struct object *obj;
    > };
    >
    > struct object
    > {
    > struct backref *refs;
    > /* ... */
    > }
    >
    > The tree lookup function probably returns the address of a backref
    > object, which links back to the real object. Isn't that cumbersome? Or
    > is there a better way?
    >
    > Furthermore, I see this example:
    >
    > struct my_struct {
    > int key;
    > struct avltree_node node;
    > };
    >
    > The tree node is not the first member. So I think (no time to verify
    > now, sorry) the special exception of casting (struct my_struct *) to
    > (struct avltree_node *) and back doesn't apply. You might try to work
    > that around with offsetof() and whatnot, but doesn't that break strict
    > aliasing rules?


    Well I think the README should be rewritten...

    Let me try again.

    In your example, I think you tried to use an AVL tree to keep track of
    objects of type 'struct object'. In order to do so, 'struct object'
    must
    embed an AVL node whose type is 'struct avltree_node'.

    For example:

    struct object {
    /* ... */
    int key;
    struct avltree_node node;
    };

    Then to insert this object into an initialized tree, you do:

    struct object *obj;
    /* initialize 'obj' */
    obj->key = 4;
    avltree_insert(&obj->node, tree);

    Then later you need to search for the previously inserted object whose
    key is 4:

    struct object dummy = { .key = 4 };
    struct avltree_node *the_node;

    the_node = avltree_lookup(&dummy, tree);
    if (!the_node) {
    /* not found ! */
    ...
    }
    /* found */

    As you noticed avltree_lookup() returns a pointer to 'struct
    avltree_node' (not struct object) that is a pointer that points to the
    member 'node' which belongs to the previously inserted object.

    Not really convenient at this point, but the library provides an
    helper
    that you can use to retrieve the object address:

    struct object *the_obj;
    the_obj = avltree_container_of(the_node, struct object , node);
    assert(the_obj->key == 4);

    Hope this example help clarify things.
    --
    Franck
    Franck Bui-Huu, Jul 1, 2010
    #5
  6. On Thu, 1 Jul 2010, Franck Bui-Huu wrote:

    > Well I think the README should be rewritten...


    I don't think so. Especially because I only read the first paragraph or so
    :)


    > In your example, I think you tried to use an AVL tree to keep track of
    > objects of type 'struct object'.


    Yes.

    I'll snip most of what you wrote because I did understand that before.
    I'll keep the parts which I find problematic.

    > struct object {
    > /* ... */
    > int key;
    > struct avltree_node node;
    > };
    >


    > Then later you need to search for the previously inserted object whose
    > key is 4:
    >
    > struct object dummy = { .key = 4 };
    > struct avltree_node *the_node;
    >
    > the_node = avltree_lookup(&dummy, tree);
    > if (!the_node) {
    > /* not found ! */
    > ...
    > }
    > /* found */
    >
    > As you noticed avltree_lookup() returns a pointer to 'struct
    > avltree_node' (not struct object) that is a pointer that points to the
    > member 'node' which belongs to the previously inserted object.
    >
    > Not really convenient at this point, but the library provides an helper
    > that you can use to retrieve the object address:
    >
    > struct object *the_obj;
    > the_obj = avltree_container_of(the_node, struct object , node);
    > assert(the_obj->key == 4);


    Therein lies my problem:

    #define avltree_container_of(node, type, member) ({ \
    const struct avltree_node *__mptr = (node); \
    (type *)( (char *)__mptr - offsetof(type,member) );})

    First, as a side note (because this is not my main concern), you state in
    the README, "[...] the library still provides an implementation which is
    fully portable (C99) [...]". The above statement-expression is a GNU C
    extension, not C99.

    Second (my main concern), I suspect that this breaks strict aliasing
    rules. That is, after the avltree_container_of() function-like macro is
    expanded and the (statement-)expression is evaluated, you end up with two
    pointers, namely "the_node" and "the_obj". They point to storage that
    overlaps, and none of them was computed from the other by following
    pointers and taking addresses of members.

    That is, you have two pointers to different types, the pointed-to areas
    overlap, and you obtained one of the pointers by type-punning (when you
    cast the pointer-to-char to pointer-to-type). Consequently, I suspect the
    compiler is allowed to assume that the objects below those pointers are
    distinct, which is in reality not the case.

    C99 6.7.2.1 p13 says, "[...] A pointer to a structure object, suitably
    converted, points to its initial member [...], and vice versa. [...]".
    Similar language can be found in C89 6.5.2.1.

    Since "node" is not the initial member of "struct object", you have to
    resort to offsetof(), instead of converting back the pointer explicitly,
    but this way you can't rely on the guarantee of the cited paragraph.

    That's why I wrote:

    >> Furthermore, I see this example:
    >>
    >> struct my_struct {
    >> int key;
    >> struct avltree_node node;
    >> };
    >>
    >> The tree node is not the first member. So I think (no time to verify
    >> now, sorry) the special exception of casting (struct my_struct *) to
    >> (struct avltree_node *) and back doesn't apply. You might try to work
    >> that around with offsetof() and whatnot, but doesn't that break strict
    >> aliasing rules?



    Third, sometimes you wish to refer to an object from multiple trees.
    Suppose you have a set of cars, and you want to order them based on
    different attributes (organize them into multiple red-black trees) at the
    same time. You want to store each "car" only once, but you want to search
    (and traverse) them based on peak torque, peak performance, price, fuel
    consumption, and so on. So you'd need (at least) four trees.

    struct car {
    struct rbtree_node nm_tree_node,
    kw_tree_node,
    bucks_tree_node,
    mpg_tree_node; /* mileage, to appease our imperial readers */

    double nm,
    kw;
    long unsigned bucks;
    double mpg;
    };

    We immediately hit the problem of "kw_tree_node", "bucks_tree_node",
    "mpg_tree_node" being non-initial members (see my suspicion of the
    offsetof() problem). Ignoring that, the comparison functions do work,
    because they each trace back from the node address to the enclosing
    "struct car" and access the corresponding key field.

    However, suppose we want to maintain a dynamic list of attributes for each
    car, and to add each car to a respective dynamic set of trees.

    struct attr {
    const char *name;
    enum {
    AT_D,
    AT_LU
    } type;
    union {
    double d;
    long unsigned lu;
    } value;
    };

    struct car2 {
    size_t num_attrs;

    /* car2 is referred to by "num_attrs" trees */
    struct rbtree_node *nodes_in_referring_trees;

    /* car2 has "num_attrs" attributes */
    struct attr *attrs;
    };


    This can work, but then the comparison function (or anything else) cannot
    use the offsetof() trick *at all*, since the tree nodes for a car2 object
    are allocated completely separately from the car2 object itself (ie. with
    different malloc() calls).

    To enable the comparison function (or anything else) to get back to the
    object, you'd have to extend the node type with a pointer-to-void member.

    (Or to embed the node type in a bigger type as its initial member -- this
    was the idea in my earlier followup:

    >> struct backref
    >> {
    >> struct avltree_node node;
    >> /* key_type key_for_this_tree; -- this was unnecessary, granted */
    >> struct object *obj;
    >> };


    >> struct object
    >> {
    >> struct backref *refs;
    >> /* ... */
    >> }



    In summary, in my humble opinion,

    (1) the offsetof() trick is not portable, with or without the
    statement-expression,

    (2) if you want to add an object to a dynamically determined set of trees,
    you have to do away with the offsetof() trick completely and maintain
    backreferences. Consequences:

    (2a) The code becomes portable (additionally without the
    statement-expression),

    (2b) The code (the client code, the comparison function etc) becomes so
    unwieldy that you'd be better off with "regular" nodes that are not
    embedded into the client structs but hold a pointer to them.

    Whenever objects are added only to a fixed set (or limited number) of
    trees, and the platform ensures the offsetof() trick, like it probably is
    the case with the Linux kernel and gcc, then the idea does save a malloc()
    (= a node per object per referring tree).


    If I'm wrong, I'd like to be corrected very much.

    Thanks,
    lacos
    Ersek, Laszlo, Jul 1, 2010
    #6
  7. On Jul 1, 7:06 pm, "Ersek, Laszlo" <> wrote:
    > On Thu, 1 Jul 2010, Malcolm McLean wrote:
    > > Don't expose nodes to the user.

    >
    > [...]
    >
    > > typedef struct
    > > {
    > >  char name[32];
    > >  float salary;
    > > } EMPLOYEE;

    >
    > IIUC, it was important for the OP to embed nodes in user-declared structs..
    > For that the node type must be complete in the user's translation units.
    >

    And actually my interface has serious deficiencies. It's OK for simple
    structs where you maintain a list of keys, but not for anything else.
    On the other hand embedding node structures in client code is a
    horrible way to use a container.
    Malcolm McLean, Jul 2, 2010
    #7
  8. "Ersek, Laszlo" <> writes:

    [...]

    >>
    >> struct object *the_obj;
    >> the_obj = avltree_container_of(the_node, struct object , node);
    >> assert(the_obj->key == 4);

    >
    > Therein lies my problem:
    >
    > #define avltree_container_of(node, type, member) ({ \
    > const struct avltree_node *__mptr = (node); \
    > (type *)( (char *)__mptr - offsetof(type,member) );})
    >
    > First, as a side note (because this is not my main concern), you state
    > in the README, "[...] the library still provides an implementation
    > which is fully portable (C99) [...]". The above statement-expression
    > is a GNU C extension, not C99.


    That's true, I completly forgot about this.

    The current definition is using GNU C extension to perform type
    checking. I don't see any ways to write this in portable C99 and still
    to keep the type checking...

    So I guess I will add this simpler but portable definition for non gcc
    users:

    #define avltree_container_of(node, type, member) \
    (type *)((char *)(node) - offsetof(type,member))

    thanks for spotting this out.

    >
    > Second (my main concern), I suspect that this breaks strict aliasing
    > rules. That is, after the avltree_container_of() function-like macro
    > is expanded and the (statement-)expression is evaluated, you end up
    > with two pointers, namely "the_node" and "the_obj". They point to
    > storage that overlaps, and none of them was computed from the other by
    > following pointers and taking addresses of members.
    >
    > That is, you have two pointers to different types, the pointed-to
    > areas overlap, and you obtained one of the pointers by type-punning
    > (when you cast the pointer-to-char to pointer-to-type).


    Not sure to understand this since type punning is more than a conversion
    of pointers of different type: you need to deference the converted
    pointer.

    > Consequently, I suspect the compiler is allowed to assume that the
    > objects below those pointers are distinct, which is in reality not the
    > case.
    >
    > C99 6.7.2.1 p13 says, "[...] A pointer to a structure object, suitably
    > converted, points to its initial member [...], and vice
    > versa. [...]". Similar language can be found in C89 6.5.2.1.
    >
    > Since "node" is not the initial member of "struct object", you have to
    > resort to offsetof(), instead of converting back the pointer
    > explicitly, but this way you can't rely on the guarantee of the cited
    > paragraph.
    >
    > That's why I wrote:
    >
    >>> Furthermore, I see this example:
    >>>
    >>> struct my_struct {
    >>> int key;
    >>> struct avltree_node node;
    >>> };
    >>>
    >>> The tree node is not the first member. So I think (no time to
    >>> verify now, sorry) the special exception of casting (struct
    >>> my_struct *) to (struct avltree_node *) and back doesn't apply. You
    >>> might try to work that around with offsetof() and whatnot, but
    >>> doesn't that break strict aliasing rules?


    OK, so let's try to answer to your second issue.

    First let's stick with the portable definition of
    avltree_container_of().

    Second, let's define a new type 'struct my_struct' having a member
    'my_node' of type 'struct avltree_node' which is not the first member.

    struct my_struct {
    int a, b, c;
    struct avltree_node my_node;
    short d;
    };

    and 'obj' an object of that type:

    struct my_struct obj;

    and 'node' a pointer to 'my_node' member:

    struct avltree_node *node = &obj.my_node;

    Now let's use avltree_container_of():

    avltree_container_of(node, struct my_struct, my_node);

    and see what's really going on:

    (struct my_struct *)((char *)node - offsetof(struct my_struct, my_node));

    First of all 'node' pointer is converted to (char *) and the result
    points to the lowest addressed byte of 'my_node' and has pointer to char
    type.

    Then offsetof(...) yields to an integer which is the offset in bytes, to
    the structure member 'my_node', from the beginning of its structure.

    Therefore,

    (char *)node - offsetof(...)

    results to the address of the beginning of the structure (whose type is
    'struct my_struct) containing the member 'my_node' pointed by 'node'.

    So by definition we can assume that this address is correctly aligned for
    accessing an object of type 'struct my_struct'. Therefore we can safely
    convert back this address to (struct my_struct *).

    And since we know that the effective type of the underlying object is
    'struct my_struct', it's safe to deference the converted pointer.

    So to sum up, I think:

    struct my_struct obj;
    char *p = (char *)&obj;
    p += offsetof(struct my_struct, my_node);
    p -= offsetof(struct my_struct, my_node);
    ((struct my_struct *)p)->a;

    is a defined case of type punning.

    >
    > Third, sometimes you wish to refer to an object from multiple
    > trees. Suppose you have a set of cars, and you want to order them
    > based on different attributes (organize them into multiple red-black
    > trees) at the same time. You want to store each "car" only once, but
    > you want to search (and traverse) them based on peak torque, peak
    > performance, price, fuel consumption, and so on. So you'd need (at
    > least) four trees.
    >
    > struct car {
    > struct rbtree_node nm_tree_node,
    > kw_tree_node,
    > bucks_tree_node,
    > mpg_tree_node; /* mileage, to appease our imperial readers */
    >
    > double nm,
    > kw;
    > long unsigned bucks;
    > double mpg;
    > };
    >
    > We immediately hit the problem of "kw_tree_node", "bucks_tree_node",
    > "mpg_tree_node" being non-initial members (see my suspicion of the
    > offsetof() problem). Ignoring that, the comparison functions do work,
    > because they each trace back from the node address to the enclosing
    > "struct car" and access the corresponding key field.
    >
    > However, suppose we want to maintain a dynamic list of attributes for
    > each car, and to add each car to a respective dynamic set of trees.
    >
    > struct attr {
    > const char *name;
    > enum {
    > AT_D,
    > AT_LU
    > } type;
    > union {
    > double d;
    > long unsigned lu;
    > } value;
    > };
    >
    > struct car2 {
    > size_t num_attrs;
    >
    > /* car2 is referred to by "num_attrs" trees */
    > struct rbtree_node *nodes_in_referring_trees;
    >
    > /* car2 has "num_attrs" attributes */
    > struct attr *attrs;
    > };
    >
    >
    > This can work, but then the comparison function (or anything else)
    > cannot use the offsetof() trick *at all*, since the tree nodes for a
    > car2 object are allocated completely separately from the car2 object
    > itself (ie. with different malloc() calls).


    Sure since node structure must be embedded (this is _the_ requirement at
    the beginning).

    I won't try to answer because I don't see what you're trying to achieve,
    sorry.

    Thanks for your comments.
    --
    Franck
    Franck Bui-Huu, Jul 2, 2010
    #8
  9. Franck Bui-Huu

    James Waldby Guest

    On Thu, 01 Jul 2010 07:27:54 -0700, Franck Bui-Huu wrote:
    > I've finally made available some C code I wrote dealing about (balanced)
    > binary search trees. It currently implements BST, AVL, Red-Black and
    > Splay trees and may be useful for others developers.

    [snip API and README notes]

    [c.l.c OT] You might also implement AA trees, which code up
    quite cleanly and perform similarly to RB trees. See for
    example <http://en.wikipedia.org/wiki/AA_tree>.

    > You can read the code from:
    > http://github.com/fbuihuu/libtree
    > or download it by using git(1):
    > $ git clone git://github.com/fbuihuu/libtree.git


    --
    jiw
    James Waldby, Jul 6, 2010
    #9
  10. Franck Bui-Huu

    Tim Rentsch Guest

    Franck Bui-Huu <> writes:

    > "Ersek, Laszlo" <> writes:
    >
    > [...]
    >
    >>>
    >>> struct object *the_obj;
    >>> the_obj = avltree_container_of(the_node, struct object , node);
    >>> assert(the_obj->key == 4);

    >>
    >> Therein lies my problem:
    >>
    >> #define avltree_container_of(node, type, member) ({ \
    >> const struct avltree_node *__mptr = (node); \
    >> (type *)( (char *)__mptr - offsetof(type,member) );})
    >>
    >> First, as a side note (because this is not my main concern), you state
    >> in the README, "[...] the library still provides an implementation
    >> which is fully portable (C99) [...]". The above statement-expression
    >> is a GNU C extension, not C99.

    >
    > That's true, I completly forgot about this.
    >
    > The current definition is using GNU C extension to perform type
    > checking. I don't see any ways to write this in portable C99 and still
    > to keep the type checking...
    >
    > So I guess I will add this simpler but portable definition for non gcc
    > users:
    >
    > #define avltree_container_of(node, type, member) \
    > (type *)((char *)(node) - offsetof(type,member))
    >
    > thanks for spotting this out.
    >
    >>
    >> Second (my main concern), I suspect that this breaks strict aliasing
    >> rules. That is, after the avltree_container_of() function-like macro
    >> is expanded and the (statement-)expression is evaluated, you end up
    >> with two pointers, namely "the_node" and "the_obj". They point to
    >> storage that overlaps, and none of them was computed from the other by
    >> following pointers and taking addresses of members.
    >>
    >> That is, you have two pointers to different types, the pointed-to
    >> areas overlap, and you obtained one of the pointers by type-punning
    >> (when you cast the pointer-to-char to pointer-to-type).

    >
    > Not sure to understand this since type punning is more than a conversion
    > of pointers of different type: you need to deference the converted
    > pointer.
    >
    >> Consequently, I suspect the compiler is allowed to assume that the
    >> objects below those pointers are distinct, which is in reality not the
    >> case.
    >>
    >> C99 6.7.2.1 p13 says, "[...] A pointer to a structure object, suitably
    >> converted, points to its initial member [...], and vice
    >> versa. [...]". Similar language can be found in C89 6.5.2.1.
    >>
    >> Since "node" is not the initial member of "struct object", you have to
    >> resort to offsetof(), instead of converting back the pointer
    >> explicitly, but this way you can't rely on the guarantee of the cited
    >> paragraph.
    >>
    >> That's why I wrote:
    >>
    >>>> Furthermore, I see this example:
    >>>>
    >>>> struct my_struct {
    >>>> int key;
    >>>> struct avltree_node node;
    >>>> };
    >>>>
    >>>> The tree node is not the first member. So I think (no time to
    >>>> verify now, sorry) the special exception of casting (struct
    >>>> my_struct *) to (struct avltree_node *) and back doesn't apply. You
    >>>> might try to work that around with offsetof() and whatnot, but
    >>>> doesn't that break strict aliasing rules?

    >
    > OK, so let's try to answer to your second issue.
    >
    > First let's stick with the portable definition of
    > avltree_container_of().
    >
    > Second, let's define a new type 'struct my_struct' having a member
    > 'my_node' of type 'struct avltree_node' which is not the first member.
    >
    > struct my_struct {
    > int a, b, c;
    > struct avltree_node my_node;
    > short d;
    > };
    >
    > and 'obj' an object of that type:
    >
    > struct my_struct obj;
    >
    > and 'node' a pointer to 'my_node' member:
    >
    > struct avltree_node *node = &obj.my_node;
    >
    > Now let's use avltree_container_of():
    >
    > avltree_container_of(node, struct my_struct, my_node);
    >
    > and see what's really going on:
    >
    > (struct my_struct *)((char *)node - offsetof(struct my_struct, my_node));
    >
    > First of all 'node' pointer is converted to (char *) and the result
    > points to the lowest addressed byte of 'my_node' and has pointer to char
    > type.
    >
    > Then offsetof(...) yields to an integer which is the offset in bytes, to
    > the structure member 'my_node', from the beginning of its structure.
    >
    > Therefore,
    >
    > (char *)node - offsetof(...)
    >
    > results to the address of the beginning of the structure (whose type is
    > 'struct my_struct) containing the member 'my_node' pointed by 'node'.
    >
    > So by definition we can assume that this address is correctly aligned for
    > accessing an object of type 'struct my_struct'. Therefore we can safely
    > convert back this address to (struct my_struct *).
    >
    > And since we know that the effective type of the underlying object is
    > 'struct my_struct', it's safe to deference the converted pointer.


    Right.

    > So to sum up, I think:
    >
    > struct my_struct obj;
    > char *p = (char *)&obj;
    > p += offsetof(struct my_struct, my_node);
    > p -= offsetof(struct my_struct, my_node);
    > ((struct my_struct *)p)->a;
    >
    > is a defined case of type punning.


    Actually there isn't any type punning going on here, since the
    types used to reference objects are the same in each case that
    the respective object actually holds. (And ignoring that member
    'a' hasn't been initialized, which is orthogonal to the question
    of type punning.) Type punning refers to the case when a region
    of memory has been stored (or perhaps declared) using one type,
    then accessed using another. That hasn't happened here. The
    pointer conversions are legal and portable, but the converted
    pointers are accessing objects whose types match those of the
    access in each case -- ergo, no type punning.
    Tim Rentsch, Jul 14, 2010
    #10
  11. On Wed, 14 Jul 2010, Tim Rentsch wrote:

    > Franck Bui-Huu <> writes:
    >
    >> "Ersek, Laszlo" <> writes:
    >>
    >>>>
    >>>> struct object *the_obj;
    >>>> the_obj = avltree_container_of(the_node, struct object , node);
    >>>> assert(the_obj->key == 4);
    >>>
    >>> Therein lies my problem:
    >>>
    >>> #define avltree_container_of(node, type, member) ({ \
    >>> const struct avltree_node *__mptr = (node); \
    >>> (type *)( (char *)__mptr - offsetof(type,member) );})
    >>>


    [snip]

    >>> Second (my main concern), I suspect that this breaks strict aliasing
    >>> rules. That is, after the avltree_container_of() function-like macro
    >>> is expanded and the (statement-)expression is evaluated, you end up
    >>> with two pointers, namely "the_node" and "the_obj". They point to
    >>> storage that overlaps, and none of them was computed from the other by
    >>> following pointers and taking addresses of members.
    >>>
    >>> That is, you have two pointers to different types, the pointed-to
    >>> areas overlap, and you obtained one of the pointers by type-punning
    >>> (when you cast the pointer-to-char to pointer-to-type).


    [snip]

    >> Therefore,
    >>
    >> (char *)node - offsetof(...)
    >>
    >> results to the address of the beginning of the structure (whose type is
    >> 'struct my_struct) containing the member 'my_node' pointed by 'node'.
    >>
    >> So by definition we can assume that this address is correctly aligned
    >> for accessing an object of type 'struct my_struct'. Therefore we can
    >> safely convert back this address to (struct my_struct *).
    >>
    >> And since we know that the effective type of the underlying object is
    >> 'struct my_struct', it's safe to deference the converted pointer.

    >
    > Right.
    >
    >> So to sum up, I think:
    >>
    >> struct my_struct obj;
    >> char *p = (char *)&obj;
    >> p += offsetof(struct my_struct, my_node);
    >> p -= offsetof(struct my_struct, my_node);
    >> ((struct my_struct *)p)->a;
    >>
    >> is a defined case of type punning.

    >
    > Actually there isn't any type punning going on here, since the types
    > used to reference objects are the same in each case that the respective
    > object actually holds. (And ignoring that member 'a' hasn't been
    > initialized, which is orthogonal to the question of type punning.)
    > Type punning refers to the case when a region of memory has been stored
    > (or perhaps declared) using one type, then accessed using another.
    > That hasn't happened here. The pointer conversions are legal and
    > portable, but the converted pointers are accessing objects whose types
    > match those of the access in each case -- ergo, no type punning.


    I probably misused the term "type punning" (see above what I meant --
    nothing more than manipulating a pointer-to-char and then casting it to a
    pointer-to-struct).

    My real problem was, again, that the compiler sees two pointers to
    different types, and the areas occupied by the pointed-to objects overlap.
    I was worried whether this breaks "strict aliasing rules".

    Of course, it doesn't; the outer structure declaration ("struct
    object_type") is visible, so if the compiler sees a (struct object_type *)
    and a (struct node_type *), it cannot assume the latter doesn't point into
    the target of the former -- unless "restrict" is in effect.


    I attribute my mistake to two specific "shocks" I suffered earlier: (1)
    the struct hack is UB in C89, and (2) if "arr" is a two-by-two "matrix",
    you can't write "arr[0][3]". These presumably drove me to the overcautious
    extreme.

    I have to admit, I still have difficulty determining what constitutes a
    promise to the compiler. Consider:

    a) It was derived by multiple illustrious contributors here and in c.l.c.m
    that multi-dimensional arrays can't have holes at all (or so I remember).
    It had to be derived because the Standard doesn't explicitly say so (I
    think). Why oh why can't you write arr[0][3] then, when the memory *must*
    be there and the access is correctly aligned? Well, because you made a
    promise to the compiler wrt. to the range of the last subscript, and the
    addressing instruction it generates may be invalid.

    Okay, then write "*(&arr[0][0] + 3)". Still undefined, because...

    Or, instead of over-indexing a struck hack array in C89, just write

    *(el_type *)((char unsigned *)hack_arr + n * sizeof(el_type))

    Still undefined, because...

    b) Contrast: hacking on a char pointer, casting it and dereferencing it is
    okay, because "we know it is correctly aligned, and the pointed-to storage
    was correctly allocated and written to earlier".

    I simply can't put my finger on the distinctive feature between these two.

    --o--

    Thanks for your reply, Tim.
    lacos
    Ersek, Laszlo, Jul 15, 2010
    #11
  12. On Jul 15, 7:34 pm, "Ersek, Laszlo" <> wrote:
    > On Wed, 14 Jul 2010, Tim Rentsch wrote:
    > > Franck Bui-Huu <> writes:

    >
    > >> "Ersek, Laszlo" <> writes:

    >
    > >>>>        struct object *the_obj;
    > >>>>        the_obj = avltree_container_of(the_node, struct object , node);
    > >>>>        assert(the_obj->key == 4);

    >
    > >>> Therein lies my problem:

    >
    > >>> #define avltree_container_of(node, type, member) ({       \
    > >>>     const struct avltree_node *__mptr = (node);           \
    > >>>     (type *)( (char *)__mptr - offsetof(type,member) );})

    >
    > [snip]
    >
    > >>> Second (my main concern), I suspect that this breaks strict aliasing
    > >>> rules. That is, after the avltree_container_of() function-like macro
    > >>> is expanded and the (statement-)expression is evaluated, you end up
    > >>> with two pointers, namely "the_node" and "the_obj". They point to
    > >>> storage that overlaps, and none of them was computed from the other by
    > >>> following pointers and taking addresses of members.

    >
    > >>> That is, you have two pointers to different types, the pointed-to
    > >>> areas overlap, and you obtained one of the pointers by type-punning
    > >>> (when you cast the pointer-to-char to pointer-to-type).

    >
    > [snip]
    >
    >
    >
    >
    >
    > >> Therefore,

    >
    > >>         (char *)node - offsetof(...)

    >
    > >> results to the address of the beginning of the structure (whose type is
    > >> 'struct my_struct) containing the member 'my_node' pointed by 'node'.

    >
    > >> So by definition we can assume that this address is correctly aligned
    > >> for accessing an object of type 'struct my_struct'. Therefore we can
    > >> safely convert back this address to (struct my_struct *).

    >
    > >> And since we know that the effective type of the underlying object is
    > >> 'struct my_struct', it's safe to deference the converted pointer.

    >
    > > Right.

    >
    > >> So to sum up, I think:

    >
    > >>         struct my_struct obj;
    > >>         char *p = (char *)&obj;
    > >>         p += offsetof(struct my_struct, my_node);
    > >>         p -= offsetof(struct my_struct, my_node);
    > >>         ((struct my_struct *)p)->a;

    >
    > >> is a defined case of type punning.

    >
    > > Actually there isn't any type punning going on here, since the types
    > > used to reference objects are the same in each case that the respective
    > > object actually holds.  (And ignoring that member 'a' hasn't been
    > > initialized, which is orthogonal to the question of type punning.)
    > > Type punning refers to the case when a region of memory has been stored
    > > (or perhaps declared) using one type, then accessed using another.
    > > That hasn't happened here.  The pointer conversions are legal and
    > > portable, but the converted pointers are accessing objects whose types
    > > match those of the access in each case -- ergo, no type punning.

    >
    > I probably misused the term "type punning" (see above what I meant --
    > nothing more than manipulating a pointer-to-char and then casting it to a
    > pointer-to-struct).
    >
    > My real problem was, again, that the compiler sees two pointers to
    > different types, and the areas occupied by the pointed-to objects overlap..
    > I was worried whether this breaks "strict aliasing rules".
    >
    > Of course, it doesn't; the outer structure declaration ("struct
    > object_type") is visible, so if the compiler sees a (struct object_type *)
    > and a (struct node_type *), it cannot assume the latter doesn't point into
    > the target of the former -- unless "restrict" is in effect.
    >


    Really ?

    I thought that "strict aliasing rules" force the compiler to assume
    that 2 different types never overlap.

    BTW, are these rules specific to GCC ?

    Thanks
    Francis Moreau, Jul 17, 2010
    #12
  13. Franck Bui-Huu

    Tim Rentsch Guest

    "Ersek, Laszlo" <> writes:

    > On Wed, 14 Jul 2010, Tim Rentsch wrote:
    >
    >> Franck Bui-Huu <> writes:
    >>
    >>> "Ersek, Laszlo" <> writes:
    >>>
    >>>>>
    >>>>> struct object *the_obj;
    >>>>> the_obj = avltree_container_of(the_node, struct object , node);
    >>>>> assert(the_obj->key == 4);
    >>>>
    >>>> Therein lies my problem:
    >>>>
    >>>> #define avltree_container_of(node, type, member) ({ \
    >>>> const struct avltree_node *__mptr = (node); \
    >>>> (type *)( (char *)__mptr - offsetof(type,member) );})
    >>>>

    >
    > [snip]
    >
    >>>> Second (my main concern), I suspect that this breaks strict
    >>>> aliasing rules. That is, after the avltree_container_of()
    >>>> function-like macro is expanded and the (statement-)expression is
    >>>> evaluated, you end up with two pointers, namely "the_node" and
    >>>> "the_obj". They point to storage that overlaps, and none of them
    >>>> was computed from the other by following pointers and taking
    >>>> addresses of members.
    >>>>
    >>>> That is, you have two pointers to different types, the pointed-to
    >>>> areas overlap, and you obtained one of the pointers by
    >>>> type-punning (when you cast the pointer-to-char to
    >>>> pointer-to-type).

    >
    > [snip]
    >
    >>> Therefore,
    >>>
    >>> (char *)node - offsetof(...)
    >>>
    >>> results to the address of the beginning of the structure (whose
    >>> type is 'struct my_struct) containing the member 'my_node' pointed
    >>> by 'node'.
    >>>
    >>> So by definition we can assume that this address is correctly
    >>> aligned for accessing an object of type 'struct
    >>> my_struct'. Therefore we can safely convert back this address to
    >>> (struct my_struct *).
    >>>
    >>> And since we know that the effective type of the underlying object
    >>> is 'struct my_struct', it's safe to deference the converted
    >>> pointer.

    >>
    >> Right.
    >>
    >>> So to sum up, I think:
    >>>
    >>> struct my_struct obj;
    >>> char *p = (char *)&obj;
    >>> p += offsetof(struct my_struct, my_node);
    >>> p -= offsetof(struct my_struct, my_node);
    >>> ((struct my_struct *)p)->a;
    >>>
    >>> is a defined case of type punning.

    >>
    >> Actually there isn't any type punning going on here, since the types
    >> used to reference objects are the same in each case that the
    >> respective object actually holds. (And ignoring that member 'a'
    >> hasn't been initialized, which is orthogonal to the question of type
    >> punning.) Type punning refers to the case when a region of memory
    >> has been stored (or perhaps declared) using one type, then accessed
    >> using another. That hasn't happened here. The pointer conversions
    >> are legal and portable, but the converted pointers are accessing
    >> objects whose types match those of the access in each case -- ergo,
    >> no type punning.

    >
    > I probably misused the term "type punning" (see above what I meant --
    > nothing more than manipulating a pointer-to-char and then casting it
    > to a pointer-to-struct).


    Yes, I realized the confusion and hoped my comments might
    clear that up.

    > My real problem was, again, that the compiler sees two pointers to
    > different types, and the areas occupied by the pointed-to objects
    > overlap. I was worried whether this breaks "strict aliasing rules".
    >
    > Of course, it doesn't; the outer structure declaration ("struct
    > object_type") is visible, so if the compiler sees a (struct
    > object_type *) and a (struct node_type *), it cannot assume the latter
    > doesn't point into the target of the former -- unless "restrict" is in
    > effect.
    >
    >
    > I attribute my mistake to two specific "shocks" I suffered earlier:
    > (1) the struct hack is UB in C89, and (2) if "arr" is a two-by-two
    > "matrix", you can't write "arr[0][3]". These presumably drove me to
    > the overcautious extreme.
    >
    > I have to admit, I still have difficulty determining what constitutes
    > a promise to the compiler. Consider:
    >
    > a) It was derived by multiple illustrious contributors here and in
    > c.l.c.m that multi-dimensional arrays can't have holes at all (or so I
    > remember). It had to be derived because the Standard doesn't
    > explicitly say so (I think). Why oh why can't you write arr[0][3]
    > then, when the memory *must* be there and the access is correctly
    > aligned? Well, because you made a promise to the compiler wrt. to the
    > range of the last subscript, and the addressing instruction it
    > generates may be invalid.
    >
    > Okay, then write "*(&arr[0][0] + 3)". Still undefined, because...
    >
    > Or, instead of over-indexing a struck hack array in C89, just write
    >
    > *(el_type *)((char unsigned *)hack_arr + n * sizeof(el_type))
    >
    > Still undefined, because...
    >
    > b) Contrast: hacking on a char pointer, casting it and dereferencing
    > it is okay, because "we know it is correctly aligned, and the
    > pointed-to storage was correctly allocated and written to earlier".
    >
    > I simply can't put my finger on the distinctive feature between these two.


    I find it useful to read the Standard in two distinct modes.
    One, what I might call the "comp.std.c mode", is a more literal
    and less assuming reading (or interpretation, some might say).
    The other, what I might call the "comp.lang.c mode", is less
    literal and allows more reading between the lines, in an effort
    to discover what the committee expects for how the words will
    be read. Mostly these two modes produce the same conclusions,
    but there are some obvious counterexamples, and I think pointer
    manipulation and conversion qualifies as a candidate here.

    Reading in the comp.lang.c mode, indexing an array past its
    (last dimension) index limit is wrong, because the compiler
    "knows" (more accurately, "is allowed to know") what that
    upper bound is. So that explains the 'arr[0][3]' example.
    Furthermore, because of how indexing works in C (because of
    how arrays convert to pointer-to-first-element) the expression
    '*(&arr[0][0]+3)' isn't any different than '*(&arr[0][3])',
    which obviously should be the same as 'arr[0][3]'.

    The third example (with 'hack_arr') is a little tricker, because
    casting a pointer to any kind of character pointer carries a certain
    amount of "magic" in the C language, so this is closer to being
    allowed. There's a different problem though, which is storing into
    any structure member is allowed to mess up any padding bytes, so the
    (presumably last) member 'hack_arr' might be messed up by that in
    its upper bytes. I think a reasonable argument could be made that
    if the size of 'hack_arr' plus its offset in the structure equals
    the size of the whole structure (ie, so there are no trailing
    padding bytes), then accessing 'hack_arr' in the way you describe
    can be expected to work (again reading in the comp.lang.c mode, and
    even so I admit it's a gray area).

    The difference with converting to a structure pointer is (a) we
    know (again, in comp.lang.c mode) that we have to be able to do
    pointer arithmetic on a character pointer to get from a
    pointer-to-member to pointer-to-structure, because otherwise
    what's the point of 'offsetof()', and (b) when we convert a
    pointer to a pointer-to-structure, whatever the compiler used to
    "know" about the size of the pointed-to object, now it "knows"
    something different, ie, the size of the structure, because that
    information is explicit in the definition of the structure type,
    and C is supposed to "trust the programmer". The explicit
    supplying of new size information is the key difference between
    the two cases. At least, I think that's a reasonable conclusion,
    reading in the comp.lang.c mode.

    Some people who read in more of a comp.std.c mode might argue that
    going from pointer-to-(nonfirst)member to pointer-to-structure is
    always undefined behavior, and I think it might be possible to make
    an argument that the Standard supports such a reading. However,
    as far as comp.lang.c goes, any sort of suggestion in that direction
    is merely evidence that the Standard needs to be revised and/or
    clarified, because surely the committee expects that this kind
    of character pointer arithmetic works and yields the expected
    (and well-defined) results.
    Tim Rentsch, Jul 17, 2010
    #13
  14. Franck Bui-Huu

    Tim Rentsch Guest

    Francis Moreau <> writes:

    > On Jul 15, 7:34 pm, "Ersek, Laszlo" <> wrote:
    >>[snip]
    >> My real problem was, again, that the compiler sees two pointers to
    >> different types, and the areas occupied by the pointed-to objects overlap.
    >> I was worried whether this breaks "strict aliasing rules".
    >>
    >> Of course, it doesn't; the outer structure declaration ("struct
    >> object_type") is visible, so if the compiler sees a (struct object_type *)
    >> and a (struct node_type *), it cannot assume the latter doesn't point into
    >> the target of the former -- unless "restrict" is in effect.
    >>

    >
    > Really ?
    >
    > I thought that "strict aliasing rules" force the compiler to assume
    > that 2 different types never overlap.


    The 'effective type' rules allow members of structures (ie, the
    types of such members) to overlap the structure (type) to which
    they belong, for obvious reasons.

    > BTW, are these rules specific to GCC ?


    No, effective type rules are defined in the ISO C Standard.
    What I believe is specific to GCC is that GCC uses the
    term "strict aliasing rules" rather than 'effective type'
    which is the term used in the Standard. (Also GCC may
    provide options to allow more restrictive or less restrictive
    aliasing rules, but that's outside the scope of what's
    being discussed above.)
    Tim Rentsch, Jul 17, 2010
    #14
  15. Tim Rentsch <> writes:

    > Francis Moreau <> writes:


    [...]

    >>
    >> I thought that "strict aliasing rules" force the compiler to assume
    >> that 2 different types never overlap.

    >
    > The 'effective type' rules allow members of structures (ie, the
    > types of such members) to overlap the structure (type) to which
    > they belong, for obvious reasons.


    I assume you're talking about the rules given by 6.5p7.

    I would call these rules, or specially this one,

    an aggregate or union type that includes one of the aforementioned
    types among its members (including, recursively, a member of a
    subaggregate or contained union), or

    the 'relax aliasing rule'. This rule is actually very annoying since
    it
    forces the compiler to generate not optimized code for no good reasons
    in 90% of all cases.

    Now let's see what are the "strict aliasing rules" from the gcc
    manpage:

    Allow the compiler to assume the strictest aliasing rules applicable
    to the language being compiled. For C (and C^++), this activates
    optimizations based on the type of expressions. In particular, an
    object of one type is assumed never to reside at the same address as
    an object of a different type, unless the types are almost the same.

    >> BTW, are these rules specific to GCC ?

    >
    > No, effective type rules are defined in the ISO C Standard.
    > What I believe is specific to GCC is that GCC uses the
    > term "strict aliasing rules" rather than 'effective type'
    > which is the term used in the Standard.


    Looking at the 2 different rules (relax vs strict), they don't have
    the
    same meaning at all.

    So it doesn't seem to me that "strict aliasing rule" is just a name
    used
    by GCC to mean the same rules given by C standard.

    --
    Francis
    Francis Moreau, Jul 18, 2010
    #15
  16. Franck Bui-Huu

    Tim Rentsch Guest

    Francis Moreau <> writes:

    > Tim Rentsch <> writes:
    >
    >> Francis Moreau <> writes:

    >
    > [...]
    >
    >>>
    >>> I thought that "strict aliasing rules" force the compiler to assume
    >>> that 2 different types never overlap.

    >>
    >> The 'effective type' rules allow members of structures (ie, the
    >> types of such members) to overlap the structure (type) to which
    >> they belong, for obvious reasons.

    >
    > I assume you're talking about the rules given by 6.5p7.
    >
    > I would call these rules, or specially this one,
    >
    > an aggregate or union type that includes one of the aforementioned
    > types among its members (including, recursively, a member of a
    > subaggregate or contained union), or
    >
    > the 'relax aliasing rule'.


    You're free to call it whatever you want, but I believe this
    usage is at odds with what most others understand, including
    the GCC folks.

    > This rule is actually very annoying since it
    > forces the compiler to generate not optimized code for no good reasons
    > in 90% of all cases.


    Oh? You think taking a pointer to a structure member shouldn't
    be allowed to access the member without causing undefined
    behavior? Wouldn't that break essentially every large C program
    in existence?

    > Now let's see what are the "strict aliasing rules" from the gcc
    > manpage:
    >
    > Allow the compiler to assume the strictest aliasing rules applicable
    > to the language being compiled. For C (and C^++), this activates
    > optimizations based on the type of expressions. In particular, an
    > object of one type is assumed never to reside at the same address as
    > an object of a different type, unless the types are almost the same.


    Please note the last line -- "unless the types are almost the same."
    It seems highly likely that gcc would transgress the rules for
    structure/member intermixing, even under the heading of "strict
    aliasing". The description in the gcc man page makes it clear
    that unions are affected, but it's not completely clear what
    the C Standard itself expects in such situations. The testing
    I have done doesn't show any difference between 'effective type'
    and 'strict aliasing', except (possibly) for the one example
    with unions shown in the gcc man page, and again it's debatable
    what the C Standard actually requires in such cases.


    >>> BTW, are these rules specific to GCC ?

    >>
    >> No, effective type rules are defined in the ISO C Standard.
    >> What I believe is specific to GCC is that GCC uses the
    >> term "strict aliasing rules" rather than 'effective type'
    >> which is the term used in the Standard.

    >
    > Looking at the 2 different rules (relax vs strict), they don't have
    > the
    > same meaning at all.
    >
    > So it doesn't seem to me that "strict aliasing rule" is just a name
    > used
    > by GCC to mean the same rules given by C standard.


    I believe you have misunderstood the intended meaning of the gcc
    documentation. Clearly that documentation can (and IMO should)
    be better written than it is, but surely such a large deviation
    away from what the C Standard requires would have a more strongly
    worded description, if such a change was indeed intended.
    Tim Rentsch, Jul 18, 2010
    #16
  17. On Sat, 17 Jul 2010, Tim Rentsch wrote:

    > I find it useful to read the Standard in two distinct modes. One, what I
    > might call the "comp.std.c mode", is a more literal and less assuming
    > reading (or interpretation, some might say). The other, what I might
    > call the "comp.lang.c mode", is less literal and allows more reading
    > between the lines, in an effort to discover what the committee expects
    > for how the words will be read. Mostly these two modes produce the same
    > conclusions, but there are some obvious counterexamples [...]


    It's great to see these "modes" "formalized"; being aware of them will
    help me read the Standard.

    Thanks!
    lacos
    Ersek, Laszlo, Jul 19, 2010
    #17
  18. Franck Bui-Huu

    Tim Rentsch Guest

    "Ersek, Laszlo" <> writes:

    > On Sat, 17 Jul 2010, Tim Rentsch wrote:
    >
    >> I find it useful to read the Standard in two distinct modes. One,
    >> what I might call the "comp.std.c mode", is a more literal and less
    >> assuming reading (or interpretation, some might say). The other,
    >> what I might call the "comp.lang.c mode", is less literal and allows
    >> more reading between the lines, in an effort to discover what the
    >> committee expects for how the words will be read. Mostly these two
    >> modes produce the same conclusions, but there are some obvious
    >> counterexamples [...]

    >
    > It's great to see these "modes" "formalized"; being aware of them will
    > help me read the Standard.


    It also can be helpful in newsgroup discussions, because different
    people make different assumptions about what the "correct" mode
    is. If their respective mode assumptions are very different, it's
    hard for two (or more) arguing posters to communicate effectively,
    especially if each believes that his mode is the only correct one.
    Tim Rentsch, Jul 19, 2010
    #18
  19. Tim Rentsch <> writes:

    > Francis Moreau <> writes:
    >
    >> Tim Rentsch <> writes:
    >>
    >>> Francis Moreau <> writes:

    >>
    >> [...]
    >>
    >>>>
    >>>> I thought that "strict aliasing rules" force the compiler to assume
    >>>> that 2 different types never overlap.
    >>>
    >>> The 'effective type' rules allow members of structures (ie, the
    >>> types of such members) to overlap the structure (type) to which
    >>> they belong, for obvious reasons.

    >>
    >> I assume you're talking about the rules given by 6.5p7.
    >>
    >> I would call these rules, or specially this one,
    >>
    >> an aggregate or union type that includes one of the aforementioned
    >> types among its members (including, recursively, a member of a
    >> subaggregate or contained union), or
    >>
    >> the 'relax aliasing rule'.

    >
    > You're free to call it whatever you want, but I believe this
    > usage is at odds with what most others understand, including
    > the GCC folks.
    >
    >> This rule is actually very annoying since it
    >> forces the compiler to generate not optimized code for no good reasons
    >> in 90% of all cases.

    >
    > Oh? You think taking a pointer to a structure member shouldn't
    > be allowed to access the member without causing undefined
    > behavior? Wouldn't that break essentially every large C program
    > in existence?


    No, the item of 6.5p7 which I pointed out doesn't deal about:

    struct object {
    int a;
    };

    [...]

    struct object an_object;
    int *p = &an_object.a;

    As you said, this is clearly defined, since we're accessing the
    (member)
    object "an_object.a" with a pointer whose type is compatible.

    However doing this:

    struct object *obj;
    int a = 5;
    obj = (struct object *)&a;

    is defined by the C standard AFAIK (by what you call 'effective type
    rules' I believe, but 'strict aliasing rules' defined by GCC breaks
    this
    rules.

    At that point, I'm quite confused ;)

    --
    Francis
    Francis Moreau, Jul 19, 2010
    #19
  20. Franck Bui-Huu

    Tim Rentsch Guest

    Francis Moreau <> writes:

    > Tim Rentsch <> writes:
    >
    >> Francis Moreau <> writes:
    >>
    >>> Tim Rentsch <> writes:
    >>>
    >>>> Francis Moreau <> writes:
    >>>
    >>> [...]
    >>>
    >>>>>
    >>>>> I thought that "strict aliasing rules" force the compiler to assume
    >>>>> that 2 different types never overlap.
    >>>>
    >>>> The 'effective type' rules allow members of structures (ie, the
    >>>> types of such members) to overlap the structure (type) to which
    >>>> they belong, for obvious reasons.
    >>>
    >>> I assume you're talking about the rules given by 6.5p7.
    >>>
    >>> I would call these rules, or specially this one,
    >>>
    >>> an aggregate or union type that includes one of the aforementioned
    >>> types among its members (including, recursively, a member of a
    >>> subaggregate or contained union), or
    >>>
    >>> the 'relax aliasing rule'.

    >>
    >> You're free to call it whatever you want, but I believe this
    >> usage is at odds with what most others understand, including
    >> the GCC folks.
    >>
    >>> This rule is actually very annoying since it
    >>> forces the compiler to generate not optimized code for no good reasons
    >>> in 90% of all cases.

    >>
    >> Oh? You think taking a pointer to a structure member shouldn't
    >> be allowed to access the member without causing undefined
    >> behavior? Wouldn't that break essentially every large C program
    >> in existence?

    >
    > No, the item of 6.5p7 which I pointed out doesn't deal about:
    >
    > struct object {
    > int a;
    > };
    >
    > [...]
    >
    > struct object an_object;
    > int *p = &an_object.a;
    >
    > As you said, this is clearly defined, since we're accessing the
    > (member) object "an_object.a" with a pointer whose type is compatible.


    Right, but this case isn't what I was asking about.

    > However doing this:
    >
    > struct object *obj;
    > int a = 5;
    > obj = (struct object *)&a;
    >
    > is defined by the C standard AFAIK (by what you call 'effective type
    > rules' I believe, but 'strict aliasing rules' defined by GCC breaks
    > this rules. [snip]


    For starters this is (usually) undefined behavior anyway, because
    of pointer alignments and size mismatches if nothing else.

    However, suppose we have this:

    int *p;
    struct { int a; int b; } *x, *y;
    x = malloc( sizeof *x );
    y = malloc( sizeof *y );
    /* presume the mallocs succeed */

    y->a = y->b = 0;
    *x = *y;
    p = &x->a;

    *p = 5;
    *x = *y;
    /* under strict aliasing must '*p == 0' still be true? */

    *x = *y;
    *p = 7;
    *y = *x;
    /* under strict aliasing must 'y->a == 7' still be true? */

    y->a = y->b = 0;
    *x = *y;
    *p = 9;
    x = (void*) p;
    *x = *y;
    /* under strict aliasing must '*p == 0' still be true? */

    Do you believe, even under gcc strict aliasing, that any of the
    comment questions can have an answer other than "Yes"?. If so,
    what leads you to that conclusion?

    My best understanding is that all these questions have the answer
    "Yes" (more exactly, that gcc is expected to produce code
    compatible with "Yes", so if it doesn't the result would be
    labelled a bug).
    Tim Rentsch, Jul 19, 2010
    #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. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,090
  2. Berehem
    Replies:
    4
    Views:
    537
    Lawrence Kirby
    Apr 28, 2005
  3. sharan
    Replies:
    4
    Views:
    674
    CBFalconer
    Oct 30, 2007
  4. sharan
    Replies:
    2
    Views:
    819
    SM Ryan
    Oct 31, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,029
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page