From 9cfaa729d7319ede30f62ffaaf82eb10fbaf8a60 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Thu, 19 Feb 2015 16:25:03 +0100 Subject: erts: Move hashmap:size/1 to maps --- erts/emulator/beam/erl_map.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index b2a16eb5ed..ecbb91bc33 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -77,6 +77,16 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) { erts_bld_uint(NULL, &hsz, n); hp = HAlloc(BIF_P, hsz); BIF_RET(erts_bld_uint(&hp, NULL, n)); + } else if (is_hashmap(BIF_ARG_1)) { + Eterm *head, *hp, res; + Uint size, hsz=0; + + head = hashmap_val(BIF_ARG_1); + size = head[1]; + (void) erts_bld_uint(NULL, &hsz, size); + hp = HAlloc(BIF_P, hsz); + res = erts_bld_uint(&hp, NULL, size); + BIF_RET(res); } BIF_ERROR(BIF_P, BADARG); -- cgit v1.2.3 From 903740ac57b00d404f430876b82cb21e0bb684a3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Thu, 19 Feb 2015 16:53:32 +0100 Subject: erts: Move hashmap:to_list/1, keys/1 and values/1 to maps --- erts/emulator/beam/erl_map.c | 115 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 113 insertions(+), 2 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index ecbb91bc33..289cd4fd13 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -31,6 +31,7 @@ #include "bif.h" #include "erl_map.h" +#include "erl_hashmap.h" /* BIFs * @@ -62,6 +63,10 @@ * - erts_internal:map_to_tuple_keys/1 */ +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); + /* erlang:map_size/1 * the corresponding instruction is implemented in: * beam/erl_bif_guard.c @@ -92,8 +97,7 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADARG); } -/* maps:to_list/1 - */ +/* maps:to_list/1 */ BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) { if (is_map(BIF_ARG_1)) { @@ -114,6 +118,8 @@ BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) { } BIF_RET(res); + } else if (is_hashmap(BIF_ARG_1)) { + return hashmap_to_list(BIF_P, BIF_ARG_1); } BIF_ERROR(BIF_P, BADARG); @@ -386,6 +392,8 @@ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { } BIF_RET(res); + } else if (is_hashmap(BIF_ARG_1)) { + BIF_RET(hashmap_keys(BIF_P, BIF_ARG_1)); } BIF_ERROR(BIF_P, BADARG); } @@ -786,10 +794,113 @@ BIF_RETTYPE maps_values_1(BIF_ALIST_1) { } BIF_RET(res); + } else if (is_hashmap(BIF_ARG_1)) { + BIF_RET(hashmap_values(BIF_P, BIF_ARG_1)); } BIF_ERROR(BIF_P, BADARG); } +static Eterm hashmap_to_list(Process *p, Eterm node) { + DECLARE_WSTACK(stack); + Eterm *hp, *kv; + Eterm res = NIL; + + hp = HAlloc(p, hashmap_size(node) * (2 + 3)); + hashmap_iterator_init(&stack, node); + while ((kv=hashmap_iterator_next(&stack)) != NULL) { + Eterm tup = TUPLE2(hp, CAR(kv), CDR(kv)); + hp += 3; + res = CONS(hp, tup, res); + hp += 2; + } + DESTROY_WSTACK(stack); + return res; +} + +void hashmap_iterator_init(ErtsWStack* s, Eterm node) { + WSTACK_PUSH((*s), (UWord)THE_NON_VALUE); /* end marker */ + WSTACK_PUSH((*s), (UWord)node); +} + +Eterm* hashmap_iterator_next(ErtsWStack* s) { + Eterm node, *ptr, hdr; + Uint32 sz; + + for (;;) { + ASSERT(!WSTACK_ISEMPTY((*s))); + node = (Eterm) WSTACK_POP((*s)); + if (is_non_value(node)) { + return NULL; + } + switch (primary_tag(node)) { + case TAG_PRIMARY_LIST: + return list_val(node); + + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + case HAMT_SUBTAG_NODE_ARRAY: + ptr++; + sz = 16; + while(sz--) { WSTACK_PUSH((*s), (UWord)ptr[sz]); } + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + ptr++; + while(sz--) { WSTACK_PUSH((*s), (UWord)ptr[sz]); } + break; + default: + erl_exit(1, "bad header"); + } + break; + + default: + erl_exit(1, "bad hamt node"); + } + } +} + +static Eterm hashmap_keys(Process* p, Eterm node) { + DECLARE_WSTACK(stack); + hashmap_head_t* root; + Eterm *hp, *kv; + Eterm res = NIL; + + root = (hashmap_head_t*) boxed_val(node); + hp = HAlloc(p, root->size * 2); + hashmap_iterator_init(&stack, node); + while ((kv=hashmap_iterator_next(&stack)) != NULL) { + res = CONS(hp, CAR(kv), res); + hp += 2; + } + DESTROY_WSTACK(stack); + return res; +} + +static Eterm hashmap_values(Process* p, Eterm node) { + DECLARE_WSTACK(stack); + hashmap_head_t* root; + Eterm *hp, *kv; + Eterm res = NIL; + + root = (hashmap_head_t*) boxed_val(node); + hp = HAlloc(p, root->size * 2); + hashmap_iterator_init(&stack, node); + while ((kv=hashmap_iterator_next(&stack)) != NULL) { + res = CONS(hp, CDR(kv), res); + hp += 2; + } + DESTROY_WSTACK(stack); + return res; +} + int erts_validate_and_sort_map(map_t* mp) { Eterm *ks = map_get_keys(mp); -- cgit v1.2.3 From f659c631f33ad86e7532c7198bbce6d7e07fe1dd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 11:48:46 +0100 Subject: erts: Move hashmap:get/2, find/2 and is_key/2 to maps --- erts/emulator/beam/erl_map.c | 97 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 97 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 289cd4fd13..0ac5885e6b 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -63,6 +63,7 @@ * - erts_internal:map_to_tuple_keys/1 */ +static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node); 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); @@ -181,6 +182,20 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) { BIF_RET(res); } + BIF_RET(am_error); + } else if (is_hashmap(BIF_ARG_2)) { + Eterm *hp, res; + const Eterm *value; + Uint32 hx = hashmap_make_hash(BIF_ARG_1); + + if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) { + hp = HAlloc(BIF_P, 3); + res = make_tuple(hp); + *hp++ = make_arityval(2); + *hp++ = am_ok; + *hp++ = *value; + BIF_RET(res); + } BIF_RET(am_error); } BIF_ERROR(BIF_P, BADARG); @@ -209,7 +224,15 @@ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { hp = HAlloc(BIF_P, 3); BIF_P->fvalue = TUPLE2(hp, error, BIF_ARG_1); BIF_ERROR(BIF_P, EXC_ERROR_2); + } else if (is_hashmap(BIF_ARG_2)) { + const Eterm *value; + Uint32 hx = hashmap_make_hash(BIF_ARG_1); + + if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) { + BIF_RET(*value); + } } + BIF_ERROR(BIF_P, BADARG); } @@ -365,6 +388,9 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { } } BIF_RET(am_false); + } else if (is_hashmap(BIF_ARG_2)) { + Uint32 hx = hashmap_make_hash(BIF_ARG_1); + BIF_RET(hashmap_get(hx, BIF_ARG_1, BIF_ARG_2) ? am_true : am_false); } BIF_ERROR(BIF_P, BADARG); } @@ -867,6 +893,77 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) { } } +static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) { + Eterm *ptr, hdr; + Eterm th[2]; + Uint ix,slot, lvl = 0; + Uint32 hval,bp; + + for (;;) { + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ + ptr = list_val(node); + if (EQ(CAR(ptr), key)) { + return &(CDR(ptr)); + } + return NULL; + 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); + node = ptr[ix+1]; + break; + case HAMT_SUBTAG_HEAD_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(th,hx,lvl,key); + 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)); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+1]; + break; + } + /* not occupied */ + return NULL; + case HAMT_SUBTAG_HEAD_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+2]; + break; + } + /* not occupied */ + return NULL; + 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; + } + } + return NULL; +} + static Eterm hashmap_keys(Process* p, Eterm node) { DECLARE_WSTACK(stack); hashmap_head_t* root; -- cgit v1.2.3 From d8c6b91a9dfb06dbe1143e6b06ef26dab153ca4b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 24 Feb 2015 10:50:51 +0100 Subject: erts: Refactor maps:get/2, find/2 and is_key/2 --- erts/emulator/beam/erl_map.c | 110 +++++++++++++------------------------------ 1 file changed, 33 insertions(+), 77 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 0ac5885e6b..304b5470f5 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -137,38 +137,45 @@ erts_maps_get_rel(Eterm key, Eterm map, Eterm *map_base) erts_maps_get(Eterm key, Eterm map) #endif { - Eterm *ks, *vs; - map_t *mp; - Uint n, i; + Uint32 hx; + if (is_map(map)) { + Eterm *ks, *vs; + map_t *mp; + Uint n, i; - mp = (map_t *)map_val_rel(map, map_base); - n = map_get_size(mp); + mp = (map_t *)map_val_rel(map, map_base); + n = map_get_size(mp); - if (n == 0) { - return NULL; - } + if (n == 0) { + return NULL; + } - ks = (Eterm *)tuple_val_rel(mp->keys, map_base) + 1; - vs = map_get_values(mp); + ks = (Eterm *)tuple_val_rel(mp->keys, map_base) + 1; + vs = map_get_values(mp); - if (is_immed(key)) { - for (i = 0; i < n; i++) { - if (ks[i] == key) { - return &vs[i]; - } - } - } + if (is_immed(key)) { + for (i = 0; i < n; i++) { + if (ks[i] == key) { + return &vs[i]; + } + } + } - for (i = 0; i < n; i++) { - if (eq_rel(ks[i], NULL, key, map_base)) { - return &vs[i]; - } + for (i = 0; i < n; i++) { + if (eq_rel(ks[i], NULL, key, map_base)) { + return &vs[i]; + } + } + return NULL; } - return NULL; + ASSERT(is_hashmap(map)); + hx = hashmap_make_hash(key); + + return hashmap_get(hx, key, map); } BIF_RETTYPE maps_find_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2)) { + if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { Eterm *hp, res; const Eterm *value; @@ -181,21 +188,6 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) { *hp++ = *value; BIF_RET(res); } - - BIF_RET(am_error); - } else if (is_hashmap(BIF_ARG_2)) { - Eterm *hp, res; - const Eterm *value; - Uint32 hx = hashmap_make_hash(BIF_ARG_1); - - if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) { - hp = HAlloc(BIF_P, 3); - res = make_tuple(hp); - *hp++ = make_arityval(2); - *hp++ = am_ok; - *hp++ = *value; - BIF_RET(res); - } BIF_RET(am_error); } BIF_ERROR(BIF_P, BADARG); @@ -207,7 +199,7 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) { */ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2)) { + if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { Eterm *hp; Eterm error; const Eterm *value; @@ -224,15 +216,7 @@ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { hp = HAlloc(BIF_P, 3); BIF_P->fvalue = TUPLE2(hp, error, BIF_ARG_1); BIF_ERROR(BIF_P, EXC_ERROR_2); - } else if (is_hashmap(BIF_ARG_2)) { - const Eterm *value; - Uint32 hx = hashmap_make_hash(BIF_ARG_1); - - if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) { - BIF_RET(*value); - } } - BIF_ERROR(BIF_P, BADARG); } @@ -361,36 +345,8 @@ error: */ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2)) { - Eterm *ks, key; - map_t *mp; - Uint n,i; - - mp = (map_t*)map_val(BIF_ARG_2); - key = BIF_ARG_1; - n = map_get_size(mp); - ks = map_get_keys(mp); - - if (n == 0) - BIF_RET(am_false); - - if (is_immed(key)) { - for( i = 0; i < n; i++) { - if (ks[i] == key) { - BIF_RET(am_true); - } - } - } - - for( i = 0; i < n; i++) { - if (EQ(ks[i], key)) { - BIF_RET(am_true); - } - } - BIF_RET(am_false); - } else if (is_hashmap(BIF_ARG_2)) { - Uint32 hx = hashmap_make_hash(BIF_ARG_1); - BIF_RET(hashmap_get(hx, BIF_ARG_1, BIF_ARG_2) ? am_true : am_false); + if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + BIF_RET(erts_maps_get(BIF_ARG_1, BIF_ARG_2) ? am_true : am_false); } BIF_ERROR(BIF_P, BADARG); } -- cgit v1.2.3 From ad19eacbdb3b32bb74897ad2425808b9d669ccb8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 15:37:55 +0100 Subject: erts: Move hashmap:put/3, update/3 to maps --- erts/emulator/beam/erl_map.c | 247 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 247 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') 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; -- cgit v1.2.3 From 8c9341288af6b66f0fd5caf229c87af29c59e711 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 17:58:52 +0100 Subject: erts: Reindent erts_maps_update --- erts/emulator/beam/erl_map.c | 78 ++++++++++++++++++++++---------------------- 1 file changed, 39 insertions(+), 39 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index f99a1b431b..3e1092bfbe 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -698,56 +698,56 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { */ int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) { - Sint n,i; - Eterm* hp,*shp; - Eterm *ks,*vs; - map_t *mp = (map_t*)map_val(map); + Sint n,i; + Eterm* hp,*shp; + Eterm *ks,*vs; + map_t *mp = (map_t*)map_val(map); - if ((n = map_get_size(mp)) == 0) { - return 0; - } + if ((n = map_get_size(mp)) == 0) { + return 0; + } - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = map_get_keys(mp); + vs = map_get_values(mp); - /* only allocate for values, - * assume key-tuple will be intact - */ + /* only allocate for values, + * assume key-tuple will be intact + */ - hp = HAlloc(p, MAP_HEADER_SIZE + n); - shp = hp; - *hp++ = MAP_HEADER; - *hp++ = n; - *hp++ = mp->keys; + hp = HAlloc(p, MAP_HEADER_SIZE + n); + shp = hp; + *hp++ = MAP_HEADER; + *hp++ = n; + *hp++ = mp->keys; - if (is_immed(key)) { - for( i = 0; i < n; i ++) { - if (ks[i] == key) { - goto found_key; - } else { - *hp++ = *vs++; - } + if (is_immed(key)) { + for( i = 0; i < n; i ++) { + if (ks[i] == key) { + goto found_key; + } else { + *hp++ = *vs++; } - } else { - for( i = 0; i < n; i ++) { - if (EQ(ks[i], key)) { - goto found_key; - } else { - *hp++ = *vs++; - } + } + } else { + for( i = 0; i < n; i ++) { + if (EQ(ks[i], key)) { + goto found_key; + } else { + *hp++ = *vs++; } } + } - HRelease(p, shp + MAP_HEADER_SIZE + n, shp); - return 0; + HRelease(p, shp + MAP_HEADER_SIZE + n, shp); + return 0; found_key: - *hp++ = value; - vs++; - if (++i < n) - sys_memcpy(hp, vs, (n - i)*sizeof(Eterm)); - *res = make_map(shp); - return 1; + *hp++ = value; + vs++; + if (++i < n) + sys_memcpy(hp, vs, (n - i)*sizeof(Eterm)); + *res = make_map(shp); + return 1; } BIF_RETTYPE maps_update_3(BIF_ALIST_3) { -- cgit v1.2.3 From 1d2c8a4280e0eb5d7182986862f20045bc3ed6f8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 24 Feb 2015 14:17:51 +0100 Subject: erts: Refactor maps:update/3 and maps:put/3 --- erts/emulator/beam/erl_map.c | 368 ++++++++++++++++++++++++------------------- 1 file changed, 206 insertions(+), 162 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 3e1092bfbe..8c44f45125 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -486,122 +486,11 @@ BIF_RETTYPE maps_new_0(BIF_ALIST_0) { BIF_RET(make_map(mp)); } -/* maps:put/3 - */ - -Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { - Sint n,i; - Sint c = 0; - Eterm* hp, *shp; - Eterm *ks,*vs, res, tup; - map_t *mp = (map_t*)map_val(map); - - n = map_get_size(mp); - - if (n == 0) { - hp = HAlloc(p, MAP_HEADER_SIZE + 1 + 2); - tup = make_tuple(hp); - *hp++ = make_arityval(1); - *hp++ = key; - res = make_map(hp); - *hp++ = MAP_HEADER; - *hp++ = 1; - *hp++ = tup; - *hp++ = value; - - return res; - } - - ks = map_get_keys(mp); - vs = map_get_values(mp); - - /* only allocate for values, - * assume key-tuple will be intact - */ - - hp = HAlloc(p, MAP_HEADER_SIZE + n); - shp = hp; /* save hp, used if optimistic update fails */ - res = make_map(hp); - *hp++ = MAP_HEADER; - *hp++ = n; - *hp++ = mp->keys; - - if (is_immed(key)) { - for( i = 0; i < n; i ++) { - if (ks[i] == key) { - *hp++ = value; - vs++; - c = 1; - } else { - *hp++ = *vs++; - } - } - } else { - for( i = 0; i < n; i ++) { - if (EQ(ks[i], key)) { - *hp++ = value; - vs++; - c = 1; - } else { - *hp++ = *vs++; - } - } - } - - if (c) - return res; - - /* need to make a new tuple, - * use old hp since it needs to be recreated anyway. - */ - tup = make_tuple(shp); - *shp++ = make_arityval(n+1); - - hp = HAlloc(p, 3 + n + 1); - res = make_map(hp); - *hp++ = MAP_HEADER; - *hp++ = n + 1; - *hp++ = tup; - - ks = map_get_keys(mp); - vs = map_get_values(mp); - - ASSERT(n >= 0); - - /* copy map in order */ - while (n && ((c = CMP_TERM(*ks, key)) < 0)) { - *shp++ = *ks++; - *hp++ = *vs++; - n--; - } - - *shp++ = key; - *hp++ = value; - - ASSERT(n >= 0); - - while(n--) { - *shp++ = *ks++; - *hp++ = *vs++; - } - /* we have one word remaining - * this will work out fine once we get the size word - * in the header. - */ - *shp = make_pos_bignum_header(0); - return res; -} +/* maps:put/3 */ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { - if (is_map(BIF_ARG_3)) { + if (is_map(BIF_ARG_3) || is_hashmap(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); } @@ -694,82 +583,237 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADARG); } -/* maps:update/3 - */ - int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) { - Sint n,i; - Eterm* hp,*shp; - Eterm *ks,*vs; - map_t *mp = (map_t*)map_val(map); + Uint32 hx; + if (is_map(map)) { + Sint n,i; + Eterm* hp,*shp; + Eterm *ks,*vs; + map_t *mp = (map_t*)map_val(map); + + if ((n = map_get_size(mp)) == 0) { + return 0; + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* only allocate for values, + * assume key-tuple will be intact + */ + + hp = HAlloc(p, MAP_HEADER_SIZE + n); + shp = hp; + *hp++ = MAP_HEADER; + *hp++ = n; + *hp++ = mp->keys; + + if (is_immed(key)) { + for( i = 0; i < n; i ++) { + if (ks[i] == key) { + goto found_key; + } else { + *hp++ = *vs++; + } + } + } else { + for( i = 0; i < n; i ++) { + if (EQ(ks[i], key)) { + goto found_key; + } else { + *hp++ = *vs++; + } + } + } - if ((n = map_get_size(mp)) == 0) { + HRelease(p, shp + MAP_HEADER_SIZE + n, shp); return 0; + +found_key: + *hp++ = value; + vs++; + if (++i < n) + sys_memcpy(hp, vs, (n - i)*sizeof(Eterm)); + *res = make_map(shp); + return 1; } - ks = map_get_keys(mp); - vs = map_get_values(mp); + ASSERT(is_hashmap(map)); + hx = hashmap_make_hash(key); + *res = hashmap_insert(p, hx, key, value, map, 1); + if (is_value(*res)) + return 1; - /* only allocate for values, - * assume key-tuple will be intact - */ + return 0; +} - hp = HAlloc(p, MAP_HEADER_SIZE + n); - shp = hp; - *hp++ = MAP_HEADER; - *hp++ = n; - *hp++ = mp->keys; +Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { + Uint32 hx; + Eterm res; + if (is_map(map)) { + Sint n,i; + Sint c = 0; + Eterm* hp, *shp; + Eterm *ks, *vs, tup; + map_t *mp = (map_t*)map_val(map); - if (is_immed(key)) { - for( i = 0; i < n; i ++) { - if (ks[i] == key) { - goto found_key; - } else { - *hp++ = *vs++; + n = map_get_size(mp); + + if (n == 0) { + hp = HAlloc(p, MAP_HEADER_SIZE + 1 + 2); + tup = make_tuple(hp); + *hp++ = make_arityval(1); + *hp++ = key; + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = 1; + *hp++ = tup; + *hp++ = value; + + return res; + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* only allocate for values, + * assume key-tuple will be intact + */ + + hp = HAlloc(p, MAP_HEADER_SIZE + n); + shp = hp; /* save hp, used if optimistic update fails */ + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = n; + *hp++ = mp->keys; + + if (is_immed(key)) { + for( i = 0; i < n; i ++) { + if (ks[i] == key) { + *hp++ = value; + vs++; + c = 1; + } else { + *hp++ = *vs++; + } + } + } else { + for( i = 0; i < n; i ++) { + if (EQ(ks[i], key)) { + *hp++ = value; + vs++; + c = 1; + } else { + *hp++ = *vs++; + } } } - } else { - for( i = 0; i < n; i ++) { - if (EQ(ks[i], key)) { - goto found_key; - } else { - *hp++ = *vs++; + + if (c) + return res; + + /* the map will grow */ + + if (n >= MAP_SMALL_MAP_LIMIT) { + hxnode_t *hxns; + Uint32 sw, hx; + Eterm tmp[2]; + + HRelease(p, shp + MAP_HEADER_SIZE + n, shp); + hp = HAlloc(p, (2 * (n + 1))); + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* create tmp hx values and leaf ptrs */ + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, (n + 1) * sizeof(hxnode_t)); + + for (i = 0; i < n; i++) { + hx = hashmap_restore_hash(tmp,0,ks[i]); + swizzle32(sw,hx); + hxns[i].hx = sw; + hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2; + hxns[i].skip = 1; + hxns[i].i = i; } + + hx = hashmap_restore_hash(tmp,0,key); + swizzle32(sw,hx); + hxns[i].hx = sw; + hxns[i].val = CONS(hp, key, value); hp += 2; + hxns[i].skip = 1; + hxns[i].i = n; + + res = hashmap_from_unsorted_array(p, hxns, n + 1); + + erts_free(ERTS_ALC_T_TMP, (void *) hxns); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + + return res; + } + + /* still a small map. need to make a new tuple, + * use old hp since it needs to be recreated anyway. */ + + tup = make_tuple(shp); + *shp++ = make_arityval(n+1); + + hp = HAlloc(p, 3 + n + 1); + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = n + 1; + *hp++ = tup; + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + ASSERT(n >= 0); + + /* copy map in order */ + while (n && ((c = CMP_TERM(*ks, key)) < 0)) { + *shp++ = *ks++; + *hp++ = *vs++; + n--; } + + *shp++ = key; + *hp++ = value; + + ASSERT(n >= 0); + + while(n--) { + *shp++ = *ks++; + *hp++ = *vs++; + } + /* we have one word remaining + * this will work out fine once we get the size word + * in the header. + */ + *shp = make_pos_bignum_header(0); + return res; } + ASSERT(is_hashmap(map)); - HRelease(p, shp + MAP_HEADER_SIZE + n, shp); - return 0; + hx = hashmap_make_hash(key); + res = hashmap_insert(p, hx, key, value, map, 0); + ASSERT(is_hashmap(res)); -found_key: - *hp++ = value; - vs++; - if (++i < n) - sys_memcpy(hp, vs, (n - i)*sizeof(Eterm)); - *res = make_map(shp); - return 1; + return res; } +/* maps:update/3 */ + BIF_RETTYPE maps_update_3(BIF_ALIST_3) { - if (is_map(BIF_ARG_3)) { + if (is_map(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { Eterm res; 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); } -/* maps:values/1 - */ +/* maps:values/1 */ BIF_RETTYPE maps_values_1(BIF_ALIST_1) { if (is_map(BIF_ARG_1)) { -- cgit v1.2.3 From 1b963c425591b75410fe46d9af3b44e47692059e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 15:49:43 +0100 Subject: erts: Move hashmap:remove/2 to maps --- erts/emulator/beam/erl_map.c | 257 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 255 insertions(+), 2 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 8c44f45125..672ac9f513 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -68,6 +68,7 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm 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); +static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); /* erlang:map_size/1 * the corresponding instruction is implemented in: @@ -495,8 +496,7 @@ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { BIF_ERROR(BIF_P, BADARG); } -/* maps:remove/3 - */ +/* maps:remove/3 */ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { Sint n; @@ -579,6 +579,9 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) { BIF_RET(res); } + } else 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); } @@ -1245,6 +1248,256 @@ static Eterm hashmap_values(Process* p, Eterm node) { 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]; + 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; +} + + int erts_validate_and_sort_map(map_t* mp) { Eterm *ks = map_get_keys(mp); -- cgit v1.2.3 From bb05557ff27e16e1e079e8f99b68713c7ca012c5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 24 Feb 2015 16:44:51 +0100 Subject: erts: Refactor maps:remove/2 --- erts/emulator/beam/erl_map.c | 182 +++++++++++++++++++++++++++---------------- 1 file changed, 113 insertions(+), 69 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 672ac9f513..69dd91d079 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -499,89 +499,93 @@ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { /* maps:remove/3 */ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { - Sint n; - Uint need; - Eterm *hp_start; - Eterm *thp, *mhp; - Eterm *ks, *vs, tup; - map_t *mp = (map_t*)map_val(map); - - n = map_get_size(mp); + Uint32 hx; + if (is_map(map)) { + Sint n; + Uint need; + Eterm *hp_start; + Eterm *thp, *mhp; + Eterm *ks, *vs, tup; + map_t *mp = (map_t*)map_val(map); - if (n == 0) { - *res = map; - return 1; - } + n = map_get_size(mp); - ks = map_get_keys(mp); - vs = map_get_values(mp); - - /* Assume key exists. - * Release allocated if it didn't. - * Allocate key tuple first. - */ - - need = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */ - hp_start = HAlloc(p, need); - thp = hp_start; - mhp = thp + n; /* offset with tuple heap size */ - - tup = make_tuple(thp); - *thp++ = make_arityval(n - 1); - - *res = make_map(mhp); - *mhp++ = MAP_HEADER; - *mhp++ = n - 1; - *mhp++ = tup; - - if (is_immed(key)) { - while (1) { - if (*ks == key) { - goto found_key; - } else if (--n) { - *mhp++ = *vs++; - *thp++ = *ks++; - } else - break; + if (n == 0) { + *res = map; + return 1; } - } else { - while(1) { - if (EQ(*ks, key)) { - goto found_key; - } else if (--n) { - *mhp++ = *vs++; - *thp++ = *ks++; - } else - break; + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* Assume key exists. + * Release allocated if it didn't. + * Allocate key tuple first. + */ + + need = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */ + hp_start = HAlloc(p, need); + thp = hp_start; + mhp = thp + n; /* offset with tuple heap size */ + + tup = make_tuple(thp); + *thp++ = make_arityval(n - 1); + + *res = make_map(mhp); + *mhp++ = MAP_HEADER; + *mhp++ = n - 1; + *mhp++ = tup; + + if (is_immed(key)) { + while (1) { + if (*ks == key) { + goto found_key; + } else if (--n) { + *mhp++ = *vs++; + *thp++ = *ks++; + } else + break; + } + } else { + while(1) { + if (EQ(*ks, key)) { + goto found_key; + } else if (--n) { + *mhp++ = *vs++; + *thp++ = *ks++; + } else + break; + } } - } - /* Not found, remove allocated memory - * and return previous map. - */ - HRelease(p, hp_start + need, hp_start); + /* Not found, remove allocated memory + * and return previous map. + */ + HRelease(p, hp_start + need, hp_start); - *res = map; - return 1; + *res = map; + return 1; found_key: - /* Copy rest of keys and values */ - if (--n) { - sys_memcpy(mhp, vs+1, n*sizeof(Eterm)); - sys_memcpy(thp, ks+1, n*sizeof(Eterm)); + /* Copy rest of keys and values */ + if (--n) { + sys_memcpy(mhp, vs+1, n*sizeof(Eterm)); + sys_memcpy(thp, ks+1, n*sizeof(Eterm)); + } + return 1; } + ASSERT(is_hashmap(map)); + hx = hashmap_make_hash(key); + *res = hashmap_delete(p, hx, key, map); return 1; } BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2)) { + if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { Eterm res; if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) { BIF_RET(res); } - } else 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); } @@ -1248,11 +1252,11 @@ static Eterm hashmap_values(Process* p, Eterm node) { return res; } -static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) { +static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm map) { Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL; Eterm th[2]; Eterm *ptr; - Eterm hdr,res = node; + Eterm hdr, res = map, node = map; Uint32 ix, bp, hval; Uint slot, lvl = 0; Uint size = 0, n = 0; @@ -1338,7 +1342,47 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) { unroll: /* the size is bounded and atleast one less than the previous size */ - size -= 1; + size -= 1; + n = hashmap_size(map) - 1; + + if (n <= MAP_SMALL_MAP_LIMIT) { + DECLARE_WSTACK(wstack); + Eterm *kv, *ks, *vs; + map_t *mp; + Eterm keys; + + DESTROY_ESTACK(stack); + + /* build flat structure */ + hp = HAlloc(p, 3 + 1 + (2 * n)); + keys = make_tuple(hp); + *hp++ = make_arityval(n); + ks = hp; + hp += n; + mp = (map_t*)hp; + hp += MAP_HEADER_SIZE; + vs = hp; + + mp->thing_word = MAP_HEADER; + mp->size = n; + mp->keys = keys; + + hashmap_iterator_init(&wstack, map); + + while ((kv=hashmap_iterator_next(&wstack)) != NULL) { + if (EQ(CAR(kv),key)) + continue; + *ks++ = CAR(kv); + *vs++ = CDR(kv); + } + + /* it cannot have multiple keys */ + erts_validate_and_sort_map(mp); + + DESTROY_WSTACK(wstack); + return make_map(mp); + } + hp = HAlloc(p, size); hp_end = hp + size; res = THE_NON_VALUE; -- cgit v1.2.3 From 73885d5d098a58aa6a4e226d075ee90b24045c66 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 16:03:03 +0100 Subject: erts: Refactor maps:from_list/1 --- erts/emulator/beam/erl_map.c | 163 ++++++++++++++++++++++--------------------- 1 file changed, 85 insertions(+), 78 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 69dd91d079..5e5e567642 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -69,6 +69,7 @@ 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); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); +static Eterm map_from_validated_list(Process *p, Eterm list, Uint size); /* erlang:map_size/1 * the corresponding instruction is implemented in: @@ -227,13 +228,8 @@ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { */ BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) { - Eterm *kv, item = BIF_ARG_1; - Eterm *hp, *thp,*vs, *ks, keys, res; - map_t *mp; - Uint size = 0, unused_size = 0; - Sint c = 0; - Sint idx = 0; - + Eterm item = BIF_ARG_1, res, *kv; + Uint size = 0; if (is_list(item) || is_nil(item)) { /* Calculate size and check validity */ @@ -254,95 +250,106 @@ BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) { if (is_not_nil(item)) goto error; - hp = HAlloc(BIF_P, 3 + 1 + (2 * size)); - thp = hp; - keys = make_tuple(hp); - *hp++ = make_arityval(size); - ks = hp; - hp += size; - mp = (map_t*)hp; - res = make_map(mp); - hp += MAP_HEADER_SIZE; - vs = hp; + BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size)); + } - mp->thing_word = MAP_HEADER; - mp->size = size; /* set later, might shrink*/ - mp->keys = keys; +error: - if (size == 0) - BIF_RET(res); + BIF_ERROR(BIF_P, BADARG); +} + +static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) { + Eterm *kv, item = list; + Eterm *hp, *thp,*vs, *ks, keys, res; + map_t *mp; + Uint unused_size = 0; + Sint c = 0; + Sint idx = 0; - item = BIF_ARG_1; - /* first entry */ - kv = tuple_val(CAR(list_val(item))); - ks[0] = kv[1]; - vs[0] = kv[2]; - size = 1; - item = CDR(list_val(item)); + hp = HAlloc(p, 3 + 1 + (2 * size)); + thp = hp; + keys = make_tuple(hp); + *hp++ = make_arityval(size); + ks = hp; + hp += size; + mp = (map_t*)hp; + res = make_map(mp); + hp += MAP_HEADER_SIZE; + vs = hp; - /* insert sort key/value pairs */ - while(is_list(item)) { + mp->thing_word = MAP_HEADER; + mp->size = size; /* set later, might shrink*/ + mp->keys = keys; - kv = tuple_val(CAR(list_val(item))); + if (size == 0) + return res; - /* compare ks backwards - * idx represent word index to be written (hole position). - * We cannot copy the elements when searching since we might - * have an equal key. So we search for just the index first =( - * - * It is perhaps faster to move the values in the first pass. - * Check for uniqueness during insert phase and then have a - * second phace compacting the map if duplicates are found - * during insert. .. or do someother sort .. shell-sort perhaps. - */ + /* first entry */ + kv = tuple_val(CAR(list_val(item))); + ks[0] = kv[1]; + vs[0] = kv[2]; + size = 1; + item = CDR(list_val(item)); + + /* insert sort key/value pairs */ + while(is_list(item)) { + + kv = tuple_val(CAR(list_val(item))); + + /* compare ks backwards + * idx represent word index to be written (hole position). + * We cannot copy the elements when searching since we might + * have an equal key. So we search for just the index first =( + * + * It is perhaps faster to move the values in the first pass. + * Check for uniqueness during insert phase and then have a + * second phace compacting the map if duplicates are found + * during insert. .. or do someother sort .. shell-sort perhaps. + */ - idx = size; + idx = size; - while(idx > 0 && (c = CMP_TERM(kv[1],ks[idx-1])) < 0) { idx--; } + while(idx > 0 && (c = CMP_TERM(kv[1],ks[idx-1])) < 0) { idx--; } - if (c == 0) { - /* last compare was equal, - * i.e. we have to release memory - * and overwrite that key/value - */ - ks[idx-1] = kv[1]; - vs[idx-1] = kv[2]; - unused_size++; - } else { - Uint i = size; - while(i > idx) { - ks[i] = ks[i-1]; - vs[i] = vs[i-1]; - i--; - } - ks[idx] = kv[1]; - vs[idx] = kv[2]; - size++; + if (c == 0) { + /* last compare was equal, + * i.e. we have to release memory + * and overwrite that key/value + */ + ks[idx-1] = kv[1]; + vs[idx-1] = kv[2]; + unused_size++; + } else { + Uint i = size; + while(i > idx) { + ks[i] = ks[i-1]; + vs[i] = vs[i-1]; + i--; } - item = CDR(list_val(item)); + ks[idx] = kv[1]; + vs[idx] = kv[2]; + size++; } + item = CDR(list_val(item)); + } - if (unused_size) { - /* the key tuple is embedded in the heap - * write a bignum to clear it. - */ - /* release values as normal since they are on the top of the heap */ - - ks[size] = make_pos_bignum_header(unused_size - 1); - HRelease(BIF_P, vs + size + unused_size, vs + size); - } + if (unused_size) { + /* the key tuple is embedded in the heap + * write a bignum to clear it. + */ + /* release values as normal since they are on the top of the heap */ - *thp = make_arityval(size); - mp->size = size; - BIF_RET(res); + ks[size] = make_pos_bignum_header(unused_size - 1); + HRelease(p, vs + size + unused_size, vs + size); } -error: - - BIF_ERROR(BIF_P, BADARG); + *thp = make_arityval(size); + mp->size = size; + return res; } + /* maps:is_key/2 */ -- cgit v1.2.3 From 9f0fccbd5e45cd11aecfd782c0dbc121c3895af6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 16:27:53 +0100 Subject: erts: Move hashmap:from_list/1 to maps --- erts/emulator/beam/erl_map.c | 442 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 441 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 5e5e567642..7281353af5 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -63,6 +63,14 @@ * - erts_internal:map_to_tuple_keys/1 */ +/* for hashmap_from_list/1 */ +typedef struct { + Uint32 hx; + Uint32 skip; + Uint i; + Eterm val; +} hxnode_t; + 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); @@ -70,6 +78,12 @@ static Eterm hashmap_keys(Process *p, Eterm map); static Eterm hashmap_values(Process *p, Eterm map); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); static Eterm map_from_validated_list(Process *p, Eterm list, Uint size); +static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size); +static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n); +static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int is_root); +static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root); +static int hxnodecmp(hxnode_t* a, hxnode_t* b); +static int hxnodecmpkey(hxnode_t* a, hxnode_t* b); /* erlang:map_size/1 * the corresponding instruction is implemented in: @@ -250,7 +264,11 @@ BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) { if (is_not_nil(item)) goto error; - BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size)); + if (size > MAP_SMALL_MAP_LIMIT) { + BIF_RET(hashmap_from_validated_list(BIF_P, BIF_ARG_1, size)); + } else { + BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size)); + } } error: @@ -349,6 +367,401 @@ static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) { return res; } +#define swizzle32(D,S) \ + do { \ + (D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20 \ + | ((S) & 0x00000f00) << 12 | ((S) & 0x0000f000) << 4 \ + | ((S) & 0x000f0000) >> 4 | ((S) & 0x00f00000) >> 12 \ + | ((S) & 0x0f000000) >> 20 | ((S) & 0xf0000000) >> 28; \ + } while(0) + +#define maskval(V,L) (((V) >> ((7 - (L))*4)) & 0xf) +#define cdepth(V1,V2) (hashmap_clz((V1) ^ (V2)) >> 2) + +static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { + Eterm item = list; + Eterm *hp; + Eterm *kv, res; + Eterm tmp[2]; + Uint32 sw, hx; + Uint ix = 0; + hxnode_t *hxns; + + ASSERT(size > 0); + + hp = HAlloc(p, (2 * size)); + + /* create tmp hx values and leaf ptrs */ + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, size * sizeof(hxnode_t)); + + while(is_list(item)) { + res = CAR(list_val(item)); + kv = tuple_val(res); + hx = hashmap_restore_hash(tmp,0,kv[1]); + swizzle32(sw,hx); + hxns[ix].hx = sw; + hxns[ix].val = CONS(hp, kv[1], kv[2]); hp += 2; + hxns[ix].skip = 1; /* will be reassigned in from_array */ + hxns[ix].i = ix; + ix++; + item = CDR(list_val(item)); + } + + res = hashmap_from_unsorted_array(p, hxns, size); + + erts_free(ERTS_ALC_T_TMP, (void *) hxns); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + + return res; +} + +Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { + Eterm tmp[2]; + Uint32 sw, hx; + Uint ix; + hxnode_t *hxns; + Eterm res; + + /* create tmp hx values and leaf ptrs */ + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t)); + + for (ix = 0; ix < n; ix++) { + hx = hashmap_restore_hash(tmp,0,CAR(list_val(leafs[ix]))); + swizzle32(sw,hx); + hxns[ix].hx = sw; + hxns[ix].val = leafs[ix]; + hxns[ix].skip = 1; + hxns[ix].i = ix; + } + + res = hashmap_from_unsorted_array(p, hxns, n); + + erts_free(ERTS_ALC_T_TMP, (void *) hxns); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + + return res; +} + +static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { + Uint jx = 0, ix = 0, lx, cx; + Eterm res; + + /* sort and compact array (remove non-unique entries) */ + qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp); + + ix = 0, cx = 0; + while(ix < n - 1) { + if (hxns[ix].hx == hxns[ix+1].hx) { + + /* find region of equal hash values */ + jx = ix + 1; + while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; } + /* find all correct keys from region + * (last in list but now hash sorted so we check highest id instead) */ + + /* resort with keys instead of hash value within region */ + + qsort(&hxns[ix], jx - ix, sizeof(hxnode_t), + (int (*)(const void *, const void *)) hxnodecmpkey); + + while(ix < jx) { + lx = ix; + while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) { + if (hxns[ix].i > hxns[lx].i) { + lx = ix; + } + ix++; + } + hxns[cx].hx = hxns[lx].hx; + hxns[cx].val = hxns[lx].val; + cx++; + } + ix = jx; + continue; + } + if (ix > cx) { + hxns[cx].hx = hxns[ix].hx; + hxns[cx].val = hxns[ix].val; + } + cx++; + ix++; + } + + if (ix < n) { + hxns[cx].hx = hxns[ix].hx; + hxns[cx].val = hxns[ix].val; + cx++; + } + + if (cx > 1) { + /* recursive decompose array */ + res = hashmap_from_sorted_unique_array(p, hxns, cx, 0); + } else { + Eterm *hp; + /* hash value has been swizzled, need to drag it down to get the + * correct slot. */ + hp = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1)); + hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf)); + hp[1] = 1; + hp[2] = hxns[0].val; + res = make_hashmap(hp); + } + + return res; +} + +static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) { + Eterm res = NIL; + Uint i,ix,jx,elems; + Uint32 sw, hx; + Eterm val; + Eterm th[2]; + hxnode_t *tmp; + + ASSERT(lvl < 32); + ix = 0; + elems = 1; + while (ix < n - 1) { + if (hxns[ix].hx == hxns[ix+1].hx) { + jx = ix + 1; + while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; } + tmp = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, ((jx - ix)) * sizeof(hxnode_t)); + + for(i = 0; i < jx - ix; i++) { + val = hxns[i + ix].val; + hx = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val))); + swizzle32(sw,hx); + tmp[i].hx = sw; + tmp[i].val = val; + tmp[i].i = i; + tmp[i].skip = 1; + } + + qsort(tmp, jx - ix, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp); + + hxns[ix].skip = jx - ix; + hxns[ix].val = hashmap_from_sorted_unique_array(p, tmp, jx - ix, lvl + 8); + erts_free(ERTS_ALC_T_TMP, (void *) tmp); + ix = jx; + if (ix < n) { elems++; } + continue; + } + hxns[ix].skip = 1; + elems++; + ix++; + } + + res = hashmap_from_chunked_array(p, hxns, elems, !lvl); + + ERTS_HOLE_CHECK(p); + + return res; +} + +#define HALLOC_EXTRA 200 +static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) { + Uint ix, d, dn, dc, slot, elems; + Uint32 v, vp, vn, hdr; + Uint bp, sz; + DECLARE_ESTACK(stack); + Eterm res = NIL, *hp = NULL, *nhp; + + ASSERT(n > 1); + + /* push initial nodes on the stack, + * this is the starting depth */ + + ix = 0; + d = 0; + vp = hxns[ix].hx; + v = hxns[ix + hxns[ix].skip].hx; + + ASSERT(vp > v); + slot = maskval(vp,d); + + while(slot == maskval(v,d)) { + ESTACK_PUSH(stack, 1 << slot); + d++; + slot = maskval(vp,d); + } + + res = hxns[ix].val; + + if (hxns[ix].skip > 1) { + dc = 7; + /* build collision nodes */ + while (dc > d) { + hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); + hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(vp,dc)); + hp[1] = res; + res = make_hashmap(hp); + dc--; + } + } + + ESTACK_PUSH(stack, res); + ESTACK_PUSH(stack, 1 << slot); + + /* all of the other nodes .. */ + elems = n - 2; /* remove first and last elements */ + while(elems--) { + hdr = ESTACK_POP(stack); + ix = ix + hxns[ix].skip; + + /* determine if node or subtree should be built by looking + * at the next value. */ + + vn = hxns[ix + hxns[ix].skip].hx; + dn = cdepth(v,vn); + ASSERT(v > vn); + + res = hxns[ix].val; + + if (hxns[ix].skip > 1) { + int wat = (d > dn) ? d : dn; + dc = 7; + /* build collision nodes */ + while (dc > wat) { + hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); + hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc)); + hp[1] = res; + res = make_hashmap(hp); + dc--; + } + } + + /* next depth is higher (implies collision) */ + if (d < dn) { + /* hdr is the popped one initially */ + while(d < dn) { + slot = maskval(v, d); + bp = 1 << slot; + ESTACK_PUSH(stack, hdr | bp); + d++; + hdr = 0; /* clear hdr for all other collisions */ + } + + slot = maskval(v, d); + bp = 1 << slot; + /* no more collisions */ + ESTACK_PUSH(stack,res); + ESTACK_PUSH(stack,bp); + } else if (d == dn) { + /* no collisions at all */ + slot = maskval(v, d); + bp = 1 << slot; + ESTACK_PUSH(stack,res); + ESTACK_PUSH(stack,hdr | bp); + } else { + /* dn < n, we have a drop and we are done + * build nodes and subtree */ + while (dn != d) { + slot = maskval(v, d); + bp = 1 << slot; + /* OR bitposition before sz calculation to handle + * redundant collisions */ + hdr |= bp; + sz = hashmap_bitcount(hdr); + hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA); + nhp = hp; + *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr); + *hp++ = res; sz--; + while (sz--) { *hp++ = ESTACK_POP(stack); } + ASSERT((hp - nhp) < 18); + res = make_hashmap(nhp); + + /* we need to pop the next hdr and push if we don't need it */ + + hdr = ESTACK_POP(stack); + d--; + } + ESTACK_PUSH(stack, res); + ESTACK_PUSH(stack, hdr); + } + + vp = v; + v = vn; + d = dn; + ERTS_HOLE_CHECK(p); + } + + /* v and vp are reused from above */ + dn = cdepth(vp,v); + ix = ix + hxns[ix].skip; + res = hxns[ix].val; + + if (hxns[ix].skip > 1) { + dc = 7; + /* build collision nodes */ + while (dc > dn) { + hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); + hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc)); + hp[1] = res; + res = make_hashmap(hp); + dc--; + } + } + + hdr = ESTACK_POP(stack); + /* pop remaining subtree if any */ + while (dn) { + slot = maskval(v, dn); + bp = 1 << slot; + /* OR bitposition before sz calculation to handle + * redundant collisions */ + hdr |= bp; + sz = hashmap_bitcount(hdr); + hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA); + nhp = hp; + *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr); + *hp++ = res; sz--; + + while (sz--) { *hp++ = ESTACK_POP(stack); } + res = make_hashmap(nhp); + hdr = ESTACK_POP(stack); + dn--; + } + + /* and finally the root .. */ + + slot = maskval(v, dn); + bp = 1 << slot; + hdr |= bp; + sz = hashmap_bitcount(hdr); + hp = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1)); + nhp = hp; + + if (is_root) { + *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++ = res; sz--; + while (sz--) { *hp++ = ESTACK_POP(stack); } + + res = make_hashmap(nhp); + + ASSERT(ESTACK_COUNT(stack) == 0); + DESTROY_ESTACK(stack); + ERTS_HOLE_CHECK(p); + return res; +} +#undef HALLOC_EXTRA + +static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) { + return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val))); +} + +static int hxnodecmp(hxnode_t *a, hxnode_t *b) { + if (a->hx < b->hx) + return 1; + else if (a->hx == b->hx) + return 0; + else + return -1; +} /* maps:is_key/2 */ @@ -1593,3 +2006,30 @@ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) { } BIF_ERROR(BIF_P, BADARG); } + +/* implementation of builtin emulations */ + +#if !defined(__GNUC__) +/* Count leading zeros emulation */ +Uint32 hashmap_clz(Uint32 x) { + Uint32 y; + int n = 32; + y = x >>16; if (y != 0) {n = n -16; x = y;} + y = x >> 8; if (y != 0) {n = n - 8; x = y;} + y = x >> 4; if (y != 0) {n = n - 4; x = y;} + y = x >> 2; if (y != 0) {n = n - 2; x = y;} + y = x >> 1; if (y != 0) return n - 2; + return n - x; +} +const Uint32 SK5 = 0x55555555, SK3 = 0x33333333; +const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF; + +/* CTPOP emulation */ +Uint32 hashmap_bitcount(Uint32 x) { + x -= ((x >> 1 ) & SK5); + x = (x & SK3 ) + ((x >> 2 ) & SK3 ); + x = (x & SKF0) + ((x >> 4 ) & SKF0); + x += x >> 8; + return (x + (x >> 16)) & 0x3F; +} +#endif -- cgit v1.2.3 From 746d2d846ebf20fc4dc303c53bcd1e908aee924b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 16:45:23 +0100 Subject: erts: Move hashmap:info/1 to erts_debug:map_info/1 --- erts/emulator/beam/erl_map.c | 133 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 133 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 7281353af5..14f16e9050 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -63,6 +63,10 @@ * - erts_internal:map_to_tuple_keys/1 */ +#ifndef DECL_AM +#define DECL_AM(S) Eterm AM_ ## S = am_atom_put(#S, sizeof(#S) - 1) +#endif + /* for hashmap_from_list/1 */ typedef struct { Uint32 hx; @@ -82,6 +86,8 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n); static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int is_root); static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root); +static Eterm hashmap_info(Process *p, Eterm node); +static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); static int hxnodecmp(hxnode_t* a, hxnode_t* b); static int hxnodecmpkey(hxnode_t* a, hxnode_t* b); @@ -1993,6 +1999,13 @@ int erts_validate_and_sort_map(map_t* mp) return 1; } +BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) { + if (is_hashmap(BIF_ARG_1)) { + BIF_RET(hashmap_info(BIF_P,BIF_ARG_1)); + } + BIF_ERROR(BIF_P, BADARG); +} + /* * erts_internal:map_to_tuple_keys/1 * @@ -2007,6 +2020,126 @@ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADARG); } +static Eterm hashmap_info(Process *p, Eterm node) { + Eterm *hp; + Eterm res = NIL, info = NIL; + Eterm *ptr, tup, hdr; + Uint sz; + DECL_AM(depth); + DECL_AM(leafs); + DECL_AM(bitmaps); + DECL_AM(arrays); + Uint nleaf=0, nbitmap=0, narray=0; + Uint bitmap_usage[16], leaf_usage[16]; + Uint lvl = 0, clvl; + DECLARE_ESTACK(stack); + + for (sz = 0; sz < 16; sz++) { + bitmap_usage[sz] = 0; + leaf_usage[sz] = 0; + } + + ptr = boxed_val(node); + ESTACK_PUSH(stack, 0); + ESTACK_PUSH(stack, node); + do { + node = ESTACK_POP(stack); + clvl = ESTACK_POP(stack); + lvl = MAX(lvl,clvl); + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: + nleaf++; + leaf_usage[clvl] += 1; + break; + 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: + 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)); + ASSERT(sz < 17); + bitmap_usage[sz-1] += 1; + while(sz--) { + ESTACK_PUSH(stack, clvl + 1); + ESTACK_PUSH(stack, ptr[sz+1]); + } + break; + case HAMT_SUBTAG_HEAD_BITMAP: + nbitmap++; + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + bitmap_usage[sz-1] += 1; + while(sz--) { + ESTACK_PUSH(stack, clvl + 1); + ESTACK_PUSH(stack, ptr[sz+2]); + } + break; + case HAMT_SUBTAG_HEAD_ARRAY: + narray++; + sz = 16; + while(sz--) { + ESTACK_PUSH(stack, clvl + 1); + ESTACK_PUSH(stack, ptr[sz+2]); + } + break; + default: + erl_exit(1, "bad header\r\n"); + break; + } + } + } while(!ESTACK_ISEMPTY(stack)); + + + /* size */ + sz = 0; + hashmap_bld_tuple_uint(NULL,&sz,16,leaf_usage); + hashmap_bld_tuple_uint(NULL,&sz,16,bitmap_usage); + + /* alloc */ + hp = HAlloc(p, 2+3 + 3*(2+4) + sz); + + info = hashmap_bld_tuple_uint(&hp,NULL,16,leaf_usage); + tup = TUPLE3(hp, AM_leafs, make_small(nleaf),info); hp += 4; + res = CONS(hp, tup, res); hp += 2; + + info = hashmap_bld_tuple_uint(&hp,NULL,16,bitmap_usage); + tup = TUPLE3(hp, AM_bitmaps, make_small(nbitmap), info); hp += 4; + res = CONS(hp, tup, res); hp += 2; + + tup = TUPLE3(hp, AM_arrays, make_small(narray),NIL); hp += 4; + res = CONS(hp, tup, res); hp += 2; + + tup = TUPLE2(hp, AM_depth, make_small(lvl)); hp += 3; + res = CONS(hp, tup, res); hp += 2; + + DESTROY_ESTACK(stack); + ERTS_HOLE_CHECK(p); + return res; +} + +static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) { + Eterm res = THE_NON_VALUE; + Eterm *ts = (Eterm *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(Eterm)); + Uint i; + + for (i = 0; i < n; i++) { + ts[i] = erts_bld_uint(hpp, szp, nums[i]); + } + res = erts_bld_tuplev(hpp, szp, n, ts); + erts_free(ERTS_ALC_T_TMP, (void *) ts); + return res; +} + + /* implementation of builtin emulations */ #if !defined(__GNUC__) -- cgit v1.2.3 From 7ac42c5d31f7722907b44d2df3421f8cd88d48c5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 17:27:41 +0100 Subject: erts: Move hashmap:merge/2 to maps --- erts/emulator/beam/erl_map.c | 467 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 392 insertions(+), 75 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 14f16e9050..8ae02e0183 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -77,6 +77,9 @@ typedef struct { 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 map_merge(Process *p, Eterm nodeA, Eterm nodeB); +static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args); +static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB); 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); @@ -452,6 +455,15 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { Uint jx = 0, ix = 0, lx, cx; Eterm res; + if (n == 0) { + Eterm *hp; + hp = HAlloc(p, 2); + hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0); + hp[1] = 0; + + return make_hashmap(hp); + } + /* sort and compact array (remove non-unique entries) */ qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp); @@ -504,8 +516,13 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { res = hashmap_from_sorted_unique_array(p, hxns, cx, 0); } else { Eterm *hp; - /* hash value has been swizzled, need to drag it down to get the + + /* we only have one item, either because n was 1 or + * because we hade multiples of the same key. + * + * hash value has been swizzled, need to drag it down to get the * correct slot. */ + hp = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1)); hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf)); hp[1] = 1; @@ -769,8 +786,7 @@ static int hxnodecmp(hxnode_t *a, hxnode_t *b) { return -1; } -/* maps:is_key/2 - */ +/* maps:is_key/2 */ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { @@ -779,8 +795,7 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADARG); } -/* maps:keys/1 - */ +/* maps:keys/1 */ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { if (is_map(BIF_ARG_1)) { @@ -807,94 +822,396 @@ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { } BIF_ERROR(BIF_P, BADARG); } -/* maps:merge/2 - */ +/* maps:merge/2 */ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_1) && is_map(BIF_ARG_2)) { - Eterm *hp,*thp; - Eterm tup; - Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2; - map_t *mp1,*mp2,*mp_new; - Uint n1,n2,i1,i2,need,unused_size=0; - int c = 0; - - mp1 = (map_t*)map_val(BIF_ARG_1); - mp2 = (map_t*)map_val(BIF_ARG_2); - n1 = map_get_size(mp1); - n2 = map_get_size(mp2); - - need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2); - - hp = HAlloc(BIF_P, need); - thp = hp; - tup = make_tuple(thp); - ks = hp + 1; hp += 1 + n1 + n2; - mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE; - vs = hp; hp += n1 + n2; - - mp_new->thing_word = MAP_HEADER; - mp_new->size = 0; - mp_new->keys = tup; - - i1 = 0; i2 = 0; - ks1 = map_get_keys(mp1); - vs1 = map_get_values(mp1); - ks2 = map_get_keys(mp2); - vs2 = map_get_values(mp2); - - while(i1 < n1 && i2 < n2) { - c = CMP_TERM(ks1[i1],ks2[i2]); - if ( c == 0) { - /* use righthand side arguments map value, - * but advance both maps */ - *ks++ = ks2[i2]; - *vs++ = vs2[i2]; - i1++, i2++, unused_size++; - } else if ( c < 0) { - *ks++ = ks1[i1]; - *vs++ = vs1[i1]; - i1++; - } else { - *ks++ = ks2[i2]; - *vs++ = vs2[i2]; - i2++; - } + if (is_map(BIF_ARG_1)) { + if (is_map(BIF_ARG_2)) { + BIF_RET(map_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); + } else if (is_hashmap(BIF_ARG_2)) { + BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_1, BIF_ARG_2, 0)); + } + } else if (is_hashmap(BIF_ARG_1)) { + if (is_hashmap(BIF_ARG_2)) { + BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); + } else if (is_map(BIF_ARG_2)) { + BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_2, BIF_ARG_1, 1)); } + } + BIF_ERROR(BIF_P, BADARG); +} - /* copy remaining */ - while (i1 < n1) { +static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { + Eterm *hp,*thp; + Eterm tup; + Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2; + map_t *mp1,*mp2,*mp_new; + Uint n1,n2,i1,i2,need,unused_size=0; + int c = 0; + + mp1 = (map_t*)map_val(nodeA); + mp2 = (map_t*)map_val(nodeB); + n1 = map_get_size(mp1); + n2 = map_get_size(mp2); + + need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2); + + hp = HAlloc(p, need); + thp = hp; + tup = make_tuple(thp); + ks = hp + 1; hp += 1 + n1 + n2; + mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE; + vs = hp; hp += n1 + n2; + + mp_new->thing_word = MAP_HEADER; + mp_new->size = 0; + mp_new->keys = tup; + + i1 = 0; i2 = 0; + ks1 = map_get_keys(mp1); + vs1 = map_get_values(mp1); + ks2 = map_get_keys(mp2); + vs2 = map_get_values(mp2); + + while(i1 < n1 && i2 < n2) { + c = CMP_TERM(ks1[i1],ks2[i2]); + if ( c == 0) { + /* use righthand side arguments map value, + * but advance both maps */ + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i1++, i2++, unused_size++; + } else if ( c < 0) { *ks++ = ks1[i1]; *vs++ = vs1[i1]; i1++; - } - - while (i2 < n2) { + } else { *ks++ = ks2[i2]; *vs++ = vs2[i2]; i2++; } + } - if (unused_size) { - /* the key tuple is embedded in the heap, write a bignum to clear it. - * - * release values as normal since they are on the top of the heap - * size = n1 + n1 - unused_size - */ + /* copy remaining */ + while (i1 < n1) { + *ks++ = ks1[i1]; + *vs++ = vs1[i1]; + i1++; + } + + while (i2 < n2) { + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i2++; + } + + if (unused_size) { + /* the key tuple is embedded in the heap, write a bignum to clear it. + * + * release values as normal since they are on the top of the heap + * size = n1 + n1 - unused_size + */ + + *ks = make_pos_bignum_header(unused_size - 1); + HRelease(p, vs + unused_size, vs); + } + + mp_new->size = n1 + n2 - unused_size; + *thp = make_arityval(n1 + n2 - unused_size); + + return make_map(mp_new); +} + +static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) { + Eterm *ks, *vs, *hp, res; + map_t *mp; + Uint n, i; + hxnode_t *hxns; + Uint32 sw, hx; + Eterm tmp[2]; + + /* convert flat to tree */ + + ASSERT(is_map(flat)); + ASSERT(is_hashmap(tree)); + + mp = (map_t*)map_val(flat); + n = map_get_size(mp); + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + hp = HAlloc(p, 2 * n); + + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t)); + + for (i = 0; i < n; i++) { + hx = hashmap_restore_hash(tmp,0,ks[i]); + swizzle32(sw,hx); + hxns[i].hx = sw; + hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2; + hxns[i].skip = 1; + hxns[i].i = i; + } + + res = hashmap_from_unsorted_array(p, hxns, n); + + erts_free(ERTS_ALC_T_TMP, (void *) hxns); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + + return swap_args ? hashmap_merge(p, tree, res) : hashmap_merge(p, res, tree); +} + +#define HALLOC_EXTRA 200 + +static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) { +#define PSTACK_TYPE struct HashmapMergePStackType + struct HashmapMergePStackType { + Eterm *srcA, *srcB; + Uint32 abm, bbm, rbm; /* node bitmaps */ + int keepA; + int ix; + Eterm array[16]; + }; + PSTACK_DECLARE(s, 4); + struct HashmapMergePStackType* sp = PSTACK_PUSH(s); + Eterm *hp, *nhp; + Eterm hdrA, hdrB; + Eterm th[2]; + Uint32 ahx, bhx; + Uint size; /* total key-value counter */ + int keepA = 0; + unsigned lvl = 0; + Eterm res = THE_NON_VALUE; + + /* + * Strategy: Do depth-first traversal of both trees (at the same time) + * and merge each pair of nodes. + */ - *ks = make_pos_bignum_header(unused_size - 1); - HRelease(BIF_P, vs + unused_size, vs); + { + hashmap_head_t* a = (hashmap_head_t*) hashmap_val(nodeA); + hashmap_head_t* b = (hashmap_head_t*) hashmap_val(nodeB); + size = a->size + b->size; + } + +recurse: + + if (primary_tag(nodeA) == TAG_PRIMARY_BOXED && + primary_tag(nodeB) == TAG_PRIMARY_LIST) { + /* Avoid implementing this combination by switching places */ + Eterm tmp = nodeA; + nodeA = nodeB; + nodeB = tmp; + keepA = !keepA; + } + + switch (primary_tag(nodeA)) { + case TAG_PRIMARY_LIST: { + sp->srcA = list_val(nodeA); + switch (primary_tag(nodeB)) { + case TAG_PRIMARY_LIST: { /* LEAF + LEAF */ + sp->srcB = list_val(nodeB); + + if (EQ(CAR(sp->srcA), CAR(sp->srcB))) { + --size; + res = keepA ? nodeA : nodeB; + } else { + ahx = hashmap_restore_hash(th, lvl, CAR(sp->srcA)); + bhx = hashmap_restore_hash(th, lvl, CAR(sp->srcB)); + sp->abm = 1 << hashmap_index(ahx); + sp->bbm = 1 << hashmap_index(bhx); + + sp->srcA = &nodeA; + sp->srcB = &nodeB; + } + break; } + case TAG_PRIMARY_BOXED: { /* LEAF + NODE */ + sp->srcB = boxed_val(nodeB); + ASSERT(is_header(*sp->srcB)); + hdrB = *sp->srcB++; + + ahx = hashmap_restore_hash(th, lvl, CAR(sp->srcA)); + 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: + sp->bbm = 0xffff; + break; - mp_new->size = n1 + n2 - unused_size; - *thp = make_arityval(n1 + n2 - unused_size); + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; + case HAMT_SUBTAG_NODE_BITMAP: + sp->bbm = MAP_HEADER_VAL(hdrB); + break; - BIF_RET(make_map(mp_new)); + default: + erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK); + break; + } + break; + } + default: + erl_exit(1, "bad primary tag %ld\r\n", nodeB); + } + break; } - BIF_ERROR(BIF_P, BADARG); + case TAG_PRIMARY_BOXED: { /* NODE + NODE */ + sp->srcA = boxed_val(nodeA); + 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: { + 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: + sp->bbm = 0xffff; + break; + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; + case HAMT_SUBTAG_NODE_BITMAP: + sp->bbm = MAP_HEADER_VAL(hdrB); + break; + default: + erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK); + } + break; + } + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcA++; + case HAMT_SUBTAG_NODE_BITMAP: { + ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED); + sp->abm = MAP_HEADER_VAL(hdrA); + 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: + sp->bbm = 0xffff; + break; + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; + case HAMT_SUBTAG_NODE_BITMAP: + sp->bbm = MAP_HEADER_VAL(hdrB); + break; + + default: + erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK); + } + break; + } + default: + erl_exit(1, "bad primary tag %ld\r\n", nodeA); + } + break; + } + default: + erl_exit(1, "bad primary tag %ld\r\n", nodeA); + } + + for (;;) { + if (is_value(res)) { /* We have a complete (sub-)tree or leaf */ + if (lvl == 0) + break; + + /* Pop from stack and continue build parent node */ + lvl--; + sp = PSTACK_POP(s); + sp->array[sp->ix++] = res; + res = THE_NON_VALUE; + if (sp->rbm) { + sp->srcA++; + sp->srcB++; + keepA = sp->keepA; + } + } else { /* Start build a node */ + sp->ix = 0; + sp->rbm = sp->abm | sp->bbm; + ASSERT(!(sp->rbm == 0 && lvl > 0)); + } + + while (sp->rbm) { + Uint32 next = sp->rbm & (sp->rbm-1); + Uint32 bit = sp->rbm ^ next; + sp->rbm = next; + if (sp->abm & bit) { + if (sp->bbm & bit) { + /* Bit clash. Push and resolve by recursive merge */ + if (sp->rbm) { + sp->keepA = keepA; + } + nodeA = *sp->srcA; + nodeB = *sp->srcB; + lvl++; + sp = PSTACK_PUSH(s); + goto recurse; + } else { + sp->array[sp->ix++] = *sp->srcA++; + } + } else { + ASSERT(sp->bbm & bit); + sp->array[sp->ix++] = *sp->srcB++; + } + } + + ASSERT(sp->ix == hashmap_bitcount(sp->abm | sp->bbm)); + if (lvl == 0) { + nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(sp->ix), HALLOC_EXTRA); + hp = nhp; + *hp++ = (sp->ix == 16 ? MAP_HEADER_HAMT_HEAD_ARRAY + : MAP_HEADER_HAMT_HEAD_BITMAP(sp->abm | sp->bbm)); + *hp++ = size; + } 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)); + } + memcpy(hp, sp->array, sp->ix * sizeof(Eterm)); + res = make_boxed(nhp); + } + PSTACK_DESTROY(s); + return res; } -/* maps:new/2 - */ + +static int hash_cmp(Uint32 ha, Uint32 hb) +{ + int i; + for (i=0; i<8; i++) { + int cmp = (int)(ha & 0xF) - (int)(hb & 0xF); + if (cmp) + return cmp; + ha >>= 4; + hb >>= 4; + } + return 0; +} + +int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp) +{ + Eterm th[2]; + unsigned lvl = 0; + + if (ap && bp) { + ASSERT(CMP_TERM(CAR(ap), CAR(bp)) != 0); + for (;;) { + Uint32 ha = hashmap_restore_hash(th, lvl, CAR(ap)); + Uint32 hb = hashmap_restore_hash(th, lvl, CAR(bp)); + int cmp = hash_cmp(ha, hb); + if (cmp) + return cmp; + lvl += 8; + } + } + return ap ? -1 : 1; +} + +/* maps:new/0 */ BIF_RETTYPE maps_new_0(BIF_ALIST_0) { Eterm* hp; -- cgit v1.2.3 From efb521c69baccb8ab905595c222abf353c5c3283 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 17:47:26 +0100 Subject: erts: Remove erl_hashmap.[ch] files --- erts/emulator/beam/erl_map.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 8ae02e0183..4242807933 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -16,6 +16,9 @@ * * %CopyrightEnd% * + * hashmaps are an adaption of Rich Hickeys Persistent HashMaps + * which were an adaption of Phil Bagwells - Hash Array Mapped Tries + * * Author: Björn-Egil Dahlberg */ @@ -31,7 +34,6 @@ #include "bif.h" #include "erl_map.h" -#include "erl_hashmap.h" /* BIFs * -- cgit v1.2.3 From f7ee6181417f05670e2e733085dd7f038d6f30f8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Thu, 26 Feb 2015 14:45:38 +0100 Subject: erts: Handle hashmap in get_map_element(s) instructions --- erts/emulator/beam/erl_map.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 4242807933..2be4c9a730 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -77,7 +77,6 @@ typedef struct { Eterm val; } hxnode_t; -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 map_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args); @@ -199,7 +198,7 @@ erts_maps_get(Eterm key, Eterm map) ASSERT(is_hashmap(map)); hx = hashmap_make_hash(key); - return hashmap_get(hx, key, map); + return erts_hashmap_get(hx, key, map); } BIF_RETTYPE maps_find_2(BIF_ALIST_2) { @@ -1660,7 +1659,7 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) { } } -static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) { +const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { Eterm *ptr, hdr; Eterm th[2]; Uint ix,slot, lvl = 0; -- cgit v1.2.3 From cdfa304b1da0eb9fb270fe78ee6acfc0dad864fc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Thu, 26 Feb 2015 17:10:40 +0100 Subject: erts: Split hashmap_insert to down and up --- erts/emulator/beam/erl_map.c | 113 +++++++++++++++++++++++++------------------ 1 file changed, 67 insertions(+), 46 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 2be4c9a730..4ad33f98a7 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -77,7 +77,7 @@ typedef struct { Eterm val; } hxnode_t; -static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update); + static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args); static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB); @@ -1391,7 +1391,7 @@ found_key: ASSERT(is_hashmap(map)); hx = hashmap_make_hash(key); - *res = hashmap_insert(p, hx, key, value, map, 1); + *res = erts_hashmap_insert(p, hx, key, value, map, 1); if (is_value(*res)) return 1; @@ -1545,7 +1545,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { ASSERT(is_hashmap(map)); hx = hashmap_make_hash(key); - res = hashmap_insert(p, hx, key, value, map, 0); + res = erts_hashmap_insert(p, hx, key, value, map, 0); ASSERT(is_hashmap(res)); return res; @@ -1730,16 +1730,34 @@ const Eterm *erts_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 erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, + Eterm map, int is_update) { + Uint size, upsz; + Eterm *hp, res = THE_NON_VALUE; + DECLARE_ESTACK(stack); + if (erts_hashmap_insert_down(hx, key, map, &size, &upsz, &stack, is_update)) { + hp = HAlloc(p, size); + res = erts_hashmap_insert_up(hp, key, value, &upsz, &stack); + } + + DESTROY_ESTACK(stack); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + ERTS_HOLE_CHECK(p); + + return res; +} + + +int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz, + Uint *update_size, ErtsEStack *sp, int is_update) { Eterm *ptr; - Eterm hdr,res,ckey,fake; + Eterm hdr, ckey; 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); + Uint size = 0, n = 0; + + *update_size = 1; for (;;) { switch(primary_tag(node)) { @@ -1747,12 +1765,11 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, ptr = list_val(node); ckey = CAR(ptr); if (EQ(ckey, key)) { - update_size = 0; + *update_size = 0; goto unroll; } if (is_update) { - res = THE_NON_VALUE; - goto bail_out; + return 0; } goto insert_subnodes; case TAG_PRIMARY_BOXED: @@ -1765,14 +1782,14 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, ix = hashmap_index(hx); hx = hashmap_shift_hash(th,hx,lvl,key); size += HAMT_NODE_ARRAY_SZ; - ESTACK_PUSH2(stack, ix, node); + 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); size += HAMT_HEAD_ARRAY_SZ; - ESTACK_PUSH2(stack, ix, node); + ESTACK_PUSH2(*sp, ix, node); node = ptr[ix+2]; break; case HAMT_SUBTAG_NODE_BITMAP: @@ -1782,8 +1799,8 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, slot = hashmap_bitcount(hval & (bp - 1)); n = hashmap_bitcount(hval); - ESTACK_PUSH(stack, n); - ESTACK_PUSH3(stack, bp, slot, node); + ESTACK_PUSH(*sp, n); + ESTACK_PUSH3(*sp, bp, slot, node); /* occupied */ if (bp & hval) { @@ -1795,8 +1812,7 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, } /* not occupied */ if (is_update) { - res = THE_NON_VALUE; - goto bail_out; + return 0; } size += HAMT_NODE_BITMAP_SZ(n+1); goto unroll; @@ -1807,8 +1823,8 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, slot = hashmap_bitcount(hval & (bp - 1)); n = hashmap_bitcount(hval); - ESTACK_PUSH(stack, n); - ESTACK_PUSH3(stack, bp, slot, node); + ESTACK_PUSH(*sp, n); + ESTACK_PUSH3(*sp, bp, slot, node); /* occupied */ if (bp & hval) { @@ -1820,8 +1836,7 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, } /* not occupied */ if (is_update) { - res = THE_NON_VALUE; - goto bail_out; + return 0; } size += HAMT_HEAD_BITMAP_SZ(n+1); goto unroll; @@ -1843,27 +1858,37 @@ insert_subnodes: cix = hashmap_index(chx); while (cix == ix) { - ESTACK_PUSH(stack, 0); - ESTACK_PUSH3(stack, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0)); + ESTACK_PUSH(*sp, 0); + ESTACK_PUSH3(*sp, 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); + ESTACK_PUSH3(*sp, cix, ix, node); unroll: - size += 2; - hp = HAlloc(p, size); + *sz = size + /* res cons */ 2; + return 1; +} + +Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, + Uint *update_size, ErtsEStack *sp) { + Eterm node, fake, *ptr, hdr; + Eterm res; + Eterm *nhp = NULL; + Uint32 ix, cix, bp, hval; + Uint slot, n; + res = CONS(hp, key, value); hp += 2; do { - node = ESTACK_POP(stack); + node = ESTACK_POP(*sp); switch(primary_tag(node)) { case TAG_PRIMARY_LIST: - ix = (Uint32) ESTACK_POP(stack); - cix = (Uint32) ESTACK_POP(stack); + ix = (Uint32) ESTACK_POP(*sp); + cix = (Uint32) ESTACK_POP(*sp); nhp = hp; *hp++ = MAP_HEADER_HAMT_NODE_BITMAP((1 << ix) | (1 << cix)); @@ -1887,7 +1912,7 @@ unroll: switch(hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_NODE_ARRAY: - slot = (Uint) ESTACK_POP(stack); + slot = (Uint) ESTACK_POP(*sp); nhp = hp; n = HAMT_NODE_ARRAY_SZ; while(n--) { *hp++ = *ptr++; } @@ -1895,19 +1920,19 @@ unroll: res = make_hashmap(nhp); break; case HAMT_SUBTAG_HEAD_ARRAY: - slot = (Uint) ESTACK_POP(stack); + slot = (Uint) ESTACK_POP(*sp); nhp = hp; n = HAMT_HEAD_ARRAY_SZ - 2; *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++; - *hp++ = (*ptr++) + update_size; + *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); + slot = (Uint) ESTACK_POP(*sp); + bp = (Uint32) ESTACK_POP(*sp); + n = (Uint32) ESTACK_POP(*sp); hval = MAP_HEADER_VAL(hdr); nhp = hp; *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval | bp); ptr++; @@ -1924,13 +1949,13 @@ unroll: 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); + slot = (Uint) ESTACK_POP(*sp); + bp = (Uint32) ESTACK_POP(*sp); + n = (Uint32) ESTACK_POP(*sp); hval = MAP_HEADER_VAL(hdr); nhp = hp; *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++; - *hp++ = (*ptr++) + update_size; + *hp++ = (*ptr++) + *update_size; n -= slot; while(slot--) { *hp++ = *ptr++; } @@ -1953,13 +1978,9 @@ unroll: break; } - } while(!ESTACK_ISEMPTY(stack)); + } while(!ESTACK_ISEMPTY(*sp)); -bail_out: - DESTROY_ESTACK(stack); - ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); - ERTS_HOLE_CHECK(p); - return res; + return res; } static Eterm hashmap_keys(Process* p, Eterm node) { -- cgit v1.2.3 From eb6f1d4923899fcb29a5d3c312f14489e7846a37 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 3 Mar 2015 09:35:10 +0100 Subject: erts: Ensure maps becomes hashmaps in maps:merge/2 Maps should become hashmaps when merged size exceeds small limit size. --- erts/emulator/beam/erl_map.c | 49 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 42 insertions(+), 7 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 4ad33f98a7..1703f86b0e 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -830,12 +830,14 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) { if (is_map(BIF_ARG_2)) { BIF_RET(map_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); } else if (is_hashmap(BIF_ARG_2)) { + /* Will always become a tree */ BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_1, BIF_ARG_2, 0)); } } else if (is_hashmap(BIF_ARG_1)) { if (is_hashmap(BIF_ARG_2)) { BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); } else if (is_map(BIF_ARG_2)) { + /* Will always become a tree */ BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_2, BIF_ARG_1, 1)); } } @@ -847,7 +849,7 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { Eterm tup; Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2; map_t *mp1,*mp2,*mp_new; - Uint n1,n2,i1,i2,need,unused_size=0; + Uint n,n1,n2,i1,i2,need,unused_size=0; int c = 0; mp1 = (map_t*)map_val(nodeA); @@ -876,13 +878,13 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { while(i1 < n1 && i2 < n2) { c = CMP_TERM(ks1[i1],ks2[i2]); - if ( c == 0) { + if (c == 0) { /* use righthand side arguments map value, * but advance both maps */ *ks++ = ks2[i2]; *vs++ = vs2[i2]; i1++, i2++, unused_size++; - } else if ( c < 0) { + } else if (c < 0) { *ks++ = ks1[i1]; *vs++ = vs1[i1]; i1++; @@ -917,8 +919,42 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { HRelease(p, vs + unused_size, vs); } - mp_new->size = n1 + n2 - unused_size; - *thp = make_arityval(n1 + n2 - unused_size); + n = n1 + n2 - unused_size; + *thp = make_arityval(n); + + /* Reshape map to a hashmap if the map exceeds the limit */ + + if (n > MAP_SMALL_MAP_LIMIT) { + Uint32 hx,sw; + Uint i; + Eterm res; + hxnode_t *hxns; + + ks = map_get_keys(mp_new); + vs = map_get_values(mp_new); + + hp = HAlloc(p, 2 * n); + + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP,n * sizeof(hxnode_t)); + + for (i = 0; i < n; i++) { + hx = hashmap_make_hash(ks[i]); + swizzle32(sw,hx); + hxns[i].hx = sw; + hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2; + hxns[i].skip = 1; + hxns[i].i = i; + } + + res = hashmap_from_unsorted_array(p, hxns, n); + + erts_free(ERTS_ALC_T_TMP, (void *) hxns); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + + return res; + } + + mp_new->size = n; return make_map(mp_new); } @@ -929,7 +965,6 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) Uint n, i; hxnode_t *hxns; Uint32 sw, hx; - Eterm tmp[2]; /* convert flat to tree */ @@ -947,7 +982,7 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t)); for (i = 0; i < n; i++) { - hx = hashmap_restore_hash(tmp,0,ks[i]); + hx = hashmap_make_hash(ks[i]); swizzle32(sw,hx); hxns[i].hx = sw; hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2; -- cgit v1.2.3 From 9794b73998690178538a1dfc193565dcd477b4fe Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 3 Mar 2015 12:46:05 +0100 Subject: erts: Fix update_map_assoc instruction Did not build a hashmap once the small limit was exceeded. --- erts/emulator/beam/erl_map.c | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 1703f86b0e..e26b97d75c 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -452,6 +452,37 @@ Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { return res; } + +Eterm erts_hashmap_from_ks_and_vs(Process *p, Eterm *ks, Eterm *vs, Uint n) { + Uint32 sw, hx; + Uint i; + hxnode_t *hxns; + Eterm *hp, res; + + ASSERT(n > 0); + + hp = HAlloc(p, (2 * n)); + + /* create tmp hx values and leaf ptrs */ + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t)); + + for(i = 0; i < n; i++) { + hx = hashmap_make_hash(ks[i]); + swizzle32(sw,hx); + hxns[i].hx = sw; + hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2; + hxns[i].skip = 1; /* will be reassigned in from_array */ + hxns[i].i = i; + } + + res = hashmap_from_unsorted_array(p, hxns, n); + + erts_free(ERTS_ALC_T_TMP, (void *) hxns); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + + return res; +} + static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { Uint jx = 0, ix = 0, lx, cx; Eterm res; -- cgit v1.2.3 From de95f407aba2c8b7bf2a5827842722581aacfd6a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 3 Mar 2015 13:34:14 +0100 Subject: erts: Refactor hashmap_from_ks_and_vs Use extra key and value if needed. --- erts/emulator/beam/erl_map.c | 54 +++++++++++++++----------------------------- 1 file changed, 18 insertions(+), 36 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index e26b97d75c..97f94d90ac 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -453,18 +453,18 @@ Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { } -Eterm erts_hashmap_from_ks_and_vs(Process *p, Eterm *ks, Eterm *vs, Uint n) { +Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n, + Eterm key, Eterm value) { Uint32 sw, hx; - Uint i; + Uint i,sz; hxnode_t *hxns; Eterm *hp, res; - ASSERT(n > 0); - - hp = HAlloc(p, (2 * n)); + sz = (key == THE_NON_VALUE) ? n : (n + 1); + hp = HAlloc(p, 2 * sz); /* create tmp hx values and leaf ptrs */ - hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t)); + hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, sz * sizeof(hxnode_t)); for(i = 0; i < n; i++) { hx = hashmap_make_hash(ks[i]); @@ -475,7 +475,16 @@ Eterm erts_hashmap_from_ks_and_vs(Process *p, Eterm *ks, Eterm *vs, Uint n) { hxns[i].i = i; } - res = hashmap_from_unsorted_array(p, hxns, n); + if (key != THE_NON_VALUE) { + hx = hashmap_make_hash(key); + swizzle32(sw,hx); + hxns[i].hx = sw; + hxns[i].val = CONS(hp, key, value); hp += 2; + hxns[i].skip = 1; + hxns[i].i = i; + } + + res = hashmap_from_unsorted_array(p, hxns, sz); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -1531,39 +1540,12 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { /* the map will grow */ - if (n >= MAP_SMALL_MAP_LIMIT) { - hxnode_t *hxns; - Uint32 sw, hx; - Eterm tmp[2]; - + if (n > MAP_SMALL_MAP_LIMIT) { HRelease(p, shp + MAP_HEADER_SIZE + n, shp); - hp = HAlloc(p, (2 * (n + 1))); ks = map_get_keys(mp); vs = map_get_values(mp); - /* create tmp hx values and leaf ptrs */ - hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, (n + 1) * sizeof(hxnode_t)); - - for (i = 0; i < n; i++) { - hx = hashmap_restore_hash(tmp,0,ks[i]); - swizzle32(sw,hx); - hxns[i].hx = sw; - hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2; - hxns[i].skip = 1; - hxns[i].i = i; - } - - hx = hashmap_restore_hash(tmp,0,key); - swizzle32(sw,hx); - hxns[i].hx = sw; - hxns[i].val = CONS(hp, key, value); hp += 2; - hxns[i].skip = 1; - hxns[i].i = n; - - res = hashmap_from_unsorted_array(p, hxns, n + 1); - - erts_free(ERTS_ALC_T_TMP, (void *) hxns); - ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + res = erts_hashmap_from_ks_and_vs_extra(p,ks,vs,n,key,value); return res; } -- cgit v1.2.3 From 3697ee925251edfe7a7ac2ed483039f414830012 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 3 Mar 2015 17:16:51 +0100 Subject: erts: Fix instruction new_map --- erts/emulator/beam/erl_map.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 97f94d90ac..ea041e2303 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -426,7 +426,6 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { } Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { - Eterm tmp[2]; Uint32 sw, hx; Uint ix; hxnode_t *hxns; @@ -436,12 +435,13 @@ Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t)); for (ix = 0; ix < n; ix++) { - hx = hashmap_restore_hash(tmp,0,CAR(list_val(leafs[ix]))); + hx = hashmap_make_hash(*leafs); swizzle32(sw,hx); hxns[ix].hx = sw; - hxns[ix].val = leafs[ix]; + hxns[ix].val = make_list(leafs); hxns[ix].skip = 1; hxns[ix].i = ix; + leafs += 2; } res = hashmap_from_unsorted_array(p, hxns, n); -- cgit v1.2.3 From 412c30b4dcdb8388b7472c8abb328f2a2fce92c0 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 3 Mar 2015 19:26:03 +0100 Subject: erts: Fix various map vs hamt size bugs --- erts/emulator/beam/erl_map.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index ea041e2303..0cf1c0e59d 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -422,6 +422,41 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + if (hashmap_size(res) <= MAP_SMALL_MAP_LIMIT) { + DECLARE_WSTACK(wstack); + Eterm *kv, *ks, *vs; + map_t *mp; + Eterm keys; + Uint n = hashmap_size(res); + + /* build flat structure */ + hp = HAlloc(p, 3 + 1 + (2 * n)); + keys = make_tuple(hp); + *hp++ = make_arityval(n); + ks = hp; + hp += n; + mp = (map_t*)hp; + hp += MAP_HEADER_SIZE; + vs = hp; + + mp->thing_word = MAP_HEADER; + mp->size = n; + mp->keys = keys; + + hashmap_iterator_init(&wstack, res); + + while ((kv=hashmap_iterator_next(&wstack)) != NULL) { + *ks++ = CAR(kv); + *vs++ = CDR(kv); + } + + /* it cannot have multiple keys */ + erts_validate_and_sort_map(mp); + + DESTROY_WSTACK(wstack); + return make_map(mp); + } + return res; } @@ -461,6 +496,7 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n Eterm *hp, res; sz = (key == THE_NON_VALUE) ? n : (n + 1); + ASSERT(sz > MAP_SMALL_MAP_LIMIT); hp = HAlloc(p, 2 * sz); /* create tmp hx values and leaf ptrs */ -- cgit v1.2.3 From f8dbf0c0ff3bd68d720faca230356d281e4e3e42 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 3 Mar 2015 19:32:00 +0100 Subject: First stab at binary_to_term for hamt with over estimation of heap size. --- erts/emulator/beam/erl_map.c | 66 +++++++++++++++++++++++++------------------- 1 file changed, 38 insertions(+), 28 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 0cf1c0e59d..eacdd0b6c3 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -87,9 +87,9 @@ static Eterm hashmap_values(Process *p, Eterm map); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); static Eterm map_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size); -static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n); -static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int is_root); -static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root); +static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n); +static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); +static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); static Eterm hashmap_info(Process *p, Eterm node); static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); static int hxnodecmp(hxnode_t* a, hxnode_t* b); @@ -396,6 +396,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { Uint32 sw, hx; Uint ix = 0; hxnode_t *hxns; + ErtsHeapFactory factory; ASSERT(size > 0); @@ -417,7 +418,8 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { item = CDR(list_val(item)); } - res = hashmap_from_unsorted_array(p, hxns, size); + factory.p = p; + res = hashmap_from_unsorted_array(&factory, hxns, size); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -460,7 +462,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { return res; } -Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { +Eterm erts_hashmap_from_array(ErtsHeapFactory* factory, Eterm *leafs, Uint n) { Uint32 sw, hx; Uint ix; hxnode_t *hxns; @@ -479,10 +481,9 @@ Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) { leafs += 2; } - res = hashmap_from_unsorted_array(p, hxns, n); + res = hashmap_from_unsorted_array(factory, hxns, n); erts_free(ERTS_ALC_T_TMP, (void *) hxns); - ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); return res; } @@ -493,6 +494,7 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n Uint32 sw, hx; Uint i,sz; hxnode_t *hxns; + ErtsHeapFactory factory; Eterm *hp, res; sz = (key == THE_NON_VALUE) ? n : (n + 1); @@ -520,7 +522,8 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n hxns[i].i = i; } - res = hashmap_from_unsorted_array(p, hxns, sz); + factory.p = p; + res = hashmap_from_unsorted_array(&factory, hxns, sz); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -528,13 +531,14 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n return res; } -static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { +static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory, + hxnode_t *hxns, Uint n) { Uint jx = 0, ix = 0, lx, cx; Eterm res; if (n == 0) { Eterm *hp; - hp = HAlloc(p, 2); + hp = erts_produce_heap(factory, 2, 0); hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0); hp[1] = 0; @@ -590,7 +594,7 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { if (cx > 1) { /* recursive decompose array */ - res = hashmap_from_sorted_unique_array(p, hxns, cx, 0); + res = hashmap_from_sorted_unique_array(factory, hxns, cx, 0); } else { Eterm *hp; @@ -600,7 +604,7 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { * hash value has been swizzled, need to drag it down to get the * correct slot. */ - hp = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1)); + hp = erts_produce_heap(factory, HAMT_HEAD_BITMAP_SZ(1), 0); hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf)); hp[1] = 1; hp[2] = hxns[0].val; @@ -610,7 +614,8 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) { return res; } -static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) { +static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory, + hxnode_t *hxns, Uint n, int lvl) { Eterm res = NIL; Uint i,ix,jx,elems; Uint32 sw, hx; @@ -640,7 +645,7 @@ static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n qsort(tmp, jx - ix, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp); hxns[ix].skip = jx - ix; - hxns[ix].val = hashmap_from_sorted_unique_array(p, tmp, jx - ix, lvl + 8); + hxns[ix].val = hashmap_from_sorted_unique_array(factory, tmp, jx - ix, lvl + 8); erts_free(ERTS_ALC_T_TMP, (void *) tmp); ix = jx; if (ix < n) { elems++; } @@ -651,15 +656,16 @@ static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n ix++; } - res = hashmap_from_chunked_array(p, hxns, elems, !lvl); + res = hashmap_from_chunked_array(factory, hxns, elems, !lvl); - ERTS_HOLE_CHECK(p); + ERTS_FACTORY_HOLE_CHECK(factory); return res; } #define HALLOC_EXTRA 200 -static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) { +static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, + hxnode_t *hxns, Uint n, int is_root) { Uint ix, d, dn, dc, slot, elems; Uint32 v, vp, vn, hdr; Uint bp, sz; @@ -691,7 +697,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int dc = 7; /* build collision nodes */ while (dc > d) { - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); + hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(vp,dc)); hp[1] = res; res = make_hashmap(hp); @@ -722,7 +728,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int dc = 7; /* build collision nodes */ while (dc > wat) { - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); + hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc)); hp[1] = res; res = make_hashmap(hp); @@ -762,7 +768,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int * redundant collisions */ hdr |= bp; sz = hashmap_bitcount(hdr); - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA); + 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++ = res; sz--; @@ -782,7 +788,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int vp = v; v = vn; d = dn; - ERTS_HOLE_CHECK(p); + ERTS_FACTORY_HOLE_CHECK(factory); } /* v and vp are reused from above */ @@ -794,7 +800,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int dc = 7; /* build collision nodes */ while (dc > dn) { - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); + hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc)); hp[1] = res; res = make_hashmap(hp); @@ -811,7 +817,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int * redundant collisions */ hdr |= bp; sz = hashmap_bitcount(hdr); - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA); + 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++ = res; sz--; @@ -828,7 +834,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int bp = 1 << slot; hdr |= bp; sz = hashmap_bitcount(hdr); - hp = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1)); + hp = erts_produce_heap(factory, sz + /* hdr + item */ (is_root ? 2 : 1), 0); nhp = hp; if (is_root) { @@ -845,7 +851,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int ASSERT(ESTACK_COUNT(stack) == 0); DESTROY_ESTACK(stack); - ERTS_HOLE_CHECK(p); + ERTS_FACTORY_HOLE_CHECK(factory); return res; } #undef HALLOC_EXTRA @@ -1005,6 +1011,7 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { Uint i; Eterm res; hxnode_t *hxns; + ErtsHeapFactory factory; ks = map_get_keys(mp_new); vs = map_get_values(mp_new); @@ -1022,7 +1029,8 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { hxns[i].i = i; } - res = hashmap_from_unsorted_array(p, hxns, n); + factory.p = p; + res = hashmap_from_unsorted_array(&factory, hxns, n); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -1041,6 +1049,7 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) Uint n, i; hxnode_t *hxns; Uint32 sw, hx; + ErtsHeapFactory factory; /* convert flat to tree */ @@ -1066,7 +1075,8 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) hxns[i].i = i; } - res = hashmap_from_unsorted_array(p, hxns, n); + factory.p = p; + res = hashmap_from_unsorted_array(&factory, hxns, n); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -1576,7 +1586,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { /* the map will grow */ - if (n > MAP_SMALL_MAP_LIMIT) { + if (n >= MAP_SMALL_MAP_LIMIT) { HRelease(p, shp + MAP_HEADER_SIZE + n, shp); ks = map_get_keys(mp); vs = map_get_values(mp); -- cgit v1.2.3 From 01e843722aa39b3411d349c6fbea80ad87a6e9ef Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 5 Mar 2015 18:48:14 +0100 Subject: erts: Reject duplicate keys for hamt in binary_to_term --- erts/emulator/beam/erl_map.c | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index eacdd0b6c3..3ccfc61b08 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -87,7 +87,7 @@ static Eterm hashmap_values(Process *p, Eterm map); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); static Eterm map_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size); -static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n); +static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys); static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); static Eterm hashmap_info(Process *p, Eterm node); @@ -419,7 +419,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { } factory.p = p; - res = hashmap_from_unsorted_array(&factory, hxns, size); + res = hashmap_from_unsorted_array(&factory, hxns, size, 0); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -462,7 +462,8 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { return res; } -Eterm erts_hashmap_from_array(ErtsHeapFactory* factory, Eterm *leafs, Uint n) { +Eterm erts_hashmap_from_array(ErtsHeapFactory* factory, Eterm *leafs, Uint n, + int reject_dupkeys) { Uint32 sw, hx; Uint ix; hxnode_t *hxns; @@ -481,7 +482,7 @@ Eterm erts_hashmap_from_array(ErtsHeapFactory* factory, Eterm *leafs, Uint n) { leafs += 2; } - res = hashmap_from_unsorted_array(factory, hxns, n); + res = hashmap_from_unsorted_array(factory, hxns, n, reject_dupkeys); erts_free(ERTS_ALC_T_TMP, (void *) hxns); @@ -523,7 +524,7 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n } factory.p = p; - res = hashmap_from_unsorted_array(&factory, hxns, sz); + res = hashmap_from_unsorted_array(&factory, hxns, sz, 0); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -532,7 +533,8 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n } static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory, - hxnode_t *hxns, Uint n) { + hxnode_t *hxns, Uint n, + int reject_dupkeys) { Uint jx = 0, ix = 0, lx, cx; Eterm res; @@ -566,7 +568,10 @@ static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory, while(ix < jx) { lx = ix; while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) { - if (hxns[ix].i > hxns[lx].i) { + if (reject_dupkeys) + return THE_NON_VALUE; + + if (hxns[ix].i > hxns[lx].i) { lx = ix; } ix++; @@ -1030,7 +1035,7 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { } factory.p = p; - res = hashmap_from_unsorted_array(&factory, hxns, n); + res = hashmap_from_unsorted_array(&factory, hxns, n, 0); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); @@ -1076,7 +1081,7 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) } factory.p = p; - res = hashmap_from_unsorted_array(&factory, hxns, n); + res = hashmap_from_unsorted_array(&factory, hxns, n, 0); erts_free(ERTS_ALC_T_TMP, (void *) hxns); ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); -- cgit v1.2.3 From 7478569d0a7d619d600816f3a75e56922d8ed428 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 10 Mar 2015 18:07:11 +0100 Subject: erts: Tweak over estimation of hashmap size for binary_to_term Strategy: Calculate an over estimation of heap size that will give such a low probability for overflow, that "it will not happen". Scary assumption 1: Uniformly distributed hash values. Scary assumption 2: Tree size is normally distributed (right?) --- erts/emulator/beam/erl_map.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 3ccfc61b08..5eafa69b06 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -2437,6 +2437,43 @@ int erts_validate_and_sort_map(map_t* mp) return 1; } +/* Really rough estimate of sqrt(x) + * Guaranteed not to be less than sqrt(x) + */ +static int int_sqrt_ceiling(Uint x) +{ + int n; + + if (x <= 2) + return x; + + n = erts_fit_in_bits_uint(x-1); + if (n & 1) { + /* Calc: sqrt(2^n) = 2^(n/2) * sqrt(2) ~= 2^(n/2) * 3 / 2 */ + return (1 << (n/2 - 1)) * 3; + } + else { + /* Calc: sqrt(2^n) = 2^(n/2) */ + return 1 << (n / 2); + } +} + +Uint hashmap_over_estimated_heap_size(Uint n) +{ + /* n is nr of key-value pairs. + Average nr of nodes is about n/3. + Standard deviation is about sqrt(n)/3. + Assuming normal probability distribution, + we overestimate nr of nodes by 14 std.devs, which gives a probability + for overrun of 1.0e-49 (same magnitude as a git SHA1 collision). + */ + Uint nodes = (n + int_sqrt_ceiling(n)*14) / 3; + return (n*2 + /* leaf cons cells */ + n + /* leaf list terms */ + nodes*2); /* headers + parent refs */ +} + + BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) { if (is_hashmap(BIF_ARG_1)) { BIF_RET(hashmap_info(BIF_P,BIF_ARG_1)); -- cgit v1.2.3 From 3fdd4046c4306256233984e289898f24324273f9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 10 Mar 2015 09:04:56 +0100 Subject: erts: Add hashmap_iterator_prev to maps --- erts/emulator/beam/erl_map.c | 45 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 5eafa69b06..65a31d3680 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1758,6 +1758,51 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) { } } +Eterm* hashmap_iterator_prev(ErtsWStack* s) { + Eterm node, *ptr, hdr; + Uint32 sz,i; + + for (;;) { + ASSERT(!WSTACK_ISEMPTY((*s))); + node = (Eterm) WSTACK_POP((*s)); + if (is_non_value(node)) { + return NULL; + } + switch (primary_tag(node)) { + case TAG_PRIMARY_LIST: + return list_val(node); + + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + case HAMT_SUBTAG_NODE_ARRAY: + ptr++; + i = 0; + while(i < 16) { WSTACK_PUSH((*s), (UWord)ptr[i++]); } + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + i = 0; + ptr++; + while(i < sz) { WSTACK_PUSH((*s), (UWord)ptr[i++]); } + break; + default: + erl_exit(1, "bad header"); + } + break; + + default: + erl_exit(1, "bad hamt node"); + } + } +} const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { Eterm *ptr, hdr; Eterm th[2]; -- cgit v1.2.3 From 27e57aa05354b743b735a41716c0e3af18f2843e Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 10 Mar 2015 19:03:19 +0100 Subject: erts: Refactor maps naming convention flatmap: Small map hashmap: Large map map: flatmap or hashmap --- erts/emulator/beam/erl_map.c | 196 +++++++++++++++++++++---------------------- 1 file changed, 98 insertions(+), 98 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 65a31d3680..ca43baf1a6 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -78,7 +78,7 @@ typedef struct { } hxnode_t; -static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB); +static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args); static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm hashmap_to_list(Process *p, Eterm map); @@ -101,11 +101,11 @@ static int hxnodecmpkey(hxnode_t* a, hxnode_t* b); */ BIF_RETTYPE map_size_1(BIF_ALIST_1) { - if (is_map(BIF_ARG_1)) { + if (is_flatmap(BIF_ARG_1)) { Eterm *hp; Uint hsz = 0; - map_t *mp = (map_t*)map_val(BIF_ARG_1); - Uint n = map_get_size(mp); + flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1); + Uint n = flatmap_get_size(mp); erts_bld_uint(NULL, &hsz, n); hp = HAlloc(BIF_P, hsz); @@ -128,15 +128,15 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) { /* maps:to_list/1 */ BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) { - if (is_map(BIF_ARG_1)) { + if (is_flatmap(BIF_ARG_1)) { Uint n; Eterm* hp; Eterm *ks,*vs, res, tup; - map_t *mp = (map_t*)map_val(BIF_ARG_1); + flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1); - ks = map_get_keys(mp); - vs = map_get_values(mp); - n = map_get_size(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); + n = flatmap_get_size(mp); hp = HAlloc(BIF_P, (2 + 3) * n); res = NIL; @@ -165,20 +165,20 @@ erts_maps_get(Eterm key, Eterm map) #endif { Uint32 hx; - if (is_map(map)) { + if (is_flatmap(map)) { Eterm *ks, *vs; - map_t *mp; + flatmap_t *mp; Uint n, i; - mp = (map_t *)map_val_rel(map, map_base); - n = map_get_size(mp); + mp = (flatmap_t *)flatmap_val_rel(map, map_base); + n = flatmap_get_size(mp); if (n == 0) { return NULL; } ks = (Eterm *)tuple_val_rel(mp->keys, map_base) + 1; - vs = map_get_values(mp); + vs = flatmap_get_values(mp); if (is_immed(key)) { for (i = 0; i < n; i++) { @@ -202,7 +202,7 @@ erts_maps_get(Eterm key, Eterm map) } BIF_RETTYPE maps_find_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { Eterm *hp, res; const Eterm *value; @@ -226,7 +226,7 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) { */ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { Eterm *hp; Eterm error; const Eterm *value; @@ -289,7 +289,7 @@ error: static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) { Eterm *kv, item = list; Eterm *hp, *thp,*vs, *ks, keys, res; - map_t *mp; + flatmap_t *mp; Uint unused_size = 0; Sint c = 0; Sint idx = 0; @@ -301,8 +301,8 @@ static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) { *hp++ = make_arityval(size); ks = hp; hp += size; - mp = (map_t*)hp; - res = make_map(mp); + mp = (flatmap_t*)hp; + res = make_flatmap(mp); hp += MAP_HEADER_SIZE; vs = hp; @@ -427,7 +427,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { if (hashmap_size(res) <= MAP_SMALL_MAP_LIMIT) { DECLARE_WSTACK(wstack); Eterm *kv, *ks, *vs; - map_t *mp; + flatmap_t *mp; Eterm keys; Uint n = hashmap_size(res); @@ -437,7 +437,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { *hp++ = make_arityval(n); ks = hp; hp += n; - mp = (map_t*)hp; + mp = (flatmap_t*)hp; hp += MAP_HEADER_SIZE; vs = hp; @@ -453,10 +453,10 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { } /* it cannot have multiple keys */ - erts_validate_and_sort_map(mp); + erts_validate_and_sort_flatmap(mp); DESTROY_WSTACK(wstack); - return make_map(mp); + return make_flatmap(mp); } return res; @@ -877,7 +877,7 @@ static int hxnodecmp(hxnode_t *a, hxnode_t *b) { /* maps:is_key/2 */ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { BIF_RET(erts_maps_get(BIF_ARG_1, BIF_ARG_2) ? am_true : am_false); } BIF_ERROR(BIF_P, BADARG); @@ -886,19 +886,19 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { /* maps:keys/1 */ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { - if (is_map(BIF_ARG_1)) { + if (is_flatmap(BIF_ARG_1)) { Eterm *hp, *ks, res = NIL; - map_t *mp; + flatmap_t *mp; Uint n; - mp = (map_t*)map_val(BIF_ARG_1); - n = map_get_size(mp); + mp = (flatmap_t*)flatmap_val(BIF_ARG_1); + n = flatmap_get_size(mp); if (n == 0) BIF_RET(res); hp = HAlloc(BIF_P, (2 * n)); - ks = map_get_keys(mp); + ks = flatmap_get_keys(mp); while(n--) { res = CONS(hp, ks[n], res); hp += 2; @@ -913,9 +913,9 @@ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { /* maps:merge/2 */ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_1)) { - if (is_map(BIF_ARG_2)) { - BIF_RET(map_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); + if (is_flatmap(BIF_ARG_1)) { + if (is_flatmap(BIF_ARG_2)) { + BIF_RET(flatmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); } else if (is_hashmap(BIF_ARG_2)) { /* Will always become a tree */ BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_1, BIF_ARG_2, 0)); @@ -923,7 +923,7 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) { } else if (is_hashmap(BIF_ARG_1)) { if (is_hashmap(BIF_ARG_2)) { BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); - } else if (is_map(BIF_ARG_2)) { + } else if (is_flatmap(BIF_ARG_2)) { /* Will always become a tree */ BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_2, BIF_ARG_1, 1)); } @@ -931,18 +931,18 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADARG); } -static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { +static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) { Eterm *hp,*thp; Eterm tup; Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2; - map_t *mp1,*mp2,*mp_new; + flatmap_t *mp1,*mp2,*mp_new; Uint n,n1,n2,i1,i2,need,unused_size=0; int c = 0; - mp1 = (map_t*)map_val(nodeA); - mp2 = (map_t*)map_val(nodeB); - n1 = map_get_size(mp1); - n2 = map_get_size(mp2); + mp1 = (flatmap_t*)flatmap_val(nodeA); + mp2 = (flatmap_t*)flatmap_val(nodeB); + n1 = flatmap_get_size(mp1); + n2 = flatmap_get_size(mp2); need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2); @@ -950,7 +950,7 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { thp = hp; tup = make_tuple(thp); ks = hp + 1; hp += 1 + n1 + n2; - mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE; + mp_new = (flatmap_t*)hp; hp += MAP_HEADER_SIZE; vs = hp; hp += n1 + n2; mp_new->thing_word = MAP_HEADER; @@ -958,10 +958,10 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { mp_new->keys = tup; i1 = 0; i2 = 0; - ks1 = map_get_keys(mp1); - vs1 = map_get_values(mp1); - ks2 = map_get_keys(mp2); - vs2 = map_get_values(mp2); + ks1 = flatmap_get_keys(mp1); + vs1 = flatmap_get_values(mp1); + ks2 = flatmap_get_keys(mp2); + vs2 = flatmap_get_values(mp2); while(i1 < n1 && i2 < n2) { c = CMP_TERM(ks1[i1],ks2[i2]); @@ -1018,8 +1018,8 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { hxnode_t *hxns; ErtsHeapFactory factory; - ks = map_get_keys(mp_new); - vs = map_get_values(mp_new); + ks = flatmap_get_keys(mp_new); + vs = flatmap_get_values(mp_new); hp = HAlloc(p, 2 * n); @@ -1045,12 +1045,12 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) { mp_new->size = n; - return make_map(mp_new); + return make_flatmap(mp_new); } static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) { Eterm *ks, *vs, *hp, res; - map_t *mp; + flatmap_t *mp; Uint n, i; hxnode_t *hxns; Uint32 sw, hx; @@ -1058,14 +1058,14 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) /* convert flat to tree */ - ASSERT(is_map(flat)); + ASSERT(is_flatmap(flat)); ASSERT(is_hashmap(tree)); - mp = (map_t*)map_val(flat); - n = map_get_size(mp); + mp = (flatmap_t*)flatmap_val(flat); + n = flatmap_get_size(mp); - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); hp = HAlloc(p, 2 * n); @@ -1343,24 +1343,24 @@ int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp) BIF_RETTYPE maps_new_0(BIF_ALIST_0) { Eterm* hp; Eterm tup; - map_t *mp; + flatmap_t *mp; hp = HAlloc(BIF_P, (MAP_HEADER_SIZE + 1)); tup = make_tuple(hp); *hp++ = make_arityval(0); - mp = (map_t*)hp; + mp = (flatmap_t*)hp; mp->thing_word = MAP_HEADER; mp->size = 0; mp->keys = tup; - BIF_RET(make_map(mp)); + BIF_RET(make_flatmap(mp)); } /* maps:put/3 */ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { - if (is_map(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { + if (is_flatmap(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3)); } BIF_ERROR(BIF_P, BADARG); @@ -1370,23 +1370,23 @@ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { Uint32 hx; - if (is_map(map)) { + if (is_flatmap(map)) { Sint n; Uint need; Eterm *hp_start; Eterm *thp, *mhp; Eterm *ks, *vs, tup; - map_t *mp = (map_t*)map_val(map); + flatmap_t *mp = (flatmap_t*)flatmap_val(map); - n = map_get_size(mp); + n = flatmap_get_size(mp); if (n == 0) { *res = map; return 1; } - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); /* Assume key exists. * Release allocated if it didn't. @@ -1401,7 +1401,7 @@ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { tup = make_tuple(thp); *thp++ = make_arityval(n - 1); - *res = make_map(mhp); + *res = make_flatmap(mhp); *mhp++ = MAP_HEADER; *mhp++ = n - 1; *mhp++ = tup; @@ -1451,7 +1451,7 @@ found_key: } BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { - if (is_map(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { Eterm res; if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) { BIF_RET(res); @@ -1462,18 +1462,18 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) { Uint32 hx; - if (is_map(map)) { + if (is_flatmap(map)) { Sint n,i; Eterm* hp,*shp; Eterm *ks,*vs; - map_t *mp = (map_t*)map_val(map); + flatmap_t *mp = (flatmap_t*)flatmap_val(map); - if ((n = map_get_size(mp)) == 0) { + if ((n = flatmap_get_size(mp)) == 0) { return 0; } - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); /* only allocate for values, * assume key-tuple will be intact @@ -1511,7 +1511,7 @@ found_key: vs++; if (++i < n) sys_memcpy(hp, vs, (n - i)*sizeof(Eterm)); - *res = make_map(shp); + *res = make_flatmap(shp); return 1; } @@ -1527,21 +1527,21 @@ found_key: Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { Uint32 hx; Eterm res; - if (is_map(map)) { + if (is_flatmap(map)) { Sint n,i; Sint c = 0; Eterm* hp, *shp; Eterm *ks, *vs, tup; - map_t *mp = (map_t*)map_val(map); + flatmap_t *mp = (flatmap_t*)flatmap_val(map); - n = map_get_size(mp); + n = flatmap_get_size(mp); if (n == 0) { hp = HAlloc(p, MAP_HEADER_SIZE + 1 + 2); tup = make_tuple(hp); *hp++ = make_arityval(1); *hp++ = key; - res = make_map(hp); + res = make_flatmap(hp); *hp++ = MAP_HEADER; *hp++ = 1; *hp++ = tup; @@ -1550,8 +1550,8 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { return res; } - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); /* only allocate for values, * assume key-tuple will be intact @@ -1559,7 +1559,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { hp = HAlloc(p, MAP_HEADER_SIZE + n); shp = hp; /* save hp, used if optimistic update fails */ - res = make_map(hp); + res = make_flatmap(hp); *hp++ = MAP_HEADER; *hp++ = n; *hp++ = mp->keys; @@ -1593,8 +1593,8 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { if (n >= MAP_SMALL_MAP_LIMIT) { HRelease(p, shp + MAP_HEADER_SIZE + n, shp); - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); res = erts_hashmap_from_ks_and_vs_extra(p,ks,vs,n,key,value); @@ -1608,13 +1608,13 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { *shp++ = make_arityval(n+1); hp = HAlloc(p, 3 + n + 1); - res = make_map(hp); + res = make_flatmap(hp); *hp++ = MAP_HEADER; *hp++ = n + 1; *hp++ = tup; - ks = map_get_keys(mp); - vs = map_get_values(mp); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); ASSERT(n >= 0); @@ -1653,7 +1653,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { /* maps:update/3 */ BIF_RETTYPE maps_update_3(BIF_ALIST_3) { - if (is_map(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { + if (is_flatmap(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { Eterm res; if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) { BIF_RET(res); @@ -1666,19 +1666,19 @@ BIF_RETTYPE maps_update_3(BIF_ALIST_3) { /* maps:values/1 */ BIF_RETTYPE maps_values_1(BIF_ALIST_1) { - if (is_map(BIF_ARG_1)) { + if (is_flatmap(BIF_ARG_1)) { Eterm *hp, *vs, res = NIL; - map_t *mp; + flatmap_t *mp; Uint n; - mp = (map_t*)map_val(BIF_ARG_1); - n = map_get_size(mp); + mp = (flatmap_t*)flatmap_val(BIF_ARG_1); + n = flatmap_get_size(mp); if (n == 0) BIF_RET(res); hp = HAlloc(BIF_P, (2 * n)); - vs = map_get_values(mp); + vs = flatmap_get_values(mp); while(n--) { res = CONS(hp, vs[n], res); hp += 2; @@ -2257,7 +2257,7 @@ unroll: if (n <= MAP_SMALL_MAP_LIMIT) { DECLARE_WSTACK(wstack); Eterm *kv, *ks, *vs; - map_t *mp; + flatmap_t *mp; Eterm keys; DESTROY_ESTACK(stack); @@ -2268,7 +2268,7 @@ unroll: *hp++ = make_arityval(n); ks = hp; hp += n; - mp = (map_t*)hp; + mp = (flatmap_t*)hp; hp += MAP_HEADER_SIZE; vs = hp; @@ -2286,10 +2286,10 @@ unroll: } /* it cannot have multiple keys */ - erts_validate_and_sort_map(mp); + erts_validate_and_sort_flatmap(mp); DESTROY_WSTACK(wstack); - return make_map(mp); + return make_flatmap(mp); } hp = HAlloc(p, size); @@ -2451,11 +2451,11 @@ not_found: } -int erts_validate_and_sort_map(map_t* mp) +int erts_validate_and_sort_flatmap(flatmap_t* mp) { - Eterm *ks = map_get_keys(mp); - Eterm *vs = map_get_values(mp); - Uint sz = map_get_size(mp); + Eterm *ks = flatmap_get_keys(mp); + Eterm *vs = flatmap_get_values(mp); + Uint sz = flatmap_get_size(mp); Uint ix,jx; Eterm tmp; int c; @@ -2533,8 +2533,8 @@ BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) { */ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) { - if (is_map(BIF_ARG_1)) { - map_t *mp = (map_t*)map_val(BIF_ARG_1); + if (is_flatmap(BIF_ARG_1)) { + flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1); BIF_RET(mp->keys); } BIF_ERROR(BIF_P, BADARG); -- cgit v1.2.3 From 2fadbefc264d33da526ec61cffc9847f724d8d92 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 10 Mar 2015 19:57:07 +0100 Subject: erts: Reintroduce is_map macro as shorthand for is_flatmap || is_hashmap --- erts/emulator/beam/erl_map.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index ca43baf1a6..16293668ad 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -202,7 +202,7 @@ erts_maps_get(Eterm key, Eterm map) } BIF_RETTYPE maps_find_2(BIF_ALIST_2) { - if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_map(BIF_ARG_2)) { Eterm *hp, res; const Eterm *value; @@ -226,7 +226,7 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) { */ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { - if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_map(BIF_ARG_2)) { Eterm *hp; Eterm error; const Eterm *value; @@ -877,7 +877,7 @@ static int hxnodecmp(hxnode_t *a, hxnode_t *b) { /* maps:is_key/2 */ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { - if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_map(BIF_ARG_2)) { BIF_RET(erts_maps_get(BIF_ARG_1, BIF_ARG_2) ? am_true : am_false); } BIF_ERROR(BIF_P, BADARG); @@ -1360,7 +1360,7 @@ BIF_RETTYPE maps_new_0(BIF_ALIST_0) { /* maps:put/3 */ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { - if (is_flatmap(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { + if (is_map(BIF_ARG_3)) { BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3)); } BIF_ERROR(BIF_P, BADARG); @@ -1451,7 +1451,7 @@ found_key: } BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { - if (is_flatmap(BIF_ARG_2) || is_hashmap(BIF_ARG_2)) { + if (is_map(BIF_ARG_2)) { Eterm res; if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) { BIF_RET(res); @@ -1653,7 +1653,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { /* maps:update/3 */ BIF_RETTYPE maps_update_3(BIF_ALIST_3) { - if (is_flatmap(BIF_ARG_3) || is_hashmap(BIF_ARG_3)) { + if (is_map(BIF_ARG_3)) { Eterm res; if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) { BIF_RET(res); -- cgit v1.2.3 From c8f731bfec32a34d49304ea78017b63af053eecd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Wed, 11 Mar 2015 18:45:12 +0100 Subject: erts, kernel: Fix erts_debug:size/1 for hashmaps This commit introduces two BIFs: * erts_internal:map_type/1 * erts_internal:map_hashmap_children/1 erts_internal:map_hashmap_children/1 is only intended for use within erts_debug:size/1 since the internal hashmap node is not allowed to leak anywhere. --- erts/emulator/beam/erl_map.c | 75 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 75 insertions(+) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 16293668ad..0e24f2e1b1 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -2540,6 +2540,81 @@ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADARG); } +/* + * erts_internal:map_type/1 + * + * Used in erts_debug:size/1 + */ + +BIF_RETTYPE erts_internal_map_type_1(BIF_ALIST_1) { + DECL_AM(hashmap); + DECL_AM(hashmap_node); + DECL_AM(flatmap); + if (is_flatmap(BIF_ARG_1)) { + BIF_RET(AM_flatmap); + } else if (is_hashmap(BIF_ARG_1)) { + Eterm hdr = *(boxed_val(BIF_ARG_1)); + ASSERT(is_header(hdr)); + switch (hdr & _HEADER_MAP_SUBTAG_MASK) { + 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: + erl_exit(1, "bad header"); + } + } + BIF_ERROR(BIF_P, BADARG); +} + +/* + * erts_internal:map_hashmap_children/1 + * + * Used in erts_debug:size/1 + */ + +BIF_RETTYPE erts_internal_map_hashmap_children_1(BIF_ALIST_1) { + if (is_hashmap(BIF_ARG_1)) { + Eterm node = BIF_ARG_1; + Eterm *ptr, hdr, *hp, res = NIL; + Uint sz = 0; + ptr = boxed_val(node); + hdr = *ptr; + + 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; + break; + case HAMT_SUBTAG_HEAD_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ptr += 2; + break; + case HAMT_SUBTAG_HEAD_ARRAY: + sz = 16; + ptr += 2; + break; + default: + erl_exit(1, "bad header\r\n"); + break; + } + ASSERT(sz < 17); + hp = HAlloc(BIF_P, 2*sz); + while(sz--) { res = CONS(hp, *ptr++, res); hp += 2; } + BIF_RET(res); + } + BIF_ERROR(BIF_P, BADARG); +} + + static Eterm hashmap_info(Process *p, Eterm node) { Eterm *hp; Eterm res = NIL, info = NIL; -- cgit v1.2.3 From 81551dd13167b9c4458c4fee7ce08e152f9f5273 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 11 Mar 2015 20:39:08 +0100 Subject: erts: Make hashmap iterator more flexible to allow mixing of 'next' and 'prev' operations. --- erts/emulator/beam/erl_map.c | 174 +++++++++++++++++++++++++------------------ 1 file changed, 102 insertions(+), 72 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 0e24f2e1b1..00ed968295 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -445,7 +445,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) { mp->size = n; mp->keys = keys; - hashmap_iterator_init(&wstack, res); + hashmap_iterator_init(&wstack, res, 0); while ((kv=hashmap_iterator_next(&wstack)) != NULL) { *ks++ = CAR(kv); @@ -1697,7 +1697,7 @@ static Eterm hashmap_to_list(Process *p, Eterm node) { Eterm res = NIL; hp = HAlloc(p, hashmap_size(node) * (2 + 3)); - hashmap_iterator_init(&stack, node); + hashmap_iterator_init(&stack, node, 0); while ((kv=hashmap_iterator_next(&stack)) != NULL) { Eterm tup = TUPLE2(hp, CAR(kv), CDR(kv)); hp += 3; @@ -1708,14 +1708,30 @@ static Eterm hashmap_to_list(Process *p, Eterm node) { return res; } -void hashmap_iterator_init(ErtsWStack* s, Eterm node) { - WSTACK_PUSH((*s), (UWord)THE_NON_VALUE); /* end marker */ - WSTACK_PUSH((*s), (UWord)node); +void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) { + Eterm hdr = *hashmap_val(node); + Uint sz; + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + sz = 16; + break; + case HAMT_SUBTAG_HEAD_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + break; + default: + erl_exit(1, "bad header"); + } + + WSTACK_PUSH3((*s), (UWord)THE_NON_VALUE, /* end marker */ + (UWord)(!reverse ? 0 : sz+1), + (UWord)node); } Eterm* hashmap_iterator_next(ErtsWStack* s) { Eterm node, *ptr, hdr; Uint32 sz; + Uint idx; for (;;) { ASSERT(!WSTACK_ISEMPTY((*s))); @@ -1723,44 +1739,50 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) { if (is_non_value(node)) { return NULL; } - switch (primary_tag(node)) { - case TAG_PRIMARY_LIST: - return list_val(node); - - case TAG_PRIMARY_BOXED: - ptr = boxed_val(node); - hdr = *ptr; - ASSERT(is_header(hdr)); - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - case HAMT_SUBTAG_NODE_ARRAY: - ptr++; - sz = 16; - while(sz--) { WSTACK_PUSH((*s), (UWord)ptr[sz]); } - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - case HAMT_SUBTAG_NODE_BITMAP: - sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz < 17); - ptr++; - while(sz--) { WSTACK_PUSH((*s), (UWord)ptr[sz]); } - break; - default: - erl_exit(1, "bad header"); - } - break; + idx = (Uint) WSTACK_POP((*s)); + for (;;) { + ASSERT(is_boxed(node)); + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + 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: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + break; + default: + erl_exit(1, "bad header"); + } - default: - erl_exit(1, "bad hamt node"); - } + idx++; + + if (idx <= sz) { + WSTACK_PUSH2((*s), (UWord)idx, (UWord)node); + + if (is_list(ptr[idx])) { + return list_val(ptr[idx]); + } + ASSERT(is_boxed(ptr[idx])); + node = ptr[idx]; + idx = 0; + } + else + break; /* and pop parent node */ + } } } Eterm* hashmap_iterator_prev(ErtsWStack* s) { Eterm node, *ptr, hdr; - Uint32 sz,i; + Uint32 sz; + Uint idx; for (;;) { ASSERT(!WSTACK_ISEMPTY((*s))); @@ -1768,41 +1790,49 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) { if (is_non_value(node)) { return NULL; } - switch (primary_tag(node)) { - case TAG_PRIMARY_LIST: - return list_val(node); - - case TAG_PRIMARY_BOXED: - ptr = boxed_val(node); - hdr = *ptr; - ASSERT(is_header(hdr)); - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - case HAMT_SUBTAG_NODE_ARRAY: - ptr++; - i = 0; - while(i < 16) { WSTACK_PUSH((*s), (UWord)ptr[i++]); } - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - case HAMT_SUBTAG_NODE_BITMAP: - sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz < 17); - i = 0; - ptr++; - while(i < sz) { WSTACK_PUSH((*s), (UWord)ptr[i++]); } - break; - default: - erl_exit(1, "bad header"); - } - break; + idx = (Uint) WSTACK_POP((*s)); + for (;;) { + ASSERT(is_boxed(node)); + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + 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: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + break; + default: + erl_exit(1, "bad header"); + } - default: - erl_exit(1, "bad hamt node"); - } + if (idx > sz) + idx = sz; + else + idx--; + + if (idx >= 1) { + WSTACK_PUSH2((*s), (UWord)idx, (UWord)node); + + if (is_list(ptr[idx])) { + return list_val(ptr[idx]); + } + ASSERT(is_boxed(ptr[idx])); + node = ptr[idx]; + idx = 17; + } + else + break; /* and pop parent node */ + } } } + const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { Eterm *ptr, hdr; Eterm th[2]; @@ -2135,7 +2165,7 @@ static Eterm hashmap_keys(Process* p, Eterm node) { root = (hashmap_head_t*) boxed_val(node); hp = HAlloc(p, root->size * 2); - hashmap_iterator_init(&stack, node); + hashmap_iterator_init(&stack, node, 0); while ((kv=hashmap_iterator_next(&stack)) != NULL) { res = CONS(hp, CAR(kv), res); hp += 2; @@ -2152,7 +2182,7 @@ static Eterm hashmap_values(Process* p, Eterm node) { root = (hashmap_head_t*) boxed_val(node); hp = HAlloc(p, root->size * 2); - hashmap_iterator_init(&stack, node); + hashmap_iterator_init(&stack, node, 0); while ((kv=hashmap_iterator_next(&stack)) != NULL) { res = CONS(hp, CDR(kv), res); hp += 2; @@ -2276,7 +2306,7 @@ unroll: mp->size = n; mp->keys = keys; - hashmap_iterator_init(&wstack, map); + hashmap_iterator_init(&wstack, map, 0); while ((kv=hashmap_iterator_next(&wstack)) != NULL) { if (EQ(CAR(kv),key)) -- cgit v1.2.3 From b398819d59863db76fc2ce2f0c1584254e38f3bb Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 12 Mar 2015 21:03:10 +0100 Subject: erts: Fix windows bug in hashmap_info undefined symbol 'MAX' --- erts/emulator/beam/erl_map.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 00ed968295..b7f07fa6c4 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -2670,7 +2670,8 @@ static Eterm hashmap_info(Process *p, Eterm node) { do { node = ESTACK_POP(stack); clvl = ESTACK_POP(stack); - lvl = MAX(lvl,clvl); + if (lvl < clvl) + lvl = clvl; switch(primary_tag(node)) { case TAG_PRIMARY_LIST: nleaf++; -- cgit v1.2.3 From 59f1846249fbbb76e786d1e73e9be5c72a41fefb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Fri, 13 Mar 2015 10:09:33 +0100 Subject: erts: Restrict GCC intrinsics by compiler version Intrinsics __builtin_clz and __builtin_popcount are only valid on GCC version 3.4 and above. --- erts/emulator/beam/erl_map.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index b7f07fa6c4..964c09e906 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -2768,7 +2768,7 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) /* implementation of builtin emulations */ -#if !defined(__GNUC__) +#if !ERTS_AT_LEAST_GCC_VSN__(3, 4, 0) /* Count leading zeros emulation */ Uint32 hashmap_clz(Uint32 x) { Uint32 y; @@ -2780,6 +2780,7 @@ Uint32 hashmap_clz(Uint32 x) { y = x >> 1; if (y != 0) return n - 2; return n - x; } + const Uint32 SK5 = 0x55555555, SK3 = 0x33333333; const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF; -- cgit v1.2.3 From 401e2544564526039ac87b3ffe79eb8af30b37b4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 16 Mar 2015 11:06:44 +0100 Subject: erts: Ensure halfword has correct temp-heap for maps --- erts/emulator/beam/erl_map.c | 139 +++++++++++++++++++++++-------------------- 1 file changed, 74 insertions(+), 65 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 964c09e906..4183b532a9 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1835,72 +1835,77 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) { const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { Eterm *ptr, hdr; - Eterm th[2]; Uint ix,slot, lvl = 0; Uint32 hval,bp; + DeclareTmpHeapNoproc(th,2); + UseTmpHeapNoproc(2); for (;;) { - switch(primary_tag(node)) { - case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ - ptr = list_val(node); - if (EQ(CAR(ptr), key)) { - return &(CDR(ptr)); - } - return NULL; - 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); - node = ptr[ix+1]; - break; - case HAMT_SUBTAG_HEAD_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - 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)); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+1]; - break; - } - /* not occupied */ - return NULL; - case HAMT_SUBTAG_HEAD_BITMAP: - hval = MAP_HEADER_VAL(hdr); - ix = hashmap_index(hx); - bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+2]; - break; - } - /* not occupied */ - return NULL; - 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; - } + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ + ptr = list_val(node); + UnUseTmpHeapNoproc(2); + if (EQ(CAR(ptr), key)) { + return &(CDR(ptr)); + } + return NULL; + 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); + node = ptr[ix+1]; + break; + case HAMT_SUBTAG_HEAD_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(th,hx,lvl,key); + 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)); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+1]; + break; + } + /* not occupied */ + UnUseTmpHeapNoproc(2); + return NULL; + case HAMT_SUBTAG_HEAD_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+2]; + break; + } + /* not occupied */ + UnUseTmpHeapNoproc(2); + return NULL; + 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; + } } + UnUseTmpHeapNoproc(2); return NULL; } @@ -2049,11 +2054,14 @@ unroll: Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, Uint *update_size, ErtsEStack *sp) { - Eterm node, fake, *ptr, hdr; + Eterm node, *ptr, hdr; Eterm res; Eterm *nhp = NULL; Uint32 ix, cix, bp, hval; Uint slot, n; + /* Needed for halfword */ + DeclareTmpHeapNoproc(fake,1); + UseTmpHeapNoproc(1); res = CONS(hp, key, value); hp += 2; @@ -2077,8 +2085,8 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, break; case TAG_PRIMARY_HEADER: /* subnodes, fake it */ - fake = node; - node = make_boxed(&fake); + *fake = node; + node = make_boxed(fake); case TAG_PRIMARY_BOXED: ptr = boxed_val(node); hdr = *ptr; @@ -2154,7 +2162,8 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, } while(!ESTACK_ISEMPTY(*sp)); - return res; + UnUseTmpHeapNoproc(1); + return res; } static Eterm hashmap_keys(Process* p, Eterm node) { -- cgit v1.2.3 From feffe2deac13ad61477c7ecf63342815c750bfe5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 17 Mar 2015 15:44:07 +0100 Subject: erts: Ensure maps uses _rel functions in halfword --- erts/emulator/beam/erl_map.c | 19 +++++++++++++------ 1 file changed, 13 insertions(+), 6 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 4183b532a9..bd6da0a6f1 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -165,7 +165,7 @@ erts_maps_get(Eterm key, Eterm map) #endif { Uint32 hx; - if (is_flatmap(map)) { + if (is_flatmap_rel(map, map_base)) { Eterm *ks, *vs; flatmap_t *mp; Uint n, i; @@ -189,16 +189,16 @@ erts_maps_get(Eterm key, Eterm map) } for (i = 0; i < n; i++) { - if (eq_rel(ks[i], NULL, key, map_base)) { + if (eq_rel(ks[i], map_base, key, NULL)) { return &vs[i]; } } return NULL; } - ASSERT(is_hashmap(map)); + ASSERT(is_hashmap_rel(map, map_base)); hx = hashmap_make_hash(key); - return erts_hashmap_get(hx, key, map); + return erts_hashmap_get_rel(hx, key, map, map_base); } BIF_RETTYPE maps_find_2(BIF_ALIST_2) { @@ -1833,7 +1833,13 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) { } } -const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { +const Eterm * +#if HALFWORD_HEAP +erts_hashmap_get_rel(Uint32 hx, Eterm key, Eterm node, Eterm *map_base) +#else +erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) +#endif +{ Eterm *ptr, hdr; Uint ix,slot, lvl = 0; Uint32 hval,bp; @@ -1845,7 +1851,8 @@ const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ ptr = list_val(node); UnUseTmpHeapNoproc(2); - if (EQ(CAR(ptr), key)) { + + if (eq_rel(CAR(ptr), map_base, key, NULL)) { return &(CDR(ptr)); } return NULL; -- cgit v1.2.3