#include <redblack.h> struct rbtree *rbinit ( int (*cmp)(const void *p1, const void *p2, const void *config), const void *config); void rbdestroy (struct rbtree *rb); const void *rbsearch (const void *key, struct rbtree *rb); const void *rbfind (const void *key, struct rbtree *rb); const void *rblookup (intmode, const void *key, struct rbtree *rb); const void *rbdelete (const void *key, struct rbtree *rb); void rbwalk (const struct rbtree *rb, void (*action)(const void *nodep, const VISIT which, const int depth, void *arg), void *arg); const void *rbmin (struct rbtree *rb); const void *rbmax (struct rbtree *rb);
rbinit initialises the tree, stores a pointer to the comparison routine and any config data, which may be NULL if not required. A pointer to type struct rbtree is returned and is used in subsequent calls into the redblack library.
A typical compare routine would be defined thus:
int cmp(const void *p1, const void *p2,
const void *config);
The arguments p1 and p2 are the pointers to the data to be compared. config is used to alter the behaviour of the compare routine in a fixed way. For example using the same compare routine with multiple trees - with this compare routine behaving differently for each tree. The config argument is just passed straight through to the compare routine and if not used may be set to NULL. N.B. It is very important that the compare routine be deterministic and stateless, i.e. always return the same result for the same given data.
rbdestroy destroys any tree allocated by rbinit and will free up any allocated nodes. N.B. The users data is not freed, since it is the users responsibility to store (and free) this data.
rbsearch searches the tree for an item. key points to the item to be searched for. rb points to the structure returned by rbinit. If the item is found in the tree, then rbsearch returns a pointer to it. If it is not found, then rbsearch adds it, and returns a pointer to the newly added item.
rbfind is like rbsearch, except that if the item is not found, then rbfind returns NULL.
rbdelete deletes an item from the tree. Its arguments are the same as for rbsearch.
rblookup allows the traversing of the tree. Which key is returned is determined by mode. If requested key cannot be found then rblookup returns NULL. mode can be any one of the following:
rbwalk performs depth-first, left-to-right traversal of a binary tree. root points to the starting node for the traversal. If that node is not the root, then only part of the tree will be visited. rbwalk calls the user function action each time a node is visited (that is, three times for an internal node, and once for a leaf). action, in turn, takes three arguments. The first is a pointer to the node being visited. The second is an integer which takes on the values preorder, postorder, and endorder depending on whether this is the first, second, or third visit to the internal node, or leaf if it is the single visit to a leaf node. (These symbols are defined in <search.h> which is automatically included with <redblack.h>.) The third argument is the depth of the node, with zero being the root.
rbmin is a macro which delivers the minimum (first) node in the tree.
rbmax is a macro which delivers the maximum (last) node in the tree.
rblookup is designed for ad-hoc moving around the tree (forward, backwards and jumping to new places). However this is not so good when wanting to read all the data out in sequence using RB_LUFIRST & RB_LUNEXT, since the key needs to be re-found each time, which can be particularly problematic if that key has been deleted! (see example1.c)
rbwalk actually walks the tree from beginning to end, calling a callback-function at every stage that it deals with a node. This is also useful if you want to work within the tree as you walk (e.g. deleting as you go). It is also fairly compatible with twalk(3). However it requires the use of a callback function which can be difficult to use if this needs to change the state of the routine calling rbwalk (you have to use global variables). (see example2.c)
rbopenlist, rbreadlist and rbcloselist (described in a seperate man page) work best for reading the entire tree in order, each call to readlist delivering another node. (see example3.c)
tdelete returns a pointer to the data for the item deleted, or NULL if the item was not found.
rbsearch, rbfind, and rbdelete also return NULL if rb was NULL on entry.
#include <redblack.h>
#include <stdlib.h>
#include <stdio.h>
void *xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if(p) return p;
fprintf(stderr, "insufficient memory\n");
exit(1);
}
int compare(const void *pa, const void *pb, const void *config)
{
if(*(int *)pa < *(int *)pb) return -1;
if(*(int *)pa > *(int *)pb) return 1;
return 0;
}
int main()
{
int i, *ptr;
void *val;
struct rbtree *rb;
srand(getpid());
if ((rb=rbinit(compare, NULL))==NULL)
{
fprintf(stderr, "insufficient memory\n");
exit(1);
}
for (i = 0; i < 12; i++)
{
ptr = (int *)xmalloc(sizeof(int));
*ptr = rand()&0xff;
val = rbsearch((void *)ptr, rb);
if(val == NULL) exit(1);
}
for(val=rblookup(RB_LUFIRST, NULL, rb);
val!=NULL;
val=rblookup(RB_LUNEXT, val, rb))
{
printf("%6d\n", *(int *)val);
}
rbdestroy(rb);
return 0;
}