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/bif.tab | 3 - erts/emulator/beam/erl_hashmap.c | 121 +-------------------------------------- erts/emulator/beam/erl_map.c | 97 +++++++++++++++++++++++++++++++ erts/emulator/beam/erl_map.h | 7 +++ 4 files changed, 105 insertions(+), 123 deletions(-) diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index f7f6eb9213..5b0f90d418 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -616,14 +616,11 @@ bif erlang:get_keys/0 # Hash Array Mappped Trie bif hashmap:put/3 -bif hashmap:get/2 -bif hashmap:find/2 bif hashmap:update/3 bif hashmap:remove/2 bif hashmap:info/1 bif hashmap:from_list/1 bif hashmap:new/0 -bif hashmap:is_key/2 bif hashmap:merge/2 # diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c index e51767146e..7e0e7fde04 100644 --- a/erts/emulator/beam/erl_hashmap.c +++ b/erts/emulator/beam/erl_hashmap.c @@ -42,19 +42,13 @@ #include "error.h" #include "bif.h" +#include "erl_map.h" #include "erl_hashmap.h" #ifndef DECL_AM #define DECL_AM(S) Eterm AM_ ## S = am_atom_put(#S, sizeof(#S) - 1) #endif -#define hashmap_make_hash(Key) make_hash_vsn(Key, 3) - -#define hashmap_restore_hash(Heap,Lvl,Key) \ - (((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7))) -#define hashmap_shift_hash(Heap,Hx,Lvl,Key) \ - (((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key))) - #if 0 static char *format_binary(Uint64 x, char *b) { int z; @@ -76,7 +70,6 @@ typedef struct { Eterm val; } hxnode_t; -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_merge(Process *p, Eterm nodeA, Eterm nodeB); @@ -143,40 +136,8 @@ BIF_RETTYPE hashmap_from_list_1(BIF_ALIST_1) { } /* hashmap:get/2 */ -BIF_RETTYPE hashmap_get_2(BIF_ALIST_2) { - 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); -} - /* hashmap:find/2 */ -BIF_RETTYPE hashmap_find_2(BIF_ALIST_2) { - 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); -} - - /* hashmap:remove/2 */ BIF_RETTYPE hashmap_remove_2(BIF_ALIST_2) { @@ -193,18 +154,8 @@ BIF_RETTYPE hashmap_remove_2(BIF_ALIST_2) { /* hashmap:is_key/2 */ -BIF_RETTYPE hashmap_is_key_2(BIF_ALIST_2) { - if (is_hashmap(BIF_ARG_1)) { - 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); -} - /* hashmap:keys/1 */ - /* hashmap:values/1 */ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) { @@ -216,76 +167,6 @@ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) { /* impl. */ -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_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update) { 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; diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index c104e08e27..48bc316e3b 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -47,6 +47,13 @@ typedef struct map_s { #define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) #define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE)) +#define hashmap_make_hash(Key) make_hash2(Key) + +#define hashmap_restore_hash(Heap,Lvl,Key) \ + (((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7))) +#define hashmap_shift_hash(Heap,Hx,Lvl,Key) \ + (((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key))) + /* erl_term.h stuff */ #define make_map(x) make_boxed((Eterm*)(x)) -- cgit v1.2.3