What's the C strategy to "imitate" a C++ template ?

Question

After reading some examples on stackoverflow, and following some of the answers for my previous questions (1), I've eventually come with a "strategy" for this.

I've come to this:

1) Have a declare section in the .h file. Here I will define the data-structure, and the accesing interface. Eg.:

/**
 * LIST DECLARATION. (DOUBLE LINKED LIST)
 */
#define NM_TEMPLATE_DECLARE_LIST(type) \
typedef struct nm_list_elem_##type##_s { \
    type data; \
    struct nm_list_elem_##type##_s *next; \
    struct nm_list_elem_##type##_s *prev; \
} nm_list_elem_##type ; \
typedef struct nm_list_##type##_s { \
    unsigned int size; \
    nm_list_elem_##type *head; \
    nm_list_elem_##type *tail; \
    int (*cmp)(const type e1, const type e2); \
} nm_list_##type ; \
\
nm_list_##type *nm_list_new_##type##_(int (*cmp)(const type e1, \
    const type e2)); \
\
(...other functions ...)

2) Wrap the functions in the interface inside MACROS:

/**
 * LIST INTERFACE
 */
#define nm_list(type) \
    nm_list_##type

#define nm_list_elem(type) \
    nm_list_elem_##type

#define nm_list_new(type,cmp) \
    nm_list_new_##type##_(cmp)

#define nm_list_delete(type, list, dst) \
    nm_list_delete_##type##_(list, dst)

#define nm_list_ins_next(type,list, elem, data) \
    nm_list_ins_next_##type##_(list, elem, data)

(...others...)

3) Implement the functions:

/**
 * LIST FUNCTION DEFINITIONS
 */
#define NM_TEMPLATE_DEFINE_LIST(type) \
nm_list_##type *nm_list_new_##type##_(int (*cmp)(const type e1, \
    const type e2)) \
{\
    nm_list_##type *list = NULL; \
    list = nm_alloc(sizeof(*list)); \
    list->size = 0; \
    list->head = NULL; \
    list->tail = NULL; \
    list->cmp = cmp; \
}\
void nm_list_delete_##type##_(nm_list_##type *list, \
    void (*destructor)(nm_list_elem_##type elem)) \
{ \
    type data; \
    while(nm_list_size(list)){ \
        data = nm_list_rem_##type(list, tail); \
        if(destructor){ \
            destructor(data); \
        } \
    } \
    nm_free(list); \
} \
(...others...)

In order to use those constructs, I have to create two files (let's call them templates.c and templates.h) .

In templates.h I will have to NM_TEMPLATE_DECLARE_LIST(int), NM_TEMPLATE_DECLARE_LIST(double) , while in templates.c I will need to NM_TEMPLATE_DEFINE_LIST(int) , NM_TEMPLATE_DEFINE_LIST(double) , in order to have the code behind a list of ints, doubles and so on, generated.

By following this strategy I will have to keep all my "template" declarations in two files, and in the same time, I will need to include templates.h whenever I need the data structures. It's a very "centralized" solution.

Do you know other strategy in order to "imitate" (at some point) templates in C++ ? Do you know a way to improve this strategy, in order to keep things in more decentralized manner, so that I won't need the two files: templates.c and templates.h ?

Answer 1

I probably shouldn't admit to doing this, but when I needed "templatized" containers in C land in the past, I wrote the 'templatized queue class' as a pair of special files, like this:

File MyQueue.include_h:

/** NOTE: THIS IS NOT a REAL .h FILE, it only looks like one!  Don't #include it! */
struct MyQueueClass
{
   void init_queue(MyQueueClass * q);
   void push_back(MyQueueClass * q, MyQueueClassItem * item);

   [....All the other standard queue header declarations would go here....]

   MyQueueClassItem * _head;
   MyQueueClassItem * _tail;
   int _size;
};

File MyQueue.include_c:

/** NOTE: THIS IS NOT A REAL .c FILE, it only looks like one! Don't compile directly! */
void init_queue(MyQueueClass * q)
{
   q->_size = 0;
   q->_head = q->_tail = NULL;
}

void push_back(MyQueueClass * q, MyQueueClassItem * item)
{
   if (q->_head == NULL) q->_head = q->_tail = item;
   else
   {
      q->_tail->_next = item;
      item->_prev = q->_tail;
      q->_tail = item;
   }
   q->_size++;
}

[....All the other standard queue function bodies would go here....]

Then, whenever I wanted to "instantiate" my Queue "template" to use a particular item-type, I'd put something like this into an actual .c and .h file:

In one of my real .h files:

#define MyQueueClass struct SomeSpecificQueueType
#define MyQueueClassItem struct SomeSpecificQueueTypeItem
# include "MyQueue.include_h"
#undef MyQueueClassItem
#undef MyQueueClass

In one of my real .c files (it doesn't matter which one):

#define MyQueueClass struct SomeSpecificQueueType
#define MyQueueClassItem struct SomeSpecificQueueTypeItem
# include "MyQueue.include_c"
#undef MyQueueClass
#undef MyQueueClassItem

.... and presto, the C preprocessor acts as a poor man's template-expander, without requiring the entire "template definition" to be made out of a giant #define statement.

Answer 2

Your example is only one of the many possible uses of templates - generating a generic data structure. This example doesn't need any of the inference which makes templates powerful; asking for something which lets you create generic data structures is not really the same question as asking for something equivalent to C++ templates.

Some of the implementation techniques used for <tgmath.h> might give some type inference capabilities, but they is still much weaker and less portable than C++ templates.

For the specific example of containers, I wouldn't bother - just create a list with void* data in it, and either use malloc and free to create the data, or give the list have a pair of function pointers to create and destroy values. You can also just rely on the client to manage the data, rather than having the value as a member of the list. If you want to save the indirection, use a variable length array as the data member. As C isn't as type-safe as C++, having void* data isn't an issue.

You can do some sophisticated code generation with macros, but there are also other tools to generate code. Personally I like using XSLT for code generation, but then you have a completely non-C-like part of your build process.

Answer 3

Save yourself some trouble and use existing queue(3) set of macros - tried and tested, used in kernel sources, etc.