Type-safe generic data structures in plain-old C?

Question

Option 1 is the approach taken by most C implementations of generic containers that I see. The Windows driver kit and the Linux kernel use a macro to allow links for the containers to be embedded anywhere in a structure, with the macro used to obtain the structure pointer from a pointer to the link field:

• list_entry() macro in Linux
• CONTAINING_RECORD() macro in Windows

Option 2 is the tack taken by BSD's tree.h and queue.h container implementation:

• http://openbsd.su/src/sys/sys/queue.h
• http://openbsd.su/src/sys/sys/tree.h

I don't think I'd consider either of these approaches type safe. Useful, but not type safe.

C has a different kind of beauty to it than C++, and type safety and being able to always see what everything is when tracing through code without involving casts in your debugger is typically not one of them.

C's beauty comes a lot from its lack of type safety, of working around the type system and at the raw level of bits and bytes. Because of that, there's certain things it can do more easily without fighting against the language like, say, variable-length structs, using the stack even for arrays whose sizes are determined at runtime, etc. It also tends to be a lot simpler to preserve ABI when you're working at this lower level.

So there's a different kind of aesthetic involved here as well as different challenges, and I'd recommend a shift in mindset when you work in C. To really appreciate it, I'd suggest doing things many people take for granted these days, like implementing your own memory allocator or device driver. When you're working at such a low level, you can't help but look at everything as memory layouts of bits and bytes as opposed to 'objects' with behaviors attached. Furthermore, there can come a point in such low-level bit/byte manipulation code where C becomes easier to comprehend than C++ code littered with reinterpret_casts, e.g.

As for your linked list example, I would suggest a non-intrusive version of a linked node (one that does not require storing list pointers into the element type, T, itself, allowing the linked list logic and representation to be decoupled from T itself), like so:

struct ListNode
{
    struct ListNode* prev;
    struct ListNode* next;
    MAX_ALIGN char element[1]; // Watch out for alignment here.
                               // see your compiler's specific info on 
                               // aligning data members.
};

Now we can create a list node like so:

struct ListNode* list_new_node(int element_size)
{
    // Watch out for alignment here.
    return malloc_max_aligned(sizeof(struct ListNode) + element_size - 1);
}

// create a list node for 'struct Foo'
void foo_init(struct Foo*);
struct ListNode* foo_node = list_new_node(sizeof(struct Foo));
foo_init(foo_node->element);

To retrieve the element from the list as T*:

T* element = list_node->element;

Since it's C, there's no type checking whatsoever when casting pointers in this way, and that will probably also give you an uneasy feeling if you're coming from a C++ background.

The tricky part here is to make sure that this member, element, is properly aligned for whatever type you want to store. When you can solve that problem as portably as you need it to be, you'll have a powerful solution for creating efficient memory layouts and allocators. Often this will have you just using max alignment for everything which might seem wasteful, but typically isn't if you are using appropriate data structures and allocators which aren't paying this overhead for numerous small elements on an individual basis.

Now this solution still involves the type casting. There's little you can do about that short of having a separate version of code of this list node and the corresponding logic to work with it for every type, T, that you want to support (short of dynamic polymorphism). However, it does not involve an additional level of indirection as you might have thought was needed, and still allocates the entire list node and element in a single allocation.

And I would recommend this simple way to achieve genericity in C in many cases. Simply replace T with a buffer that has a length matching sizeof(T) and aligned properly. If you have a reasonably portable and safe way you can generalize to ensure proper alignment, you'll have a very powerful way of working with memory in a way that often improves cache hits, reduces the frequency of heap allocations/deallocations, the amount of indirection required, build times, etc.

If you need more automation like having list_new_node automatically initialize struct Foo, I would recommend creating a general type table struct that you can pass around which contains information like how big T is, a function pointer pointing to a function to create a default instance of T, another to copy T, clone T, destroy T, a comparator, etc. In C++, you can generate this table automatically using templates and built-in language concepts like copy constructors and destructors. C requires a bit more manual effort, but you can still reduce it the boilerplate a bit with macros.

