From c157dce842bf78080c533472fcec74df01ed8fdb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Fri, 20 Mar 2015 18:01:50 +0100 Subject: erts: Combine flat and hash maps under one unifying tag --- erts/emulator/beam/beam_emu.c | 16 +-- erts/emulator/beam/copy.c | 57 ++++---- erts/emulator/beam/erl_db_util.c | 18 +-- erts/emulator/beam/erl_gc.h | 7 +- erts/emulator/beam/erl_map.c | 42 +++--- erts/emulator/beam/erl_map.h | 50 ++++--- erts/emulator/beam/erl_nif.c | 4 +- erts/emulator/beam/erl_printf_term.c | 139 ++++++++++--------- erts/emulator/beam/erl_term.c | 1 - erts/emulator/beam/erl_term.h | 99 +++++++------- erts/emulator/beam/external.c | 22 +-- erts/emulator/beam/io.c | 6 +- erts/emulator/beam/utils.c | 250 ++++++++++++++++++----------------- 13 files changed, 349 insertions(+), 362 deletions(-) diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c index 6526e87e4c..8fcdc72895 100644 --- a/erts/emulator/beam/beam_emu.c +++ b/erts/emulator/beam/beam_emu.c @@ -6602,8 +6602,8 @@ new_map(Process* p, Eterm* reg, BeamInstr* I) keys = make_tuple(thp); *thp++ = make_arityval(n/2); - mp = (flatmap_t *)mhp; mhp += MAP_HEADER_SIZE; - mp->thing_word = MAP_HEADER; + mp = (flatmap_t *)mhp; mhp += MAP_HEADER_FLATMAP_SZ; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = n/2; mp->keys = keys; @@ -6684,7 +6684,7 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) * update list are new). */ - need = 2*(num_old+num_updates) + 1 + MAP_HEADER_SIZE; + need = 2*(num_old+num_updates) + 1 + MAP_HEADER_FLATMAP_SZ; if (HeapWordsLeft(p) < need) { Uint live = Arg(3); reg[live] = map; @@ -6723,8 +6723,8 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) res = make_flatmap(hp); mp = (flatmap_t *)hp; - hp += MAP_HEADER_SIZE; - mp->thing_word = MAP_HEADER; + hp += MAP_HEADER_FLATMAP_SZ; + mp->thing_word = MAP_HEADER_FLATMAP; mp->keys = make_tuple(kp-1); old_vals = flatmap_get_values(old_mp); @@ -6906,7 +6906,7 @@ update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I) * Allocate the exact heap space needed. */ - need = num_old + MAP_HEADER_SIZE; + need = num_old + MAP_HEADER_FLATMAP_SZ; if (HeapWordsLeft(p) < need) { Uint live = Arg(3); reg[live] = map; @@ -6927,8 +6927,8 @@ update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I) res = make_flatmap(hp); mp = (flatmap_t *)hp; - hp += MAP_HEADER_SIZE; - mp->thing_word = MAP_HEADER; + hp += MAP_HEADER_FLATMAP_SZ; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = num_old; mp->keys = old_mp->keys; diff --git a/erts/emulator/beam/copy.c b/erts/emulator/beam/copy.c index 027b85b079..4d12dae787 100644 --- a/erts/emulator/beam/copy.c +++ b/erts/emulator/beam/copy.c @@ -127,8 +127,25 @@ Uint size_object(Eterm obj) obj = *bptr; break; } - case HASHMAP_SUBTAG: + case MAP_SUBTAG: switch (MAP_HEADER_TYPE(hdr)) { + case MAP_HEADER_TAG_FLATMAP_HEAD : + { + Uint n; + flatmap_t *mp; + mp = (flatmap_t*)flatmap_val_rel(obj,base); + ptr = (Eterm *)mp; + n = flatmap_get_size(mp) + 1; + sum += n + 2; + ptr += 2; /* hdr + size words */ + while (n--) { + obj = *ptr++; + if (!IS_CONST(obj)) { + ESTACK_PUSH(s, obj); + } + } + goto pop_next; + } case MAP_HEADER_TAG_HAMT_HEAD_BITMAP : case MAP_HEADER_TAG_HAMT_HEAD_ARRAY : case MAP_HEADER_TAG_HAMT_NODE_BITMAP : @@ -183,25 +200,7 @@ Uint size_object(Eterm obj) goto pop_next; } break; - case MAP_SUBTAG: - { - Uint n; - flatmap_t *mp; - mp = (flatmap_t*)flatmap_val_rel(obj,base); - ptr = (Eterm *)mp; - n = flatmap_get_size(mp) + 1; - sum += n + 2; - ptr += 2; /* hdr + size words */ - while (n--) { - obj = *ptr++; - if (!IS_CONST(obj)) { - ESTACK_PUSH(s, obj); - } - } - goto pop_next; - } - break; - case BIN_MATCHSTATE_SUBTAG: + case BIN_MATCHSTATE_SUBTAG: erl_exit(ERTS_ABORT_EXIT, "size_object: matchstate term not allowed"); default: @@ -369,15 +368,6 @@ Eterm copy_struct(Eterm obj, Uint sz, Eterm** hpp, ErlOffHeap* off_heap) } } break; - case MAP_SUBTAG: - { - i = flatmap_get_size(objp) + 3; - *argp = make_flatmap_rel(htop, dst_base); - while (i--) { - *htop++ = *objp++; - } - } - break; case REFC_BINARY_SUBTAG: { ProcBin* pb; @@ -502,9 +492,16 @@ Eterm copy_struct(Eterm obj, Uint sz, Eterm** hpp, ErlOffHeap* off_heap) *argp = make_external_rel(tp, dst_base); } break; - case HASHMAP_SUBTAG: + case MAP_SUBTAG: tp = htop; switch (MAP_HEADER_TYPE(hdr)) { + case MAP_HEADER_TAG_FLATMAP_HEAD : + i = flatmap_get_size(objp) + 3; + *argp = make_flatmap_rel(htop, dst_base); + while (i--) { + *htop++ = *objp++; + } + break; case MAP_HEADER_TAG_HAMT_HEAD_BITMAP : case MAP_HEADER_TAG_HAMT_HEAD_ARRAY : *htop++ = *objp++; diff --git a/erts/emulator/beam/erl_db_util.c b/erts/emulator/beam/erl_db_util.c index 9d699d4b22..0bf562d937 100644 --- a/erts/emulator/beam/erl_db_util.c +++ b/erts/emulator/beam/erl_db_util.c @@ -2153,16 +2153,16 @@ restart: break; case matchMkFlatMap: n = *pc++; - ehp = HAllocX(build_proc, 1 + MAP_HEADER_SIZE + n, HEAP_XTRA); + ehp = HAllocX(build_proc, 1 + MAP_HEADER_FLATMAP_SZ + n, HEAP_XTRA); t = *ehp++ = *--esp; { flatmap_t *m = (flatmap_t *)ehp; - m->thing_word = MAP_HEADER; + m->thing_word = MAP_HEADER_FLATMAP; m->size = n; m->keys = t; } t = make_flatmap(ehp); - ehp += MAP_HEADER_SIZE; + ehp += MAP_HEADER_FLATMAP_SZ; while (n--) { *ehp++ = *--esp; } @@ -3540,14 +3540,10 @@ static DMCRet dmc_one_term(DMCContext *context, DMC_PUSH(*stack, c); break; case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE): - n = flatmap_get_size(flatmap_val(c)); - DMC_PUSH(*text, matchPushM); - ++(context->stack_used); - DMC_PUSH(*text, n); - DMC_PUSH(*stack, c); - break; - case (_TAG_HEADER_HASHMAP >> _TAG_PRIMARY_SIZE): - n = hashmap_size(c); + if (is_flatmap(c)) + n = flatmap_get_size(flatmap_val(c)); + else + n = hashmap_size(c); DMC_PUSH(*text, matchPushM); ++(context->stack_used); DMC_PUSH(*text, n); diff --git a/erts/emulator/beam/erl_gc.h b/erts/emulator/beam/erl_gc.h index 8afcb060a1..bd6dcc9078 100644 --- a/erts/emulator/beam/erl_gc.h +++ b/erts/emulator/beam/erl_gc.h @@ -55,9 +55,10 @@ do { \ nelts = header_arity(HDR); \ switch ((HDR) & _HEADER_SUBTAG_MASK) { \ case SUB_BINARY_SUBTAG: nelts++; break; \ - case MAP_SUBTAG: nelts+=flatmap_get_size(PTR) + 1; break; \ - case HASHMAP_SUBTAG: nelts=hashmap_bitcount(MAP_HEADER_VAL(HDR)); \ - nelts += is_hashmap_header_head(HDR) ? 1 : 0; break; \ + case MAP_SUBTAG: \ + if (is_flatmap_header(HDR)) nelts+=flatmap_get_size(PTR) + 1; \ + else nelts += hashmap_bitcount(MAP_HEADER_VAL(HDR)); \ + break; \ case FUN_SUBTAG: nelts+=((ErlFunThing*)(PTR))->num_free+1; break; \ } \ gval = make_boxed(HTOP); \ diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 35446501d4..4af8e6f274 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -303,10 +303,10 @@ static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size) { hp += size; mp = (flatmap_t*)hp; res = make_flatmap(mp); - hp += MAP_HEADER_SIZE; + hp += MAP_HEADER_FLATMAP_SZ; vs = hp; - mp->thing_word = MAP_HEADER; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = size; /* set later, might shrink*/ mp->keys = keys; @@ -438,10 +438,10 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { ks = hp; hp += n; mp = (flatmap_t*)hp; - hp += MAP_HEADER_SIZE; + hp += MAP_HEADER_FLATMAP_SZ; vs = hp; - mp->thing_word = MAP_HEADER; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = n; mp->keys = keys; @@ -944,16 +944,16 @@ static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) { n1 = flatmap_get_size(mp1); n2 = flatmap_get_size(mp2); - need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2); + need = MAP_HEADER_FLATMAP_SZ + 1 + 2 * (n1 + n2); hp = HAlloc(p, need); thp = hp; tup = make_tuple(thp); ks = hp + 1; hp += 1 + n1 + n2; - mp_new = (flatmap_t*)hp; hp += MAP_HEADER_SIZE; + mp_new = (flatmap_t*)hp; hp += MAP_HEADER_FLATMAP_SZ; vs = hp; hp += n1 + n2; - mp_new->thing_word = MAP_HEADER; + mp_new->thing_word = MAP_HEADER_FLATMAP; mp_new->size = 0; mp_new->keys = tup; @@ -1344,12 +1344,12 @@ BIF_RETTYPE maps_new_0(BIF_ALIST_0) { Eterm tup; flatmap_t *mp; - hp = HAlloc(BIF_P, (MAP_HEADER_SIZE + 1)); + hp = HAlloc(BIF_P, (MAP_HEADER_FLATMAP_SZ + 1)); tup = make_tuple(hp); *hp++ = make_arityval(0); mp = (flatmap_t*)hp; - mp->thing_word = MAP_HEADER; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = 0; mp->keys = tup; @@ -1401,7 +1401,7 @@ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { *thp++ = make_arityval(n - 1); *res = make_flatmap(mhp); - *mhp++ = MAP_HEADER; + *mhp++ = MAP_HEADER_FLATMAP; *mhp++ = n - 1; *mhp++ = tup; @@ -1478,9 +1478,9 @@ int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) * assume key-tuple will be intact */ - hp = HAlloc(p, MAP_HEADER_SIZE + n); + hp = HAlloc(p, MAP_HEADER_FLATMAP_SZ + n); shp = hp; - *hp++ = MAP_HEADER; + *hp++ = MAP_HEADER_FLATMAP; *hp++ = n; *hp++ = mp->keys; @@ -1502,7 +1502,7 @@ int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) } } - HRelease(p, shp + MAP_HEADER_SIZE + n, shp); + HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp); return 0; found_key: @@ -1536,12 +1536,12 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { n = flatmap_get_size(mp); if (n == 0) { - hp = HAlloc(p, MAP_HEADER_SIZE + 1 + 2); + hp = HAlloc(p, MAP_HEADER_FLATMAP_SZ + 1 + 2); tup = make_tuple(hp); *hp++ = make_arityval(1); *hp++ = key; res = make_flatmap(hp); - *hp++ = MAP_HEADER; + *hp++ = MAP_HEADER_FLATMAP; *hp++ = 1; *hp++ = tup; *hp++ = value; @@ -1556,10 +1556,10 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { * assume key-tuple will be intact */ - hp = HAlloc(p, MAP_HEADER_SIZE + n); + hp = HAlloc(p, MAP_HEADER_FLATMAP_SZ + n); shp = hp; /* save hp, used if optimistic update fails */ res = make_flatmap(hp); - *hp++ = MAP_HEADER; + *hp++ = MAP_HEADER_FLATMAP; *hp++ = n; *hp++ = mp->keys; @@ -1591,7 +1591,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { /* the map will grow */ if (n >= MAP_SMALL_MAP_LIMIT) { - HRelease(p, shp + MAP_HEADER_SIZE + n, shp); + HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp); ks = flatmap_get_keys(mp); vs = flatmap_get_values(mp); @@ -1608,7 +1608,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { hp = HAlloc(p, 3 + n + 1); res = make_flatmap(hp); - *hp++ = MAP_HEADER; + *hp++ = MAP_HEADER_FLATMAP; *hp++ = n + 1; *hp++ = tup; @@ -2258,10 +2258,10 @@ unroll: ks = hp; hp += n; mp = (flatmap_t*)hp; - hp += MAP_HEADER_SIZE; + hp += MAP_HEADER_FLATMAP_SZ; vs = hp; - mp->thing_word = MAP_HEADER; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = n; mp->keys = keys; diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index 9fc1a72b68..2cc6768bfc 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -55,9 +55,9 @@ typedef struct flatmap_s { /* the head-node is a bitmap or array with an untagged size */ -#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) +#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) #define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE)) -#define hashmap_make_hash(Key) make_internal_hash(Key) +#define hashmap_make_hash(Key) make_internal_hash(Key) #define hashmap_restore_hash(Heap,Lvl,Key) \ (((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7))) @@ -66,27 +66,15 @@ typedef struct flatmap_s { /* erl_term.h stuff */ -#define make_flatmap(x) make_boxed((Eterm*)(x)) -#define make_flatmap_rel(x, BASE) make_boxed_rel((Eterm*)(x),(BASE)) -#define is_flatmap(x) (is_boxed((x)) && is_flatmap_header(*boxed_val((x)))) -#define is_flatmap_rel(RTERM,BASE) is_flatmap(rterm2wterm(RTERM,BASE)) -#define is_not_flatmap(x) (!is_flatmap((x))) -#define is_flatmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_MAP) -#define header_is_flatmap(x) ((((x) & (_HEADER_SUBTAG_MASK)) == MAP_SUBTAG)) -#define flatmap_val(x) (_unchecked_boxed_val((x))) -#define flatmap_val_rel(RTERM, BASE) flatmap_val(rterm2wterm(RTERM, BASE)) - -#define flatmap_get_values(x) (((Eterm *)(x)) + 3) -#define flatmap_get_keys(x) (((Eterm *)tuple_val(((flatmap_t *)(x))->keys)) + 1) -#define flatmap_get_size(x) (((flatmap_t*)(x))->size) +#define flatmap_get_values(x) (((Eterm *)(x)) + 3) +#define flatmap_get_keys(x) (((Eterm *)tuple_val(((flatmap_t *)(x))->keys)) + 1) +#define flatmap_get_size(x) (((flatmap_t*)(x))->size) #ifdef DEBUG #define MAP_SMALL_MAP_LIMIT (3) #else #define MAP_SMALL_MAP_LIMIT (32) #endif -#define MAP_HEADER _make_header(1,_TAG_HEADER_MAP) -#define MAP_HEADER_SIZE (sizeof(flatmap_t) / sizeof(Eterm)) struct ErtsWStack_; struct ErtsEStack_; @@ -170,7 +158,10 @@ typedef struct hashmap_head_s { #define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2))) #define MAKE_MAP_HEADER(Type,Arity,Val) \ - (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_HASHMAP)) + (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_MAP)) + +#define MAP_HEADER_FLATMAP \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_FLATMAP_HEAD,0x1,0x0) #define MAP_HEADER_HAMT_HEAD_ARRAY \ MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_ARRAY,0x1,0xffff) @@ -181,15 +172,22 @@ typedef struct hashmap_head_s { #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_HEAD_ARRAY_SZ (18) -#define HAMT_NODE_BITMAP_SZ(n) (1 + n) -#define HAMT_HEAD_BITMAP_SZ(n) (2 + n) +#define MAP_HEADER_FLATMAP_SZ (sizeof(flatmap_t) / sizeof(Eterm)) + +#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) + +/* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ +#define _HEADER_MAP_SUBTAG_MASK (0xfc) +/* 1 bit map tag + 1 ignore bit + 4 bits subtag + 2 ignore bits */ +#define _HEADER_MAP_HASHMAP_HEAD_MASK (0xbc) -#define _HEADER_MAP_SUBTAG_MASK (0xfc) /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ -#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) +#define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | MAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | MAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | MAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_FLATMAP ((MAP_HEADER_TAG_FLATMAP_HEAD << _HEADER_ARITY_OFFS) | MAP_SUBTAG) #define hashmap_index(hash) (((Uint32)hash) & 0xf) diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index c7c8b3fee3..660f446a52 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1926,14 +1926,14 @@ int enif_get_map_size(ErlNifEnv* env, ERL_NIF_TERM term, size_t *size) ERL_NIF_TERM enif_make_new_map(ErlNifEnv* env) { - Eterm* hp = alloc_heap(env,MAP_HEADER_SIZE+1); + Eterm* hp = alloc_heap(env,MAP_HEADER_FLATMAP_SZ+1); Eterm tup; flatmap_t *mp; tup = make_tuple(hp); *hp++ = make_arityval(0); mp = (flatmap_t*)hp; - mp->thing_word = MAP_HEADER; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = 0; mp->keys = tup; diff --git a/erts/emulator/beam/erl_printf_term.c b/erts/emulator/beam/erl_printf_term.c index ac5b139f8d..e0dfbd31b8 100644 --- a/erts/emulator/beam/erl_printf_term.c +++ b/erts/emulator/beam/erl_printf_term.c @@ -565,77 +565,74 @@ print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount, } break; case MAP_DEF: - { - Uint n; - Eterm *ks, *vs; - flatmap_t *mp = (flatmap_t *)flatmap_val(wobj); - n = flatmap_get_size(mp); - ks = flatmap_get_keys(mp); - vs = flatmap_get_values(mp); - - PRINT_CHAR(res, fn, arg, '#'); - PRINT_CHAR(res, fn, arg, '{'); - WSTACK_PUSH(s, PRT_CLOSE_TUPLE); - if (n > 0) { - n--; - WSTACK_PUSH5(s, vs[n], PRT_TERM, PRT_ASSOC, ks[n], PRT_TERM); - while (n--) { - WSTACK_PUSH6(s, PRT_COMMA, vs[n], PRT_TERM, PRT_ASSOC, - ks[n], PRT_TERM); - } - } - } - break; - case HASHMAP_DEF: - { - Uint n,mapval; - Eterm *head; - head = hashmap_val(wobj); - mapval = MAP_HEADER_VAL(*head); - switch (MAP_HEADER_TYPE(*head)) { - case MAP_HEADER_TAG_HAMT_HEAD_ARRAY: - case MAP_HEADER_TAG_HAMT_HEAD_BITMAP: - PRINT_STRING(res, fn, arg, "#<"); - PRINT_UWORD(res, fn, arg, 'x', 0, 1, mapval); - PRINT_STRING(res, fn, arg, ">{"); - WSTACK_PUSH(s,PRT_CLOSE_TUPLE); - n = hashmap_bitcount(mapval); - ASSERT(n < 17); - head += 2; - if (n > 0) { - n--; - WSTACK_PUSH(s, head[n]); - WSTACK_PUSH(s, PRT_TERM); - while (n--) { - WSTACK_PUSH(s, PRT_COMMA); - WSTACK_PUSH(s, head[n]); - WSTACK_PUSH(s, PRT_TERM); - } - } - break; - case MAP_HEADER_TAG_HAMT_NODE_BITMAP: - n = hashmap_bitcount(mapval); - head++; - PRINT_CHAR(res, fn, arg, '<'); - PRINT_UWORD(res, fn, arg, 'x', 0, 1, mapval); - PRINT_STRING(res, fn, arg, ">{"); - WSTACK_PUSH(s,PRT_CLOSE_TUPLE); - ASSERT(n < 17); - if (n > 0) { - n--; - WSTACK_PUSH(s, head[n]); - WSTACK_PUSH(s, PRT_TERM); - while (n--) { - WSTACK_PUSH(s, PRT_COMMA); - WSTACK_PUSH(s, head[n]); - WSTACK_PUSH(s, PRT_TERM); - } - } - break; - } - } - break; - default: + if (is_flatmap(wobj)) { + Uint n; + Eterm *ks, *vs; + flatmap_t *mp = (flatmap_t *)flatmap_val(wobj); + n = flatmap_get_size(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); + + PRINT_CHAR(res, fn, arg, '#'); + PRINT_CHAR(res, fn, arg, '{'); + WSTACK_PUSH(s, PRT_CLOSE_TUPLE); + if (n > 0) { + n--; + WSTACK_PUSH5(s, vs[n], PRT_TERM, PRT_ASSOC, ks[n], PRT_TERM); + while (n--) { + WSTACK_PUSH6(s, PRT_COMMA, vs[n], PRT_TERM, PRT_ASSOC, + ks[n], PRT_TERM); + } + } + } else { + Uint n, mapval; + Eterm *head; + head = hashmap_val(wobj); + mapval = MAP_HEADER_VAL(*head); + switch (MAP_HEADER_TYPE(*head)) { + case MAP_HEADER_TAG_HAMT_HEAD_ARRAY: + case MAP_HEADER_TAG_HAMT_HEAD_BITMAP: + PRINT_STRING(res, fn, arg, "#<"); + PRINT_UWORD(res, fn, arg, 'x', 0, 1, mapval); + PRINT_STRING(res, fn, arg, ">{"); + WSTACK_PUSH(s,PRT_CLOSE_TUPLE); + n = hashmap_bitcount(mapval); + ASSERT(n < 17); + head += 2; + if (n > 0) { + n--; + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + while (n--) { + WSTACK_PUSH(s, PRT_COMMA); + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + } + } + break; + case MAP_HEADER_TAG_HAMT_NODE_BITMAP: + n = hashmap_bitcount(mapval); + head++; + PRINT_CHAR(res, fn, arg, '<'); + PRINT_UWORD(res, fn, arg, 'x', 0, 1, mapval); + PRINT_STRING(res, fn, arg, ">{"); + WSTACK_PUSH(s,PRT_CLOSE_TUPLE); + ASSERT(n < 17); + if (n > 0) { + n--; + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + while (n--) { + WSTACK_PUSH(s, PRT_COMMA); + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + } + } + break; + } + } + break; + default: PRINT_STRING(res, fn, arg, "'); diff --git a/erts/emulator/beam/erl_term.c b/erts/emulator/beam/erl_term.c index d6fb88ea61..bc04d7b78e 100644 --- a/erts/emulator/beam/erl_term.c +++ b/erts/emulator/beam/erl_term.c @@ -90,7 +90,6 @@ unsigned tag_val_def(Wterm x) case (_TAG_HEADER_REFC_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; case (_TAG_HEADER_HEAP_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; case (_TAG_HEADER_SUB_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; - case (_TAG_HEADER_HASHMAP >> _TAG_PRIMARY_SIZE): return HASHMAP_DEF; } break; diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h index 1625a4ec15..095aa54ddd 100644 --- a/erts/emulator/beam/erl_term.h +++ b/erts/emulator/beam/erl_term.h @@ -141,29 +141,27 @@ struct erl_node_; /* Declared in erl_node_tables.h */ #define HEAP_BINARY_SUBTAG (0x9 << _TAG_PRIMARY_SIZE) /* BINARY */ #define SUB_BINARY_SUBTAG (0xA << _TAG_PRIMARY_SIZE) /* BINARY */ /* _BINARY_XXX_MASK depends on 0xB being unused */ -#define HASHMAP_SUBTAG (0xB << _TAG_PRIMARY_SIZE) /* HASHMAP */ #define EXTERNAL_PID_SUBTAG (0xC << _TAG_PRIMARY_SIZE) /* EXTERNAL_PID */ #define EXTERNAL_PORT_SUBTAG (0xD << _TAG_PRIMARY_SIZE) /* EXTERNAL_PORT */ #define EXTERNAL_REF_SUBTAG (0xE << _TAG_PRIMARY_SIZE) /* EXTERNAL_REF */ #define MAP_SUBTAG (0xF << _TAG_PRIMARY_SIZE) /* MAP */ -#define _TAG_HEADER_ARITYVAL (TAG_PRIMARY_HEADER|ARITYVAL_SUBTAG) -#define _TAG_HEADER_FUN (TAG_PRIMARY_HEADER|FUN_SUBTAG) -#define _TAG_HEADER_POS_BIG (TAG_PRIMARY_HEADER|POS_BIG_SUBTAG) -#define _TAG_HEADER_NEG_BIG (TAG_PRIMARY_HEADER|NEG_BIG_SUBTAG) -#define _TAG_HEADER_FLOAT (TAG_PRIMARY_HEADER|FLOAT_SUBTAG) -#define _TAG_HEADER_EXPORT (TAG_PRIMARY_HEADER|EXPORT_SUBTAG) -#define _TAG_HEADER_REF (TAG_PRIMARY_HEADER|REF_SUBTAG) -#define _TAG_HEADER_REFC_BIN (TAG_PRIMARY_HEADER|REFC_BINARY_SUBTAG) -#define _TAG_HEADER_HEAP_BIN (TAG_PRIMARY_HEADER|HEAP_BINARY_SUBTAG) -#define _TAG_HEADER_SUB_BIN (TAG_PRIMARY_HEADER|SUB_BINARY_SUBTAG) -#define _TAG_HEADER_EXTERNAL_PID (TAG_PRIMARY_HEADER|EXTERNAL_PID_SUBTAG) -#define _TAG_HEADER_EXTERNAL_PORT (TAG_PRIMARY_HEADER|EXTERNAL_PORT_SUBTAG) -#define _TAG_HEADER_EXTERNAL_REF (TAG_PRIMARY_HEADER|EXTERNAL_REF_SUBTAG) +#define _TAG_HEADER_ARITYVAL (TAG_PRIMARY_HEADER|ARITYVAL_SUBTAG) +#define _TAG_HEADER_FUN (TAG_PRIMARY_HEADER|FUN_SUBTAG) +#define _TAG_HEADER_POS_BIG (TAG_PRIMARY_HEADER|POS_BIG_SUBTAG) +#define _TAG_HEADER_NEG_BIG (TAG_PRIMARY_HEADER|NEG_BIG_SUBTAG) +#define _TAG_HEADER_FLOAT (TAG_PRIMARY_HEADER|FLOAT_SUBTAG) +#define _TAG_HEADER_EXPORT (TAG_PRIMARY_HEADER|EXPORT_SUBTAG) +#define _TAG_HEADER_REF (TAG_PRIMARY_HEADER|REF_SUBTAG) +#define _TAG_HEADER_REFC_BIN (TAG_PRIMARY_HEADER|REFC_BINARY_SUBTAG) +#define _TAG_HEADER_HEAP_BIN (TAG_PRIMARY_HEADER|HEAP_BINARY_SUBTAG) +#define _TAG_HEADER_SUB_BIN (TAG_PRIMARY_HEADER|SUB_BINARY_SUBTAG) +#define _TAG_HEADER_EXTERNAL_PID (TAG_PRIMARY_HEADER|EXTERNAL_PID_SUBTAG) +#define _TAG_HEADER_EXTERNAL_PORT (TAG_PRIMARY_HEADER|EXTERNAL_PORT_SUBTAG) +#define _TAG_HEADER_EXTERNAL_REF (TAG_PRIMARY_HEADER|EXTERNAL_REF_SUBTAG) #define _TAG_HEADER_BIN_MATCHSTATE (TAG_PRIMARY_HEADER|BIN_MATCHSTATE_SUBTAG) -#define _TAG_HEADER_MAP (TAG_PRIMARY_HEADER|MAP_SUBTAG) -#define _TAG_HEADER_HASHMAP (TAG_PRIMARY_HEADER|HASHMAP_SUBTAG) +#define _TAG_HEADER_MAP (TAG_PRIMARY_HEADER|MAP_SUBTAG) #define _TAG_HEADER_MASK 0x3F @@ -302,7 +300,7 @@ _ET_DECLARE_CHECKED(Uint,atom_val,Eterm) #define is_header(x) (((x) & _TAG_PRIMARY_MASK) == TAG_PRIMARY_HEADER) //#define _unchecked_header_arity(x) ((x) >> _HEADER_ARITY_OFFS) #define _unchecked_header_arity(x) \ - (is_hashmap_header(x) ? MAP_HEADER_ARITY(x) : ((x) >> _HEADER_ARITY_OFFS)) + (is_map_header(x) ? MAP_HEADER_ARITY(x) : ((x) >> _HEADER_ARITY_OFFS)) _ET_DECLARE_CHECKED(Uint,header_arity,Eterm) #define header_arity(x) _ET_APPLY(header_arity,(x)) @@ -1001,7 +999,7 @@ _ET_DECLARE_CHECKED(struct erl_node_*,external_ref_node,Eterm) #define MAP_HEADER_ARITY_SZ (8) #define MAP_HEADER_VAL_SZ (16) -#define MAP_HEADER_TAG_FLAT (0x0) +#define MAP_HEADER_TAG_FLATMAP_HEAD (0x0) #define MAP_HEADER_TAG_HAMT_NODE_BITMAP (0x1) #define MAP_HEADER_TAG_HAMT_HEAD_ARRAY (0x2) #define MAP_HEADER_TAG_HAMT_HEAD_BITMAP (0x3) @@ -1010,17 +1008,27 @@ _ET_DECLARE_CHECKED(struct erl_node_*,external_ref_node,Eterm) #define MAP_HEADER_ARITY(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ)) & (0xff)) #define MAP_HEADER_VAL(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ + MAP_HEADER_ARITY_SZ)) & (0xffff)) -#define make_hashmap(x) make_boxed((Eterm*)(x)) -#define make_hashmap_rel make_boxed_rel -#define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x)))) -#define is_not_hashmap(x) (!is_hashmap(x)) -#define is_hashmap_rel(RTERM,BASE) is_hashmap(rterm2wterm(RTERM,BASE)) -#define is_hashmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HASHMAP) -#define hashmap_val(x) _unchecked_boxed_val((x)) -#define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE)) - -#define is_map(x) (is_flatmap(x) || is_hashmap(x)) -#define is_map_rel(x,BASE) (is_flatmap_rel(x,BASE) || is_hashmap_rel(x,BASE)) +#define make_hashmap(x) make_boxed((Eterm*)(x)) +#define make_hashmap_rel make_boxed_rel +#define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x)))) +#define is_not_hashmap(x) (!is_hashmap(x)) +#define is_hashmap_rel(RTERM,BASE) is_hashmap(rterm2wterm(RTERM,BASE)) +#define is_hashmap_header(x) (((x) & (_HEADER_MAP_HASHMAP_HEAD_MASK)) == HAMT_SUBTAG_HEAD_ARRAY) +#define hashmap_val(x) _unchecked_boxed_val((x)) +#define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE)) + +#define make_flatmap(x) make_boxed((Eterm*)(x)) +#define make_flatmap_rel(x, BASE) make_boxed_rel((Eterm*)(x),(BASE)) +#define is_flatmap(x) (is_boxed((x)) && is_flatmap_header(*boxed_val((x)))) +#define is_flatmap_rel(RTERM,BASE) is_flatmap(rterm2wterm(RTERM,BASE)) +#define is_not_flatmap(x) (!is_flatmap((x))) +#define is_flatmap_header(x) (((x) & (_HEADER_MAP_SUBTAG_MASK)) == HAMT_SUBTAG_HEAD_FLATMAP) +#define flatmap_val(x) (_unchecked_boxed_val((x))) +#define flatmap_val_rel(RTERM, BASE) flatmap_val(rterm2wterm(RTERM, BASE)) + +#define is_map_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_MAP) +#define is_map(x) (is_boxed((x)) && is_map_header(*boxed_val(x))) +#define is_map_rel(RTERM,BASE) is_map(rterm2wterm(RTERM,BASE)) /* number tests */ @@ -1113,23 +1121,22 @@ _ET_DECLARE_CHECKED(Uint,y_reg_index,Uint) #define BINARY_DEF 0x0 #define LIST_DEF 0x1 #define NIL_DEF 0x2 -#define HASHMAP_DEF 0x3 -#define MAP_DEF 0x4 -#define TUPLE_DEF 0x5 -#define PID_DEF 0x6 -#define EXTERNAL_PID_DEF 0x7 -#define PORT_DEF 0x8 -#define EXTERNAL_PORT_DEF 0x9 -#define EXPORT_DEF 0xa -#define FUN_DEF 0xb -#define REF_DEF 0xc -#define EXTERNAL_REF_DEF 0xd -#define ATOM_DEF 0xe -#define FLOAT_DEF 0xf -#define BIG_DEF 0x10 -#define SMALL_DEF 0x11 - -#define FIRST_VACANT_TAG_DEF 0x12 +#define MAP_DEF 0x3 +#define TUPLE_DEF 0x4 +#define PID_DEF 0x5 +#define EXTERNAL_PID_DEF 0x6 +#define PORT_DEF 0x7 +#define EXTERNAL_PORT_DEF 0x8 +#define EXPORT_DEF 0x9 +#define FUN_DEF 0xa +#define REF_DEF 0xb +#define EXTERNAL_REF_DEF 0xc +#define ATOM_DEF 0xd +#define FLOAT_DEF 0xe +#define BIG_DEF 0xf +#define SMALL_DEF 0x10 + +#define FIRST_VACANT_TAG_DEF 0x11 #if ET_DEBUG extern unsigned tag_val_def_debug(Wterm, const char*, unsigned); diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index b0b232f185..2a9189b51e 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -2604,7 +2604,7 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, break; case MAP_DEF: - { + if (is_flatmap(obj)) { flatmap_t *mp = (flatmap_t*)flatmap_val(obj); Uint size = flatmap_get_size(mp); @@ -2618,11 +2618,7 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, WSTACK_PUSH4(s, (UWord)kptr, (UWord)vptr, ENC_MAP_PAIR, size); } - } - break; - - case HASHMAP_DEF: - { + } else { Eterm hdr; Uint node_sz; ptr = boxed_val(obj); @@ -2656,7 +2652,6 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, } } break; - case FLOAT_DEF: GET_DOUBLE(obj, f); if (dflags & DFLAG_NEW_FLOATS) { @@ -3607,7 +3602,7 @@ dec_term_atom_common: kptr = hp - 1; mp = (flatmap_t*)hp; - hp += MAP_HEADER_SIZE; + hp += MAP_HEADER_FLATMAP_SZ; hp += size; vptr = hp - 1; @@ -3893,7 +3888,7 @@ dec_term_atom_common: while (maps_list) { next = (Eterm *)(EXPAND_POINTER(*maps_list)); - *maps_list = MAP_HEADER; + *maps_list = MAP_HEADER_FLATMAP; if (!erts_validate_and_sort_flatmap((flatmap_t*)maps_list)) goto error; maps_list = next; @@ -4121,7 +4116,7 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, } break; case MAP_DEF: - { + if (is_flatmap(obj)) { flatmap_t *mp = (flatmap_t*)flatmap_val(obj); Uint size = flatmap_get_size(mp); Uint i; @@ -4158,11 +4153,7 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, ++ptr; } goto outer_loop; - } - break; - - case HASHMAP_DEF: - { + } else { Eterm *ptr; Eterm hdr; Uint node_sz; @@ -4190,7 +4181,6 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, } result += 1 + 4; /* tag + 4 bytes size */ } - break; case FLOAT_DEF: if (dflags & DFLAG_NEW_FLOATS) { diff --git a/erts/emulator/beam/io.c b/erts/emulator/beam/io.c index 46f0eba5e0..1db3a9fba7 100644 --- a/erts/emulator/beam/io.c +++ b/erts/emulator/beam/io.c @@ -5354,7 +5354,7 @@ driver_deliver_term(Eterm to, ErlDrvTermData* data, int len) if (ptr[0] > MAP_SMALL_MAP_LIMIT) { need += hashmap_over_estimated_heap_size(ptr[0]); } else { - need += MAP_HEADER_SIZE + 1 + 2*ptr[0]; + need += MAP_HEADER_FLATMAP_SZ + 1 + 2*ptr[0]; } depth -= 2*ptr[0]; if (depth < 0) ERTS_DDT_FAIL; @@ -5627,12 +5627,12 @@ driver_deliver_term(Eterm to, ErlDrvTermData* data, int len) hp += 1 + size; mp = (flatmap_t*)hp; - mp->thing_word = MAP_HEADER; + mp->thing_word = MAP_HEADER_FLATMAP; mp->size = size; mp->keys = make_tuple(tp); mess = make_flatmap(mp); - hp += MAP_HEADER_SIZE + size; /* advance "heap" pointer */ + hp += MAP_HEADER_FLATMAP_SZ + size; tp += size; /* point at last key */ vp = hp - 1; /* point at last value */ diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 6edb466a36..cb4ef2b376 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1025,11 +1025,8 @@ tail_recur: break; } case MAP_DEF: - case HASHMAP_DEF: - { - hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term); - break; - } + hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term); + break; case TUPLE_DEF: { Eterm* ptr = tuple_val(term); @@ -1273,41 +1270,40 @@ make_hash2(Eterm term) } } break; - case MAP_SUBTAG: - { - flatmap_t *mp = (flatmap_t *)flatmap_val(term); - int i; - int size = flatmap_get_size(mp); - Eterm *ks = flatmap_get_keys(mp); - Eterm *vs = flatmap_get_values(mp); - UINT32_HASH(size, HCONST_16); - if (size == 0) { - goto hash2_common; - } - /* We want a portable hash function that is *independent* of - * the order in which keys and values are encountered. - * We therefore calculate context independent hashes for all . - * key-value pairs and then xor them together. - */ - ESTACK_PUSH(s, hash_xor_pairs); - ESTACK_PUSH(s, hash); - ESTACK_PUSH(s, HASH_MAP_TAIL); - hash = 0; - hash_xor_pairs = 0; - for (i = size - 1; i >= 0; i--) { - ESTACK_PUSH(s, HASH_MAP_PAIR); - ESTACK_PUSH(s, vs[i]); - ESTACK_PUSH(s, ks[i]); - } - goto hash2_common; - } - break; - case HASHMAP_SUBTAG: + case MAP_SUBTAG: { Eterm* ptr = boxed_val(term) + 1; Uint size; int i; switch (hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_FLATMAP: + { + flatmap_t *mp = (flatmap_t *)flatmap_val(term); + Eterm *ks = flatmap_get_keys(mp); + Eterm *vs = flatmap_get_values(mp); + size = flatmap_get_size(mp); + UINT32_HASH(size, HCONST_16); + if (size == 0) + goto hash2_common; + + /* We want a portable hash function that is *independent* of + * the order in which keys and values are encountered. + * We therefore calculate context independent hashes for all . + * key-value pairs and then xor them together. + */ + ESTACK_PUSH(s, hash_xor_pairs); + ESTACK_PUSH(s, hash); + ESTACK_PUSH(s, HASH_MAP_TAIL); + hash = 0; + hash_xor_pairs = 0; + for (i = size - 1; i >= 0; i--) { + ESTACK_PUSH(s, HASH_MAP_PAIR); + ESTACK_PUSH(s, vs[i]); + ESTACK_PUSH(s, ks[i]); + } + goto hash2_common; + } + case HAMT_SUBTAG_HEAD_ARRAY: case HAMT_SUBTAG_HEAD_BITMAP: size = *ptr++; @@ -1675,42 +1671,40 @@ make_internal_hash(Eterm term) } } break; - case MAP_SUBTAG: - { - flatmap_t *mp = (flatmap_t *)flatmap_val(term); - int i; - int size = flatmap_get_size(mp); - Eterm *ks = flatmap_get_keys(mp); - Eterm *vs = flatmap_get_values(mp); - UINT32_HASH(size, HCONST_16); - if (size == 0) { - goto pop_next; - } - /* We want a hash function that is *independent* of - * the order in which keys and values are encountered. - * We therefore calculate context independent hashes for all . - * key-value pairs and then xor them together. - */ - ESTACK_PUSH(s, hash_xor_pairs); - ESTACK_PUSH(s, hash); - ESTACK_PUSH(s, HASH_MAP_TAIL); - hash = 0; - hash_xor_pairs = 0; - for (i = size - 1; i >= 0; i--) { - ESTACK_PUSH(s, HASH_MAP_PAIR); - ESTACK_PUSH(s, vs[i]); - ESTACK_PUSH(s, ks[i]); - } - goto pop_next; - } - break; - case HASHMAP_SUBTAG: + + case MAP_SUBTAG: { Eterm* ptr = boxed_val(term) + 1; Uint size; int i; switch (hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: + case HAMT_SUBTAG_HEAD_FLATMAP: + { + flatmap_t *mp = (flatmap_t *)flatmap_val(term); + Eterm *ks = flatmap_get_keys(mp); + Eterm *vs = flatmap_get_values(mp); + size = flatmap_get_size(mp); + UINT32_HASH(size, HCONST_16); + if (size == 0) + goto pop_next; + + /* We want a hash function that is *independent* of + * the order in which keys and values are encountered. + * We therefore calculate context independent hashes for all . + * key-value pairs and then xor them together. + */ + ESTACK_PUSH(s, hash_xor_pairs); + ESTACK_PUSH(s, hash); + ESTACK_PUSH(s, HASH_MAP_TAIL); + hash = 0; + hash_xor_pairs = 0; + for (i = size - 1; i >= 0; i--) { + ESTACK_PUSH(s, HASH_MAP_PAIR); + ESTACK_PUSH(s, vs[i]); + ESTACK_PUSH(s, ks[i]); + } + goto pop_next; + } case HAMT_SUBTAG_HEAD_BITMAP: size = *ptr++; UINT32_HASH(size, HCONST_16); @@ -2170,11 +2164,8 @@ tail_recur: break; case MAP_DEF: - case HASHMAP_DEF: - { - hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term); - break; - } + hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term); + break; case TUPLE_DEF: { Eterm* ptr = tuple_val(term); @@ -2579,22 +2570,6 @@ tailrecur_ne: ++bb; goto term_array; } - case MAP_SUBTAG: - { - aa = flatmap_val_rel(a, a_base); - if (!is_boxed(b) || *boxed_val_rel(b,b_base) != *aa) - goto not_equal; - bb = flatmap_val_rel(b,b_base); - sz = flatmap_get_size((flatmap_t*)aa); - - if (sz != flatmap_get_size((flatmap_t*)bb)) goto not_equal; - if (sz == 0) goto pop_next; - - aa += 2; - bb += 2; - sz += 1; /* increment for tuple-keys */ - goto term_array; - } case REFC_BINARY_SUBTAG: case HEAP_BINARY_SUBTAG: case SUB_BINARY_SUBTAG: @@ -2786,8 +2761,23 @@ tailrecur_ne: } break; /* not equal */ } - case HASHMAP_SUBTAG: - { + case MAP_SUBTAG: + if (is_flatmap_rel(a, a_base)) { + aa = flatmap_val_rel(a, a_base); + if (!is_boxed(b) || *boxed_val_rel(b,b_base) != *aa) + goto not_equal; + bb = flatmap_val_rel(b,b_base); + sz = flatmap_get_size((flatmap_t*)aa); + + if (sz != flatmap_get_size((flatmap_t*)bb)) goto not_equal; + if (sz == 0) goto pop_next; + + aa += 2; + bb += 2; + sz += 1; /* increment for tuple-keys */ + goto term_array; + + } else { if (!is_boxed(b) || *boxed_val_rel(b,b_base) != hdr) goto not_equal; @@ -3124,44 +3114,56 @@ tailrecur_ne: ++aa; ++bb; goto term_array; - case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE) : - if (!is_flatmap_rel(b,b_base)) { - a_tag = MAP_DEF; - goto mixed_types; - } - aa = (Eterm *)flatmap_val_rel(a,a_base); - bb = (Eterm *)flatmap_val_rel(b,b_base); - - i = flatmap_get_size((flatmap_t*)aa); - if (i != flatmap_get_size((flatmap_t*)bb)) { - RETURN_NEQ((int)(i - flatmap_get_size((flatmap_t*)bb))); - } - if (i == 0) { - goto pop_next; - } - aa += 2; - bb += 2; - if (exact) { - i += 1; /* increment for tuple-keys */ - goto term_array; - } - else { - /* Value array */ - WSTACK_PUSH3(stack, (UWord)(bb+1), (UWord)(aa+1), TERM_ARRAY_OP_WORD(i)); - /* Switch back from 'exact' key compare */ - WSTACK_PUSH(stack, OP_WORD(SWITCH_EXACT_OFF_OP)); - /* Now do 'exact' compare of key tuples */ - a = *aa; - b = *bb; - exact = 1; - goto bodyrecur; - } - - case (_TAG_HEADER_HASHMAP >> _TAG_PRIMARY_SIZE) : + case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE) : { struct erts_cmp_hashmap_state* sp; + if (is_flatmap_header(ahdr)) { + if (!is_flatmap_rel(b,b_base)) { + if (is_hashmap_rel(b,b_base)) { + aa = (Eterm *)flatmap_val_rel(a,a_base); + i = flatmap_get_size((flatmap_t*)aa) - hashmap_size_rel(b,b_base); + ASSERT(i != 0); + RETURN_NEQ(i); + } + a_tag = MAP_DEF; + goto mixed_types; + } + aa = (Eterm *)flatmap_val_rel(a,a_base); + bb = (Eterm *)flatmap_val_rel(b,b_base); + + i = flatmap_get_size((flatmap_t*)aa); + if (i != flatmap_get_size((flatmap_t*)bb)) { + RETURN_NEQ((int)(i - flatmap_get_size((flatmap_t*)bb))); + } + if (i == 0) { + goto pop_next; + } + aa += 2; + bb += 2; + if (exact) { + i += 1; /* increment for tuple-keys */ + goto term_array; + } + else { + /* Value array */ + WSTACK_PUSH3(stack,(UWord)(bb+1),(UWord)(aa+1),TERM_ARRAY_OP_WORD(i)); + /* Switch back from 'exact' key compare */ + WSTACK_PUSH(stack,OP_WORD(SWITCH_EXACT_OFF_OP)); + /* Now do 'exact' compare of key tuples */ + a = *aa; + b = *bb; + exact = 1; + goto bodyrecur; + } + } if (!is_hashmap_rel(b,b_base)) { - a_tag = HASHMAP_DEF; + if (is_flatmap_rel(b,b_base)) { + bb = (Eterm *)flatmap_val_rel(b,b_base); + i = hashmap_size_rel(a,a_base) - flatmap_get_size((flatmap_t*)bb); + ASSERT(i != 0); + RETURN_NEQ(i); + } + a_tag = MAP_DEF; goto mixed_types; } i = hashmap_size_rel(a,a_base) - hashmap_size_rel(b,b_base); -- cgit v1.2.3