aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_hashmap.c
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-02-10 23:32:12 +0100
committerBjörn-Egil Dahlberg <[email protected]>2015-03-12 19:15:24 +0100
commit6cc099bf98f384de1de3c0d8542c83db43fb5cec (patch)
tree15f19f1e96bcc6b2c805d9ad186cf370e3dfda03 /erts/emulator/beam/erl_hashmap.c
parent442c9b4d11a62c55b46ffb25f27b5ec5fb3adda7 (diff)
downloadotp-6cc099bf98f384de1de3c0d8542c83db43fb5cec.tar.gz
otp-6cc099bf98f384de1de3c0d8542c83db43fb5cec.tar.bz2
otp-6cc099bf98f384de1de3c0d8542c83db43fb5cec.zip
erts: Make hashmap compare non-recursive
Diffstat (limited to 'erts/emulator/beam/erl_hashmap.c')
-rw-r--r--erts/emulator/beam/erl_hashmap.c103
1 files changed, 3 insertions, 100 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 2fd743a2d8..b423111715 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -1009,12 +1009,12 @@ recurse:
return res;
}
-static void hashmap_iterator_init(ErtsWStack* s, Eterm node) {
+void hashmap_iterator_init(ErtsWStack* s, Eterm node) {
WSTACK_PUSH((*s), (UWord)THE_NON_VALUE); /* end marker */
WSTACK_PUSH((*s), (UWord)node);
}
-static Eterm* hashmap_iterator_next(ErtsWStack* s) {
+Eterm* hashmap_iterator_next(ErtsWStack* s) {
Eterm node, *ptr, hdr;
Uint32 sz;
@@ -1125,7 +1125,7 @@ static int hash_cmp(Uint32 ha, Uint32 hb)
return 0;
}
-static int key_hash_cmp(Eterm* ap, Eterm* bp)
+int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp)
{
Eterm th[2];
unsigned lvl = 0;
@@ -1144,103 +1144,6 @@ static int key_hash_cmp(Eterm* ap, Eterm* bp)
return ap ? -1 : 1;
}
-int hashmap_cmp(Eterm a, Eterm b)
-{
- DECLARE_WSTACK(astack);
- DECLARE_WSTACK(bstack);
- Eterm *ap;
- Eterm *bp;
- Eterm min_key;
- int cmp_res = 0;
-
- /* Strategy:
- Phase 1.
- While keys are identical
- Do synchronous stepping through leafs of both trees in hash order.
- Maintain min value of min key.
-
- Phase 2: (If key diff was found in phase 1)
- Ignore values from now on.
- Continue iterate trees by always advancing the one lagging behind hash-wise.
- Identical keys are skipped
- A minimal key can only be candidate as tie-breaker if we have passed
- that hash value in the other tree (which means the key did not exist
- in the other tree).
- */
-
- hashmap_iterator_init(&astack, a);
- hashmap_iterator_init(&bstack, b);
-
- for (;;) { /* Phase 1 */
- int cmp;
- ap = hashmap_iterator_next(&astack);
- bp = hashmap_iterator_next(&bstack);
- if (!ap) {
- ASSERT(!bp);
- return cmp_res;
- }
- cmp = CMP_TERM(CAR(ap), CAR(bp));
- if (cmp)
- break;
-
- /* No key diff found so far, compare values */
- if (!cmp_res || (CMP_TERM(CAR(ap), min_key) < 0)) {
- cmp = CMP(CDR(ap), CDR(bp));
- if (cmp) {
- cmp_res = cmp;
- min_key = CAR(ap);
- }
- }
- }
-
- /* Phase 2 */
-
- if (key_hash_cmp(ap,bp) < 0) {
- min_key = CAR(ap);
- cmp_res = -1;
- ap = hashmap_iterator_next(&astack);
- }
- else {
- min_key = CAR(bp);
- cmp_res = 1;
- bp = hashmap_iterator_next(&bstack);
- }
-
- for (;;) {
- int hash_cmp;
-
- while (ap && bp && CMP_TERM(CAR(ap), CAR(bp)) == 0) {
- ap = hashmap_iterator_next(&astack);
- bp = hashmap_iterator_next(&bstack);
- }
- if (!ap && !bp)
- break;
-
- hash_cmp = key_hash_cmp(ap,bp);
- if (hash_cmp < 0) {
- ASSERT(ap);
- if (CMP_TERM(CAR(ap), min_key) < 0) {
- min_key = CAR(ap);
- cmp_res = -1;
- }
- ap = hashmap_iterator_next(&astack);
- }
- else if (hash_cmp > 0) {
- ASSERT(bp);
- if (CMP_TERM(CAR(bp), min_key) < 0) {
- min_key = CAR(bp);
- cmp_res = 1;
- }
- bp = hashmap_iterator_next(&bstack);
- }
- }
-
- DESTROY_WSTACK(astack);
- DESTROY_WSTACK(bstack);
-
- return cmp_res;
-}
-
/* hashmap:info/0 */
static Eterm hashmap_info(Process *p, Eterm node) {