erts: Move hashmap:remove/2 to maps

3 files changed, 255 insertions, 261 deletions

diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 55a7b62e7d..320cd39da8 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -615,7 +615,6 @@ bif erlang:fun_info_mfa/1
 bif erlang:get_keys/0
 
 # Hash Array Mappped Trie
-bif hashmap:remove/2
 bif hashmap:info/1
 bif hashmap:from_list/1
 bif hashmap:new/0
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 594a404e9f..9b16a5a88f 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -69,7 +69,6 @@ typedef struct {
     Eterm  val;
 } hxnode_t;
 
-static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node);
 static Eterm hashmap_from_list(Process *p, Eterm node);
 static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
 static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
@@ -115,14 +114,6 @@ BIF_RETTYPE hashmap_from_list_1(BIF_ALIST_1) {
 
 /* hashmap:remove/2 */
 
-BIF_RETTYPE hashmap_remove_2(BIF_ALIST_2) {
-    if (is_hashmap(BIF_ARG_2)) {
-	Uint32 hx = hashmap_make_hash(BIF_ARG_1);
-
-	BIF_RET(hashmap_delete(BIF_P, hx, BIF_ARG_1, BIF_ARG_2));
-    }
-    BIF_ERROR(BIF_P, BADARG);
-}
 /* hashmap:size/1 */
 
 /* erlang:is_hashmap/1 */
@@ -143,255 +134,6 @@ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) {
 /* impl. */
 
 
-static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) {
-    Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL;
-    Eterm th[2];
-    Eterm *ptr;
-    Eterm hdr,res = node;
-    Uint32 ix, bp, hval;
-    Uint slot, lvl = 0;
-    Uint size = 0, n = 0;
-    DECLARE_ESTACK(stack);
-
-    for (;;) {
-	switch(primary_tag(node)) {
-	    case TAG_PRIMARY_LIST:
-		if (EQ(CAR(list_val(node)), key)) {
-		    goto unroll;
-		}
-		goto not_found;
-	    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 */
-			goto not_found;
-		    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 */
-			goto not_found;
-		    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;
-	}
-    }
-
-unroll:
-    /* the size is bounded and atleast one less than the previous size */
-    size  -= 1;
-    hp     = HAlloc(p, size);
-    hp_end = hp + size;
-    res    = THE_NON_VALUE;
-
-    do {
-	node = ESTACK_POP(stack);
-
-	/* all nodes are things */
-	ptr = boxed_val(node);
-	hdr = *ptr;
-	ASSERT(is_header(hdr));
-
-	switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-	    case HAMT_SUBTAG_NODE_ARRAY:
-		ix  = (Uint) ESTACK_POP(stack);
-		nhp = hp;
-		if (res == THE_NON_VALUE) {
-		    *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(0xffff ^ (1 << ix)); ptr++;
-		    n     = 16;
-		    n    -= ix;
-		    while(ix--) { *hp++ = *ptr++; }
-		    ptr++; n--;
-		    while(n--) { *hp++ = *ptr++; }
-		    res = make_hashmap(nhp);
-		} else {
-		    n = HAMT_NODE_ARRAY_SZ;
-		    while(n--) { *hp++ = *ptr++; }
-		    nhp[ix+1] = res;
-		    res = make_hashmap(nhp);
-		}
-		break;
-	    case HAMT_SUBTAG_HEAD_ARRAY:
-		ix  = (Uint) ESTACK_POP(stack);
-		nhp = hp;
-		if (res == THE_NON_VALUE) {
-		    n     = 16;
-		    n    -= ix;
-		    *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(0xffff ^ (1 << ix)); ptr++;
-		    *hp++ = (*ptr++) - 1;
-		    while(ix--) { *hp++ = *ptr++; }
-		    ptr++; n--;
-		    while(n--) { *hp++ = *ptr++; }
-		    res = make_hashmap(nhp);
-		} else {
-		    n     = 16;
-		    *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
-		    *hp++ = (*ptr++) - 1;
-		    while(n--) { *hp++ = *ptr++; }
-		    nhp[ix+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);
-		nhp  = hp;
-
-		/* bitmap change matrix
-		 * res | none    leaf    bitmap
-		 * ----------------------------
-		 * n=1 | remove  remove  keep
-		 * n=2 | other   keep    keep
-		 * n>2 | shrink  keep    keep
-		 *
-		 * other: (remember, n is 2)
-		 *   shrink if the other bitmap value is a bitmap node
-		 *   remove if the other bitmap value is a leaf
-		 *
-		 * remove:
-		 *   this bitmap node is removed, res is moved up in tree (could be none)
-		 *   this is a special case of shrink
-		 *
-		 * keep:
-		 *   the current path index is still used down in the tree, need to keep it
-		 *   copy as usual with the updated res
-		 *
-		 * shrink:
-		 *   the current path index is no longer used down in the tree, remove it (shrink)
-		 */
-		if (res == THE_NON_VALUE) {
-		    if (n == 1) {
-			break;
-		    } else if (n == 2) {
-			if (slot == 0) {
-			    ix = 2; /* off by one 'cause hdr */
-			} else {
-			    ix = 1; /* off by one 'cause hdr */
-			}
-			if (primary_tag(ptr[ix]) == TAG_PRIMARY_LIST) {
-			    res = ptr[ix];
-			} else {
-			    hval  = MAP_HEADER_VAL(hdr);
-			    *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp);
-			    *hp++ = ptr[ix];
-			    res = make_hashmap(nhp);
-			}
-		    } else {
-			/* n > 2 */
-			hval  = MAP_HEADER_VAL(hdr);
-			*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); ptr++;
-			n    -= slot;
-			while(slot--) { *hp++ = *ptr++; }
-			ptr++; n--;
-			while(n--) { *hp++ = *ptr++; }
-			res = make_hashmap(nhp);
-		    }
-		} else if (primary_tag(res) == TAG_PRIMARY_LIST && n == 1) {
-		    break;
-		} else {
-		    /* res is bitmap or leaf && n > 1, keep */
-		    n    -= slot;
-		    *hp++ = *ptr++;
-		    while(slot--) { *hp++ = *ptr++; }
-		    *hp++ = res;
-		    ptr++; n--;
-		    while(n--) { *hp++ = *ptr++; }
-		    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);
-		nhp  = hp;
-
-		if (res != THE_NON_VALUE) {
-		    *hp++ = *ptr++;
-		    *hp++ = (*ptr++) - 1;
-		    n    -= slot;
-		    while(slot--) { *hp++ = *ptr++; }
-		    *hp++ = res;
-		    ptr++; n--;
-		    while(n--) { *hp++ = *ptr++; }
-		} else {
-		    hval  = MAP_HEADER_VAL(hdr);
-		    *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval ^ bp); ptr++;
-		    *hp++ = (*ptr++) - 1;
-		    n    -= slot;
-		    while(slot--) { *hp++ = *ptr++; }
-		    ptr++; n--;
-		    while(n--) { *hp++ = *ptr++; }
-		}
-		res = make_hashmap(nhp);
-		break;
-	    default:
-		erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-		break;
-	}
-    } while(!ESTACK_ISEMPTY(stack));
-    HRelease(p, hp_end, hp);
-not_found:
-    DESTROY_ESTACK(stack);
-    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-    ERTS_HOLE_CHECK(p);
-    return res;
-}
-
 #define swizzle32(D,S) \
     do { \
 	(D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20  \
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 8c44f45125..672ac9f513 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -68,6 +68,7 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm
 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);
+static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node);
 
 /* erlang:map_size/1
  * the corresponding instruction is implemented in:
@@ -495,8 +496,7 @@ BIF_RETTYPE maps_put_3(BIF_ALIST_3) {
     BIF_ERROR(BIF_P, BADARG);
 }
 
-/* maps:remove/3
- */
+/* maps:remove/3 */
 
 int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) {
     Sint n;
@@ -579,6 +579,9 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) {
 	if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) {
 	    BIF_RET(res);
 	}
