aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam')
-rw-r--r--erts/emulator/beam/bif.tab1
-rw-r--r--erts/emulator/beam/erl_db.c96
-rw-r--r--erts/emulator/beam/erl_db.h1
-rw-r--r--erts/emulator/beam/erl_db_hash.c318
-rw-r--r--erts/emulator/beam/erl_db_tree.c407
-rw-r--r--erts/emulator/beam/erl_db_util.h8
6 files changed, 817 insertions, 14 deletions
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 6f50297fc5..4140938210 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -361,6 +361,7 @@ bif ets:select_reverse/1
bif ets:select_reverse/2
bif ets:select_reverse/3
bif ets:select_delete/2
+bif ets:select_replace/2
bif ets:match_spec_compile/1
bif ets:match_spec_run_r/3
diff --git a/erts/emulator/beam/erl_db.c b/erts/emulator/beam/erl_db.c
index 2f188b5391..81fe79a92e 100644
--- a/erts/emulator/beam/erl_db.c
+++ b/erts/emulator/beam/erl_db.c
@@ -362,6 +362,7 @@ static SWord free_table_continue(Process *p, DbTable *tb, SWord reds);
static void print_table(fmtfn_t to, void *to_arg, int show, DbTable* tb);
static BIF_RETTYPE ets_select_delete_1(BIF_ALIST_1);
static BIF_RETTYPE ets_select_count_1(BIF_ALIST_1);
+static BIF_RETTYPE ets_select_replace_1(BIF_ALIST_1);
static BIF_RETTYPE ets_select_trap_1(BIF_ALIST_1);
static BIF_RETTYPE ets_delete_trap(BIF_ALIST_1);
static Eterm table_info(Process* p, DbTable* tb, Eterm What);
@@ -376,6 +377,7 @@ static BIF_RETTYPE ets_select3(Process* p, Eterm arg1, Eterm arg2, Eterm arg3);
*/
Export ets_select_delete_continue_exp;
Export ets_select_count_continue_exp;
+Export ets_select_replace_continue_exp;
Export ets_select_continue_exp;
/*
@@ -2922,6 +2924,95 @@ BIF_RETTYPE ets_select_count_2(BIF_ALIST_2)
return result;
}
+/*
+ ** This is for trapping, cannot be called directly.
+ */
+static BIF_RETTYPE ets_select_replace_1(BIF_ALIST_1)
+{
+ Process *p = BIF_P;
+ Eterm a1 = BIF_ARG_1;
+ BIF_RETTYPE result;
+ DbTable* tb;
+ int cret;
+ Eterm ret;
+ Eterm *tptr;
+ db_lock_kind_t kind = LCK_WRITE_REC;
+
+ CHECK_TABLES();
+ ASSERT(is_tuple(a1));
+ tptr = tuple_val(a1);
+ ASSERT(arityval(*tptr) >= 1);
+
+ if ((tb = db_get_table(p, tptr[1], DB_WRITE, kind)) == NULL) {
+ BIF_ERROR(p,BADARG);
+ }
+
+ cret = tb->common.meth->db_select_replace_continue(p,tb,a1,&ret);
+
+ if(!DID_TRAP(p,ret) && ITERATION_SAFETY(p,tb) != ITER_SAFE) {
+ unfix_table_locked(p, tb, &kind);
+ }
+
+ db_unlock(tb, kind);
+
+ switch (cret) {
+ case DB_ERROR_NONE:
+ ERTS_BIF_PREP_RET(result, ret);
+ break;
+ default:
+ ERTS_BIF_PREP_ERROR(result, p, BADARG);
+ break;
+ }
+ erts_match_set_release_result(p);
+
+ return result;
+}
+
+
+BIF_RETTYPE ets_select_replace_2(BIF_ALIST_2)
+{
+ BIF_RETTYPE result;
+ DbTable* tb;
+ int cret;
+ Eterm ret;
+ enum DbIterSafety safety;
+
+ CHECK_TABLES();
+
+ if ((tb = db_get_table(BIF_P, BIF_ARG_1, DB_WRITE, LCK_WRITE_REC)) == NULL) {
+ BIF_ERROR(BIF_P, BADARG);
+ }
+ safety = ITERATION_SAFETY(BIF_P,tb);
+ if (safety == ITER_UNSAFE) {
+ local_fix_table(tb);
+ }
+ cret = tb->common.meth->db_select_replace(BIF_P, tb, BIF_ARG_2, &ret);
+
+ if (DID_TRAP(BIF_P,ret) && safety != ITER_SAFE) {
+ fix_table_locked(BIF_P,tb);
+ }
+ if (safety == ITER_UNSAFE) {
+ local_unfix_table(tb);
+ }
+ db_unlock(tb, LCK_WRITE_REC);
+
+ switch (cret) {
+ case DB_ERROR_NONE:
+ ERTS_BIF_PREP_RET(result, ret);
+ break;
+ case DB_ERROR_SYSRES:
+ ERTS_BIF_PREP_ERROR(result, BIF_P, SYSTEM_LIMIT);
+ break;
+ default:
+ ERTS_BIF_PREP_ERROR(result, BIF_P, BADARG);
+ break;
+ }
+
+ erts_match_set_release_result(BIF_P);
+
+ return result;
+}
+
BIF_RETTYPE ets_select_reverse_3(BIF_ALIST_3)
{
@@ -3335,6 +3426,11 @@ void init_db(ErtsDbSpinCount db_spin_count)
&ets_select_count_1);
/* Non visual BIF to trap to. */
+ erts_init_trap_export(&ets_select_replace_continue_exp,
+ am_ets, am_atom_put("replace_trap",11), 1,
+ &ets_select_replace_1);
+
+ /* Non visual BIF to trap to. */
erts_init_trap_export(&ets_select_continue_exp,
am_ets, am_atom_put("select_trap",11), 1,
&ets_select_trap_1);
diff --git a/erts/emulator/beam/erl_db.h b/erts/emulator/beam/erl_db.h
index cbf4b9e007..4ff9f224e8 100644
--- a/erts/emulator/beam/erl_db.h
+++ b/erts/emulator/beam/erl_db.h
@@ -122,6 +122,7 @@ extern int erts_ets_realloc_always_moves; /* set in erl_init */
extern int erts_ets_always_compress; /* set in erl_init */
extern Export ets_select_delete_continue_exp;
extern Export ets_select_count_continue_exp;
+extern Export ets_select_replace_continue_exp;
extern Export ets_select_continue_exp;
extern erts_smp_atomic_t erts_ets_misc_mem_size;
diff --git a/erts/emulator/beam/erl_db_hash.c b/erts/emulator/beam/erl_db_hash.c
index 18405342da..a4ca6dce77 100644
--- a/erts/emulator/beam/erl_db_hash.c
+++ b/erts/emulator/beam/erl_db_hash.c
@@ -288,6 +288,9 @@ static ERTS_INLINE Sint next_slot_w(DbTableHash* tb, Uint ix,
#endif
}
+#ifndef MIN
+#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
+#endif
/*
* Some special binary flags
@@ -403,6 +406,9 @@ static int db_select_count_hash(Process *p, DbTable *tbl, Eterm tid,
static int db_select_delete_hash(Process *p, DbTable *tbl, Eterm tid,
Eterm pattern, Eterm *ret);
+static int db_select_replace_hash(Process *p, DbTable *tbl,
+ Eterm pattern, Eterm *ret);
+
static int db_select_continue_hash(Process *p, DbTable *tbl,
Eterm continuation, Eterm *ret);
@@ -411,6 +417,10 @@ static int db_select_count_continue_hash(Process *p, DbTable *tbl,
static int db_select_delete_continue_hash(Process *p, DbTable *tbl,
Eterm continuation, Eterm *ret);
+
+static int db_select_replace_continue_hash(Process *p, DbTable *tbl,
+ Eterm continuation, Eterm *ret);
+
static int db_take_hash(Process *, DbTable *, Eterm, Eterm *);
static void db_print_hash(fmtfn_t to,
void *to_arg,
@@ -523,6 +533,8 @@ DbTableMethod db_hash =
db_select_delete_continue_hash,
db_select_count_hash,
db_select_count_continue_hash,
+ db_select_replace_hash,
+ db_select_replace_continue_hash,
db_take_hash,
db_delete_all_objects_hash,
db_free_table_hash,
@@ -1989,6 +2001,312 @@ static int db_take_hash(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
return DB_ERROR_NONE;
}
+static int db_select_replace_hash(Process *p,
+ DbTable *tbl,
+ Eterm pattern,
+ Eterm *ret)
+{
+ DbTableHash *tb = &tbl->hash;
+ struct mp_info mpi;
+ Uint slot_ix = 0;
+ HashDbTerm **current = NULL, **initial = NULL, **iter = NULL;
+ HashDbTerm *new = NULL, *next = NULL;
+ HashValue hval = INVALID_HASH;
+ unsigned current_list_pos = 0;
+ Eterm key;
+ Eterm match_res;
+ Eterm *hp;
+ int num_left = 1000;
+ Uint got = 0;
+ Eterm continuation;
+ int errcode;
+ Eterm mpb;
+ Eterm egot;
+ erts_smp_rwmtx_t* lck;
+
+#define RET_TO_BIF(Term,RetVal) do { \
+ if (mpi.mp != NULL) { \
+ erts_bin_free(mpi.mp); \
+ } \
+ if (mpi.lists != mpi.dlists) { \
+ erts_free(ERTS_ALC_T_DB_SEL_LIST, \
+ (void *) mpi.lists); \
+ } \
+ *ret = (Term); \
+ return RetVal; \
+ } while(0)
+
+
+ if ((errcode = analyze_pattern(tb, pattern, &mpi)) != DB_ERROR_NONE) {
+ RET_TO_BIF(NIL,errcode);
+ }
+
+ if (!mpi.something_can_match) {
+ RET_TO_BIF(make_small(0), DB_ERROR_NONE);
+ /* can't possibly match anything */
+ }
+
+ if (!mpi.key_given) {
+ /* Run this code if pattern is variable or GETKEY(pattern) */
+ /* is a variable */
+ lck = WLOCK_HASH(tb,slot_ix);
+ current = &BUCKET(tb,slot_ix);
+ } else {
+ /* We have at least one */
+ slot_ix = mpi.lists[current_list_pos].ix;
+ lck = WLOCK_HASH(tb, slot_ix);
+ current = mpi.lists[current_list_pos++].bucket;
+ ASSERT(*current == BUCKET(tb,slot_ix));
+ }
+
+
+ initial = current;
+ for(;;) {
+ if ((*current) == NULL) {
+ if (mpi.key_given) { /* Key is bound */
+ WUNLOCK_HASH(lck);
+ if (current_list_pos == mpi.num_lists) {
+ goto done;
+ } else {
+ slot_ix = mpi.lists[current_list_pos].ix;
+ lck = WLOCK_HASH(tb, slot_ix);
+ current = mpi.lists[current_list_pos].bucket;
+ ASSERT(mpi.lists[current_list_pos].bucket == &BUCKET(tb,slot_ix));
+ ++current_list_pos;
+ }
+ } else {
+ if ((slot_ix=next_slot_w(tb,slot_ix,&lck)) == 0) {
+ goto done;
+ }
+ if (num_left <= 0) {
+ WUNLOCK_HASH(lck);
+ goto trap;
+ }
+ current = &BUCKET(tb,slot_ix);
+ }
+ initial = current;
+ }
+ else if ((*current)->hvalue == INVALID_HASH) {
+ current = &((*current)->next);
+ }
+ else if (tb->common.status & DB_BAG) {
+ match_res = db_match_dbterm(&tb->common, p, mpi.mp, 0,
+ &(*current)->dbterm, NULL, 0);
+ if (is_value(match_res) &&
+ is_value(key = db_getkey(tb->common.keypos, match_res)) &&
+ eq(key, GETKEY(tb, (*current)->dbterm.tpl)))
+ {
+ // we need to make sure we don't end up with duplicate objects;
+ // it's quite inefficient
+ int object_exists = 0;
+ for (iter = initial; *iter != NULL; iter = &((*iter)->next))
+ if (((*iter)->hvalue != INVALID_HASH)
+ && (*iter != *current)
+ && db_eq(&tb->common, match_res, &(*iter)->dbterm))
+ {
+ object_exists = 1;
+ break;
+ }
+
+ if (!object_exists) {
+ next = (*current)->next;
+ hval = (*current)->hvalue;
+ new = replace_dbterm(tb, *current, match_res);
+ new->next = next;
+ new->hvalue = hval;
+ *current = new;
+ ++got;
+ }
+ }
+ --num_left;
+ current = &((*current)->next);
+ }
+ else {
+ match_res = db_match_dbterm(&tb->common, p, mpi.mp, 0,
+ &(*current)->dbterm, NULL, 0);
+ if (is_value(match_res) &&
+ is_value(key = db_getkey(tb->common.keypos, match_res)) &&
+ eq(key, GETKEY(tb, (*current)->dbterm.tpl)))
+ {
+ next = (*current)->next;
+ hval = (*current)->hvalue;
+ new = replace_dbterm(tb, *current, match_res);
+ new->next = next;
+ new->hvalue = hval;
+ *current = new;
+ ++got;
+ }
+ --num_left;
+ current = &((*current)->next);
+ }
+ }
+done:
+ // the more objects we've replaced, the more reductions we've consumed
+ BUMP_REDS(p, MIN(2000, (1000 - num_left) + (int)got));
+ RET_TO_BIF(erts_make_integer(got,p),DB_ERROR_NONE);
+trap:
+ BUMP_ALL_REDS(p);
+ if (IS_USMALL(0, got)) {
+ hp = HAlloc(p, PROC_BIN_SIZE + 5);
+ egot = make_small(got);
+ }
+ else {
+ hp = HAlloc(p, BIG_UINT_HEAP_SIZE + PROC_BIN_SIZE + 5);
+ egot = uint_to_big(got, hp);
+ hp += BIG_UINT_HEAP_SIZE;
+ }
+ mpb = db_make_mp_binary(p,mpi.mp,&hp);
+ continuation = TUPLE4(hp, tb->common.id, make_small(slot_ix),
+ mpb,
+ egot);
+ mpi.mp = NULL; /*otherwise the return macro will destroy it */
+ RET_TO_BIF(bif_trap1(&ets_select_replace_continue_exp, p,
+ continuation),
+ DB_ERROR_NONE);
+
+#undef RET_TO_BIF
+
+}
+
+/*
+** This is called when select_replace traps
+*/
+static int db_select_replace_continue_hash(Process *p,
+ DbTable *tbl,
+ Eterm continuation,
+ Eterm *ret)
+{
+ DbTableHash *tb = &tbl->hash;
+ Uint slot_ix;
+ HashDbTerm **current = NULL, **initial = NULL, **iter = NULL;
+ HashDbTerm *new = NULL, *next = NULL;
+ HashValue hval = INVALID_HASH;
+ Eterm key;
+ Eterm match_res;
+ Eterm *hp;
+ int num_left = 1000;
+ Uint got, prev_got;
+ Eterm *tptr;
+ Binary *mp;
+ Eterm egot;
+ erts_smp_rwmtx_t* lck;
+
+#define RET_TO_BIF(Term,RetVal) do { \
+ *ret = (Term); \
+ return RetVal; \
+ } while(0)
+
+
+ tptr = tuple_val(continuation);
+ slot_ix = unsigned_val(tptr[2]);
+ mp = ((ProcBin *) binary_val(tptr[3]))->val;
+ if (is_big(tptr[4])) {
+ got = big_to_uint32(tptr[4]);
+ } else {
+ got = unsigned_val(tptr[4]);
+ }
+ prev_got = got;
+
+ lck = WLOCK_HASH(tb,slot_ix);
+ if (slot_ix >= NACTIVE(tb)) {
+ WUNLOCK_HASH(lck);
+ goto done;
+ }
+ current = &BUCKET(tb,slot_ix);
+ initial = current;
+
+ for(;;) {
+ if ((*current) == NULL) {
+ if ((slot_ix=next_slot_w(tb,slot_ix,&lck)) == 0) {
+ goto done;
+ }
+ if (num_left <= 0) {
+ WUNLOCK_HASH(lck);
+ goto trap;
+ }
+ current = &BUCKET(tb,slot_ix);
+ initial = current;
+ }
+ else if ((*current)->hvalue == INVALID_HASH) {
+ current = &((*current)->next);
+ }
+ else if (tb->common.status & DB_BAG) {
+ match_res = db_match_dbterm(&tb->common, p, mp, 0,
+ &(*current)->dbterm, NULL, 0);
+ if (is_value(match_res) &&
+ is_value(key = db_getkey(tb->common.keypos, match_res)) &&
+ eq(key, GETKEY(tb, (*current)->dbterm.tpl)))
+ {
+ // we need to make sure we don't end up with duplicate objects;
+ // it's quite inefficient
+ int object_exists = 0;
+ for (iter = initial; *iter != NULL; iter = &((*iter)->next))
+ if (((*iter)->hvalue != INVALID_HASH)
+ && (*iter != *current)
+ && db_eq(&tb->common, match_res, &(*iter)->dbterm))
+ {
+ object_exists = 1;
+ break;
+ }
+
+ if (!object_exists) {
+ next = (*current)->next;
+ hval = (*current)->hvalue;
+ new = replace_dbterm(tb, *current, match_res);
+ new->next = next;
+ new->hvalue = hval;
+ *current = new;
+ ++got;
+ }
+ }
+ --num_left;
+ current = &((*current)->next);
+ }
+ else {
+ match_res = db_match_dbterm(&tb->common, p, mp, 0,
+ &(*current)->dbterm, NULL, 0);
+ if (is_value(match_res) &&
+ is_value(key = db_getkey(tb->common.keypos, match_res)) &&
+ eq(key, GETKEY(tb, (*current)->dbterm.tpl)))
+ {
+ next = (*current)->next;
+ hval = (*current)->hvalue;
+ new = replace_dbterm(tb, *current, match_res);
+ new->next = next;
+ new->hvalue = hval;
+ *current = new;
+ ++got;
+ }
+ --num_left;
+ current = &((*current)->next);
+ }
+ }
+done:
+ // the more objects we've replaced, the more reductions we've consumed
+ BUMP_REDS(p, MIN(2000, (1000 - num_left) + (int)(got - prev_got)));
+ RET_TO_BIF(erts_make_integer(got,p),DB_ERROR_NONE);
+trap:
+ BUMP_ALL_REDS(p);
+ if (IS_USMALL(0, got)) {
+ hp = HAlloc(p, 5);
+ egot = make_small(got);
+ }
+ else {
+ hp = HAlloc(p, BIG_UINT_HEAP_SIZE + 5);
+ egot = uint_to_big(got, hp);
+ hp += BIG_UINT_HEAP_SIZE;
+ }
+ continuation = TUPLE4(hp, tb->common.id, make_small(slot_ix),
+ tptr[3],
+ egot);
+ RET_TO_BIF(bif_trap1(&ets_select_replace_continue_exp, p,
+ continuation),
+ DB_ERROR_NONE);
+
+#undef RET_TO_BIF
+
+}
+
/*
** Other interface routines (not directly coupled to one bif)
*/
diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c
index 14a7451267..af1296367a 100644
--- a/erts/emulator/beam/erl_db_tree.c
+++ b/erts/emulator/beam/erl_db_tree.c
@@ -76,9 +76,18 @@
((Dtt->pos) ? \
(Dtt)->array[(Dtt)->pos - 1] : NULL)
-#define EMPTY_NODE(Dtt) (TOP_NODE(Dtt) == NULL)
+#define TOPN_NODE(Dtt, Pos) \
+ (((Pos) < Dtt->pos) ? \
+ (Dtt)->array[(Dtt)->pos - ((Pos) + 1)] : NULL)
+
+#define REPLACE_TOP_NODE(Dtt, Node) \
+ if ((Dtt)->pos) (Dtt)->array[(Dtt)->pos - 1] = (Node)
+#define EMPTY_NODE(Dtt) (TOP_NODE(Dtt) == NULL)
+#ifndef MIN
+#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
+#endif
/* Obtain table static stack if available. NULL if not.
** Must be released with release_stack()
@@ -225,9 +234,9 @@ struct mp_info {
Eterm most; /* The highest matching key (possibly
* partially bound expression) */
- TreeDbTerm *save_term; /* If the key is completely bound, this
- * will be the Tree node we're searching
- * for, otherwise it will be useless */
+ TreeDbTerm **save_term; /* If the key is completely bound, this
+ * will be the Tree node we're searching
+ * for, otherwise it will be useless */
Binary *mp; /* The compiled match program */
};
@@ -277,6 +286,21 @@ struct select_delete_context {
};
/*
+ * Used by doit_select_replace
+ */
+struct select_replace_context {
+ Process *p;
+ DbTableTree *tb;
+ Binary *mp;
+ Eterm end_condition;
+ Eterm *lastobj;
+ Sint32 max;
+ int keypos;
+ int all_objects;
+ Sint replaced;
+};
+
+/*
** Forward declarations
*/
static TreeDbTerm *linkout_tree(DbTableTree *tb, Eterm key);
@@ -290,6 +314,7 @@ 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*,
@@ -311,8 +336,16 @@ static void traverse_forward(DbTableTree *tb,
TreeDbTerm *,
void *,
int),
- void *context);
-static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
+ void *context);
+static void traverse_update_backwards(DbTableTree *tb,
+ DbTreeStack*,
+ Eterm lastkey,
+ int (*doit)(DbTableTree *tb,
+ TreeDbTerm **, // out
+ void *,
+ int),
+ 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);
@@ -335,6 +368,10 @@ static int doit_select_delete(DbTableTree *tb,
TreeDbTerm *this,
void *ptr,
int forward);
+static int doit_select_replace(DbTableTree *tb,
+ TreeDbTerm **this_ptr,
+ void *ptr,
+ int forward);
static int partly_bound_can_match_lesser(Eterm partly_bound_1,
Eterm partly_bound_2);
@@ -383,6 +420,10 @@ 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);
+static int db_select_replace_tree(Process *p, DbTable *tbl,
+ Eterm pattern, Eterm *ret);
+static int db_select_replace_continue_tree(Process *p, DbTable *tbl,
+ Eterm continuation, Eterm *ret);
static int db_take_tree(Process *, DbTable *, Eterm, Eterm *);
static void db_print_tree(fmtfn_t to, void *to_arg,
int show, DbTable *tbl);
@@ -435,6 +476,8 @@ DbTableMethod db_tree =
db_select_delete_continue_tree,
db_select_count_tree,
db_select_count_continue_tree,
+ db_select_replace_tree,
+ db_select_replace_continue_tree,
db_take_tree,
db_delete_all_objects_tree,
db_free_table_tree,
@@ -1103,7 +1146,7 @@ static int db_select_tree(Process *p, DbTable *tbl, Eterm tid,
if (!mpi.got_partial && mpi.some_limitation &&
CMP_EQ(mpi.least,mpi.most)) {
- doit_select(tb,mpi.save_term,&sc,0 /* direction doesn't matter */);
+ doit_select(tb,*(mpi.save_term),&sc,0 /* direction doesn't matter */);
RET_TO_BIF(sc.accum,DB_ERROR_NONE);
}
@@ -1306,7 +1349,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid,
if (!mpi.got_partial && mpi.some_limitation &&
CMP_EQ(mpi.least,mpi.most)) {
- doit_select_count(tb,mpi.save_term,&sc,0 /* dummy */);
+ doit_select_count(tb,*(mpi.save_term),&sc,0 /* dummy */);
RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE);
}
@@ -1409,7 +1452,7 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid,
if (!mpi.got_partial && mpi.some_limitation &&
CMP_EQ(mpi.least,mpi.most)) {
- doit_select(tb,mpi.save_term,&sc, 0 /* direction doesn't matter */);
+ doit_select(tb,*(mpi.save_term),&sc, 0 /* direction doesn't matter */);
if (sc.accum != NIL) {
hp=HAlloc(p, 3);
RET_TO_BIF(TUPLE2(hp,sc.accum,am_EOT),DB_ERROR_NONE);
@@ -1650,7 +1693,7 @@ 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(tb,*(mpi.save_term),&sc, 0 /* direction doesn't
matter */);
RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE);
}
@@ -1702,6 +1745,212 @@ 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)
+{
+ DbTableTree *tb = &tbl->tree;
+ DbTreeStack* stack;
+ struct select_replace_context sc;
+ unsigned sz;
+ Eterm *hp;
+ Eterm lastkey;
+ Eterm end_condition;
+ Binary *mp;
+ Eterm key;
+ Eterm *tptr;
+ Eterm ereplaced;
+ Sint prev_replaced;
+
+
+#define RET_TO_BIF(Term, State) do { *ret = (Term); return State; } while(0);
+
+ /* Decode continuation. We know it's a tuple and everything else as
+ this is only called by ourselves */
+
+ /* continuation:
+ {Table, Lastkey, EndCondition, MatchProgBin, HowManyReplaced}*/
+
+ tptr = tuple_val(continuation);
+
+ if (arityval(*tptr) != 5)
+ erts_exit(ERTS_ERROR_EXIT,"Internal error in ets:select_replace/1");
+
+ lastkey = tptr[2];
+ end_condition = tptr[3];
+ if (!(thing_subtag(*binary_val(tptr[4])) == REFC_BINARY_SUBTAG))
+ RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
+ mp = ((ProcBin *) binary_val(tptr[4]))->val;
+ if (!IsMatchProgBinary(mp))
+ RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
+
+ sc.p = p;
+ sc.mp = mp;
+ sc.end_condition = NIL;
+ sc.lastobj = NULL;
+ sc.max = 1000;
+ sc.keypos = tb->common.keypos;
+ if (is_big(tptr[5])) {
+ sc.replaced = big_to_uint32(tptr[5]);
+ } else {
+ sc.replaced = unsigned_val(tptr[5]);
+ }
+ prev_replaced = sc.replaced;
+
+ stack = get_any_stack(tb);
+ traverse_update_backwards(tb, stack, lastkey, &doit_select_replace, &sc);
+ release_stack(tb,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)));
+
+ if (sc.max > 0) {
+ RET_TO_BIF(erts_make_integer(sc.replaced,p), DB_ERROR_NONE);
+ }
+ key = GETKEY(tb, sc.lastobj);
+ if (end_condition != NIL &&
+ (cmp_partly_bound(end_condition,key) > 0)) {
+ /* done anyway */
+ RET_TO_BIF(make_small(sc.replaced),DB_ERROR_NONE);
+ }
+ /* Not done yet, let's trap. */
+ sz = size_object(key);
+ if (IS_USMALL(0, sc.replaced)) {
+ hp = HAlloc(p, sz + 6);
+ ereplaced = make_small(sc.replaced);
+ }
+ else {
+ hp = HAlloc(p, BIG_UINT_HEAP_SIZE + sz + 6);
+ ereplaced = uint_to_big(sc.replaced, hp);
+ hp += BIG_UINT_HEAP_SIZE;
+ }
+ key = copy_struct(key, sz, &hp, &MSO(p));
+ continuation = TUPLE5
+ (hp,
+ tptr[1],
+ key,
+ tptr[3],
+ tptr[4],
+ ereplaced);
+ RET_TO_BIF(bif_trap1(&ets_select_replace_continue_exp, p, continuation),
+ DB_ERROR_NONE);
+
+#undef RET_TO_BIF
+}
+
+static int db_select_replace_tree(Process *p, DbTable *tbl,
+ Eterm pattern, Eterm *ret)
+{
+ DbTableTree *tb = &tbl->tree;
+ DbTreeStack* stack;
+ struct select_replace_context sc;
+ struct mp_info mpi;
+ Eterm lastkey = THE_NON_VALUE;
+ Eterm key;
+ Eterm continuation;
+ unsigned sz;
+ Eterm *hp;
+ TreeDbTerm *this;
+ int errcode;
+ Eterm ereplaced;
+ Eterm mpb;
+
+
+#define RET_TO_BIF(Term,RetVal) do { \
+ if (mpi.mp != NULL) { \
+ erts_bin_free(mpi.mp); \
+ } \
+ *ret = (Term); \
+ return RetVal; \
+ } while(0)
+
+ mpi.mp = NULL;
+
+ sc.lastobj = NULL;
+ sc.p = p;
+ sc.tb = tb;
+ sc.max = 1000;
+ sc.end_condition = NIL;
+ sc.keypos = tb->common.keypos;
+ sc.replaced = 0;
+
+ if ((errcode = analyze_pattern(tb, pattern, &mpi)) != DB_ERROR_NONE) {
+ RET_TO_BIF(NIL,errcode);
+ }
+
+ if (!mpi.something_can_match) {
+ RET_TO_BIF(make_small(0),DB_ERROR_NONE);
+ /* can't possibly match anything */
+ }
+
+ sc.mp = mpi.mp;
+ sc.all_objects = mpi.all_objects;
+
+ stack = get_static_stack(tb);
+ if (!mpi.got_partial && mpi.some_limitation &&
+ CMP_EQ(mpi.least,mpi.most)) {
+ TreeDbTerm* term = *(mpi.save_term);
+ doit_select_replace(tb,mpi.save_term,&sc,0 /* dummy */);
+ if (stack != NULL) {
+ if (TOP_NODE(stack) == term)
+ // throw away potentially invalid reference
+ REPLACE_TOP_NODE(stack, *(mpi.save_term));
+ release_stack(tb, stack);
+ }
+ RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE);
+ }
+
+ if (stack == NULL)
+ stack = get_any_stack(tb);
+
+ if (mpi.some_limitation) {
+ if ((this = find_next_from_pb_key(tb, 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);
+ // 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) {
+ RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE);
+ }
+
+ key = GETKEY(tb, sc.lastobj);
+ sz = size_object(key);
+ if (IS_USMALL(0, sc.replaced)) {
+ hp = HAlloc(p, sz + PROC_BIN_SIZE + 6);
+ ereplaced = make_small(sc.replaced);
+ }
+ else {
+ hp = HAlloc(p, BIG_UINT_HEAP_SIZE + sz + PROC_BIN_SIZE + 6);
+ ereplaced = uint_to_big(sc.replaced, hp);
+ hp += BIG_UINT_HEAP_SIZE;
+ }
+ 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);
+
+ continuation = TUPLE5
+ (hp,
+ tb->common.id,
+ key,
+ sc.end_condition, /* From the match program, needn't be copied */
+ mpb,
+ ereplaced);
+
+ /* Don't free mpi.mp, so don't use macro */
+ *ret = bif_trap1(&ets_select_replace_continue_exp, p, continuation);
+ return DB_ERROR_NONE;
+
+#undef RET_TO_BIF
+
+}
+
static int db_take_tree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
{
DbTableTree *tb = &tbl->tree;
@@ -2011,7 +2260,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, tpl, &(mpi->save_term), &partly_bound);
if ( res >= 0 ) { /* Can match something */
key = 0;
mpi->something_can_match = 1;
@@ -2514,6 +2763,58 @@ static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
return this;
}
+/*
+ * Find node and return the address of the node pointer (NULL if not found)
+ * Tries to reuse the existing stack for performance.
+ */
+
+static TreeDbTerm **find_ptr(DbTableTree *tb, DbTreeStack *stack, TreeDbTerm *this) {
+ Eterm key = GETKEY(tb, this->dbterm.tpl);
+ TreeDbTerm *tmp;
+ TreeDbTerm *parent;
+ Sint c;
+
+ if(( tmp = TOP_NODE(stack)) != NULL) {
+ if (!cmp_key_eq(tb,key,tmp)) {
+ /* Start from the beginning */
+ stack->pos = stack->slot = 0;
+ }
+ }
+ if (EMPTY_NODE(stack)) { /* Have to rebuild the stack */
+ if (( tmp = tb->root ) == NULL)
+ return NULL;
+ for (;;) {
+ PUSH_NODE(stack, tmp);
+ if (( c = cmp_key(tb,key,tmp) ) < 0) {
+ if (tmp->left == NULL) /* We are at the next
+ and the element does
+ not exist */
+ break;
+ else
+ tmp = tmp->left;
+ } else if (c > 0) {
+ if (tmp->right == NULL) /* Done */
+ return NULL;
+ else
+ tmp = tmp->right;
+ } else
+ break;
+ }
+ }
+
+ if (TOP_NODE(stack) != this)
+ return NULL;
+
+ parent = TOPN_NODE(stack, 1);
+ if (parent == NULL)
+ return ((this != tb->root) ? NULL : &(tb->root));
+ if (parent->left == this)
+ return &(parent->left);
+ if (parent->right == this)
+ return &(parent->right);
+ return NULL;
+}
+
static int
db_lookup_dbterm_tree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
DbUpdateHandle* handle)
@@ -2655,13 +2956,60 @@ 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,
+ DbTreeStack* stack,
+ Eterm lastkey,
+ int (*doit)(DbTableTree*,
+ TreeDbTerm**,
+ void*,
+ int),
+ void* context)
+{
+ int res;
+ TreeDbTerm *this, *next, **this_ptr;
+
+ if (lastkey == THE_NON_VALUE) {
+ stack->pos = stack->slot = 0;
+ if (( this = tb->root ) == NULL) {
+ return;
+ }
+ while (this != NULL) {
+ PUSH_NODE(stack, this);
+ this = this->right;
+ }
+ this = TOP_NODE(stack);
+ this_ptr = find_ptr(tb, 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));
+ if (!res)
+ return;
+ } else {
+ next = find_prev(tb, stack, lastkey);
+ }
+
+ while ((this = next) != NULL) {
+ this_ptr = find_ptr(tb, 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));
+ if (!res)
+ return;
+ }
+}
+
+/*
* 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,
+static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm ***ret,
Eterm *partly_bound)
{
- TreeDbTerm *this;
+ TreeDbTerm **this;
Eterm key;
ASSERT(ret != NULL);
@@ -2671,7 +3019,7 @@ static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret,
if (is_non_value(key))
return -1; /* can't possibly match anything */
if (!db_has_variable(key)) { /* Bound key */
- if (( this = find_node(tb, key) ) == NULL) {
+ if (( this = find_node2(tb, key) ) == NULL) {
return -1;
}
*ret = this;
@@ -3094,6 +3442,37 @@ static int doit_select_delete(DbTableTree *tb, TreeDbTerm *this, void *ptr,
return 1;
}
+static int doit_select_replace(DbTableTree *tb, TreeDbTerm **this, void *ptr,
+ int forward)
+{
+ struct select_replace_context *sc = (struct select_replace_context *) ptr;
+ Eterm ret, key;
+
+ sc->lastobj = (*this)->dbterm.tpl;
+
+ /* Always backwards traversing */
+ if (sc->end_condition != NIL &&
+ (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, 0,
+ &(*this)->dbterm, NULL, 0);
+
+ if (is_value(ret) &&
+ is_value(key = db_getkey(tb->common.keypos, ret)) &&
+ (cmp_key(tb, key, *this) == 0))
+ {
+ *this = replace_dbterm(tb, *this, ret);
+ sc->lastobj = (*this)->dbterm.tpl;
+ ++(sc->replaced);
+ }
+ if (--(sc->max) <= 0) {
+ return 0;
+ }
+ return 1;
+}
+
#ifdef TREE_DEBUG
static void do_dump_tree2(DbTableTree* tb, int to, void *to_arg, int show,
TreeDbTerm *t, int offset)
diff --git a/erts/emulator/beam/erl_db_util.h b/erts/emulator/beam/erl_db_util.h
index 72298842d7..89ef79d2dc 100644
--- a/erts/emulator/beam/erl_db_util.h
+++ b/erts/emulator/beam/erl_db_util.h
@@ -169,6 +169,14 @@ typedef struct db_table_method
DbTable* tb, /* [in out] */
Eterm continuation,
Eterm* ret);
+ int (*db_select_replace)(Process* p,
+ DbTable* tb, /* [in out] */
+ Eterm pattern,
+ Eterm* ret);
+ int (*db_select_replace_continue)(Process* p,
+ DbTable* tb, /* [in out] */
+ Eterm continuation,
+ Eterm* ret);
int (*db_take)(Process *, DbTable *, Eterm, Eterm *);
int (*db_delete_all_objects)(Process* p,
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-01 23:41:52 +0000