1 files changed, 46 insertions, 4 deletions

diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h
index 1f2c7da091..418837be8e 100644
--- a/erts/emulator/beam/erl_db_catree.h
+++ b/erts/emulator/beam/erl_db_catree.h
@@ -34,23 +34,33 @@
 struct DbTableCATreeNode;
 
 typedef struct {
+    Eterm term;
+    struct erl_off_heap_header* oh;
+    Uint size;
+    Eterm heap[1];
+} DbRouteKey;
+
+typedef struct {
     erts_rwmtx_t lock; /* The lock for this base node */
     Sint lock_statistics;
     int is_valid; /* If this base node is still valid */
     TreeDbTerm *root; /* The root of the sequential tree */
-    DbTable * tab; /* Table ptr, used when freeing using thread progress */
     ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */
     struct DbTableCATreeNode * next; /* Used when gradually deleting */
+
+    char end_of_struct__;
 } DbTableCATreeBaseNode;
 
 typedef struct {
+#ifdef ERTS_ENABLE_LOCK_CHECK
+    Sint lc_order;
+#endif
     ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */
-    DbTable* tab; /* Table ptr, used when freeing using thread progress */
     erts_mtx_t lock; /* Used when joining route nodes */
     int is_valid; /* If this route node is still valid */
     erts_atomic_t left;
     erts_atomic_t right;
-    DbTerm key;
+    DbRouteKey key;
 } DbTableCATreeRouteNode;
 
 typedef struct DbTableCATreeNode {
@@ -58,7 +68,7 @@ typedef struct DbTableCATreeNode {
     union {
         DbTableCATreeRouteNode route;
         DbTableCATreeBaseNode base;
-    } baseOrRoute;
+    } u;
 } DbTableCATreeNode;
 
 typedef struct {
@@ -79,13 +89,45 @@ typedef struct db_table_catree {
     int is_routing_nodes_freed;
 } DbTableCATree;
 
+typedef struct {
+    DbTableCATree* tb;
+    Eterm next_route_key;
+    DbTableCATreeNode* locked_bnode;
+    DbTableCATreeNode* bnode_parent;
+    int bnode_level;
+    int read_only;
+    DbRouteKey* search_key;
+} CATreeRootIterator;
+
+
 void db_initialize_catree(void);
 
 int db_create_catree(Process *p, DbTable *tbl);
 
 
+TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator*);
+
+TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, CATreeRootIterator*);
+TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, CATreeRootIterator*);
+TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator*, int next, Eterm* keyp);
+TreeDbTerm** catree_find_next_root(CATreeRootIterator*, Eterm* keyp);
+TreeDbTerm** catree_find_prev_root(CATreeRootIterator*, Eterm* keyp);
+TreeDbTerm** catree_find_first_root(CATreeRootIterator*);
+TreeDbTerm** catree_find_last_root(CATreeRootIterator*);
+
+
 #ifdef ERTS_ENABLE_LOCK_COUNT
 void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable);
 #endif
 
+void db_catree_force_split(DbTableCATree*, int on);
+
+typedef struct {
+    Uint route_nodes;
+    Uint base_nodes;
+    Uint max_depth;
+} DbCATreeStats;
+void db_calc_stats_catree(DbTableCATree*, DbCATreeStats*);
+
+
 #endif /* _DB_CATREE_H */