NAME

LIBRARY

SYNOPSIS

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

• 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 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_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

SEE ALSO

HISTORY

AUTHORS