Another trick that can be useful if you go with a more macro-oriented code generation route is to cash in a prefix or suffix-based naming convention of identifiers. For example, CLONE(Type, ptr) could be defined to return Type##Clone(ptr), so CLONE(Foo, foo) could invoke FooClone(foo). This is kind of a cheat to get something akin to function overloading in C, and is useful when generating code in bulk (when CLONE is used to implement another macro) or even a bit of copying and pasting of boilerplate-type code to at least improve the uniformity of the boilerplate.

Option 1, either using void * or some union based variant is what most C programs use, and it may give you BETTER performance than the C++/macro style of having multiple implementations for different types, as it has less code duplication, and thus less icache pressure and fewer icache misses.

GLib is has a bunch of generic data structures in it, http://www.gtk.org/

CCAN has a bunch of useful snippets and such http://ccan.ozlabs.org/

I use void pointers (void*) to represent generic data structures defined with structs and typedefs. Below I share my implementation of a lib which I'm working on.

With this kind of implementation, you can think of each new type, defined with typedef, like a pseudo-class. Here, this pseudo-class is the set of the source code (some_type_implementation.c) and its header file (some_type_implementation.h).

In the source code, you have to define the struct that will present the new type. Note the struct in the "node.c" source file. There I made a void pointer to the "info" atribute. This pointer may carry any type of pointer (I think), but the price you have to pay is a type identifier inside the struct (int type), and all the switchs to make the propper handle of each type defined. So, in the node.h" header file, I defined the type "Node" (just to avoid have to type struct node every time), and also I had to define the constants "EMPTY_NODE", "COMPLEX_NODE", and "MATRIX_NODE".

You can perform the compilation, by hand, with "gcc *.c -lm".

main.c Source File

#include <stdio.h>
#include <math.h>

#define PI M_PI

#include "complex.h"
#include "matrix.h"
#include "node.h" 


int main()
{
    //testCpx();
    //testMtx();
    testNode();

    return 0;
}

node.c Source File

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "node.h"
#include "complex.h"
#include "matrix.h"

#define PI M_PI


struct node
{
    int type;

    void* info;
};


Node* newNode(int type,void* info)
{
    Node* newNode = (Node*) malloc(sizeof(Node));

    newNode->type = type;

    if(info != NULL)
    {
        switch(type)
        {
            case COMPLEX_NODE:
                newNode->info = (Complex*) info;
            break;

            case MATRIX_NODE:
                newNode->info = (Matrix*) info;
            break;
        }
    }
    else
        newNode->info = NULL;

    return newNode;
}

int emptyInfoNode(Node* node)
{
    return (node->info == NULL);
}

void printNode(Node* node)
{
    if(emptyInfoNode(node))
    {
        printf("Type:%d\n",node->type);
        printf("Empty info\n");
    }
    else
    {
        switch(node->type)
        {
            case COMPLEX_NODE:
                printCpx(node->info);
            break;

            case MATRIX_NODE:
                printMtx(node->info);
            break;
        }
    }
}

void testNode()
{
    Node *node1,*node2, *node3;
    Complex *Z;
    Matrix *M;

    Z = mkCpx(POLAR,5,3*PI/4);

    M = newMtx(3,4,PI);

    node1 = newNode(COMPLEX_NODE,Z);
    node2 = newNode(MATRIX_NODE,M);
    node3 = newNode(EMPTY_NODE,NULL);



    printNode(node1);
    printNode(node2);
    printNode(node3);
}

node.h Header File

#define EMPTY_NODE   0
#define COMPLEX_NODE 1
#define MATRIX_NODE  2


typedef struct node Node;


Node* newNode(int type,void* info);
int emptyInfoNode(Node* node);
void printNode(Node* node);
void testNode();

