rbdestroy man page on DragonFly

Man page or keyword search:  
man Server   44335 pages
apropos Keyword Search (all sections)
Output format
DragonFly logo
[printable version]

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
       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  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
       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, 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
       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 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
       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)
[top]

List of man pages available for DragonFly

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net