void* as generic in C, is it safe?

Question

get ready for a question a bit "twisted"...

I've implemented in the past a lot of data structure (tree, list, hash table, graph as well), using the macro i can implement some kind o generic. However i was wandering if it is possible to implement generic data structure using void pointer but somehow i would like to be able to use a typecheking...

I don't know if it is clear what i'm trying to say... but basically i don't think it is always safe to put "void*" as generic, at the same time i don't think is always a good idea to use the macro as way to make a generic data structure (since basically what a preprocessor does with the macro does is code substitution), because if you look around the web you can find such examples.

A good idea might be, in my opinion but probably i'm not right, is to use the macro for make a standard interface for the data stored in a data structure, among the interface functions i would put code for correct type checking, given a void*. Inspired by the software engineer techinique this could be a good way to proceed.

It is surely true that probably for too sofisticated stuff would be better to switch language (C++/Java) but it is even true that this is not always possible.

So in summary... how the problem of "generic" in C is usually handled? i rely on your experience for an answer!

Answer 1

Briefly, there’s no convenient way to get type-safe generic data structures and functions in C.

Non-generic:

struct node {
  int value;
  struct node *next;
};

Generic, but unsafe—a void* has no type information:

struct node {
  void *value;
  struct node *next;
};

Safe, but ugly:

#define DECLARE_NODE_TYPE(type) \
  struct node_##type { \
    type value; \
    struct node_##type *next; \
  };

DECLARE_NODE_TYPE(int)
node_int *x = ...

Same idea, but slightly less ugly:

// declare_node_type.h

struct node_##NODE_TYPE {
  NODE_TYPE value;
  struct node_##NODE_TYPE *next;
};

#undef NODE_TYPE

// elsewhere

#define NODE_TYPE int
#include "declare_node_type.h"

node_int *x = ...

Generic and safe, but C++, not C:

template<typename T>
struct node {
  T value;
  node<T> *next;
};

node<int> *x = ...

Answer 2

You can do safer stuff with void*; getting back to the linked example of Jon Purdy:

typedef struct {
    union {
        void* data;  // generic data
        int idata;   // int is not stored dynamically
    };
    int type;    // additional type information
    Node* next;  // link
} Node;

#define NODE_TYPE_INT 0
Node* createNodeInt(Node* self, Node* next, int value) {
    self->idata = value;
    self->type = NODE_TYPE_INT;
    self->next = next;
    return self;
}

// in this case relying on user defined types...
Node* createNodeGeneric(Node* self, Node* next, void* data, int type) {
    assert(type != NODE_TYPE_INT && ..);
    self->data = data;
    self->type = type;
    self->next = next;
    return self;
}

Another approach is to use the common first member as the base type:

typedef struct {
    int type;
} Node;

#define TYPE_BINARY 0
typedef struct {
    Node base;
    Node* left;
    Node* right;
    int op;
} BinaryOp;

#define TYPE_LEAF_INT 1
typedef struct {
    Node base;
    int a;
} LeafInt;

#define TYPE_LEAF_FLOAT 2
typedef struct {
    Node base;
    float b;
} LeafFloat;

void op(BinaryOp* node) {
    switch(node->left.type) {
    case TYPE_BINARY:
        op((BinaryOp*)node->left);
        break;
    case TYPE_LEAF_INT:
        evalInt((LeafInt*)node->left);
        break;
    ...
    }
}

Node* foo() {
    LeafInt* left;
    LeafFloat* right;
    BinaryOp* op;
    // allocate
    ...
    // init
    createLeafInt(left, 42);
    createLeafFloat(right, 13.37);
    createBinaryOp(op, &left->base, &right->base);
    // and return
    return &op->base;
}
}