erts: Implement ets:info(T, stats) for catrees

{RouteNodes, BaseNodes, MaxRouteTreeDepth}

3 files changed, 57 insertions, 2 deletions

diff --git a/erts/emulator/beam/erl_db.c b/erts/emulator/beam/erl_db.c
index 3653c0bf7c..337efa94bd 100644
--- a/erts/emulator/beam/erl_db.c
+++ b/erts/emulator/beam/erl_db.c
@@ -4247,9 +4247,20 @@ static Eterm table_info(Process* p, DbTable* tb, Eterm What)
 			 make_small(stats.max_chain_len),
 			 make_small(stats.kept_items));
 	}
-	else {
+	else if (IS_CATREE_TABLE(tb->common.status)) {
+            DbCATreeStats stats;
+            Eterm* hp;
+
+            db_calc_stats_catree(&tb->catree, &stats);
+            hp = HAlloc(p, 4);
+            ret = TUPLE3(hp,
+                         make_small(stats.route_nodes),
+                         make_small(stats.base_nodes),
+                         make_small(stats.max_depth));
+
+        }
+        else
 	    ret = am_false;
-	}
     }
     return ret;
 }
diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c
index d433a5b56e..f467230ced 100644
--- a/erts/emulator/beam/erl_db_catree.c
+++ b/erts/emulator/beam/erl_db_catree.c
@@ -2118,6 +2118,42 @@ void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable)
 }
 #endif /* ERTS_ENABLE_LOCK_COUNT */
 
+void db_calc_stats_catree(DbTableCATree* tb, DbCATreeStats* stats)
+{
+    DbTableCATreeNode* stack[ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT];
+    DbTableCATreeNode* node;
+    Uint depth = 0;
+
+    stats->route_nodes = 0;
+    stats->base_nodes = 0;
+    stats->max_depth = 0;
+
+    node = GET_ROOT(tb);
+    do {
+        while (!node->is_base_node) {
+            stats->route_nodes++;
+            ASSERT(depth < sizeof(stack)/sizeof(*stack));
+            stack[depth++] = node;  /* PUSH parent */
+            if (stats->max_depth < depth)
+                stats->max_depth = depth;
+            node = GET_LEFT(node);
+        }
+        stats->base_nodes++;
+
+        while (depth > 0) {
+            DbTableCATreeNode* parent = stack[depth-1];
+            if (node == GET_LEFT(parent)) {
+                node = GET_RIGHT(parent);
+                break;
+            }
+            else {
+                ASSERT(node == GET_RIGHT(parent));
+                node = parent;
+                depth--; /* POP parent */
+            }
+        }
+    } while (depth > 0);
+}
 
 #ifdef HARDDEBUG
 
diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h
index 510a9e81d3..e3d574589c 100644
--- a/erts/emulator/beam/erl_db_catree.h
+++ b/erts/emulator/beam/erl_db_catree.h
@@ -120,4 +120,12 @@ TreeDbTerm** catree_find_last_root(CATreeRootIterator*);
 void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable);
 #endif
 
+typedef struct {
+    Uint route_nodes;
+    Uint base_nodes;
+    Uint max_depth;
+} DbCATreeStats;
+void db_calc_stats_catree(DbTableCATree*, DbCATreeStats*);
+
+
 #endif /* _DB_CATREE_H */