64  *	  there is an explicit "parent" link in the avl_node_t.
113  * - otherwise we return through parent nodes until we've come from a right
293 	avl_node_t *parent = AVL_XPARENT(node);  in avl_rotation()  local
362 		AVL_SETPARENT(child, parent);  in avl_rotation()
363 		if (parent != NULL)  in avl_rotation()
364 			parent->avl_child[which_child] = child;  in avl_rotation()
430 	 * fixup parent of all this to point to gchild  in avl_rotation()
444 	AVL_SETPARENT(gchild, parent);  in avl_rotation()
446 	if (parent != NULL)  in avl_rotation()
447 		parent->avl_child[which_child] = gchild;  in avl_rotation()
460  * which will be the parent of the new node.
469 	avl_node_t *parent = AVL_INDEX2NODE(where);  in avl_insert()  local
492 	AVL_SETPARENT(node, parent);  in avl_insert()
493 	if (parent != NULL) {  in avl_insert()
494 		ASSERT(parent->avl_child[which_child] == NULL);  in avl_insert()
495 		parent->avl_child[which_child] = node;  in avl_insert()
507 		node = parent;  in avl_insert()
533 		parent = AVL_XPARENT(node);  in avl_insert()
665 	avl_node_t *parent;  in avl_remove()  local
717 		parent = AVL_XPARENT(node);  in avl_remove()
718 		if (parent != NULL)  in avl_remove()
719 			parent->avl_child[AVL_XCHILD(node)] = node;  in avl_remove()
727 		 * It always has a parent and at most 1 child.  in avl_remove()
730 		parent = AVL_XPARENT(delete);  in avl_remove()
731 		parent->avl_child[AVL_XCHILD(delete)] = delete;  in avl_remove()
744 	parent = AVL_XPARENT(delete);  in avl_remove()
752 	 * Connect parent directly to node (leaving out delete).  in avl_remove()
755 		AVL_SETPARENT(node, parent);  in avl_remove()
758 	if (parent == NULL) {  in avl_remove()
762 	parent->avl_child[which_child] = node;  in avl_remove()
766 	 * Since the subtree is now shorter, begin adjusting parent balances  in avl_remove()
774 		 * Capture the parent and which_child values for the next  in avl_remove()
777 		node = parent;  in avl_remove()
780 		parent = AVL_XPARENT(node);  in avl_remove()
804 	} while (parent != NULL);  in avl_remove()
951  * The cookie is really an avl_node_t to the current node's parent and
960 	avl_node_t	*parent;  in avl_destroy_nodes()  local
980 		parent = AVL_XPARENT(node);  in avl_destroy_nodes()
985 	 * If there is no parent to return to we are done.  in avl_destroy_nodes()
987 	parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT);  in avl_destroy_nodes()
988 	if (parent == NULL) {  in avl_destroy_nodes()
998 	 * Remove the child pointer we just visited from the parent and tree.  in avl_destroy_nodes()
1001 	parent->avl_child[child] = NULL;  in avl_destroy_nodes()
1006 	 * If we just did a right child or there isn't one, go up to parent.  in avl_destroy_nodes()
1008 	if (child == 1 || parent->avl_child[1] == NULL) {  in avl_destroy_nodes()
1009 		node = parent;  in avl_destroy_nodes()
1010 		parent = AVL_XPARENT(parent);  in avl_destroy_nodes()
1015 	 * Do parent's right child, then leftmost descendent.  in avl_destroy_nodes()
1017 	node = parent->avl_child[1];  in avl_destroy_nodes()
1019 		parent = node;  in avl_destroy_nodes()
1030 		parent = node;  in avl_destroy_nodes()
1039 	if (parent == NULL) {  in avl_destroy_nodes()
1043 		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));  in avl_destroy_nodes()