aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_hashmap.c')
-rw-r--r--erts/emulator/beam/erl_hashmap.c129
1 files changed, 129 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 2e3a4b8982..2fd743a2d8 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -1112,6 +1112,135 @@ static Eterm hashmap_values(Process* p, Eterm node) {
return res;
}
+static int hash_cmp(Uint32 ha, Uint32 hb)
+{
+ int i;
+ for (i=0; i<8; i++) {
+ int cmp = (int)(ha & 0xF) - (int)(hb & 0xF);
+ if (cmp)
+ return cmp;
+ ha >>= 4;
+ hb >>= 4;
+ }
+ return 0;
+}
+
+static int key_hash_cmp(Eterm* ap, Eterm* bp)
+{
+ Eterm th[2];
+ unsigned lvl = 0;
+
+ if (ap && bp) {
+ ASSERT(CMP_TERM(CAR(ap), CAR(bp)) != 0);
+ for (;;) {
+ Uint32 ha = hashmap_restore_hash(th, lvl, CAR(ap));
+ Uint32 hb = hashmap_restore_hash(th, lvl, CAR(bp));
+ int cmp = hash_cmp(ha, hb);
+ if (cmp)
+ return cmp;
+ lvl += 8;
+ }
+ }
+ 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) {