erts: Move hashmap:put/3, update/3 to maps

3 files changed, 247 insertions, 259 deletions

diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 5b0f90d418..55a7b62e7d 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -615,8 +615,6 @@ bif erlang:fun_info_mfa/1
 bif erlang:get_keys/0
 
 # Hash Array Mappped Trie
-bif hashmap:put/3
-bif hashmap:update/3
 bif hashmap:remove/2
 bif hashmap:info/1
 bif hashmap:from_list/1
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 7e0e7fde04..594a404e9f 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -60,7 +60,6 @@ static char *format_binary(Uint64 x, char *b) {
 }
 #endif
 
-static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update);
 
 /* for hashmap_from_list/1 */
 typedef struct {
@@ -97,32 +96,8 @@ BIF_RETTYPE hashmap_new_0(BIF_ALIST_0) {
 
 /* hashmap:put/3 */
 
-BIF_RETTYPE hashmap_put_3(BIF_ALIST_3) {
-    if (is_hashmap(BIF_ARG_3)) {
-	Uint32 hx = hashmap_make_hash(BIF_ARG_1);
-	Eterm map;
-
-	map = hashmap_insert(BIF_P, hx, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, 0);
-	ASSERT(is_hashmap(map));
-	BIF_RET(map);
-    }
-    BIF_ERROR(BIF_P, BADARG);
-}
-
 /* hashmap:update/3 */
 
-BIF_RETTYPE hashmap_update_3(BIF_ALIST_3) {
-    if (is_hashmap(BIF_ARG_3)) {
-	Uint32 hx = hashmap_make_hash(BIF_ARG_1);
-	Eterm map;
-
-	map = hashmap_insert(BIF_P, hx, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, 1);
-	if (is_value(map))
-	    BIF_RET(map);
-    }
-    BIF_ERROR(BIF_P, BADARG);
-}
-
 /* hashmap:to_list/1 */
 
 /* hashmap:from_list/1 */
@@ -168,238 +143,6 @@ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) {
 /* impl. */
 
 
-static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value,
-			    Eterm node, int is_update) {
-    Eterm *hp = NULL, *nhp = NULL;
-    Eterm *ptr;
-    Eterm hdr,res,ckey,fake;
-    Eterm th[2];
-    Uint32 ix, cix, bp, hval, chx;
-    Uint slot, lvl = 0, clvl;
-    Uint size = 0, n = 0, update_size = 1;
-    DECLARE_ESTACK(stack);
-
-    for (;;) {
-	switch(primary_tag(node)) {
-	    case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
-		ptr  = list_val(node);
-		ckey = CAR(ptr);
-		if (EQ(ckey, key)) {
-		    update_size = 0;
-		    goto unroll;
-		}
-		if (is_update) {
-		    res = THE_NON_VALUE;
-		    goto bail_out;
-		}
-		goto insert_subnodes;
-	    case TAG_PRIMARY_BOXED:
-		ptr = boxed_val(node);
-		hdr = *ptr;
-		ASSERT(is_header(hdr));
-
-		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-		    case HAMT_SUBTAG_NODE_ARRAY:
-			ix    = hashmap_index(hx);
-			hx    = hashmap_shift_hash(th,hx,lvl,key);
-			size += HAMT_NODE_ARRAY_SZ;
-			ESTACK_PUSH2(stack, ix, node);
-			node  = ptr[ix+1];
-			break;
-		    case HAMT_SUBTAG_HEAD_ARRAY:
-			ix    = hashmap_index(hx);
-			hx    = hashmap_shift_hash(th,hx,lvl,key);
-			size += HAMT_HEAD_ARRAY_SZ;
-			ESTACK_PUSH2(stack, ix, node);
-			node  = ptr[ix+2];
-			break;
-		    case HAMT_SUBTAG_NODE_BITMAP:
-			hval = MAP_HEADER_VAL(hdr);
-			ix   = hashmap_index(hx);
-			bp   = 1 << ix;
-			slot = hashmap_bitcount(hval & (bp - 1));
-			n    = hashmap_bitcount(hval);
-
-			ESTACK_PUSH(stack, n);
-			ESTACK_PUSH3(stack, bp, slot, node);
-
-			/* occupied */
-			if (bp & hval) {
-			    hx    = hashmap_shift_hash(th,hx,lvl,key);
-			    node  = ptr[slot+1];
-			    ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); 
-			    size += HAMT_NODE_BITMAP_SZ(n);
-			    break;
-			}
-			/* not occupied */
-			if (is_update) {
-			    res = THE_NON_VALUE;
-			    goto bail_out;
-			}
-			size += HAMT_NODE_BITMAP_SZ(n+1);
-			goto unroll;
-		    case HAMT_SUBTAG_HEAD_BITMAP:
-			hval = MAP_HEADER_VAL(hdr);
-			ix   = hashmap_index(hx);
-			bp   = 1 << ix;
-			slot = hashmap_bitcount(hval & (bp - 1));
-			n    = hashmap_bitcount(hval);
-
-			ESTACK_PUSH(stack, n);
-			ESTACK_PUSH3(stack, bp, slot, node);
-
-			/* occupied */
-			if (bp & hval) {
-			    hx    = hashmap_shift_hash(th,hx,lvl,key);
-			    node  = ptr[slot+2];
-			    ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); 
-			    size += HAMT_HEAD_BITMAP_SZ(n);
-			    break;
-			}
-			/* not occupied */
-			if (is_update) {
-			    res = THE_NON_VALUE;
-			    goto bail_out;
-			}
-			size += HAMT_HEAD_BITMAP_SZ(n+1);
-			goto unroll;
-		    default:
-			erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-			break;
-		}
-		break;
-	    default:
-		erl_exit(1, "bad primary tag %p\r\n", node);
-		break;
-	}
-    }
-insert_subnodes:
-    clvl  = lvl;
-    chx   = hashmap_restore_hash(th,clvl,ckey);
-    size += HAMT_NODE_BITMAP_SZ(2);
-    ix    = hashmap_index(hx);
-    cix   = hashmap_index(chx);
-
-    while (cix == ix) {
-	ESTACK_PUSH(stack, 0);
-	ESTACK_PUSH3(stack, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0));
-	size += HAMT_NODE_BITMAP_SZ(1);
-	hx    = hashmap_shift_hash(th,hx,lvl,key);
-	chx   = hashmap_shift_hash(th,chx,clvl,ckey);
-	ix    = hashmap_index(hx);
-	cix   = hashmap_index(chx);
-    }
-    ESTACK_PUSH3(stack, cix, ix, node);
-
-unroll:
-    size += 2;
-    hp  = HAlloc(p, size);
-    res = CONS(hp, key, value); hp += 2;
-
-    do {
-	node = ESTACK_POP(stack);
-	switch(primary_tag(node)) {
-	    case TAG_PRIMARY_LIST:
-		ix   = (Uint32) ESTACK_POP(stack);
-		cix  = (Uint32) ESTACK_POP(stack);
-
-		nhp   = hp;
-		*hp++ = MAP_HEADER_HAMT_NODE_BITMAP((1 << ix) | (1 << cix));
-		if (ix < cix) {
-		    *hp++ = res;
-		    *hp++ = node;
-		} else {
-		    *hp++ = node;
-		    *hp++ = res;
-		}
-		res = make_hashmap(nhp);
-		break;
-	    case TAG_PRIMARY_HEADER:
-		/* subnodes, fake it */
-		fake = node;
-		node = make_boxed(&fake);
-	    case TAG_PRIMARY_BOXED:
-		ptr = boxed_val(node);
-		hdr = *ptr;
-		ASSERT(is_header(hdr));
-
-		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-		    case HAMT_SUBTAG_NODE_ARRAY:
-			slot  = (Uint)   ESTACK_POP(stack);
-			nhp   = hp;
-			n     = HAMT_NODE_ARRAY_SZ;
-			while(n--) { *hp++ = *ptr++; }
-			nhp[slot+1] = res;
-			res = make_hashmap(nhp);
-			break;
-		    case HAMT_SUBTAG_HEAD_ARRAY:
-			slot  = (Uint)   ESTACK_POP(stack);
-			nhp   = hp;
-			n     = HAMT_HEAD_ARRAY_SZ - 2;
-			*hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
-			*hp++ = (*ptr++) + update_size;
-			while(n--) { *hp++ = *ptr++; }
-			nhp[slot+2] = res;
-			res = make_hashmap(nhp);
-			break;
-		    case HAMT_SUBTAG_NODE_BITMAP:
-			slot  = (Uint)   ESTACK_POP(stack);
-			bp    = (Uint32) ESTACK_POP(stack);
-			n     = (Uint32) ESTACK_POP(stack);
-			hval  = MAP_HEADER_VAL(hdr);
-			nhp   = hp;
-			*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval | bp); ptr++;
-
-			n -= slot;
-			while(slot--) { *hp++ = *ptr++; }
-			*hp++ = res;
-			if (hval & bp) { ptr++; n--; }
-			while(n--) { *hp++ = *ptr++; }
-
-			if ((hval | bp) == 0xffff) {
-			    *nhp = make_arityval(16);
-			}
-			res = make_hashmap(nhp);
-			break;
-		    case HAMT_SUBTAG_HEAD_BITMAP:
-			slot  = (Uint)   ESTACK_POP(stack);
-			bp    = (Uint32) ESTACK_POP(stack);
-			n     = (Uint32) ESTACK_POP(stack);
-			hval  = MAP_HEADER_VAL(hdr);
-			nhp   = hp;
-			*hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++;
-			*hp++ = (*ptr++) + update_size;
-
-			n -= slot;
-			while(slot--) { *hp++ = *ptr++; }
-			*hp++ = res;
-			if (hval & bp) { ptr++; n--; }
-			while(n--) { *hp++ = *ptr++; }
-
-			if ((hval | bp) == 0xffff) {
-			    *nhp = MAP_HEADER_HAMT_HEAD_ARRAY;
-			}
-			res = make_hashmap(nhp);
-			break;
-		    default:
-			erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-			break;
-		}
-		break;
-	    default:
-		erl_exit(1, "bad primary tag %x\r\n", primary_tag(node));
-		break;
-	}
-
-    } while(!ESTACK_ISEMPTY(stack));
-
-bail_out:
-    DESTROY_ESTACK(stack);
-    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-    ERTS_HOLE_CHECK(p);
-    return res;
-}
-
 static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) {
     Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL;
     Eterm th[2];
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 304b5470f5..f99a1b431b 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -64,6 +64,7 @@
  */
 
 static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node);
