diff options
| -rw-r--r-- | erts/emulator/beam/erl_db_catree.c | 138 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_db_tree.c | 32 | ||||
| -rw-r--r-- | lib/stdlib/test/ets_SUITE.erl | 24 |
3 files changed, 118 insertions, 76 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); diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index e49181b12f..cc369979f7 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -6052,8 +6052,9 @@ smp_ordered_iteration(Config) when is_list(Config) -> smp_ordered_iteration_do(Opts) -> KeyRange = 1000, + OffHeap = fun() -> dummy end, % To exercise key copy/destroy code. KeyFun = fun(K, Type) -> - {K div 10, K rem 10, Type} + {K div 10, K rem 10, Type, OffHeap} end, StimKeyFun = fun(K) -> KeyFun(K, element(rand:uniform(3), @@ -6084,7 +6085,7 @@ smp_ordered_iteration_do(Opts) -> incr_counter(select_delete_bk, Counters); R when R =< 20 -> %% Delete partially bound key - ets:select_delete(T, [{{{K div 10, '_', volatile}, '_'}, [], [true]}]), + ets:select_delete(T, [{{{K div 10, '_', volatile, '_'}, '_'}, [], [true]}]), incr_counter(select_delete_pbk, Counters); R when R =< 21 -> %% Replace bound key @@ -6093,7 +6094,7 @@ smp_ordered_iteration_do(Opts) -> incr_counter(select_replace_bk, Counters); _ -> %% Replace partially bound key - ets:select_replace(T, [{{{K div 10, '_', volatile}, '$1'}, [], + ets:select_replace(T, [{{{K div 10, '_', volatile, '_'}, '$1'}, [], [{{{element,1,'$_'}, {'+','$1',1}}}]}]), incr_counter(select_replace_pbk, Counters) end, @@ -6106,14 +6107,17 @@ smp_ordered_iteration_do(Opts) -> FiniF = fun (Acc) -> Acc end, Pids = run_sched_workers(InitF, ExecF, FiniF, infinite), timer:send_after(1000, stop), + + Log2ChunkMax = math:log2(NStable*2), Rounds = fun Loop(N) -> - NStable = ets:select_count(T, [{{{'_', '_', stable}, '_'}, [], [true]}]), + MS = [{{{'_', '_', stable, '_'}, '_'}, [], [true]}], + NStable = ets:select_count(T, MS), NStable = count_stable(T, next, ets:first(T), 0), NStable = count_stable(T, prev, ets:last(T), 0), - NStable = length(ets:select(T, [{{{'_', '_', stable}, '_'}, [], [true]}])), - NStable = length(ets:select_reverse(T, [{{{'_', '_', stable}, '_'}, [], [true]}])), - NStable = ets_select_chunks_count(T, [{{{'_', '_', stable}, '_'}, [], [true]}], - rand:uniform(5)), + NStable = length(ets:select(T, MS)), + NStable = length(ets:select_reverse(T, MS)), + Chunk = round(math:pow(2, rand:uniform()*Log2ChunkMax)), + NStable = ets_select_chunks_count(T, MS, Chunk), receive stop -> N after 0 -> Loop(N+1) end @@ -6130,9 +6134,9 @@ smp_ordered_iteration_do(Opts) -> incr_counter(Name, Counters) -> Counters#{Name => maps:get(Name, Counters, 0) + 1}. -count_stable(T, Next, {_, _, stable}=Key, N) -> +count_stable(T, Next, {_, _, stable, _}=Key, N) -> count_stable(T, Next, ets:Next(T, Key), N+1); -count_stable(T, Next, {_, _, volatile}=Key, N) -> +count_stable(T, Next, {_, _, volatile, _}=Key, N) -> count_stable(T, Next, ets:Next(T, Key), N); count_stable(_, _, '$end_of_table', N) -> N. |