Lines Matching refs:node
139 avl_node_t *node = AVL_DATA2NODE(oldnode, off); in avl_walk() local
147 if (node == NULL) in avl_walk()
156 if (node->avl_child[left] != NULL) { in avl_walk()
157 for (node = node->avl_child[left]; in avl_walk()
158 node->avl_child[right] != NULL; in avl_walk()
159 node = node->avl_child[right]) in avl_walk()
166 was_child = AVL_XCHILD(node); in avl_walk()
167 node = AVL_XPARENT(node); in avl_walk()
168 if (node == NULL) in avl_walk()
175 return (AVL_NODE2DATA(node, off)); in avl_walk()
185 avl_node_t *node; in avl_first() local
189 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) in avl_first()
190 prev = node; in avl_first()
204 avl_node_t *node; in avl_last() local
208 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) in avl_last()
209 prev = node; in avl_last()
229 avl_node_t *node = AVL_INDEX2NODE(where); in avl_nearest() local
233 if (node == NULL) { in avl_nearest()
237 data = AVL_NODE2DATA(node, off); in avl_nearest()
257 avl_node_t *node; in avl_find() local
263 for (node = tree->avl_root; node != NULL; in avl_find()
264 node = node->avl_child[child]) { in avl_find()
266 prev = node; in avl_find()
268 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); in avl_find()
275 return (AVL_NODE2DATA(node, off)); in avl_find()
303 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) in avl_rotation() argument
309 avl_node_t *parent = AVL_XPARENT(node); in avl_rotation()
310 avl_node_t *child = node->avl_child[left]; in avl_rotation()
315 int which_child = AVL_XCHILD(node); in avl_rotation()
359 node->avl_child[left] = cright; in avl_rotation()
361 AVL_SETPARENT(cright, node); in avl_rotation()
368 child->avl_child[right] = node; in avl_rotation()
369 AVL_SETBALANCE(node, -child_bal); in avl_rotation()
370 AVL_SETCHILD(node, right); in avl_rotation()
371 AVL_SETPARENT(node, child); in avl_rotation()
429 node->avl_child[left] = gright; in avl_rotation()
431 AVL_SETPARENT(gright, node); in avl_rotation()
454 gchild->avl_child[right] = node; in avl_rotation()
455 AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); in avl_rotation()
456 AVL_SETPARENT(node, gchild); in avl_rotation()
457 AVL_SETCHILD(node, right); in avl_rotation()
484 avl_node_t *node; in avl_insert() local
496 node = AVL_DATA2NODE(new_data, off); in avl_insert()
503 node->avl_child[0] = NULL; in avl_insert()
504 node->avl_child[1] = NULL; in avl_insert()
506 AVL_SETCHILD(node, which_child); in avl_insert()
507 AVL_SETBALANCE(node, 0); in avl_insert()
508 AVL_SETPARENT(node, parent); in avl_insert()
511 parent->avl_child[which_child] = node; in avl_insert()
514 tree->avl_root = node; in avl_insert()
523 node = parent; in avl_insert()
524 if (node == NULL) in avl_insert()
530 old_balance = AVL_XBALANCE(node); in avl_insert()
537 AVL_SETBALANCE(node, 0); in avl_insert()
548 AVL_SETBALANCE(node, new_balance); in avl_insert()
549 parent = AVL_XPARENT(node); in avl_insert()
550 which_child = AVL_XCHILD(node); in avl_insert()
556 (void) avl_rotation(tree, node, new_balance); in avl_insert()
578 avl_node_t *node; in avl_insert_here() local
593 node = AVL_DATA2NODE(here, tree->avl_offset); in avl_insert_here()
602 if (node->avl_child[child] != NULL) { in avl_insert_here()
603 node = node->avl_child[child]; in avl_insert_here()
605 while (node->avl_child[child] != NULL) { in avl_insert_here()
608 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
613 node = node->avl_child[child]; in avl_insert_here()
617 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
623 ASSERT(node->avl_child[child] == NULL); in avl_insert_here()
625 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); in avl_insert_here()
682 avl_node_t *node; in avl_remove() local
718 for (node = delete->avl_child[left]; in avl_remove()
719 node->avl_child[right] != NULL; in avl_remove()
720 node = node->avl_child[right]) in avl_remove()
727 tmp = *node; in avl_remove()
729 *node = *delete; in avl_remove()
730 if (node->avl_child[left] == node) in avl_remove()
731 node->avl_child[left] = &tmp; in avl_remove()
733 parent = AVL_XPARENT(node); in avl_remove()
735 parent->avl_child[AVL_XCHILD(node)] = node; in avl_remove()
737 tree->avl_root = node; in avl_remove()
738 AVL_SETPARENT(node->avl_child[left], node); in avl_remove()
739 AVL_SETPARENT(node->avl_child[right], node); in avl_remove()
763 node = delete->avl_child[0]; in avl_remove()
765 node = delete->avl_child[1]; in avl_remove()
770 if (node != NULL) { in avl_remove()
771 AVL_SETPARENT(node, parent); in avl_remove()
772 AVL_SETCHILD(node, which_child); in avl_remove()
775 tree->avl_root = node; in avl_remove()
778 parent->avl_child[which_child] = node; in avl_remove()
793 node = parent; in avl_remove()
794 old_balance = AVL_XBALANCE(node); in avl_remove()
796 parent = AVL_XPARENT(node); in avl_remove()
797 which_child = AVL_XCHILD(node); in avl_remove()
805 AVL_SETBALANCE(node, new_balance); in avl_remove()
817 AVL_SETBALANCE(node, new_balance); in avl_remove()
818 else if (!avl_rotation(tree, node, new_balance)) in avl_remove()
975 avl_node_t *node; in avl_destroy_nodes() local
995 node = AVL_DATA2NODE(first, off); in avl_destroy_nodes()
996 parent = AVL_XPARENT(node); in avl_destroy_nodes()
1025 node = parent; in avl_destroy_nodes()
1033 node = parent->avl_child[1]; in avl_destroy_nodes()
1034 while (node->avl_child[0] != NULL) { in avl_destroy_nodes()
1035 parent = node; in avl_destroy_nodes()
1036 node = node->avl_child[0]; in avl_destroy_nodes()
1044 if (node->avl_child[1] != NULL) { in avl_destroy_nodes()
1045 ASSERT(AVL_XBALANCE(node) == 1); in avl_destroy_nodes()
1046 parent = node; in avl_destroy_nodes()
1047 node = node->avl_child[1]; in avl_destroy_nodes()
1048 ASSERT(node->avl_child[0] == NULL && in avl_destroy_nodes()
1049 node->avl_child[1] == NULL); in avl_destroy_nodes()
1051 ASSERT(AVL_XBALANCE(node) <= 0); in avl_destroy_nodes()
1057 ASSERT(node == tree->avl_root); in avl_destroy_nodes()
1059 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); in avl_destroy_nodes()
1062 return (AVL_NODE2DATA(node, off)); in avl_destroy_nodes()