Lines Matching full:parent
49 * program which uses dict to define, for instance, a macro called ``parent''.
59 #define parent dict_parent macro
95 lowleft->parent = upper; in rotate_left()
97 lower->parent = upparent = upper->parent; in rotate_left()
99 /* don't need to check for root node here because root->parent is in rotate_left()
100 the sentinel nil node, and root->parent->left points back to root */ in rotate_left()
110 upper->parent = lower; in rotate_left()
124 lowright->parent = upper; in rotate_right()
126 lower->parent = upparent = upper->parent; in rotate_right()
136 upper->parent = lower; in rotate_right()
274 new->nilnode.parent = &new->nilnode; in dict_create()
351 dict->nilnode.parent = &dict->nilnode; in dict_init()
372 dict->nilnode.parent = &dict->nilnode; in dict_init_like()
388 dict->nilnode.parent = &dict->nilnode; in dict_clear()
412 /* nil->left is the root node; check that its parent pointer is nil */ in dict_verify()
413 if (nil->left->parent != nil) in dict_verify()
570 dnode_t *parent = nil, *uncle, *grandpa; in dict_insert() local
582 parent = where; in dict_insert()
595 parent->left = node; in dict_insert()
597 parent->right = node; in dict_insert()
599 node->parent = parent; in dict_insert()
609 while (parent->color == dnode_red) { in dict_insert()
610 grandpa = parent->parent; in dict_insert()
611 if (parent == grandpa->left) { in dict_insert()
613 if (uncle->color == dnode_red) { /* red parent, red uncle */ in dict_insert()
614 parent->color = dnode_black; in dict_insert()
618 parent = grandpa->parent; in dict_insert()
619 } else { /* red parent, black uncle */ in dict_insert()
620 if (node == parent->right) { in dict_insert()
621 rotate_left(parent); in dict_insert()
622 parent = node; in dict_insert()
623 dict_assert (grandpa == parent->parent); in dict_insert()
624 /* rotation between parent and child preserves grandpa */ in dict_insert()
626 parent->color = dnode_black; in dict_insert()
631 } else { /* symmetric cases: parent == parent->parent->right */ in dict_insert()
634 parent->color = dnode_black; in dict_insert()
638 parent = grandpa->parent; in dict_insert()
640 if (node == parent->left) { in dict_insert()
641 rotate_right(parent); in dict_insert()
642 parent = node; in dict_insert()
643 dict_assert (grandpa == parent->parent); in dict_insert()
645 parent->color = dnode_black; in dict_insert()
667 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; in dict_delete()
688 dnode_t *nextparent = next->parent; in dict_delete()
692 dict_assert (next->parent != nil); in dict_delete()
701 child->parent = nextparent; in dict_delete()
715 next->parent = delparent; in dict_delete()
718 next->left->parent = next; in dict_delete()
719 next->right->parent = next; in dict_delete()
736 child->parent = delparent = delete->parent; in dict_delete()
746 delete->parent = NULL; in dict_delete()
757 dnode_t *parent, *sister; in dict_delete() local
762 parent = child->parent; in dict_delete()
763 if (child == parent->left) { in dict_delete()
764 sister = parent->right; in dict_delete()
768 parent->color = dnode_red; in dict_delete()
769 rotate_left(parent); in dict_delete()
770 sister = parent->right; in dict_delete()
776 child = parent; in dict_delete()
783 sister = parent->right; in dict_delete()
786 sister->color = parent->color; in dict_delete()
788 parent->color = dnode_black; in dict_delete()
789 rotate_left(parent); in dict_delete()
792 } else { /* symmetric case: child == child->parent->right */ in dict_delete()
793 dict_assert (child == parent->right); in dict_delete()
794 sister = parent->left; in dict_delete()
798 parent->color = dnode_red; in dict_delete()
799 rotate_right(parent); in dict_delete()
800 sister = parent->left; in dict_delete()
806 child = parent; in dict_delete()
813 sister = parent->left; in dict_delete()
816 sister->color = parent->color; in dict_delete()
818 parent->color = dnode_black; in dict_delete()
819 rotate_right(parent); in dict_delete()
901 dnode_t *nil = dict_nil(dict), *parent, *left; in dict_next() local
910 parent = curr->parent; in dict_next()
912 while (parent != nil && curr == parent->right) { in dict_next()
913 curr = parent; in dict_next()
914 parent = curr->parent; in dict_next()
917 return (parent == nil) ? NULL : parent; in dict_next()
927 dnode_t *nil = dict_nil(dict), *parent, *right; in dict_prev() local
936 parent = curr->parent; in dict_prev()
938 while (parent != nil && curr == parent->left) { in dict_prev()
939 curr = parent; in dict_prev()
940 parent = curr->parent; in dict_prev()
943 return (parent == nil) ? NULL : parent; in dict_prev()
993 new->parent = NULL; in dnode_create()
1003 dnode->parent = NULL; in dnode_init()
1035 return (dnode->parent && dnode->left && dnode->right); in dnode_is_in_a_dict()
1122 complete->parent = tree[level]; in dict_load_end()
1138 complete->parent = tree[level]; in dict_load_end()
1145 complete->parent = curr; in dict_load_end()
1158 complete->parent = tree[i]; in dict_load_end()
1165 complete->parent = dictnil; in dict_load_end()