Lines Matching +full:parent +full:- +full:child
9 * or https://opensource.org/licenses/CDDL-1.0.
32 * AVL - generic AVL tree implementation for kernel use
46 * rotations, which bring unbalanced subtrees back into the semi-balanced state.
50 * - The AVL specific data structures are physically embedded as fields
55 * - Since the AVL data is always embedded in other structures, there is
61 * - The implementation uses iteration instead of explicit recursion,
64 * there is an explicit "parent" link in the avl_node_t.
66 * - The left/right children pointers of a node are in an array.
76 * int left_heavy; // -1 when left subtree is taller at some node,
80 * int right_heavy;// will be the opposite of left_heavy (-1 or 1)
82 * int direction; // 0 for "<" (ie. left child); 1 for ">" (right)
88 * - The avl_index_t is an opaque "cookie" used to find nodes at or
94 * Note - in addition to userland (e.g. libavl and libutil) and the kernel
119 * - If there is a left child, go to it, then to it's rightmost descendant.
121 * - otherwise we return through parent nodes until we've come from a right
122 * child.
125 * NULL - if at the end of the nodes
131 size_t off = tree->avl_offset; in avl_walk()
133 int right = 1 - left; in avl_walk()
146 * If this node has a left child, go down one left, then all in avl_walk()
149 if (node->avl_child[left] != NULL) { in avl_walk()
150 for (node = node->avl_child[left]; in avl_walk()
151 node->avl_child[right] != NULL; in avl_walk()
152 node = node->avl_child[right]) in avl_walk()
173 * (leftmost child from root of tree)
180 size_t off = tree->avl_offset; in avl_first()
182 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) in avl_first()
192 * (rightmost child from root of tree)
199 size_t off = tree->avl_offset; in avl_last()
201 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) in avl_last()
212 * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
221 int child = AVL_INDEX2CHILD(where); in avl_nearest() local
224 size_t off = tree->avl_offset; in avl_nearest()
227 ASSERT(tree->avl_root == NULL); in avl_nearest()
231 if (child != direction) in avl_nearest()
252 int child = 0; in avl_find() local
254 size_t off = tree->avl_offset; in avl_find()
256 for (node = tree->avl_root; node != NULL; in avl_find()
257 node = node->avl_child[child]) { in avl_find()
261 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); in avl_find()
262 ASSERT(-1 <= diff && diff <= 1); in avl_find()
270 child = (diff > 0); in avl_find()
274 *where = AVL_MKINDEX(prev, child); in avl_find()
292 * -2 or +2.
297 int left = !(balance < 0); /* when balance = -2, left will be 0 */ in avl_rotation()
298 int right = 1 - left; in avl_rotation()
300 int right_heavy = -left_heavy; in avl_rotation()
301 avl_node_t *parent = AVL_XPARENT(node); in avl_rotation() local
302 avl_node_t *child = node->avl_child[left]; in avl_rotation() local
308 int child_bal = AVL_XBALANCE(child); in avl_rotation()
311 * case 1 : node is overly left heavy, the left child is balanced or in avl_rotation()
314 * (node bal:-2) in avl_rotation()
317 * (child bal:0 or -1) in avl_rotation()
324 * (child bal:1 or 0) in avl_rotation()
327 * (node bal:-1 or 0) in avl_rotation()
332 * we detect this situation by noting that child's balance is not in avl_rotation()
340 * If child used to be left heavy (now balanced) we reduced in avl_rotation()
341 * the height of this sub-tree -- used in "return...;" below in avl_rotation()
346 * move "cright" to be node's left child in avl_rotation()
348 cright = child->avl_child[right]; in avl_rotation()
349 node->avl_child[left] = cright; in avl_rotation()
356 * move node to be child's right child in avl_rotation()
358 child->avl_child[right] = node; in avl_rotation()
359 AVL_SETBALANCE(node, -child_bal); in avl_rotation()
361 AVL_SETPARENT(node, child); in avl_rotation()
366 AVL_SETBALANCE(child, child_bal); in avl_rotation()
367 AVL_SETCHILD(child, which_child); in avl_rotation()
368 AVL_SETPARENT(child, parent); in avl_rotation()
369 if (parent != NULL) in avl_rotation()
370 parent->avl_child[which_child] = child; in avl_rotation()
372 tree->avl_root = child; in avl_rotation()
378 * case 2 : When node is left heavy, but child is right heavy we use in avl_rotation()
381 * (node b:-2) in avl_rotation()
385 * (child b:+1) in avl_rotation()
399 * (child b:?) (node b:?) in avl_rotation()
405 * if gchild was right_heavy, then child is now left heavy in avl_rotation()
408 gchild = child->avl_child[right]; in avl_rotation()
409 gleft = gchild->avl_child[left]; in avl_rotation()
410 gright = gchild->avl_child[right]; in avl_rotation()
413 * move gright to left child of node and in avl_rotation()
415 * move gleft to right child of node in avl_rotation()
417 node->avl_child[left] = gright; in avl_rotation()
423 child->avl_child[right] = gleft; in avl_rotation()
425 AVL_SETPARENT(gleft, child); in avl_rotation()
430 * move child to left child of gchild and in avl_rotation()
432 * move node to right child of gchild and in avl_rotation()
434 * fixup parent of all this to point to gchild in avl_rotation()
437 gchild->avl_child[left] = child; in avl_rotation()
438 AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0)); in avl_rotation()
439 AVL_SETPARENT(child, gchild); in avl_rotation()
440 AVL_SETCHILD(child, left); in avl_rotation()
442 gchild->avl_child[right] = node; in avl_rotation()
448 AVL_SETPARENT(gchild, parent); in avl_rotation()
450 if (parent != NULL) in avl_rotation()
451 parent->avl_child[which_child] = gchild; in avl_rotation()
453 tree->avl_root = gchild; in avl_rotation()
464 * which will be the parent of the new node.
473 avl_node_t *parent = AVL_INDEX2NODE(where); in avl_insert() local
477 size_t off = tree->avl_offset; in avl_insert()
488 ++tree->avl_numnodes; in avl_insert()
490 node->avl_child[0] = NULL; in avl_insert()
491 node->avl_child[1] = NULL; in avl_insert()
495 AVL_SETPARENT(node, parent); in avl_insert()
496 if (parent != NULL) { in avl_insert()
497 ASSERT(parent->avl_child[which_child] == NULL); in avl_insert()
498 parent->avl_child[which_child] = node; in avl_insert()
500 ASSERT(tree->avl_root == NULL); in avl_insert()
501 tree->avl_root = node; in avl_insert()
510 node = parent; in avl_insert()
518 new_balance = old_balance + (which_child ? 1 : -1); in avl_insert()
530 * from -1 to -2 balance, do a rotation. in avl_insert()
536 parent = AVL_XPARENT(node); in avl_insert()
551 * if the given child of the node is already present we move to either
566 int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */ in avl_insert_here() local
577 * If corresponding child of node is not NULL, go to the neighboring in avl_insert_here()
580 node = AVL_DATA2NODE(here, tree->avl_offset); in avl_insert_here()
583 diff = tree->avl_compar(new_data, here); in avl_insert_here()
584 ASSERT(-1 <= diff && diff <= 1); in avl_insert_here()
586 ASSERT(diff > 0 ? child == 1 : child == 0); in avl_insert_here()
589 if (node->avl_child[child] != NULL) { in avl_insert_here()
590 node = node->avl_child[child]; in avl_insert_here()
591 child = 1 - child; in avl_insert_here()
592 while (node->avl_child[child] != NULL) { in avl_insert_here()
594 diff = tree->avl_compar(new_data, in avl_insert_here()
595 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
596 ASSERT(-1 <= diff && diff <= 1); in avl_insert_here()
598 ASSERT(diff > 0 ? child == 1 : child == 0); in avl_insert_here()
600 node = node->avl_child[child]; in avl_insert_here()
603 diff = tree->avl_compar(new_data, in avl_insert_here()
604 AVL_NODE2DATA(node, tree->avl_offset)); in avl_insert_here()
605 ASSERT(-1 <= diff && diff <= 1); in avl_insert_here()
607 ASSERT(diff > 0 ? child == 1 : child == 0); in avl_insert_here()
610 ASSERT(node->avl_child[child] == NULL); in avl_insert_here()
612 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); in avl_insert_here()
617 * be added to the tree with a VERIFY which is enabled for non-DEBUG builds.
656 avl_node_t *parent; in avl_remove() local
664 size_t off = tree->avl_offset; in avl_remove()
669 * Deletion is easiest with a node that has at most 1 child. in avl_remove()
671 * neighbor node. That node will have at most 1 child. Note this in avl_remove()
678 if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { in avl_remove()
685 right = 1 - left; in avl_remove()
691 for (node = delete->avl_child[left]; in avl_remove()
692 node->avl_child[right] != NULL; in avl_remove()
693 node = node->avl_child[right]) in avl_remove()
703 if (node->avl_child[left] == node) in avl_remove()
704 node->avl_child[left] = &tmp; in avl_remove()
706 parent = AVL_XPARENT(node); in avl_remove()
707 if (parent != NULL) in avl_remove()
708 parent->avl_child[AVL_XCHILD(node)] = node; in avl_remove()
710 tree->avl_root = node; in avl_remove()
711 AVL_SETPARENT(node->avl_child[left], node); in avl_remove()
712 AVL_SETPARENT(node->avl_child[right], node); in avl_remove()
716 * It always has a parent and at most 1 child. in avl_remove()
719 parent = AVL_XPARENT(delete); in avl_remove()
720 parent->avl_child[AVL_XCHILD(delete)] = delete; in avl_remove()
721 which_child = (delete->avl_child[1] != 0); in avl_remove()
722 if (delete->avl_child[which_child] != NULL) in avl_remove()
723 AVL_SETPARENT(delete->avl_child[which_child], delete); in avl_remove()
731 ASSERT(tree->avl_numnodes > 0); in avl_remove()
732 --tree->avl_numnodes; in avl_remove()
733 parent = AVL_XPARENT(delete); in avl_remove()
735 if (delete->avl_child[0] != NULL) in avl_remove()
736 node = delete->avl_child[0]; in avl_remove()
738 node = delete->avl_child[1]; in avl_remove()
741 * Connect parent directly to node (leaving out delete). in avl_remove()
744 AVL_SETPARENT(node, parent); in avl_remove()
747 if (parent == NULL) { in avl_remove()
748 tree->avl_root = node; in avl_remove()
751 parent->avl_child[which_child] = node; in avl_remove()
755 * Since the subtree is now shorter, begin adjusting parent balances in avl_remove()
763 * Capture the parent and which_child values for the next in avl_remove()
766 node = parent; in avl_remove()
768 new_balance = old_balance - (which_child ? 1 : -1); in avl_remove()
769 parent = AVL_XPARENT(node); in avl_remove()
787 * of the sub-tree we have finished adjusting. in avl_remove()
793 } while (parent != NULL); in avl_remove()
806 (t->avl_compar(obj, neighbor) <= 0)); in avl_update_lt()
809 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { in avl_update_lt()
823 (t->avl_compar(obj, neighbor) >= 0)); in avl_update_gt()
826 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { in avl_update_gt()
840 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { in avl_update()
846 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { in avl_update()
860 ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar); in avl_swap()
861 ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset); in avl_swap()
863 temp_node = tree1->avl_root; in avl_swap()
864 temp_numnodes = tree1->avl_numnodes; in avl_swap()
865 tree1->avl_root = tree2->avl_root; in avl_swap()
866 tree1->avl_numnodes = tree2->avl_numnodes; in avl_swap()
867 tree2->avl_root = temp_node; in avl_swap()
868 tree2->avl_numnodes = temp_numnodes; in avl_swap()
886 tree->avl_compar = compar; in avl_create()
887 tree->avl_root = NULL; in avl_create()
888 tree->avl_numnodes = 0; in avl_create()
889 tree->avl_offset = offset; in avl_create()
899 ASSERT(tree->avl_numnodes == 0); in avl_destroy()
900 ASSERT(tree->avl_root == NULL); in avl_destroy()
911 return (tree->avl_numnodes); in avl_numnodes()
918 return (tree->avl_numnodes == 0); in avl_is_empty()
924 * Post-order tree walk used to visit all tree nodes and destroy the tree
937 * The cookie is really an avl_node_t to the current node's parent and
938 * an indication of which child you looked at last.
946 avl_node_t *parent; in avl_destroy_nodes() local
947 int child; in avl_destroy_nodes() local
949 size_t off = tree->avl_offset; in avl_destroy_nodes()
966 parent = AVL_XPARENT(node); in avl_destroy_nodes()
971 * If there is no parent to return to we are done. in avl_destroy_nodes()
973 parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT); in avl_destroy_nodes()
974 if (parent == NULL) { in avl_destroy_nodes()
975 if (tree->avl_root != NULL) { in avl_destroy_nodes()
976 ASSERT(tree->avl_numnodes == 1); in avl_destroy_nodes()
977 tree->avl_root = NULL; in avl_destroy_nodes()
978 tree->avl_numnodes = 0; in avl_destroy_nodes()
984 * Remove the child pointer we just visited from the parent and tree. in avl_destroy_nodes()
986 child = (uintptr_t)(*cookie) & CHILDBIT; in avl_destroy_nodes()
987 parent->avl_child[child] = NULL; in avl_destroy_nodes()
988 ASSERT(tree->avl_numnodes > 1); in avl_destroy_nodes()
989 --tree->avl_numnodes; in avl_destroy_nodes()
992 * If we just removed a right child or there isn't one, go up to parent. in avl_destroy_nodes()
994 if (child == 1 || parent->avl_child[1] == NULL) { in avl_destroy_nodes()
995 node = parent; in avl_destroy_nodes()
996 parent = AVL_XPARENT(parent); in avl_destroy_nodes()
1001 * Do parent's right child, then leftmost descendent. in avl_destroy_nodes()
1003 node = parent->avl_child[1]; in avl_destroy_nodes()
1004 while (node->avl_child[0] != NULL) { in avl_destroy_nodes()
1005 parent = node; in avl_destroy_nodes()
1006 node = node->avl_child[0]; in avl_destroy_nodes()
1010 * If here, we moved to a left child. It may have one in avl_destroy_nodes()
1011 * child on the right (when balance == +1). in avl_destroy_nodes()
1014 if (node->avl_child[1] != NULL) { in avl_destroy_nodes()
1016 parent = node; in avl_destroy_nodes()
1017 node = node->avl_child[1]; in avl_destroy_nodes()
1018 ASSERT(node->avl_child[0] == NULL && in avl_destroy_nodes()
1019 node->avl_child[1] == NULL); in avl_destroy_nodes()
1025 if (parent == NULL) { in avl_destroy_nodes()
1027 ASSERT(node == tree->avl_root); in avl_destroy_nodes()
1029 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); in avl_destroy_nodes()