Add a more scalable ETS ordered_set implementation

The current ETS ordered_set implementation can quickly become a
scalability bottleneck on multicore machines when an application updates
an ordered_set table from concurrent processes [1][2]. The current
implementation is based on an AVL tree protected from concurrent writes
by a single readers-writer lock. Furthermore, the current implementation
has an optimization, called the stack optimization [3], that can improve
the performance when only a single process accesses a table but can
cause bad scalability even in read-only scenarios. It is possible to
pass the option {write_concurrency, true} to ets:new/2 when creating an
ETS table of type ordered_set but this option has no effect for tables
of type ordered_set without this commit. The new ETS ordered_set
implementation, added by this commit, is only activated when one passes
the options ordered_set and {write_concurrency, true} to the ets:new/2
function. Thus, the previous ordered_set implementation (from here on
called the default implementation) can still be used in applications
that do not benefit from the new implementation. The benchmark results
on the following web page show that the new implementation is many times
faster than the old implementation in some scenarios and that the old
implementation is still better than the new implementation in some
scenarios.

http://winsh.me/ets_catree_benchmark/ets_ca_tree_benchmark_results.html

The new implementation is expected to scale better than the default
implementation when concurrent processes use the following ETS
operations to operate on a table:

delete/2, delete_object/2, first/1, insert/2 (single object),
insert_new/2 (single object), lookup/2, lookup_element/2, member/2,
next/2, take/2 and update_element/3 (single object).

Currently, the new implementation does not have scalable support for the
other operations (e.g., select/2). However, when these operations are
used infrequently, the new implantation may still scale better than the
default implementation as the benchmark results at the URL above shows.

Description of the New Implementation
----------------------------------

The new implementation is based on a data structure which is called the
contention adapting search tree (CA tree for short). The following
publication contains a detailed description of the CA tree:

A Contention Adapting Approach to Concurrent Ordered Sets
Journal of Parallel and Distributed Computing, 2018
Kjell Winblad and Konstantinos Sagonas
https://doi.org/10.1016/j.jpdc.2017.11.007
http://www.it.uu.se/research/group/languages/software/ca_tree/catree_proofs.pdf

A discussion of how the CA tree can be used as an ETS back-end can be
found in another publication [1]. The CA tree is a data structure that
dynamically changes its synchronization granularity based on detected
contention. Internally, the CA tree uses instances of a sequential data
structure to store items. The CA tree implementation contained in this
commit uses the same AVL tree implementation as is used for the default
ordered set implementation. This AVL tree implementation is reused so
that much of the existing code to implement the ETS operations can be
reused.

Tests
-----

The ETS tests in `lib/stdlib/test/ets_SUITE.erl` have been extended to
also test the new ordered_set implementation. The function
ets_SUITE:throughput_benchmark/0 has also been added to this file. This
function can be used to measure and compare the performance of the
different ETS table types and options. This function writes benchmark
data to standard output that can be visualized by the HTML page
`lib/stdlib/test/ets_SUITE_data/visualize_throughput.html`.

[1]
More Scalable Ordered Set for ETS Using Adaptation.
In Thirteenth ACM SIGPLAN workshop on Erlang (2014).
Kjell Winblad and Konstantinos Sagonas.
https://doi.org/10.1145/2633448.2633455
http://www.it.uu.se/research/group/languages/software/ca_tree/erlang_paper.pdf

[2]
On the Scalability of the Erlang Term Storage
In Twelfth ACM SIGPLAN workshop on Erlang (2013)
Kjell Winblad, David Klaftenegger and Konstantinos Sagonas
https://doi.org/10.1145/2505305.2505308
http://winsh.me/papers/erlang_workshop_2013.pdf

[3]
The stack optimization works by keeping one preallocated stack instance
in every ordered_set table. This stack is updated so that it contains
the search path in some read operations (e.g., ets:next/2). This makes
it possible for a subsequent ets:next/2 to avoid traversing some nodes
in some cases. Unfortunately, the preallocated stack needs to be flagged
so that it is not updated concurrently by several threads which cause
bad scalability.

1 files changed, 552 insertions, 362 deletions

diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c
index 2eb874b005..f643344477 100644
--- a/erts/emulator/beam/erl_db_tree.c
+++ b/erts/emulator/beam/erl_db_tree.c
@@ -48,34 +48,13 @@
 #include "erl_binary.h"
 
 #include "erl_db_tree.h"
+#include "erl_db_tree_util.h"
 
 #define GETKEY_WITH_POS(Keypos, Tplp) (*((Tplp) + Keypos))
 #define NITEMS(tb) ((int)erts_atomic_read_nob(&(tb)->common.nitems))
 
-/*
-** A stack of this size is enough for an AVL tree with more than
-** 0xFFFFFFFF elements. May be subject to change if
-** the datatype of the element counter is changed to a 64 bit integer.
-** The Maximal height of an AVL tree is calculated as:
-** h(n) <= 1.4404 * log(n + 2) - 0.328
-** Where n denotes the number of nodes, h(n) the height of the tree
-** with n nodes and log is the binary logarithm.
-*/
-
-#define STACK_NEED 50
 #define TREE_MAX_ELEMENTS 0xFFFFFFFFUL
 
-#define PUSH_NODE(Dtt, Tdt)                     \
-    ((Dtt)->array[(Dtt)->pos++] = Tdt)
-
-#define POP_NODE(Dtt)			\
-     (((Dtt)->pos) ? 			\
-      (Dtt)->array[--((Dtt)->pos)] : NULL)
-
-#define TOP_NODE(Dtt)                   \
-     ((Dtt->pos) ? 			\
-      (Dtt)->array[(Dtt)->pos - 1] : NULL)
-
 #define TOPN_NODE(Dtt, Pos)                   \
      (((Pos) < Dtt->pos) ? 			\
       (Dtt)->array[(Dtt)->pos - ((Pos) + 1)] : NULL)
@@ -89,9 +68,9 @@
 /* Obtain table static stack if available. NULL if not.
 ** Must be released with release_stack()
 */
