diff options
Diffstat (limited to 'erts/emulator')
-rw-r--r-- | erts/emulator/beam/erl_db_catree.c | 138 | ||||
-rw-r--r-- | erts/emulator/beam/erl_db_tree.c | 32 |
2 files changed, 104 insertions, 66 deletions
diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index b52a4a53fe..639c7e5e03 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -1532,52 +1532,7 @@ TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator* iter) return &base_node->u.base.root; } - -TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, - CATreeRootIterator* iter) -{ -#ifdef DEBUG - DbTableCATreeNode *rejected_base = NULL; -#endif - DbTableCATreeNode *node; - DbTableCATreeNode *parent; - DbTableCATreeNode* next_route_node; - int current_level; - - ASSERT(!iter->locked_bnode); - - while (1) { - node = GET_ROOT_ACQB(iter->tb); - current_level = 0; - parent = NULL; - next_route_node = NULL; - while (!node->is_base_node) { - current_level++; - parent = node; - if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) <= 0) { - next_route_node = node; - node = GET_LEFT_ACQB(node); - } else { - node = GET_RIGHT_ACQB(node); - } - } - ASSERT(node != rejected_base); - lock_iter_base_node(iter, node, parent, current_level); - if (node->u.base.is_valid) { - iter->next_route_key = (next_route_node ? - next_route_node->u.route.key.term : - THE_NON_VALUE); - return &node->u.base.root; - } - /* Retry */ - unlock_iter_base_node(iter); -#ifdef DEBUG - rejected_base = node; -#endif - } -} - -static Eterm copy_iter_search_key(CATreeRootIterator* iter, Eterm key) +static Eterm save_iter_search_key(CATreeRootIterator* iter, Eterm key) { Uint key_size; @@ -1585,7 +1540,8 @@ static Eterm copy_iter_search_key(CATreeRootIterator* iter, Eterm key) return key; if (iter->search_key) { - ASSERT(key != iter->search_key->term); + if (key == iter->search_key->term) + return key; /* already saved */ destroy_route_key(iter->search_key); } key_size = size_object(key); @@ -1598,8 +1554,9 @@ static Eterm copy_iter_search_key(CATreeRootIterator* iter, Eterm key) return copy_route_key(iter->search_key, key, key_size); } -TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, - Eterm *keyp) +TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, + int forward, + Eterm *search_keyp) { #ifdef DEBUG DbTableCATreeNode *rejected_invalid = NULL; @@ -1608,16 +1565,16 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, DbTableCATreeNode *node; DbTableCATreeNode *parent; DbTableCATreeNode* next_route_node; - Eterm key = iter->next_route_key; + Eterm route_key = iter->next_route_key; int current_level; if (iter->locked_bnode) { - if (keyp) - *keyp = copy_iter_search_key(iter, *keyp); + if (search_keyp) + *search_keyp = save_iter_search_key(iter, *search_keyp); unlock_iter_base_node(iter); } - if (is_non_value(key)) + if (is_non_value(route_key)) return NULL; while (1) { @@ -1628,8 +1585,8 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, while (!node->is_base_node) { current_level++; parent = node; - if (next) { - if (cmp_key_route(key,node) < 0) { + if (forward) { + if (cmp_key_route(route_key,node) < 0) { next_route_node = node; node = GET_LEFT_ACQB(node); } else { @@ -1637,7 +1594,7 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, } } else { - if (cmp_key_route(key,node) > 0) { + if (cmp_key_route(route_key,node) > 0) { next_route_node = node; node = GET_RIGHT_ACQB(node); } else { @@ -1660,7 +1617,7 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, unlock_iter_base_node(iter); return NULL; } - key = next_route_node->u.route.key.term; + route_key = next_route_node->u.route.key.term; IF_DEBUG(rejected_empty = node); } else @@ -1681,8 +1638,16 @@ TreeDbTerm** catree_find_prev_root(CATreeRootIterator *iter, Eterm* keyp) return catree_find_nextprev_root(iter, 0, keyp); } - -TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, +/* @brief Find root of tree where object with smallest key of all larger than + * partially bound key may reside. Can be used as a starting point for + * a reverse iteration with pb_key. + * + * @param pb_key The partially bound key. Example {42, '$1'} + * @param iter An initialized root iterator. + * + * @return Pointer to found root pointer. May not be NULL. + */ +TreeDbTerm** catree_find_next_from_pb_key_root(Eterm pb_key, CATreeRootIterator* iter) { #ifdef DEBUG @@ -1703,7 +1668,7 @@ TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, while (!node->is_base_node) { current_level++; parent = node; - if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) >= 0) { + if (cmp_partly_bound(pb_key, GET_ROUTE_NODE_KEY(node)) >= 0) { next_route_node = node; node = GET_RIGHT_ACQB(node); } else { @@ -1726,6 +1691,59 @@ TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, } } +/* @brief Find root of tree where object with largest key of all smaller than + * partially bound key may reside. Can be used as a starting point for + * a forward iteration with pb_key. + * + * @param pb_key The partially bound key. Example {42, '$1'} + * @param iter An initialized root iterator. + * + * @return Pointer to found root pointer. May not be NULL. + */ +TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, + CATreeRootIterator* iter) +{ +#ifdef DEBUG + DbTableCATreeNode *rejected_base = NULL; +#endif + DbTableCATreeNode *node; + DbTableCATreeNode *parent; + DbTableCATreeNode* next_route_node; + int current_level; + + ASSERT(!iter->locked_bnode); + + while (1) { + node = GET_ROOT_ACQB(iter->tb); + current_level = 0; + parent = NULL; + next_route_node = NULL; + while (!node->is_base_node) { + current_level++; + parent = node; + if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) <= 0) { + next_route_node = node; + node = GET_LEFT_ACQB(node); + } else { + node = GET_RIGHT_ACQB(node); + } + } + ASSERT(node != rejected_base); + lock_iter_base_node(iter, node, parent, current_level); + if (node->u.base.is_valid) { + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + return &node->u.base.root; + } + /* Retry */ + unlock_iter_base_node(iter); +#ifdef DEBUG + rejected_base = node; +#endif + } +} + static TreeDbTerm** catree_find_firstlast_root(CATreeRootIterator* iter, int first) { diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index f5fac9dcb6..02a5934a6e 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -2963,8 +2963,18 @@ found_prev: } +/* @brief Find object with smallest key of all larger than partially bound key. + * Can be used as a starting point for a reverse iteration with pb_key. + * + * @param pb_key The partially bound key. Example {42, '$1'} + * @param *rootpp Will return pointer to root pointer of tree with found object. + * @param iter Root iterator or NULL for plain DbTableTree. + * @param stack A stack to use. Will be cleared. + * + * @return found object or NULL if no such key exists. + */ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, - DbTreeStack* stack, Eterm key, + DbTreeStack* stack, Eterm pb_key, CATreeRootIterator* iter) { TreeDbTerm* root; @@ -2973,7 +2983,7 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, Sint c; if (iter) { - *rootpp = catree_find_next_from_pb_key_root(key, iter); + *rootpp = catree_find_next_from_pb_key_root(pb_key, iter); ASSERT(*rootpp); root = **rootpp; } @@ -2988,7 +2998,7 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, return NULL; for (;;) { PUSH_NODE(stack, this); - if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) >= 0) { + if (( c = cmp_partly_bound(pb_key,GETKEY(tbl, this->dbterm.tpl))) >= 0) { if (this->right == NULL) { stack->pos = candidate; return TOP_NODE(stack); @@ -3003,8 +3013,18 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, } } +/* @brief Find object with largest key of all smaller than partially bound key. + * Can be used as a starting point for a forward iteration with pb_key. + * + * @param pb_key The partially bound key. Example {42, '$1'} + * @param *rootpp Will return pointer to root pointer of found object. + * @param iter Root iterator or NULL for plain DbTableTree. + * @param stack A stack to use. Will be cleared. + * + * @return found object or NULL if no such key exists. + */ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, - DbTreeStack* stack, Eterm key, + DbTreeStack* stack, Eterm pb_key, CATreeRootIterator* iter) { TreeDbTerm* root; @@ -3013,7 +3033,7 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, Sint c; if (iter) { - *rootpp = catree_find_prev_from_pb_key_root(key, iter); + *rootpp = catree_find_prev_from_pb_key_root(pb_key, iter); ASSERT(*rootpp); root = **rootpp; } @@ -3028,7 +3048,7 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, return NULL; for (;;) { PUSH_NODE(stack, this); - if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) <= 0) { + if (( c = cmp_partly_bound(pb_key,GETKEY(tbl, this->dbterm.tpl))) <= 0) { if (this->left == NULL) { stack->pos = candidate; return TOP_NODE(stack); |