diff options
| -rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 129 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_hashmap.h | 2 | ||||
| -rw-r--r-- | erts/emulator/beam/utils.c | 13 |
3 files changed, 144 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) { diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h index 4ef795b11e..4a4163bce9 100644 --- a/erts/emulator/beam/erl_hashmap.h +++ b/erts/emulator/beam/erl_hashmap.h @@ -24,11 +24,13 @@ #include "sys.h" Eterm erts_hashmap_get(Eterm key, Eterm map); +int hashmap_cmp(Eterm a, Eterm b); /* erl_term.h stuff */ #define make_hashmap(x) make_boxed((Eterm*)(x)) #define make_hashmap_rel make_boxed_rel #define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x)))) +#define is_hashmap_rel(RTERM,BASE) is_hashmap(rterm2wterm(RTERM,BASE)) #define is_hashmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HASHMAP) #define hashmap_val(x) _unchecked_boxed_val((x)) #define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE)) diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 908116c64c..9fd53e941d 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2702,6 +2702,19 @@ tailrecur_ne: goto tailrecur; } + case (_TAG_HEADER_HASHMAP >> _TAG_PRIMARY_SIZE) : + { + if (!is_hashmap_rel(b,b_base)) { + a_tag = HASHMAP_DEF; + goto mixed_types; + } + i = (((hashmap_head_t*) hashmap_val_rel(a,a_base))->size - + ((hashmap_head_t*) hashmap_val_rel(b,b_base))->size); + if (i) { + RETURN_NEQ(i); + } + ON_CMP_GOTO(hashmap_cmp(a, b)); + } case (_TAG_HEADER_FLOAT >> _TAG_PRIMARY_SIZE): if (!is_float_rel(b,b_base)) { a_tag = FLOAT_DEF; |