Lines Matching full:tree
30 * This file defines the interface for a B-Tree implementation for ZFS. The
31 * tree can be used to store arbitrary sortable data types with low overhead
32 * and good operation performance. In addition the tree intelligently
35 * Note that for all B-Tree functions, the values returned are pointers to the
36 * internal copies of the data in the tree. The internal data can only be
38 * with respect to any other elements in the tree.
40 * The major drawback of the B-Tree is that any returned elements or indexes
45 * The B-Tree has two types of nodes: core nodes, and leaf nodes. Core
49 * layer of the tree. Unlike B+ Trees, in this B-Tree implementation the
51 * elements. Each element occurs only once in the tree, no matter what kind
54 * The tree's height is the same throughout, unlike many other forms of search
55 * tree. Each node (except for the root) must be between half minus one and
60 * This tree was implemented using descriptions from Wikipedia's articles on
138 * T - The element type stored inside the B-Tree.
148 NAME(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems, \
152 (void) tree; \
180 * Initialize an B-Tree. Arguments are:
182 * tree - the tree to be initialized
185 * find - optional function to accelerate searches inside B-Tree nodes
200 * Find a node with a matching value in the tree. Returns the matching node
211 * Insert a node into the tree.
219 * Return the first or last valued node in the tree. Will return NULL if the
220 * tree is empty. The index can be NULL if the location of the first or last
227 * Return the next or previous valued node in the tree. The second index can
237 * Get a value from a tree and an index.
242 * Add a single value to the tree. The value must not compare equal to any
243 * other node already in the tree. Note that the value will be copied out, not
250 * Remove a single value from the tree. The value must be in the tree. The
251 * pointer passed in may be a pointer into a tree-controlled buffer, but it
257 * Remove the value at the given location from the tree.
262 * Return the number of nodes in the tree
267 * Used to destroy any remaining nodes in a tree. The cookie argument should
269 * removed from the tree and may be free()'d. Returns NULL when the tree is
273 * and finally zfs_btree_destroy(). No other B-Tree routines will be valid.
279 * zfs_btree_t *tree;
284 * while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL)
286 * zfs_btree_destroy(tree);
291 * Destroys all nodes in the tree quickly. This doesn't give the caller an
298 * Final destroy of an B-Tree. Arguments are:
300 * tree - the empty tree to destroy
302 void zfs_btree_destroy(zfs_btree_t *tree);
305 void zfs_btree_verify(zfs_btree_t *tree);