|
|
#include <rbtree.h>RBTree *rbt_init(size_t n, int (*cmp)(const void *, const void *), void *(*alloc)(size_t), void (*toss)(const void *));
void rbt_walk(RBTree *rbtp, int order, void (*operate)(const void *));
void rbt_free(RBTree *rbtp);
void *rbt_find(RBTree *rbtp, const void *item);
void *rbt_insert(RBTree *rbtp, const void *item);
in rbt_delete(RBTree *rbtp, const void *item);
A tree is traversed by calling rbt_walk. The six different regular traversals are specified by the order argument. It is exactly one of RBT_PREORDER, RBT_INORDER, or RBT_POSTORDER, optionally combined (bitwise OR) with RBT_REVERSE. A ``preorder'' traversal visits the parent before either child, a ``postorder'' traversal visits the parent after any child, and an ``inorder'' traversal visits the parent between the two children. Unless RBT_REVERSE is specified, the children are visited in ascending order (as specified by the cmp argument). Visiting a node causes the function pointed to by the operate argument to be called, being passed a pointer to the start of that node's data.
For the remaining functions, item points to a particular data item to which the function is to be applied.
A data item can be searched for without modifying the tree by calling rbt_find. rbt_insert acts just like rbt_find except the data will be added to the tree if a match is not found. And, rbt_delete will remove the item from the tree if it was present.
rbt_find returns a null pointer if no match for the data is found; otherwise it returns a pointer to the start of the matching data.
rbt_delete returns nonzero when no match for the item is present in the tree; otherwise it returns zero having found a match and removed it from the tree.
#include <rbtree.h> #include <stdio.h> #include <string.h>If the above is invoked with the three arguments ``aa cc bb'', it will output these three lines:static int compare(const void *p1, const void *p2) { return strcmp(*(const char **)p1, *(const char **)p2); }
static void print(const void *p) { puts(*(const char **)p); }
int main(int argc, char **argv) { const char *s; RBTree *rbtp;
if ((rbtp = rbt_init(sizeof(const char *), &compare, 0, 0)) == 0) return 2; while ((s = *++argv) != 0) { if (rbt_insert(rbtp, &s) == 0) return 2; } rbt_walk(rbtp, RBT_INORDER|RBT_REVERSE, &print); rbt_free(rbtp); return 0; }
cc bb aa