aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_db_catree.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_db_catree.c')
-rw-r--r--erts/emulator/beam/erl_db_catree.c138
1 files changed, 78 insertions, 60 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)
{
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 03:16:57 +0000