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

FreeBSD Manual Pages

  
 
  

home | help 
GTREE(3)		    Library Functions Manual		      GTREE(3)

NAME
       gtree --	generic	balanced tree library

LIBRARY
       PDEL Library (libpdel, -lpdel)

SYNOPSIS
       #include	<sys/types.h>
       #include	<stdio.h>
       #include	<pdel/util/gtree.h>

       struct gtree *
       gtree_create(void   *arg,   const   char	  *mtype,   gtree_cmp_t	 *cmp,
	   gtree_add_t *add, gtree_del_t *del, gtree_print_t print);

       void
       gtree_destroy(struct gtree **gp);

       void
       gtree_arg(struct	gtree *g);

       void *
       gtree_get(struct	gtree *g, const	void *item);

       int
       gtree_put(struct	gtree *g, const	void *item);

       int
       gtree_put_prealloc(struct gtree *g, const void *item, void *node);

       u_int
       gtree_node_size(void);

       int
       gtree_remove(struct gtree *g, const void	*item);

       u_int
       gtree_size(struct gtree *g);

       void *
       gtree_first(struct gtree	*g);

       void *
       gtree_last(struct gtree *g);

       void *
       gtree_next(struct gtree *g, const void *item);

       void *
       gtree_prev(struct gtree *g, const void *item);

       int
       gtree_traverse(struct			 gtree			   *g,
	   int (*handler)(struct gtree *g, void	*item));

       int
       gtree_dump(struct gtree *g, void	***listp, const	char *mtype);

       void
       gtree_print(struct gtree	*g, FILE *fp);

DESCRIPTION
       The  gtree  functions implement a generic balanced tree data structure.
       A balanced tree stores a	sorted set of items of type void * and guaran-
       tees O(log n) search time.  The user code  supplies  callback  routines
       for:

	  •   Comparing	two items

	  •   Housekeeping associated with adding and removing an item

       gtree_create()  creates a new tree.  The	arg parameter can be retrieved
       at any time via gtree_arg() and is otherwise ignored.  mtype is a typed
       memory type string (see typed_mem(3)) used when allocating  memory  for
       the tree.

       The  cmp,  add, del, and	print parameters are pointers to user-supplied
       callback	functions having the following types:

	  typedef int	  gtree_cmp_t(struct gtree *g,
			      const void *item1, const void *item2);
	  typedef void	  gtree_add_t(struct gtree *g, void *item);
	  typedef void	  gtree_del_t(struct gtree *g, void *item);
	  typedef const	  char *gtree_print_t(struct gtree *g, const void *item);

       The cmp function	should return an integer that is  negative,  zero,  or
       positive	 if the	first item is less than, equal to, or greater than the
       second.	This function must return values consistent with a  total  or-
       dering  of  the	items.	If not specified, item1	- item2	is used, i.e.,
       the sorting is based on the pointers themselves.

       The add and del routines, if not	NULL, will be called whenever an  item
       is  added  to,  or removed from,	the tree.  For example,	if gtree_put()
       causes a	new item to replace an old item, there will be a call  to  the
       del  function  for the old item,	followed by a call to the add function
       for the new item.  These	callbacks are typically	used to	 increase  and
       decrease	reference counts.

       The print callback (also	optional) is used by gtree_print() to print an
       item when dumping the contents of the tree for debugging.

       gtree_destroy()	destroys  a tree and free's all	associated memory.  If
       any items remain	in the tree, the del callback will be invoked once for
       each item.  Note	that this function takes a pointer to a	pointer	 to  a
       tree.  Upon return, the pointer to the tree will	be set to NULL.	 If it
       is already equal	to NULL, gtree_destroy() does nothing.

       gtree_get()  retrieves  an  item	previously stored in the tree, or else
       returns NULL if the item	is not found.

       gtree_put() adds	an item	to the tree, replacing any item	that is	 equal
       to it (as determined by the cmp callback).  NULL	is an invalid item and
       may not be stored in a tree.

       gtree_put_prealloc()  is	 equivalent  to	 gtree_put()  except  that the
       caller pre-allocates the	memory necessary to add	the item to the	 tree,
       which guarantees	a successful operation.	 node must point to memory al-
       located	with  the  same	 typed_mem(3)  memory  type  as	 was passed to
       gtree_new() and the size	of this	memory block must be at	least as large
       as  the	size   of   an	 internal   node,   which   is	 returned   by
       gtree_node_size().

       gtree_remove() removes an item from the tree.  If the item does not ex-
       ist, nothing happens.

       gtree_size() returns the	number of items	in the tree.

       gtree_first()  and  gtree_last()	return the first and last items	in the
       tree, respectively, or NULL if the tree	is  empty.   gtree_next()  and
       gtree_prev()  return the	next and previous item in the tree to item, or
       NULL if there are no more items in the  tree.   Traversing  the	entire
       tree  via  gtree_next() and gtree_prev()	takes O(n log n) time, where n
       is the number of	items in the tree.

       gtree_traverse()	traverses the items in the  tree  in  order,  invoking
       handler with each item.	If handler returns -1, the traversal stops and
       gtree_traverse()	 immediately  returns  -1  to  the caller.  Otherwise,
       gtree_traverse()	returns	0 after	all items have	been  traversed.   Any
       attempt	to modify the tree before gtree_traverse() returns will	return
       an error.

       gtree_dump() generates a	sorted array of	all the	items in the tree.   A
       pointer	to the array is	stored in *listp.  The array is	allocated with
       memory type mtype.  The caller must eventually free the array, also us-
       ing mtype.

       gtree_print() prints out	the tree for debugging purposes.

RETURN VALUES
       gtree_put() and gtree_put_prealloc() return 0 if	the item is new, or  1
       if the item replaced an existing	item.

       gtree_remove()  returns	0  if the item was not found, or 1 if the item
       was found and removed.

       gtree_dump() returns the	number of items	in the generated array.

       gtree_create(), gtree_put(), and	gtree_dump() return -1 or NULL to  in-
       dicate an error;	errno will be set to the appropriate value.

IMPLEMENTATION NOTES
       The  gtree library is designed to gracefully handle certain bugs	in the
       user code.  For example,	a reentrant call to  gtree_put()  from	within
       the  add	 callback  function  called  as	a result of a previous call to
       gtree_put() will	return an error	with errno set to EBUSY.

SEE ALSO
       ghash(3), libpdel(3), typed_mem(3)

HISTORY
       The   PDEL   library   was   developed	at   Packet    Design,	  LLC.
       http://www.packetdesign.com/

AUTHORS
       Archie Cobbs <archie@freebsd.org>

FreeBSD	ports 15.0		April 22, 2002			      GTREE(3)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=gtree_traverse&sektion=3&manpath=FreeBSD+Ports+15.0>

home | help