diff options
Diffstat (limited to 'erts/emulator/beam/erl_hashmap.c')
-rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 103 |
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) { |