aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
authorBjörn-Egil Dahlberg <[email protected]>2015-02-23 11:48:46 +0100
committerBjörn-Egil Dahlberg <[email protected]>2015-03-12 19:15:26 +0100
commitf659c631f33ad86e7532c7198bbce6d7e07fe1dd (patch)
tree017d34e85d8e65b6b1bfe521404c8dd45495d312 /erts/emulator
parent7da662fb9eb519625b3833fec34419c32620f041 (diff)
downloadotp-f659c631f33ad86e7532c7198bbce6d7e07fe1dd.tar.gz
otp-f659c631f33ad86e7532c7198bbce6d7e07fe1dd.tar.bz2
otp-f659c631f33ad86e7532c7198bbce6d7e07fe1dd.zip
erts: Move hashmap:get/2, find/2 and is_key/2 to maps
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/bif.tab3
-rw-r--r--erts/emulator/beam/erl_hashmap.c121
-rw-r--r--erts/emulator/beam/erl_map.c97
-rw-r--r--erts/emulator/beam/erl_map.h7
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);
@@ -182,6 +183,20 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) {
}
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))