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");

Procedural Terrain Generation

Windows Forms Launcher Window

I've often been interested in groups of algorithms that offer procedural generation of gameplay environments.  There is a rather wide range for these algorithms, both in computational time and complexity.  Some algorithms, such as Diamond Square are rather trivial to implement.  Others, such as the algorithms behind the MMO Love, are obviously much more in depth.  Since I'm about to explore a hybrid of these algorithms (Perlin Noise and others) I figured I'd resort back to an old project I worked on concerning terrain generation.  The idea of the project was to act as a tool to demonstrate how certain algorithms worked and compare them (as well as get some more experience with OpenGL 4).  The final launcher looked something like that on the right.  A drop-down of the algorithm, a radio select rendering mode, and algorithm specific settings.  The user could launch multiple windows and compare the differences.  This served as a rather effective tool for differentiating different methods and the effect of algorithm variables on the output (e.g. generating a terrain map with a decay rate of 0.3 instead of 0.7).  With a simple rotating camera and variable zoom levels, the user could inspect the final results of their work.

Diamond Square with high variation and low decay

It was nice to have effective proof of the weaknesses these algorithms have.  For example, Diamond Square in it's normal form, is prone to artifacts (especially with typical linear congruential number generation) and frequently builds mountains.  We also found sequential random additions was decent at generating rolling hills, but not smooth ones that often resembled cones.

All in all, procedural worlds won't replace the mapmaker anytime soon, but they are a powerful tool, and can serve as a nice base that can be tweaked and remodeled later.  I'd recommend game programmers become familiar with Diamond Square and Perlin Noise at the very least.

With a greater decay and lower variation

Wireframe View

  Go To the Project Page

SRT Moved to GitHub

Since Git as a VCS has become more prominent and the popularity of the service GitHub has (rightfully) skyrocketed, I finally got around to putting the Simple SDL RayTracer onto GitHub.  Not everyone in the industry uses SVN so it's high time I got comfortable with something else too.  If you've been holding off on Git because the clients have been bad I don't really blame you.  But they have gotten much better since I first tried them out, especially on Windows, and are frequently being offered as plugins for IDEs if that's the sorta thing you're into.