erts: Make hashmap compare non-recursive

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) {