53 #define parent dict_parent  macro
89     lowleft->parent = upper;  in rotate_left()
91     lower->parent = upparent = upper->parent;  in rotate_left()
104     upper->parent = lower;  in rotate_left()
118     lowright->parent = upper;  in rotate_right()
120     lower->parent = upparent = upper->parent;  in rotate_right()
130     upper->parent = lower;  in rotate_right()
268 	new->nilnode.parent = &new->nilnode;  in dict_create()
345     dict->nilnode.parent = &dict->nilnode;  in dict_init()
366     dict->nilnode.parent = &dict->nilnode;  in dict_init_like()
382     dict->nilnode.parent = &dict->nilnode;  in dict_clear()
407     if (nil->left->parent != nil)  in dict_verify()
564     dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()  local
576 	parent = where;  in dict_insert()
589 	parent->left = node;  in dict_insert()
591 	parent->right = node;  in dict_insert()
593     node->parent = parent;  in dict_insert()
603     while (parent->color == dnode_red) {  in dict_insert()
604 	grandpa = parent->parent;  in dict_insert()
605 	if (parent == grandpa->left) {  in dict_insert()
608 		parent->color = dnode_black;  in dict_insert()
612 		parent = grandpa->parent;  in dict_insert()
614 	    	if (node == parent->right) {  in dict_insert()
615 		    rotate_left(parent);  in dict_insert()
616 		    parent = node;  in dict_insert()
617 		    assert (grandpa == parent->parent);  in dict_insert()
620 		parent->color = dnode_black;  in dict_insert()
628 		parent->color = dnode_black;  in dict_insert()
632 		parent = grandpa->parent;  in dict_insert()
634 	    	if (node == parent->left) {  in dict_insert()
635 		    rotate_right(parent);  in dict_insert()
636 		    parent = node;  in dict_insert()
637 		    assert (grandpa == parent->parent);  in dict_insert()
639 		parent->color = dnode_black;  in dict_insert()
661     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()
682 	dnode_t *nextparent = next->parent;  in dict_delete()
686 	assert (next->parent != nil);  in dict_delete()
695 	child->parent = nextparent;  in dict_delete()
709 	next->parent = delparent;  in dict_delete()
712 	next->left->parent = next;  in dict_delete()
713 	next->right->parent = next;  in dict_delete()
730 	child->parent = delparent = delete->parent;  in dict_delete()
740     delete->parent = NULL;  in dict_delete()
751 	dnode_t *parent, *sister;  in dict_delete()  local
756 	    parent = child->parent;  in dict_delete()
757 	    if (child == parent->left) {  in dict_delete()
758 		sister = parent->right;  in dict_delete()
762 		    parent->color = dnode_red;  in dict_delete()
763 		    rotate_left(parent);  in dict_delete()
764 		    sister = parent->right;  in dict_delete()
770 		    child = parent;  in dict_delete()
777 			sister = parent->right;  in dict_delete()
780 		    sister->color = parent->color;  in dict_delete()
782 		    parent->color = dnode_black;  in dict_delete()
783 		    rotate_left(parent);  in dict_delete()
787 		assert (child == parent->right);  in dict_delete()
788 		sister = parent->left;  in dict_delete()
792 		    parent->color = dnode_red;  in dict_delete()
793 		    rotate_right(parent);  in dict_delete()
794 		    sister = parent->left;  in dict_delete()
800 		    child = parent;  in dict_delete()
807 			sister = parent->left;  in dict_delete()
810 		    sister->color = parent->color;  in dict_delete()
812 		    parent->color = dnode_black;  in dict_delete()
813 		    rotate_right(parent);  in dict_delete()
895     dnode_t *nil = dict_nil(dict), *parent, *left;  in dict_next()  local
904     parent = curr->parent;  in dict_next()
906     while (parent != nil && curr == parent->right) {  in dict_next()
907 	curr = parent;  in dict_next()
908 	parent = curr->parent;  in dict_next()
911     return (parent == nil) ? NULL : parent;  in dict_next()
921     dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()  local
930     parent = curr->parent;  in dict_prev()
932     while (parent != nil && curr == parent->left) {  in dict_prev()
933 	curr = parent;  in dict_prev()
934 	parent = curr->parent;  in dict_prev()
937     return (parent == nil) ? NULL : parent;  in dict_prev()
987 	new->parent = NULL;  in dnode_create()
997     dnode->parent = NULL;  in dnode_init()
1027     return (dnode->parent && dnode->left && dnode->right);  in dnode_is_in_a_dict()
1112 		    complete->parent = tree[level];  in dict_load_end()
1128 		complete->parent = tree[level];  in dict_load_end()
1135 	    complete->parent = curr;  in dict_load_end()
1148 	    complete->parent = tree[i];  in dict_load_end()
1155     complete->parent = dictnil;  in dict_load_end()