Lines Matching full:parent
50 * program which uses dict to define, for instance, a macro called ``parent''.
60 #define parent dict_parent macro
96 lowleft->parent = upper; in rotate_left()
98 lower->parent = upparent = upper->parent; in rotate_left()
100 /* don't need to check for root node here because root->parent is in rotate_left()
101 the sentinel nil node, and root->parent->left points back to root */ in rotate_left()
111 upper->parent = lower; in rotate_left()
125 lowright->parent = upper; in rotate_right()
127 lower->parent = upparent = upper->parent; in rotate_right()
137 upper->parent = lower; in rotate_right()
276 new->nilnode.parent = &new->nilnode; in dict_create()
361 dict->nilnode.parent = &dict->nilnode; in dict_init()
382 dict->nilnode.parent = &dict->nilnode; in dict_init_like()
398 dict->nilnode.parent = &dict->nilnode; in dict_clear()
422 /* nil->left is the root node; check that its parent pointer is nil */ in dict_verify()
423 if (nil->left->parent != nil) in dict_verify()
581 dnode_t *parent = nil, *uncle, *grandpa; in dict_insert() local
593 parent = where; in dict_insert()
606 parent->left = node; in dict_insert()
608 parent->right = node; in dict_insert()
610 node->parent = parent; in dict_insert()
620 while (parent->color == dnode_red) { in dict_insert()
621 grandpa = parent->parent; in dict_insert()
622 if (parent == grandpa->left) { in dict_insert()
624 if (uncle->color == dnode_red) { /* red parent, red uncle */ in dict_insert()
625 parent->color = dnode_black; in dict_insert()
629 parent = grandpa->parent; in dict_insert()
630 } else { /* red parent, black uncle */ in dict_insert()
631 if (node == parent->right) { in dict_insert()
632 rotate_left(parent); in dict_insert()
633 parent = node; in dict_insert()
634 dict_assert (grandpa == parent->parent); in dict_insert()
635 /* rotation between parent and child preserves grandpa */ in dict_insert()
637 parent->color = dnode_black; in dict_insert()
642 } else { /* symmetric cases: parent == parent->parent->right */ in dict_insert()
645 parent->color = dnode_black; in dict_insert()
649 parent = grandpa->parent; in dict_insert()
651 if (node == parent->left) { in dict_insert()
652 rotate_right(parent); in dict_insert()
653 parent = node; in dict_insert()
654 dict_assert (grandpa == parent->parent); in dict_insert()
656 parent->color = dnode_black; in dict_insert()
678 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; in dict_delete()
699 dnode_t *nextparent = next->parent; in dict_delete()
703 dict_assert (next->parent != nil); in dict_delete()
712 child->parent = nextparent; in dict_delete()
726 next->parent = delparent; in dict_delete()
729 next->left->parent = next; in dict_delete()
730 next->right->parent = next; in dict_delete()
747 child->parent = delparent = delete->parent; in dict_delete()
757 delete->parent = NULL; in dict_delete()
768 dnode_t *parent, *sister; in dict_delete() local
773 parent = child->parent; in dict_delete()
774 if (child == parent->left) { in dict_delete()
775 sister = parent->right; in dict_delete()
779 parent->color = dnode_red; in dict_delete()
780 rotate_left(parent); in dict_delete()
781 sister = parent->right; in dict_delete()
787 child = parent; in dict_delete()
794 sister = parent->right; in dict_delete()
797 sister->color = parent->color; in dict_delete()
799 parent->color = dnode_black; in dict_delete()
800 rotate_left(parent); in dict_delete()
803 } else { /* symmetric case: child == child->parent->right */ in dict_delete()
804 dict_assert (child == parent->right); in dict_delete()
805 sister = parent->left; in dict_delete()
809 parent->color = dnode_red; in dict_delete()
810 rotate_right(parent); in dict_delete()
811 sister = parent->left; in dict_delete()
817 child = parent; in dict_delete()
824 sister = parent->left; in dict_delete()
827 sister->color = parent->color; in dict_delete()
829 parent->color = dnode_black; in dict_delete()
830 rotate_right(parent); in dict_delete()
912 dnode_t *nil = dict_nil(dict), *parent, *left; in dict_next() local
921 parent = curr->parent; in dict_next()
923 while (parent != nil && curr == parent->right) { in dict_next()
924 curr = parent; in dict_next()
925 parent = curr->parent; in dict_next()
928 return (parent == nil) ? NULL : parent; in dict_next()
938 dnode_t *nil = dict_nil(dict), *parent, *right; in dict_prev() local
947 parent = curr->parent; in dict_prev()
949 while (parent != nil && curr == parent->left) { in dict_prev()
950 curr = parent; in dict_prev()
951 parent = curr->parent; in dict_prev()
954 return (parent == nil) ? NULL : parent; in dict_prev()
1004 new->parent = NULL; in dnode_create()
1014 dnode->parent = NULL; in dnode_init()
1046 return (dnode->parent && dnode->left && dnode->right); in dnode_is_in_a_dict()
1133 complete->parent = tree[level]; in dict_load_end()
1149 complete->parent = tree[level]; in dict_load_end()
1156 complete->parent = curr; in dict_load_end()
1169 complete->parent = tree[i]; in dict_load_end()
1176 complete->parent = dictnil; in dict_load_end()