aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_db_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_db_tree.c')
-rw-r--r--erts/emulator/beam/erl_db_tree.c355
1 files changed, 190 insertions, 165 deletions
diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c
index 25029ba90f..02d211a4bb 100644
--- a/erts/emulator/beam/erl_db_tree.c
+++ b/erts/emulator/beam/erl_db_tree.c
@@ -1,18 +1,19 @@
/*
* %CopyrightBegin%
*
- * Copyright Ericsson AB 1998-2013. All Rights Reserved.
+ * Copyright Ericsson AB 1998-2016. All Rights Reserved.
*
- * The contents of this file are subject to the Erlang Public License,
- * Version 1.1, (the "License"); you may not use this file except in
- * compliance with the License. You should have received a copy of the
- * Erlang Public License along with this software. If not, it can be
- * retrieved online at http://www.erlang.org/.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
*
- * Software distributed under the License is distributed on an "AS IS"
- * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
- * the License for the specific language governing rights and limitations
- * under the License.
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
*
* %CopyrightEnd%
*/
@@ -279,7 +280,7 @@ struct select_delete_context {
/*
** Forward declarations
*/
-static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key, Eterm* key_base);
+static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key);
static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
Eterm object);
static int do_free_tree_cont(DbTableTree *tb, int num_left);
@@ -290,15 +291,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, Eterm* kbase);
-static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack*, Eterm key, Eterm* kbase);
+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,
DbTreeStack*,
- Eterm lastkey, Eterm* lk_base,
+ Eterm lastkey,
int (*doit)(DbTableTree *tb,
TreeDbTerm *,
void *,
@@ -306,7 +307,7 @@ static void traverse_backwards(DbTableTree *tb,
void *context);
static void traverse_forward(DbTableTree *tb,
DbTreeStack*,
- Eterm lastkey, Eterm* lk_base,
+ Eterm lastkey,
int (*doit)(DbTableTree *tb,
TreeDbTerm *,
void *,
@@ -314,8 +315,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, Eterm* bk_base);
-static Sint do_cmp_partly_bound(Eterm a, Eterm b, Eterm* b_base, int *done);
+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,
struct mp_info *mpi);
@@ -383,6 +384,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
Eterm pattern, Eterm *ret);
static int db_select_delete_continue_tree(Process *p, DbTable *tbl,
Eterm continuation, Eterm *ret);
+static int db_take_tree(Process *, DbTable *, Eterm, Eterm *);
static void db_print_tree(int to, void *to_arg,
int show, DbTable *tbl);
static int db_free_table_tree(DbTable *tbl);
@@ -398,8 +400,11 @@ static int db_delete_all_objects_tree(Process* p, DbTable* tbl);
#ifdef HARDDEBUG
static void db_check_table_tree(DbTable *tbl);
#endif
-static int db_lookup_dbterm_tree(DbTable *, Eterm key, DbUpdateHandle*);
-static void db_finalize_dbterm_tree(DbUpdateHandle*);
+static int
+db_lookup_dbterm_tree(Process *, DbTable *, Eterm key, Eterm obj,
+ DbUpdateHandle*);
+static void
+db_finalize_dbterm_tree(int cret, DbUpdateHandle *);
/*
** Static variables
@@ -431,6 +436,7 @@ DbTableMethod db_tree =
db_select_delete_continue_tree,
db_select_count_tree,
db_select_count_continue_tree,
+ db_take_tree,
db_delete_all_objects_tree,
db_free_table_tree,
db_free_table_continue_tree,
@@ -485,7 +491,7 @@ static int db_first_tree(Process *p, DbTable *tbl, Eterm *ret)
*ret = am_EOT;
return DB_ERROR_NONE;
}
- /* Walk down to the tree to the left */
+ /* Walk down the tree to the left */
if ((stack = get_static_stack(tb)) != NULL) {
stack->pos = stack->slot = 0;
}
@@ -511,7 +517,7 @@ static int db_next_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
if (is_atom(key) && key == am_EOT)
return DB_ERROR_BADKEY;
stack = get_any_stack(tb);
- this = find_next(tb, stack, key, NULL);
+ this = find_next(tb, stack, key);
release_stack(tb,stack);
if (this == NULL) {
*ret = am_EOT;
@@ -531,7 +537,7 @@ static int db_last_tree(Process *p, DbTable *tbl, Eterm *ret)
*ret = am_EOT;
return DB_ERROR_NONE;
}
- /* Walk down to the tree to the left */
+ /* Walk down the tree to the right */
if ((stack = get_static_stack(tb)) != NULL) {
stack->pos = stack->slot = 0;
}
@@ -557,7 +563,7 @@ static int db_prev_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
if (is_atom(key) && key == am_EOT)
return DB_ERROR_BADKEY;
stack = get_any_stack(tb);
- this = find_prev(tb, stack, key, NULL);
+ this = find_prev(tb, stack, key);
release_stack(tb,stack);
if (this == NULL) {
*ret = am_EOT;
@@ -567,19 +573,13 @@ 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, Eterm* key_base,
- TreeDbTerm* obj)
-{
- return cmp_rel(key, key_base,
- GETKEY(tb,obj->dbterm.tpl), obj->dbterm.tpl);
+static ERTS_INLINE Sint cmp_key(DbTableTree* tb, Eterm key, TreeDbTerm* obj) {
+ return CMP(key, GETKEY(tb,obj->dbterm.tpl));
}
-static ERTS_INLINE int cmp_key_eq(DbTableTree* tb, Eterm key, Eterm* key_base,
- TreeDbTerm* obj)
-{
+static ERTS_INLINE int cmp_key_eq(DbTableTree* tb, Eterm key, 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;
+ return is_same(key, obj_key) || CMP(key, obj_key) == 0;
}
static int db_put_tree(DbTable *tbl, Eterm obj, int key_clash_fail)
@@ -613,7 +613,7 @@ 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(tb, key, NULL, *this)) < 0) {
+ } else if ((c = cmp_key(tb, key, *this)) < 0) {
/* go lefts */
dstack[dpos++] = DIR_LEFT;
tstack[tpos++] = this;
@@ -768,7 +768,7 @@ static int db_erase_tree(DbTable *tbl, Eterm key, Eterm *ret)
*ret = am_true;
- if ((res = linkout_tree(tb, key, NULL)) != NULL) {
+ if ((res = linkout_tree(tb, key)) != NULL) {
free_term(tb, res);
}
return DB_ERROR_NONE;
@@ -964,15 +964,15 @@ static int db_select_continue_tree(Process *p,
stack = get_any_stack(tb);
if (chunk_size) {
if (reverse) {
- traverse_backwards(tb, stack, lastkey, NULL, &doit_select_chunk, &sc);
+ traverse_backwards(tb, stack, lastkey, &doit_select_chunk, &sc);
} else {
- traverse_forward(tb, stack, lastkey, NULL, &doit_select_chunk, &sc);
+ traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc);
}
} else {
if (reverse) {
- traverse_forward(tb, stack, lastkey, NULL, &doit_select, &sc);
+ traverse_forward(tb, stack, lastkey, &doit_select, &sc);
} else {
- traverse_backwards(tb, stack, lastkey, NULL, &doit_select, &sc);
+ traverse_backwards(tb, stack, lastkey, &doit_select, &sc);
}
}
release_stack(tb,stack);
@@ -997,9 +997,9 @@ static int db_select_continue_tree(Process *p,
}
key = GETKEY(tb, sc.lastobj);
- sz = size_object_rel(key,sc.lastobj);
+ sz = size_object(key);
hp = HAlloc(p, 9 + sz);
- key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
continuation = TUPLE8
(hp,
tptr[1],
@@ -1020,8 +1020,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,sc.lastobj) < 0) ||
- (reverse && cmp_partly_bound(end_condition,key,sc.lastobj) > 0))) {
+ ((!reverse && cmp_partly_bound(end_condition,key) < 0) ||
+ (reverse && cmp_partly_bound(end_condition,key) > 0))) {
/* done anyway */
if (!sc.got) {
RET_TO_BIF(am_EOT, DB_ERROR_NONE);
@@ -1033,16 +1033,16 @@ static int db_select_continue_tree(Process *p,
}
} else {
if (end_condition != NIL &&
- ((!reverse && cmp_partly_bound(end_condition,key,sc.lastobj) > 0) ||
- (reverse && cmp_partly_bound(end_condition,key,sc.lastobj) < 0))) {
+ ((!reverse && cmp_partly_bound(end_condition,key) > 0) ||
+ (reverse && cmp_partly_bound(end_condition,key) < 0))) {
/* done anyway */
RET_TO_BIF(sc.accum,DB_ERROR_NONE);
}
}
/* Not done yet, let's trap. */
- sz = size_object_rel(key,sc.lastobj);
+ sz = size_object(key);
hp = HAlloc(p, 9 + sz);
- key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
continuation = TUPLE8
(hp,
tptr[1],
@@ -1069,7 +1069,6 @@ 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;
@@ -1111,7 +1110,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_EQ(mpi.least,mpi.most)) {
doit_select(tb,mpi.save_term,&sc,0 /* direction doesn't matter */);
RET_TO_BIF(sc.accum,DB_ERROR_NONE);
}
@@ -1121,20 +1120,18 @@ 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, lk_base, &doit_select, &sc);
+ traverse_forward(tb, stack, lastkey, &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, lk_base, &doit_select, &sc);
+ traverse_backwards(tb, stack, lastkey, &doit_select, &sc);
}
release_stack(tb,stack);
#ifdef HARDDEBUG
@@ -1147,9 +1144,9 @@ static int db_select_tree(Process *p, DbTable *tbl,
}
key = GETKEY(tb, sc.lastobj);
- sz = size_object_rel(key, sc.lastobj);
+ sz = size_object(key);
hp = HAlloc(p, 9 + sz + PROC_BIN_SIZE);
- key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
if (mpi.all_objects)
(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
mpb=db_make_mp_binary(p,mpi.mp,&hp);
@@ -1207,7 +1204,7 @@ static int db_select_count_continue_tree(Process *p,
tptr = tuple_val(continuation);
if (arityval(*tptr) != 5)
- erl_exit(1,"Internal error in ets:select_count/1");
+ erts_exit(ERTS_ERROR_EXIT,"Internal error in ets:select_count/1");
lastkey = tptr[2];
end_condition = tptr[3];
@@ -1230,7 +1227,7 @@ static int db_select_count_continue_tree(Process *p,
}
stack = get_any_stack(tb);
- traverse_backwards(tb, stack, lastkey, NULL, &doit_select_count, &sc);
+ traverse_backwards(tb, stack, lastkey, &doit_select_count, &sc);
release_stack(tb,stack);
BUMP_REDS(p, 1000 - sc.max);
@@ -1240,12 +1237,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,sc.lastobj) > 0)) {
+ (cmp_partly_bound(end_condition,key) > 0)) {
/* done anyway */
RET_TO_BIF(make_small(sc.got),DB_ERROR_NONE);
}
/* Not done yet, let's trap. */
- sz = size_object_rel(key, sc.lastobj);
+ sz = size_object(key);
if (IS_USMALL(0, sc.got)) {
hp = HAlloc(p, sz + 6);
egot = make_small(sc.got);
@@ -1255,7 +1252,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_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
continuation = TUPLE5
(hp,
tptr[1],
@@ -1278,7 +1275,6 @@ 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;
@@ -1319,7 +1315,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_EQ(mpi.least,mpi.most)) {
doit_select_count(tb,mpi.save_term,&sc,0 /* dummy */);
RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE);
}
@@ -1328,12 +1324,11 @@ 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, lk_base, &doit_select_count, &sc);
+ traverse_backwards(tb, stack, lastkey, &doit_select_count, &sc);
release_stack(tb,stack);
BUMP_REDS(p, 1000 - sc.max);
if (sc.max > 0) {
@@ -1341,7 +1336,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl,
}
key = GETKEY(tb, sc.lastobj);
- sz = size_object_rel(key, sc.lastobj);
+ sz = size_object(key);
if (IS_USMALL(0, sc.got)) {
hp = HAlloc(p, sz + PROC_BIN_SIZE + 6);
egot = make_small(sc.got);
@@ -1351,7 +1346,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_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
if (mpi.all_objects)
(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
mpb = db_make_mp_binary(p,mpi.mp,&hp);
@@ -1382,7 +1377,6 @@ 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;
@@ -1424,7 +1418,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_EQ(mpi.least,mpi.most)) {
doit_select(tb,mpi.save_term,&sc, 0 /* direction doesn't matter */);
if (sc.accum != NIL) {
hp=HAlloc(p, 3);
@@ -1439,20 +1433,18 @@ 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, lk_base, &doit_select_chunk, &sc);
+ traverse_backwards(tb, stack, lastkey, &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, lk_base, &doit_select_chunk, &sc);
+ traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc);
}
release_stack(tb,stack);
@@ -1477,9 +1469,9 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
}
key = GETKEY(tb, sc.lastobj);
- sz = size_object_rel(key, sc.lastobj);
+ sz = size_object(key);
hp = HAlloc(p, 9 + sz + PROC_BIN_SIZE);
- key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
if (mpi.all_objects)
(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
mpb = db_make_mp_binary(p,mpi.mp,&hp);
@@ -1502,9 +1494,9 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl,
}
key = GETKEY(tb, sc.lastobj);
- sz = size_object_rel(key, sc.lastobj);
+ sz = size_object(key);
hp = HAlloc(p, 9 + sz + PROC_BIN_SIZE);
- key = copy_struct_rel(key, sz, &hp, &MSO(p), sc.lastobj, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
if (mpi.all_objects)
(mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
@@ -1580,7 +1572,7 @@ static int db_select_delete_continue_tree(Process *p,
sc.keypos = tb->common.keypos;
ASSERT(!erts_smp_atomic_read_nob(&tb->is_stack_busy));
- traverse_backwards(tb, &tb->static_stack, lastkey, NULL, &doit_select_delete, &sc);
+ traverse_backwards(tb, &tb->static_stack, lastkey, &doit_select_delete, &sc);
BUMP_REDS(p, 1000 - sc.max);
@@ -1589,11 +1581,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,sc.lastterm->dbterm.tpl) > 0) { /* done anyway */
+ cmp_partly_bound(end_condition,key) > 0) { /* done anyway */
RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE);
}
/* Not done yet, let's trap. */
- sz = size_object_rel(key, sc.lastterm->dbterm.tpl);
+ sz = size_object(key);
if (IS_USMALL(0, sc.accum)) {
hp = HAlloc(p, sz + 6);
eaccsum = make_small(sc.accum);
@@ -1603,7 +1595,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_rel(key, sz, &hp, &MSO(p), sc.lastterm->dbterm.tpl, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
continuation = TUPLE5
(hp,
tptr[1],
@@ -1624,7 +1616,6 @@ 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;
@@ -1668,7 +1659,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_EQ(mpi.least,mpi.most)) {
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);
@@ -1677,12 +1668,11 @@ 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, lk_base, &doit_select_delete, &sc);
+ traverse_backwards(tb, &tb->static_stack, lastkey, &doit_select_delete, &sc);
BUMP_REDS(p, 1000 - sc.max);
if (sc.max > 0) {
@@ -1690,7 +1680,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
}
key = GETKEY(tb, (sc.lastterm)->dbterm.tpl);
- sz = size_object_rel(key, sc.lastterm->dbterm.tpl);
+ sz = size_object(key);
if (IS_USMALL(0, sc.accum)) {
hp = HAlloc(p, sz + PROC_BIN_SIZE + 6);
eaccsum = make_small(sc.accum);
@@ -1700,7 +1690,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_rel(key, sz, &hp, &MSO(p), sc.lastterm->dbterm.tpl, NULL);
+ key = copy_struct(key, sz, &hp, &MSO(p));
mpb = db_make_mp_binary(p,mpi.mp,&hp);
continuation = TUPLE5
@@ -1722,6 +1712,28 @@ static int db_select_delete_tree(Process *p, DbTable *tbl,
}
+static int db_take_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+{
+ DbTableTree *tb = &tbl->tree;
+ TreeDbTerm *this;
+
+ *ret = NIL;
+ this = linkout_tree(tb, key);
+ 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,
+ &this->dbterm, &hp, &MSO(p));
+ *ret = CONS(hp, copy, NIL);
+ hp += 2;
+ HRelease(p, hend, hp);
+ free_term(tb, this);
+ }
+ return DB_ERROR_NONE;
+}
+
/*
** Other interface routines (not directly coupled to one bif)
*/
@@ -1817,9 +1829,7 @@ do_db_tree_foreach_offheap(TreeDbTerm *tdbt,
do_db_tree_foreach_offheap(tdbt->right, func, arg);
}
-static TreeDbTerm *linkout_tree(DbTableTree *tb,
- Eterm key, Eterm* key_base)
-{
+static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key) {
TreeDbTerm **tstack[STACK_NEED];
int tpos = 0;
int dstack[STACK_NEED+1];
@@ -1841,7 +1851,7 @@ static TreeDbTerm *linkout_tree(DbTableTree *tb,
for (;;) {
if (!*this) { /* Failure */
return NULL;
- } else if ((c = cmp_key(tb, key, key_base, *this)) < 0) {
+ } else if ((c = cmp_key(tb, key, *this)) < 0) {
dstack[dpos++] = DIR_LEFT;
tstack[tpos++] = this;
this = &((*this)->left);
@@ -1905,7 +1915,7 @@ static TreeDbTerm *linkout_object_tree(DbTableTree *tb,
for (;;) {
if (!*this) { /* Failure */
return NULL;
- } else if ((c = cmp_key(tb,key,NULL,*this)) < 0) {
+ } else if ((c = cmp_key(tb,key,*this)) < 0) {
dstack[dpos++] = DIR_LEFT;
tstack[tpos++] = this;
this = &((*this)->left);
@@ -2291,15 +2301,13 @@ done:
* Find next and previous in sort order
*/
-static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack,
- Eterm key, Eterm* key_base)
-{
+static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
TreeDbTerm *this;
TreeDbTerm *tmp;
Sint c;
if(( this = TOP_NODE(stack)) != NULL) {
- if (!cmp_key_eq(tb,key,key_base,this)) {
+ if (!cmp_key_eq(tb,key,this)) {
/* Start from the beginning */
stack->pos = stack->slot = 0;
}
@@ -2309,7 +2317,7 @@ static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack,
return NULL;
for (;;) {
PUSH_NODE(stack, this);
- if (( c = cmp_key(tb,key,key_base,this) ) > 0) {
+ if (( c = cmp_key(tb,key,this) ) > 0) {
if (this->right == NULL) /* We are at the previos
and the element does
not exist */
@@ -2349,15 +2357,13 @@ static TreeDbTerm *find_next(DbTableTree *tb, DbTreeStack* stack,
return this;
}
-static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack,
- Eterm key, Eterm* key_base)
-{
+static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack, Eterm key) {
TreeDbTerm *this;
TreeDbTerm *tmp;
Sint c;
if(( this = TOP_NODE(stack)) != NULL) {
- if (!cmp_key_eq(tb,key,key_base,this)) {
+ if (!cmp_key_eq(tb,key,this)) {
/* Start from the beginning */
stack->pos = stack->slot = 0;
}
@@ -2367,7 +2373,7 @@ static TreeDbTerm *find_prev(DbTableTree *tb, DbTreeStack* stack,
return NULL;
for (;;) {
PUSH_NODE(stack, this);
- if (( c = cmp_key(tb,key,key_base,this) ) < 0) {
+ if (( c = cmp_key(tb,key,this) ) < 0) {
if (this->left == NULL) /* We are at the next
and the element does
not exist */
@@ -2420,8 +2426,7 @@ 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),
- this->dbterm.tpl) ) >= 0) {
+ if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl))) >= 0) {
if (this->right == NULL) {
do {
tmp = POP_NODE(stack);
@@ -2454,8 +2459,7 @@ 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),
- this->dbterm.tpl) ) <= 0) {
+ if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl))) <= 0) {
if (this->left == NULL) {
do {
tmp = POP_NODE(stack);
@@ -2486,10 +2490,10 @@ static TreeDbTerm *find_node(DbTableTree *tb, Eterm key)
DbTreeStack* stack = get_static_stack(tb);
if(!stack || EMPTY_NODE(stack)
- || !cmp_key_eq(tb, key, NULL, (this=TOP_NODE(stack)))) {
+ || !cmp_key_eq(tb, key, (this=TOP_NODE(stack)))) {
this = tb->root;
- while (this != NULL && (res = cmp_key(tb,key,NULL,this)) != 0) {
+ while (this != NULL && (res = cmp_key(tb,key,this)) != 0) {
if (res < 0)
this = this->left;
else
@@ -2511,7 +2515,7 @@ static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
Sint res;
this = &tb->root;
- while ((*this) != NULL && (res = cmp_key(tb, key, NULL, *this)) != 0) {
+ while ((*this) != NULL && (res = cmp_key(tb, key, *this)) != 0) {
if (res < 0)
this = &((*this)->left);
else
@@ -2522,33 +2526,63 @@ static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
return this;
}
-static int db_lookup_dbterm_tree(DbTable *tbl, Eterm key, DbUpdateHandle* handle)
+static int
+db_lookup_dbterm_tree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
+ DbUpdateHandle* handle)
{
DbTableTree *tb = &tbl->tree;
TreeDbTerm **pp = find_node2(tb, key);
-
- if (pp == NULL) return 0;
+ int flags = 0;
+
+ if (pp == NULL) {
+ if (obj == THE_NON_VALUE) {
+ return 0;
+ } else {
+ Eterm *objp = tuple_val(obj);
+ int arity = arityval(*objp);
+ Eterm *htop, *hend;
+
+ ASSERT(arity >= tb->common.keypos);
+ htop = HAlloc(p, arity + 1);
+ hend = htop + arity + 1;
+ sys_memcpy(htop, objp, sizeof(Eterm) * (arity + 1));
+ htop[tb->common.keypos] = key;
+ obj = make_tuple(htop);
+
+ if (db_put_tree(tbl, obj, 1) != DB_ERROR_NONE) {
+ return 0;
+ }
+
+ pp = find_node2(tb, key);
+ ASSERT(pp != NULL);
+ HRelease(p, hend, htop);
+ flags |= DB_NEW_OBJECT;
+ }
+ }
handle->tb = tbl;
handle->dbterm = &(*pp)->dbterm;
- handle->mustResize = 0;
+ handle->flags = flags;
handle->bp = (void**) pp;
handle->new_size = (*pp)->dbterm.size;
-#if HALFWORD_HEAP
- handle->abs_vec = NULL;
-#endif
return 1;
}
-static void db_finalize_dbterm_tree(DbUpdateHandle* handle)
+static void
+db_finalize_dbterm_tree(int cret, DbUpdateHandle *handle)
{
- if (handle->mustResize) {
- TreeDbTerm* oldp = (TreeDbTerm*) *handle->bp;
+ DbTable *tbl = handle->tb;
+ DbTableTree *tb = &tbl->tree;
+ 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);
+ } else if (handle->flags & DB_MUST_RESIZE) {
db_finalize_resize(handle, offsetof(TreeDbTerm,dbterm));
- reset_static_stack(&handle->tb->tree);
+ reset_static_stack(tb);
- free_term(&handle->tb->tree, oldp);
+ free_term(tb, bp);
}
#ifdef DEBUG
handle->dbterm = 0;
@@ -2561,7 +2595,7 @@ static void db_finalize_dbterm_tree(DbUpdateHandle* handle)
*/
static void traverse_backwards(DbTableTree *tb,
DbTreeStack* stack,
- Eterm lastkey, Eterm* lk_base,
+ Eterm lastkey,
int (*doit)(DbTableTree *,
TreeDbTerm *,
void *,
@@ -2580,16 +2614,15 @@ static void traverse_backwards(DbTableTree *tb,
this = this->right;
}
this = TOP_NODE(stack);
- next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl),
- this->dbterm.tpl);
+ next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl));
if (!((*doit)(tb, this, context, 0)))
return;
} else {
- next = find_prev(tb, stack, lastkey, lk_base);
+ next = find_prev(tb, stack, lastkey);
}
while ((this = next) != NULL) {
- next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl), this->dbterm.tpl);
+ next = find_prev(tb, stack, GETKEY(tb, this->dbterm.tpl));
if (!((*doit)(tb, this, context, 0)))
return;
}
@@ -2600,7 +2633,7 @@ static void traverse_backwards(DbTableTree *tb,
*/
static void traverse_forward(DbTableTree *tb,
DbTreeStack* stack,
- Eterm lastkey, Eterm* lk_base,
+ Eterm lastkey,
int (*doit)(DbTableTree *,
TreeDbTerm *,
void *,
@@ -2619,15 +2652,15 @@ static void traverse_forward(DbTableTree *tb,
this = this->left;
}
this = TOP_NODE(stack);
- next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl), this->dbterm.tpl);
+ next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl));
if (!((*doit)(tb, this, context, 1)))
return;
} else {
- next = find_next(tb, stack, lastkey, lk_base);
+ next = find_next(tb, stack, lastkey);
}
while ((this = next) != NULL) {
- next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl), this->dbterm.tpl);
+ next = find_next(tb, stack, GETKEY(tb, this->dbterm.tpl));
if (!((*doit)(tb, this, context, 1)))
return;
}
@@ -2656,7 +2689,7 @@ static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
*ret = this;
return 1;
} else if (partly_bound != NULL && key != am_Underscore &&
- db_is_variable(key) < 0)
+ db_is_variable(key) < 0 && !db_has_map(key))
*partly_bound = key;
return 0;
@@ -2664,7 +2697,7 @@ static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
-static Sint do_cmp_partly_bound(Eterm a, Eterm b, Eterm* b_base, int *done)
+static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done)
{
Eterm* aa;
Eterm* bb;
@@ -2678,44 +2711,44 @@ static Sint do_cmp_partly_bound(Eterm a, Eterm b, Eterm* b_base, int *done)
*done = 1;
return 0;
}
- if (is_same(a,NULL,b,b_base))
+ if (is_same(a,b))
return 0;
switch (a & _TAG_PRIMARY_MASK) {
case TAG_PRIMARY_LIST:
if (!is_list(b)) {
- return cmp_rel(a,NULL,b,b_base);
+ return CMP(a,b);
}
aa = list_val(a);
- bb = list_val_rel(b,b_base);
+ bb = list_val(b);
while (1) {
- if ((j = do_cmp_partly_bound(*aa++, *bb++, b_base, done)) != 0 || *done)
+ if ((j = do_cmp_partly_bound(*aa++, *bb++, done)) != 0 || *done)
return j;
- if (is_same(*aa, NULL, *bb, b_base))
+ if (is_same(*aa, *bb))
return 0;
if (is_not_list(*aa) || is_not_list(*bb))
- return do_cmp_partly_bound(*aa, *bb, b_base, done);
+ return do_cmp_partly_bound(*aa, *bb, done);
aa = list_val(*aa);
- bb = list_val_rel(*bb,b_base);
+ bb = list_val(*bb);
}
case TAG_PRIMARY_BOXED:
if ((b & _TAG_PRIMARY_MASK) != TAG_PRIMARY_BOXED) {
- return cmp_rel(a,NULL,b,b_base);
+ return CMP(a,b);
}
a_hdr = ((*boxed_val(a)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
- b_hdr = ((*boxed_val_rel(b,b_base)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
+ b_hdr = ((*boxed_val(b)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
if (a_hdr != b_hdr) {
- return cmp_rel(a, NULL, b, b_base);
+ return CMP(a,b);
}
if (a_hdr == (_TAG_HEADER_ARITYVAL >> _TAG_PRIMARY_SIZE)) {
aa = tuple_val(a);
- bb = tuple_val_rel(b, b_base);
+ bb = tuple_val(b);
/* 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, b_base, done)) != 0
+ if ((j = do_cmp_partly_bound(*++aa, *++bb, done)) != 0
|| *done)
return j;
}
@@ -2723,14 +2756,13 @@ static Sint do_cmp_partly_bound(Eterm a, Eterm b, Eterm* b_base, int *done)
}
/* Drop through */
default:
- return cmp_rel(a, NULL, b, b_base);
+ return CMP(a,b);
}
}
-static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key, Eterm* bk_base)
-{
+static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key) {
int done = 0;
- Sint ret = do_cmp_partly_bound(partly_bound_key, bound_key, bk_base, &done);
+ Sint ret = do_cmp_partly_bound(partly_bound_key, bound_key, &done);
#ifdef HARDDEBUG
erts_fprintf(stderr,"\ncmp_partly_bound: %T", partly_bound_key);
if (ret < 0)
@@ -2739,7 +2771,7 @@ static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key, Eterm* bk_
erts_fprintf(stderr," > ");
else
erts_fprintf(stderr," == ");
- erts_fprintf(stderr,"%R\n", bound_key, bk_base);
+ erts_fprintf(stderr,"%T\n", bound_key);
#endif
return ret;
}
@@ -2956,12 +2988,10 @@ 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),
- this->dbterm.tpl) < 0) ||
+ GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) < 0) ||
(!forward &&
cmp_partly_bound(sc->end_condition,
- GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
- this->dbterm.tpl) > 0))) {
+ GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0))) {
return 0;
}
ret = db_match_dbterm(&tb->common,sc->p,sc->mp,sc->all_objects,
@@ -2993,8 +3023,7 @@ 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),
- this->dbterm.tpl) > 0)) {
+ GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0)) {
return 0;
}
ret = db_match_dbterm(&tb->common, sc->p, sc->mp, 0,
@@ -3020,12 +3049,10 @@ 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),
- this->dbterm.tpl) < 0) ||
+ GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) < 0) ||
(!forward &&
cmp_partly_bound(sc->end_condition,
- GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl),
- this->dbterm.tpl) > 0))) {
+ GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0))) {
return 0;
}
@@ -3063,14 +3090,13 @@ 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),
- this->dbterm.tpl) > 0)
+ GETKEY_WITH_POS(sc->keypos, this->dbterm.tpl)) > 0)
return 0;
ret = db_match_dbterm(&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, this->dbterm.tpl);
+ linkout_tree(sc->tb, key);
sc->erase_lastterm = 1;
++sc->accum;
}
@@ -3096,11 +3122,10 @@ static void do_dump_tree2(DbTableTree* tb, int to, void *to_arg, int show,
}
else {
prefix = "";
- term = make_tuple_rel(t->dbterm.tpl,t->dbterm.tpl);
+ term = make_tuple(t->dbterm.tpl);
}
- erts_print(to, to_arg, "%*s%s%R (addr = %p, bal = %d)\n",
- offset, "", prefix, term, t->dbterm.tpl,
- t, t->balance);
+ erts_print(to, to_arg, "%*s%s%T (addr = %p, bal = %d)\n",
+ offset, "", prefix, term, t, t->balance);
}
do_dump_tree2(tb, to, to_arg, show, t->left, offset + 4);
}