diff options
author | Sverker Eriksson <[email protected]> | 2015-01-23 20:02:27 +0100 |
---|---|---|
committer | Björn-Egil Dahlberg <[email protected]> | 2015-03-12 18:56:42 +0100 |
commit | b38518ff23477322da221212f29d5ad0d1fb96fa (patch) | |
tree | 6a02a51f92e84a99cb920fcd9e4b976b2ceb9f1e | |
parent | e5d514d5adb230bbc832db5c6cf344a69a8df3bf (diff) | |
download | otp-b38518ff23477322da221212f29d5ad0d1fb96fa.tar.gz otp-b38518ff23477322da221212f29d5ad0d1fb96fa.tar.bz2 otp-b38518ff23477322da221212f29d5ad0d1fb96fa.zip |
erts: Cleanup hashmap_merge_2
-rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 212 |
1 files changed, 78 insertions, 134 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c index 9445a7db9a..1697449234 100644 --- a/erts/emulator/beam/erl_hashmap.c +++ b/erts/emulator/beam/erl_hashmap.c @@ -820,34 +820,23 @@ static void hashmap_to_list_doer(Eterm* kv, hashmap_doer_state* sp) { #define HALLOC_EXTRA 200 -#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; + Eterm *srcA, *srcB, *dst; + Uint32 abm, bbm, rbm; /* node bitmaps */ int keepA; Eterm array[16]; - }stack[16]; + }stack[16], *sp = stack; Eterm *hp, *nhp; - Eterm *ptrA, *ptrB; Eterm hdrA, hdrB; Eterm th[2]; - Uint32 ahx, bhx, abm, bbm, rbm, bit; - Uint ix; - Uint size; + Uint32 ahx, bhx; + Uint size; /* total key-value counter */ int keepA = 0; unsigned lvl = 0; + unsigned node_sz; 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. @@ -872,50 +861,46 @@ recurse: switch (primary_tag(nodeA)) { case TAG_PRIMARY_LIST: { - ptrA = list_val(nodeA); + sp->srcA = list_val(nodeA); switch (primary_tag(nodeB)) { case TAG_PRIMARY_LIST: { /* LEAF + LEAF */ - ptrB = list_val(nodeB); + sp->srcB = list_val(nodeB); - if (EQ(CAR(ptrA), CAR(ptrB))) { + if (EQ(CAR(sp->srcA), CAR(sp->srcB))) { --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); + 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); - ptrA = &nodeA; - ptrB = &nodeB; + sp->srcA = &nodeA; + sp->srcB = &nodeB; } break; } case TAG_PRIMARY_BOXED: { /* LEAF + NODE */ - ptrB = boxed_val(nodeB); - ASSERT(is_header(*ptrB)); - hdrB = *ptrB++; - - ahx = hashmap_restore_hash(th, lvl, CAR(ptrA)); - abm = 1 << hashmap_index(ahx); + 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: - ptrB++; + case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++; case HAMT_SUBTAG_NODE_ARRAY: - bbm = 0xffff; - ptrA = &nodeA; + sp->bbm = 0xffff; break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptrB++; + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; case HAMT_SUBTAG_NODE_BITMAP: - bbm = MAP_HEADER_VAL(hdrB); - ptrA = &nodeA; + sp->bbm = MAP_HEADER_VAL(hdrB); break; default: - erl_exit(1, "bad header tag %ld\r\n", *ptrB & _HEADER_MAP_SUBTAG_MASK); + erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK); break; } break; @@ -926,83 +911,50 @@ recurse: break; } case TAG_PRIMARY_BOXED: { /* NODE + NODE */ - ptrA = boxed_val(nodeA); - hdrA = *ptrA; + sp->srcA = boxed_val(nodeA); + hdrA = *sp->srcA++; ASSERT(is_header(hdrA)); - ptrA++; switch (hdrA & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptrA++; + case HAMT_SUBTAG_HEAD_ARRAY: sp->srcA++; case HAMT_SUBTAG_NODE_ARRAY: { ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED); - ptrB = boxed_val(nodeB); - hdrB = *ptrB; + 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: - ASSERT(lvl == 0); - abm = 0xffff; - bbm = 0xffff; - ptrB += 2; - break; + case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++; case HAMT_SUBTAG_NODE_ARRAY: - ASSERT(lvl > 0); - abm = 0xffff; - bbm = 0xffff; - ptrB++; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ASSERT(lvl == 0); - abm = 0xffff; - bbm = MAP_HEADER_VAL(hdrB); - ptrB += 2; + sp->bbm = 0xffff; break; + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; case HAMT_SUBTAG_NODE_BITMAP: - ASSERT(lvl > 0); - abm = 0xffff; - bbm = MAP_HEADER_VAL(hdrB); - ptrB += 1; + sp->bbm = MAP_HEADER_VAL(hdrB); break; default: - erl_exit(1, "bad header tag %ld\r\n", *ptrB & _HEADER_MAP_SUBTAG_MASK); + erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK); } break; } - case HAMT_SUBTAG_HEAD_BITMAP: - ptrA++; + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcA++; case HAMT_SUBTAG_NODE_BITMAP: { ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED); - abm = MAP_HEADER_VAL(hdrA); - ptrB = boxed_val(nodeB); - hdrB = *ptrB; + 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: - ASSERT(lvl == 0); - bbm = 0xffff; - ptrB += 2; - break; - + case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++; case HAMT_SUBTAG_NODE_ARRAY: - ASSERT(lvl > 0); - bbm = 0xffff; - ptrB++; + sp->bbm = 0xffff; break; - - case HAMT_SUBTAG_HEAD_BITMAP: - ASSERT(lvl == 0); - bbm = MAP_HEADER_VAL(hdrB); - ptrB += 2; - break; - + case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; case HAMT_SUBTAG_NODE_BITMAP: - ASSERT(lvl > 0); - bbm = MAP_HEADER_VAL(hdrB); - ptrB += 1; + sp->bbm = MAP_HEADER_VAL(hdrB); break; default: - erl_exit(1, "bad header tag %ld\r\n", *ptrB & _HEADER_MAP_SUBTAG_MASK); + erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK); } break; } @@ -1022,69 +974,61 @@ recurse: /* 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; + sp--; + *sp->dst++ = res; res = THE_NON_VALUE; - if (rbm) { - ptrA = stack[lvl].ptrA; - ptrB = stack[lvl].ptrB; - keepA = stack[lvl].keepA; + if (sp->rbm) { + sp->srcA++; + sp->srcB++; + keepA = sp->keepA; } } else { /* Start build a node */ - ix = 0; - rbm = abm | bbm; - ASSERT(!(rbm == 0 && lvl > 0)); + sp->dst = sp->array; + sp->rbm = sp->abm | sp->bbm; + ASSERT(!(sp->rbm == 0 && lvl > 0)); } - while (rbm) { - Uint32 next = rbm & (rbm-1); - bit = rbm ^ next; - rbm = next; - if (abm & bit) { - if (bbm & bit) { + 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 (rbm) { - stack[lvl].ptrA = ptrA + 1; - stack[lvl].ptrB = ptrB + 1; - stack[lvl].keepA = keepA; + if (sp->rbm) { + sp->keepA = keepA; } - stack[lvl].abm = abm; - stack[lvl].bbm = bbm; - stack[lvl].rbm = rbm; - stack[lvl].ix = ix; - nodeA = *ptrA; - nodeB = *ptrB; + nodeA = *sp->srcA; + nodeB = *sp->srcB; lvl++; + sp++; goto recurse; } else { - stack[lvl].array[ix++] = *ptrA++; + *sp->dst++ = *sp->srcA++; } } else { - ASSERT(bbm & bit); - stack[lvl].array[ix++] = *ptrB++; + ASSERT(sp->bbm & bit); + *sp->dst++ = *sp->srcB++; } } + node_sz = sp->dst - sp->array; + ASSERT(node_sz == hashmap_bitcount(sp->abm | sp->bbm)); if (lvl == 0) { - nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(ix), HALLOC_EXTRA); + nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(node_sz), HALLOC_EXTRA); hp = nhp; - *hp++ = (ix == 16) ? MAP_HEADER_HAMT_HEAD_ARRAY - : MAP_HEADER_HAMT_HEAD_BITMAP(abm | bbm); + *hp++ = (node_sz == 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(ix), HALLOC_EXTRA); + nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(node_sz), HALLOC_EXTRA); hp = nhp; - *hp++ = (ix == 16) ? make_arityval(16) - : MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm); + *hp++ = (node_sz == 16 ? make_arityval(16) + : MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm)); } - memcpy(hp, stack[lvl].array, ix * sizeof(Eterm)); + memcpy(hp, sp->array, node_sz * sizeof(Eterm)); res = make_boxed(nhp); } - - return res; } static void hashmap_do_foreach(Eterm node, hashmap_doer* fptr, |