-static DbTreeStack* get_static_stack(DbTableTree* tb)
+ERTS_INLINE static DbTreeStack* get_static_stack(DbTableTree* tb)
 {
-    if (!erts_atomic_xchg_acqb(&tb->is_stack_busy, 1)) {
+    if (tb != NULL && !erts_atomic_xchg_acqb(&tb->is_stack_busy, 1)) {
 	return &tb->static_stack;
     }
     return NULL;
@@ -100,13 +79,14 @@ static DbTreeStack* get_static_stack(DbTableTree* tb)
 /* Obtain static stack if available, otherwise empty dynamic stack.
 ** Must be released with release_stack()
 */
-static DbTreeStack* get_any_stack(DbTableTree* tb)
+static DbTreeStack* get_any_stack(DbTable* tb, DbTableTree* stack_container)
 {
     DbTreeStack* stack;
-    if (!erts_atomic_xchg_acqb(&tb->is_stack_busy, 1)) {
-	return &tb->static_stack;
+    if (stack_container != NULL &&
+        !erts_atomic_xchg_acqb(&stack_container->is_stack_busy, 1)) {
+	return &stack_container->static_stack;
     }
-    stack = erts_db_alloc(ERTS_ALC_T_DB_STK, (DbTable *) tb,
+    stack = erts_db_alloc(ERTS_ALC_T_DB_STK, tb,
 			  sizeof(DbTreeStack) + sizeof(TreeDbTerm*) * STACK_NEED);
     stack->pos = 0;
     stack->slot = 0;
@@ -114,62 +94,59 @@ static DbTreeStack* get_any_stack(DbTableTree* tb)
     return stack;
 }
 
-static void release_stack(DbTableTree* tb, DbTreeStack* stack)
+static void release_stack(DbTable* tb, DbTableTree* stack_container, DbTreeStack* stack)
 {
-    if (stack == &tb->static_stack) {
-	ASSERT(erts_atomic_read_nob(&tb->is_stack_busy) == 1);
-	erts_atomic_set_relb(&tb->is_stack_busy, 0);
+    if (stack_container != NULL && stack == &stack_container->static_stack) {
+	ASSERT(erts_atomic_read_nob(&stack_container->is_stack_busy) == 1);
+	erts_atomic_set_relb(&stack_container->is_stack_busy, 0);
     }
     else {
-	erts_db_free(ERTS_ALC_T_DB_STK, (DbTable *) tb,
+	erts_db_free(ERTS_ALC_T_DB_STK, tb,
 		     (void *) stack, sizeof(DbTreeStack) + sizeof(TreeDbTerm*) * STACK_NEED);
     }
 }
 
-static ERTS_INLINE void reset_static_stack(DbTableTree* tb)
+static ERTS_INLINE void reset_stack(DbTreeStack* stack)
 {
-    tb->static_stack.pos = 0;
-    tb->static_stack.slot = 0;
+    if (stack != NULL) {
+        stack->pos = 0;
+        stack->slot = 0;
+    }
 }
 
-static ERTS_INLINE void free_term(DbTableTree *tb, TreeDbTerm* p)
+static ERTS_INLINE void reset_static_stack(DbTableTree* tb)
 {
-    db_free_term((DbTable*)tb, p, offsetof(TreeDbTerm, dbterm));
+    if (tb != NULL) {
+        reset_stack(&tb->static_stack);
+    }
 }
 
-static ERTS_INLINE TreeDbTerm* new_dbterm(DbTableTree *tb, Eterm obj)
+static ERTS_INLINE TreeDbTerm* new_dbterm(DbTableCommon *tb, Eterm obj)
 {
     TreeDbTerm* p;
-    if (tb->common.compress) {
-	p = db_store_term_comp(&tb->common, NULL, offsetof(TreeDbTerm,dbterm), obj);
+    if (tb->compress) {
+	p = db_store_term_comp(tb, NULL, offsetof(TreeDbTerm,dbterm), obj);
     }
     else {
-	p = db_store_term(&tb->common, NULL, offsetof(TreeDbTerm,dbterm), obj);
+	p = db_store_term(tb, NULL, offsetof(TreeDbTerm,dbterm), obj);
     }
     return p;
 }
-static ERTS_INLINE TreeDbTerm* replace_dbterm(DbTableTree *tb, TreeDbTerm* old,
+static ERTS_INLINE TreeDbTerm* replace_dbterm(DbTableCommon *tb, TreeDbTerm* old,
 					      Eterm obj)
 {
     TreeDbTerm* p;
     ASSERT(old != NULL);
-    if (tb->common.compress) {
-	p = db_store_term_comp(&tb->common, &(old->dbterm), offsetof(TreeDbTerm,dbterm), obj);
+    if (tb->compress) {
+	p = db_store_term_comp(tb, &(old->dbterm), offsetof(TreeDbTerm,dbterm), obj);
     }
     else {
-	p = db_store_term(&tb->common, &(old->dbterm), offsetof(TreeDbTerm,dbterm), obj);
+	p = db_store_term(tb, &(old->dbterm), offsetof(TreeDbTerm,dbterm), obj);
     }
     return p;
 }
 
 /*
-** Some macros for "direction stacks"
-*/
-#define DIR_LEFT 0
-#define DIR_RIGHT 1
-#define DIR_END 2 
-
-/*
  * Number of records to delete before trapping.
  */
 #define DELETE_RECORD_LIMIT 12000
@@ -262,7 +239,9 @@ struct select_count_context {
  */
 struct select_delete_context {
     Process *p;
-    DbTableTree *tb;
+    DbTableCommon *tb;
+    TreeDbTerm **root;
+    DbTreeStack *stack;
     Uint accum;
     Binary *mp;
     Eterm end_condition;
@@ -277,7 +256,8 @@ struct select_delete_context {
  */
 struct select_replace_context {
     Process *p;
-    DbTableTree *tb;
+    DbTableCommon *tb;
+    TreeDbTerm **root;
     Binary *mp;
     Eterm end_condition;
     Eterm *lastobj;
@@ -292,73 +272,82 @@ typedef int (*extra_match_validator_t)(int keypos, Eterm match, Eterm guard, Ete
 /*
 ** Forward declarations 
 */
-static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key);
-static TreeDbTerm *linkout_object_tree(DbTableTree *tb, 
-				       Eterm object);
+static TreeDbTerm *linkout_tree(DbTableCommon *tb, TreeDbTerm **root,
+                                Eterm key, DbTreeStack *stack);
+static TreeDbTerm *linkout_object_tree(DbTableCommon *tb,  TreeDbTerm **root,
+				       Eterm object, DbTableTree *stack);
 static SWord do_free_tree_continue(DbTableTree *tb, SWord reds);
-static void free_term(DbTableTree *tb, TreeDbTerm* p);
-static int balance_left(TreeDbTerm **this); 
-static int balance_right(TreeDbTerm **this); 
+static void free_term(DbTable *tb, TreeDbTerm* p);
+int tree_balance_left(TreeDbTerm **this); 
+int tree_balance_right(TreeDbTerm **this); 
 static int delsub(TreeDbTerm **this); 
-static TreeDbTerm *slot_search(Process *p, DbTableTree *tb, Sint slot);
-static TreeDbTerm *find_node(DbTableTree *tb, Eterm key);
-static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key);
-static TreeDbTerm **find_ptr(DbTableTree *tb, DbTreeStack*, TreeDbTerm *this);
-static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack*, Eterm key);
-static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack*, Eterm key);
-static TreeDbTerm *find_next_from_pb_key(DbTableTree *tb, DbTreeStack*,
-					 Eterm key);
-static TreeDbTerm *find_prev_from_pb_key(DbTableTree *tb, DbTreeStack*,
-					 Eterm key);
-static void traverse_backwards(DbTableTree *tb,
+static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root, Sint slot,
+                               DbTable *tb, DbTableTree *stack_container);
+static TreeDbTerm *find_node(DbTableCommon *tb, TreeDbTerm *root,
+                             Eterm key, DbTableTree *stack_container);
+static TreeDbTerm **find_node2(DbTableCommon *tb, TreeDbTerm **root, Eterm key);
+static TreeDbTerm **find_ptr(DbTableCommon *tb, TreeDbTerm **root,
+                             DbTreeStack *stack, TreeDbTerm *this);
+static TreeDbTerm *find_next(DbTableCommon *tb, TreeDbTerm *root,
+                             DbTreeStack* stack, Eterm key);
+static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root,
+                             DbTreeStack* stack, Eterm key);
+static TreeDbTerm *find_next_from_pb_key(DbTableCommon *tb, TreeDbTerm *root,
+                                         DbTreeStack* stack, Eterm key);
+static TreeDbTerm *find_prev_from_pb_key(DbTableCommon *tb, TreeDbTerm *root,
+                                         DbTreeStack* stack, Eterm key);
+static void traverse_backwards(DbTableCommon *tb,
+                               TreeDbTerm **root,
 			       DbTreeStack*,
 			       Eterm lastkey,
-			       int (*doit)(DbTableTree *tb,
+			       int (*doit)(DbTableCommon *,
 					   TreeDbTerm *,
 					   void *,
 					   int),
 			       void *context); 
-static void traverse_forward(DbTableTree *tb,
+static void traverse_forward(DbTableCommon *tb,
+                             TreeDbTerm **root,
 			     DbTreeStack*,
 			     Eterm lastkey,
-			     int (*doit)(DbTableTree *tb,
+			     int (*doit)(DbTableCommon *tb,
 					 TreeDbTerm *,
 					 void *,
 					 int),
 			     void *context);
-static void traverse_update_backwards(DbTableTree *tb,
+static void traverse_update_backwards(DbTableCommon *tb,
+                                      TreeDbTerm **root,
                                       DbTreeStack*,
                                       Eterm lastkey,
-                                      int (*doit)(DbTableTree *tb,
+                                      int (*doit)(DbTableCommon *tb,
                                                   TreeDbTerm **, // out
                                                   void *,
                                                   int),
                                       void *context);
-static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm ***ret,
-		     Eterm *partly_bound_key);
+static int key_given(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern,
+                     TreeDbTerm ***ret, Eterm *partly_bound);
 static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key);
 static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done);
 
-static int analyze_pattern(DbTableTree *tb, Eterm pattern, 
+static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, 
                            extra_match_validator_t extra_validator, /* Optional callback */
                            struct mp_info *mpi);
-static int doit_select(DbTableTree *tb,
+static int doit_select(DbTableCommon *tb,
 		       TreeDbTerm *this,
 		       void *ptr,
 		       int forward);
-static int doit_select_count(DbTableTree *tb,
+static int doit_select_count(DbTableCommon *tb,
 			     TreeDbTerm *this,
 			     void *ptr,
 			     int forward);
-static int doit_select_chunk(DbTableTree *tb,
+static int doit_select_chunk(DbTableCommon *tb,
 			     TreeDbTerm *this,
 			     void *ptr,
 			     int forward);
-static int doit_select_delete(DbTableTree *tb,
+static int doit_select_delete(DbTableCommon *tb,
 			      TreeDbTerm *this,
 			      void *ptr,
 			      int forward);
-static int doit_select_replace(DbTableTree *tb,
+static int doit_select_replace(DbTableCommon *tb,
                                TreeDbTerm **this_ptr,
                                void *ptr,
                                int forward);
@@ -508,18 +497,18 @@ int db_create_tree(Process *p, DbTable *tbl)
     return DB_ERROR_NONE;
 }
 
-static int db_first_tree(Process *p, DbTable *tbl, Eterm *ret)
+int db_first_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root,
+                         Eterm *ret, DbTableTree *stack_container)
 {
-    DbTableTree *tb = &tbl->tree;
     DbTreeStack* stack;
     TreeDbTerm *this;
 
-    if (( this = tb->root ) == NULL) {
+    if (( this = root ) == NULL) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
     }
     /* Walk down the tree to the left */
-    if ((stack = get_static_stack(tb)) != NULL) {
+    if ((stack = get_static_stack(stack_container)) != NULL) {
 	stack->pos = stack->slot = 0;
     }
     while (this->left != NULL) {
@@ -529,23 +518,27 @@ static int db_first_tree(Process *p, DbTable *tbl, Eterm *ret)
     if (stack) {
 	PUSH_NODE(stack, this);
 	stack->slot = 1;
-	release_stack(tb,stack);
+	release_stack(tbl,stack_container,stack);
     }
     *ret = db_copy_key(p, tbl, &this->dbterm);
     return DB_ERROR_NONE;
 }
 
-static int db_next_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+static int db_first_tree(Process *p, DbTable *tbl, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
-    DbTreeStack* stack;
+    return db_first_tree_common(p, tbl, tb->root, ret, tb);
+}
+
+int db_next_tree_common(Process *p, DbTable *tbl,
+                        TreeDbTerm *root, Eterm key,
+                        Eterm *ret, DbTreeStack* stack)
+{
     TreeDbTerm *this;
 
     if (is_atom(key) && key == am_EOT)
 	return DB_ERROR_BADKEY;
-    stack = get_any_stack(tb);
-    this = find_next(tb, stack, key);
-    release_stack(tb,stack);
+    this = find_next(&tbl->common, root, stack, key);
     if (this == NULL) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
@@ -554,18 +547,27 @@ static int db_next_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
     return DB_ERROR_NONE;
 }
 
-static int db_last_tree(Process *p, DbTable *tbl, Eterm *ret)
+static int db_next_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    DbTreeStack* stack = get_any_stack(tbl, tb);
+    int ret_val = db_next_tree_common(p, tbl, tb->root, key, ret, stack);
+    release_stack(tbl,tb,stack);
+    return ret_val;
+}
+
+int db_last_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root,
+                        Eterm *ret, DbTableTree *stack_container)
+{
     TreeDbTerm *this;
     DbTreeStack* stack;
 
-    if (( this = tb->root ) == NULL) {
+    if (( this = root ) == NULL) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
     }
     /* Walk down the tree to the right */
-    if ((stack = get_static_stack(tb)) != NULL) {
+    if ((stack = get_static_stack(stack_container)) != NULL) {
 	stack->pos = stack->slot = 0;
     }    
     while (this->right != NULL) {
@@ -574,24 +576,27 @@ static int db_last_tree(Process *p, DbTable *tbl, Eterm *ret)
     }
     if (stack) {
 	PUSH_NODE(stack, this);
-	stack->slot = NITEMS(tb);
-	release_stack(tb,stack);
+	stack->slot = NITEMS(tbl);
+	release_stack(tbl,stack_container,stack);
     }
     *ret = db_copy_key(p, tbl, &this->dbterm);
     return DB_ERROR_NONE;
 }
 
-static int db_prev_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+static int db_last_tree(Process *p, DbTable *tbl, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_last_tree_common(p, tbl, tb->root, ret, tb);
+}
+
+int db_prev_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm key,
+                 Eterm *ret, DbTreeStack* stack)
+{
     TreeDbTerm *this;
-    DbTreeStack* stack;
 
     if (is_atom(key) && key == am_EOT)
 	return DB_ERROR_BADKEY;
-    stack = get_any_stack(tb);
-    this = find_prev(tb, stack, key);
-    release_stack(tb,stack);
+    this = find_prev(&tbl->common, root, stack, key);
     if (this == NULL) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
@@ -600,25 +605,30 @@ static int db_prev_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
     return DB_ERROR_NONE;
 }
 
-static ERTS_INLINE Sint cmp_key(DbTableTree* tb, Eterm key, TreeDbTerm* obj) {
-    return CMP(key, GETKEY(tb,obj->dbterm.tpl));
+static int db_prev_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+{
+    DbTableTree *tb = &tbl->tree;
+    DbTreeStack* stack = get_any_stack(tbl, tb);
+    int res = db_prev_tree_common(p, tbl, tb->root, key, ret, stack);
+    release_stack(tbl,tb,stack);
+    return res;
 }
 
-static ERTS_INLINE int cmp_key_eq(DbTableTree* tb, Eterm key, TreeDbTerm* obj) {
+static ERTS_INLINE int cmp_key_eq(DbTableCommon* tb, Eterm key, TreeDbTerm* obj) {
     Eterm obj_key = GETKEY(tb,obj->dbterm.tpl);
     return is_same(key, obj_key) || CMP(key, obj_key) == 0;
 }
 
-static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
+int db_put_tree_common(DbTableCommon *tb, TreeDbTerm **root, Eterm obj,
+                       int key_clash_fail, DbTableTree *stack_container)
 {
-    DbTableTree *tb = &tbl->tree;
     /* Non recursive insertion in AVL tree, building our own stack */
     TreeDbTerm **tstack[STACK_NEED];
     int tpos = 0;
     int dstack[STACK_NEED+1];
     int dpos = 0;
     int state = 0;
-    TreeDbTerm **this = &tb->root;
+    TreeDbTerm **this = root;
     Sint c;
     Eterm key;
     int dir;
@@ -626,14 +636,14 @@ static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
 
     key = GETKEY(tb, tuple_val(obj));
 
-    reset_static_stack(tb);
+    reset_static_stack(stack_container);
 
     dstack[dpos++] = DIR_END;
     for (;;)
 	if (!*this) { /* Found our place */
 	    state = 1;
-	    if (erts_atomic_inc_read_nob(&tb->common.nitems) >= TREE_MAX_ELEMENTS) {
-		erts_atomic_dec_nob(&tb->common.nitems);
+	    if (erts_atomic_inc_read_nob(&tb->nitems) >= TREE_MAX_ELEMENTS) {
+		erts_atomic_dec_nob(&tb->nitems);
 		return DB_ERROR_SYSRES;
 	    }
 	    *this = new_dbterm(tb, obj);
@@ -724,9 +734,15 @@ static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
     return DB_ERROR_NONE;
 }
 
-static int db_get_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_put_tree_common(&tb->common, &tb->root, obj, key_clash_fail, tb);
+}
+
+int db_get_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm *root, Eterm key,
+                       Eterm *ret, DbTableTree *stack_container)
+{
     Eterm copy;
     Eterm *hp, *hend;
     TreeDbTerm *this;
@@ -737,13 +753,13 @@ static int db_get_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
      * The list created around it is purely for interface conformance.
      */
     
-    this = find_node(tb,key);
+    this = find_node(tb,root,key,stack_container);
     if (this == NULL) {
 	*ret = NIL;
     } else {
 	hp = HAlloc(p, this->dbterm.size + 2);
 	hend = hp + this->dbterm.size + 2;
-	copy = db_copy_object_from_ets(&tb->common, &this->dbterm, &hp, &MSO(p));
+	copy = db_copy_object_from_ets(tb, &this->dbterm, &hp, &MSO(p));
 	*ret = CONS(hp, copy, NIL);
 	hp += 2;
 	HRelease(p,hend,hp);
@@ -751,18 +767,28 @@ static int db_get_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
     return DB_ERROR_NONE;
 }
 
-static int db_member_tree(DbTable *tbl, Eterm key, Eterm *ret)
+static int db_get_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_get_tree_common(p, &tb->common, tb->root, key, ret, tb);
+}
 
-    *ret = (find_node(tb,key) == NULL) ? am_false : am_true;
+int db_member_tree_common(DbTableCommon *tb, TreeDbTerm *root, Eterm key, Eterm *ret,
+                          DbTableTree *stack_container)
+{
+    *ret = (find_node(tb,root,key,stack_container) == NULL) ? am_false : am_true;
     return DB_ERROR_NONE;
 }
 
-static int db_get_element_tree(Process *p, DbTable *tbl,
-			       Eterm key, int ndex, Eterm *ret)
+static int db_member_tree(DbTable *tbl, Eterm key, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_member_tree_common(&tb->common, tb->root, key, ret, tb);
+}
+
+int db_get_element_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm *root, Eterm key,
+                               int ndex, Eterm *ret, DbTableTree *stack_container)
+{
     /*
      * Look the node up:
      */
@@ -776,49 +802,68 @@ static int db_get_element_tree(Process *p, DbTable *tbl,
      * around the element here either.
      */
     
-    this = find_node(tb,key);
+    this = find_node(tb,root,key,stack_container);
     if (this == NULL) {
 	return DB_ERROR_BADKEY;
     } else {
 	if (ndex > arityval(this->dbterm.tpl[0])) {
 	    return DB_ERROR_BADPARAM;
 	}
-	*ret = db_copy_element_from_ets(&tb->common, p, &this->dbterm, ndex, &hp, 0);
+	*ret = db_copy_element_from_ets(tb, p, &this->dbterm, ndex, &hp, 0);
     }
     return DB_ERROR_NONE;
 }
 
-static int db_erase_tree(DbTable *tbl, Eterm key, Eterm *ret)
+static int db_get_element_tree(Process *p, DbTable *tbl,
+			       Eterm key, int ndex, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_get_element_tree_common(p, &tb->common, tb->root, key,
+                                      ndex, ret, tb);
+}
+
+int db_erase_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm key, Eterm *ret,
+                         DbTreeStack *stack /* NULL if no static stack */)
+{
     TreeDbTerm *res;
 
     *ret = am_true;
 
-    if ((res = linkout_tree(tb, key)) != NULL) {
-	free_term(tb, res);
+    if ((res = linkout_tree(&tbl->common, root,key, stack)) != NULL) {
+	free_term(tbl, res);
     }
     return DB_ERROR_NONE;
 }
 
-static int db_erase_object_tree(DbTable *tbl, Eterm object, Eterm *ret)
+static int db_erase_tree(DbTable *tbl, Eterm key, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_erase_tree_common(tbl, &tb->root, key, ret, &tb->static_stack);
+}
+
+int db_erase_object_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm object,
+                                Eterm *ret, DbTableTree *stack_container)
+{
     TreeDbTerm *res;
 
     *ret = am_true;
 
-    if ((res = linkout_object_tree(tb, object)) != NULL) {
-	free_term(tb, res);
+    if ((res = linkout_object_tree(&tbl->common, root, object, stack_container)) != NULL) {
+	free_term(tbl, res);
     }
     return DB_ERROR_NONE;
 }
 
-
-static int db_slot_tree(Process *p, DbTable *tbl, 
-			Eterm slot_term, Eterm *ret)
+static int db_erase_object_tree(DbTable *tbl, Eterm object, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return  db_erase_object_tree_common(tbl, &tb->root, object, ret, tb);
+}
+
+int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root,
+                        Eterm slot_term, Eterm *ret,
+                        DbTableTree *stack_container)
+{
     Sint slot;
     TreeDbTerm *st;
     Eterm *hp, *hend;
@@ -834,10 +879,10 @@ static int db_slot_tree(Process *p, DbTable *tbl,
 
     if (is_not_small(slot_term) ||
 	((slot = signed_val(slot_term)) < 0) ||
-	(slot > NITEMS(tb)))
+	(slot > NITEMS(tbl)))
 	return DB_ERROR_BADPARAM;
 
-    if (slot == NITEMS(tb)) {
+    if (slot == NITEMS(tbl)) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
     }
@@ -847,20 +892,27 @@ static int db_slot_tree(Process *p, DbTable *tbl,
      * are counted from 1 and up.
      */
     ++slot;
-    st = slot_search(p, tb, slot); 
+    st = slot_search(p, root, slot, tbl, stack_container); 
     if (st == NULL) {
 	*ret = am_false;
 	return DB_ERROR_UNSPEC;
     }
     hp = HAlloc(p, st->dbterm.size + 2);
     hend = hp + st->dbterm.size + 2;
-    copy = db_copy_object_from_ets(&tb->common, &st->dbterm, &hp, &MSO(p));
+    copy = db_copy_object_from_ets(&tbl->common, &st->dbterm, &hp, &MSO(p));
     *ret = CONS(hp, copy, NIL);
     hp += 2;
     HRelease(p,hend,hp);
     return DB_ERROR_NONE;
 }
 
+static int db_slot_tree(Process *p, DbTable *tbl, 
+			Eterm slot_term, Eterm *ret)
+{
+    DbTableTree *tb = &tbl->tree;
+    return db_slot_tree_common(p, tbl, tb->root, slot_term, ret, tb);
+}
+
 
 
 static BIF_RETTYPE ets_select_reverse(BIF_ALIST_3)
@@ -926,19 +978,14 @@ static BIF_RETTYPE bif_trap3(Export *bif,
 {
     BIF_TRAP3(bif, p, p1, p2, p3);
 }
-    
-/*
-** This is called either when the select bif traps or when ets:select/1 
-** is called. It does mostly the same as db_select_tree and may in either case
-** trap to itself again (via the ets:select/1 bif).
-** Note that this is common for db_select_tree and db_select_chunk_tree.
-*/
-static int db_select_continue_tree(Process *p, 
-				   DbTable *tbl,
-				   Eterm continuation,
-				   Eterm *ret)
+
+int db_select_continue_tree_common(Process *p, 
+                                   DbTableCommon *tb,
+                                   TreeDbTerm **root,
+                                   Eterm continuation,
+                                   Eterm *ret,
+                                   DbTableTree *stack_container)
 {
-    DbTableTree *tb = &tbl->tree;
     DbTreeStack* stack;
     struct select_context sc;
     unsigned sz;
@@ -980,26 +1027,26 @@ static int db_select_continue_tree(Process *p,
     sc.end_condition = NIL;
     sc.lastobj = NULL;
     sc.max = 1000;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     sc.chunk_size = chunk_size;
     reverse = unsigned_val(tptr[7]);
     sc.got = signed_val(tptr[8]);
 
-    stack = get_any_stack(tb);
+    stack = get_any_stack((DbTable*)tb, stack_container);
     if (chunk_size) {
 	if (reverse) {
-	    traverse_backwards(tb, stack, lastkey, &doit_select_chunk, &sc);
+	    traverse_backwards(tb, root, stack, lastkey, &doit_select_chunk, &sc);
 	} else {
-	    traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc);
+	    traverse_forward(tb, root, stack, lastkey, &doit_select_chunk, &sc);
 	}
     } else {
 	if (reverse) {
-	    traverse_forward(tb, stack, lastkey, &doit_select, &sc);
+	    traverse_forward(tb, root, stack, lastkey, &doit_select, &sc);
 	} else {
-	    traverse_backwards(tb, stack, lastkey, &doit_select, &sc);
+	    traverse_backwards(tb, root, stack, lastkey, &doit_select, &sc);
 	}
     }
-    release_stack(tb,stack);
+    release_stack((DbTable*)tb,stack_container,stack);
 
     BUMP_REDS(p, 1000 - sc.max);
 
@@ -1082,13 +1129,28 @@ static int db_select_continue_tree(Process *p,
 
 #undef RET_TO_BIF
 }
+    
+/*
+** This is called either when the select bif traps or when ets:select/1 
+** is called. It does mostly the same as db_select_tree and may in either case
+** trap to itself again (via the ets:select/1 bif).
+** Note that this is common for db_select_tree and db_select_chunk_tree.
+*/
+static int db_select_continue_tree(Process *p, 
+				   DbTable *tbl,
+				   Eterm continuation,
+				   Eterm *ret)
+{
+    DbTableTree *tb = &tbl->tree;
+    return db_select_continue_tree_common(p, &tb->common, &tb->root,
+                                          continuation, ret, tb);
+}
 
-
-static int db_select_tree(Process *p, DbTable *tbl, Eterm tid,
-			  Eterm pattern, int reverse, Eterm *ret)
+int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root,
+                          Eterm tid, Eterm pattern, int reverse, Eterm *ret,
+                          DbTableTree *stack_container)
 {
     /* Strategy: Traverse backwards to build resulting list from tail to head */
-    DbTableTree *tb = &tbl->tree;
     DbTreeStack* stack;
     struct select_context sc;
     struct mp_info mpi;
@@ -1117,11 +1179,11 @@ static int db_select_tree(Process *p, DbTable *tbl, Eterm tid,
     sc.p = p;
     sc.max = 1000; 
     sc.end_condition = NIL;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     sc.got = 0;
     sc.chunk_size = 0;
 
-    if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
+    if ((errcode = analyze_pattern(tb, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
 	RET_TO_BIF(NIL,errcode);
     }
 
@@ -1138,25 +1200,25 @@ static int db_select_tree(Process *p, DbTable *tbl, Eterm tid,
 	RET_TO_BIF(sc.accum,DB_ERROR_NONE);
     }
 
-    stack = get_any_stack(tb);
+    stack = get_any_stack((DbTable*)tb,stack_container);
     if (reverse) {
 	if (mpi.some_limitation) {
-	    if ((this = find_prev_from_pb_key(tb, stack, mpi.least)) != NULL) {
+	    if ((this = find_prev_from_pb_key(tb, *root, stack, mpi.least)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
 	    }
 	    sc.end_condition = mpi.most;
 	}
-	traverse_forward(tb, stack, lastkey, &doit_select, &sc);
+	traverse_forward(tb, root, stack, lastkey, &doit_select, &sc);
     } else {
 	if (mpi.some_limitation) {
-	    if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
+	    if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
 	    }
 	    sc.end_condition = mpi.least;
 	}
-	traverse_backwards(tb, stack, lastkey, &doit_select, &sc);
+	traverse_backwards(tb, root, stack, lastkey, &doit_select, &sc);
     }
-    release_stack(tb,stack);
+    release_stack((DbTable*)tb,stack_container,stack);
 #ifdef HARDDEBUG
 	erts_fprintf(stderr,"Least: %T\n", mpi.least);
 	erts_fprintf(stderr,"Most: %T\n", mpi.most);
@@ -1192,16 +1254,21 @@ static int db_select_tree(Process *p, DbTable *tbl, Eterm tid,
 
 }
 
-    
-/*
-** This is called either when the select_count bif traps.
-*/
-static int db_select_count_continue_tree(Process *p, 
-					 DbTable *tbl,
-					 Eterm continuation,
-					 Eterm *ret)
+static int db_select_tree(Process *p, DbTable *tbl, Eterm tid,
+			  Eterm pattern, int reverse, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_tree_common(p, &tb->common, &tb->root, tid,
+                                 pattern, reverse, ret, tb);
+}
+
+int db_select_count_continue_tree_common(Process *p, 
+                                         DbTableCommon *tb,
+                                         TreeDbTerm **root,
+                                         Eterm continuation,
+                                         Eterm *ret,
+                                         DbTableTree *stack_container)
+{
     DbTreeStack* stack;
     struct select_count_context sc;
     unsigned sz;
@@ -1238,16 +1305,16 @@ static int db_select_count_continue_tree(Process *p,
     sc.end_condition = NIL;
     sc.lastobj = NULL;
     sc.max = 1000;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     if (is_big(tptr[5])) {
 	sc.got = big_to_uint32(tptr[5]);
     } else {
 	sc.got = unsigned_val(tptr[5]);
     }
 
-    stack = get_any_stack(tb);
-    traverse_backwards(tb, stack, lastkey, &doit_select_count, &sc);
-    release_stack(tb,stack);
+    stack = get_any_stack((DbTable*)tb, stack_container);
+    traverse_backwards(tb, root, stack, lastkey, &doit_select_count, &sc);
+    release_stack((DbTable*)tb,stack_container,stack);
 
     BUMP_REDS(p, 1000 - sc.max);
 
@@ -1285,11 +1352,24 @@ static int db_select_count_continue_tree(Process *p,
 #undef RET_TO_BIF
 }
 
-
-static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid,
-				Eterm pattern, Eterm *ret)
+/*
+** This is called either when the select_count bif traps.
+*/
+static int db_select_count_continue_tree(Process *p, 
+                                         DbTable *tbl,
+                                         Eterm continuation,
+                                         Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_count_continue_tree_common(p, &tb->common, &tb->root,
+                                                continuation, ret, tb);    
+}
+
+
+int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root,
+                                Eterm tid, Eterm pattern, Eterm *ret,
+                                DbTableTree *stack_container)
+{
     DbTreeStack* stack;
     struct select_count_context sc;
     struct mp_info mpi;
@@ -1318,10 +1398,10 @@ static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid,
     sc.p = p;
     sc.max = 1000; 
     sc.end_condition = NIL;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     sc.got = 0;
 
-    if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
+    if ((errcode = analyze_pattern(tb, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
 	RET_TO_BIF(NIL,errcode);
     }
 
@@ -1338,16 +1418,16 @@ static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid,
 	RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE);
     }
 
-    stack = get_any_stack(tb);
+    stack = get_any_stack((DbTable*)tb, stack_container);
     if (mpi.some_limitation) {
-	if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
+	if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) {
 	    lastkey = GETKEY(tb, this->dbterm.tpl);
 	}
 	sc.end_condition = mpi.least;
     }
     
-    traverse_backwards(tb, stack, lastkey, &doit_select_count, &sc);
-    release_stack(tb,stack);
+    traverse_backwards(tb, root, stack, lastkey, &doit_select_count, &sc);
+    release_stack((DbTable*)tb,stack_container,stack);
     BUMP_REDS(p, 1000 - sc.max);
     if (sc.max > 0) {
 	RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE);
@@ -1383,12 +1463,20 @@ static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid,
 
 }
 
-static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid,
-				Eterm pattern, Sint chunk_size,
-				int reverse,
-				Eterm *ret)
+static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid,
+                                Eterm pattern, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_count_tree_common(p, &tb->common, &tb->root,
+                                       tid, pattern, ret, tb);
+}
+
+
+int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root,
+                                Eterm tid, Eterm pattern, Sint chunk_size,
+                                int reverse, Eterm *ret,
+                                DbTableTree *stack_container)
+{
     DbTreeStack* stack;
     struct select_context sc;
     struct mp_info mpi;
@@ -1417,11 +1505,11 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid,
     sc.p = p;
     sc.max = 1000; 
     sc.end_condition = NIL;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     sc.got = 0;
     sc.chunk_size = chunk_size;
 
-    if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
+    if ((errcode = analyze_pattern(tb, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
 	RET_TO_BIF(NIL,errcode);
     }
 
@@ -1443,25 +1531,25 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid,
 	}
     }
 
-    stack = get_any_stack(tb);
+    stack = get_any_stack((DbTable*)tb,stack_container);
     if (reverse) {
 	if (mpi.some_limitation) {
-	    if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
+	    if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
 	    }
 	    sc.end_condition = mpi.least;
 	}
-	traverse_backwards(tb, stack, lastkey, &doit_select_chunk, &sc);
+	traverse_backwards(tb, root, stack, lastkey, &doit_select_chunk, &sc);
     } else {
 	if (mpi.some_limitation) {
-	    if ((this = find_prev_from_pb_key(tb, stack, mpi.least)) != NULL) {
+	    if ((this = find_prev_from_pb_key(tb, *root, stack, mpi.least)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
 	    }
 	    sc.end_condition = mpi.most;
 	}
-	traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc);
+	traverse_forward(tb, root, stack, lastkey, &doit_select_chunk, &sc);
     }
-    release_stack(tb,stack);
+    release_stack((DbTable*)tb,stack_container,stack);
 
     BUMP_REDS(p, 1000 - sc.max);
     if (sc.max > 0 || sc.got == chunk_size) {
@@ -1530,15 +1618,25 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid,
 
 }
 
-/*
-** This is called when select_delete traps
-*/
-static int db_select_delete_continue_tree(Process *p, 
-					  DbTable *tbl,
-					  Eterm continuation,
-					  Eterm *ret)
+static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid,
+                                Eterm pattern, Sint chunk_size,
+                                int reverse,
+                                Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_chunk_tree_common(p, &tb->common, &tb->root,
+                                       tid, pattern, chunk_size,
+                                       reverse, ret, tb);
+}
+
+
+int db_select_delete_continue_tree_common(Process *p,
+                                          DbTable *tbl,
+                                          TreeDbTerm **root,
+                                          Eterm continuation,
+                                          Eterm *ret,
+                                          DbTreeStack* stack)
+{
     struct select_delete_context sc;
     unsigned sz;
     Eterm *hp; 
@@ -1552,7 +1650,7 @@ static int db_select_delete_continue_tree(Process *p,
 
 #define RET_TO_BIF(Term, State) do { 		\
 	if (sc.erase_lastterm) {		\
-	    free_term(tb, sc.lastterm);		\
+	    free_term(tbl, sc.lastterm);		\
 	}					\
 	*ret = (Term); 				\
 	return State; 				\
@@ -1571,7 +1669,9 @@ static int db_select_delete_continue_tree(Process *p,
 
     mp = erts_db_get_match_prog_binary_unchecked(tptr[4]);
     sc.p = p;
-    sc.tb = tb;
+    sc.tb = &tbl->common;
+    sc.root = root;
+    sc.stack = stack;
     if (is_big(tptr[5])) {
 	sc.accum = big_to_uint32(tptr[5]);
     } else {
@@ -1580,17 +1680,16 @@ static int db_select_delete_continue_tree(Process *p,
     sc.mp = mp;
     sc.end_condition = NIL;
     sc.max = 1000;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tbl->common.keypos;
 
-    ASSERT(!erts_atomic_read_nob(&tb->is_stack_busy));
-    traverse_backwards(tb, &tb->static_stack, lastkey, &doit_select_delete, &sc);
+    traverse_backwards(&tbl->common, root, stack, lastkey, &doit_select_delete, &sc);
 
     BUMP_REDS(p, 1000 - sc.max);
 
     if (sc.max > 0) {
 	RET_TO_BIF(erts_make_integer(sc.accum, p), DB_ERROR_NONE);
     }	
-    key = GETKEY(tb, (sc.lastterm)->dbterm.tpl);
+    key = GETKEY(&tbl->common, (sc.lastterm)->dbterm.tpl);
     if (end_condition != NIL && 
 	cmp_partly_bound(end_condition,key) > 0) { /* done anyway */
 	RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE);
@@ -1620,10 +1719,24 @@ static int db_select_delete_continue_tree(Process *p,
 #undef RET_TO_BIF
 }
 
-static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
-				 Eterm pattern, Eterm *ret)
+static int db_select_delete_continue_tree(Process *p, 
+					  DbTable *tbl,
+					  Eterm continuation,
+					  Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    ASSERT(!erts_atomic_read_nob(&tb->is_stack_busy));
+    return db_select_delete_continue_tree_common(p, tbl, &tb->root,
+                                                 continuation, ret,
+                                                 &tb->static_stack);
+}
+
+int db_select_delete_tree_common(Process *p, DbTable *tbl,
+                                 TreeDbTerm **root,
+                                 Eterm tid, Eterm pattern,
+                                 Eterm *ret,
+                                 DbTreeStack* stack)
+{
     struct select_delete_context sc;
     struct mp_info mpi;
     Eterm lastkey = THE_NON_VALUE;
@@ -1641,7 +1754,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
 	    erts_bin_free(mpi.mp);       	\
 	}					\
 	if (sc.erase_lastterm) {                \
-	    free_term(tb, sc.lastterm);         \
+	    free_term(tbl, sc.lastterm);         \
 	}                                       \
 	*ret = (Term); 				\
 	return RetVal; 			        \
@@ -1655,10 +1768,12 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
     sc.p = p;
     sc.max = 1000; 
     sc.end_condition = NIL;
-    sc.keypos = tb->common.keypos;
-    sc.tb = tb;
+    sc.keypos = tbl->common.keypos;
+    sc.tb = &tbl->common;
+    sc.root = root;
+    sc.stack = stack;
     
-    if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
+    if ((errcode = analyze_pattern(&tbl->common, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) {
 	RET_TO_BIF(0,errcode);
     }
 
@@ -1671,26 +1786,26 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
 
     if (!mpi.got_partial && mpi.some_limitation && 
 	CMP_EQ(mpi.least,mpi.most)) {
-	doit_select_delete(tb,*(mpi.save_term),&sc, 0 /* direction doesn't
+	doit_select_delete(&tbl->common,*(mpi.save_term),&sc, 0 /* direction doesn't
 						      matter */);
 	RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE);
     }
 
     if (mpi.some_limitation) {
-	if ((this = find_next_from_pb_key(tb, &tb->static_stack, mpi.most)) != NULL) {
-	    lastkey = GETKEY(tb, this->dbterm.tpl);
+	if ((this = find_next_from_pb_key(&tbl->common, *root, stack, mpi.most)) != NULL) {
+	    lastkey = GETKEY(&tbl->common, this->dbterm.tpl);
 	}
 	sc.end_condition = mpi.least;
     }
 
-    traverse_backwards(tb, &tb->static_stack, lastkey, &doit_select_delete, &sc);
+    traverse_backwards(&tbl->common, root, stack, lastkey, &doit_select_delete, &sc);
     BUMP_REDS(p, 1000 - sc.max);
 
     if (sc.max > 0) {
 	RET_TO_BIF(erts_make_integer(sc.accum,p), DB_ERROR_NONE);
     }
 
-    key = GETKEY(tb, (sc.lastterm)->dbterm.tpl);
+    key = GETKEY(&tbl->common, (sc.lastterm)->dbterm.tpl);
     sz = size_object(key);
     if (IS_USMALL(0, sc.accum)) {
 	hp = HAlloc(p, sz + ERTS_MAGIC_REF_THING_SIZE + 6);
@@ -1714,7 +1829,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
 
     /* Don't free mpi.mp, so don't use macro */
     if (sc.erase_lastterm) {
-	free_term(tb, sc.lastterm);
+	free_term(tbl, sc.lastterm);
     }
     *ret = bif_trap1(&ets_select_delete_continue_exp, p, continuation); 
     return DB_ERROR_NONE;
@@ -1723,12 +1838,21 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
 
 }
 
-static int db_select_replace_continue_tree(Process *p,
-                                           DbTable *tbl,
-                                           Eterm continuation,
-                                           Eterm *ret)
+static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid,
+				 Eterm pattern, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_delete_tree_common(p, tbl, &tb->root, tid, pattern, ret,
+                                        &tb->static_stack);
+}
+
+int db_select_replace_continue_tree_common(Process *p,
+                                           DbTableCommon *tb,
+                                           TreeDbTerm **root,
+                                           Eterm continuation,
+                                           Eterm *ret,
+                                           DbTableTree *stack_container)
+{
     DbTreeStack* stack;
     struct select_replace_context sc;
     unsigned sz;
@@ -1764,7 +1888,7 @@ static int db_select_replace_continue_tree(Process *p,
     sc.end_condition = NIL;
     sc.lastobj = NULL;
     sc.max = 1000;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     if (is_big(tptr[5])) {
         sc.replaced = big_to_uint32(tptr[5]);
     } else {
@@ -1772,9 +1896,9 @@ static int db_select_replace_continue_tree(Process *p,
     }
     prev_replaced = sc.replaced;
 
-    stack = get_any_stack(tb);
-    traverse_update_backwards(tb, stack, lastkey, &doit_select_replace, &sc);
-    release_stack(tb,stack);
+    stack = get_any_stack((DbTable*)tb,stack_container);
+    traverse_update_backwards(tb, root, stack, lastkey, &doit_select_replace, &sc);
+    release_stack((DbTable*)tb,stack_container,stack);
 
     // the more objects we've replaced, the more reductions we've consumed
     BUMP_REDS(p, MIN(2000, (1000 - sc.max) + (sc.replaced - prev_replaced)));
@@ -1813,10 +1937,20 @@ static int db_select_replace_continue_tree(Process *p,
 #undef RET_TO_BIF
 }
 
-static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid,
-                                  Eterm pattern, Eterm *ret)
+static int db_select_replace_continue_tree(Process *p,
+                                           DbTable *tbl,
+                                           Eterm continuation,
+                                           Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_replace_continue_tree_common(p, &tb->common, &tb->root,
+                                                  continuation, ret, tb);
+}
+
+int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root,
+                                  Eterm tid, Eterm pattern, Eterm *ret,
+                                  DbTableTree *stack_container)
+{
     DbTreeStack* stack;
     struct select_replace_context sc;
     struct mp_info mpi;
@@ -1844,12 +1978,13 @@ static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid,
     sc.lastobj = NULL;
     sc.p = p;
     sc.tb = tb;
+    sc.root = root;
     sc.max = 1000;
     sc.end_condition = NIL;
-    sc.keypos = tb->common.keypos;
+    sc.keypos = tb->keypos;
     sc.replaced = 0;
 
-    if ((errcode = analyze_pattern(tb, pattern, db_match_keeps_key, &mpi)) != DB_ERROR_NONE) {
+    if ((errcode = analyze_pattern(tb, root, pattern, db_match_keeps_key, &mpi)) != DB_ERROR_NONE) {
         RET_TO_BIF(NIL,errcode);
     }
 
@@ -1860,7 +1995,7 @@ static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid,
 
     sc.mp = mpi.mp;
 
-    stack = get_static_stack(tb);
+    stack = get_static_stack(stack_container);
     if (!mpi.got_partial && mpi.some_limitation &&
             CMP_EQ(mpi.least,mpi.most)) {
         TreeDbTerm* term = *(mpi.save_term);
@@ -1869,23 +2004,23 @@ static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid,
             if (TOP_NODE(stack) == term)
                 // throw away potentially invalid reference
                 REPLACE_TOP_NODE(stack, *(mpi.save_term));
-            release_stack(tb, stack);
+            release_stack((DbTable*)tb,stack_container, stack);
         }
         RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE);
     }
 
     if (stack == NULL)
-        stack = get_any_stack(tb);
+        stack = get_any_stack((DbTable*)tb,stack_container);
 
     if (mpi.some_limitation) {
-        if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
+        if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) {
             lastkey = GETKEY(tb, this->dbterm.tpl);
         }
         sc.end_condition = mpi.least;
     }
 
-    traverse_update_backwards(tb, stack, lastkey, &doit_select_replace, &sc);
-    release_stack(tb,stack);
+    traverse_update_backwards(tb, root, stack, lastkey, &doit_select_replace, &sc);
+    release_stack((DbTable*)tb,stack_container,stack);
     // the more objects we've replaced, the more reductions we've consumed
     BUMP_REDS(p, MIN(2000, (1000 - sc.max) + sc.replaced));
     if (sc.max > 0) {
@@ -1922,52 +2057,73 @@ static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid,
 
 }
 
-static int db_take_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid,
+                                  Eterm pattern, Eterm *ret)
 {
     DbTableTree *tb = &tbl->tree;
+    return db_select_replace_tree_common(p, &tb->common, &tb->root,
+                                         tid, pattern, ret, tb);
+}
+
+int db_take_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root,
+                        Eterm key, Eterm *ret,
+                        DbTreeStack *stack /* NULL if no static stack */)
+{
     TreeDbTerm *this;
 
     *ret = NIL;
-    this = linkout_tree(tb, key);
+    this = linkout_tree(&tbl->common, root, key, stack);
     if (this) {
         Eterm copy, *hp, *hend;
 
         hp = HAlloc(p, this->dbterm.size + 2);
         hend = hp + this->dbterm.size + 2;
-        copy = db_copy_object_from_ets(&tb->common,
+        copy = db_copy_object_from_ets(&tbl->common,
                                        &this->dbterm, &hp, &MSO(p));
         *ret = CONS(hp, copy, NIL);
         hp += 2;
         HRelease(p, hend, hp);
-        free_term(tb, this);
+        free_term(tbl, this);
     }
     return DB_ERROR_NONE;
 }
 
+static int db_take_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+{
+    DbTableTree *tb = &tbl->tree;
+    return db_take_tree_common(p, tbl, &tb->root,
+                               key, ret, &tb->static_stack);
+}
+
 /*
 ** Other interface routines (not directly coupled to one bif)
 */
 
-
-/* Display tree contents (for dump) */
-static void db_print_tree(fmtfn_t to, void *to_arg,
-			  int show,
-			  DbTable *tbl)
+void db_print_tree_common(fmtfn_t to, void *to_arg,
+                          int show, TreeDbTerm *root, DbTable *tbl)
 {
-    DbTableTree *tb = &tbl->tree;
 #ifdef TREE_DEBUG
     if (show)
 	erts_print(to, to_arg, "\nTree data dump:\n"
 		   "------------------------------------------------\n");
-    do_dump_tree2(&tbl->tree, to, to_arg, show, tb->root, 0);
+    do_dump_tree2(&tbl->common, to, to_arg, show, root, 0);
     if (show)
 	erts_print(to, to_arg, "\n"
 		   "------------------------------------------------\n");
 #else
-    erts_print(to, to_arg, "Ordered set (AVL tree), Elements: %d\n", NITEMS(tb));
+    erts_print(to, to_arg, "Ordered set (AVL tree), Elements: %d\n", NITEMS(tbl));
 #endif
 }
 
+/* Display tree contents (for dump) */
+static void db_print_tree(fmtfn_t to, void *to_arg,
+			  int show,
+			  DbTable *tbl)
+{
+    DbTableTree *tb = &tbl->tree;
+    db_print_tree_common(to, to_arg, show, tb->root, tbl);
+}
+
 /* release all memory occupied by a single table */
 static int db_free_empty_table_tree(DbTable *tbl)
 {
@@ -1992,8 +2148,10 @@ static SWord db_free_table_continue_tree(DbTable *tbl, SWord reds)
 		     (DbTable *) tb,
 		     (void *) tb->static_stack.array,
 		     sizeof(TreeDbTerm *) * STACK_NEED);
-	ASSERT(erts_atomic_read_nob(&tb->common.memory_size)
-	       == sizeof(DbTable));
+	ASSERT((erts_atomic_read_nob(&tb->common.memory_size)
+	       == sizeof(DbTable)) ||
+               (erts_atomic_read_nob(&tb->common.memory_size)
+                == (sizeof(DbTable) + sizeof(DbFixation))));
     }
     return reds;
 }
@@ -2012,11 +2170,18 @@ static void do_db_tree_foreach_offheap(TreeDbTerm *,
 				       void (*)(ErlOffHeap *, void *),
 				       void *);
 
+void db_foreach_offheap_tree_common(TreeDbTerm *root,
+                                    void (*func)(ErlOffHeap *, void *),
+                                    void * arg)
+{
+    do_db_tree_foreach_offheap(root, func, arg);
+}
+
 static void db_foreach_offheap_tree(DbTable *tbl,
 				    void (*func)(ErlOffHeap *, void *),
 				    void * arg)
 {
-    do_db_tree_foreach_offheap(tbl->tree.root, func, arg);
+    db_foreach_offheap_tree_common(tbl->tree.root, func, arg);
 }
 
 
@@ -2041,13 +2206,14 @@ do_db_tree_foreach_offheap(TreeDbTerm *tdbt,
     do_db_tree_foreach_offheap(tdbt->right, func, arg);
 }
 
-static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key) {
+static TreeDbTerm *linkout_tree(DbTableCommon *tb, TreeDbTerm **root,
+                                Eterm key, DbTreeStack *stack) {
     TreeDbTerm **tstack[STACK_NEED];
     int tpos = 0;
     int dstack[STACK_NEED+1];
     int dpos = 0;
     int state = 0;
-    TreeDbTerm **this = &tb->root;
+    TreeDbTerm **this = root;
     Sint c;
     int dir;
     TreeDbTerm *q = NULL;
@@ -2058,7 +2224,7 @@ static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key) {
      * keep the balance. As in insert, we do the stacking ourselves.
      */
 
-    reset_static_stack(tb);
+    reset_stack(stack);
     dstack[dpos++] = DIR_END;
     for (;;) {
 	if (!*this) { /* Failure */
@@ -2084,30 +2250,30 @@ static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key) {
 		tstack[tpos++] = this;
 		state = delsub(this);
 	    }
-	    erts_atomic_dec_nob(&tb->common.nitems);
+	    erts_atomic_dec_nob(&tb->nitems);
 	    break;
 	}
     }
     while (state && ( dir = dstack[--dpos] ) != DIR_END) {
 	this = tstack[--tpos];
 	if (dir == DIR_LEFT) {
-	    state = balance_left(this);
+	    state = tree_balance_left(this);
 	} else {
-	    state = balance_right(this);
+	    state = tree_balance_right(this);
 	}
     }
     return q;
 }
 
-static TreeDbTerm *linkout_object_tree(DbTableTree *tb, 
-				       Eterm object)
+static TreeDbTerm *linkout_object_tree(DbTableCommon *tb,  TreeDbTerm **root,
+				       Eterm object, DbTableTree *stack)
 {
     TreeDbTerm **tstack[STACK_NEED];
     int tpos = 0;
     int dstack[STACK_NEED+1];
     int dpos = 0;
     int state = 0;
-    TreeDbTerm **this = &tb->root;
+    TreeDbTerm **this = root;
     Sint c;
     int dir;
     TreeDbTerm *q = NULL;
@@ -2122,7 +2288,7 @@ static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
     
     key = GETKEY(tb, tuple_val(object));
 
-    reset_static_stack(tb);
+    reset_static_stack(stack);
     dstack[dpos++] = DIR_END;
     for (;;) {
 	if (!*this) { /* Failure */
@@ -2136,7 +2302,7 @@ static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
 	    tstack[tpos++] = this;
 	    this = &((*this)->right);
 	} else { /* Equal key, found the only possible matching object*/
-	    if (!db_eq(&tb->common,object,&(*this)->dbterm)) {
+	    if (!db_eq(tb,object,&(*this)->dbterm)) {
 		return NULL;
 	    }
 	    q = (*this);
@@ -2151,16 +2317,16 @@ static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
 		tstack[tpos++] = this;
 		state = delsub(this);
 	    }
-	    erts_atomic_dec_nob(&tb->common.nitems);
+	    erts_atomic_dec_nob(&tb->nitems);
 	    break;
 	}
     }
     while (state && ( dir = dstack[--dpos] ) != DIR_END) {
 	this = tstack[--tpos];
 	if (dir == DIR_LEFT) {
-	    state = balance_left(this);
+	    state = tree_balance_left(this);
 	} else {
-	    state = balance_right(this);
+	    state = tree_balance_right(this);
 	}
     }
     return q;
@@ -2170,7 +2336,7 @@ static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
 ** For the select functions, analyzes the pattern and determines which
 ** part of the tree should be searched. Also compiles the match program
 */
-static int analyze_pattern(DbTableTree *tb, Eterm pattern,
+static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern,
                            extra_match_validator_t extra_validator, /* Optional callback */
                            struct mp_info *mpi)
 {
@@ -2231,7 +2397,7 @@ static int analyze_pattern(DbTableTree *tb, Eterm pattern,
 	guards[i] = guard = ptpl[2];
 	bodies[i] = body = ptpl[3];
 
-        if(extra_validator != NULL && !extra_validator(tb->common.keypos, match, guard, body)) {
+        if(extra_validator != NULL && !extra_validator(tb->keypos, match, guard, body)) {
 	    if (buff != sbuff) {
 		erts_free(ERTS_ALC_T_DB_TMP, buff);
 	    }
@@ -2244,7 +2410,7 @@ static int analyze_pattern(DbTableTree *tb, Eterm pattern,
 	++i;
 
 	partly_bound = NIL;
-	res = key_given(tb, tpl, &(mpi->save_term), &partly_bound);
+	res = key_given(tb, root, tpl, &(mpi->save_term), &partly_bound);
 	if ( res >= 0 ) {   /* Can match something */
 	    key = 0;
 	    mpi->something_can_match = 1;
@@ -2308,7 +2474,7 @@ static SWord do_free_tree_continue(DbTableTree *tb, SWord reds)
 		PUSH_NODE(&tb->static_stack, root);
 		root = p;
 	    } else {
-		free_term(tb, root);
+		free_term((DbTable*)tb, root);
 		if (--reds < 0) {
                     return reds;   /* Done enough for now */
                 }
@@ -2322,7 +2488,7 @@ static SWord do_free_tree_continue(DbTableTree *tb, SWord reds)
 /*
  * Deletion helpers
  */
-static int balance_left(TreeDbTerm **this) 
+int tree_balance_left(TreeDbTerm **this) 
 {
     TreeDbTerm *p, *p1, *p2;
     int b1, b2, h = 1;
@@ -2367,7 +2533,7 @@ static int balance_left(TreeDbTerm **this)
     return h;
 }
 
-static int balance_right(TreeDbTerm **this) 
+int tree_balance_right(TreeDbTerm **this) 
 {
     TreeDbTerm *p, *p1, *p2;
     int b1, b2, h = 1;
@@ -2439,7 +2605,7 @@ static int delsub(TreeDbTerm **this)
     h = 1;
     while (tpos && h) {
 	r = tstack[--tpos];
-	h = balance_right(r);
+	h = tree_balance_right(r);
     }
     return h;
 }
@@ -2448,11 +2614,13 @@ static int delsub(TreeDbTerm **this)
  * Helper for db_slot
  */
 
-static TreeDbTerm *slot_search(Process *p, DbTableTree *tb, Sint slot)
+static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root,
+                               Sint slot, DbTable *tb,
+                               DbTableTree *stack_container)
 {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
-    DbTreeStack* stack = get_any_stack(tb);
+    DbTreeStack* stack = get_any_stack(tb,stack_container);
     ASSERT(stack != NULL);
 
     if (slot == 1) { /* Don't search from where we are if we are 
@@ -2465,7 +2633,7 @@ static TreeDbTerm *slot_search(Process *p, DbTableTree *tb, Sint slot)
 	stack->pos = 0;
     }
     if (EMPTY_NODE(stack)) {
-	this = tb->root;
+	this = root;
 	if (this == NULL)
 	    goto done;
 	while (this->left != NULL){
@@ -2514,7 +2682,7 @@ static TreeDbTerm *slot_search(Process *p, DbTableTree *tb, Sint slot)
 	}
     }
 done:
-    release_stack(tb,stack);
+    release_stack(tb,stack_container,stack);
     return this;
 }
 
@@ -2522,7 +2690,8 @@ done:
  * Find next and previous in sort order
  */
 
-static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
+static TreeDbTerm *find_next(DbTableCommon *tb, TreeDbTerm *root,
+                             DbTreeStack* stack, Eterm key) {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
     Sint c;
@@ -2534,7 +2703,7 @@ static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
 	}
     }
     if (EMPTY_NODE(stack)) { /* Have to rebuild the stack */
-	if (( this = tb->root ) == NULL)
+	if (( this = root ) == NULL)
 	    return NULL;
 	for (;;) {
 	    PUSH_NODE(stack, this);
@@ -2578,7 +2747,8 @@ static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
     return this;
 }
 
-static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
+static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root,
+                             DbTreeStack* stack, Eterm key) {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
     Sint c;
@@ -2590,7 +2760,7 @@ static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
 	}
     }
     if (EMPTY_NODE(stack)) { /* Have to rebuild the stack */
-	if (( this = tb->root ) == NULL)
+	if (( this = root ) == NULL)
 	    return NULL;
 	for (;;) {
 	    PUSH_NODE(stack, this);
@@ -2634,8 +2804,8 @@ static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
     return this;
 }
 
-static TreeDbTerm *find_next_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
-					 Eterm key)
+static TreeDbTerm *find_next_from_pb_key(DbTableCommon *tb, TreeDbTerm *root,
+                                         DbTreeStack* stack, Eterm key)
 {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
@@ -2643,7 +2813,7 @@ static TreeDbTerm *find_next_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
 
     /* spool the stack, we have to "re-search" */
     stack->pos = stack->slot = 0;
-    if (( this = tb->root ) == NULL)
+    if (( this = root ) == NULL)
 	return NULL;
     for (;;) {
 	PUSH_NODE(stack, this);
@@ -2667,8 +2837,8 @@ static TreeDbTerm *find_next_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
     }
 }
 
-static TreeDbTerm *find_prev_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
-					 Eterm key)
+static TreeDbTerm *find_prev_from_pb_key(DbTableCommon *tb, TreeDbTerm *root,
+                                         DbTreeStack* stack, Eterm key)
 {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
@@ -2676,7 +2846,7 @@ static TreeDbTerm *find_prev_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
 
     /* spool the stack, we have to "re-search" */
     stack->pos = stack->slot = 0;
-    if (( this = tb->root ) == NULL)
+    if (( this = root ) == NULL)
 	return NULL;
     for (;;) {
 	PUSH_NODE(stack, this);
@@ -2704,16 +2874,17 @@ static TreeDbTerm *find_prev_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
 /*
  * Just lookup a node
  */
-static TreeDbTerm *find_node(DbTableTree *tb, Eterm key)
+static TreeDbTerm *find_node(DbTableCommon *tb, TreeDbTerm *root,
+                             Eterm key, DbTableTree *stack_container)
 {
     TreeDbTerm *this;
     Sint res;
-    DbTreeStack* stack = get_static_stack(tb);
+    DbTreeStack* stack = get_static_stack(stack_container);
 
     if(!stack || EMPTY_NODE(stack)
        || !cmp_key_eq(tb, key, (this=TOP_NODE(stack)))) {
 
-	this = tb->root;
+	this = root;
 	while (this != NULL && (res = cmp_key(tb,key,this)) != 0) {
 	    if (res < 0)
 		this = this->left;
@@ -2722,7 +2893,7 @@ static TreeDbTerm *find_node(DbTableTree *tb, Eterm key)
 	}
     }
     if (stack) {
-	release_stack(tb,stack);
+	release_stack((DbTable*)tb,stack_container,stack);
     }
     return this;
 }
@@ -2730,12 +2901,12 @@ static TreeDbTerm *find_node(DbTableTree *tb, Eterm key)
 /*
  * Lookup a node and return the address of the node pointer in the tree
  */
-static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
+static TreeDbTerm **find_node2(DbTableCommon *tb, TreeDbTerm **root, Eterm key)
 {
     TreeDbTerm **this;
     Sint res;
 
-    this = &tb->root;
+    this = root;
     while ((*this) != NULL && (res = cmp_key(tb, key, *this)) != 0) {
 	if (res < 0)
 	    this = &((*this)->left);
@@ -2752,7 +2923,8 @@ static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
  * Tries to reuse the existing stack for performance.
  */
 
-static TreeDbTerm **find_ptr(DbTableTree *tb, DbTreeStack *stack, TreeDbTerm *this) {
+static TreeDbTerm **find_ptr(DbTableCommon *tb, TreeDbTerm **root,
+                             DbTreeStack *stack, TreeDbTerm *this) {
     Eterm key = GETKEY(tb, this->dbterm.tpl);
     TreeDbTerm *tmp;
     TreeDbTerm *parent;
@@ -2765,7 +2937,7 @@ static TreeDbTerm **find_ptr(DbTableTree *tb, DbTreeStack *stack, TreeDbTerm *th
 	}
     }
     if (EMPTY_NODE(stack)) { /* Have to rebuild the stack */
-	if (( tmp = tb->root ) == NULL)
+	if (( tmp = *root ) == NULL)
 	    return NULL;
 	for (;;) {
 	    PUSH_NODE(stack, tmp);
@@ -2791,7 +2963,7 @@ static TreeDbTerm **find_ptr(DbTableTree *tb, DbTreeStack *stack, TreeDbTerm *th
 
     parent = TOPN_NODE(stack, 1);
     if (parent == NULL)
-        return ((this != tb->root) ? NULL : &(tb->root));
+        return ((this != *root) ? NULL : root);
     if (parent->left == this)
         return &(parent->left);
     if (parent->right == this)
@@ -2799,12 +2971,11 @@ static TreeDbTerm **find_ptr(DbTableTree *tb, DbTreeStack *stack, TreeDbTerm *th
     return NULL;
 }
 
-static int
-db_lookup_dbterm_tree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
-                      DbUpdateHandle* handle)
+int db_lookup_dbterm_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root,
+                                 Eterm key, Eterm obj, DbUpdateHandle* handle,
+                                 DbTableTree *stack_container)
 {
-    DbTableTree *tb = &tbl->tree;
-    TreeDbTerm **pp = find_node2(tb, key);
+    TreeDbTerm **pp = find_node2(&tbl->common, root, key);
     int flags = 0;
 
     if (pp == NULL) {
@@ -2815,18 +2986,19 @@ db_lookup_dbterm_tree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
             int arity = arityval(*objp);
             Eterm *htop, *hend;
 
-            ASSERT(arity >= tb->common.keypos);
+            ASSERT(arity >= tbl->common.keypos);
             htop = HAlloc(p, arity + 1);
             hend = htop + arity + 1;
             sys_memcpy(htop, objp, sizeof(Eterm) * (arity + 1));
-            htop[tb->common.keypos] = key;
+            htop[tbl->common.keypos] = key;
             obj = make_tuple(htop);
 
-            if (db_put_tree(tbl, obj, 1) != DB_ERROR_NONE) {
+            if (db_put_tree_common(&tbl->common, root,
+                                   obj, 1, stack_container) != DB_ERROR_NONE) {
                 return 0;
             }
 
-            pp = find_node2(tb, key);
+            pp = find_node2(&tbl->common, root, key);
             ASSERT(pp != NULL);
             HRelease(p, hend, htop);
             flags |= DB_NEW_OBJECT;
@@ -2841,21 +3013,28 @@ db_lookup_dbterm_tree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
     return 1;
 }
 
-static void
-db_finalize_dbterm_tree(int cret, DbUpdateHandle *handle)
+static int
+db_lookup_dbterm_tree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
+                      DbUpdateHandle* handle)
 {
-    DbTable *tbl = handle->tb;
     DbTableTree *tb = &tbl->tree;
+    return db_lookup_dbterm_tree_common(p, tbl, &tb->root, key, obj, handle, tb);
+}
+
+void db_finalize_dbterm_tree_common(int cret, DbUpdateHandle *handle,
+                                    DbTableTree *stack_container)
+{
+    DbTable *tbl = handle->tb;
     TreeDbTerm *bp = (TreeDbTerm *) *handle->bp;
 
     if (handle->flags & DB_NEW_OBJECT && cret != DB_ERROR_NONE) {
         Eterm ret;
-        db_erase_tree(tbl, GETKEY(tb, bp->dbterm.tpl), &ret);
+        db_erase_tree(tbl, GETKEY(&tbl->common, bp->dbterm.tpl), &ret);
     } else if (handle->flags & DB_MUST_RESIZE) {
 	db_finalize_resize(handle, offsetof(TreeDbTerm,dbterm));
-        reset_static_stack(tb);
+        reset_static_stack(stack_container);
 
-        free_term(tb, bp);
+        free_term(tbl, bp);
     }
 #ifdef DEBUG
     handle->dbterm = 0;
@@ -2863,13 +3042,22 @@ db_finalize_dbterm_tree(int cret, DbUpdateHandle *handle)
     return;
 }   
 
+static void
+db_finalize_dbterm_tree(int cret, DbUpdateHandle *handle)
+{
+    DbTable *tbl = handle->tb;
+    DbTableTree *tb = &tbl->tree;
+    db_finalize_dbterm_tree_common(cret, handle, tb);
+}
+
 /*
  * Traverse the tree with a callback function, used by db_match_xxx
  */
-static void traverse_backwards(DbTableTree *tb,
+static void traverse_backwards(DbTableCommon *tb,
+                               TreeDbTerm **root,
 			       DbTreeStack* stack,
 			       Eterm lastkey,
-			       int (*doit)(DbTableTree *,
+			       int (*doit)(DbTableCommon *,
 					   TreeDbTerm *,
 					   void *,
 					   int),
@@ -2879,7 +3067,7 @@ static void traverse_backwards(DbTableTree *tb,
 
     if (lastkey == THE_NON_VALUE) {
 	stack->pos = stack->slot = 0;
-	if (( this = tb->root ) == NULL) {
+	if (( this = *root ) == NULL) {
 	    return;
 	}
 	while (this != NULL) {
@@ -2887,15 +3075,15 @@ static void traverse_backwards(DbTableTree *tb,
 	    this = this->right;
 	}
 	this = TOP_NODE(stack);
-	next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl));
+	next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl));
 	if (!((*doit)(tb, this, context, 0)))
 	    return;
     } else {
-	next = find_prev(tb, stack, lastkey);
+	next = find_prev(tb, *root, stack, lastkey);
     }
 
     while ((this = next) != NULL) {
-	next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl));
+	next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl));
 	if (!((*doit)(tb, this, context, 0)))
 	    return;
     }
@@ -2904,10 +3092,11 @@ static void traverse_backwards(DbTableTree *tb,
 /*
  * Traverse the tree with a callback function, used by db_match_xxx
  */
-static void traverse_forward(DbTableTree *tb,
+static void traverse_forward(DbTableCommon *tb,
+                             TreeDbTerm **root,
 			     DbTreeStack* stack,
 			     Eterm lastkey,
-			     int (*doit)(DbTableTree *,
+			     int (*doit)(DbTableCommon *,
 					 TreeDbTerm *,
 					 void *,
 					 int),
@@ -2917,7 +3106,7 @@ static void traverse_forward(DbTableTree *tb,
 
     if (lastkey == THE_NON_VALUE) {
 	stack->pos = stack->slot = 0;
-	if (( this = tb->root ) == NULL) {
+	if (( this = *root ) == NULL) {
 	    return;
 	}
 	while (this != NULL) {
@@ -2925,15 +3114,15 @@ static void traverse_forward(DbTableTree *tb,
 	    this = this->left;
 	}
 	this = TOP_NODE(stack);
-	next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl));
+	next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl));
 	if (!((*doit)(tb, this, context, 1)))
 	    return;
     } else {
-	next = find_next(tb, stack, lastkey);
+	next = find_next(tb, *root, stack, lastkey);
     }
 
     while ((this = next) != NULL) {
-	next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl));
+	next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl));
 	if (!((*doit)(tb, this, context, 1)))
 	    return;
     }
@@ -2942,10 +3131,11 @@ static void traverse_forward(DbTableTree *tb,
 /*
  * Traverse the tree with an update callback function, used by db_select_replace
  */
-static void traverse_update_backwards(DbTableTree *tb,
+static void traverse_update_backwards(DbTableCommon *tb,
+                                      TreeDbTerm **root,
                                       DbTreeStack* stack,
                                       Eterm lastkey,
-                                      int (*doit)(DbTableTree*,
+                                      int (*doit)(DbTableCommon*,
                                                   TreeDbTerm**,
                                                   void*,
                                                   int),
@@ -2956,7 +3146,7 @@ static void traverse_update_backwards(DbTableTree *tb,
 
     if (lastkey == THE_NON_VALUE) {
         stack->pos = stack->slot = 0;
-        if (( this = tb->root ) == NULL) {
+        if (( this = *root ) == NULL) {
             return;
         }
         while (this != NULL) {
@@ -2964,23 +3154,23 @@ static void traverse_update_backwards(DbTableTree *tb,
             this = this->right;
         }
         this = TOP_NODE(stack);
-        this_ptr = find_ptr(tb, stack, this);
+        this_ptr = find_ptr(tb, root, stack, this);
         ASSERT(this_ptr != NULL);
         res = (*doit)(tb, this_ptr, context, 0);
         REPLACE_TOP_NODE(stack, *this_ptr);
-        next = find_prev(tb, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl));
+        next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl));
         if (!res)
             return;
     } else {
-        next = find_prev(tb, stack, lastkey);
+        next = find_prev(tb, *root, stack, lastkey);
     }
 
     while ((this = next) != NULL) {
-        this_ptr = find_ptr(tb, stack, this);
+        this_ptr = find_ptr(tb, root, stack, this);
         ASSERT(this_ptr != NULL);
         res = (*doit)(tb, this_ptr, context, 0);
         REPLACE_TOP_NODE(stack, *this_ptr);
-        next = find_prev(tb, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl));
+        next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl));
         if (!res)
             return;
     }
@@ -2990,8 +3180,8 @@ static void traverse_update_backwards(DbTableTree *tb,
  * Returns 0 if not given 1 if given and -1 on no possible match
  * if key is given; *ret is set to point to the object concerned.
  */
-static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm ***ret,
-		     Eterm *partly_bound)
+static int key_given(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern,
+                     TreeDbTerm ***ret, Eterm *partly_bound)
 {
     TreeDbTerm **this;
     Eterm key;
@@ -2999,11 +3189,11 @@ static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm ***ret,
     ASSERT(ret != NULL);
     if (pattern == am_Underscore || db_is_variable(pattern) != -1)
 	return 0;
-    key = db_getkey(tb->common.keypos, pattern);
+    key = db_getkey(tb->keypos, pattern);
     if (is_non_value(key))
 	return -1;  /* can't possibly match anything */
     if (!db_has_variable(key)) {   /* Bound key */
-	if (( this = find_node2(tb, key) ) == NULL) {
+	if (( this = find_node2(tb, root, key) ) == NULL) {
 	    return -1;
 	}
 	*ret = this;
@@ -3296,7 +3486,7 @@ static int do_partly_bound_can_match_greater(Eterm a, Eterm b,
  * Callback functions for the different match functions
  */
 
-static int doit_select(DbTableTree *tb, TreeDbTerm *this, void *ptr,
+static int doit_select(DbTableCommon *tb, TreeDbTerm *this, void *ptr,
 		       int forward)
 {
     struct select_context *sc = (struct select_context *) ptr;
@@ -3314,7 +3504,7 @@ static int doit_select(DbTableTree *tb, TreeDbTerm *this, void *ptr,
 			   GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0))) {
 	return 0;
     }
-    ret = db_match_dbterm(&tb->common, sc->p, sc->mp, &this->dbterm, &hp, 2);
+    ret = db_match_dbterm(tb, sc->p,sc->mp, &this->dbterm, &hp, 2);
     if (is_value(ret)) {
 	sc->accum = CONS(hp, ret, sc->accum);
     }
@@ -3331,7 +3521,7 @@ static int doit_select(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     return 1;
 }
 
-static int doit_select_count(DbTableTree *tb, TreeDbTerm *this, void *ptr,
+static int doit_select_count(DbTableCommon *tb, TreeDbTerm *this, void *ptr,
 			     int forward)
 {
     struct select_count_context *sc = (struct select_count_context *) ptr;
@@ -3345,7 +3535,7 @@ static int doit_select_count(DbTableTree *tb, TreeDbTerm *this, void *ptr,
 			  GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0)) {
 	return 0;
     }
-    ret = db_match_dbterm(&tb->common, sc->p, sc->mp, &this->dbterm, NULL, 0);
+    ret = db_match_dbterm(tb, sc->p, sc->mp, &this->dbterm, NULL, 0);
     if (ret == am_true) {
 	++(sc->got);
     }
@@ -3355,7 +3545,7 @@ static int doit_select_count(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     return 1;
 }
 
-static int doit_select_chunk(DbTableTree *tb, TreeDbTerm *this, void *ptr,
+static int doit_select_chunk(DbTableCommon *tb, TreeDbTerm *this, void *ptr,
 			     int forward)
 {
     struct select_context *sc = (struct select_context *) ptr;
@@ -3374,7 +3564,7 @@ static int doit_select_chunk(DbTableTree *tb, TreeDbTerm *this, void *ptr,
 	return 0;
     }
 
-    ret = db_match_dbterm(&tb->common, sc->p, sc->mp, &this->dbterm, &hp, 2);
+    ret = db_match_dbterm(tb, sc->p, sc->mp, &this->dbterm, &hp, 2);
     if (is_value(ret)) {
 	++(sc->got);
 	sc->accum = CONS(hp, ret, sc->accum);
@@ -3393,7 +3583,7 @@ static int doit_select_chunk(DbTableTree *tb, TreeDbTerm *this, void *ptr,
 }
 
 
-static int doit_select_delete(DbTableTree *tb, TreeDbTerm *this, void *ptr,
+static int doit_select_delete(DbTableCommon *tb, TreeDbTerm *this, void *ptr,
 			      int forward)
 {
     struct select_delete_context *sc = (struct select_delete_context *) ptr;
@@ -3401,7 +3591,7 @@ static int doit_select_delete(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     Eterm key;
 
     if (sc->erase_lastterm)
-	free_term(tb, sc->lastterm);
+	free_term((DbTable*)tb, sc->lastterm);
     sc->erase_lastterm = 0;
     sc->lastterm = this;
     
@@ -3409,10 +3599,10 @@ static int doit_select_delete(DbTableTree *tb, TreeDbTerm *this, void *ptr,
 	cmp_partly_bound(sc->end_condition, 
 			 GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0)
 	return 0;
-    ret = db_match_dbterm(&tb->common, sc->p, sc->mp, &this->dbterm, NULL, 0);
+    ret = db_match_dbterm(tb, sc->p, sc->mp, &this->dbterm, NULL, 0);
     if (ret == am_true) {
 	key = GETKEY(sc->tb, this->dbterm.tpl);
-	linkout_tree(sc->tb, key);
+	linkout_tree(sc->tb, sc->root, key, sc->stack);
 	sc->erase_lastterm = 1;
 	++sc->accum;
     }
@@ -3422,7 +3612,7 @@ static int doit_select_delete(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     return 1;
 }
 
-static int doit_select_replace(DbTableTree *tb, TreeDbTerm **this, void *ptr,
+static int doit_select_replace(DbTableCommon *tb, TreeDbTerm **this, void *ptr,
                                int forward)
 {
     struct select_replace_context *sc = (struct select_replace_context *) ptr;
@@ -3436,13 +3626,13 @@ static int doit_select_replace(DbTableTree *tb, TreeDbTerm **this, void *ptr,
 			  GETKEY_WITH_POS(sc->keypos, (*this)->dbterm.tpl)) > 0)) {
 	return 0;
     }
-    ret = db_match_dbterm(&tb->common, sc->p, sc->mp, &(*this)->dbterm, NULL, 0);
+    ret = db_match_dbterm(tb, sc->p, sc->mp, &(*this)->dbterm, NULL, 0);
 
     if (is_value(ret)) {
         TreeDbTerm* new;
         TreeDbTerm* old = *this;
 #ifdef DEBUG
-        Eterm key = db_getkey(tb->common.keypos, ret);
+        Eterm key = db_getkey(tb->keypos, ret);
         ASSERT(is_value(key));
         ASSERT(cmp_key(tb, key, old) == 0);
 #endif
@@ -3452,7 +3642,7 @@ static int doit_select_replace(DbTableTree *tb, TreeDbTerm **this, void *ptr,
         new->balance = old->balance;
         sc->lastobj = new->dbterm.tpl;
         *this = new;
-        free_term(tb, old);
+        free_term((DbTable*)tb, old);
         ++(sc->replaced);
     }
     if (--(sc->max) <= 0) {
@@ -3462,7 +3652,7 @@ static int doit_select_replace(DbTableTree *tb, TreeDbTerm **this, void *ptr,
 }
 
 #ifdef TREE_DEBUG
-static void do_dump_tree2(DbTableTree* tb, int to, void *to_arg, int show,
+static void do_dump_tree2(DbTableCommon* tb, int to, void *to_arg, int show,
 			  TreeDbTerm *t, int offset)
 {
     if (t == NULL)
@@ -3471,7 +3661,7 @@ static void do_dump_tree2(DbTableTree* tb, int to, void *to_arg, int show,
     if (show) {
 	const char* prefix;
 	Eterm term;
-	if (tb->common.compress) {
+	if (tb->compress) {
 	    prefix = "key=";
 	    term = GETKEY(tb, t->dbterm.tpl);
 	}
@@ -3526,7 +3716,7 @@ static void check_slot_pos(DbTableTree *tb)
 		   "element position %d is really 0x%08X, when stack says "
 		   "it's 0x%08X\n", tb->stack.slot, t, 
 		   tb->stack.array[tb->stack.pos - 1]);
-	do_dump_tree2(tb, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
+	do_dump_tree2(&tb->common, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
     }
 }
 	
@@ -3541,14 +3731,14 @@ static void check_saved_stack(DbTableTree *tb)
      if (t != stack->array[0]) {
 	 erts_fprintf(stderr,"tb->stack[0] is 0x%08X, should be 0x%08X\n",
 		      stack->array[0], t);
-	 do_dump_tree2(tb, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
+	 do_dump_tree2(&tb->common, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
 	 return;
      }
      while (n < stack->pos) {
 	 if (t == NULL) {
 	     erts_fprintf(stderr, "NULL pointer in tree when stack not empty,"
 			" stack depth is %d\n", n);
-	     do_dump_tree2(tb, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
+	     do_dump_tree2(&tb->common, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
 	     return;
 	 }
 	 n++;
@@ -3562,7 +3752,7 @@ static void check_saved_stack(DbTableTree *tb)
 			    "represent child pointer in tree!"
 			    "(left == 0x%08X, right == 0x%08X\n", 
 			    n, tb->stack[n], t->left, t->right);
-		 do_dump_tree2(tb, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
+		 do_dump_tree2(&tb->common, ERTS_PRINT_STDERR, NULL, 1, tb->root, 0);
 		 return;
 	     }
 	 }
@@ -3581,7 +3771,7 @@ static int check_table_tree(DbTableTree* tb, TreeDbTerm *t)
 	erts_fprintf(stderr,"balance = %d, left = 0x%08X, right = 0x%08X\n",
 		     t->balance, t->left, t->right);
 	erts_fprintf(stderr,"\nDump:\n---------------------------------\n");
-	do_dump_tree2(tb, ERTS_PRINT_STDERR, NULL, 1, t, 0);
+	do_dump_tree2(&tb->common, ERTS_PRINT_STDERR, NULL, 1, t, 0);
 	erts_fprintf(stderr,"\n---------------------------------\n");
     }
     return ((rh > lh) ? rh : lh) + 1;