carangil

I did come across the linux kernel lists when I was looking up list implementations.  I decided just to put it on the top of the struct to make it easier. 

The advantage of the linux kernel list struct over mine, is you could have an object that can be put in multiple lists, because the listnode struct can be anywhere inside the larger struct.  The disadvantage is you have to know what lists those are in advance:

typedef struct {

   struct list_head multiples_of_5;

   struct list_head multiples_of_7;

   struct list_head perfect_numbers;

   struct list_head prime_numbers;

   unsigned int number;

} natural_numbers_t;

In cases where I may need objects that can exist in multiple lists, and I don't know what those lists are in advance, I'm always free to construct one of these:

typedef struct

{

    zlistnode_t zlistnode;

    natural_number_t* natnum;

} natural_number_node_t;

After (not) thinking about it for a couple days, I think I've actually worked it out.  Skip to the end if you want to see what I came up with that's generic, typesafe, and seems to follow strict-alias rules.  Or stick with the whole post to see how I came to it.

The above examples are slightly contrived, but when I look at real uses in my code, it's easy to not mix things up.  This is the real list structure I'm using in my code:
 

typedef struct zlistnode_s
{
    struct zlistnode_s* next;
    struct zlistnode_s* prev;
} zlistnode_t;

typedef struct
{   zlistnode_t* head;
    zlistnode_t* tail;
} zlist_t;

zerr zlist_addtail( zlist_t* list, zlistnode_t* node);
...
 

When I use a zlist_t, it's usually a list of a single type.  Something like this:
 

typedef struct {
    zlistnode_t zlistnode;
    zchar* name;
    zbool important_boolean;
    zuint32 crazy_int;
} supernode_t;
 

I had list access macros like this:
 

#define zlist_head(ZLIST)      ((ZLIST)->head)
#define zlist_next(ZLISTNODE)  (   ((zlistnode_t*)(ZLISTNODE)) -> next )
 

so iterating a list looked like:
 

supernode_t*  n = zlist_head(&my_supernode_list);  // of course a warning converting from zlistnode_t* to supernode_t*
while(n)
{
    //do stuff with n
    n = zlist_next(n);  //of course another warning here too
}
 

I originally put(void*) casts in the zlist_* macros to make the warnings go away.  When adding an item to the list:

zlist_addtail( &mylist, (zlistnode_t*) mynode); // casting a supernode_t* to a zlistnode_t*

So instead I do this:

zlist_addtail( &mylist, &mynode->zlistnode);  //take the first element of supernode_t*  (it's still a zlistnode_t*, but 'safer')

Also I changes zlist_next to:

#define zlist_next(ZLISTNODE)   ((ZLISTNODE)->zlistnode.next)

This macro is very safe, in that, the list item (say, a supernode_t) just needs to make sure the zlistnode_t is named
zlistnode'.  And if I accidently use the macro on a non-zlistnode-ified struct, I'll get a compile error instead of run-time crash.

So what I've done is completely embedded the zlistnode's inside the structs, and the zlistnodes link to themselves to make the linked list.  The zlist functions now only deal with true, bona-fide zlistnode_t pointers, with no casting or trickery.  There's only 1 thing left unclean:  When I store a supernode_t* in the list, I'm not really storing a supernode_t, I'm storing the zlistnode_t that's 'inside' the supernode.  When I call zlist_next, I'm really getting supernode->zlistnode.next, which is a zlistnode_t*.  I can cast it to a supernode_t*, and since it's the first element, it's guaranteed to be the 'same' pointer, but it still smells of aliasing.

Here, I think is the solution:

t

ypedef struct zlistnode_s
{
    void* next;
    void* prev;
} zlistnode_t;

typedef struct
{   void* head;
    void* tail;
} zlist_t;

zerr zlist_addtail( zlist_t* list, zlistnode_t* node);

#define zlist_head(ZLIST)      ((ZLIST)->head)
#define zlist_next(ZLISTNODE)   ((ZLISTNODE)->zlistnode.next)
 

This almost 'does it all'

