aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--erts/emulator/beam/bif.tab3
-rw-r--r--erts/emulator/beam/erl_hashmap.c133
-rw-r--r--erts/emulator/beam/erl_hashmap.h10
-rw-r--r--erts/emulator/beam/erl_map.c115
-rw-r--r--erts/emulator/beam/erl_map.h7
5 files changed, 123 insertions, 145 deletions
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 *