erts: Tidy some ordered_set iteration code

with variable name changes, some comments
and moved catree_find_prev_from_pb_key_root after its twin.

2 files changed, 102 insertions, 65 deletions

diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c
index 7a5587f1fd..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;
 
@@ -1599,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;
@@ -1609,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) {
@@ -1629,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 {
@@ -1638,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 {
@@ -1661,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
@@ -1682,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
@@ -1704,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 {
@@ -1727,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);