C templates

[alex_sv]

From time to time I am writing in C. After writing in C++ most of all
I would like to use a library that provides generic data structures
and algorithms like STL vector/map.
Some time ago I created such means for my own use.
May be someone will also find it useful for his needs.

The library contains of the header files only.

Sample usage:

#define AVL_TREE_NS(name) my_##name
#define AVL_TREE_KEY_TYPE int
#define AVL_TREE_COMPARE(a, b) (a - b)
#define AVL_TREE_XMALLOC xmalloc
#define AVL_TREE_XFREE xfree
#define AVL_TREE_ADD_NODE_REQUIRED
#define AVL_TREE_FIND_NODE_REQUIRED
#define AVL_TREE_REMOVE_NODE_REQUIRED
#include <templates/avl_tree.h>

static void test_simple_avl_tree()
{
my_tree t;

UT_BEGIN("test simple avl tree");

my_init_tree(&t);

my_add_node(&t, 10);
my_add_node(&t, 40);
my_add_node(&t, 30);
my_add_node(&t, 20);
my_add_node(&t, 50);

my_remove_node(&t, 30);

UT_VERIFY(my_find_node(&t, 10) != 0);
UT_VERIFY(my_find_node(&t, 20) != 0);
UT_VERIFY(my_find_node(&t, 40) != 0);
UT_VERIFY(my_find_node(&t, 50) != 0);
UT_VERIFY(my_find_node(&t, 30) == 0);

my_uninit_tree(&t);

UT_END();
}


UT_xxx names are the macros from my own small unit-test framework.

All the algorithms are not thread safe. It is expected that user-
provided memory allocation functions never return NULL but handle such
a situation internally.

At the moment the following is implemented
— AVL tree (recursive implementation)
— RB tree (non-recursive implementation)
— Stack
— Vector
— Fixed Allocator (effective memory allocation for the object of same
size)
— Binary Search

License - MIT.

Link to the google code project: http://code.google.com/p/ctemplates/

 

[Malcolm McLean]

From time to time I am writing in C. After writing in C++ most of all
I would like to use a library that provides generic data structures
and algorithms like STL vector/map.

You can create generic structures in C by using void pointers,
function pointers, and arrays of unsigned chars to hold arbitrary
bytes.

However whilst lots of generic linked list, binary tree, exapnding
array and other libraries have been written, none of them has gained
general acceptance. This is partly because no standards body has had
sufficient influence and desire to standardise, but it is also
because, in C, it is generally as easy to write somethign like a
linked list from scratch as it is to use a geenric library. Whether
this says somethign good or somethign bad about C, I'm not sure.

 

[ImpalerCore]

You can create generic structures in C by using void pointers,
function pointers, and arrays of unsigned chars to hold arbitrary
bytes.

However whilst lots of generic linked list, binary tree, exapnding
array and other libraries have been written, none of them has gained
general acceptance. This is partly because no standards body has had
sufficient influence and desire to standardise, but it is also
because, in C, it is generally as easy to write somethign like a
linked list from scratch as it is to use a geenric library. Whether
this says somethign good or somethign bad about C, I'm not sure.

While it may be easy to write a linked list from scratch for a
specific application, I think that point doesn't negate the fact that
having a generic container library would be very useful. Writing
generic containers can be quite difficult (for instance, try to create
a generic chaining hash table) and at the minimum more time consuming.

With that said, I agree with the rest of your points, and tend to
prefer void*, function pointers, casting, with limited macros to
sweeten the syntax.