preprocessor macros i don't understand

Question

i'm currently looking through some source code i found on the net, which makes use of preprocessor macros in a way i don't understand. it implements the quad-edge data-structure. hope, someone can clear things for me!

typedef int edge_ref;

typedef struct {
    edge_ref next[4];
    void *data[4];
    unsigned mark;
} edge_struct;

#define ROT(e) (((e)&0xfffffffcu)+(((e)+1)&3u))
#define SYM(e) (((e)&0xfffffffcu)+(((e)+2)&3u))
#define TOR(e) (((e)&0xfffffffcu)+(((e)+3)&3u))

#define ONEXT(e) ((edge_struct *)((e)&0xfffffffcu))->next[(e)&3]
#define ROTRNEXT(e) ((edge_struct *)((e)&0xfffffffcu))->next[((e)+1)&3]
#define SYMDNEXT(e) ((edge_struct *)((e)&0xfffffffcu))->next[((e)+2)&3]
#define TORLNEXT(e) ((edge_struct *)((e)&0xfffffffcu))->next[((e)+3)&3]

#define MARK(e)  ((edge_struct *)((e)&0xfffffffcu))->mark

and this is how they are used:

edge_ref e;
e = (edge_ref) malloc(sizeof(edge_struct));
ONEXT(e) = e;
SYMDNEXT(e) = SYM(e);
ROTRNEXT(e) = TOR(e);
TORLNEXT(e) = ROT(e);
MARK(e) = 0;
return e;

this is just an excerpt to outline what i'm having problems with. the whole thing can be found here

Answer 1

0xfffffffcu is just an unsigned constant with all bits set to 1 except the last 2 bits which are 0, i.e. 11111111111111111111111111111100. It's being used as a mask to maninpulate the bottom two bits of e. The whole point of these macros seems to be so that you can work with an array of 4 structs which you treat as a circular array (i.e. modulo 4 indexing).

Answer 2

These macros are just a simple code substitution. As to what there are doing is another thing.

ONEXT(e) = e;

becomes ((edge_struct *)((e)&0xfffffffcu))->next[(e)&3] = e;

Which looks to me like they are loading a structure with data that is related to the address.

Don't get overwhelmed with the macros. Just substitute the code in for the macros and figure out what it does. After that re-write it and add some comments so the next person doesn't have to go through what you are now.

Answer 3

Wait a moment...

typedef int edge_ref;

#define ONEXT(e) ((edge_struct *)((e)&0xfffffffcu))->next[(e)&3]

e = (edge_ref) malloc(sizeof(edge_struct));
ONEXT(e) = e;

The return of malloc is casted to a signed int, which is used without a check for NULL and masked with an unsigned int...

I don't know what this code is for, but I strongly recommend to not use it for any purpose.

Answer 4

My guess is that they have added tags to pointers, assuming they are aligned. (That's why there is masking operations before dereferencing).

Answer 5

They are assuming that the malloc function is returning memory address aligned to at least four bytes. Since they assume that all memory allocations will result in a value with the lower two bits set to zero, they are using these two bits to store information. So, to get the data in the structure they need to clear these two bits to get the true address:

((edge_struct *)((e)&0xfffffffcu))

So, an edge_ref is a pointer to an object of type edge_struct and an index into the object's internal array (the (e)&3u bit).

File under: clever, but euurrgghh (alongside the XOR list).