aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--erts/emulator/beam/bif.tab2
-rw-r--r--erts/emulator/beam/erl_hashmap.c257
-rw-r--r--erts/emulator/beam/erl_map.c247
3 files changed, 247 insertions, 259 deletions
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 5b0f90d418..55a7b62e7d 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -615,8 +615,6 @@ bif erlang:fun_info_mfa/1
bif erlang:get_keys/0
# Hash Array Mappped Trie
-bif hashmap:put/3
-bif hashmap:update/3
bif hashmap:remove/2
bif hashmap:info/1
bif hashmap:from_list/1
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];
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 304b5470f5..f99a1b431b 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -64,6 +64,7 @@
*/
static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node);
+static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update);
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);
@@ -594,6 +595,13 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
BIF_RETTYPE maps_put_3(BIF_ALIST_3) {
if (is_map(BIF_ARG_3)) {
BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3));
+ } else 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);
}
@@ -748,6 +756,13 @@ BIF_RETTYPE maps_update_3(BIF_ALIST_3) {
if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) {
BIF_RET(res);
}
+ } else 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);
}
@@ -920,6 +935,238 @@ static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) {
return NULL;
}
+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_keys(Process* p, Eterm node) {
DECLARE_WSTACK(stack);
hashmap_head_t* root;