Lines Matching refs:parent
43 * program which uses dict to define, for instance, a macro called ``parent''.
53 #define parent dict_parent
88 lowleft->parent = upper;
90 lower->parent = upparent = upper->parent;
92 /* don't need to check for root node here because root->parent is
93 the sentinel nil node, and root->parent->left points back to root */
103 upper->parent = lower;
116 lowright->parent = upper;
118 lower->parent = upparent = upper->parent;
128 upper->parent = lower;
260 new->nilnode.parent = &new->nilnode;
333 dict->nilnode.parent = &dict->nilnode;
353 dict->nilnode.parent = &dict->nilnode;
368 dict->nilnode.parent = &dict->nilnode;
391 /* nil->left is the root node; check that its parent pointer is nil */
392 if (nil->left->parent != nil)
545 dnode_t *parent = nil, *uncle, *grandpa;
557 parent = where;
570 parent->left = node;
572 parent->right = node;
574 node->parent = parent;
584 while (parent->color == dnode_red) {
585 grandpa = parent->parent;
586 if (parent == grandpa->left) {
588 if (uncle->color == dnode_red) { /* red parent, red uncle */
589 parent->color = dnode_black;
593 parent = grandpa->parent;
594 } else { /* red parent, black uncle */
595 if (node == parent->right) {
596 rotate_left(parent);
597 parent = node;
598 dict_assert(grandpa == parent->parent);
599 /* rotation between parent and child preserves grandpa */
601 parent->color = dnode_black;
606 } else { /* symmetric cases: parent == parent->parent->right */
609 parent->color = dnode_black;
613 parent = grandpa->parent;
615 if (node == parent->left) {
616 rotate_right(parent);
617 parent = node;
618 dict_assert(grandpa == parent->parent);
620 parent->color = dnode_black;
641 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
662 dnode_t *nextparent = next->parent;
666 dict_assert(next->parent != nil);
675 child->parent = nextparent;
689 next->parent = delparent;
692 next->left->parent = next;
693 next->right->parent = next;
710 child->parent = delparent = delete->parent;
720 delete->parent = NULL;
731 dnode_t *parent, *sister;
736 parent = child->parent;
737 if (child == parent->left) {
738 sister = parent->right;
742 parent->color = dnode_red;
743 rotate_left(parent);
744 sister = parent->right;
750 child = parent;
757 sister = parent->right;
760 sister->color = parent->color;
762 parent->color = dnode_black;
763 rotate_left(parent);
766 } else { /* symmetric case: child == child->parent->right */
767 dict_assert(child == parent->right);
768 sister = parent->left;
772 parent->color = dnode_red;
773 rotate_right(parent);
774 sister = parent->left;
780 child = parent;
787 sister = parent->left;
790 sister->color = parent->color;
792 parent->color = dnode_black;
793 rotate_right(parent);
871 dnode_t *nil = dict_nil(dict), *parent, *left;
880 parent = curr->parent;
882 while (parent != nil && curr == parent->right) {
883 curr = parent;
884 parent = curr->parent;
887 return (parent == nil) ? NULL : parent;
896 dnode_t *nil = dict_nil(dict), *parent, *right;
905 parent = curr->parent;
907 while (parent != nil && curr == parent->left) {
908 curr = parent;
909 parent = curr->parent;
912 return (parent == nil) ? NULL : parent;
962 new->parent = NULL;
972 dnode->parent = NULL;
1004 return (dnode->parent && dnode->left && dnode->right);
1091 complete->parent = tree[level];
1107 complete->parent = tree[level];
1114 complete->parent = curr;
1127 complete->parent = tree[i];
1134 complete->parent = dictnil;