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);
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);
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.
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.
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
.
The PDEL library was developed at Packet Design, LLC.
http://www.packetdesign.com/
Archie Cobbs ⟨archie@freebsd.org⟩