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.c257
1 files changed, 0 insertions, 257 deletions
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];
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-10 13:21:16 +0000