aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_hashmap.c')
-rw-r--r--erts/emulator/beam/erl_hashmap.c258
1 files changed, 0 insertions, 258 deletions
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 \
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-01 06:15:36 +0000