ETS: Allow for matchspec-based replacement

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,