Lines Matching refs:left
52 #define left dict_left macro
70 #define dict_root(D) ((D)->nilnode.left)
88 upper->right = lowleft = lower->left; in rotate_left()
96 if (upper == upparent->left) { in rotate_left()
97 upparent->left = lower; in rotate_left()
103 lower->left = upper; in rotate_left()
115 lower = upper->left; in rotate_right()
116 upper->left = lowright = lower->right; in rotate_right()
124 dict_assert(upper == upparent->left); in rotate_right()
125 upparent->left = lower; in rotate_right()
140 free_nodes(dict, node->left, nil); in free_nodes()
193 height_left = verify_redblack(nil, root->left); in verify_redblack()
200 if (root->left->color != dnode_black) in verify_redblack()
223 return 1 + verify_node_count(nil, root->left) in verify_node_count()
238 || verify_dict_has_node(nil, root->left, node) in verify_dict_has_node()
259 new->nilnode.left = &new->nilnode; in dict_create()
304 dict->nilnode.left = &dict->nilnode; in dict_free_nodes()
332 dict->nilnode.left = &dict->nilnode; in dict_init()
352 dict->nilnode.left = &dict->nilnode; in dict_init_like()
367 dict->nilnode.left = &dict->nilnode; in dict_clear()
393 if (nil->left->parent != nil) in dict_verify()
412 int dict_similar(const dict_t *left, const dict_t *right) in dict_similar() argument
414 if (left->compare != right->compare) in dict_similar()
417 if (left->allocnode != right->allocnode) in dict_similar()
420 if (left->freenode != right->freenode) in dict_similar()
423 if (left->context != right->context) in dict_similar()
426 if (left->dupes != right->dupes) in dict_similar()
451 root = root->left; in dict_lookup()
460 root = root->left; in dict_lookup()
490 root = root->left; in dict_lower_bound()
496 root = root->left; in dict_lower_bound()
518 root = root->left; in dict_upper_bound()
563 where = where->left; in dict_insert()
571 parent->left = node; in dict_insert()
576 node->left = nil; in dict_insert()
587 if (parent == grandpa->left) { in dict_insert()
608 uncle = grandpa->left; in dict_insert()
616 if (node == parent->left) { in dict_insert()
661 if (delete->left != nil && delete->right != nil) { in dict_delete()
668 dict_assert(next->left == nil); in dict_delete()
678 if (nextparent->left == next) { in dict_delete()
679 nextparent->left = child; in dict_delete()
691 next->left = delete->left; in dict_delete()
693 next->left->parent = next; in dict_delete()
698 if (delparent->left == delete) { in dict_delete()
699 delparent->left = next; in dict_delete()
707 dict_assert(delete->left == nil || delete->right == nil); in dict_delete()
709 child = (delete->left != nil) ? delete->left : delete->right; in dict_delete()
713 if (delete == delparent->left) { in dict_delete()
714 delparent->left = child; in dict_delete()
723 delete->left = NULL; in dict_delete()
738 if (child == parent->left) { in dict_delete()
748 if (sister->left->color == dnode_black in dict_delete()
754 dict_assert(sister->left->color == dnode_red); in dict_delete()
755 sister->left->color = dnode_black; in dict_delete()
769 sister = parent->left; in dict_delete()
775 sister = parent->left; in dict_delete()
779 && sister->left->color == dnode_black) { in dict_delete()
783 if (sister->left->color == dnode_black) { in dict_delete()
788 sister = parent->left; in dict_delete()
792 sister->left->color = dnode_black; in dict_delete()
840 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; in dict_first() local
843 while ((left = root->left) != nil) in dict_first()
844 root = left; in dict_first()
872 dnode_t *nil = dict_nil(dict), *parent, *left; in dict_next() local
876 while ((left = curr->left) != nil) in dict_next()
877 curr = left; in dict_next()
899 if (curr->left != nil) { in dict_prev()
900 curr = curr->left; in dict_prev()
908 while (parent != nil && curr == parent->left) { in dict_prev()
964 new->left = NULL; in dnode_create()
974 dnode->left = NULL; in dnode_init()
1005 return (dnode->parent && dnode->left && dnode->right); in dnode_is_in_a_dict()
1027 load->nilnode.left = &load->nilnode; in load_begin_internal()
1048 dict_assert(dict->compare(nil->left->key, key) <= 0); in dict_load_next()
1050 dict_assert(dict->compare(nil->left->key, key) < 0); in dict_load_next()
1055 nil->right->left = newnode; in dict_load_next()
1057 newnode->left = nil; in dict_load_next()
1078 for (curr = loadnil->left; curr != loadnil; curr = next) { in dict_load_end()
1079 next = curr->left; in dict_load_end()
1100 curr->left = dictnil; in dict_load_end()
1113 curr->left = complete; in dict_load_end()
1174 leftnode->left = NULL; /* suppress assertion in dict_load_next */ in dict_merge()
1185 rightnode->left = NULL; in dict_merge()