aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/erl_hashmap.c103
-rw-r--r--erts/emulator/beam/erl_hashmap.h8
-rw-r--r--erts/emulator/beam/global.h9
-rw-r--r--erts/emulator/beam/utils.c253
4 files changed, 250 insertions, 123 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) {
diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h
index 4a4163bce9..8ba249b053 100644
--- a/erts/emulator/beam/erl_hashmap.h
+++ b/erts/emulator/beam/erl_hashmap.h
@@ -24,7 +24,10 @@
#include "sys.h"
Eterm erts_hashmap_get(Eterm key, Eterm map);
-int hashmap_cmp(Eterm a, Eterm b);
+struct ErtsWStack_;
+void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node);
+Eterm* hashmap_iterator_next(struct ErtsWStack_* s);
+int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp);
/* erl_term.h stuff */
#define make_hashmap(x) make_boxed((Eterm*)(x))
@@ -67,6 +70,9 @@ typedef struct hashmap_head_s {
Uint size;
Eterm items[1];
} hashmap_head_t;
+
+#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size)
+#define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE))
/* the bitmap-node
* typedef struct hashmap_bitmap_node_s {
diff --git a/erts/emulator/beam/global.h b/erts/emulator/beam/global.h
index 7585705949..ad7e6fb89d 100644
--- a/erts/emulator/beam/global.h
+++ b/erts/emulator/beam/global.h
@@ -529,7 +529,7 @@ void erl_grow_wstack(ErtsWStack*, Uint need);
#define WSTK_CONCAT(a,b) a##b
#define WSTK_DEF_STACK(s) WSTK_CONCAT(s,_default_wstack)
-#define DECLARE_WSTACK(s) \
+#define WSTACK_DECLARE(s) \
UWord WSTK_DEF_STACK(s)[DEF_WSTACK_SIZE]; \
ErtsWStack s = { \
WSTK_DEF_STACK(s), /* wstart */ \
@@ -538,6 +538,7 @@ void erl_grow_wstack(ErtsWStack*, Uint need);
WSTK_DEF_STACK(s), /* wdflt */ \
ERTS_ALC_T_ESTACK /* alloc_type */ \
}
+#define DECLARE_WSTACK WSTACK_DECLARE
#define WSTACK_CHANGE_ALLOCATOR(s,t) \
do { \
@@ -548,12 +549,13 @@ do { \
s.alloc_type = (t); \
} while (0)
-#define DESTROY_WSTACK(s) \
+#define WSTACK_DESTROY(s) \
do { \
if (s.wstart != WSTK_DEF_STACK(s)) { \
erts_free(s.alloc_type, s.wstart); \
} \
} while(0)
+#define DESTROY_WSTACK WSTACK_DESTROY
#define WSTACK_DEBUG(s) \
do { \
@@ -686,7 +688,8 @@ do { \
#define WSTACK_ISEMPTY(s) (s.wsp == s.wstart)
#define WSTACK_POP(s) ((ASSERT(s.wsp > s.wstart)),*(--s.wsp))
-
+#define WSTACK_ROLLBACK(s, count) (ASSERT(WSTACK_COUNT(s) >= (count)), \
+ s.wsp = s.wstart + (count))
/* PSTACK - Stack of any type.
* Usage:
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 9fd53e941d..f79cb8db7d 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -2512,7 +2512,18 @@ Sint erts_cmp_rel_opt(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base, int exact)
Sint erts_cmp(Eterm a, Eterm b, int exact)
#endif
{
- DECLARE_WSTACK(stack);
+#define PSTACK_TYPE struct erts_cmp_hashmap_state
+ struct erts_cmp_hashmap_state {
+ Sint wstack_rollback;
+ int was_exact;
+ Eterm *ap;
+ Eterm *bp;
+ Eterm min_key;
+ Sint cmp_res; /* result so far -1,0,+1 */
+ };
+ PSTACK_DECLARE(hmap_stack, 1);
+ WSTACK_DECLARE(stack);
+ WSTACK_DECLARE(b_stack); /* only used by hashmaps */
Eterm* aa;
Eterm* bb;
int i;
@@ -2528,6 +2539,26 @@ Sint erts_cmp(Eterm a, Eterm b, int exact)
Uint32 *anum;
Uint32 *bnum;
+/* The WSTACK contains naked Eterms and Operations marked with header-tags */
+#define OP_BITS 4
+#define OP_MASK 0xF
+#define TERM_ARRAY_OP 0
+#define SWITCH_EXACT_OFF_OP 1
+#define HASHMAP_PHASE1_ARE_KEYS_EQUAL 2
+#define HASHMAP_PHASE1_IS_MIN_KEY 3
+#define HASHMAP_PHASE1_CMP_VALUES 4
+#define HASHMAP_PHASE2_ARE_KEYS_EQUAL 5
+#define HASHMAP_PHASE2_IS_MIN_KEY_A 6
+#define HASHMAP_PHASE2_IS_MIN_KEY_B 7
+
+
+#define OP_WORD(OP) (((OP) << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER)
+#define TERM_ARRAY_OP_WORD(SZ) OP_WORD(((SZ) << OP_BITS) | TERM_ARRAY_OP)
+
+#define GET_OP(WORD) (ASSERT(is_header(WORD)), ((WORD) >> _TAG_PRIMARY_SIZE) & OP_MASK)
+#define GET_OP_ARG(WORD) (ASSERT(is_header(WORD)), ((WORD) >> (OP_BITS + _TAG_PRIMARY_SIZE)))
+
+
#define RETURN_NEQ(cmp) { j=(cmp); ASSERT(j != 0); goto not_equal; }
#define ON_CMP_GOTO(cmp) if ((j=(cmp)) == 0) goto pop_next; else goto not_equal
@@ -2543,6 +2574,8 @@ Sint erts_cmp(Eterm a, Eterm b, int exact)
} while (0)
+bodyrecur:
+ j = 0;
tailrecur:
if (is_same(a,a_base,b,b_base)) { /* Equal values or pointers. */
goto pop_next;
@@ -2692,28 +2725,60 @@ tailrecur_ne:
}
else {
/* Value array */
- WSTACK_PUSH3(stack, i, (UWord)(bb+1), (UWord)(aa+1) | TAG_PRIMARY_HEADER);
- /* Marker to switch back from 'exact' compare */
- WSTACK_PUSH(stack, (UWord)NULL | TAG_PRIMARY_HEADER);
+ WSTACK_PUSH3(stack, (UWord)(bb+1), (UWord)(aa+1), TERM_ARRAY_OP_WORD(i));
+ /* Switch back from 'exact' key compare */
+ WSTACK_PUSH(stack, OP_WORD(SWITCH_EXACT_OFF_OP));
/* Now do 'exact' compare of key tuples */
a = *aa;
b = *bb;
exact = 1;
- goto tailrecur;
+ goto bodyrecur;
}
case (_TAG_HEADER_HASHMAP >> _TAG_PRIMARY_SIZE) :
{
+ struct erts_cmp_hashmap_state* sp;
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);
+ i = hashmap_size_rel(a,a_base) - hashmap_size_rel(b,b_base);
if (i) {
RETURN_NEQ(i);
}
- ON_CMP_GOTO(hashmap_cmp(a, b));
+ if (hashmap_size_rel(a,a_base) == 0) {
+ goto pop_next;
+ }
+
+ /* Hashmap compare strategy:
+ Phase 1. While keys are identical
+ Do synchronous stepping through leafs of both trees in hash
+ order. Maintain value compare result of minimal 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).
+ */
+
+ sp = PSTACK_PUSH(hmap_stack);
+ hashmap_iterator_init(&stack, a);
+ hashmap_iterator_init(&b_stack, b);
+ sp->ap = hashmap_iterator_next(&stack);
+ sp->bp = hashmap_iterator_next(&b_stack);
+ sp->cmp_res = 0;
+ ASSERT(sp->ap && sp->bp);
+
+ a = CAR(sp->ap);
+ b = CAR(sp->bp);
+ sp->was_exact = exact;
+ exact = 1;
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE1_ARE_KEYS_EQUAL));
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
}
case (_TAG_HEADER_FLOAT >> _TAG_PRIMARY_SIZE):
if (!is_float_rel(b,b_base)) {
@@ -3074,8 +3139,7 @@ term_array: /* arrays in 'aa' and 'bb', length in 'i' */
goto not_equal;
}
} else {
- /* (ab)Use TAG_PRIMARY_HEADER to recognize a term_array */
- WSTACK_PUSH3(stack, i, (UWord)bb, (UWord)aa | TAG_PRIMARY_HEADER);
+ WSTACK_PUSH3(stack, (UWord)bb, (UWord)aa, TERM_ARRAY_OP_WORD(i));
goto tailrecur_ne;
}
}
@@ -3087,28 +3151,179 @@ term_array: /* arrays in 'aa' and 'bb', length in 'i' */
pop_next:
if (!WSTACK_ISEMPTY(stack)) {
UWord something = WSTACK_POP(stack);
- if (primary_tag((Eterm) something) == TAG_PRIMARY_HEADER) { /* a term_array */
- if (something == ((UWord)NULL | TAG_PRIMARY_HEADER)) {
+ struct erts_cmp_hashmap_state* sp;
+ if (primary_tag((Eterm) something) == TAG_PRIMARY_HEADER) { /* an operation */
+ switch (GET_OP(something)) {
+ case TERM_ARRAY_OP:
+ i = GET_OP_ARG(something);
+ aa = (Eterm*)WSTACK_POP(stack);
+ bb = (Eterm*) WSTACK_POP(stack);
+ goto term_array;
+
+ case SWITCH_EXACT_OFF_OP:
/* Done with exact compare of map keys, switch back */
ASSERT(exact);
exact = 0;
goto pop_next;
- }
- aa = (Eterm *)something;
- bb = (Eterm*) WSTACK_POP(stack);
- i = WSTACK_POP(stack);
- goto term_array;
+
+ case HASHMAP_PHASE1_ARE_KEYS_EQUAL: {
+ sp = PSTACK_TOP(hmap_stack);
+ if (j) {
+ /* Key diff found, enter phase 2 */
+ if (hashmap_key_hash_cmp(sp->ap, sp->bp) < 0) {
+ sp->min_key = CAR(sp->ap);
+ sp->cmp_res = -1;
+ sp->ap = hashmap_iterator_next(&stack);
+ }
+ else {
+ sp->min_key = CAR(sp->bp);
+ sp->cmp_res = 1;
+ sp->bp = hashmap_iterator_next(&b_stack);
+ }
+ exact = 1; /* only exact key compares in phase 2 */
+ goto case_HASHMAP_PHASE2_LOOP;
+ }
+
+ /* No key diff found so far, compare values if min key */
+
+ if (sp->cmp_res) {
+ a = CAR(sp->ap);
+ b = sp->min_key;
+ exact = 1;
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE1_IS_MIN_KEY));
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
+ }
+ /* no min key-value found yet */
+ a = CDR(sp->ap);
+ b = CDR(sp->bp);
+ exact = sp->was_exact;
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE1_CMP_VALUES));
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
+ }
+ case HASHMAP_PHASE1_IS_MIN_KEY:
+ sp = PSTACK_TOP(hmap_stack);
+ if (j < 0) {
+ a = CDR(sp->ap);
+ b = CDR(sp->bp);
+ exact = sp->was_exact;
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE1_CMP_VALUES));
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
+ }
+ goto case_HASHMAP_PHASE1_LOOP;
+
+ case HASHMAP_PHASE1_CMP_VALUES:
+ sp = PSTACK_TOP(hmap_stack);
+ if (j) {
+ sp->cmp_res = j;
+ sp->min_key = CAR(sp->ap);
+ }
+ case_HASHMAP_PHASE1_LOOP:
+ sp->ap = hashmap_iterator_next(&stack);
+ sp->bp = hashmap_iterator_next(&b_stack);
+ if (!sp->ap) {
+ /* end of maps with identical keys */
+ ASSERT(!sp->bp);
+ j = sp->cmp_res;
+ exact = sp->was_exact;
+ (void) PSTACK_POP(hmap_stack);
+ ON_CMP_GOTO(j);
+ }
+ a = CAR(sp->ap);
+ b = CAR(sp->bp);
+ exact = 1;
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE1_ARE_KEYS_EQUAL));
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
+
+ case_HASHMAP_PHASE2_LOOP:
+ if (sp->ap && sp->bp) {
+ a = CAR(sp->ap);
+ b = CAR(sp->bp);
+ ASSERT(exact);
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE2_ARE_KEYS_EQUAL));
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
+ }
+ goto case_HASHMAP_PHASE2_NEXT_STEP;
+
+ case HASHMAP_PHASE2_ARE_KEYS_EQUAL:
+ sp = PSTACK_TOP(hmap_stack);
+ if (j == 0) {
+ /* keys are equal, skip them */
+ sp->ap = hashmap_iterator_next(&stack);
+ sp->bp = hashmap_iterator_next(&b_stack);
+ goto case_HASHMAP_PHASE2_LOOP;
+ }
+ /* fall through */
+ case_HASHMAP_PHASE2_NEXT_STEP:
+ if (sp->ap || sp->bp) {
+ if (hashmap_key_hash_cmp(sp->ap, sp->bp) < 0) {
+ ASSERT(sp->ap);
+ a = CAR(sp->ap);
+ b = sp->min_key;
+ ASSERT(exact);
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE2_IS_MIN_KEY_A));
+ }
+ else { /* hash_cmp > 0 */
+ ASSERT(sp->bp);
+ a = CAR(sp->bp);
+ b = sp->min_key;
+ ASSERT(exact);
+ WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE2_IS_MIN_KEY_B));
+ }
+ sp->wstack_rollback = WSTACK_COUNT(stack);
+ goto bodyrecur;
+ }
+ /* End of both maps */
+ j = sp->cmp_res;
+ exact = sp->was_exact;
+ (void) PSTACK_POP(hmap_stack);
+ ON_CMP_GOTO(j);
+
+ case HASHMAP_PHASE2_IS_MIN_KEY_A:
+ sp = PSTACK_TOP(hmap_stack);
+ if (j < 0) {
+ sp->min_key = CAR(sp->ap);
+ sp->cmp_res = -1;
+ }
+ sp->ap = hashmap_iterator_next(&stack);
+ goto case_HASHMAP_PHASE2_LOOP;
+
+ case HASHMAP_PHASE2_IS_MIN_KEY_B:
+ sp = PSTACK_TOP(hmap_stack);
+ if (j < 0) {
+ sp->min_key = CAR(sp->bp);
+ sp->cmp_res = 1;
+ }
+ sp->bp = hashmap_iterator_next(&b_stack);
+ goto case_HASHMAP_PHASE2_LOOP;
+
+ default:
+ ASSERT(!"Invalid cmp op");
+ } /* switch */
}
a = (Eterm) something;
b = (Eterm) WSTACK_POP(stack);
goto tailrecur;
}
- DESTROY_WSTACK(stack);
+ ASSERT(PSTACK_IS_EMPTY(hmap_stack));
+ PSTACK_DESTROY(hmap_stack);
+ WSTACK_DESTROY(stack);
+ WSTACK_DESTROY(b_stack);
return 0;
not_equal:
- DESTROY_WSTACK(stack);
+ if (!PSTACK_IS_EMPTY(hmap_stack)) {
+ WSTACK_ROLLBACK(stack, PSTACK_TOP(hmap_stack)->wstack_rollback);
+ goto pop_next;
+ }
+ PSTACK_DESTROY(hmap_stack);
+ WSTACK_DESTROY(stack);
+ WSTACK_DESTROY(b_stack);
return j;
#undef CMP_NODES
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-18 16:59:20 +0000