common/avl/avl.c

81  *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
107  * Small arrays to translate between balance (or diff) values and child indices.
125  * - If there is a left child, go to it, then to it's rightmost descendant.
128  *   child.
152 	 * If this node has a left child, go down one left, then all
179  * (leftmost child from root of tree)
198  * (rightmost child from root of tree)
218  * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
227 	int child = AVL_INDEX2CHILD(where);
237 	if (child != direction)
258 	int child = 0;
263 	    node = node->avl_child[child]) {
276 		child = avl_balance2child[1 + diff];
281 		*where = AVL_MKINDEX(prev, child);
309 	avl_node_t *child = node->avl_child[left];
315 	int child_bal = AVL_XBALANCE(child);
319 	 * case 1 : node is overly left heavy, the left child is balanced or
325 	 *              (child bal:0 or -1)
332 	 *              (child bal:1 or 0)
340 	 * we detect this situation by noting that child's balance is not
349 		 * If child used to be left heavy (now balanced) we reduced
355 		 * move "cright" to be node's left child
357 		cright = child->avl_child[right];
365 		 * move node to be child's right child
367 		child->avl_child[right] = node;
370 		AVL_SETPARENT(node, child);
375 		AVL_SETBALANCE(child, child_bal);
376 		AVL_SETCHILD(child, which_child);
377 		AVL_SETPARENT(child, parent);
379 			parent->avl_child[which_child] = child;
381 			tree->avl_root = child;
388 	 * case 2 : When node is left heavy, but child is right heavy we use
395 	 *             (child b:+1)
409 	 *        (child b:?)   (node b:?)
415 	 *	 if gchild was right_heavy, then child is now left heavy
419 	gchild = child->avl_child[right];
424 	 * move gright to left child of node and
426 	 * move gleft to right child of node
434 	child->avl_child[right] = gleft;
436 		AVL_SETPARENT(gleft, child);
441 	 * move child to left child of gchild and
443 	 * move node to right child of gchild and
448 	gchild->avl_child[left] = child;
449 	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));
450 	AVL_SETPARENT(child, gchild);
451 	AVL_SETCHILD(child, left);
563  * if the given child of the node is already present we move to either
578 	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
589 	 * If corresponding child of node is not NULL, go to the neighboring
598 	ASSERT(diff > 0 ? child == 1 : child == 0);
601 	if (node->avl_child[child] != NULL) {
602 		node = node->avl_child[child];
603 		child = 1 - child;
604 		while (node->avl_child[child] != NULL) {
610 			ASSERT(diff > 0 ? child == 1 : child == 0);
612 			node = node->avl_child[child];
619 		ASSERT(diff > 0 ? child == 1 : child == 0);
622 	ASSERT(node->avl_child[child] == NULL);
624 	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
692 	 * Deletion is easiest with a node that has at most 1 child.
694 	 * neighbor node. That node will have at most 1 child. Note this
739 		 * It always has a parent and at most 1 child.
964  * an indication of which child you looked at last.
973 	int		child;
1010 	 * Remove the child pointer we just visited from the parent and tree.
1012 	child = (uintptr_t)(*cookie) & CHILDBIT;
1013 	parent->avl_child[child] = NULL;
1018 	 * If we just did a right child or there isn't one, go up to parent.
1020 	if (child == 1 || parent->avl_child[1] == NULL) {
1027 	 * Do parent's right child, then leftmost descendent.
1036 	 * If here, we moved to a left child. It may have one
1037 	 * child on the right (when balance == +1).