Lines Matching refs:node
124 avl_node_t *node = AVL_DATA2NODE(oldnode, off); in avl_walk() local
132 if (node == NULL) in avl_walk()
141 if (node->avl_child[left] != NULL) { in avl_walk()
142 for (node = node->avl_child[left]; in avl_walk()
143 node->avl_child[right] != NULL; in avl_walk()
144 node = node->avl_child[right]) in avl_walk()
151 was_child = AVL_XCHILD(node); in avl_walk()
152 node = AVL_XPARENT(node); in avl_walk()
153 if (node == NULL) in avl_walk()
160 return (AVL_NODE2DATA(node, off)); in avl_walk()
170 avl_node_t *node; in avl_first() local
174 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) in avl_first()
175 prev = node; in avl_first()
189 avl_node_t *node; in avl_last() local
193 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) in avl_last()
194 prev = node; in avl_last()
214 avl_node_t *node = AVL_INDEX2NODE(where); in avl_nearest() local
218 if (node == NULL) { in avl_nearest()
222 data = AVL_NODE2DATA(node, off); in avl_nearest()
242 avl_node_t *node; in avl_find() local
248 for (node = tree->avl_root; node != NULL; in avl_find()
249 node = node->avl_child[child]) { in avl_find()
251 prev = node; in avl_find()
253 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); in avl_find()
260 return (AVL_NODE2DATA(node, off)); in avl_find()
287 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) in avl_rotation() argument
293 avl_node_t *parent = AVL_XPARENT(node); in avl_rotation()
294 avl_node_t *child = node->avl_child[left]; in avl_rotation()
299 int which_child = AVL_XCHILD(node); in avl_rotation()
343 node->avl_child[left] = cright; in avl_rotation()
345 AVL_SETPARENT(cright, node); in avl_rotation()
352 child->avl_child[right] = node; in avl_rotation()
353 AVL_SETBALANCE(node, -child_bal); in avl_rotation()
354 AVL_SETCHILD(node, right); in avl_rotation()
355 AVL_SETPARENT(node, child); in avl_rotation()
413 node->avl_child[left] = gright; in avl_rotation()
415 AVL_SETPARENT(gright, node); in avl_rotation()
438 gchild->avl_child[right] = node; in avl_rotation()
439 AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); in avl_rotation()
440 AVL_SETPARENT(node, gchild); in avl_rotation()
441 AVL_SETCHILD(node, right); in avl_rotation()
468 avl_node_t *node; in avl_insert() local
480 node = AVL_DATA2NODE(new_data, off); in avl_insert()
487 node->avl_child[0] = NULL; in avl_insert()
488 node->avl_child[1] = NULL; in avl_insert()
490 AVL_SETCHILD(node, which_child); in avl_insert()
491 AVL_SETBALANCE(node, 0); in avl_insert()
492 AVL_SETPARENT(node, parent); in avl_insert()
495 parent->avl_child[which_child] = node; in avl_insert()
498 tree->avl_root = node; in avl_insert()
507 node = parent; in avl_insert()
508 if (node == NULL) in avl_insert()
514 old_balance = AVL_XBALANCE(node); in avl_insert()
521 AVL_SETBALANCE(node, 0); in avl_insert()
532 AVL_SETBALANCE(node, new_balance); in avl_insert()
533 parent = AVL_XPARENT(node); in avl_insert()
534 which_child = AVL_XCHILD(node); in avl_insert()
540 (void) avl_rotation(tree, node, new_balance); in avl_insert()
562 avl_node_t *node; in avl_insert_here() local
577 node = AVL_DATA2NODE(here, tree->avl_offset); in avl_insert_here()
586 if (node->avl_child[child] != NULL) { in avl_insert_here()
587 node = node->avl_child[child]; in avl_insert_here()
589 while (node->avl_child[child] != NULL) { in avl_insert_here()
592 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
597 node = node->avl_child[child]; in avl_insert_here()
601 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
607 ASSERT(node->avl_child[child] == NULL); in avl_insert_here()
609 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); in avl_insert_here()
666 avl_node_t *node; in avl_remove() local
702 for (node = delete->avl_child[left]; in avl_remove()
703 node->avl_child[right] != NULL; in avl_remove()
704 node = node->avl_child[right]) in avl_remove()
711 tmp = *node; in avl_remove()
713 *node = *delete; in avl_remove()
714 if (node->avl_child[left] == node) in avl_remove()
715 node->avl_child[left] = &tmp; in avl_remove()
717 parent = AVL_XPARENT(node); in avl_remove()
719 parent->avl_child[AVL_XCHILD(node)] = node; in avl_remove()
721 tree->avl_root = node; in avl_remove()
722 AVL_SETPARENT(node->avl_child[left], node); in avl_remove()
723 AVL_SETPARENT(node->avl_child[right], node); in avl_remove()
747 node = delete->avl_child[0]; in avl_remove()
749 node = delete->avl_child[1]; in avl_remove()
754 if (node != NULL) { in avl_remove()
755 AVL_SETPARENT(node, parent); in avl_remove()
756 AVL_SETCHILD(node, which_child); in avl_remove()
759 tree->avl_root = node; in avl_remove()
762 parent->avl_child[which_child] = node; in avl_remove()
777 node = parent; in avl_remove()
778 old_balance = AVL_XBALANCE(node); in avl_remove()
780 parent = AVL_XPARENT(node); in avl_remove()
781 which_child = AVL_XCHILD(node); in avl_remove()
789 AVL_SETBALANCE(node, new_balance); in avl_remove()
801 AVL_SETBALANCE(node, new_balance); in avl_remove()
802 else if (!avl_rotation(tree, node, new_balance)) in avl_remove()
959 avl_node_t *node; in avl_destroy_nodes() local
979 node = AVL_DATA2NODE(first, off); in avl_destroy_nodes()
980 parent = AVL_XPARENT(node); in avl_destroy_nodes()
1009 node = parent; in avl_destroy_nodes()
1017 node = parent->avl_child[1]; in avl_destroy_nodes()
1018 while (node->avl_child[0] != NULL) { in avl_destroy_nodes()
1019 parent = node; in avl_destroy_nodes()
1020 node = node->avl_child[0]; in avl_destroy_nodes()
1028 if (node->avl_child[1] != NULL) { in avl_destroy_nodes()
1029 ASSERT(AVL_XBALANCE(node) == 1); in avl_destroy_nodes()
1030 parent = node; in avl_destroy_nodes()
1031 node = node->avl_child[1]; in avl_destroy_nodes()
1032 ASSERT(node->avl_child[0] == NULL && in avl_destroy_nodes()
1033 node->avl_child[1] == NULL); in avl_destroy_nodes()
1035 ASSERT(AVL_XBALANCE(node) <= 0); in avl_destroy_nodes()
1041 ASSERT(node == tree->avl_root); in avl_destroy_nodes()
1043 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); in avl_destroy_nodes()
1046 return (AVL_NODE2DATA(node, off)); in avl_destroy_nodes()