Yet another binary search tree library

[Franck Bui-Huu]

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

 

[Ersek, Laszlo]

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

 

[Malcolm McLean]

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;
}

 

[Ersek, Laszlo]

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

 

[Franck Bui-Huu]

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.

 

[Ersek, Laszlo]

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.



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:


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

 

[Malcolm McLean]

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.

 

[Franck Bui-Huu]

[...]

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.

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.

 

[James Waldby]

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

 

[Tim Rentsch]

[...]

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.

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.

 

[Ersek, Laszlo]

[snip]
[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

 

[Francis Moreau]

       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

 

[Tim Rentsch]

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]

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

 

[Francis Moreau]

[...]

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.

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.

 

[Tim Rentsch]

[...]

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.

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.

 

[Ersek, Laszlo]

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

 

[Tim Rentsch]

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.

 

[Francis Moreau]

[...]


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

 

[Tim Rentsch]

[...]


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