aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--erts/emulator/beam/erl_db_catree.c138
-rw-r--r--erts/emulator/beam/erl_db_tree.c32
-rw-r--r--lib/stdlib/test/ets_SUITE.erl24
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.