DragonFly On-Line Manual Pages
RBINIT(3) Linux Programmer's Manual RBINIT(3)
NAME
rbinit, rbdestroy, rbsearch, rbfind, rbdelete, rbwalk - manage a red-
black binary tree
SYNOPSIS
#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);
DESCRIPTION
rbinit, rbdestroy, rbsearch, rbfind, rblookup, rbdelete and rbwalk
manage a redblack balanced binary tree. They are generalized from
"Introduction to Algorithms" by Cormen, Leiserson & Rivest. The last
field in each node of the tree is a pointer to the corresponding data
item. (The calling program must store the actual data.) cmp points to
a comparison routine, which takes pointers to three items. The first
two are pointers to the data to be compared. The last is some static
configuration data which is passed to the comparison routine each time.
It should return an integer which is negative, zero, or positive,
depending on whether the first item is less than, equal to, or greater
than the second.
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:
RB_LUEQUAL
Returns node exactly matching the key. This is equivalent to
rbfind
RB_LUGTEQ
Returns the node exactly matching the specified key, if this is
not found then the next node that is greater than the specified
key is returned.
RB_LULTEQ
Returns the node exactly matching the specified key, if this is
not found then the next node that is less than the specified key
is returned.
RB_LUGREAT
Returns the node that is just greater than the specified key -
not equal to. This mode is similar to RB_LUNEXT except that the
specified key need not exist in the tree.
RB_LULESS
Returns the node that is just less than the specified key - not
equal to. This mode is similar to RB_LUPREV except that the
specified key need not exist in the tree.
RB_LUNEXT
Looks for the key specified, if not found returns NULL. If the
node is found returns the next node that is greater than the one
found (or NULL if there is no next node). This is used to step
through the tree in order.
RB_LUPREV
Looks for the key specified, if not found returns NULL. If the
node is found returns the previous node that is less than the
one found (or NULL if there is no previous node). This is used
to step through the tree in reverse order.
RB_LUFIRST
Returns the first node in the tree (i.e. the one with the lowest
key). The argument key is ignored.
RB_LULAST
Returns the last node in the tree (i.e. the one with the largest
key). The argument key is ignored.
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.
READING BACK THE DATA
There are essentially three different ways that the data can be read
out of the tree. Each with different optimisations.
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)
RETURN VALUE
rbinit returns a pointer to the new tree, NULL if there was
insufficient memory to allocate the structure. rbdestroy has no return
value. rbwalk has no return value. rbsearch returns a pointer to a
matching item in the tree, or to the newly added item, or NULL if there
was insufficient memory to add the item. rbfind returns a pointer to
the item, or NULL if no match is found. If there are multiple elements
that match the key, the element returned is unspecified.
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.
WARNINGS
rbdelete frees the memory required for the node in the tree. The user
is responsible for freeing the memory for the corresponding data.
EXAMPLE
The following program inserts twelve random numbers into a binary tree,
then prints the numbers in order.
#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;
}
CONFORMING TO
SVID
SEE ALSO
rbopenlist(3), rbgen(1), tsearch(3).
GNU May 23, 2000 RBINIT(3)