aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/erl_hashmap.c180
1 files changed, 116 insertions, 64 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 74f27fb3ac..bdcb479c30 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -70,7 +70,7 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node);
static Eterm hashmap_to_list(Process *p, Eterm map);
static Eterm hashmap_keys(Process *p, Eterm map);
static Eterm hashmap_values(Process *p, Eterm map);
-static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, Uint lvl, Uint *sizep, int keepA);
+static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
/* hashmap:new/0 */
@@ -196,10 +196,7 @@ BIF_RETTYPE hashmap_values_1(BIF_ALIST_1) {
BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) {
if (is_hashmap(BIF_ARG_1) && is_hashmap(BIF_ARG_2)) {
- hashmap_head_t* a = (hashmap_head_t*) hashmap_val(BIF_ARG_1);
- hashmap_head_t* b = (hashmap_head_t*) hashmap_val(BIF_ARG_2);
- Uint size = a->size + b->size;
- BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2, 0, &size, 0));
+ BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
}
BIF_ERROR(BIF_P, BADARG);
}
@@ -797,15 +794,46 @@ static Eterm hashmap_to_list(Process *p, Eterm node) {
#define HALLOC_EXTRA 200
-static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB,
- Uint lvl, Uint *sizep, int keepA) {
+#if defined(VALGRIND) || defined(GO_SUPER_FAST)
+# define UNDEF(V,I)
+#else
+# define UNDEF(V,I) V=I
+#endif
+
+static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
+ struct {
+ Eterm *ptrA, *ptrB;
+ Uint32 abm, bbm, rbm;
+ Uint ix;
+ int keepA;
+ Eterm array[16];
+ }stack[16];
Eterm *hp, *nhp;
Eterm *ptrA, *ptrB;
- Eterm array[16];
Eterm hdrA, hdrB;
Eterm th[2];
Uint32 ahx, bhx, abm, bbm, rbm, bit;
Uint ix;
+ Uint size;
+ int keepA = 0;
+ unsigned lvl = 0;
+ Eterm res = THE_NON_VALUE;
+
+ UNDEF(abm,0);
+ UNDEF(bbm,0);
+
+ /*
+ * Strategy: Do depth-first traversal of both trees (at the same time)
+ * and merge each pair of nodes.
+ */
+
+ {
+ hashmap_head_t* a = (hashmap_head_t*) hashmap_val(nodeA);
+ hashmap_head_t* b = (hashmap_head_t*) hashmap_val(nodeB);
+ size = a->size + b->size;
+ }
+
+recurse:
if (primary_tag(nodeA) == TAG_PRIMARY_BOXED &&
primary_tag(nodeB) == TAG_PRIMARY_LIST) {
@@ -817,40 +845,27 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB,
}
switch (primary_tag(nodeA)) {
- case TAG_PRIMARY_LIST: { /* LEAF NODE [K|V] */
+ case TAG_PRIMARY_LIST: {
ptrA = list_val(nodeA);
switch (primary_tag(nodeB)) {
- case TAG_PRIMARY_LIST: { /* LEAF NODE [K|V] */
+ case TAG_PRIMARY_LIST: { /* LEAF + LEAF */
ptrB = list_val(nodeB);
if (EQ(CAR(ptrA), CAR(ptrB))) {
- --(*sizep);
- return keepA ? nodeA : nodeB;
- }
- ahx = hashmap_restore_hash(th, lvl, CAR(ptrA));
- bhx = hashmap_restore_hash(th, lvl, CAR(ptrB));
- abm = 1 << hashmap_index(ahx);
- bbm = 1 << hashmap_index(bhx);
-
- if (abm != bbm) {
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(2), HALLOC_EXTRA);
- hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm);
- if (abm < bbm) {
- hp[1] = CAR(ptrA);
- hp[2] = CAR(ptrB);
- } else {
- hp[1] = CAR(ptrB);
- hp[2] = CAR(ptrA);
- }
- }
- else {
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
- hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(abm);
- hp[1] = hashmap_merge(p, nodeA, nodeB, lvl+1, sizep, keepA);
+ --size;
+ res = keepA ? nodeA : nodeB;
+ } else {
+ ahx = hashmap_restore_hash(th, lvl, CAR(ptrA));
+ bhx = hashmap_restore_hash(th, lvl, CAR(ptrB));
+ abm = 1 << hashmap_index(ahx);
+ bbm = 1 << hashmap_index(bhx);
+
+ ptrA = &nodeA;
+ ptrB = &nodeB;
}
- return make_hashmap(hp);
+ break;
}
- case TAG_PRIMARY_BOXED: {
+ case TAG_PRIMARY_BOXED: { /* LEAF + NODE */
ptrB = boxed_val(nodeB);
ASSERT(is_header(*ptrB));
hdrB = *ptrB++;
@@ -884,7 +899,7 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB,
}
break;
}
- case TAG_PRIMARY_BOXED: {
+ case TAG_PRIMARY_BOXED: { /* NODE + NODE */
ptrA = boxed_val(nodeA);
hdrA = *ptrA;
ASSERT(is_header(hdrA));
@@ -974,39 +989,76 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB,
erl_exit(1, "bad primary tag %ld\r\n", nodeA);
}
- ix = 0;
- rbm = abm | bbm;
- ASSERT(rbm != 0);
- do {
- Uint32 next = rbm & (rbm-1);
- bit = rbm ^ next;
- rbm = next;
- if (abm & bit) {
- if (bbm & bit) {
- array[ix++] = hashmap_merge(p, *ptrA++, *ptrB++, lvl+1, sizep, keepA);
+ for (;;) {
+ if (is_value(res)) { /* We have a complete (sub-)tree or leaf */
+ if (lvl == 0)
+ return res;
+
+ /* Pop from stack and continue build parent node */
+ lvl--;
+ abm = stack[lvl].abm;
+ bbm = stack[lvl].bbm;
+ rbm = stack[lvl].rbm;
+ ix = stack[lvl].ix;
+ stack[lvl].array[ix++] = res;
+ res = THE_NON_VALUE;
+ if (rbm) {
+ ptrA = stack[lvl].ptrA;
+ ptrB = stack[lvl].ptrB;
+ keepA = stack[lvl].keepA;
+ }
+ } else { /* Start build a node */
+ ix = 0;
+ rbm = abm | bbm;
+ ASSERT(!(rbm == 0 && lvl > 0));
+ }
+
+ while (rbm) {
+ Uint32 next = rbm & (rbm-1);
+ bit = rbm ^ next;
+ rbm = next;
+ if (abm & bit) {
+ if (bbm & bit) {
+ /* Bit clash. Push and resolve by recursive merge */
+ if (rbm) {
+ stack[lvl].ptrA = ptrA + 1;
+ stack[lvl].ptrB = ptrB + 1;
+ stack[lvl].keepA = keepA;
+ }
+ stack[lvl].abm = abm;
+ stack[lvl].bbm = bbm;
+ stack[lvl].rbm = rbm;
+ stack[lvl].ix = ix;
+ nodeA = *ptrA;
+ nodeB = *ptrB;
+ lvl++;
+ goto recurse;
+ } else {
+ stack[lvl].array[ix++] = *ptrA++;
+ }
} else {
- array[ix++] = *ptrA++;
+ ASSERT(bbm & bit);
+ stack[lvl].array[ix++] = *ptrB++;
}
+ }
+
+ if (lvl == 0) {
+ nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(ix), HALLOC_EXTRA);
+ hp = nhp;
+ *hp++ = (ix == 16) ? MAP_HEADER_HAMT_HEAD_ARRAY
+ : MAP_HEADER_HAMT_HEAD_BITMAP(abm | bbm);
+ *hp++ = size;
} else {
- ASSERT(bbm & bit);
- array[ix++] = *ptrB++;
+ nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(ix), HALLOC_EXTRA);
+ hp = nhp;
+ *hp++ = (ix == 16) ? make_arityval(16)
+ : MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm);
}
- }while (rbm);
-
- if (lvl == 0) {
- nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(ix), HALLOC_EXTRA);
- hp = nhp;
- *hp++ = (ix == 16) ? MAP_HEADER_HAMT_HEAD_ARRAY
- : MAP_HEADER_HAMT_HEAD_BITMAP(abm | bbm);
- *hp++ = *sizep;
- } else {
- nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(ix), HALLOC_EXTRA);
- hp = nhp;
- *hp++ = (ix == 16) ? make_arityval(16)
- : MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm);
+ memcpy(hp, stack[lvl].array, ix * sizeof(Eterm));
+ res = make_boxed(nhp);
}
- memcpy(hp, array, ix * sizeof(Eterm));
- return make_boxed(nhp);
+
+ return res;
}
typedef void hashmap_doer(Eterm*, void*);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 03:23:28 +0000