It's a first implementation of polymorphic binary tree in C.
As example bintree.h was used to make generic Binary search tree (src/bst.h), and then a specific integer binary search tree (src/ibst.h).
make all compiles all sources, make clean deletes all binaries.
Integer binary search tree
#include "src/ibst.h"
bst *tree = ibst_new(8 /* initial non zero size */);
ibst_add(tree, 3);
ibst_add(tree, -2);
ibst_rm(tree, 3);
if (ibst_find(tree, -2)) {
// do something
}
ibst_free(tree)The core issue is to limit calls to malloc to create each node.
A classic stack that extends its memory by realloc.
For a constant amortized analysis it doubles its size when the stack is full.
A malloced pool manager.
-
pool_empty(sizeof_content, init_size)mallocs a pool ofinit_sizeelements and stores all free pointers in a stack. -
pool_collector(pool, free_func)enables ~garbage collector usingfree_func(that had to usepool_remove). -
pool_slot(pool)provides pointer to asizeof_contentfree area.If the pool is full:
-
if there is a garbage collector function, it will call it on every elements to find a free slot.
-
else, it mallocs a new area and double its size.
-
Again, constant amortized analysis.
-
pool_remove(pool, ptr)explicitly free this element
Provide basic tree functions. Trees are like Directed acyclic graph in order to share node between branches. Therefore nodes can have several parents.
-
bt_new(sizeof_content, init_size, bool)create a binary tree.boolis a way to chose garbage collector on your nodes (for instance it's useless in bst.c). -
bt_root(bt)returnnilnode if the tree is empty, otherwise the root.To create a root use
bt_newr(bt_root(bt), root)and don't touch much thenilnode ;) -
bt_nil(bt)return thenilnode of the binary tree. -
bt_root_nil(bt)remove the root of thebttree.Root doesn't have parent so there is a specific function to delete the root.
-
bt_node(bt)return a whole new node usingpool_slot. -
bt_newr(parent, right)placerightas the right child ofparent(rightcan bebt_nil(bt)) -
bt_newl(parent, left)similar to above.
-
node_right(node)return the right child ofnode -
node_left(node)a bit like above -
node_data(node)return pointer to area to store data. -
node_parent(node)don't have too much sens in a directed acyclic graph, but return the latest parent assigned ofnode, which is useful in classic tree like bst.
-
bt_node_free(bt, node)must be use to explicitly remove a node from memory -
bt_free(bt)free the whole tree ans nodes
make test executes all test.
All executables were checked by valgrind and remained without leak memory so far.