Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Yet another binary search tree library

Reply
Thread Tools

Yet another binary search tree library

 
 
Franck Bui-Huu
Guest
Posts: n/a
 
      07-01-2010
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
 
Reply With Quote
 
 
 
 
Ersek, Laszlo
Guest
Posts: n/a
 
      07-01-2010
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
 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      07-01-2010
On Jul 1, 5:27*pm, Franck Bui-Huu <(E-Mail Removed)> 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;
}
 
Reply With Quote
 
Ersek, Laszlo
Guest
Posts: n/a
 
      07-01-2010
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
 
Reply With Quote
 
Franck Bui-Huu
Guest
Posts: n/a
 
      07-01-2010
"Ersek, Laszlo" <(E-Mail Removed)> 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


 
Reply With Quote
 
Ersek, Laszlo
Guest
Posts: n/a
 
      07-01-2010
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
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      07-02-2010
On Jul 1, 7:06*pm, "Ersek, Laszlo" <(E-Mail Removed)> 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.
 
Reply With Quote
 
Franck Bui-Huu
Guest
Posts: n/a
 
      07-02-2010
"Ersek, Laszlo" <(E-Mail Removed)> 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
 
Reply With Quote
 
James Waldby
Guest
Posts: n/a
 
      07-06-2010
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
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      07-14-2010
Franck Bui-Huu <(E-Mail Removed)> writes:

> "Ersek, Laszlo" <(E-Mail Removed)> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 1 10-30-2007 11:01 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments