aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-03-24 15:27:11 +0100
committerSverker Eriksson <[email protected]>2015-03-24 20:04:16 +0100
commitdb54eaa94562b49c81b677948a8e9139ebdb010e (patch)
tree957ef209b525c522eee9e2116efd843d257aa204 /erts
parent1f23b603f022c7345dd573bf917926a575ae030d (diff)
downloadotp-db54eaa94562b49c81b677948a8e9139ebdb010e.tar.gz
otp-db54eaa94562b49c81b677948a8e9139ebdb010e.tar.bz2
otp-db54eaa94562b49c81b677948a8e9139ebdb010e.zip
erts: Remove HAMT_SUBTAG_NODE_ARRAY
This will also fix a bug in term_to_binary treating full nodes as tuples and emiting LIST_EXT for leafs.
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/erl_map.c88
-rw-r--r--erts/emulator/beam/erl_map.h6
-rw-r--r--erts/emulator/beam/external.c6
-rw-r--r--erts/emulator/beam/utils.c5
-rw-r--r--erts/emulator/test/map_SUITE.erl14
5 files changed, 29 insertions, 90 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 26233a98c6..ef806c2cfa 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -775,7 +775,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
sz = hashmap_bitcount(hdr);
hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
nhp = hp;
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+ *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
*hp++ = res; sz--;
while (sz--) { *hp++ = ESTACK_POP(stack); }
ASSERT((hp - nhp) < 18);
@@ -824,7 +824,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
sz = hashmap_bitcount(hdr);
hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
nhp = hp;
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+ *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
*hp++ = res; sz--;
while (sz--) { *hp++ = ESTACK_POP(stack); }
@@ -846,7 +846,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
*hp++ = n;
} else {
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+ *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
}
*hp++ = res; sz--;
@@ -1163,8 +1163,8 @@ recurse:
sp->abm = 1 << hashmap_index(ahx);
sp->srcA = &nodeA;
switch(hdrB & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++;
- case HAMT_SUBTAG_NODE_ARRAY:
+ case HAMT_SUBTAG_HEAD_ARRAY:
+ sp->srcB++;
sp->bbm = 0xffff;
break;
@@ -1189,16 +1189,16 @@ recurse:
hdrA = *sp->srcA++;
ASSERT(is_header(hdrA));
switch (hdrA & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcA++;
- case HAMT_SUBTAG_NODE_ARRAY: {
+ case HAMT_SUBTAG_HEAD_ARRAY: {
+ sp->srcA++;
ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED);
sp->abm = 0xffff;
sp->srcB = boxed_val(nodeB);
hdrB = *sp->srcB++;
ASSERT(is_header(hdrB));
switch (hdrB & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++;
- case HAMT_SUBTAG_NODE_ARRAY:
+ case HAMT_SUBTAG_HEAD_ARRAY:
+ sp->srcB++;
sp->bbm = 0xffff;
break;
case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
@@ -1218,8 +1218,8 @@ recurse:
hdrB = *sp->srcB++;
ASSERT(is_header(hdrB));
switch (hdrB & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++;
- case HAMT_SUBTAG_NODE_ARRAY:
+ case HAMT_SUBTAG_HEAD_ARRAY:
+ sp->srcB++;
sp->bbm = 0xffff;
break;
case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
@@ -1296,8 +1296,7 @@ recurse:
} else {
nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sp->ix), HALLOC_EXTRA);
hp = nhp;
- *hp++ = (sp->ix == 16 ? make_arityval(16)
- : MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm));
+ *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm);
}
memcpy(hp, sp->array, sp->ix * sizeof(Eterm));
res = make_boxed(nhp);
@@ -1748,7 +1747,6 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) {
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
case HAMT_SUBTAG_HEAD_ARRAY:
ptr++;
- case HAMT_SUBTAG_NODE_ARRAY:
sz = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
@@ -1799,7 +1797,6 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) {
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
case HAMT_SUBTAG_HEAD_ARRAY:
ptr++;
- case HAMT_SUBTAG_NODE_ARRAY:
sz = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
@@ -1862,11 +1859,6 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node)
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);
- node = ptr[ix+1];
- break;
case HAMT_SUBTAG_HEAD_ARRAY:
ix = hashmap_index(hx);
hx = hashmap_shift_hash(th,hx,lvl,key);
@@ -1964,13 +1956,6 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz,
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(*sp, ix, node);
- node = ptr[ix+1];
- break;
case HAMT_SUBTAG_HEAD_ARRAY:
ix = hashmap_index(hx);
hx = hashmap_shift_hash(th,hx,lvl,key);
@@ -2100,14 +2085,6 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
ASSERT(is_header(hdr));
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_NODE_ARRAY:
- slot = (Uint) ESTACK_POP(*sp);
- 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(*sp);
nhp = hp;
@@ -2132,9 +2109,6 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
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:
@@ -2230,13 +2204,6 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm map) {
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);
@@ -2351,24 +2318,6 @@ unroll:
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;
@@ -2610,7 +2559,6 @@ BIF_RETTYPE erts_internal_map_type_1(BIF_ALIST_1) {
case HAMT_SUBTAG_HEAD_ARRAY:
case HAMT_SUBTAG_HEAD_BITMAP:
BIF_RET(AM_hashmap);
- case HAMT_SUBTAG_NODE_ARRAY:
case HAMT_SUBTAG_NODE_BITMAP:
BIF_RET(AM_hashmap_node);
default:
@@ -2637,10 +2585,6 @@ BIF_RETTYPE erts_internal_map_hashmap_children_1(BIF_ALIST_1) {
ASSERT(is_header(hdr));
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_NODE_ARRAY:
- sz = 16;
- ptr += 1;
- break;
case HAMT_SUBTAG_NODE_BITMAP:
sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
ptr += 1;
@@ -2703,14 +2647,6 @@ static Eterm hashmap_info(Process *p, Eterm node) {
hdr = *ptr;
ASSERT(is_header(hdr));
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_NODE_ARRAY:
- narray++;
- sz = 16;
- while(sz--) {
- ESTACK_PUSH(stack, clvl + 1);
- ESTACK_PUSH(stack, ptr[sz+1]);
- }
- break;
case HAMT_SUBTAG_NODE_BITMAP:
nbitmap++;
sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index 1333a734a8..9fc1a72b68 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -178,21 +178,15 @@ typedef struct hashmap_head_s {
#define MAP_HEADER_HAMT_HEAD_BITMAP(Bmp) \
MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_BITMAP,0x1,Bmp)
-#define MAP_HEADER_HAMT_NODE_ARRAY \
- make_arityval(16)
-
#define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \
MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp)
#define HAMT_HEAD_EMPTY_SZ (2)
-#define HAMT_NODE_ARRAY_SZ (17)
#define HAMT_HEAD_ARRAY_SZ (18)
#define HAMT_NODE_BITMAP_SZ(n) (1 + n)
#define HAMT_HEAD_BITMAP_SZ(n) (2 + n)
#define _HEADER_MAP_SUBTAG_MASK (0xfc) /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */
-/* SUBTAG_NODE_ARRAY is in fact a tuple with 16 elements */
-#define HAMT_SUBTAG_NODE_ARRAY (((16 << _HEADER_ARITY_OFFS) | ARITYVAL_SUBTAG) & _HEADER_MAP_SUBTAG_MASK)
#define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG)
#define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG)
#define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG)
diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index c99b60ed09..b0b232f185 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -2633,8 +2633,6 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep,
*ep++ = MAP_EXT;
ptr++;
put_int32(*ptr, ep); ep += 4;
- /*fall through*/
- case HAMT_SUBTAG_NODE_ARRAY:
node_sz = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
@@ -4172,8 +4170,8 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj,
hdr = *ptr;
ASSERT(is_header(hdr));
switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: ptr++;
- case HAMT_SUBTAG_NODE_ARRAY:
+ case HAMT_SUBTAG_HEAD_ARRAY:
+ ptr++;
node_sz = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP: ptr++;
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 3549e18538..d98251addc 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -1321,7 +1321,6 @@ make_hash2(Eterm term)
}
switch (hdr & _HEADER_MAP_SUBTAG_MASK) {
case HAMT_SUBTAG_HEAD_ARRAY:
- case HAMT_SUBTAG_NODE_ARRAY:
i = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
@@ -1724,7 +1723,6 @@ make_internal_hash(Eterm term)
}
switch (hdr & _HEADER_MAP_SUBTAG_MASK) {
case HAMT_SUBTAG_HEAD_ARRAY:
- case HAMT_SUBTAG_NODE_ARRAY:
i = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
@@ -2797,14 +2795,13 @@ tailrecur_ne:
switch (hdr & _HEADER_MAP_SUBTAG_MASK) {
case HAMT_SUBTAG_HEAD_ARRAY:
aa++; bb++;
- case HAMT_SUBTAG_NODE_ARRAY:
sz = 16;
break;
case HAMT_SUBTAG_HEAD_BITMAP:
aa++; bb++;
case HAMT_SUBTAG_NODE_BITMAP:
sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
- ASSERT(sz > 0 && sz < 16);
+ ASSERT(sz > 0 && sz < 17);
break;
default:
erl_exit(1, "Unknown hashmap subsubtag\n");
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 1da08beb8b..fea327445f 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -1149,6 +1149,20 @@ t_map_encode_decode(Config) when is_list(Config) ->
97,55 % 55 :: integer()
>>),
+ %% Maps of different sizes
+ lists:foldl(fun(Key, M0) ->
+ M1 = M0#{Key => Key},
+ case Key rem 17 of
+ 0 ->
+ M1 = binary_to_term(term_to_binary(M1));
+ _ ->
+ ok
+ end,
+ M1
+ end,
+ #{},
+ lists:seq(1,10000)),
+
%% many maps in same binary
MapList = lists:foldl(fun(K, [M|_]=Acc) -> [M#{K => K} | Acc] end,
[#{}],