Lines Matching refs:left
51 #define left dict_left
69 #define dict_root(D) ((D)->nilnode.left)
77 * Perform a ``left rotation'' adjustment on the tree. The given node P and
78 * its right child C are rearranged so that the P instead becomes the left
79 * child of C. The left subtree of C is inherited as the new right subtree
88 upper->right = lowleft = lower->left;
94 the sentinel nil node, and root->parent->left points back to root */
96 if (upper == upparent->left) {
97 upparent->left = lower;
103 lower->left = upper;
109 * the same procedure, but with left and right interchanged.
116 lower = upper->left;
117 upper->left = lowright = lower->right;
125 assert (upper == upparent->left);
126 upparent->left = lower;
142 free_nodes(dict, node->left, nil);
184 * be computed recursively and compared for left and right siblings for
196 height_left = verify_redblack(nil, root->left);
203 if (root->left->color != dnode_black)
227 return 1 + verify_node_count(nil, root->left)
243 || verify_dict_has_node(nil, root->left, node)
266 new->nilnode.left = &new->nilnode;
314 dict->nilnode.left = &dict->nilnode;
343 dict->nilnode.left = &dict->nilnode;
364 dict->nilnode.left = &dict->nilnode;
380 dict->nilnode.left = &dict->nilnode;
406 /* nil->left is the root node; check that its parent pointer is nil */
407 if (nil->left->parent != nil)
426 int dict_similar(const dict_t *left, const dict_t *right)
428 if (left->compare != right->compare)
431 if (left->allocnode != right->allocnode)
434 if (left->freenode != right->freenode)
437 if (left->context != right->context)
440 if (left->dupes != right->dupes)
466 root = root->left;
475 root = root->left;
506 root = root->left;
512 root = root->left;
535 root = root->left;
581 where = where->left;
589 parent->left = node;
594 node->left = nil;
605 if (parent == grandpa->left) {
626 uncle = grandpa->left;
634 if (node == parent->left) {
680 if (delete->left != nil && delete->right != nil) {
687 assert (next->left == nil);
697 if (nextparent->left == next) {
698 nextparent->left = child;
710 next->left = delete->left;
712 next->left->parent = next;
717 if (delparent->left == delete) {
718 delparent->left = next;
726 assert (delete->left == nil || delete->right == nil);
728 child = (delete->left != nil) ? delete->left : delete->right;
732 if (delete == delparent->left) {
733 delparent->left = child;
742 delete->left = NULL;
757 if (child == parent->left) {
767 if (sister->left->color == dnode_black
773 assert (sister->left->color == dnode_red);
774 sister->left->color = dnode_black;
788 sister = parent->left;
794 sister = parent->left;
798 && sister->left->color == dnode_black) {
802 if (sister->left->color == dnode_black) {
807 sister = parent->left;
811 sister->left->color = dnode_black;
861 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
864 while ((left = root->left) != nil)
865 root = left;
888 * next key in the the left to right ordering. If the node has
895 dnode_t *nil = dict_nil(dict), *parent, *left;
899 while ((left = curr->left) != nil)
900 curr = left;
923 if (curr->left != nil) {
924 curr = curr->left;
932 while (parent != nil && curr == parent->left) {
988 new->left = NULL;
998 dnode->left = NULL;
1027 return (dnode->parent && dnode->left && dnode->right);
1047 load->nilnode.left = &load->nilnode;
1068 assert (dict->compare(nil->left->key, key) <= 0);
1070 assert (dict->compare(nil->left->key, key) < 0);
1075 nil->right->left = newnode;
1077 newnode->left = nil;
1098 for (curr = loadnil->left; curr != loadnil; curr = next) {
1099 next = curr->left;
1120 curr->left = dictnil;
1133 curr->left = complete;
1194 leftnode->left = NULL; /* suppress assertion in dict_load_next */
1205 rightnode->left = NULL;