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/bif.tab | 3 - erts/emulator/beam/erl_hashmap.c | 133 +-------------------------------------- erts/emulator/beam/erl_hashmap.h | 10 +-- erts/emulator/beam/erl_map.c | 115 ++++++++++++++++++++++++++++++++- erts/emulator/beam/erl_map.h | 7 +++ 5 files changed, 123 insertions(+), 145 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 8606a41c7b..6bd9291d34 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -622,12 +622,9 @@ bif hashmap:update/3 bif hashmap:remove/2 bif hashmap:info/1 bif hashmap:from_list/1 -bif hashmap:to_list/1 bif hashmap:new/0 bif hashmap:is_key/2 -bif hashmap:keys/1 bif erlang:is_hashmap/1 -bif hashmap:values/1 bif hashmap:merge/2 # diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c index 3f6e12cdd8..064ae73acd 100644 --- a/erts/emulator/beam/erl_hashmap.c +++ b/erts/emulator/beam/erl_hashmap.c @@ -79,9 +79,6 @@ typedef struct { static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); static Eterm hashmap_from_list(Process *p, 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); static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n); @@ -135,14 +132,6 @@ BIF_RETTYPE hashmap_update_3(BIF_ALIST_3) { /* hashmap:to_list/1 */ -BIF_RETTYPE hashmap_to_list_1(BIF_ALIST_1) { - if (is_hashmap(BIF_ARG_1)) { - return hashmap_to_list(BIF_P, BIF_ARG_1); - } - - BIF_ERROR(BIF_P, BADARG); -} - /* hashmap:from_list/1 */ BIF_RETTYPE hashmap_from_list_1(BIF_ALIST_1) { @@ -222,25 +211,10 @@ BIF_RETTYPE hashmap_is_key_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADARG); } -/* hashmap:keys/1 - */ - -BIF_RETTYPE hashmap_keys_1(BIF_ALIST_1) { - if (is_hashmap(BIF_ARG_1)) { - BIF_RET(hashmap_keys(BIF_P, BIF_ARG_1)); - } - BIF_ERROR(BIF_P, BADARG); -} +/* hashmap:keys/1 */ -/* hashmap:keys/1 - */ -BIF_RETTYPE hashmap_values_1(BIF_ALIST_1) { - if (is_hashmap(BIF_ARG_1)) { - BIF_RET(hashmap_values(BIF_P, BIF_ARG_1)); - } - BIF_ERROR(BIF_P, BADARG); -} +/* hashmap:values/1 */ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) { if (is_hashmap(BIF_ARG_1) && is_hashmap(BIF_ARG_2)) { @@ -1448,109 +1422,6 @@ recurse: 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_to_list(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 + 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; -} - -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; -} - static int hash_cmp(Uint32 ha, Uint32 hb) { int i; diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h index b5fbc636e6..5a9aa05f61 100644 --- a/erts/emulator/beam/erl_hashmap.h +++ b/erts/emulator/beam/erl_hashmap.h @@ -25,9 +25,6 @@ #include "erl_term.h" Eterm erts_hashmap_get(Eterm key, Eterm map); -struct ErtsWStack_; -void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node); -Eterm* hashmap_iterator_next(struct ErtsWStack_* s); int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp); Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n); @@ -46,18 +43,13 @@ Uint32 hashmap_bitcount(Uint32 x); * node :: leaf | array | bitmap * head */ - -/* the head-node is a bitmap or array with an untagged size */ - typedef struct hashmap_head_s { Eterm thing_word; Uint size; Eterm items[1]; } hashmap_head_t; -#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) -#define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE)) - + /* thing_word tagscheme * Need two bits for map subtags 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); diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index 2e02ca4677..c104e08e27 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -42,8 +42,12 @@ typedef struct map_s { * ----------- */ +/* the head-node is a bitmap or array with an untagged size */ +#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) +#define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE)) + /* erl_term.h stuff */ #define make_map(x) make_boxed((Eterm*)(x)) #define make_map_rel(x, BASE) make_boxed_rel((Eterm*)(x),(BASE)) @@ -62,10 +66,13 @@ typedef struct map_s { #define MAP_HEADER _make_header(1,_TAG_HEADER_MAP) #define MAP_HEADER_SIZE (sizeof(map_t) / sizeof(Eterm)) +struct ErtsWStack_; Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map); int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res); int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res); int erts_validate_and_sort_map(map_t* map); +void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node); +Eterm* hashmap_iterator_next(struct ErtsWStack_* s); #if HALFWORD_HEAP const Eterm * -- cgit v1.2.3