Typesafety:

• The zlist_addtail function only accepts zlist_t*  and zlistnode_t*
• zlist_head macro only compiles on things that have a 'head'
• zlist_next macro only functions on things that a zlistnode 'inside'

But there's a nice key difference:  When I store the 'next' or 'head' or 'prev' pointers in the list, they are note other listnodes, they are 'void*'. Because any struct you allocate can be cast freely back and forth to void or their actual type, this is what's happening:

supernode_t* n = mk_supernode();   //n is really a supernode_t

zlist_addtail( &mylist, &n->zlistnode ); //stores 'n' aka 'n->zlistnode' in the list as a 'void*' (totally allowed)

later:

n = zlist_next(n);
which, if you do the macro substitution is:

n = n->zlistnode.next;    // You are not type-punning a zlistnode_t* into a supernode_t*.  You are just turning the zlistnode_t* back into itself from a void*.  (totally allowed)
 

If you want to get really pendantic, you can argue that I'm cheating by passing a zlistnode_t* into addhead/addtail, and I'm indirectly going from supernode_t* to zlistnode_t* to void* and then to supernode_t*, so I'm not playing completely by the rules.  But to that I say, a void* that points to a struct and a void* that points to the first member of a struct are the same void*.  And if I only access super_node_t specific elements from supernode_t*'s and only access listnode_t* elements (next/prev), there's no way the data of these overlapped structs can alias each other.

Unless I'm wrong is some way?

Unions are often used for type punning, but I'm not really punning.  Punning is taking something like a float*, and casting it an an int*, say for instance to manipulate the bits of the float in some goofy way.  (For instance the classic absolute value trick where you just clear out the sign bit without bothering the fpu).

Using a union does help, since I could do this:

typedef union {
  generic_list_t as_generic;
  int_t as_int;
  string_t as_string;
  }   generic_list_u;

And then I can pass around generic_list_u's around all I want.  Technically writing to the as_int field and then reading from the as_generic field is implementation-specific behavior, but gcc and I think most sane compilers would do the expected thing.  But this requires that I know all the possible list types in advance.  The whole point was to not specify this.  The example here are slightly contrived, but in my real code I have linked list implementaion that just deals with how to insert/remove generic_list_t elements from a double linked list.  I'm free to make lists of anything I want, as long as I put a generic_list_t at the top of whatever struct I want to make a list of.

If I use void pointers, the warning goes away:

void print_thing_void(generic_list_t* n)
{
    void* v  = (void*) n;      

    if (n->type == TYPE_STRING)
    {
        string_t* s = (string_t*) v;
        printf("%s\n", s->str);
    }

    if (n->type == TYPE_INT)
    {
        int_t* i = (int_t*) v;
        printf("%d\n", i->x);
    }
}

Instead of print_list, what if I have a contrived example like increment:

void increment(generic_list_t* n)
{
	if (n->type == TYPE_INT)
	{
		int_t* i = (int_t*) n;

		i->x++;
	}
}

// then sometime later:


int_t some_int;

//...

before_increment = some_int->x;

increment( &(some_int->gen)); 

after_increment = some_int->x;        //what value is this?

printf(" %d %d\n", before_increment, after_increment);

In the above code, is gcc free to do something like : "hey, increment takes a generic_list_t*, so nothing is messing with the 'x' value, so when increment returns, I won't bother to dereference some_int again, and I'll just say that after_increment is the same as before_increment, optimize out the after_increment variable, and just call printf with two before_increments"  ?

Is there a proper way to reconcile strict aliasing rules with 'struct inheritance' in c99?

Am I missing something?

va[f].vertices = new CVector3[ numverts ];

I'm not primarily a Java programmer, but is this really creating a full object's worth of overhead for each CVector3? It just seems like a lot of memory to me, especially for a mobile device.  Your heap is capping out at 100mb, whereas quake 2 only required 24MB of ram.  Ok, they used 16 bit integers for a lot of it, so double it to 50 MB using 32 bit floats for modern systems.  And this was for multiple models and a full level map.

