diff options
| -rw-r--r-- | erts/emulator/beam/bif.tab | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 225 |
2 files changed, 226 insertions, 0 deletions
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index ed85021f8a..6408883e96 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -626,6 +626,7 @@ bif hashmap:keys/1 bif hashmap:size/1 bif erlang:is_hashmap/1 bif hashmap:values/1 +bif hashmap:merge/2 # # Obsolete diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c index 5cb768a3fe..74f27fb3ac 100644 --- a/erts/emulator/beam/erl_hashmap.c +++ b/erts/emulator/beam/erl_hashmap.c @@ -70,6 +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_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); /* hashmap:new/0 */ @@ -193,6 +194,16 @@ BIF_RETTYPE hashmap_values_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADARG); } +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_ERROR(BIF_P, BADARG); +} + /* impl. */ static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) { @@ -784,6 +795,220 @@ static Eterm hashmap_to_list(Process *p, Eterm node) { return res; } +#define HALLOC_EXTRA 200 + +static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, + Uint lvl, Uint *sizep, int keepA) { + Eterm *hp, *nhp; + Eterm *ptrA, *ptrB; + Eterm array[16]; + Eterm hdrA, hdrB; + Eterm th[2]; + Uint32 ahx, bhx, abm, bbm, rbm, bit; + Uint ix; + + 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: { /* LEAF NODE [K|V] */ + ptrA = list_val(nodeA); + switch (primary_tag(nodeB)) { + case TAG_PRIMARY_LIST: { /* LEAF NODE [K|V] */ + 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); + } + return make_hashmap(hp); + } + case TAG_PRIMARY_BOXED: { + ptrB = boxed_val(nodeB); + ASSERT(is_header(*ptrB)); + hdrB = *ptrB++; + + ahx = hashmap_restore_hash(th, lvl, CAR(ptrA)); + abm = 1 << hashmap_index(ahx); + + switch(hdrB & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptrB++; + case HAMT_SUBTAG_NODE_ARRAY: + bbm = 0xffff; + ptrA = &nodeA; + break; + + case HAMT_SUBTAG_HEAD_BITMAP: + ptrB++; + case HAMT_SUBTAG_NODE_BITMAP: + bbm = MAP_HEADER_VAL(hdrB); + ptrA = &nodeA; + break; + + default: + erl_exit(1, "bad header tag %ld\r\n", *ptrB & _HEADER_MAP_SUBTAG_MASK); + break; + } + break; + } + default: + erl_exit(1, "bad primary tag %ld\r\n", nodeB); + } + break; + } + case TAG_PRIMARY_BOXED: { + ptrA = boxed_val(nodeA); + hdrA = *ptrA; + ASSERT(is_header(hdrA)); + ptrA++; + switch (hdrA & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptrA++; + case HAMT_SUBTAG_NODE_ARRAY: { + ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED); + ptrB = boxed_val(nodeB); + hdrB = *ptrB; + 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_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; + break; + case HAMT_SUBTAG_NODE_BITMAP: + ASSERT(lvl > 0); + abm = 0xffff; + bbm = MAP_HEADER_VAL(hdrB); + ptrB += 1; + break; + default: + erl_exit(1, "bad header tag %ld\r\n", *ptrB & _HEADER_MAP_SUBTAG_MASK); + } + break; + } + case HAMT_SUBTAG_HEAD_BITMAP: + ptrA++; + case HAMT_SUBTAG_NODE_BITMAP: { + ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED); + abm = MAP_HEADER_VAL(hdrA); + ptrB = boxed_val(nodeB); + hdrB = *ptrB; + 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_NODE_ARRAY: + ASSERT(lvl > 0); + bbm = 0xffff; + ptrB++; + break; + + case HAMT_SUBTAG_HEAD_BITMAP: + ASSERT(lvl == 0); + bbm = MAP_HEADER_VAL(hdrB); + ptrB += 2; + break; + + case HAMT_SUBTAG_NODE_BITMAP: + ASSERT(lvl > 0); + bbm = MAP_HEADER_VAL(hdrB); + ptrB += 1; + break; + + default: + erl_exit(1, "bad header tag %ld\r\n", *ptrB & _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); + } + + 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); + } else { + array[ix++] = *ptrA++; + } + } else { + ASSERT(bbm & bit); + array[ix++] = *ptrB++; + } + }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, array, ix * sizeof(Eterm)); + return make_boxed(nhp); +} + typedef void hashmap_doer(Eterm*, void*); static void hashmap_do_foreach(Eterm node, hashmap_doer* fptr, void* farg) { |