Lines Matching refs:node
138 avl_node_t *node = AVL_DATA2NODE(oldnode, off); in avl_walk() local
146 if (node == NULL) in avl_walk()
155 if (node->avl_child[left] != NULL) { in avl_walk()
156 for (node = node->avl_child[left]; in avl_walk()
157 node->avl_child[right] != NULL; in avl_walk()
158 node = node->avl_child[right]) in avl_walk()
165 was_child = AVL_XCHILD(node); in avl_walk()
166 node = AVL_XPARENT(node); in avl_walk()
167 if (node == NULL) in avl_walk()
174 return (AVL_NODE2DATA(node, off)); in avl_walk()
184 avl_node_t *node; in avl_first() local
188 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) in avl_first()
189 prev = node; in avl_first()
203 avl_node_t *node; in avl_last() local
207 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) in avl_last()
208 prev = node; in avl_last()
228 avl_node_t *node = AVL_INDEX2NODE(where); in avl_nearest() local
232 if (node == NULL) { in avl_nearest()
236 data = AVL_NODE2DATA(node, off); in avl_nearest()
256 avl_node_t *node; in avl_find() local
262 for (node = tree->avl_root; node != NULL; in avl_find()
263 node = node->avl_child[child]) { in avl_find()
265 prev = node; in avl_find()
267 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); in avl_find()
274 return (AVL_NODE2DATA(node, off)); in avl_find()
302 avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) in avl_rotation() argument
308 avl_node_t *parent = AVL_XPARENT(node); in avl_rotation()
309 avl_node_t *child = node->avl_child[left]; in avl_rotation()
314 int which_child = AVL_XCHILD(node); in avl_rotation()
358 node->avl_child[left] = cright; in avl_rotation()
360 AVL_SETPARENT(cright, node); in avl_rotation()
367 child->avl_child[right] = node; in avl_rotation()
368 AVL_SETBALANCE(node, -child_bal); in avl_rotation()
369 AVL_SETCHILD(node, right); in avl_rotation()
370 AVL_SETPARENT(node, child); in avl_rotation()
428 node->avl_child[left] = gright; in avl_rotation()
430 AVL_SETPARENT(gright, node); in avl_rotation()
453 gchild->avl_child[right] = node; in avl_rotation()
454 AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); in avl_rotation()
455 AVL_SETPARENT(node, gchild); in avl_rotation()
456 AVL_SETCHILD(node, right); in avl_rotation()
483 avl_node_t *node; in avl_insert() local
495 node = AVL_DATA2NODE(new_data, off); in avl_insert()
502 node->avl_child[0] = NULL; in avl_insert()
503 node->avl_child[1] = NULL; in avl_insert()
505 AVL_SETCHILD(node, which_child); in avl_insert()
506 AVL_SETBALANCE(node, 0); in avl_insert()
507 AVL_SETPARENT(node, parent); in avl_insert()
510 parent->avl_child[which_child] = node; in avl_insert()
513 tree->avl_root = node; in avl_insert()
522 node = parent; in avl_insert()
523 if (node == NULL) in avl_insert()
529 old_balance = AVL_XBALANCE(node); in avl_insert()
536 AVL_SETBALANCE(node, 0); in avl_insert()
547 AVL_SETBALANCE(node, new_balance); in avl_insert()
548 parent = AVL_XPARENT(node); in avl_insert()
549 which_child = AVL_XCHILD(node); in avl_insert()
555 (void) avl_rotation(tree, node, new_balance); in avl_insert()
577 avl_node_t *node; in avl_insert_here() local
592 node = AVL_DATA2NODE(here, tree->avl_offset); in avl_insert_here()
601 if (node->avl_child[child] != NULL) { in avl_insert_here()
602 node = node->avl_child[child]; in avl_insert_here()
604 while (node->avl_child[child] != NULL) { in avl_insert_here()
607 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
612 node = node->avl_child[child]; in avl_insert_here()
616 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
622 ASSERT(node->avl_child[child] == NULL); in avl_insert_here()
624 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); in avl_insert_here()
678 avl_node_t *node; in avl_remove() local
714 for (node = delete->avl_child[left]; in avl_remove()
715 node->avl_child[right] != NULL; in avl_remove()
716 node = node->avl_child[right]) in avl_remove()
723 tmp = *node; in avl_remove()
725 *node = *delete; in avl_remove()
726 if (node->avl_child[left] == node) in avl_remove()
727 node->avl_child[left] = &tmp; in avl_remove()
729 parent = AVL_XPARENT(node); in avl_remove()
731 parent->avl_child[AVL_XCHILD(node)] = node; in avl_remove()
733 tree->avl_root = node; in avl_remove()
734 AVL_SETPARENT(node->avl_child[left], node); in avl_remove()
735 AVL_SETPARENT(node->avl_child[right], node); in avl_remove()
759 node = delete->avl_child[0]; in avl_remove()
761 node = delete->avl_child[1]; in avl_remove()
766 if (node != NULL) { in avl_remove()
767 AVL_SETPARENT(node, parent); in avl_remove()
768 AVL_SETCHILD(node, which_child); in avl_remove()
771 tree->avl_root = node; in avl_remove()
774 parent->avl_child[which_child] = node; in avl_remove()
789 node = parent; in avl_remove()
790 old_balance = AVL_XBALANCE(node); in avl_remove()
792 parent = AVL_XPARENT(node); in avl_remove()
793 which_child = AVL_XCHILD(node); in avl_remove()
801 AVL_SETBALANCE(node, new_balance); in avl_remove()
813 AVL_SETBALANCE(node, new_balance); in avl_remove()
814 else if (!avl_rotation(tree, node, new_balance)) in avl_remove()
971 avl_node_t *node; in avl_destroy_nodes() local
991 node = AVL_DATA2NODE(first, off); in avl_destroy_nodes()
992 parent = AVL_XPARENT(node); in avl_destroy_nodes()
1021 node = parent; in avl_destroy_nodes()
1029 node = parent->avl_child[1]; in avl_destroy_nodes()
1030 while (node->avl_child[0] != NULL) { in avl_destroy_nodes()
1031 parent = node; in avl_destroy_nodes()
1032 node = node->avl_child[0]; in avl_destroy_nodes()
1040 if (node->avl_child[1] != NULL) { in avl_destroy_nodes()
1041 ASSERT(AVL_XBALANCE(node) == 1); in avl_destroy_nodes()
1042 parent = node; in avl_destroy_nodes()
1043 node = node->avl_child[1]; in avl_destroy_nodes()
1044 ASSERT(node->avl_child[0] == NULL && in avl_destroy_nodes()
1045 node->avl_child[1] == NULL); in avl_destroy_nodes()
1047 ASSERT(AVL_XBALANCE(node) <= 0); in avl_destroy_nodes()
1053 ASSERT(node == tree->avl_root); in avl_destroy_nodes()
1055 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); in avl_destroy_nodes()
1058 return (AVL_NODE2DATA(node, off)); in avl_destroy_nodes()