+static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update);
 static Eterm hashmap_to_list(Process *p, Eterm map);
 static Eterm hashmap_keys(Process *p, Eterm map);
 static Eterm hashmap_values(Process *p, Eterm map);
@@ -594,6 +595,13 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 BIF_RETTYPE maps_put_3(BIF_ALIST_3) {
     if (is_map(BIF_ARG_3)) {
 	BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3));
+    } else if (is_hashmap(BIF_ARG_3)) {
+	Uint32 hx = hashmap_make_hash(BIF_ARG_1);
+	Eterm map;
+
+	map = hashmap_insert(BIF_P, hx, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, 0);
+	ASSERT(is_hashmap(map));
+	BIF_RET(map);
     }
     BIF_ERROR(BIF_P, BADARG);
 }
@@ -748,6 +756,13 @@ BIF_RETTYPE maps_update_3(BIF_ALIST_3) {
 	if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) {
 	    BIF_RET(res);
 	}
+    } else if (is_hashmap(BIF_ARG_3)) {
+	Uint32 hx = hashmap_make_hash(BIF_ARG_1);
+	Eterm map;
+
+	map = hashmap_insert(BIF_P, hx, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, 1);
+	if (is_value(map))
+	    BIF_RET(map);
     }
     BIF_ERROR(BIF_P, BADARG);
 }
