diff options
author | Björn-Egil Dahlberg <[email protected]> | 2015-02-23 17:27:41 +0100 |
---|---|---|
committer | Björn-Egil Dahlberg <[email protected]> | 2015-03-12 19:15:28 +0100 |
commit | 7ac42c5d31f7722907b44d2df3421f8cd88d48c5 (patch) | |
tree | 3f9298c1256f5f25802f39ade7078dcd8142bd88 /erts/emulator/beam/erl_hashmap.c | |
parent | 746d2d846ebf20fc4dc303c53bcd1e908aee924b (diff) | |
download | otp-7ac42c5d31f7722907b44d2df3421f8cd88d48c5.tar.gz otp-7ac42c5d31f7722907b44d2df3421f8cd88d48c5.tar.bz2 otp-7ac42c5d31f7722907b44d2df3421f8cd88d48c5.zip |
erts: Move hashmap:merge/2 to maps
Diffstat (limited to 'erts/emulator/beam/erl_hashmap.c')
-rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 262 |
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 */ |