aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/bif.tab1
-rw-r--r--erts/emulator/beam/erl_hashmap.c258
-rw-r--r--erts/emulator/beam/erl_map.c257
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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 12:53:44 +0000