Background

Examples

List

// Define your struct somewhere.structObject {intsome_value;    ...// Don't forget to embed the ListNode!ListNodenode;};...// Create some Object variables.structObjectobj1,obj2;obj1.some_value=1;obj2.some_value=2;// Create your List.Listmy_list;list_init(&my_list);// Populate your List. Notice how the API abstracts itself and only cares about the ListNode.list_insert_back(&my_list,&obj1.node);list_insert_back(&my_list,&obj2.node);// Let's see what is stored in the List:inti=1;ListNode*n;list_for_each(n,&my_list) {if (i==1) {assert(n==&obj1.node);    }elseif (i==2){assert(n==&obj2.node);    }++i;}...// Let's get the ListNode at the front of the List.ListNode*front_node_ptr=list_front(&my_list);// Getting the "node" member from an Object variable is easy: ("obj1.node"),// but how do you get the Object variable when you only have the "node" member?// Solution: the macro "list_entry":structObject*obj_ptr=list_entry(front_node_ptr,structObject,node);assert(obj_ptr==&obj1);

RBTree

// Define your struct somewhere.structObject {intkey;    ...// Don't forget to embed the RBTreeNode!RBTreeNodenode;};...// You must define a compare function which compares a key with the key of a RBTreeNode.intcompare(constvoid*some_key,constRBTreeNode*some_node) {return*(constint*)some_key-rbtree_entry(some_node,structObject,node)->key;}// You can OPTIONALLY define a collide function which handles key collisions. When a key// collision happens, no matter what, the old RBTreeNode will be replaced by the new// RBTreeNode. If this function is defined, then it will be called after the old// RBTreeNode is replaced in the RBTree. This function is great if you need to free up// resources in the Object variable pertaining to the discarded RBTreeNode. This function// is also great for enabling multi-key functionality in the RBTree.voidcollide(constRBTreeNode*old_node,constRBTreeNode*new_node,void*auxiliary_data) {// When a RBTree is created, we can give it auxiliary data to hold onto. This data is then// passed to this function for usage. This data, for example, could be a memory pool struct// that is needed to free up the resources used by the Object variable pertaining to the// old_node parameter.    ...}...// Create some Object variables.structObjectobj1,obj2;obj1.key=1;obj2.key=2;// Create you RBTree. In this case we don't have any auxiliary data that needs to be used// in the collide function, so we just pass NULL. As previously mentioned, the collide// function itself is optional. If you don't need to do any special resource management,// just pass "NULL" in place of "collide" in the initialize function.RBTreemy_rbtree;rbtree_init(&my_rbtree,compare,collide,NULL);// Populate your RBTree. Notice how the API abstracts itself and only cares about the// RBTreeNode and its key. Because red black trees are always ordered in some way, order// of insertion will never affect the inorderness of the tree.rbtree_insert(&my_rbtree,&obj2.key,&obj2.node);rbtree_insert(&my_rbtree,&obj1.key,&obj1.node);// Because of the way our compare function is designed, the RBTree stores its RBTreeNodes// inorder from smallest key to greatest key. Let's see what is stored in the RBTree:inti=1;RBTreeNode*n;rbtree_for_each(n,&my_rbtree) {if (i==1) {assert(n==&obj1.node);    }elseif (i==2) {assert(n==&obj2.node);    }++i;}...// Let's get the RBTreeNode with the greatest key.RBTreeNode*greatest_node_ptr=rbtree_last(&my_rbtree);// Getting the "node" member from an Object variable is easy: ("obj1.node"),// but how do you get the Object variable when you only have the "node" member?// Solution: the macro "rbtree_entry":structObject*obj_ptr=rbtree_entry(greatest_node_ptr,structObject,node);assert(obj_ptr==&obj2);

HashTable