Does Java/Android have any reasonable way to pack it down?  Quake in the old days was in C, so each vector took just 3 floats.  In many ways programming for a mobile device is just like an old PC.

You could pack things down into larger allocations:

class CVector3Array {

   int capacity;

   int count;

   float[] data;  //constructor will size to  3 * number of vectors

}

You would have to implement a few things yourself, and this:

vertices.set( i, x,y,z);

won't be as elegant as

vertices[i] = new CVector3d(x,y,z);

But it might end up cleaner than dropping to C.

•  

Quote

I'm a hardcore C programmer, and even program C in an OO style (function pointers in structs for polymorphism, etc), and some people give me trouble for it. I understand C++ is there, but for my own personal projects (not at work: at work I use whatever the rest of the team is using because its not my project) I choose C.




DracoLacorente, Was that style something you eased into on your own? I'm self-taught so it's a lot of give and take when it comes to style. I actually started off learning Python somewhat formally but it was so whitespace-unfriendly. The freedoms C gives you while staying kind of centered is why I like it. That and of course the inline assembly capability that people frown upon. I don't want to be that guy but it honestly just rings my bells.

I had zero style throughout high school and most of college.  Even after college my style was somewhat poor.  It was after working at my current company for about a year or so that some of the style and design of the code at work began to rub off on me an influence my code at home.  There's a few key experiences that have shook my style quite dramatically:

• I took a Java class at school.  The ideas of objects and polymorphism were cool, but I saw a lot of stuff that seemed over-OO-ified.  (the Integer class, for example).  But the idea of interfaces and abstraction really influenced my style.

• I was taking a computer graphics class and we had to write a ray tracer.  In the campus library had 'Practical Ray Tracing in C' http://www.amazon.com/Practical-Ray-Tracing-Craig-Lindley/dp/0471573019  That book really changed my C programming style.  By putting function pointers in a struct, you can change the object's behavior. 

• At work, one of the projects I help maintain is a large C codebase.  It has full manual memory management.  It sucks.  There is one part of that code base (a data tree structure) that uses reference counting.  I've adopted reference counting in my home-coded C projects.
•  

This is typical of my style at home:

typedef struct inner_s {
   char* str;
   void (*do_something)(struct inner_s* inner);
} inner_t;

typedef struct {
   inner_t* i1;
   inner_t* i2;
} outer_t;

void free_outer(outer_t* x)
{
   z_free(x->i1);
   z_free(x->i2);
}

void foo(outer_t* x)
{
	x->i1->do_something(x->i1);
	x->i2->do_something(x->i2);  
}


void free_inner(inner_t* x)
{
  z_free(x->str);
}



void inner_do_something_interesting(inner_t* in)
{
  printf(" oh my god %s!\n", in->str); 
}

void inner_do_something_boring(inner_t* in)
{
  printf("I'm bored\n");
}

inner_t* inner_mk(char* string)
{
   inner_t* inner = z_alloc(sizeof(*inner), free_inner);
   inner->str = z_addref(string);
   inner->do_something = inner_do_something_interesting;
   return inner;
}

outer_t* a = z_alloc( sizeof (*outer), free_outer);


char* reused_string = z_strdup("hello");

a->i1 = inner_mk(reused_string);
a->i2 = inner_mk(reused_string);

//sometimes you want to override a method
a->i2->do_something = inner_do_something_boring;


z_free(reused_string); //don't need this anymore, we inner_mk addref'ed it

foo(a); //this calls the 'do_something' method on both i1 and i2


//sometime later, something else copies a reference to a:

a_copy = z_addref(a);
//
and then maybe the original a goes out of scope:

z_free(a);

//then eventually the copy goes out of scope:

z_free(a_copy);  

//now z->i1, z->i2 are freed, recursively freeing the last reference to 'reused_string' which is now eventually destroyed

C++ programmers tell me the above is crazy and I should have made C++ classes for inner and outer, and then used boost smart pointers.  At work I program how I'm supposed to program to get things done.  At home, I program for fun, whatever way I want.