GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  GTREE (3)

NAME

gtree - generic balanced tree library

CONTENTS

Library
Synopsis
Description
Return Values
Implementation Notes
See Also
History
Authors

LIBRARY

PDEL Library (libpdel, -lpdel)

SYNOPSIS


.In sys/types.h
.In stdio.h
.In 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 guarantees 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 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 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 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 exist, 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 using 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 indicate 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


.An Archie Cobbs Aq archie@freebsd.org
Search for    or go to Top of page |  Section 3 |  Main Index


Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.