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
87 upper->right = lowleft = lower->left;
93 the sentinel nil node, and root->parent->left points back to root */
95 if (upper == upparent->left) {
96 upparent->left = lower;
102 lower->left = upper;
108 * the same procedure, but with left and right interchanged.
114 lower = upper->left;
115 upper->left = lowright = lower->right;
123 dict_assert(upper == upparent->left);
124 upparent->left = lower;
139 free_nodes(dict, node->left, nil);
181 * be computed recursively and compared for left and right siblings for
192 height_left = verify_redblack(nil, root->left);
199 if (root->left->color != dnode_black)
222 return 1 + verify_node_count(nil, root->left)
237 || verify_dict_has_node(nil, root->left, node)
258 new->nilnode.left = &new->nilnode;
303 dict->nilnode.left = &dict->nilnode;
331 dict->nilnode.left = &dict->nilnode;
351 dict->nilnode.left = &dict->nilnode;
366 dict->nilnode.left = &dict->nilnode;
391 /* nil->left is the root node; check that its parent pointer is nil */
392 if (nil->left->parent != nil)
411 int dict_similar(const dict_t *left, const dict_t *right)
413 if (left->compare != right->compare)
416 if (left->allocnode != right->allocnode)
419 if (left->freenode != right->freenode)
422 if (left->context != right->context)
425 if (left->dupes != right->dupes)
450 root = root->left;
459 root = root->left;
489 root = root->left;
495 root = root->left;
517 root = root->left;
562 where = where->left;
570 parent->left = node;
575 node->left = nil;
586 if (parent == grandpa->left) {
607 uncle = grandpa->left;
615 if (node == parent->left) {
660 if (delete->left != nil && delete->right != nil) {
667 dict_assert(next->left == nil);
677 if (nextparent->left == next) {
678 nextparent->left = child;
690 next->left = delete->left;
692 next->left->parent = next;
697 if (delparent->left == delete) {
698 delparent->left = next;
706 dict_assert(delete->left == nil || delete->right == nil);
708 child = (delete->left != nil) ? delete->left : delete->right;
712 if (delete == delparent->left) {
713 delparent->left = child;
722 delete->left = NULL;
737 if (child == parent->left) {
747 if (sister->left->color == dnode_black
753 dict_assert(sister->left->color == dnode_red);
754 sister->left->color = dnode_black;
768 sister = parent->left;
774 sister = parent->left;
778 && sister->left->color == dnode_black) {
782 if (sister->left->color == dnode_black) {
787 sister = parent->left;
791 sister->left->color = dnode_black;
839 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
842 while ((left = root->left) != nil)
843 root = left;
865 * next key in the the left to right ordering. If the node has
871 dnode_t *nil = dict_nil(dict), *parent, *left;
875 while ((left = curr->left) != nil)
876 curr = left;
898 if (curr->left != nil) {
899 curr = curr->left;
907 while (parent != nil && curr == parent->left) {
963 new->left = NULL;
973 dnode->left = NULL;
1004 return (dnode->parent && dnode->left && dnode->right);
1026 load->nilnode.left = &load->nilnode;
1047 dict_assert(dict->compare(nil->left->key, key) <= 0);
1049 dict_assert(dict->compare(nil->left->key, key) < 0);
1054 nil->right->left = newnode;
1056 newnode->left = nil;
1077 for (curr = loadnil->left; curr != loadnil; curr = next) {
1078 next = curr->left;
1099 curr->left = dictnil;
1112 curr->left = complete;
1173 leftnode->left = NULL; /* suppress assertion in dict_load_next */
1184 rightnode->left = NULL;