Lines Matching refs:tree
121 avl_walk(avl_tree_t *tree, void *oldnode, int left) in avl_walk() argument
123 size_t off = tree->avl_offset; in avl_walk()
168 avl_first(avl_tree_t *tree) in avl_first() argument
172 size_t off = tree->avl_offset; in avl_first()
174 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) in avl_first()
187 avl_last(avl_tree_t *tree) in avl_last() argument
191 size_t off = tree->avl_offset; in avl_last()
193 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) in avl_last()
211 avl_nearest(avl_tree_t *tree, avl_index_t where, int direction) in avl_nearest() argument
216 size_t off = tree->avl_offset; in avl_nearest()
219 ASSERT(tree->avl_root == NULL); in avl_nearest()
226 return (avl_walk(tree, data, direction)); in avl_nearest()
240 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where) in avl_find() argument
246 size_t off = tree->avl_offset; in avl_find()
248 for (node = tree->avl_root; node != NULL; in avl_find()
253 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); in avl_find()
287 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) in avl_rotation() argument
366 tree->avl_root = child; in avl_rotation()
449 tree->avl_root = gchild; in avl_rotation()
466 avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) in avl_insert() argument
473 size_t off = tree->avl_offset; in avl_insert()
475 ASSERT(tree); in avl_insert()
485 ++tree->avl_numnodes; in avl_insert()
497 ASSERT(tree->avl_root == NULL); in avl_insert()
498 tree->avl_root = node; in avl_insert()
540 (void) avl_rotation(tree, node, new_balance); in avl_insert()
557 avl_tree_t *tree, in avl_insert_here() argument
568 ASSERT(tree != NULL); in avl_insert_here()
577 node = AVL_DATA2NODE(here, tree->avl_offset); in avl_insert_here()
580 diff = tree->avl_compar(new_data, here); in avl_insert_here()
591 diff = tree->avl_compar(new_data, in avl_insert_here()
592 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
600 diff = tree->avl_compar(new_data, in avl_insert_here()
601 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
609 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); in avl_insert_here()
616 avl_add(avl_tree_t *tree, void *new_node) in avl_add() argument
628 if (avl_find(tree, new_node, &where) != NULL) in avl_add()
635 avl_insert(tree, new_node, where); in avl_add()
662 avl_remove(avl_tree_t *tree, void *data) in avl_remove() argument
673 size_t off = tree->avl_offset; in avl_remove()
675 ASSERT(tree); in avl_remove()
721 tree->avl_root = node; in avl_remove()
742 ASSERT(tree->avl_numnodes > 0); in avl_remove()
743 --tree->avl_numnodes; in avl_remove()
759 tree->avl_root = node; in avl_remove()
802 else if (!avl_rotation(tree, node, new_balance)) in avl_remove()
807 #define AVL_REINSERT(tree, obj) \ argument
808 avl_remove((tree), (obj)); \
809 avl_add((tree), (obj))
887 avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), in avl_create() argument
890 ASSERT(tree); in avl_create()
898 tree->avl_compar = compar; in avl_create()
899 tree->avl_root = NULL; in avl_create()
900 tree->avl_numnodes = 0; in avl_create()
901 tree->avl_size = size; in avl_create()
902 tree->avl_offset = offset; in avl_create()
910 avl_destroy(avl_tree_t *tree) in avl_destroy() argument
912 ASSERT(tree); in avl_destroy()
913 ASSERT(tree->avl_numnodes == 0); in avl_destroy()
914 ASSERT(tree->avl_root == NULL); in avl_destroy()
922 avl_numnodes(avl_tree_t *tree) in avl_numnodes() argument
924 ASSERT(tree); in avl_numnodes()
925 return (tree->avl_numnodes); in avl_numnodes()
929 avl_is_empty(avl_tree_t *tree) in avl_is_empty() argument
931 ASSERT(tree); in avl_is_empty()
932 return (tree->avl_numnodes == 0); in avl_is_empty()
957 avl_destroy_nodes(avl_tree_t *tree, void **cookie) in avl_destroy_nodes() argument
963 size_t off = tree->avl_offset; in avl_destroy_nodes()
969 first = avl_first(tree); in avl_destroy_nodes()
989 if (tree->avl_root != NULL) { in avl_destroy_nodes()
990 ASSERT(tree->avl_numnodes == 1); in avl_destroy_nodes()
991 tree->avl_root = NULL; in avl_destroy_nodes()
992 tree->avl_numnodes = 0; in avl_destroy_nodes()
1002 ASSERT(tree->avl_numnodes > 1); in avl_destroy_nodes()
1003 --tree->avl_numnodes; in avl_destroy_nodes()
1041 ASSERT(node == tree->avl_root); in avl_destroy_nodes()