Lines Matching refs:child
82 * int direction; // 0 for "<" (ie. left child); 1 for ">" (right)
108 * Small arrays to translate between balance (or diff) values and child indices.
126 * - If there is a left child, go to it, then to it's rightmost descendant.
129 * child.
153 * If this node has a left child, go down one left, then all
180 * (leftmost child from root of tree)
199 * (rightmost child from root of tree)
219 * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
228 int child = AVL_INDEX2CHILD(where);
238 if (child != direction)
259 int child = 0;
264 node = node->avl_child[child]) {
277 child = avl_balance2child[1 + diff];
282 *where = AVL_MKINDEX(prev, child);
310 avl_node_t *child = node->avl_child[left];
316 int child_bal = AVL_XBALANCE(child);
320 * case 1 : node is overly left heavy, the left child is balanced or
326 * (child bal:0 or -1)
333 * (child bal:1 or 0)
341 * we detect this situation by noting that child's balance is not
350 * If child used to be left heavy (now balanced) we reduced
356 * move "cright" to be node's left child
358 cright = child->avl_child[right];
366 * move node to be child's right child
368 child->avl_child[right] = node;
371 AVL_SETPARENT(node, child);
376 AVL_SETBALANCE(child, child_bal);
377 AVL_SETCHILD(child, which_child);
378 AVL_SETPARENT(child, parent);
380 parent->avl_child[which_child] = child;
382 tree->avl_root = child;
389 * case 2 : When node is left heavy, but child is right heavy we use
396 * (child b:+1)
410 * (child b:?) (node b:?)
416 * if gchild was right_heavy, then child is now left heavy
420 gchild = child->avl_child[right];
425 * move gright to left child of node and
427 * move gleft to right child of node
435 child->avl_child[right] = gleft;
437 AVL_SETPARENT(gleft, child);
442 * move child to left child of gchild and
444 * move node to right child of gchild and
449 gchild->avl_child[left] = child;
450 AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));
451 AVL_SETPARENT(child, gchild);
452 AVL_SETCHILD(child, left);
564 * if the given child of the node is already present we move to either
579 int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
590 * If corresponding child of node is not NULL, go to the neighboring
599 ASSERT(diff > 0 ? child == 1 : child == 0);
602 if (node->avl_child[child] != NULL) {
603 node = node->avl_child[child];
604 child = 1 - child;
605 while (node->avl_child[child] != NULL) {
611 ASSERT(diff > 0 ? child == 1 : child == 0);
613 node = node->avl_child[child];
620 ASSERT(diff > 0 ? child == 1 : child == 0);
623 ASSERT(node->avl_child[child] == NULL);
625 avl_insert(tree, new_data, AVL_MKINDEX(node, child));
696 * Deletion is easiest with a node that has at most 1 child.
698 * neighbor node. That node will have at most 1 child. Note this
743 * It always has a parent and at most 1 child.
968 * an indication of which child you looked at last.
977 int child;
1014 * Remove the child pointer we just visited from the parent and tree.
1016 child = (uintptr_t)(*cookie) & CHILDBIT;
1017 parent->avl_child[child] = NULL;
1022 * If we just did a right child or there isn't one, go up to parent.
1024 if (child == 1 || parent->avl_child[1] == NULL) {
1031 * Do parent's right child, then leftmost descendent.
1040 * If here, we moved to a left child. It may have one
1041 * child on the right (when balance == +1).