aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-01-27 16:32:37 +0100
committerBjörn-Egil Dahlberg <[email protected]>2015-03-12 19:15:23 +0100
commit8db065e5f6c07904db0c63175c906334e2eb5c59 (patch)
tree0c4358a4b0816edd1a33aa7e7ced7248a9ba42d3 /erts/emulator/beam
parent85c8e9c956ac7f2fa15abe56a513a2d97839af23 (diff)
downloadotp-8db065e5f6c07904db0c63175c906334e2eb5c59.tar.gz
otp-8db065e5f6c07904db0c63175c906334e2eb5c59.tar.bz2
otp-8db065e5f6c07904db0c63175c906334e2eb5c59.zip
erts: Rewrite hashmap:to_list, keys and values
to use an iterator instead of foreach with callback. Will be easier to make yielding.
Diffstat (limited to 'erts/emulator/beam')
-rw-r--r--erts/emulator/beam/erl_hashmap.c175
1 files changed, 86 insertions, 89 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 4ca0877385..2e3a4b8982 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -73,12 +73,6 @@ 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[]);
-typedef struct {
- Eterm* hp;
- Eterm res;
-}hashmap_doer_state;
-typedef void hashmap_doer(Eterm*, hashmap_doer_state*);
-static void hashmap_do_foreach(Eterm node, hashmap_doer* fptr, hashmap_doer_state*);
/* hashmap:new/0 */
@@ -798,26 +792,6 @@ not_found:
return res;
}
-static void hashmap_to_list_doer(Eterm* kv, hashmap_doer_state* sp);
-
-static Eterm hashmap_to_list(Process *p, Eterm node) {
- hashmap_head_t* root;
- hashmap_doer_state state;
-
- root = (hashmap_head_t*) boxed_val(node);
- state.hp = HAlloc(p, root->size * (2 + 3));
- state.res = NIL;
- hashmap_do_foreach(node, hashmap_to_list_doer, &state);
- return state.res;
-}
-
-static void hashmap_to_list_doer(Eterm* kv, hashmap_doer_state* sp) {
- Eterm tup = TUPLE2(sp->hp, CAR(kv), CDR(kv));
- sp->hp += 3;
- sp->res = CONS(sp->hp, tup, sp->res);
- sp->hp += 2;
-}
-
#define HALLOC_EXTRA 200
static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
@@ -1035,84 +1009,107 @@ recurse:
return res;
}
-static void hashmap_do_foreach(Eterm node, hashmap_doer* fptr,
- hashmap_doer_state* farg) {
- Eterm *ptr, hdr;
- Uint sz;
- DECLARE_ESTACK(stack);
+static void hashmap_iterator_init(ErtsWStack* s, Eterm node) {
+ WSTACK_PUSH((*s), (UWord)THE_NON_VALUE); /* end marker */
+ WSTACK_PUSH((*s), (UWord)node);
+}
- ESTACK_PUSH(stack, node);
- do {
- node = ESTACK_POP(stack);
- switch(primary_tag(node)) {
- case TAG_PRIMARY_LIST:
- ptr = list_val(node);
- (*fptr)(ptr, farg); /* Do! */
- break;
- 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--) { ESTACK_PUSH(stack, 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--) { ESTACK_PUSH(stack, ptr[sz]); }
- break;
- default:
- erl_exit(1, "bad header\r\n");
- break;
- }
- }
- } while(!ESTACK_ISEMPTY(stack));
+static Eterm* hashmap_iterator_next(ErtsWStack* s) {
+ Eterm node, *ptr, hdr;
+ Uint32 sz;
- DESTROY_ESTACK(stack);
+ 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 void hashmap_keys_doer(Eterm* kv, hashmap_doer_state*);
-
-static Eterm hashmap_keys(Process* p, Eterm node) {
+static Eterm hashmap_to_list(Process *p, Eterm node) {
+ DECLARE_WSTACK(stack);
hashmap_head_t* root;
- hashmap_doer_state state;
+ Eterm *hp, *kv;
+ Eterm res = NIL;
root = (hashmap_head_t*) boxed_val(node);
- state.hp = HAlloc(p, root->size * 2);
- state.res = NIL;
- hashmap_do_foreach(node, hashmap_keys_doer, &state);
- return state.res;
+ 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 void hashmap_keys_doer(Eterm* kv, hashmap_doer_state* statep) {
- statep->res = CONS(statep->hp, CAR(kv), statep->res);
- statep->hp += 2;
-}
+static Eterm hashmap_keys(Process* p, Eterm node) {
+ DECLARE_WSTACK(stack);
+ hashmap_head_t* root;
+ Eterm *hp, *kv;
+ Eterm res = NIL;
-static void hashmap_values_doer(Eterm* kv, hashmap_doer_state*);
+ 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;
- hashmap_doer_state state;
+ Eterm *hp, *kv;
+ Eterm res = NIL;
root = (hashmap_head_t*) boxed_val(node);
- state.hp = HAlloc(p, root->size * 2);
- state.res = NIL;
- hashmap_do_foreach(node, hashmap_values_doer, &state);
- return state.res;
-}
-
-static void hashmap_values_doer(Eterm* kv, hashmap_doer_state* statep) {
- statep->res = CONS(statep->hp, CDR(kv), statep->res);
- statep->hp += 2;
+ 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;
}
/* hashmap:info/0 */