Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
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 man-
       age a redblack balanced binary tree.  They are generalized from "Intro-
       duction 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 com-
       parison	routine,  which	 takes pointers	to three items.	 The first two
       are pointers to the data	to be compared.	The last is some  static  con-
       figuration data which is	passed to the comparison routine each time. It
       should return an	integer	which is negative, zero, or positive,  depend-
       ing  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  con-
       fig 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 re-
       turns 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  vis-
       ited.   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  au-
       tomatically  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, back-
       wards 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 call-
       back-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  re-
       quires  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 insuffi-
       cient 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  in-
       sufficient  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  en-
       try.

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)

NAME | SYNOPSIS | DESCRIPTION | READING BACK THE DATA | RETURN VALUE | WARNINGS | EXAMPLE | CONFORMING TO | SEE ALSO

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=rbinit&sektion=3&manpath=FreeBSD+12.1-RELEASE+and+Ports>

home | help