erts: Introduce more Maps BIFs

 * map:remove/2

 * map:keys/1

 * map:values/1

 * map:is_key/2

 * map:update/3
   - Equivalent to ':=' operator in #{ K := V } maps.

 * map:from_list/1
   - map:from_list/1 takes any unsorted key/value list, [{K,V}], and
     produces a map. Duplicate keys are removed. The latest key is kept.

 * map:find/2
  - Searches for a pair that *equals* input key.

 * map:merge/2
  - Merge two maps to one map.

3 files changed, 547 insertions, 35 deletions

diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 8f85f931c9..306861a4c5 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -572,7 +572,6 @@ bif erlang:binary_to_float/1
 bif io:printable_range/0
 bif os:unsetenv/1
 
-
 #
 # New in R17A
 #
@@ -582,9 +581,17 @@ bif re:inspect/2
 ubif erlang:is_map/1
 ubif erlang:map_size/1
 bif map:to_list/1
-bif map:new/0
+bif map:find/2
 bif map:get/2
+bif map:from_list/1
+bif map:is_key/2
+bif map:keys/1
+bif map:merge/2
+bif map:new/0
 bif map:put/3
+bif map:remove/2
+bif map:update/3
+bif map:values/1
 
 #
 # Obsolete
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 6a59fa29b8..6fd60f0689 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -32,6 +32,57 @@
 
 #include "erl_map.h"
 
