HALFWORD ETS relative terms

In halfword emulator, make ETS use a variant of the internal term
format that uses relative offsets instead of absolute pointers. This
will allow storage in high memory (>4G). Preprocessor macros (like
list_val_rel(TERM,BASE)) are used to make normal (fullword) emulator
almost completely unchanged while still reusing most of the code.

1 files changed, 147 insertions, 160 deletions

diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c
index 8108494fc5..c74ccdc119 100644
--- a/erts/emulator/beam/erl_db_tree.c
+++ b/erts/emulator/beam/erl_db_tree.c
@@ -48,9 +48,6 @@
 
 #include "erl_db_tree.h"
 
-
-
-#define GETKEY(dtt, tplp)   (*((tplp) +  (dtt)->common.keypos))
 #define GETKEY_WITH_POS(Keypos, Tplp) (*((Tplp) + Keypos))
 #define NITEMS(tb) ((int)erts_smp_atomic_read(&(tb)->common.nitems))
 
@@ -282,7 +279,7 @@ struct select_delete_context {
 /*
 ** Forward declarations 
 */
-static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key);
+static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key, Eterm* key_base);
 static TreeDbTerm *linkout_object_tree(DbTableTree *tb, 
 				       Eterm object);
 static int do_free_tree_cont(DbTableTree *tb, int num_left);
@@ -293,15 +290,15 @@ 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_next(DbTableTree *tb, DbTreeStack*, Eterm key);
-static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack*, Eterm key);
+static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack*, Eterm key, Eterm* kbase);
+static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack*, Eterm key, Eterm* kbase);
 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,
 			       DbTreeStack*,
-			       Eterm lastkey,
+			       Eterm lastkey, Eterm* lk_base,
 			       int (*doit)(DbTableTree *tb,
 					   TreeDbTerm *,
 					   void *,
@@ -309,7 +306,7 @@ static void traverse_backwards(DbTableTree *tb,
 			       void *context); 
 static void traverse_forward(DbTableTree *tb,
 			     DbTreeStack*,
-			     Eterm lastkey,
+			     Eterm lastkey, Eterm* lk_base,
 			     int (*doit)(DbTableTree *tb,
 					 TreeDbTerm *,
 					 void *,
@@ -317,8 +314,8 @@ static void traverse_forward(DbTableTree *tb,
 			     void *context); 
 static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
 		     Eterm *partly_bound_key);
-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 Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key, Eterm* bk_base);
+static Sint do_cmp_partly_bound(Eterm a, Eterm b, Eterm* b_base, int *done);
 
 static int analyze_pattern(DbTableTree *tb, Eterm pattern, 
 			   struct mp_info *mpi);
@@ -492,9 +489,6 @@ static int db_first_tree(Process *p, DbTable *tbl, Eterm *ret)
     DbTableTree *tb = &tbl->tree;
     DbTreeStack* stack;
     TreeDbTerm *this;
-    Eterm e;
-    Eterm *hp;
-    Uint sz;
 
     if (( this = tb->root ) == NULL) {
 	*ret = am_EOT;
@@ -513,13 +507,7 @@ static int db_first_tree(Process *p, DbTable *tbl, Eterm *ret)
 	stack->slot = 1;
 	release_stack(tb,stack);
     }
-    e = GETKEY(tb, this->dbterm.tpl);
-    sz = size_object(e);
-
-    hp = HAlloc(p, sz);
-
-    *ret = copy_struct(e,sz,&hp,&MSO(p));
-    
+    *ret = db_copy_key(p, tbl, &this->dbterm);
     return DB_ERROR_NONE;
 }
 
@@ -528,26 +516,17 @@ static int db_next_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
     DbTableTree *tb = &tbl->tree;
     DbTreeStack* stack;
     TreeDbTerm *this;
-    Eterm e;
-    Eterm *hp;
-    Uint sz;
 
     if (is_atom(key) && key == am_EOT)
 	return DB_ERROR_BADKEY;
     stack = get_any_stack(tb);
-    this = find_next(tb, stack, key);
+    this = find_next(tb, stack, key, NULL);
     release_stack(tb,stack);
     if (this == NULL) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
     }
-    e = GETKEY(tb, this->dbterm.tpl);
-    sz = size_object(e);
-
-    hp = HAlloc(p, sz);
-
-    *ret = copy_struct(e,sz,&hp,&MSO(p));
-    
+    *ret = db_copy_key(p, tbl, &this->dbterm);
     return DB_ERROR_NONE;
 }
 
@@ -556,9 +535,6 @@ static int db_last_tree(Process *p, DbTable *tbl, Eterm *ret)
     DbTableTree *tb = &tbl->tree;
     TreeDbTerm *this;
     DbTreeStack* stack;
-    Eterm e;
-    Eterm *hp;
-    Uint sz;
 
     if (( this = tb->root ) == NULL) {
 	*ret = am_EOT;
@@ -577,13 +553,7 @@ static int db_last_tree(Process *p, DbTable *tbl, Eterm *ret)
 	stack->slot = NITEMS(tb);
 	release_stack(tb,stack);
     }
