aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-02-11 21:50:25 +0100
committerBjörn-Egil Dahlberg <[email protected]>2015-03-12 19:15:23 +0100
commit442c9b4d11a62c55b46ffb25f27b5ec5fb3adda7 (patch)
tree1167524b8fea2e3299cfdc33b97da180d784805e /erts/emulator
parentaad7d6fe4e1e9fe086d275ab3ea34c5285cc8edb (diff)
downloadotp-442c9b4d11a62c55b46ffb25f27b5ec5fb3adda7.tar.gz
otp-442c9b4d11a62c55b46ffb25f27b5ec5fb3adda7.tar.bz2
otp-442c9b4d11a62c55b46ffb25f27b5ec5fb3adda7.zip
erts: First recursive version of hashmap compare
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/erl_hashmap.c129
-rw-r--r--erts/emulator/beam/erl_hashmap.h2
-rw-r--r--erts/emulator/beam/utils.c13
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;