aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/bif.tab1
-rw-r--r--erts/emulator/beam/erl_hashmap.c266
2 files changed, 264 insertions, 3 deletions
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 17e61f4664..cf606a9deb 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -617,6 +617,7 @@ bif erlang:get_keys/0
# Hash Array Mappped Trie
bif hashmap:put/3
bif hashmap:get/2
+bif hashmap:remove/2
bif hashmap:info/1
bif hashmap:to_list/1
bif hashmap:new/0
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 5f913edfa6..31d54569e0 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -48,6 +48,7 @@
#define DECL_AM(S) Eterm AM_ ## S = am_atom_put(#S, sizeof(#S) - 1)
#endif
+#if 0
static char *format_binary(Uint64 x, char *b) {
int z;
b[64] = '\0';
@@ -56,11 +57,13 @@ static char *format_binary(Uint64 x, char *b) {
}
return b;
}
+#endif
static Uint32 hashmap_shift_hash(Uint32 hx, Uint *lvl, Eterm key);
static Uint32 hashmap_restore_hash(Uint lvl, Eterm key);
static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node);
static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node);
+static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node);
static Eterm hashmap_to_list(Process *p, Eterm map);
static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
@@ -109,7 +112,7 @@ BIF_RETTYPE hashmap_get_2(BIF_ALIST_2) {
if (is_hashmap(BIF_ARG_2)) {
const Eterm *value;
Uint32 hx = make_hash2(BIF_ARG_1);
-
+
if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) {
BIF_RET(*value);
}
@@ -117,6 +120,16 @@ BIF_RETTYPE hashmap_get_2(BIF_ALIST_2) {
BIF_ERROR(BIF_P, BADARG);
}
+/* hashmap:remove/2 */
+
+BIF_RETTYPE hashmap_remove_2(BIF_ALIST_2) {
+ if (is_hashmap(BIF_ARG_2)) {
+ Uint32 hx = make_hash2(BIF_ARG_1);
+
+ BIF_RET(hashmap_delete(BIF_P, hx, BIF_ARG_1, BIF_ARG_2));
+ }
+ BIF_ERROR(BIF_P, BADARG);
+}
/* hashmap:size/1 */
BIF_RETTYPE hashmap_size_1(BIF_ALIST_1) {
@@ -432,6 +445,254 @@ unroll:
return res;
}
+static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) {
+ Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL;
+ 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(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(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(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(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;
+}
+
static Eterm hashmap_to_list(Process *p, Eterm node) {
Eterm *hp;
Eterm res = NIL;
@@ -510,7 +771,7 @@ static Uint32 hashmap_shift_hash(Uint32 hx, Uint *lvl, Eterm key) {
/* hashmap:info/0 */
static Eterm hashmap_info(Process *p, Eterm node) {
- Eterm *hp, **hpp;
+ Eterm *hp;
Eterm res = NIL, info = NIL;
Eterm *ptr, tup, hdr;
Uint sz;
@@ -620,7 +881,6 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
Eterm *ts = (Eterm *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(Eterm));
Uint i;
-
for (i = 0; i < n; i++) {
ts[i] = erts_bld_uint(hpp, szp, nums[i]);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 11:55:48 +0000