-    e = GETKEY(tb, this->dbterm.tpl);
-    sz = size_object(e);
-
-    hp = HAlloc(p, sz);
-
-    *ret = copy_struct(e,sz,&hp,&MSO(p));
-    
+    *ret = db_copy_key(p, tbl, &this->dbterm);
     return DB_ERROR_NONE;
 }
 
@@ -592,27 +562,33 @@ static int db_prev_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
     DbTableTree *tb = &tbl->tree;
     TreeDbTerm *this;
     DbTreeStack* stack;
-    Eterm e;
-    Eterm *hp;
-    Uint sz;
 
     if (is_atom(key) && key == am_EOT)
 	return DB_ERROR_BADKEY;
     stack = get_any_stack(tb);
-    this = find_prev(tb, stack, key);
+    this = find_prev(tb, stack, key, NULL);
     release_stack(tb,stack);
     if (this == NULL) {
 	*ret = am_EOT;
 	return DB_ERROR_NONE;
     }
-    e = GETKEY(tb, this->dbterm.tpl);
-    sz = size_object(e);
+    *ret = db_copy_key(p, tbl, &this->dbterm);
+    return DB_ERROR_NONE;
+}
 
-    hp = HAlloc(p, sz);
+static ERTS_INLINE int cmp_key(DbTableTree* tb, Eterm key, Eterm* key_base,
+			       TreeDbTerm* obj)
+{
+    return cmp_rel(key, key_base,
+		   GETKEY(tb,obj->dbterm.tpl), obj->dbterm.tpl);
+}
 
-    *ret = copy_struct(e,sz,&hp,&MSO(p));
-    
-    return DB_ERROR_NONE;
+static ERTS_INLINE int cmp_key_eq(DbTableTree* tb, Eterm key, Eterm* key_base,
+				  TreeDbTerm* obj)
+{
+    Eterm obj_key = GETKEY(tb,obj->dbterm.tpl);
+    return is_same(key, key_base, obj_key, obj->dbterm.tpl)
+	|| cmp_rel(key, key_base, obj_key, obj->dbterm.tpl) == 0;
 }
 
 static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
@@ -646,8 +622,8 @@ static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
 	    (*this)->balance = 0;
 	    (*this)->left = (*this)->right = NULL;
 	    break;
