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.c262
1 files changed, 0 insertions, 262 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index fecdc2ef31..0c146137f5 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -56,9 +56,6 @@ static char *format_binary(Uint64 x, char *b) {
}
#endif
-
-static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
-
/* hashmap:new/0 */
/* hashmap:put/3 */
@@ -85,263 +82,4 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
/* hashmap:values/1 */
-BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) {
- if (is_hashmap(BIF_ARG_1) && is_hashmap(BIF_ARG_2)) {
- BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
- }
- BIF_ERROR(BIF_P, BADARG);
-}
-
-/* impl. */
-
-
-#define HALLOC_EXTRA 200
-
-static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
-#define PSTACK_TYPE struct HashmapMergePStackType
- struct HashmapMergePStackType {
- Eterm *srcA, *srcB;
- Uint32 abm, bbm, rbm; /* node bitmaps */
- int keepA;
- int ix;
- Eterm array[16];
- };
- PSTACK_DECLARE(s, 4);
- struct HashmapMergePStackType* sp = PSTACK_PUSH(s);
- Eterm *hp, *nhp;
- Eterm hdrA, hdrB;
- Eterm th[2];
- Uint32 ahx, bhx;
- Uint size; /* total key-value counter */
- int keepA = 0;
- unsigned lvl = 0;
- Eterm res = THE_NON_VALUE;
-
- /*
- * 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) {
- /* Avoid implementing this combination by switching places */
- Eterm tmp = nodeA;
- nodeA = nodeB;
- nodeB = tmp;
- keepA = !keepA;
- }
-
- switch (primary_tag(nodeA)) {
- case TAG_PRIMARY_LIST: {
- sp->srcA = list_val(nodeA);
- switch (primary_tag(nodeB)) {
- case TAG_PRIMARY_LIST: { /* LEAF + LEAF */
- sp->srcB = list_val(nodeB);
-
- if (EQ(CAR(sp->srcA), CAR(sp->srcB))) {
- --size;
- res = keepA ? nodeA : nodeB;
- } else {
- ahx = hashmap_restore_hash(th, lvl, CAR(sp->srcA));
- bhx = hashmap_restore_hash(th, lvl, CAR(sp->srcB));
- sp->abm = 1 << hashmap_index(ahx);
- sp->bbm = 1 << hashmap_index(bhx);
-
- sp->srcA = &nodeA;
- sp->srcB = &nodeB;
- }
- break;
- }
- case TAG_PRIMARY_BOXED: { /* LEAF + NODE */
- sp->srcB = boxed_val(nodeB);
- ASSERT(is_header(*sp->srcB));
- hdrB = *sp->srcB++;
-
- ahx = hashmap_restore_hash(th, lvl, CAR(sp->srcA));
- sp->abm = 1 << hashmap_index(ahx);
- sp->srcA = &nodeA;
- switch(hdrB & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++;
- case HAMT_SUBTAG_NODE_ARRAY:
- sp->bbm = 0xffff;
- break;
-
- case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sp->bbm = MAP_HEADER_VAL(hdrB);
- break;
-
- default:
- erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK);
- break;
- }
- break;
- }
- default:
- erl_exit(1, "bad primary tag %ld\r\n", nodeB);
- }
- break;
- }
- case TAG_PRIMARY_BOXED: { /* NODE + NODE */
- sp->srcA = boxed_val(nodeA);
- hdrA = *sp->srcA++;
- ASSERT(is_header(hdrA));
- switch (hdrA & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcA++;
- case HAMT_SUBTAG_NODE_ARRAY: {
- ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED);
- sp->abm = 0xffff;
- sp->srcB = boxed_val(nodeB);
- hdrB = *sp->srcB++;
- ASSERT(is_header(hdrB));
- switch (hdrB & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++;
- case HAMT_SUBTAG_NODE_ARRAY:
- sp->bbm = 0xffff;
- break;
- case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sp->bbm = MAP_HEADER_VAL(hdrB);
- break;
- default:
- erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK);
- }
- break;
- }
- case HAMT_SUBTAG_HEAD_BITMAP: sp->srcA++;
- case HAMT_SUBTAG_NODE_BITMAP: {
- ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED);
- sp->abm = MAP_HEADER_VAL(hdrA);
- sp->srcB = boxed_val(nodeB);
- hdrB = *sp->srcB++;
- ASSERT(is_header(hdrB));
- switch (hdrB & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++;
- case HAMT_SUBTAG_NODE_ARRAY:
- sp->bbm = 0xffff;
- break;
- case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
- case HAMT_SUBTAG_NODE_BITMAP:
- sp->bbm = MAP_HEADER_VAL(hdrB);
- break;
-
- default:
- erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK);
- }
- break;
- }
- default:
- erl_exit(1, "bad primary tag %ld\r\n", nodeA);
- }
- break;
- }
- default:
- erl_exit(1, "bad primary tag %ld\r\n", nodeA);
- }
-
- for (;;) {
- if (is_value(res)) { /* We have a complete (sub-)tree or leaf */
- if (lvl == 0)
- break;
-
- /* Pop from stack and continue build parent node */
- lvl--;
- sp = PSTACK_POP(s);
- sp->array[sp->ix++] = res;
- res = THE_NON_VALUE;
- if (sp->rbm) {
- sp->srcA++;
- sp->srcB++;
- keepA = sp->keepA;
- }
- } else { /* Start build a node */
- sp->ix = 0;
- sp->rbm = sp->abm | sp->bbm;
- ASSERT(!(sp->rbm == 0 && lvl > 0));
- }
-
- while (sp->rbm) {
- Uint32 next = sp->rbm & (sp->rbm-1);
- Uint32 bit = sp->rbm ^ next;
- sp->rbm = next;
- if (sp->abm & bit) {
- if (sp->bbm & bit) {
- /* Bit clash. Push and resolve by recursive merge */
- if (sp->rbm) {
- sp->keepA = keepA;
- }
- nodeA = *sp->srcA;
- nodeB = *sp->srcB;
- lvl++;
- sp = PSTACK_PUSH(s);
- goto recurse;
- } else {
- sp->array[sp->ix++] = *sp->srcA++;
- }
- } else {
- ASSERT(sp->bbm & bit);
- sp->array[sp->ix++] = *sp->srcB++;
- }
- }
-
- ASSERT(sp->ix == hashmap_bitcount(sp->abm | sp->bbm));
- if (lvl == 0) {
- nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(sp->ix), HALLOC_EXTRA);
- hp = nhp;
- *hp++ = (sp->ix == 16 ? MAP_HEADER_HAMT_HEAD_ARRAY
- : MAP_HEADER_HAMT_HEAD_BITMAP(sp->abm | sp->bbm));
- *hp++ = size;
- } else {
- nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sp->ix), HALLOC_EXTRA);
- hp = nhp;
- *hp++ = (sp->ix == 16 ? make_arityval(16)
- : MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm));
- }
- memcpy(hp, sp->array, sp->ix * sizeof(Eterm));
- res = make_boxed(nhp);
- }
- PSTACK_DESTROY(s);
- 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;
-}
-
-int hashmap_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;
-}
-
/* hashmap:info/0 */
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-30 17:31:43 +0000