Introducing CDS (The C Data Structures Library)

CDS was a side project to demonstrate I can write efficient data structures in a procedural language like C.  It currently supports all types (with void pointers) with the following data structures:

• dynamic array (cds_dynamic_array)
• singly linked list (cds_slist)
• doubly linked list (cds_dlist)
• stack (cds_stack)
• queue (cds_queue)
• binary search tree (cds_binary_tree)
• hash table (cds_hash_table) 

CDS tries to use consistent practices amongst the entire code base.  Every custom type, function, and macro starts with the cds_ or CDS_ prefix.  Data structure functions are typically structured in the following way: cds_datastructurename_function().  Therefore, to push_back an element onto a dynamic array you would call cds_dynamic_array_push_back(array, data);  This tends to make function calls and type names long, but is good practice, keeps things consistent, and avoids polluting the namespace.

Every data structure function returns a cds_result enum.  Every error code that could be thrown in any of the provided functions is a cds_result.  This keeps results more informative, consistent, and performance friendly.  Rather than returning -1 or NULL when an error occurs, it returns more specific information (e.g. CDS_BAD_ALLOC).  This is better practice because a number of things can potentially go wrong with a given operation, and this tries to ease the amount of time spent guessing.

Common operations include:
    create: allocates the given structure
    clear: removes the elements from the given structure
    delete: deletes the given structure (but not its elements)
    delete_all: deletes the given structure and its pointers to other elements
    add/push_back/insert/etc: adds the pointer to the structure
    remove/pop_back/pop/etc: removes a pointer from the structure
    count: get the current count of the structure
    find: search for a pointer address or do a value comparison via a cds_cmp_func
    iterate: passes every data type in the container safely to the given cds_visit_func

Assertions are given but not fully apparent in all of the code.  They can be compiled out of runtime code since they use optional macros.  There is support for custom memory allocators and log functions that can be interchanged easily at run/compile time so long as they match the function format of their stdlib equivalents.  Other intricacies include custom growth behavoirs, type specific comparisons, and more through function pointers, enums, and macros.

This code is still unfinished and in a relatively early state.  Since school and work keep getting in the way I'm releasing it now but intend on improving it later.  The code is free for non commercial use and commercially with permission (contact email given in the README).  Use at your own risk!

Browse CDS on GitHub

Here's a sample program example demonstrating cds_stack.  You'll see similar semantics for the rest of the data structures too.

UPDATE: I've revisited the library and am no longer so strict on the "every function returns an error result" philosophy.  Sometimes it is excessive and  actually makes code more error prone.  However, a vast majority of the functions still follow the old format.
UPDATE 2: CDS has received a significant new release, with full ANSI C compatibility, Doxygen Documentation, new functions, rewritten examples, and a host of bug fixes.  You can read about it here.

/* Create the stack */
cds_log("Running the stack test...\n");
cds_stack *stack = NULL;
cds_result cr = cds_stack_create(&stack);
if (cds_error_check(cr))
        return 1;
 
/* Add the values to the stack */
cds_log("Adding the usual values...\n");
int values[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
unsigned int n = 10;
unsigned int i;
for (i = 0; i < n; ++i) {
        cr = cds_stack_push(stack, values + i);
        if (cds_error_check(cr))
                return 1;
}
 
logStack(stack, 1);
 
/* Clean up the stack */
cds_log("Popping everything off the stack...\n");
int *top = NULL;
/* if you want to allow null values in your stack 
 * use cds_stack_count() instead */
while ((top = cds_stack_top(stack)) != NULL) {
        cds_log("Pop: %d\n", *(int *)top);
        cr = cds_stack_pop(stack);
        if (cds_error_check(cr))
                return 1;
}
 
/* if you call pop on an empty stack it returns CDS_UNDERFLOW */
cds_log("The stack is now clear.  Count: %u\n", cds_stack_count(stack));
cds_log("If you try to pop an empty stack, it will return: ");
cr = cds_stack_pop(stack);
char resultString[CDS_RESULT_MAX_STR_LEN];
cds_result_string(cr, resultString);
cds_log("%s\n", resultString);
 
/* you can also iterate on a stack like all the other data structures 
 * but we don't do that here
 */
cds_log("Deleting the stack...\n");
cr = cds_stack_delete(&stack);
if (cds_error_check(cr))
        return 1;
cds_log("Deletion successful...\n");