aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/erl_db_catree.c138
-rw-r--r--erts/emulator/beam/erl_db_tree.c32
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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-31 16:42:04 +0000