@@ -920,6 +935,238 @@ static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) {
     return NULL;
 }
 
+static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value,
+			    Eterm node, int is_update) {
+    Eterm *hp = NULL, *nhp = NULL;
+    Eterm *ptr;
+    Eterm hdr,res,ckey,fake;
+    Eterm th[2];
+    Uint32 ix, cix, bp, hval, chx;
+    Uint slot, lvl = 0, clvl;
+    Uint size = 0, n = 0, update_size = 1;
+    DECLARE_ESTACK(stack);
+
+    for (;;) {
+	switch(primary_tag(node)) {
+	    case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
+		ptr  = list_val(node);
+		ckey = CAR(ptr);
+		if (EQ(ckey, key)) {
+		    update_size = 0;
+		    goto unroll;
+		}
+		if (is_update) {
+		    res = THE_NON_VALUE;
+		    goto bail_out;
+		}
+		goto insert_subnodes;
+	    case TAG_PRIMARY_BOXED:
+		ptr = boxed_val(node);
+		hdr = *ptr;
+		ASSERT(is_header(hdr));
+
+		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
+		    case HAMT_SUBTAG_NODE_ARRAY:
+			ix    = hashmap_index(hx);
+			hx    = hashmap_shift_hash(th,hx,lvl,key);
+			size += HAMT_NODE_ARRAY_SZ;
+			ESTACK_PUSH2(stack, ix, node);
+			node  = ptr[ix+1];
+			break;
+		    case HAMT_SUBTAG_HEAD_ARRAY:
+			ix    = hashmap_index(hx);
+			hx    = hashmap_shift_hash(th,hx,lvl,key);
+			size += HAMT_HEAD_ARRAY_SZ;
+			ESTACK_PUSH2(stack, ix, node);
+			node  = ptr[ix+2];
+			break;
+		    case HAMT_SUBTAG_NODE_BITMAP:
+			hval = MAP_HEADER_VAL(hdr);
+			ix   = hashmap_index(hx);
+			bp   = 1 << ix;
+			slot = hashmap_bitcount(hval & (bp - 1));
+			n    = hashmap_bitcount(hval);
+
+			ESTACK_PUSH(stack, n);
+			ESTACK_PUSH3(stack, bp, slot, node);
+
+			/* occupied */
+			if (bp & hval) {
+			    hx    = hashmap_shift_hash(th,hx,lvl,key);
+			    node  = ptr[slot+1];
+			    ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17);
+			    size += HAMT_NODE_BITMAP_SZ(n);
+			    break;
+			}
+			/* not occupied */
+			if (is_update) {
+			    res = THE_NON_VALUE;
+			    goto bail_out;
+			}
+			size += HAMT_NODE_BITMAP_SZ(n+1);
+			goto unroll;
+		    case HAMT_SUBTAG_HEAD_BITMAP:
+			hval = MAP_HEADER_VAL(hdr);
+			ix   = hashmap_index(hx);
+			bp   = 1 << ix;
+			slot = hashmap_bitcount(hval & (bp - 1));
+			n    = hashmap_bitcount(hval);
+
+			ESTACK_PUSH(stack, n);
+			ESTACK_PUSH3(stack, bp, slot, node);
+
+			/* occupied */
+			if (bp & hval) {
+			    hx    = hashmap_shift_hash(th,hx,lvl,key);
+			    node  = ptr[slot+2];
+			    ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18);
+			    size += HAMT_HEAD_BITMAP_SZ(n);
+			    break;
+			}
+			/* not occupied */
+			if (is_update) {
+			    res = THE_NON_VALUE;
+			    goto bail_out;
+			}
+			size += HAMT_HEAD_BITMAP_SZ(n+1);
+			goto unroll;
+		    default:
+			erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
+			break;
+		}
+		break;
+	    default:
+		erl_exit(1, "bad primary tag %p\r\n", node);
+		break;
+	}
+    }
+insert_subnodes:
+    clvl  = lvl;
+    chx   = hashmap_restore_hash(th,clvl,ckey);
+    size += HAMT_NODE_BITMAP_SZ(2);
+    ix    = hashmap_index(hx);
+    cix   = hashmap_index(chx);
+
+    while (cix == ix) {
+	ESTACK_PUSH(stack, 0);
+	ESTACK_PUSH3(stack, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0));
+	size += HAMT_NODE_BITMAP_SZ(1);
+	hx    = hashmap_shift_hash(th,hx,lvl,key);
+	chx   = hashmap_shift_hash(th,chx,clvl,ckey);
+	ix    = hashmap_index(hx);
+	cix   = hashmap_index(chx);
+    }
+    ESTACK_PUSH3(stack, cix, ix, node);
+
+unroll:
+    size += 2;
+    hp  = HAlloc(p, size);
+    res = CONS(hp, key, value); hp += 2;
+
+    do {
+	node = ESTACK_POP(stack);
+	switch(primary_tag(node)) {
+	    case TAG_PRIMARY_LIST:
+		ix   = (Uint32) ESTACK_POP(stack);
+		cix  = (Uint32) ESTACK_POP(stack);
+
+		nhp   = hp;
+		*hp++ = MAP_HEADER_HAMT_NODE_BITMAP((1 << ix) | (1 << cix));
+		if (ix < cix) {
+		    *hp++ = res;
+		    *hp++ = node;
+		} else {
+		    *hp++ = node;
+		    *hp++ = res;
+		}
+		res = make_hashmap(nhp);
+		break;
+	    case TAG_PRIMARY_HEADER:
+		/* subnodes, fake it */
+		fake = node;
+		node = make_boxed(&fake);
+	    case TAG_PRIMARY_BOXED:
+		ptr = boxed_val(node);
+		hdr = *ptr;
+		ASSERT(is_header(hdr));
+
+		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
+		    case HAMT_SUBTAG_NODE_ARRAY:
+			slot  = (Uint)   ESTACK_POP(stack);
+			nhp   = hp;
+			n     = HAMT_NODE_ARRAY_SZ;
+			while(n--) { *hp++ = *ptr++; }
+			nhp[slot+1] = res;
+			res = make_hashmap(nhp);
+			break;
+		    case HAMT_SUBTAG_HEAD_ARRAY:
+			slot  = (Uint)   ESTACK_POP(stack);
+			nhp   = hp;
+			n     = HAMT_HEAD_ARRAY_SZ - 2;
+			*hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
+			*hp++ = (*ptr++) + update_size;
+			while(n--) { *hp++ = *ptr++; }
+			nhp[slot+2] = res;
+			res = make_hashmap(nhp);
+			break;
+		    case HAMT_SUBTAG_NODE_BITMAP:
+			slot  = (Uint)   ESTACK_POP(stack);
+			bp    = (Uint32) ESTACK_POP(stack);
+			n     = (Uint32) ESTACK_POP(stack);
+			hval  = MAP_HEADER_VAL(hdr);
+			nhp   = hp;
+			*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval | bp); ptr++;
+
+			n -= slot;
+			while(slot--) { *hp++ = *ptr++; }
+			*hp++ = res;
+			if (hval & bp) { ptr++; n--; }
+			while(n--) { *hp++ = *ptr++; }
+
+			if ((hval | bp) == 0xffff) {
+			    *nhp = make_arityval(16);
+			}
+			res = make_hashmap(nhp);
+			break;
+		    case HAMT_SUBTAG_HEAD_BITMAP:
+			slot  = (Uint)   ESTACK_POP(stack);
+			bp    = (Uint32) ESTACK_POP(stack);
+			n     = (Uint32) ESTACK_POP(stack);
+			hval  = MAP_HEADER_VAL(hdr);
+			nhp   = hp;
+			*hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++;
+			*hp++ = (*ptr++) + update_size;
+
+			n -= slot;
+			while(slot--) { *hp++ = *ptr++; }
+			*hp++ = res;
+			if (hval & bp) { ptr++; n--; }
+			while(n--) { *hp++ = *ptr++; }
+
+			if ((hval | bp) == 0xffff) {
+			    *nhp = MAP_HEADER_HAMT_HEAD_ARRAY;
+			}
+			res = make_hashmap(nhp);
+			break;
+		    default:
+			erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
+			break;
+		}
+		break;
+	    default:
+		erl_exit(1, "bad primary tag %x\r\n", primary_tag(node));
+		break;
+	}
+
+    } while(!ESTACK_ISEMPTY(stack));
+
+bail_out:
+    DESTROY_ESTACK(stack);
+    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+    ERTS_HOLE_CHECK(p);
+    return res;
+}
+
 static Eterm hashmap_keys(Process* p, Eterm node) {
     DECLARE_WSTACK(stack);
     hashmap_head_t* root;