From 1b963c425591b75410fe46d9af3b44e47692059e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 23 Feb 2015 15:49:43 +0100 Subject: erts: Move hashmap:remove/2 to maps --- erts/emulator/beam/bif.tab | 1 - erts/emulator/beam/erl_hashmap.c | 258 --------------------------------------- erts/emulator/beam/erl_map.c | 257 +++++++++++++++++++++++++++++++++++++- 3 files changed, 255 insertions(+), 261 deletions(-) diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 55a7b62e7d..320cd39da8 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -615,7 +615,6 @@ bif erlang:fun_info_mfa/1 bif erlang:get_keys/0 # Hash Array Mappped Trie -bif hashmap:remove/2 bif hashmap:info/1 bif hashmap:from_list/1 bif hashmap:new/0 diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c index 594a404e9f..9b16a5a88f 100644 --- a/erts/emulator/beam/erl_hashmap.c +++ b/erts/emulator/beam/erl_hashmap.c @@ -69,7 +69,6 @@ typedef struct { Eterm val; } hxnode_t; -static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); static Eterm hashmap_from_list(Process *p, Eterm node); static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); @@ -115,14 +114,6 @@ BIF_RETTYPE hashmap_from_list_1(BIF_ALIST_1) { /* hashmap:remove/2 */ -BIF_RETTYPE hashmap_remove_2(BIF_ALIST_2) { - if (is_hashmap(BIF_ARG_2)) { - Uint32 hx = hashmap_make_hash(BIF_ARG_1); - - BIF_RET(hashmap_delete(BIF_P, hx, BIF_ARG_1, BIF_ARG_2)); - } - BIF_ERROR(BIF_P, BADARG); -} /* hashmap:size/1 */ /* erlang:is_hashmap/1 */ @@ -143,255 +134,6 @@ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) { /* impl. */ -static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) { - Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL; - Eterm th[2]; - Eterm *ptr; - Eterm hdr,res = node; - Uint32 ix, bp, hval; - Uint slot, lvl = 0; - Uint size = 0, n = 0; - DECLARE_ESTACK(stack); - - for (;;) { - switch(primary_tag(node)) { - case TAG_PRIMARY_LIST: - if (EQ(CAR(list_val(node)), key)) { - goto unroll; - } - goto not_found; - case TAG_PRIMARY_BOXED: - ptr = boxed_val(node); - hdr = *ptr; - ASSERT(is_header(hdr)); - - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - size += HAMT_NODE_ARRAY_SZ; - ESTACK_PUSH2(stack, ix, node); - node = ptr[ix+1]; - break; - case HAMT_SUBTAG_HEAD_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - size += HAMT_HEAD_ARRAY_SZ; - ESTACK_PUSH2(stack, ix, node); - node = ptr[ix+2]; - break; - case HAMT_SUBTAG_NODE_BITMAP: - hval = MAP_HEADER_VAL(hdr); - ix = hashmap_index(hx); - bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - n = hashmap_bitcount(hval); - - ESTACK_PUSH(stack, n); - ESTACK_PUSH3(stack, bp, slot, node); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+1]; - ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); - size += HAMT_NODE_BITMAP_SZ(n); - break; - } - /* not occupied */ - goto not_found; - case HAMT_SUBTAG_HEAD_BITMAP: - hval = MAP_HEADER_VAL(hdr); - ix = hashmap_index(hx); - bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - n = hashmap_bitcount(hval); - - ESTACK_PUSH(stack, n); - ESTACK_PUSH3(stack, bp, slot, node); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+2]; - ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); - size += HAMT_HEAD_BITMAP_SZ(n); - break; - } - /* not occupied */ - goto not_found; - default: - erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); - break; - } - break; - default: - erl_exit(1, "bad primary tag %p\r\n", node); - break; - } - } - -unroll: - /* the size is bounded and atleast one less than the previous size */ - size -= 1; - hp = HAlloc(p, size); - hp_end = hp + size; - res = THE_NON_VALUE; - - do { - node = ESTACK_POP(stack); - - /* all nodes are things */ - ptr = boxed_val(node); - hdr = *ptr; - ASSERT(is_header(hdr)); - - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - ix = (Uint) ESTACK_POP(stack); - nhp = hp; - if (res == THE_NON_VALUE) { - *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(0xffff ^ (1 << ix)); ptr++; - n = 16; - n -= ix; - while(ix--) { *hp++ = *ptr++; } - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - res = make_hashmap(nhp); - } else { - n = HAMT_NODE_ARRAY_SZ; - while(n--) { *hp++ = *ptr++; } - nhp[ix+1] = res; - res = make_hashmap(nhp); - } - break; - case HAMT_SUBTAG_HEAD_ARRAY: - ix = (Uint) ESTACK_POP(stack); - nhp = hp; - if (res == THE_NON_VALUE) { - n = 16; - n -= ix; - *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(0xffff ^ (1 << ix)); ptr++; - *hp++ = (*ptr++) - 1; - while(ix--) { *hp++ = *ptr++; } - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - res = make_hashmap(nhp); - } else { - n = 16; - *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++; - *hp++ = (*ptr++) - 1; - while(n--) { *hp++ = *ptr++; } - nhp[ix+2] = res; - res = make_hashmap(nhp); - } - break; - case HAMT_SUBTAG_NODE_BITMAP: - slot = (Uint) ESTACK_POP(stack); - bp = (Uint32) ESTACK_POP(stack); - n = (Uint32) ESTACK_POP(stack); - nhp = hp; - - /* bitmap change matrix - * res | none leaf bitmap - * ---------------------------- - * n=1 | remove remove keep - * n=2 | other keep keep - * n>2 | shrink keep keep - * - * other: (remember, n is 2) - * shrink if the other bitmap value is a bitmap node - * remove if the other bitmap value is a leaf - * - * remove: - * this bitmap node is removed, res is moved up in tree (could be none) - * this is a special case of shrink - * - * keep: - * the current path index is still used down in the tree, need to keep it - * copy as usual with the updated res - * - * shrink: - * the current path index is no longer used down in the tree, remove it (shrink) - */ - if (res == THE_NON_VALUE) { - if (n == 1) { - break; - } else if (n == 2) { - if (slot == 0) { - ix = 2; /* off by one 'cause hdr */ - } else { - ix = 1; /* off by one 'cause hdr */ - } - if (primary_tag(ptr[ix]) == TAG_PRIMARY_LIST) { - res = ptr[ix]; - } else { - hval = MAP_HEADER_VAL(hdr); - *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); - *hp++ = ptr[ix]; - res = make_hashmap(nhp); - } - } else { - /* n > 2 */ - hval = MAP_HEADER_VAL(hdr); - *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); ptr++; - n -= slot; - while(slot--) { *hp++ = *ptr++; } - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - res = make_hashmap(nhp); - } - } else if (primary_tag(res) == TAG_PRIMARY_LIST && n == 1) { - break; - } else { - /* res is bitmap or leaf && n > 1, keep */ - n -= slot; - *hp++ = *ptr++; - while(slot--) { *hp++ = *ptr++; } - *hp++ = res; - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - res = make_hashmap(nhp); - } - break; - case HAMT_SUBTAG_HEAD_BITMAP: - slot = (Uint) ESTACK_POP(stack); - bp = (Uint32) ESTACK_POP(stack); - n = (Uint32) ESTACK_POP(stack); - nhp = hp; - - if (res != THE_NON_VALUE) { - *hp++ = *ptr++; - *hp++ = (*ptr++) - 1; - n -= slot; - while(slot--) { *hp++ = *ptr++; } - *hp++ = res; - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - } else { - hval = MAP_HEADER_VAL(hdr); - *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval ^ bp); ptr++; - *hp++ = (*ptr++) - 1; - n -= slot; - while(slot--) { *hp++ = *ptr++; } - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - } - res = make_hashmap(nhp); - break; - default: - erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); - break; - } - } while(!ESTACK_ISEMPTY(stack)); - HRelease(p, hp_end, hp); -not_found: - DESTROY_ESTACK(stack); - ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); - ERTS_HOLE_CHECK(p); - return res; -} - #define swizzle32(D,S) \ do { \ (D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20 \ diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 8c44f45125..672ac9f513 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -68,6 +68,7 @@ static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm 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_delete(Process *p, Uint32 hx, Eterm key, Eterm node); /* erlang:map_size/1 * the corresponding instruction is implemented in: @@ -495,8 +496,7 @@ BIF_RETTYPE maps_put_3(BIF_ALIST_3) { BIF_ERROR(BIF_P, BADARG); } -/* maps:remove/3 - */ +/* maps:remove/3 */ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { Sint n; @@ -579,6 +579,9 @@ BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) { BIF_RET(res); } + } else if (is_hashmap(BIF_ARG_2)) { + Uint32 hx = hashmap_make_hash(BIF_ARG_1); + BIF_RET(hashmap_delete(BIF_P, hx, BIF_ARG_1, BIF_ARG_2)); } BIF_ERROR(BIF_P, BADARG); } @@ -1245,6 +1248,256 @@ static Eterm hashmap_values(Process* p, Eterm node) { return res; } +static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node) { + Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL; + Eterm th[2]; + Eterm *ptr; + Eterm hdr,res = node; + Uint32 ix, bp, hval; + Uint slot, lvl = 0; + Uint size = 0, n = 0; + DECLARE_ESTACK(stack); + + for (;;) { + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: + if (EQ(CAR(list_val(node)), key)) { + goto unroll; + } + goto not_found; + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_NODE_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(th,hx,lvl,key); + size += HAMT_NODE_ARRAY_SZ; + ESTACK_PUSH2(stack, ix, node); + node = ptr[ix+1]; + break; + case HAMT_SUBTAG_HEAD_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(th,hx,lvl,key); + size += HAMT_HEAD_ARRAY_SZ; + ESTACK_PUSH2(stack, ix, node); + node = ptr[ix+2]; + break; + case HAMT_SUBTAG_NODE_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + n = hashmap_bitcount(hval); + + ESTACK_PUSH(stack, n); + ESTACK_PUSH3(stack, bp, slot, node); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+1]; + ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); + size += HAMT_NODE_BITMAP_SZ(n); + break; + } + /* not occupied */ + goto not_found; + case HAMT_SUBTAG_HEAD_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + n = hashmap_bitcount(hval); + + ESTACK_PUSH(stack, n); + ESTACK_PUSH3(stack, bp, slot, node); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+2]; + ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); + size += HAMT_HEAD_BITMAP_SZ(n); + break; + } + /* not occupied */ + goto not_found; + default: + erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); + break; + } + break; + default: + erl_exit(1, "bad primary tag %p\r\n", node); + break; + } + } + +unroll: + /* the size is bounded and atleast one less than the previous size */ + size -= 1; + hp = HAlloc(p, size); + hp_end = hp + size; + res = THE_NON_VALUE; + + do { + node = ESTACK_POP(stack); + + /* all nodes are things */ + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_NODE_ARRAY: + ix = (Uint) ESTACK_POP(stack); + nhp = hp; + if (res == THE_NON_VALUE) { + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(0xffff ^ (1 << ix)); ptr++; + n = 16; + n -= ix; + while(ix--) { *hp++ = *ptr++; } + ptr++; n--; + while(n--) { *hp++ = *ptr++; } + res = make_hashmap(nhp); + } else { + n = HAMT_NODE_ARRAY_SZ; + while(n--) { *hp++ = *ptr++; } + nhp[ix+1] = res; + res = make_hashmap(nhp); + } + break; + case HAMT_SUBTAG_HEAD_ARRAY: + ix = (Uint) ESTACK_POP(stack); + nhp = hp; + if (res == THE_NON_VALUE) { + n = 16; + n -= ix; + *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(0xffff ^ (1 << ix)); ptr++; + *hp++ = (*ptr++) - 1; + while(ix--) { *hp++ = *ptr++; } + ptr++; n--; + while(n--) { *hp++ = *ptr++; } + res = make_hashmap(nhp); + } else { + n = 16; + *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++; + *hp++ = (*ptr++) - 1; + while(n--) { *hp++ = *ptr++; } + nhp[ix+2] = res; + res = make_hashmap(nhp); + } + break; + case HAMT_SUBTAG_NODE_BITMAP: + slot = (Uint) ESTACK_POP(stack); + bp = (Uint32) ESTACK_POP(stack); + n = (Uint32) ESTACK_POP(stack); + nhp = hp; + + /* bitmap change matrix + * res | none leaf bitmap + * ---------------------------- + * n=1 | remove remove keep + * n=2 | other keep keep + * n>2 | shrink keep keep + * + * other: (remember, n is 2) + * shrink if the other bitmap value is a bitmap node + * remove if the other bitmap value is a leaf + * + * remove: + * this bitmap node is removed, res is moved up in tree (could be none) + * this is a special case of shrink + * + * keep: + * the current path index is still used down in the tree, need to keep it + * copy as usual with the updated res + * + * shrink: + * the current path index is no longer used down in the tree, remove it (shrink) + */ + if (res == THE_NON_VALUE) { + if (n == 1) { + break; + } else if (n == 2) { + if (slot == 0) { + ix = 2; /* off by one 'cause hdr */ + } else { + ix = 1; /* off by one 'cause hdr */ + } + if (primary_tag(ptr[ix]) == TAG_PRIMARY_LIST) { + res = ptr[ix]; + } else { + hval = MAP_HEADER_VAL(hdr); + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); + *hp++ = ptr[ix]; + res = make_hashmap(nhp); + } + } else { + /* n > 2 */ + hval = MAP_HEADER_VAL(hdr); + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); ptr++; + n -= slot; + while(slot--) { *hp++ = *ptr++; } + ptr++; n--; + while(n--) { *hp++ = *ptr++; } + res = make_hashmap(nhp); + } + } else if (primary_tag(res) == TAG_PRIMARY_LIST && n == 1) { + break; + } else { + /* res is bitmap or leaf && n > 1, keep */ + n -= slot; + *hp++ = *ptr++; + while(slot--) { *hp++ = *ptr++; } + *hp++ = res; + ptr++; n--; + while(n--) { *hp++ = *ptr++; } + res = make_hashmap(nhp); + } + break; + case HAMT_SUBTAG_HEAD_BITMAP: + slot = (Uint) ESTACK_POP(stack); + bp = (Uint32) ESTACK_POP(stack); + n = (Uint32) ESTACK_POP(stack); + nhp = hp; + + if (res != THE_NON_VALUE) { + *hp++ = *ptr++; + *hp++ = (*ptr++) - 1; + n -= slot; + while(slot--) { *hp++ = *ptr++; } + *hp++ = res; + ptr++; n--; + while(n--) { *hp++ = *ptr++; } + } else { + hval = MAP_HEADER_VAL(hdr); + *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval ^ bp); ptr++; + *hp++ = (*ptr++) - 1; + n -= slot; + while(slot--) { *hp++ = *ptr++; } + ptr++; n--; + while(n--) { *hp++ = *ptr++; } + } + res = make_hashmap(nhp); + break; + default: + erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); + break; + } + } while(!ESTACK_ISEMPTY(stack)); + HRelease(p, hp_end, hp); +not_found: + DESTROY_ESTACK(stack); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + ERTS_HOLE_CHECK(p); + return res; +} + + int erts_validate_and_sort_map(map_t* mp) { Eterm *ks = map_get_keys(mp); -- cgit v1.2.3