// Define your struct somewhere.structObject {intkey;    ...// Don't forget to embed the HashTableNode!HashTableNodenode;};...// You must define a hash function which takes in a key and returns its hashcode. In this// case we aren't going to do anything fancy since this is just an example.size_thash(constvoid*key) {return*(constint*)key;}// You must define an equal function which determines if a key is equal to the key of a HashTableNode.intequal(constvoid*some_key,constHashTableNode*some_node) {return*(constint*)some_key==hashtable_entry(some_node,structObject,node)->key;}// You can OPTIONALLY define a collide function which handles key collisions. When a key// collision happens, no matter what, the old HashTableNode will be replaced by the new// HashTableNode. If this function is defined, then it will be called after the old// HashTableNode is replaced in the HashTable. This function is great if you need to free up// resources in the Object variable pertaining to the discarded HashTableNode. This function// is also great for enabling multi-key functionality in the HashTable.voidcollide(constHashTableNode*old_node,constHashTableNode*new_node,void*auxiliary_data) {// When a HashTable is created, we can give it auxiliary data to hold onto. This data is then// passed to this function for usage. This data, for example, could be a memory pool struct// that is needed to free up the resources used by the Object variable pertaining to the// old_node parameter.    ...}...// Create some Object variables.structObjectobj1,obj2;obj1.key=1;obj2.key=2;// You must create a bucket array which is an array of pointers to HashTableNodes. This// array is used by the HashTable for the duration of its lifetime. In this case we will// have 50 buckets in the bucket array.HashTableNode*bucket_array[50];// Create you HashTable. In this case we don't have any auxiliary data that needs to be used// in the collide function, so we just pass NULL. As previously mentioned, the collide// function itself is optional. If you don't need to do any special resource management,// just pass "NULL" in place of "collide" in the initialize function.HashTablemy_hashtable;hashtable_init(&my_hashtable,bucket_array,50,hash,equal,collide,NULL);// Populate your HashTable. Notice how the API abstracts itself and only cares about the// HashTableNode and its key.hashtable_insert(&my_hashtable,&obj1.key,&obj1.node);hashtable_insert(&my_hashtable,&obj2.key,&obj2.node);// HashTable provides no guarantee on the ordering of HashTableNodes in the bucket array.// Let's see what is stored in the HashTable:intsum_of_keys=0,bucket_index;HashTableNode*n;hashtable_for_each(n,bucket_index,&my_hashtable) {sum_of_keys+=hashtable_entry(n,structObject,node)->key;}assert(sum_of_keys==3);...// Let's get the HashTableNode with the key that equals 1.intkey=1;HashTableNode*node_ptr=hashtable_lookup_key(&my_hashtable,&key);// Getting the "node" member from an Object variable is easy: ("obj1.node"),// but how do you get the Object variable when you only have the "node" member?// Solution: the macro "hashtable_entry":structObject*obj_ptr=hashtable_entry(node_ptr,structObject,node);assert(obj_ptr==&obj1);

Stack

// Define your struct somewhere.structObject {intsome_value;    ...// Don't forget to embed the StackNode!StackNodenode;};...// Create some Object variables.structObjectobj1,obj2;obj1.some_value=1;obj2.some_value=2;// Create your Stack.Stackmy_stack;stack_init(&my_stack);// Populate your Stack. Notice how the API abstracts itself and only cares about the StackNode.stack_push(&my_stack,&obj1.node);stack_push(&my_stack,&obj2.node);// Let's see what is stored in the Stack:inti=1;StackNode*n;stack_for_each(n,&my_stack) {if (i==1) {assert(n==&obj2.node);    }elseif (i==2){assert(n==&obj1.node);    }++i;}...// Let's get the StackNode at the top of the Stack.StackNode*top_node_ptr=stack_peek(&my_stack);// Getting the "node" member from an Object variable is easy: ("obj1.node"),// but how do you get the Object variable when you only have the "node" member?// Solution: the macro "stack_entry":structObject*obj_ptr=stack_entry(top_node_ptr,structObject,node);assert(obj_ptr==&obj2);

Queue

// Define your struct somewhere.structObject {intsome_value;    ...// Don't forget to embed the QueueNode!QueueNodenode;};...// Create some Object variables.structObjectobj1,obj2;obj1.some_value=1;obj2.some_value=2;// Create your Queue.Queuemy_queue;queue_init(&my_queue);// Populate your Queue. Notice how the API abstracts itself and only cares about the QueueNode.queue_push(&my_queue,&obj1.node);queue_push(&my_queue,&obj2.node);// Let's see what is stored in the Queue:inti=1;QueueNode*n;queue_for_each(n,&my_queue) {if (i==1) {assert(n==&obj1.node);    }elseif (i==2){assert(n==&obj2.node);    }++i;}...// Let's get the QueueNode at the front of the Queue.QueueNode*front_node_ptr=queue_peek(&my_queue);// Getting the "node" member from an Object variable is easy: ("obj1.node"),// but how do you get the Object variable when you only have the "node" member?// Solution: the macro "queue_entry":structObject*obj_ptr=queue_entry(front_node_ptr,structObject,node);assert(obj_ptr==&obj1);

Installation

Running Tests

make

cd tests/makegcc test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -pedantic-errors -std=c89./test_list C89PASSED: List C89rm -f test_listgcc test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -std=gnu89./test_list GNU89PASSED: List GNU89rm -f test_listg++ test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -pedantic-errors -std=c++11./test_list C++11PASSED: List C++11rm -f test_listg++ test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -std=gnu++11./test_list GNU++11PASSED: List GNU++11rm -f test_listgcc test_rbtree.c ../src/rbtree.c -o test_rbtree -Wall -Wextra -Werror -pedantic-errors -std=c89./test_rbtree C89PASSED: RBTree C89rm -f test_rbtreegcc test_rbtree.c ../src/rbtree.c -o test_rbtree -Wall -Wextra -Werror -std=gnu89./test_rbtree GNU89PASSED: RBTree GNU89etc... (this goes on for a while)

Contributing