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 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 call- back 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 posi- tive 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 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 guar- antees 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_tra- verse() 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 mem- ory 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 Archie Cobbs <archie@freebsd.org> FreeBSD ports 15.quarterly April 22, 2002 GTREE(3)
NAME | LIBRARY | SYNOPSIS | DESCRIPTION | RETURN VALUES | IMPLEMENTATION NOTES | SEE ALSO | HISTORY | AUTHORS
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=gtree_first&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>