+/* BIFs
+ *
+ * DONE:
+ * - erlang:is_map/1
+ * - erlang:map_size/1
+ *
+ * - map:find/2
+ * - map:from_list/1
+ * - map:get/2
+ * - map:is_key/2
+ * - map:keys/1
+ * - map:merge/2
+ * - map:new/0
+ * - map:put/3
+ * - map:remove/2
+ * - map:to_list/1
+ * - map:update/3
+ * - map:values/1
+ *
+ * TODO:
+ * - map:foldl/3
+ * - map:foldr/3
+ * - map:map/3
+ * - map:size/1
+ * - map:without/2
+ *
+ */
+
+/* erlang:map_size/1
+ * the corresponding instruction is implemented in:
+ *     beam/erl_bif_guard.c
+ */
+
+BIF_RETTYPE map_size_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Eterm *hp;
+	Uint hsz  = 0;
+	map_t *mp = (map_t*)map_val(BIF_ARG_1);
+	Uint n    = map_get_size(mp);
+
+	erts_bld_uint(NULL, &hsz, n);
+	hp = HAlloc(BIF_P, hsz);
+	BIF_RET(erts_bld_uint(&hp, NULL, n));
+    }
+
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* map:to_list/1
+ */
+
 BIF_RETTYPE map_to_list_1(BIF_ALIST_1) {
     if (is_map(BIF_ARG_1)) {
 	Uint n;
@@ -56,43 +107,40 @@ BIF_RETTYPE map_to_list_1(BIF_ALIST_1) {
     BIF_ERROR(BIF_P, BADARG);
 }
 
-
-/* erlang:map_size/1
- * the corresponding instruction is implemented in:
- *     beam/erl_bif_guard.c
+/* map:find/2
+ * return value if key *equals* a key in the map
  */
 
-BIF_RETTYPE map_size_1(BIF_ALIST_1) {
-    if (is_map(BIF_ARG_1)) {
-	Eterm *hp;
-	Uint hsz  = 0;
-	map_t *mp = (map_t*)map_val(BIF_ARG_1);
-	Uint n    = map_get_size(mp);
+BIF_RETTYPE map_find_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Eterm *hp, *ks,*vs, key, res;
+	map_t *mp;
+	Uint n,i;
 
-	erts_bld_uint(NULL, &hsz, n);
-	hp = HAlloc(BIF_P, hsz);
-	BIF_RET(erts_bld_uint(&hp, NULL, n));
-    }
+	mp  = (map_t*)map_val(BIF_ARG_2);
+	key = BIF_ARG_1;
+	n   = map_get_size(mp);
+	ks  = map_get_keys(mp);
+	vs  = map_get_values(mp);
 
+	for( i = 0; i < n; i++) {
+	    if (CMP(ks[i], key)==0) {
+		hp    = HAlloc(BIF_P, 3);
+		res   = make_tuple(hp);
+		*hp++ = make_arityval(2);
+		*hp++ = am_ok;
+		*hp++ = vs[i];
+		BIF_RET(res);
+	    }
+	}
+	BIF_RET(am_error);
+    }
     BIF_ERROR(BIF_P, BADARG);
 }
-
-BIF_RETTYPE map_new_0(BIF_ALIST_0) {
-    Eterm* hp;
-    Eterm tup;
-    map_t *mp;
-
-    hp    = HAlloc(BIF_P, (3 + 1));
-    tup   = make_tuple(hp);
-    *hp++ = make_arityval(0);
-
-    mp    = (map_t*)hp;
-    mp->thing_word = MAP_HEADER;
-    mp->size = 0;
-    mp->keys = tup;
-
-    BIF_RET(make_map(mp));
-}
+/* map:get/2
+ * return value if key *matches* a key in the map
+ * exception bad_key if none matches
+ */
 
 BIF_RETTYPE map_get_2(BIF_ALIST_2) {
     if (is_map(BIF_ARG_2)) {
@@ -136,6 +184,297 @@ error:
     BIF_ERROR(BIF_P, BADARG);
 }
 
+/* map:from_list/1
+ * List may be unsorted [{K,V}]
+ */
+
+BIF_RETTYPE map_from_list_1(BIF_ALIST_1) {
+    Eterm *kv, item = BIF_ARG_1;
+    Eterm *hp, *thp,*vs, *ks, keys, res;
+    map_t *mp;
+    Uint  size = 0, unused_size = 0;
+    Sint  c = 0;
+    Sint  idx = 0;
+
+    if (is_list(item) || is_nil(item)) {
+
+	/* Calculate size and check validity */
+
+	while(is_list(item)) {
+	    res = CAR(list_val(item));
+	    if (is_not_tuple(res))
+		goto error;
+
+	    kv = tuple_val(res);
+	    if (*kv != make_arityval(2))
+		goto error;
+
+	    size++;
+	    item = CDR(list_val(item));
+	}
+
+	if (is_not_nil(item))
+	    goto error;
+
+	hp    = HAlloc(BIF_P, 3 + 1 + (2 * size));
+	thp   = hp;
+	keys  = make_tuple(hp);
+	*hp++ = make_arityval(size);
+	ks    = hp;
+	hp   += size;
+	mp    = (map_t*)hp;
+	res   = make_map(mp);
+	hp   += MAP_HEADER_SIZE;
+	vs    = hp;
+
+	mp->thing_word = MAP_HEADER;
+	mp->size = size; /* set later, might shrink*/
+	mp->keys = keys;
+
+	if (size == 0)
+	    BIF_RET(res);
+
+	item  = BIF_ARG_1;
+
+	/* first entry */
+	kv    = tuple_val(CAR(list_val(item)));
+	ks[0] = kv[1];
+	vs[0] = kv[2];
+	size  = 1;
+	item  = CDR(list_val(item));
+
+	/* insert sort key/value pairs */
+	while(is_list(item)) {
+
+	    kv = tuple_val(CAR(list_val(item)));
+
+	    /* compare ks backwards
+	     * idx represent word index to be written (hole position).
+	     * We cannot copy the elements when searching since we might
+	     * have an equal key. So we search for just the index first =(
+	     *
+	     * It is perhaps faster to move the values in the first pass.
+	     * Check for uniqueness during insert phase and then have a
+	     * second phace compacting the map if duplicates are found
+	     * during insert. .. or do someother sort .. shell-sort perhaps.
+	     */
+
+	    idx = size;
+
+	    while(idx > 0 && (c = CMP(kv[1],ks[idx-1])) < 0) { idx--; }
+
+	    if (c == 0) {
+		/* last compare was equal,
+		 * i.e. we have to release memory
+		 * and overwrite that key/value
+		 */
+		ks[idx-1] = kv[1];
+		vs[idx-1] = kv[2];
+		unused_size++;
+	    } else {
+		Uint i = size;
+		while(i > idx) {
+		    ks[i] = ks[i-1];
+		    vs[i] = vs[i-1];
+		    i--;
+		}
+		ks[idx] = kv[1];
+		vs[idx] = kv[2];
+		size++;
+	    }
+	    item = CDR(list_val(item));
+	}
+
+	if (unused_size) {
+	    /* the key tuple is embedded in the heap
+	     * write a bignum to clear it.
+	     */
+	    /* release values as normal since they are on the top of the heap */
+
+	    ks[size] = make_pos_bignum_header(unused_size - 1);
+	    HRelease(BIF_P, vs + size + unused_size, vs + size);
+	}
+
+	*thp = make_arityval(size);
+	mp->size = size;
+	BIF_RET(res);
+    }
+
+error:
+
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* map:is_key/2
+ */
+
+BIF_RETTYPE map_is_key_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Eterm *ks, key;
+	map_t *mp;
+	Uint n,i;
+
+	mp  = (map_t*)map_val(BIF_ARG_2);
+	key = BIF_ARG_1;
+	n   = map_get_size(mp);
+	ks  = map_get_keys(mp);
+
+	if (n == 0)
+	    BIF_RET(am_false);
+
+	if (is_immed(key)) {
+	    for( i = 0; i < n; i++) {
+		if (ks[i] == key) {
+		    BIF_RET(am_true);
+		}
+	    }
+	}
+
+	for( i = 0; i < n; i++) {
+	    if (eq(ks[i], key)) {
+		BIF_RET(am_true);
+	    }
+	}
+	BIF_RET(am_false);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* map:keys/1
+ */
+
+BIF_RETTYPE map_keys_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Eterm *hp, *ks, res = NIL;
+	map_t *mp;
+	Uint n;
+
+	mp  = (map_t*)map_val(BIF_ARG_1);
+	n   = map_get_size(mp);
+
+	if (n == 0)
+	    BIF_RET(res);
+
+	hp  = HAlloc(BIF_P, (2 * n));
+	ks  = map_get_keys(mp);
+
+	while(n--) {
+	    res = CONS(hp, ks[n], res); hp += 2;
+	}
+
+	BIF_RET(res);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+/* map:merge/2
+ */
+
+BIF_RETTYPE map_merge_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_1) && is_map(BIF_ARG_2)) {
+	Eterm *hp,*thp;
+	Eterm tup;
+	Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2;
+	map_t *mp1,*mp2,*mp_new;
+	Uint n1,n2,i1,i2,need,unused_size=0;
+	int c = 0;
+
+	mp1  = (map_t*)map_val(BIF_ARG_1);
+	mp2  = (map_t*)map_val(BIF_ARG_2);
+	n1   = map_get_size(mp1);
+	n2   = map_get_size(mp2);
+
+	need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2);
+
+	hp     = HAlloc(BIF_P, need);
+	thp    = hp;
+	tup    = make_tuple(thp);
+	ks     = hp + 1; hp += 1 + n1 + n2;
+	mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE;
+	vs     = hp; hp += n1 + n2;
+
+	mp_new->thing_word = MAP_HEADER;
+	mp_new->size = 0;
+	mp_new->keys = tup;
+
+	i1  = 0; i2 = 0;
+	ks1 = map_get_keys(mp1);
+	vs1 = map_get_values(mp1);
+	ks2 = map_get_keys(mp2);
+	vs2 = map_get_values(mp2);
+
+	while(i1 < n1 && i2 < n2) {
+	    c = CMP(ks1[i1],ks2[i2]);
+	    if ( c == 0) {
+		/* use righthand side arguments map value,
+		 * but advance both maps */
+		*ks++ = ks2[i2];
+		*vs++ = vs2[i2];
+		i1++, i2++, unused_size++;
+	    } else if ( c < 0) {
+		*ks++ = ks1[i1];
+		*vs++ = vs1[i1];
+		i1++;
+	    } else {
+		*ks++ = ks2[i2];
+		*vs++ = vs2[i2];
+		i2++;
+	    }
+	}
+
+	/* copy remaining */
+	while (i1 < n1) {
+	    *ks++ = ks1[i1];
+	    *vs++ = vs1[i1];
+	    i1++;
+	}
+
+	while (i2 < n2) {
+	    *ks++ = ks2[i2];
+	    *vs++ = vs2[i2];
+	    i2++;
+	}
+
+	if (unused_size) {
+	    /* the key tuple is embedded in the heap, write a bignum to clear it.
+	     *
+	     * release values as normal since they are on the top of the heap
+	     * size = n1 + n1 - unused_size
+	     */
+
+	    *ks = make_pos_bignum_header(unused_size - 1);
+	    HRelease(BIF_P, vs + unused_size, vs);
+	}
+
+	mp_new->size = n1 + n2 - unused_size;
+	*thp = make_arityval(n1 + n2 - unused_size);
+
+	BIF_RET(make_map(mp_new));
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+/* map:new/2
+ */
+
+BIF_RETTYPE map_new_0(BIF_ALIST_0) {
+    Eterm* hp;
+    Eterm tup;
+    map_t *mp;
+
+    hp    = HAlloc(BIF_P, (3 + 1));
+    tup   = make_tuple(hp);
+    *hp++ = make_arityval(0);
+
+    mp    = (map_t*)hp;
+    mp->thing_word = MAP_HEADER;
+    mp->size = 0;
+    mp->keys = tup;
+
+    BIF_RET(make_map(mp));
+}
+
+/* map:put/3
+ */
+
 BIF_RETTYPE map_put_3(BIF_ALIST_3) {
     if (is_map(BIF_ARG_3)) {
 	Sint n,i;
@@ -242,3 +581,167 @@ BIF_RETTYPE map_put_3(BIF_ALIST_3) {
 
     BIF_ERROR(BIF_P, BADARG);
 }
+
+/* map:remove/3
+ */
+
+BIF_RETTYPE map_remove_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Sint n;
+	Sint found = 0;
+	Uint need;
+	Eterm *thp, *mhp;
+	Eterm *ks, *vs, res, key,tup;
+	map_t *mp = (map_t*)map_val(BIF_ARG_2);
+
+	key = BIF_ARG_1;
+	n   = map_get_size(mp);
+
+	if (n == 0)
+	    BIF_RET(BIF_ARG_2);
+
+	ks  = map_get_keys(mp);
+	vs  = map_get_values(mp);
+
+	/* Assume key exists.
+	 * Release allocated if it didn't.
+	 * Allocate key tuple first.
+	 */
+
+	need   = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */
+	thp    = HAlloc(BIF_P, need);
+	mhp    = thp + n;               /* offset with tuple heap size */
+
+	tup    = make_tuple(thp);
+	*thp++ = make_arityval(n - 1);
+
+	res    = make_map(mhp);
+	*mhp++ = MAP_HEADER;
+	*mhp++ = n - 1;
+	*mhp++ = tup;
+
+	if (is_immed(key)) {
+	    while(n--) {
+		if (*ks == key) {
+		    ks++;
+		    vs++;
+		    found = 1;
+		} else {
+		    *mhp++ = *vs++;
+		    *thp++ = *ks++;
+		}
+	    }
+	} else {
+	    while(n--) {
+		if (eq(*ks, key)) {
+		    ks++;
+		    vs++;
+		    found = 1;
+		} else {
+		    *mhp++ = *vs++;
+		    *thp++ = *ks++;
+		}
+	    }
+	}
+
+	if (found)
+	    BIF_RET(res);
+
+	/* Not found, remove allocated memory
+	 * and return previous map.
+	 */
+	HRelease(BIF_P, thp + need, thp);
+	BIF_RET(BIF_ARG_2);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* map:update/3
+ */
+
+BIF_RETTYPE map_update_3(BIF_ALIST_3) {
+    if (is_map(BIF_ARG_3)) {
+	Sint n,i;
+	Sint found = 0;
+	Eterm* hp,*shp;
+	Eterm *ks,*vs, res, key;
+	map_t *mp = (map_t*)map_val(BIF_ARG_3);
+
+	key = BIF_ARG_1;
+	n   = map_get_size(mp);
+
+	if (n == 0) {
+	    BIF_ERROR(BIF_P, BADARG);
+	}
+
+	ks  = map_get_keys(mp);
+	vs  = map_get_values(mp);
+
+	/* only allocate for values,
+	 * assume key-tuple will be intact
+	 */
+
+	hp  = HAlloc(BIF_P, 3 + n);
+	shp = hp;
+	res = make_map(hp);
+	*hp++ = MAP_HEADER;
+	*hp++ = n;
+	*hp++ = mp->keys;
+
+	if (is_immed(key)) {
+	    for( i = 0; i < n; i ++) {
+		if (ks[i] == key) {
+		    *hp++ = BIF_ARG_2;
+		    vs++;
+		    found = 1;
+		} else {
+		    *hp++ = *vs++;
+		}
+	    }
+	} else {
+	    for( i = 0; i < n; i ++) {
+		if (eq(ks[i], key)) {
+		    *hp++ = BIF_ARG_2;
+		    vs++;
+		    found = 1;
+		} else {
+		    *hp++ = *vs++;
+		}
+	    }
+	}
+
+	if (found)
+	    BIF_RET(res);
+
+	HRelease(BIF_P, shp + 3 + n, shp);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+
+/* map:values/1
+ */
+
+BIF_RETTYPE map_values_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Eterm *hp, *vs, res = NIL;
+	map_t *mp;
+	Uint n;
+
+	mp  = (map_t*)map_val(BIF_ARG_1);
+	n   = map_get_size(mp);
+
+	if (n == 0)
+	    BIF_RET(res);
+
+	hp  = HAlloc(BIF_P, (2 * n));
+	vs  = map_get_values(mp);
+
+	while(n--) {
+	    res = CONS(hp, vs[n], res); hp += 2;
+	}
+
+	BIF_RET(res);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index ca8ce0f974..4f0d26e100 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -33,11 +33,12 @@ typedef struct map_s {
  *
  * -----------
  * Eterm   THING	
- * Eterm   Keys -> {K1, K2, K3, ..., Kn} where n = arity
+ * Uint    size
+ * Eterm   Keys -> {K1, K2, K3, ..., Kn} where n = size
  * ----
  * Eterm   V1
  * ...
- * Eterm   Vn, where n = arity
+ * Eterm   Vn, where n = size
  * -----------
  */
 
@@ -59,6 +60,7 @@ typedef struct map_s {
 #define map_get_size(x)        (((map_t*)(x))->size)
 
 #define MAP_HEADER             _make_header(1,_TAG_HEADER_MAP)
+#define MAP_HEADER_SIZE        (sizeof(map_t) / sizeof(Eterm))
 
 #endif