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

FreeBSD Manual Pages


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

     gtree -- generic balanced tree library

     PDEL Library (libpdel, -lpdel)

     #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);

     gtree_destroy(struct gtree	**gp);

     gtree_arg(struct gtree *g);

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

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

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


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

     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);

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

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

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

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

	+o   Comparing two items

	+o   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 mem-
     ory type string (see typed_mem(3))	used when allocating memory for	the

     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 pos-
     itive if the first	item is	less than, equal to, or	greater	than the sec-
     ond.  This	function must return values consistent with a total ordering
     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	func-
     tion 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	refer-
     ence 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 al-
     ready equal to NULL, gtree_destroy() does nothing.

     gtree_get() retrieves an item previously stored in	the tree, or else re-
     turns 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 allocated
     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 at-
     tempt to modify the tree before gtree_traverse() returns will return an

     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 using

     gtree_print() prints out the tree for debugging purposes.

     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	indi-
     cate an error; errno will be set to the appropriate value.

     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.

     ghash(3), libpdel(3), typed_mem(3)

     The PDEL library was developed at Packet Design, LLC.

     Archie Cobbs <>

BSD				April 22, 2002				   BSD


Want to link to this manual page? Use this URL:

home | help