matrix.c Source File

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "matrix.h"

struct matrix
{
    // Meta-information about the matrix 
    int rows;
    int cols;

    // The elements of the matrix, in the form of a vector 
    double** MTX;
};

Matrix* newMtx(int rows,int cols,double value)
{
    register int row , col;
    Matrix* M = (Matrix*)malloc(sizeof(Matrix));

    M->rows = rows;
    M->cols = cols;
    M->MTX = (double**) malloc(rows*sizeof(double*));

    for(row = 0; row < rows ; row++)
    {
        M->MTX[row] = (double*) malloc(cols*sizeof(double));

        for(col = 0; col < cols ; col++) 
            M->MTX[row][col] = value;
    }

    return M;
}

Matrix* mkMtx(int rows,int cols,double** MTX)
{   
    Matrix* M;
    if(MTX == NULL)
    {
        M = newMtx(rows,cols,0);
    }
    else
    {
        M = (Matrix*)malloc(sizeof(Matrix));
        M->rows = rows;
        M->cols = cols;
        M->MTX  = MTX;
    }
    return M;
}

double getElemMtx(Matrix* M , int row , int col)
{
    return M->MTX[row][col];
}

void printRowMtx(double* row,int cols)
{
    register int j;
    for(j = 0 ; j < cols ; j++) 
        printf("%g ",row[j]);           
}

void printMtx(Matrix* M)
{
    register int row = 0, col = 0;

    printf("\vSize\n");
    printf("\tRows:%d\n",M->rows);
    printf("\tCols:%d\n",M->cols);
    printf("\n");
    for(; row < M->rows ; row++)
    {
        printRowMtx(M->MTX[row],M->cols);
        printf("\n");
    }

    printf("\n");
}

void testMtx()
{
    Matrix* M = mkMtx(10,10,NULL);
    printMtx(M);
}

matrix.h Header File

typedef struct matrix Matrix;

Matrix* newMtx(int rows,int cols,double value);
Matrix* mkMatrix(int rows,int cols,double** MTX);
void print(Matrix* M);
double getMtx(Matrix* M , int row , int col);
void printRowMtx(double* row,int cols);
void printMtx(Matrix* M);
void testMtx();

complex.c Source File

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "complex.h"

struct complex
{
    int type;

    double a;
    double b;
};

Complex* mkCpx(int type,double a,double b)
{
    /** Doc - {{{
     * This function makes a new Complex number.
     * 
     * @params:
     * |-->type: Is an interger that denotes if the number is in
     * |         the analitic or in the polar form.
     * |         ANALITIC:0
     * |         POLAR   :1
     * |
     * |-->a: Is the real part if type = 0 and is the radius if 
     * |      type = 1
     * |
     * `-->b: Is the imaginary part if type = 0 and is the argument
     *        if type = 1
     * 
     * @return:
     *      Returns the new Complex number initialized with the values 
     *      passed
     *}}} */

    Complex* number = (Complex*)malloc(sizeof(Complex));

    number->type = type;
    number->a    = a;
    number->b    = b;

    return number;
}

void printCpx(Complex* number)
{
    switch(number->type)
    {
        case ANALITIC:
            printf("Re:%g | Im:%g\n",number->a,number->b);
        break;

        case POLAR:
            printf("Radius:%g | Arg:%g\n",number->a,number->b);
        break;
    }
}

void testCpx()
{
    Complex* Z = mkCpx(ANALITIC,3,2);
    printCpx(Z);
}

complex.h Header File

#define ANALITIC 0 
#define POLAR    1 

typedef struct complex Complex;

Complex* mkCpx(int type,double a,double b);
void printCpx(Complex* number);
void testCpx();

I hope I hadn't missed nothing.

Your option 1 is what most old time c programmers would go for, possibly salted with a little of 2 to cut down on the repetitive typing, and just maybe employing a few function pointers for a flavor of polymorphism.