-	} else if ((c = cmp(key,GETKEY(tb,(*this)->dbterm.tpl))) < 0) { 
-	    /* go left */
+	} else if ((c = cmp_key(tb, key, NULL, *this)) < 0) {
+	    /* go lefts */
 	    dstack[dpos++] = DIR_LEFT;
 	    tstack[tpos++] = this;
 	    this = &((*this)->left);
@@ -801,7 +777,7 @@ static int db_erase_tree(DbTable *tbl, Eterm key, Eterm *ret)
 
     *ret = am_true;
 
-    if ((res = linkout_tree(tb, key)) != NULL) {
+    if ((res = linkout_tree(tb, key, NULL)) != NULL) {
 	free_term(tb, res);
     }
     return DB_ERROR_NONE;
@@ -993,15 +969,15 @@ static int db_select_continue_tree(Process *p,
     stack = get_any_stack(tb);
     if (chunk_size) {
 	if (reverse) {
-	    traverse_backwards(tb, stack, lastkey, &doit_select_chunk, &sc); 
+	    traverse_backwards(tb, stack, lastkey, NULL, &doit_select_chunk, &sc);
 	} else {
-	    traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc); 
+	    traverse_forward(tb, stack, lastkey, NULL, &doit_select_chunk, &sc);
 	}
     } else {
 	if (reverse) {
-	    traverse_forward(tb, stack, lastkey, &doit_select, &sc);
+	    traverse_forward(tb, stack, lastkey, NULL, &doit_select, &sc);
 	} else {
-	    traverse_backwards(tb, stack, lastkey, &doit_select, &sc);
+	    traverse_backwards(tb, stack, lastkey, NULL, &doit_select, &sc);
 	}
     }
     release_stack(tb,stack);
@@ -1026,10 +1002,9 @@ static int db_select_continue_tree(Process *p,
 	    }
 
 	    key = GETKEY(tb, sc.lastobj);
-
-	    sz = size_object(key);
+	    sz = size_object_rel(key,sc.lastobj);
 	    hp = HAlloc(p, 9 + sz);
-	    key = copy_struct(key, sz, &hp, &MSO(p));
+	    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
 	    continuation = TUPLE8
 		(hp,
 		 tptr[1],
@@ -1050,8 +1025,8 @@ static int db_select_continue_tree(Process *p,
     key = GETKEY(tb, sc.lastobj);
     if (chunk_size) {
 	if (end_condition != NIL && 
-	    ((!reverse && cmp_partly_bound(end_condition,key) < 0) ||
-	     (reverse && cmp_partly_bound(end_condition,key) > 0))) { 
+	    ((!reverse && cmp_partly_bound(end_condition,key,sc.lastobj) < 0) ||
+	     (reverse && cmp_partly_bound(end_condition,key,sc.lastobj) > 0))) {
 	    /* done anyway */
 	    if (!sc.got) {
 		RET_TO_BIF(am_EOT, DB_ERROR_NONE);
@@ -1063,16 +1038,16 @@ static int db_select_continue_tree(Process *p,
 	}
     } else {
 	if (end_condition != NIL && 
-	    ((!reverse && cmp_partly_bound(end_condition,key) > 0) ||
-	     (reverse && cmp_partly_bound(end_condition,key) < 0))) { 
+	    ((!reverse && cmp_partly_bound(end_condition,key,sc.lastobj) > 0) ||
+	     (reverse && cmp_partly_bound(end_condition,key,sc.lastobj) < 0))) {
 	    /* done anyway */
 	    RET_TO_BIF(sc.accum,DB_ERROR_NONE);
 	}
     }
     /* Not done yet, let's trap. */
-    sz = size_object(key);
+    sz = size_object_rel(key,sc.lastobj);
     hp = HAlloc(p, 9 + sz);
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
     continuation = TUPLE8
 	(hp,
 	 tptr[1],
@@ -1099,6 +1074,7 @@ static int db_select_tree(Process *p, DbTable *tbl,
     struct select_context sc;
     struct mp_info mpi;
     Eterm lastkey = THE_NON_VALUE;
+    Eterm* lk_base = NULL;
     Eterm key;
     Eterm continuation;
     unsigned sz;
@@ -1140,7 +1116,7 @@ static int db_select_tree(Process *p, DbTable *tbl,
     sc.all_objects = mpi.all_objects;
 
     if (!mpi.got_partial && mpi.some_limitation && 
-	cmp(mpi.least,mpi.most) == 0) {
+	CMP(mpi.least,mpi.most) == 0) {
 	doit_select(tb,mpi.save_term,&sc,0 /* direction doesn't matter */);
 	RET_TO_BIF(sc.accum,DB_ERROR_NONE);
     }
@@ -1150,20 +1126,20 @@ static int db_select_tree(Process *p, DbTable *tbl,
 	if (mpi.some_limitation) {
 	    if ((this = find_prev_from_pb_key(tb, stack, mpi.least)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
+		lk_base = this->dbterm.tpl;
 	    }
 	    sc.end_condition = mpi.most;
 	}
-	
-	traverse_forward(tb, stack, lastkey, &doit_select, &sc);
+	traverse_forward(tb, stack, lastkey, lk_base, &doit_select, &sc);
     } else {
 	if (mpi.some_limitation) {
 	    if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
+		lk_base = this->dbterm.tpl;
 	    }
 	    sc.end_condition = mpi.least;
 	}
-	
-	traverse_backwards(tb, stack, lastkey, &doit_select, &sc);
+	traverse_backwards(tb, stack, lastkey, lk_base, &doit_select, &sc);
     }
     release_stack(tb,stack);
 #ifdef HARDDEBUG
@@ -1176,9 +1152,9 @@ static int db_select_tree(Process *p, DbTable *tbl,
     }
 
     key = GETKEY(tb, sc.lastobj);
-    sz = size_object(key);
+    sz = size_object_rel(key, sc.lastobj);
     hp = HAlloc(p, 9 + sz + PROC_BIN_SIZE);
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
     if (mpi.all_objects)
 	(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
     mpb=db_make_mp_binary(p,mpi.mp,&hp);
@@ -1259,7 +1235,7 @@ static int db_select_count_continue_tree(Process *p,
     }
 
     stack = get_any_stack(tb);
-    traverse_backwards(tb, stack, lastkey, &doit_select_count, &sc);
+    traverse_backwards(tb, stack, lastkey, NULL, &doit_select_count, &sc);
     release_stack(tb,stack);
 
     BUMP_REDS(p, 1000 - sc.max);
@@ -1269,12 +1245,12 @@ static int db_select_count_continue_tree(Process *p,
     }	
     key = GETKEY(tb, sc.lastobj);
     if (end_condition != NIL && 
-	(cmp_partly_bound(end_condition,key) > 0)) { 
+	(cmp_partly_bound(end_condition,key,sc.lastobj) > 0)) {
 	/* done anyway */
 	RET_TO_BIF(make_small(sc.got),DB_ERROR_NONE);
     }
     /* Not done yet, let's trap. */
-    sz = size_object(key);
+    sz = size_object_rel(key, sc.lastobj);
     if (IS_USMALL(0, sc.got)) {
 	hp = HAlloc(p, sz + 6);
 	egot = make_small(sc.got);
@@ -1284,7 +1260,7 @@ static int db_select_count_continue_tree(Process *p,
 	egot = uint_to_big(sc.got, hp);
 	hp += BIG_UINT_HEAP_SIZE;
     }
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
     continuation = TUPLE5
 	(hp,
 	 tptr[1],
@@ -1307,6 +1283,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl,
     struct select_count_context sc;
     struct mp_info mpi;
     Eterm lastkey = THE_NON_VALUE;
+    Eterm* lk_base = NULL;
     Eterm key;
     Eterm continuation;
     unsigned sz;
@@ -1347,7 +1324,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl,
     sc.all_objects = mpi.all_objects;
 
     if (!mpi.got_partial && mpi.some_limitation && 
-	cmp(mpi.least,mpi.most) == 0) {
+	CMP(mpi.least,mpi.most) == 0) {
 	doit_select_count(tb,mpi.save_term,&sc,0 /* dummy */);
 	RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE);
     }
@@ -1356,11 +1333,12 @@ static int db_select_count_tree(Process *p, DbTable *tbl,
     if (mpi.some_limitation) {
 	if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
 	    lastkey = GETKEY(tb, this->dbterm.tpl);
+	    lk_base = this->dbterm.tpl;
 	}
 	sc.end_condition = mpi.least;
     }
     
-    traverse_backwards(tb, stack, lastkey, &doit_select_count, &sc);
+    traverse_backwards(tb, stack, lastkey, lk_base, &doit_select_count, &sc);
     release_stack(tb,stack);
     BUMP_REDS(p, 1000 - sc.max);
     if (sc.max > 0) {
@@ -1368,7 +1346,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl,
     }
 
     key = GETKEY(tb, sc.lastobj);
-    sz = size_object(key);
+    sz = size_object_rel(key, sc.lastobj);
     if (IS_USMALL(0, sc.got)) {
 	hp = HAlloc(p, sz + PROC_BIN_SIZE + 6);
 	egot = make_small(sc.got);
@@ -1378,7 +1356,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl,
 	egot = uint_to_big(sc.got, hp);
 	hp += BIG_UINT_HEAP_SIZE;
     }
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
     if (mpi.all_objects)
 	(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
     mpb = db_make_mp_binary(p,mpi.mp,&hp);
@@ -1409,6 +1387,7 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
     struct select_context sc;
     struct mp_info mpi;
     Eterm lastkey = THE_NON_VALUE;
+    Eterm* lk_base = NULL;
     Eterm key;
     Eterm continuation;
     unsigned sz;
@@ -1450,7 +1429,7 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
     sc.all_objects = mpi.all_objects;
 
     if (!mpi.got_partial && mpi.some_limitation && 
-	cmp(mpi.least,mpi.most) == 0) {
+	CMP(mpi.least,mpi.most) == 0) {
 	doit_select(tb,mpi.save_term,&sc, 0 /* direction doesn't matter */);
 	if (sc.accum != NIL) {
 	    hp=HAlloc(p, 3);
@@ -1465,20 +1444,20 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
 	if (mpi.some_limitation) {
 	    if ((this = find_next_from_pb_key(tb, stack, mpi.most)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
+		lk_base = this->dbterm.tpl;
 	    }
 	    sc.end_condition = mpi.least;
 	}
-
-	traverse_backwards(tb, stack, lastkey, &doit_select_chunk, &sc);
+	traverse_backwards(tb, stack, lastkey, lk_base, &doit_select_chunk, &sc);
     } else {
 	if (mpi.some_limitation) {
 	    if ((this = find_prev_from_pb_key(tb, stack, mpi.least)) != NULL) {
 		lastkey = GETKEY(tb, this->dbterm.tpl);
+		lk_base = this->dbterm.tpl;
 	    }
 	    sc.end_condition = mpi.most;
 	}
-
-	traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc);
+	traverse_forward(tb, stack, lastkey, lk_base, &doit_select_chunk, &sc);
     }
     release_stack(tb,stack);
 
@@ -1503,9 +1482,9 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
 	}
 
 	key = GETKEY(tb, sc.lastobj);
-	sz = size_object(key);
+	sz = size_object_rel(key, sc.lastobj);
 	hp = HAlloc(p, 9 + sz + PROC_BIN_SIZE);
-	key = copy_struct(key, sz, &hp, &MSO(p));
+	key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
 	if (mpi.all_objects)
 	    (mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
 	mpb = db_make_mp_binary(p,mpi.mp,&hp);
@@ -1528,9 +1507,9 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
     }
 
     key = GETKEY(tb, sc.lastobj);
-    sz = size_object(key);
+    sz = size_object_rel(key, sc.lastobj);
     hp = HAlloc(p, 9 + sz + PROC_BIN_SIZE);
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
 
     if (mpi.all_objects)
 	(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
@@ -1606,7 +1585,7 @@ static int db_select_delete_continue_tree(Process *p,
     sc.keypos = tb->common.keypos;
 
     ASSERT(!erts_smp_atomic_read(&tb->is_stack_busy));
-    traverse_backwards(tb, &tb->static_stack, lastkey, &doit_select_delete, &sc);
+    traverse_backwards(tb, &tb->static_stack, lastkey, NULL, &doit_select_delete, &sc);
 
     BUMP_REDS(p, 1000 - sc.max);
 
@@ -1615,11 +1594,11 @@ static int db_select_delete_continue_tree(Process *p,
     }	
     key = GETKEY(tb, (sc.lastterm)->dbterm.tpl);
     if (end_condition != NIL && 
-	cmp_partly_bound(end_condition,key) > 0) { /* done anyway */
+	cmp_partly_bound(end_condition,key,sc.lastterm->dbterm.tpl) > 0) { /* done anyway */
 	RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE);
     }
     /* Not done yet, let's trap. */
-    sz = size_object(key);
+    sz = size_object_rel(key, sc.lastterm->dbterm.tpl);
     if (IS_USMALL(0, sc.accum)) {
 	hp = HAlloc(p, sz + 6);
 	eaccsum = make_small(sc.accum);
@@ -1629,7 +1608,7 @@ static int db_select_delete_continue_tree(Process *p,
 	eaccsum = uint_to_big(sc.accum, hp);
 	hp += BIG_UINT_HEAP_SIZE;
     }
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastterm->dbterm.tpl, NULL);
     continuation = TUPLE5
 	(hp,
 	 tptr[1],
@@ -1650,6 +1629,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
     struct select_delete_context sc;
     struct mp_info mpi;
     Eterm lastkey = THE_NON_VALUE;
+    Eterm* lk_base = NULL;
     Eterm key;
     Eterm continuation;
     unsigned sz;
@@ -1693,7 +1673,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
     sc.mp = mpi.mp;
 
     if (!mpi.got_partial && mpi.some_limitation && 
-	cmp(mpi.least,mpi.most) == 0) {
+	CMP(mpi.least,mpi.most) == 0) {
 	doit_select_delete(tb,mpi.save_term,&sc, 0 /* direction doesn't 
 						      matter */);
 	RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE);
@@ -1702,11 +1682,12 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
     if (mpi.some_limitation) {
 	if ((this = find_next_from_pb_key(tb, &tb->static_stack, mpi.most)) != NULL) {
 	    lastkey = GETKEY(tb, this->dbterm.tpl);
+	    lk_base = this->dbterm.tpl;
 	}
 	sc.end_condition = mpi.least;
     }
 
-    traverse_backwards(tb, &tb->static_stack, lastkey, &doit_select_delete, &sc);
+    traverse_backwards(tb, &tb->static_stack, lastkey, lk_base, &doit_select_delete, &sc);
     BUMP_REDS(p, 1000 - sc.max);
 
     if (sc.max > 0) {
@@ -1714,7 +1695,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
     }
 
     key = GETKEY(tb, (sc.lastterm)->dbterm.tpl);
-    sz = size_object(key);
+    sz = size_object_rel(key, sc.lastterm->dbterm.tpl);
     if (IS_USMALL(0, sc.accum)) {
 	hp = HAlloc(p, sz + PROC_BIN_SIZE + 6);
 	eaccsum = make_small(sc.accum);
@@ -1724,7 +1705,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
 	eaccsum = uint_to_big(sc.accum, hp);
 	hp += BIG_UINT_HEAP_SIZE;
     }
-    key = copy_struct(key, sz, &hp, &MSO(p));
+    key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastterm->dbterm.tpl, NULL);
     mpb = db_make_mp_binary(p,mpi.mp,&hp);
     
     continuation = TUPLE5
@@ -1842,7 +1823,7 @@ do_db_tree_foreach_offheap(TreeDbTerm *tdbt,
 }
 
 static TreeDbTerm *linkout_tree(DbTableTree *tb, 
-				Eterm key)
+				Eterm key, Eterm* key_base)
 {
     TreeDbTerm **tstack[STACK_NEED];
     int tpos = 0;
@@ -1865,7 +1846,7 @@ static TreeDbTerm *linkout_tree(DbTableTree *tb,
     for (;;) {
 	if (!*this) { /* Failure */
 	    return NULL;
-	} else if ((c = cmp(key,GETKEY(tb,(*this)->dbterm.tpl))) < 0) { 
+	} else if ((c = cmp_key(tb, key, key_base, *this)) < 0) {
 	    dstack[dpos++] = DIR_LEFT;
 	    tstack[tpos++] = this;
 	    this = &((*this)->left);
@@ -1929,7 +1910,7 @@ static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
     for (;;) {
 	if (!*this) { /* Failure */
 	    return NULL;
-	} else if ((c = cmp(key,GETKEY(tb,(*this)->dbterm.tpl))) < 0) { 
+	} else if ((c = cmp_key(tb,key,NULL,*this)) < 0) {
 	    dstack[dpos++] = DIR_LEFT;
 	    tstack[tpos++] = this;
 	    this = &((*this)->left);
@@ -2324,14 +2305,15 @@ done:
  * Find next and previous in sort order
  */
 
-static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack, Eterm key)
+static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack,
+			     Eterm key, Eterm* key_base)
 {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
     Sint c;
 
     if(( this = TOP_NODE(stack)) != NULL) {
-	if (!CMP_EQ(GETKEY(tb, this->dbterm.tpl),key)) {
+	if (!cmp_key_eq(tb,key,key_base,this)) {
 	    /* Start from the beginning */
 	    stack->pos = stack->slot = 0;
 	}
@@ -2341,14 +2323,14 @@ static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack, Eterm key)
 	    return NULL;
 	for (;;) {
 	    PUSH_NODE(stack, this);
-	    if (( c = cmp(GETKEY(tb, this->dbterm.tpl),key) ) < 0) {
+	    if (( c = cmp_key(tb,key,key_base,this) ) > 0) {
 		if (this->right == NULL) /* We are at the previos 
 					    and the element does
 					    not exist */
 		    break;
 		else
 		    this = this->right;
-	    } else if (c > 0) {
+	    } else if (c < 0) {
 		if (this->left == NULL) /* Done */
 		    return this;
 		else
@@ -2381,14 +2363,15 @@ 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(DbTableTree *tb, DbTreeStack* stack,
+			     Eterm key, Eterm* key_base)
 {
     TreeDbTerm *this;
     TreeDbTerm *tmp;
     Sint c;
 
     if(( this = TOP_NODE(stack)) != NULL) {
-	if (!CMP_EQ(GETKEY(tb, this->dbterm.tpl),key)) {
+	if (!cmp_key_eq(tb,key,key_base,this)) {
 	    /* Start from the beginning */
 	    stack->pos = stack->slot = 0;
 	}
@@ -2398,14 +2381,14 @@ static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack, Eterm key)
 	    return NULL;
 	for (;;) {
 	    PUSH_NODE(stack, this);
-	    if (( c = cmp(GETKEY(tb, this->dbterm.tpl),key) ) > 0) {
+	    if (( c = cmp_key(tb,key,key_base,this) ) < 0) {
 		if (this->left == NULL) /* We are at the next 
 					   and the element does
 					   not exist */
 		    break;
 		else
 		    this = this->left;
-	    } else if (c < 0) {
+	    } else if (c > 0) {
 		if (this->right == NULL) /* Done */
 		    return this;
 		else
@@ -2451,7 +2434,8 @@ static TreeDbTerm *find_next_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
 	return NULL;
     for (;;) {
 	PUSH_NODE(stack, this);
-	if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl)) ) >= 0) {
+	if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl),
+				   this->dbterm.tpl) ) >= 0) {
 	    if (this->right == NULL) {
 		do {
 		    tmp = POP_NODE(stack);
@@ -2484,7 +2468,8 @@ static TreeDbTerm *find_prev_from_pb_key(DbTableTree *tb, DbTreeStack* stack,
 	return NULL;
     for (;;) {
 	PUSH_NODE(stack, this);
-	if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl)) ) <= 0) {
+	if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl),
+				   this->dbterm.tpl) ) <= 0) {
 	    if (this->left == NULL) {
 		do {
 		    tmp = POP_NODE(stack);
@@ -2514,12 +2499,11 @@ static TreeDbTerm *find_node(DbTableTree *tb, Eterm key)
     Sint res;
     DbTreeStack* stack = get_static_stack(tb);
 
-    if(!stack || EMPTY_NODE(stack) 
-       || !CMP_EQ(GETKEY(tb, ( this = TOP_NODE(stack) )->dbterm.tpl), key)) {
+    if(!stack || EMPTY_NODE(stack)
+       || !cmp_key_eq(tb, key, NULL, (this=TOP_NODE(stack)))) {
 
 	this = tb->root;
-	while (this != NULL && 
-	       ( res = cmp(key, GETKEY(tb, this->dbterm.tpl)) ) != 0) {
+	while (this != NULL && (res = cmp_key(tb,key,NULL,this)) != 0) {
 	    if (res < 0)
 		this = this->left;
 	    else
@@ -2541,8 +2525,7 @@ static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
     Sint res;
 
     this = &tb->root;
-    while ((*this) != NULL && 
-	   ( res = cmp(key, GETKEY(tb, (*this)->dbterm.tpl)) ) != 0) {
+    while ((*this) != NULL && (res = cmp_key(tb, key, NULL, *this)) != 0) {
 	if (res < 0)
 	    this = &((*this)->left);
 	else
@@ -2565,6 +2548,9 @@ static int db_lookup_dbterm_tree(DbTable *tbl, Eterm key, DbUpdateHandle* handle
     handle->mustResize = 0;
     handle->bp = (void**) pp;
     handle->new_size = (*pp)->dbterm.size;
+    #if HALFWORD_HEAP
+    handle->new_tuple = handle->dbterm->tpl;
+    #endif
     return 1;
 }
 
@@ -2589,7 +2575,7 @@ static void db_finalize_dbterm_tree(DbUpdateHandle* handle)
  */
 static void traverse_backwards(DbTableTree *tb,
 			       DbTreeStack* stack,
-			       Eterm lastkey,
+			       Eterm lastkey, Eterm* lk_base,
 			       int (*doit)(DbTableTree *,
 					   TreeDbTerm *,
 					   void *,
@@ -2608,15 +2594,16 @@ 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, stack, GETKEY(tb, this->dbterm.tpl),
+			 this->dbterm.tpl);
 	if (!((*doit)(tb, this, context, 0)))
 	    return;
     } else {
-	next = find_prev(tb, stack, lastkey);
+	next = find_prev(tb, stack, lastkey, lk_base);
     }
 
     while ((this = next) != NULL) {
-	next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl));
+	next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl), this->dbterm.tpl);
 	if (!((*doit)(tb, this, context, 0)))
 	    return;
     }
@@ -2627,7 +2614,7 @@ static void traverse_backwards(DbTableTree *tb,
  */
 static void traverse_forward(DbTableTree *tb,
 			     DbTreeStack* stack,
-			     Eterm lastkey,
+			     Eterm lastkey, Eterm* lk_base,
 			     int (*doit)(DbTableTree *,
 					 TreeDbTerm *,
 					 void *,
@@ -2646,15 +2633,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, stack, GETKEY(tb, this->dbterm.tpl), this->dbterm.tpl);
 	if (!((*doit)(tb, this, context, 1)))
 	    return;
     } else {
-	next = find_next(tb, stack, lastkey);
+	next = find_next(tb, stack, lastkey, lk_base);
     }
 
     while ((this = next) != NULL) {
-	next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl));
+	next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl), this->dbterm.tpl);
 	if (!((*doit)(tb, this, context, 1)))
 	    return;
     }
@@ -2680,7 +2667,7 @@ static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
 	if (( this = find_node(tb, key) ) == NULL) {
 	    return -1;
 	}
-	*ret = this; 
+	*ret = this;
 	return 1;
     } else if (partly_bound != NULL && key != am_Underscore && 
 	       db_is_variable(key) < 0)
@@ -2691,7 +2678,7 @@ static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
 
 
 
-static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done)
+static Sint do_cmp_partly_bound(Eterm a, Eterm b, Eterm* b_base, int *done)
 {
     Eterm* aa;
     Eterm* bb;
@@ -2705,44 +2692,44 @@ static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done)
 	*done = 1;
 	return 0;
     }
-    if (a == b)
+    if (is_same(a,NULL,b,b_base))
 	return 0;
     
     switch (a & _TAG_PRIMARY_MASK) {
     case TAG_PRIMARY_LIST:
 	if (!is_list(b)) {
-	    return cmp(a,b);
+	    return cmp_rel(a,NULL,b,b_base);
 	}
 	aa = list_val(a);
-	bb = list_val(b);
+	bb = list_val_rel(b,b_base);
 	while (1) {
-	    if ((j = do_cmp_partly_bound(*aa++, *bb++, done)) != 0 || *done) 
+	    if ((j = do_cmp_partly_bound(*aa++, *bb++, b_base, done)) != 0 || *done)
 		return j;
 	    if (*aa==*bb)
 		return 0;
 	    if (is_not_list(*aa) || is_not_list(*bb))
-		return do_cmp_partly_bound(*aa, *bb, done);
+		return do_cmp_partly_bound(*aa, *bb, b_base, done);
 	    aa = list_val(*aa);
-	    bb = list_val(*bb);
+	    bb = list_val_rel(*bb,b_base);
 	}
     case TAG_PRIMARY_BOXED:
 	if ((b & _TAG_PRIMARY_MASK) != TAG_PRIMARY_BOXED) {
-	    return cmp(a,b);
+	    return cmp_rel(a,NULL,b,b_base);
 	}
 	a_hdr = ((*boxed_val(a)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
-	b_hdr = ((*boxed_val(b)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
+	b_hdr = ((*boxed_val_rel(b,b_base)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
 	if (a_hdr != b_hdr) {
-	    return cmp(a, b);
+	    return cmp_rel(a, NULL, b, b_base);
 	}
 	if (a_hdr == (_TAG_HEADER_ARITYVAL >> _TAG_PRIMARY_SIZE)) {
 	    aa = tuple_val(a);
-	    bb = tuple_val(b);
+	    bb = tuple_val_rel(b, b_base);
 	    /* compare the arities */
 	    i = arityval(*aa);	/* get the arity*/
 	    if (i < arityval(*bb)) return(-1);
 	    if (i > arityval(*bb)) return(1);
 	    while (i--) {
-		if ((j = do_cmp_partly_bound(*++aa, *++bb, done)) != 0 
+		if ((j = do_cmp_partly_bound(*++aa, *++bb, b_base, done)) != 0
 		    || *done) 
 		    return j;
 	    }
@@ -2750,14 +2737,14 @@ static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done)
 	}
 	/* Drop through */
       default:
-	  return cmp(a, b);
+	  return cmp_rel(a, NULL, b, b_base);
     }
 }
 
-static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key) 
+static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key, Eterm* bk_base)
 {
     int done = 0;
-    Sint ret = do_cmp_partly_bound(partly_bound_key, bound_key, &done);
+    Sint ret = do_cmp_partly_bound(partly_bound_key, bound_key, bk_base, &done);
 #ifdef HARDDEBUG
     erts_fprintf(stderr,"\ncmp_partly_bound: %T", partly_bound_key);
     if (ret < 0)
@@ -2766,7 +2753,7 @@ static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key)
 	erts_fprintf(stderr," > ");
     else
 	erts_fprintf(stderr," == ");
-    erts_fprintf(stderr,"%T\n",bound_key);
+    erts_fprintf(stderr,"%T\n",bound_key);  // SVERK: printing rterm
 #endif
     return ret;
 }
@@ -2853,7 +2840,7 @@ static int do_partly_bound_can_match_lesser(Eterm a, Eterm b,
 
     if (not_eq_tags(a,b)) {
 	*done = 1;
-	return (cmp(a, b) < 0) ? 1 : 0;
+	return (CMP(a, b) < 0) ? 1 : 0;
     }
 
     /* we now know that tags are the same */
@@ -2889,7 +2876,7 @@ static int do_partly_bound_can_match_lesser(Eterm a, Eterm b,
 	    bb = list_val(*bb);
 	}
     default:
-	if((i = cmp(a, b)) != 0) {
+	if((i = CMP(a, b)) != 0) {
 	    *done = 1;
 	}
 	return (i < 0) ? 1 : 0;
@@ -2924,7 +2911,7 @@ static int do_partly_bound_can_match_greater(Eterm a, Eterm b,
 
     if (not_eq_tags(a,b)) {
 	*done = 1;
-	return (cmp(a, b) > 0) ? 1 : 0;
+	return (CMP(a, b) > 0) ? 1 : 0;
     }
 
     /* we now know that tags are the same */
@@ -2960,7 +2947,7 @@ static int do_partly_bound_can_match_greater(Eterm a, Eterm b,
 	    bb = list_val(*bb);
 	}
     default:
-	if((i = cmp(a, b)) != 0) {
+	if((i = CMP(a, b)) != 0) {
 	    *done = 1;
 	}
 	return (i > 0) ? 1 : 0;
@@ -2983,12 +2970,12 @@ static int doit_select(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     if (sc->end_condition != NIL && 
 	((forward && 
 	  cmp_partly_bound(sc->end_condition, 
-			   GETKEY_WITH_POS(sc->keypos, 
-					   this->dbterm.tpl)) < 0) ||
+			   GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
+			   this->dbterm.tpl) < 0) ||
 	 (!forward && 
 	  cmp_partly_bound(sc->end_condition, 
-			   GETKEY_WITH_POS(sc->keypos, 
-					   this->dbterm.tpl)) > 0))) {
+			   GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
+			   this->dbterm.tpl) > 0))) {
 	return 0;
     }
     ret = db_prog_match_and_copy(&tb->common,sc->p,sc->mp,sc->all_objects,
@@ -3020,8 +3007,8 @@ static int doit_select_count(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     /* Always backwards traversing */
     if (sc->end_condition != NIL && 
 	(cmp_partly_bound(sc->end_condition, 
-			  GETKEY_WITH_POS(sc->keypos, 
-					  this->dbterm.tpl)) > 0)) {
+			  GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
+			  this->dbterm.tpl) > 0)) {
 	return 0;
     }
     ret = db_prog_match_and_copy(&tb->common, sc->p, sc->mp, 0,
@@ -3047,12 +3034,12 @@ static int doit_select_chunk(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     if (sc->end_condition != NIL && 
 	((forward && 
 	  cmp_partly_bound(sc->end_condition, 
-			   GETKEY_WITH_POS(sc->keypos, 
-					   this->dbterm.tpl)) < 0) ||
+			   GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
+			   this->dbterm.tpl) < 0) ||
 	 (!forward && 
 	  cmp_partly_bound(sc->end_condition, 
-			   GETKEY_WITH_POS(sc->keypos, 
-					   this->dbterm.tpl)) > 0))) {
+			   GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
+			   this->dbterm.tpl) > 0))) {
 	return 0;
     }
 
@@ -3090,14 +3077,14 @@ static int doit_select_delete(DbTableTree *tb, TreeDbTerm *this, void *ptr,
     
     if (sc->end_condition != NIL && 
 	cmp_partly_bound(sc->end_condition, 
-			 GETKEY_WITH_POS(sc->keypos, 
-					 this->dbterm.tpl)) > 0)
+			 GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
+			 this->dbterm.tpl) > 0)
 	return 0;
     ret = db_prog_match_and_copy(&tb->common, sc->p, sc->mp, 0,
 				 &this->dbterm, NULL, 0);
     if (ret == am_true) {
 	key = GETKEY(sc->tb, this->dbterm.tpl);
-	linkout_tree(sc->tb, key);
+	linkout_tree(sc->tb, key, this->dbterm.tpl);
 	sc->erase_lastterm = 1;
 	++sc->accum;
     }