Update to CDS

Doxygen Documentation Makes Learning the API Much Easier

With new found (but short lived) free time over the break, I got around to committing a major new release of the CDS Library.  In addition to a host of new functions and finished structures, I made everything compatible with ANSI C and implemented Doxygen Documentation.  Other annoyances, such as const correctness have been ironed out, and all of the examples have been rewritten in a way that tries to teach new users how everything works.  CDS is still relatively new, and could benefit from more iterations and tweaking.  However, at this time it is pretty solid given the time constraints.  Functionality, style, and typenames are much more consistent now.  As usual, you can always find the latest version of CDS on GitHub. 

Browse CDS on GitHub

You can refer to my first post on CDS for more information here. Enjoy!

Below is a simple example program demonstrating the usage of a cds_dynamic_array:

int main(void) {
     /* create the array */
     cds_dynamic_array *array = NULL;
     unsigned int size = CDS_DEFAULT_DYNAMIC_ARRAY_SIZE; /* 4 by default */
     cds_result cr = cds_dynamic_array_create(&array, size); /* notice the address of the pointer is passed in */
    
     /* checks for an error, prints and returns 1 if something failed
      * we do this (in this example) repeatedly for safety
      */
     if (cds_error_check(cr)) return 1;
 
     /* add the strings to the container */
     char * presidents[] = {"washington", "jefferson", "roosevelt", "reagan", "clinton", "obama"};
     unsigned int numPresidents = 6;
     unsigned int i;
     for (i = 0; i < numPresidents; ++i) {
          cr = cds_dynamic_array_push_back(array, presidents[i]); /* will need to reallocate when i == 4 */
          if (cds_error_check(cr)) return 1;
     }
 
     /* print out the array */
     cds_log("Displaying the contents of the dynamic array...\n");
     logArray(array, 1);
 
     /* try adding past the current size of the array */
     void *curValue;
     cds_log("Adding some more strings to the container...\n");
     char *otherPresidents[] = {"adams", "bush", "coolidge", "kennedy"};
     unsigned int numOtherPresidents = 4;
     /* since the default size is 4, we've grown once, 4 * 1.5 = 6 */
     /* therefore, on the next insertion, the array will need to grow */
     /* we can use a custom growth function, to resize things differently */
     for (i = 0; i < numOtherPresidents; ++i) {
          cr = cds_dynamic_array_push_back_gf(array, otherPresidents[i], &arrayDoubleGrowth);
          if (cds_error_check(cr)) return 1;
     }
 
     /* lets try printing the array using an iterate function */
     cds_log("Printing the contents of the array using the iterate function...\n");
     cr = cds_dynamic_array_iterate(array, &printString2);
     if (cds_error_check(cr)) return 1;
 
     /* accessing the last element first just for the sake of printing it */
     unsigned int count = cds_dynamic_array_count(array);
     cr = cds_dynamic_array_get(array, count - 1, &curValue);
     cds_log("Removing the last element in the collection: %s", (char *)curValue);
 
     /* remove the element at the end of the array */
     cr = cds_dynamic_array_pop_back(array);
     if (cds_error_check(cr)) return 1;
 
     /* this will remove the element from the container, but give it as a pointer */
     cr = cds_dynamic_array_pop_back_data(array, &curValue);
     if (cds_error_check(cr)) return 1;
     cds_log("Removed: %s from the back of the array\n", (char *) curValue);
 
     /* remove functions will rely on pointer addresses by default
      * we know that roosevelt's address is in the array so this will work */
     cr = cds_dynamic_array_remove(array, presidents[2]);
     if (cds_error_check(cr)) return 1;
 
     /* if we want to remove with value equality, we must use the cmp functions 
      * so while "adams" is in the array, this is a new address
      */
     char adamsStr[] = "adams";
     cr = cds_dynamic_array_remove(array, adamsStr);
     char resultString[CDS_RESULT_MAX_STR_LEN];
     cds_result_string(cr, resultString);
     cds_log("Attempt to remove the same string at a different address: %s\n", resultString);
 
     /* if we use our strcmp equivalent, this can be done with the proper function */
     cr = cds_dynamic_array_remove_cmp(array, adamsStr, &cmpStr);
     cds_result_string(cr, resultString);
     cds_log("Attempt to remove the same string using the comparison function: %s\n", resultString);
 
     logArray(array, 0);
 
     /* you can also remove elements by index (with safe bounds checking) */
     cds_log("Removing from index 2...\n");
     cr = cds_dynamic_array_remove_at(array, 2);
     logArray(array, 0);
 
     /* The dynamic array supports multiple removal behavoirs
      * By default it is shift down, which maintains the relative order of elements
      * if remove_at(2) CDS_SHIFT DOWN: a b c d e f becomes a b d e f
      * It also supports replacing the removed element with the element at the end
      * This disrupts the relative order of elements, but is more efficient than shifting large arrays
      * if remove_at(2) CDS_REPLACE_WITH_LAST a b c d e f becomes a b f d e
      */
     cds_log("Removing from index 2 using CDS_REPLACE_WITH_LAST\n");
     cr = cds_dynamic_array_remove_at_rb(array, 2, CDS_REPLACE_WITH_LAST);
     logArray(array, 0);
 
     /* Reverse the relative order of elements */
     cds_log("Reversing the order of elements in the dynamic array...\n");
     cr = cds_dynamic_array_reverse(array);
     logArray(array, 0);
 
     cds_log("Deleting the dynamic array...\n");
     cr = cds_dynamic_array_delete(&array);
     if (cds_error_check(cr)) return 1;
     cds_log("Deletion successful...\n");
     return 0;
}

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