+    } else if (is_hashmap(BIF_ARG_2)) {
+	Uint32 hx = hashmap_make_hash(BIF_ARG_1);
+	BIF_RET(hashmap_delete(BIF_P, hx, BIF_ARG_1, BIF_ARG_2));
     }
     BIF_ERROR(BIF_P, BADARG);
 }
@@ -1245,6 +1248,256 @@ static Eterm hashmap_values(Process* p, Eterm node) {
     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];
+    Eterm *ptr;
+    Eterm hdr,res = node;
+    Uint32 ix, bp, hval;
+    Uint slot, lvl = 0;
+    Uint size = 0, n = 0;
+    DECLARE_ESTACK(stack);
+
+    for (;;) {
+	switch(primary_tag(node)) {
+	    case TAG_PRIMARY_LIST:
+		if (EQ(CAR(list_val(node)), key)) {
+		    goto unroll;
+		}
+		goto not_found;
+	    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 */
+			goto not_found;
+		    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 */
+			goto not_found;
+		    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;
+	}
+    }
+
+unroll:
+    /* the size is bounded and atleast one less than the previous size */
+    size  -= 1;
+    hp     = HAlloc(p, size);
+    hp_end = hp + size;
+    res    = THE_NON_VALUE;
+
+    do {
+	node = ESTACK_POP(stack);
+
+	/* all nodes are things */
+	ptr = boxed_val(node);
+	hdr = *ptr;
+	ASSERT(is_header(hdr));
+
+	switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
+	    case HAMT_SUBTAG_NODE_ARRAY:
+		ix  = (Uint) ESTACK_POP(stack);
+		nhp = hp;
+		if (res == THE_NON_VALUE) {
+		    *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(0xffff ^ (1 << ix)); ptr++;
+		    n     = 16;
+		    n    -= ix;
+		    while(ix--) { *hp++ = *ptr++; }
+		    ptr++; n--;
+		    while(n--) { *hp++ = *ptr++; }
+		    res = make_hashmap(nhp);
+		} else {
+		    n = HAMT_NODE_ARRAY_SZ;
+		    while(n--) { *hp++ = *ptr++; }
+		    nhp[ix+1] = res;
+		    res = make_hashmap(nhp);
+		}
+		break;
+	    case HAMT_SUBTAG_HEAD_ARRAY:
+		ix  = (Uint) ESTACK_POP(stack);
+		nhp = hp;
+		if (res == THE_NON_VALUE) {
+		    n     = 16;
+		    n    -= ix;
+		    *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(0xffff ^ (1 << ix)); ptr++;
+		    *hp++ = (*ptr++) - 1;
+		    while(ix--) { *hp++ = *ptr++; }
+		    ptr++; n--;
+		    while(n--) { *hp++ = *ptr++; }
+		    res = make_hashmap(nhp);
+		} else {
+		    n     = 16;
+		    *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
+		    *hp++ = (*ptr++) - 1;
+		    while(n--) { *hp++ = *ptr++; }
+		    nhp[ix+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);
+		nhp  = hp;
+
+		/* bitmap change matrix
+		 * res | none    leaf    bitmap
+		 * ----------------------------
+		 * n=1 | remove  remove  keep
+		 * n=2 | other   keep    keep
+		 * n>2 | shrink  keep    keep
+		 *
+		 * other: (remember, n is 2)
+		 *   shrink if the other bitmap value is a bitmap node
+		 *   remove if the other bitmap value is a leaf
+		 *
+		 * remove:
+		 *   this bitmap node is removed, res is moved up in tree (could be none)
+		 *   this is a special case of shrink
+		 *
+		 * keep:
+		 *   the current path index is still used down in the tree, need to keep it
+		 *   copy as usual with the updated res
+		 *
+		 * shrink:
+		 *   the current path index is no longer used down in the tree, remove it (shrink)
+		 */
+		if (res == THE_NON_VALUE) {
+		    if (n == 1) {
+			break;
+		    } else if (n == 2) {
+			if (slot == 0) {
+			    ix = 2; /* off by one 'cause hdr */
+			} else {
+			    ix = 1; /* off by one 'cause hdr */
+			}
+			if (primary_tag(ptr[ix]) == TAG_PRIMARY_LIST) {
+			    res = ptr[ix];
+			} else {
+			    hval  = MAP_HEADER_VAL(hdr);
+			    *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp);
+			    *hp++ = ptr[ix];
+			    res = make_hashmap(nhp);
+			}
+		    } else {
+			/* n > 2 */
+			hval  = MAP_HEADER_VAL(hdr);
+			*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); ptr++;
+			n    -= slot;
+			while(slot--) { *hp++ = *ptr++; }
+			ptr++; n--;
+			while(n--) { *hp++ = *ptr++; }
+			res = make_hashmap(nhp);
+		    }
+		} else if (primary_tag(res) == TAG_PRIMARY_LIST && n == 1) {
+		    break;
+		} else {
+		    /* res is bitmap or leaf && n > 1, keep */
+		    n    -= slot;
+		    *hp++ = *ptr++;
+		    while(slot--) { *hp++ = *ptr++; }
+		    *hp++ = res;
+		    ptr++; n--;
+		    while(n--) { *hp++ = *ptr++; }
+		    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);
+		nhp  = hp;
+
+		if (res != THE_NON_VALUE) {
+		    *hp++ = *ptr++;
+		    *hp++ = (*ptr++) - 1;
+		    n    -= slot;
+		    while(slot--) { *hp++ = *ptr++; }
+		    *hp++ = res;
+		    ptr++; n--;
+		    while(n--) { *hp++ = *ptr++; }
+		} else {
+		    hval  = MAP_HEADER_VAL(hdr);
+		    *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval ^ bp); ptr++;
+		    *hp++ = (*ptr++) - 1;
+		    n    -= slot;
+		    while(slot--) { *hp++ = *ptr++; }
+		    ptr++; n--;
+		    while(n--) { *hp++ = *ptr++; }
+		}
+		res = make_hashmap(nhp);
+		break;
+	    default:
+		erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
+		break;
+	}
+    } while(!ESTACK_ISEMPTY(stack));
+    HRelease(p, hp_end, hp);
+not_found:
+    DESTROY_ESTACK(stack);
+    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+    ERTS_HOLE_CHECK(p);
+    return res;
+}
+
+
 int erts_validate_and_sort_map(map_t* mp)
 {
     Eterm *ks  = map_get_keys(mp);