aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/bif.tab1
-rw-r--r--erts/emulator/beam/erl_hashmap.c472
-rw-r--r--erts/emulator/beam/erl_hashmap.h12
-rw-r--r--erts/emulator/beam/erl_map.c442
-rw-r--r--erts/emulator/beam/erl_map.h13
5 files changed, 454 insertions, 486 deletions
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 320cd39da8..7e92e58cab 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -616,7 +616,6 @@ bif erlang:get_keys/0
# Hash Array Mappped Trie
bif hashmap:info/1
-bif hashmap:from_list/1
bif hashmap:new/0
bif hashmap:merge/2
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 9b16a5a88f..06012950e1 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -61,22 +61,8 @@ static char *format_binary(Uint64 x, char *b) {
#endif
-/* for hashmap_from_list/1 */
-typedef struct {
- Uint32 hx;
- Uint32 skip;
- Uint i;
- Eterm val;
-} hxnode_t;
-
-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[]);
-static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n);
-static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int is_root);
-static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root);
-static int hxnodecmp(hxnode_t* a, hxnode_t* b);
-static int hxnodecmpkey(hxnode_t* a, hxnode_t* b);
/* hashmap:new/0 */
@@ -101,13 +87,6 @@ BIF_RETTYPE hashmap_new_0(BIF_ALIST_0) {
/* hashmap:from_list/1 */
-BIF_RETTYPE hashmap_from_list_1(BIF_ALIST_1) {
- if (is_list(BIF_ARG_1) || is_nil(BIF_ARG_1)) {
- return hashmap_from_list(BIF_P, BIF_ARG_1);
- }
-
- BIF_ERROR(BIF_P, BADARG);
-}
/* hashmap:get/2 */
/* hashmap:find/2 */
@@ -134,435 +113,11 @@ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) {
/* impl. */
-#define swizzle32(D,S) \
- do { \
- (D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20 \
- | ((S) & 0x00000f00) << 12 | ((S) & 0x0000f000) << 4 \
- | ((S) & 0x000f0000) >> 4 | ((S) & 0x00f00000) >> 12 \
- | ((S) & 0x0f000000) >> 20 | ((S) & 0xf0000000) >> 28; \
- } while(0)
-
-
-static Eterm hashmap_from_list(Process *p, Eterm list) {
- Eterm *kv, res, item = list;
- Eterm *hp;
- Eterm tmp[2];
- Uint32 sw, hx;
- Uint ix = 0, n = 0;
- hxnode_t *hxns;
-
- /* Calculate size and check validity */
-
- if (is_nil(list)) {
- hp = HAlloc(p, HAMT_HEAD_EMPTY_SZ);
- hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0);
- hp[1] = 0;
- return make_hashmap(hp);
- }
-
- while(is_list(item)) {
- res = CAR(list_val(item));
- if (is_not_tuple(res))
- goto error;
-
- kv = tuple_val(res);
- if (*kv != make_arityval(2))
- goto error;
-
- n++;
- item = CDR(list_val(item));
- }
-
- if (is_not_nil(item))
- goto error;
-
- hp = HAlloc(p, (2 * n));
-
- /* create tmp hx values and leaf ptrs */
- hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
- item = list;
-
- while(is_list(item)) {
- res = CAR(list_val(item));
- kv = tuple_val(res);
- hx = hashmap_restore_hash(tmp,0,kv[1]);
- swizzle32(sw,hx);
- hxns[ix].hx = sw;
- hxns[ix].val = CONS(hp, kv[1], kv[2]); hp += 2;
- hxns[ix].skip = 1; /* will be reassigned in from_array */
- hxns[ix].i = ix;
- ix++;
- item = CDR(list_val(item));
- }
-
- ASSERT(n > 0);
-
- res = hashmap_from_unsorted_array(p, hxns, n);
-
- erts_free(ERTS_ALC_T_TMP, (void *) hxns);
- ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-
- BIF_RET(res);
-error:
- BIF_ERROR(p, BADARG);
-}
-
-Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) {
- Eterm tmp[2];
- Uint32 sw, hx;
- Uint ix;
- hxnode_t *hxns;
- Eterm res;
-
- /* create tmp hx values and leaf ptrs */
- hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
-
- for (ix = 0; ix < n; ix++) {
- hx = hashmap_restore_hash(tmp,0,CAR(list_val(leafs[ix])));
- swizzle32(sw,hx);
- hxns[ix].hx = sw;
- hxns[ix].val = leafs[ix];
- hxns[ix].skip = 1;
- hxns[ix].i = ix;
- }
-
- res = hashmap_from_unsorted_array(p, hxns, n);
-
- erts_free(ERTS_ALC_T_TMP, (void *) hxns);
- ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-
- return res;
-}
-
-static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
- Uint jx = 0, ix = 0, lx, cx;
- Eterm res;
-
- /* sort and compact array (remove non-unique entries) */
- qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
-
- ix = 0, cx = 0;
- while(ix < n - 1) {
- if (hxns[ix].hx == hxns[ix+1].hx) {
-
- /* find region of equal hash values */
- jx = ix + 1;
- while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
- /* find all correct keys from region
- * (last in list but now hash sorted so we check highest id instead) */
-
- /* resort with keys instead of hash value within region */
-
- qsort(&hxns[ix], jx - ix, sizeof(hxnode_t),
- (int (*)(const void *, const void *)) hxnodecmpkey);
-
- while(ix < jx) {
- lx = ix;
- while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) {
- if (hxns[ix].i > hxns[lx].i) {
- lx = ix;
- }
- ix++;
- }
- hxns[cx].hx = hxns[lx].hx;
- hxns[cx].val = hxns[lx].val;
- cx++;
- }
- ix = jx;
- continue;
- }
- if (ix > cx) {
- hxns[cx].hx = hxns[ix].hx;
- hxns[cx].val = hxns[ix].val;
- }
- cx++;
- ix++;
- }
-
- if (ix < n) {
- hxns[cx].hx = hxns[ix].hx;
- hxns[cx].val = hxns[ix].val;
- cx++;
- }
-
- if (cx > 1) {
- /* recursive decompose array */
- res = hashmap_from_sorted_unique_array(p, hxns, cx, 0);
- } else {
- Eterm *hp;
- /* hash value has been swizzled, need to drag it down to get the
- * correct slot. */
- hp = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1));
- hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf));
- hp[1] = 1;
- hp[2] = hxns[0].val;
- res = make_hashmap(hp);
- }
-
- return res;
-}
-
-static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) {
- Eterm res = NIL;
- Uint i,ix,jx,elems;
- Uint32 sw, hx;
- Eterm val;
- Eterm th[2];
- hxnode_t *tmp;
-
- ASSERT(lvl < 32);
- ix = 0;
- elems = 1;
- while (ix < n - 1) {
- if (hxns[ix].hx == hxns[ix+1].hx) {
- jx = ix + 1;
- while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
- tmp = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, ((jx - ix)) * sizeof(hxnode_t));
-
- for(i = 0; i < jx - ix; i++) {
- val = hxns[i + ix].val;
- hx = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val)));
- swizzle32(sw,hx);
- tmp[i].hx = sw;
- tmp[i].val = val;
- tmp[i].i = i;
- tmp[i].skip = 1;
- }
-
- qsort(tmp, jx - ix, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
-
- hxns[ix].skip = jx - ix;
- hxns[ix].val = hashmap_from_sorted_unique_array(p, tmp, jx - ix, lvl + 8);
- erts_free(ERTS_ALC_T_TMP, (void *) tmp);
- ix = jx;
- if (ix < n) { elems++; }
- continue;
- }
- hxns[ix].skip = 1;
- elems++;
- ix++;
- }
-
- res = hashmap_from_chunked_array(p, hxns, elems, !lvl);
-
- ERTS_HOLE_CHECK(p);
-
- return res;
-}
-
-#define maskval(V,L) (((V) >> ((7 - (L))*4)) & 0xf)
-#define cdepth(V1,V2) (hashmap_clz((V1) ^ (V2)) >> 2)
-
/* n must be > 1
* hash values in hxns has to be unique
*/
#define HALLOC_EXTRA 200
-static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) {
- Uint ix, d, dn, dc, slot, elems;
- Uint32 v, vp, vn, hdr;
- Uint bp, sz;
- DECLARE_ESTACK(stack);
- Eterm res = NIL, *hp = NULL, *nhp;
-
- ASSERT(n > 1);
-
- /* push initial nodes on the stack,
- * this is the starting depth */
-
- ix = 0;
- d = 0;
- vp = hxns[ix].hx;
- v = hxns[ix + hxns[ix].skip].hx;
-
- ASSERT(vp > v);
- slot = maskval(vp,d);
-
- while(slot == maskval(v,d)) {
- ESTACK_PUSH(stack, 1 << slot);
- d++;
- slot = maskval(vp,d);
- }
-
- res = hxns[ix].val;
-
- if (hxns[ix].skip > 1) {
- dc = 7;
- /* build collision nodes */
- while (dc > d) {
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
- hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(vp,dc));
- hp[1] = res;
- res = make_hashmap(hp);
- dc--;
- }
- }
-
- ESTACK_PUSH(stack, res);
- ESTACK_PUSH(stack, 1 << slot);
-
- /* all of the other nodes .. */
- elems = n - 2; /* remove first and last elements */
- while(elems--) {
- hdr = ESTACK_POP(stack);
- ix = ix + hxns[ix].skip;
-
- /* determine if node or subtree should be built by looking
- * at the next value. */
-
- vn = hxns[ix + hxns[ix].skip].hx;
- dn = cdepth(v,vn);
- ASSERT(v > vn);
-
- res = hxns[ix].val;
-
- if (hxns[ix].skip > 1) {
- int wat = (d > dn) ? d : dn;
- dc = 7;
- /* build collision nodes */
- while (dc > wat) {
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
- hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
- hp[1] = res;
- res = make_hashmap(hp);
- dc--;
- }
- }
-
- /* next depth is higher (implies collision) */
- if (d < dn) {
- /* hdr is the popped one initially */
- while(d < dn) {
- slot = maskval(v, d);
- bp = 1 << slot;
- ESTACK_PUSH(stack, hdr | bp);
- d++;
- hdr = 0; /* clear hdr for all other collisions */
- }
-
- slot = maskval(v, d);
- bp = 1 << slot;
- /* no more collisions */
- ESTACK_PUSH(stack,res);
- ESTACK_PUSH(stack,bp);
- } else if (d == dn) {
- /* no collisions at all */
- slot = maskval(v, d);
- bp = 1 << slot;
- ESTACK_PUSH(stack,res);
- ESTACK_PUSH(stack,hdr | bp);
- } else {
- /* dn < n, we have a drop and we are done
- * build nodes and subtree */
- while (dn != d) {
- slot = maskval(v, d);
- bp = 1 << slot;
- /* OR bitposition before sz calculation to handle
- * redundant collisions */
- hdr |= bp;
- sz = hashmap_bitcount(hdr);
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
- nhp = hp;
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
- *hp++ = res; sz--;
- while (sz--) { *hp++ = ESTACK_POP(stack); }
- ASSERT((hp - nhp) < 18);
- res = make_hashmap(nhp);
-
- /* we need to pop the next hdr and push if we don't need it */
-
- hdr = ESTACK_POP(stack);
- d--;
- }
- ESTACK_PUSH(stack, res);
- ESTACK_PUSH(stack, hdr);
- }
-
- vp = v;
- v = vn;
- d = dn;
- ERTS_HOLE_CHECK(p);
- }
-
- /* v and vp are reused from above */
- dn = cdepth(vp,v);
- ix = ix + hxns[ix].skip;
- res = hxns[ix].val;
-
- if (hxns[ix].skip > 1) {
- dc = 7;
- /* build collision nodes */
- while (dc > dn) {
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
- hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
- hp[1] = res;
- res = make_hashmap(hp);
- dc--;
- }
- }
-
- hdr = ESTACK_POP(stack);
- /* pop remaining subtree if any */
- while (dn) {
- slot = maskval(v, dn);
- bp = 1 << slot;
- /* OR bitposition before sz calculation to handle
- * redundant collisions */
- hdr |= bp;
- sz = hashmap_bitcount(hdr);
- hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
- nhp = hp;
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
- *hp++ = res; sz--;
-
- while (sz--) { *hp++ = ESTACK_POP(stack); }
- res = make_hashmap(nhp);
- hdr = ESTACK_POP(stack);
- dn--;
- }
-
- /* and finally the root .. */
-
- slot = maskval(v, dn);
- bp = 1 << slot;
- hdr |= bp;
- sz = hashmap_bitcount(hdr);
- hp = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1));
- nhp = hp;
-
- if (is_root) {
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
- *hp++ = n;
- } else {
- *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
- }
-
- *hp++ = res; sz--;
- while (sz--) { *hp++ = ESTACK_POP(stack); }
-
- res = make_hashmap(nhp);
-
- ASSERT(ESTACK_COUNT(stack) == 0);
- DESTROY_ESTACK(stack);
- ERTS_HOLE_CHECK(p);
- return res;
-}
-#undef HALLOC_EXTRA
-
-static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) {
- return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
-}
-
-static int hxnodecmp(hxnode_t *a, hxnode_t *b) {
- if (a->hx < b->hx)
- return 1;
- else if (a->hx == b->hx)
- return 0;
- else
- return -1;
-}
-
-#define HALLOC_EXTRA 200
static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
#define PSTACK_TYPE struct HashmapMergePStackType
@@ -938,30 +493,3 @@ BIF_RETTYPE hashmap_info_1(BIF_ALIST_1) {
}
BIF_ERROR(BIF_P, BADARG);
}
-
-/* implementation of builtin emulations */
-
-#if !defined(__GNUC__)
-/* Count leading zeros emulation */
-Uint32 hashmap_clz(Uint32 x) {
- Uint32 y;
- int n = 32;
- y = x >>16; if (y != 0) {n = n -16; x = y;}
- y = x >> 8; if (y != 0) {n = n - 8; x = y;}
- y = x >> 4; if (y != 0) {n = n - 4; x = y;}
- y = x >> 2; if (y != 0) {n = n - 2; x = y;}
- y = x >> 1; if (y != 0) return n - 2;
- return n - x;
-}
-const Uint32 SK5 = 0x55555555, SK3 = 0x33333333;
-const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF;
-
-/* CTPOP emulation */
-Uint32 hashmap_bitcount(Uint32 x) {
- x -= ((x >> 1 ) & SK5);
- x = (x & SK3 ) + ((x >> 2 ) & SK3 );
- x = (x & SKF0) + ((x >> 4 ) & SKF0);
- x += x >> 8;
- return (x + (x >> 16)) & 0x3F;
-}
-#endif
diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h
index 5a9aa05f61..7ac33b34b0 100644
--- a/erts/emulator/beam/erl_hashmap.h
+++ b/erts/emulator/beam/erl_hashmap.h
@@ -24,20 +24,10 @@
#include "sys.h"
#include "erl_term.h"
-Eterm erts_hashmap_get(Eterm key, Eterm map);
int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp);
-Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
/* HASH */
-#if defined(__GNUC__)
-#define hashmap_clz(x) ((Uint32) __builtin_clz((unsigned int)(x)))
-#define hashmap_bitcount(x) ((Uint32) __builtin_popcount((unsigned int) (x)))
-#else
-Uint32 hashmap_clz(Uint32 x);
-Uint32 hashmap_bitcount(Uint32 x);
-#endif
-
/* hamt nodes v2.0
*
* node :: leaf | array | bitmap
@@ -49,8 +39,6 @@ typedef struct hashmap_head_s {
Eterm items[1];
} hashmap_head_t;
-
-
/* thing_word tagscheme
* Need two bits for map subtags
*
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 5e5e567642..7281353af5 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -63,6 +63,14 @@
* - erts_internal:map_to_tuple_keys/1
*/
+/* for hashmap_from_list/1 */
+typedef struct {
+ Uint32 hx;
+ Uint32 skip;
+ Uint i;
+ Eterm val;
+} hxnode_t;
+
static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node);
static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update);
static Eterm hashmap_to_list(Process *p, Eterm map);
@@ -70,6 +78,12 @@ 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);
static Eterm map_from_validated_list(Process *p, Eterm list, Uint size);
+static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size);
+static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n);
+static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int is_root);
+static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root);
+static int hxnodecmp(hxnode_t* a, hxnode_t* b);
+static int hxnodecmpkey(hxnode_t* a, hxnode_t* b);
/* erlang:map_size/1
* the corresponding instruction is implemented in:
@@ -250,7 +264,11 @@ BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) {
if (is_not_nil(item))
goto error;
- BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size));
+ if (size > MAP_SMALL_MAP_LIMIT) {
+ BIF_RET(hashmap_from_validated_list(BIF_P, BIF_ARG_1, size));
+ } else {
+ BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size));
+ }
}
error:
@@ -349,6 +367,401 @@ static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) {
return res;
}
+#define swizzle32(D,S) \
+ do { \
+ (D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20 \
+ | ((S) & 0x00000f00) << 12 | ((S) & 0x0000f000) << 4 \
+ | ((S) & 0x000f0000) >> 4 | ((S) & 0x00f00000) >> 12 \
+ | ((S) & 0x0f000000) >> 20 | ((S) & 0xf0000000) >> 28; \
+ } while(0)
+
+#define maskval(V,L) (((V) >> ((7 - (L))*4)) & 0xf)
+#define cdepth(V1,V2) (hashmap_clz((V1) ^ (V2)) >> 2)
+
+static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
+ Eterm item = list;
+ Eterm *hp;
+ Eterm *kv, res;
+ Eterm tmp[2];
+ Uint32 sw, hx;
+ Uint ix = 0;
+ hxnode_t *hxns;
+
+ ASSERT(size > 0);
+
+ hp = HAlloc(p, (2 * size));
+
+ /* create tmp hx values and leaf ptrs */
+ hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, size * sizeof(hxnode_t));
+
+ while(is_list(item)) {
+ res = CAR(list_val(item));
+ kv = tuple_val(res);
+ hx = hashmap_restore_hash(tmp,0,kv[1]);
+ swizzle32(sw,hx);
+ hxns[ix].hx = sw;
+ hxns[ix].val = CONS(hp, kv[1], kv[2]); hp += 2;
+ hxns[ix].skip = 1; /* will be reassigned in from_array */
+ hxns[ix].i = ix;
+ ix++;
+ item = CDR(list_val(item));
+ }
+
+ res = hashmap_from_unsorted_array(p, hxns, size);
+
+ erts_free(ERTS_ALC_T_TMP, (void *) hxns);
+ ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+
+ return res;
+}
+
+Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) {
+ Eterm tmp[2];
+ Uint32 sw, hx;
+ Uint ix;
+ hxnode_t *hxns;
+ Eterm res;
+
+ /* create tmp hx values and leaf ptrs */
+ hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
+
+ for (ix = 0; ix < n; ix++) {
+ hx = hashmap_restore_hash(tmp,0,CAR(list_val(leafs[ix])));
+ swizzle32(sw,hx);
+ hxns[ix].hx = sw;
+ hxns[ix].val = leafs[ix];
+ hxns[ix].skip = 1;
+ hxns[ix].i = ix;
+ }
+
+ res = hashmap_from_unsorted_array(p, hxns, n);
+
+ erts_free(ERTS_ALC_T_TMP, (void *) hxns);
+ ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+
+ return res;
+}
+
+static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
+ Uint jx = 0, ix = 0, lx, cx;
+ Eterm res;
+
+ /* sort and compact array (remove non-unique entries) */
+ qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
+
+ ix = 0, cx = 0;
+ while(ix < n - 1) {
+ if (hxns[ix].hx == hxns[ix+1].hx) {
+
+ /* find region of equal hash values */
+ jx = ix + 1;
+ while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
+ /* find all correct keys from region
+ * (last in list but now hash sorted so we check highest id instead) */
+
+ /* resort with keys instead of hash value within region */
+
+ qsort(&hxns[ix], jx - ix, sizeof(hxnode_t),
+ (int (*)(const void *, const void *)) hxnodecmpkey);
+
+ while(ix < jx) {
+ lx = ix;
+ while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) {
+ if (hxns[ix].i > hxns[lx].i) {
+ lx = ix;
+ }
+ ix++;
+ }
+ hxns[cx].hx = hxns[lx].hx;
+ hxns[cx].val = hxns[lx].val;
+ cx++;
+ }
+ ix = jx;
+ continue;
+ }
+ if (ix > cx) {
+ hxns[cx].hx = hxns[ix].hx;
+ hxns[cx].val = hxns[ix].val;
+ }
+ cx++;
+ ix++;
+ }
+
+ if (ix < n) {
+ hxns[cx].hx = hxns[ix].hx;
+ hxns[cx].val = hxns[ix].val;
+ cx++;
+ }
+
+ if (cx > 1) {
+ /* recursive decompose array */
+ res = hashmap_from_sorted_unique_array(p, hxns, cx, 0);
+ } else {
+ Eterm *hp;
+ /* hash value has been swizzled, need to drag it down to get the
+ * correct slot. */
+ hp = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1));
+ hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf));
+ hp[1] = 1;
+ hp[2] = hxns[0].val;
+ res = make_hashmap(hp);
+ }
+
+ return res;
+}
+
+static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) {
+ Eterm res = NIL;
+ Uint i,ix,jx,elems;
+ Uint32 sw, hx;
+ Eterm val;
+ Eterm th[2];
+ hxnode_t *tmp;
+
+ ASSERT(lvl < 32);
+ ix = 0;
+ elems = 1;
+ while (ix < n - 1) {
+ if (hxns[ix].hx == hxns[ix+1].hx) {
+ jx = ix + 1;
+ while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
+ tmp = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, ((jx - ix)) * sizeof(hxnode_t));
+
+ for(i = 0; i < jx - ix; i++) {
+ val = hxns[i + ix].val;
+ hx = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val)));
+ swizzle32(sw,hx);
+ tmp[i].hx = sw;
+ tmp[i].val = val;
+ tmp[i].i = i;
+ tmp[i].skip = 1;
+ }
+
+ qsort(tmp, jx - ix, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
+
+ hxns[ix].skip = jx - ix;
+ hxns[ix].val = hashmap_from_sorted_unique_array(p, tmp, jx - ix, lvl + 8);
+ erts_free(ERTS_ALC_T_TMP, (void *) tmp);
+ ix = jx;
+ if (ix < n) { elems++; }
+ continue;
+ }
+ hxns[ix].skip = 1;
+ elems++;
+ ix++;
+ }
+
+ res = hashmap_from_chunked_array(p, hxns, elems, !lvl);
+
+ ERTS_HOLE_CHECK(p);
+
+ return res;
+}
+
+#define HALLOC_EXTRA 200
+static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) {
+ Uint ix, d, dn, dc, slot, elems;
+ Uint32 v, vp, vn, hdr;
+ Uint bp, sz;
+ DECLARE_ESTACK(stack);
+ Eterm res = NIL, *hp = NULL, *nhp;
+
+ ASSERT(n > 1);
+
+ /* push initial nodes on the stack,
+ * this is the starting depth */
+
+ ix = 0;
+ d = 0;
+ vp = hxns[ix].hx;
+ v = hxns[ix + hxns[ix].skip].hx;
+
+ ASSERT(vp > v);
+ slot = maskval(vp,d);
+
+ while(slot == maskval(v,d)) {
+ ESTACK_PUSH(stack, 1 << slot);
+ d++;
+ slot = maskval(vp,d);
+ }
+
+ res = hxns[ix].val;
+
+ if (hxns[ix].skip > 1) {
+ dc = 7;
+ /* build collision nodes */
+ while (dc > d) {
+ hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(vp,dc));
+ hp[1] = res;
+ res = make_hashmap(hp);
+ dc--;
+ }
+ }
+
+ ESTACK_PUSH(stack, res);
+ ESTACK_PUSH(stack, 1 << slot);
+
+ /* all of the other nodes .. */
+ elems = n - 2; /* remove first and last elements */
+ while(elems--) {
+ hdr = ESTACK_POP(stack);
+ ix = ix + hxns[ix].skip;
+
+ /* determine if node or subtree should be built by looking
+ * at the next value. */
+
+ vn = hxns[ix + hxns[ix].skip].hx;
+ dn = cdepth(v,vn);
+ ASSERT(v > vn);
+
+ res = hxns[ix].val;
+
+ if (hxns[ix].skip > 1) {
+ int wat = (d > dn) ? d : dn;
+ dc = 7;
+ /* build collision nodes */
+ while (dc > wat) {
+ hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
+ hp[1] = res;
+ res = make_hashmap(hp);
+ dc--;
+ }
+ }
+
+ /* next depth is higher (implies collision) */
+ if (d < dn) {
+ /* hdr is the popped one initially */
+ while(d < dn) {
+ slot = maskval(v, d);
+ bp = 1 << slot;
+ ESTACK_PUSH(stack, hdr | bp);
+ d++;
+ hdr = 0; /* clear hdr for all other collisions */
+ }
+
+ slot = maskval(v, d);
+ bp = 1 << slot;
+ /* no more collisions */
+ ESTACK_PUSH(stack,res);
+ ESTACK_PUSH(stack,bp);
+ } else if (d == dn) {
+ /* no collisions at all */
+ slot = maskval(v, d);
+ bp = 1 << slot;
+ ESTACK_PUSH(stack,res);
+ ESTACK_PUSH(stack,hdr | bp);
+ } else {
+ /* dn < n, we have a drop and we are done
+ * build nodes and subtree */
+ while (dn != d) {
+ slot = maskval(v, d);
+ bp = 1 << slot;
+ /* OR bitposition before sz calculation to handle
+ * redundant collisions */
+ hdr |= bp;
+ sz = hashmap_bitcount(hdr);
+ hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
+ nhp = hp;
+ *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+ *hp++ = res; sz--;
+ while (sz--) { *hp++ = ESTACK_POP(stack); }
+ ASSERT((hp - nhp) < 18);
+ res = make_hashmap(nhp);
+
+ /* we need to pop the next hdr and push if we don't need it */
+
+ hdr = ESTACK_POP(stack);
+ d--;
+ }
+ ESTACK_PUSH(stack, res);
+ ESTACK_PUSH(stack, hdr);
+ }
+
+ vp = v;
+ v = vn;
+ d = dn;
+ ERTS_HOLE_CHECK(p);
+ }
+
+ /* v and vp are reused from above */
+ dn = cdepth(vp,v);
+ ix = ix + hxns[ix].skip;
+ res = hxns[ix].val;
+
+ if (hxns[ix].skip > 1) {
+ dc = 7;
+ /* build collision nodes */
+ while (dc > dn) {
+ hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
+ hp[1] = res;
+ res = make_hashmap(hp);
+ dc--;
+ }
+ }
+
+ hdr = ESTACK_POP(stack);
+ /* pop remaining subtree if any */
+ while (dn) {
+ slot = maskval(v, dn);
+ bp = 1 << slot;
+ /* OR bitposition before sz calculation to handle
+ * redundant collisions */
+ hdr |= bp;
+ sz = hashmap_bitcount(hdr);
+ hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
+ nhp = hp;
+ *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+ *hp++ = res; sz--;
+
+ while (sz--) { *hp++ = ESTACK_POP(stack); }
+ res = make_hashmap(nhp);
+ hdr = ESTACK_POP(stack);
+ dn--;
+ }
+
+ /* and finally the root .. */
+
+ slot = maskval(v, dn);
+ bp = 1 << slot;
+ hdr |= bp;
+ sz = hashmap_bitcount(hdr);
+ hp = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1));
+ nhp = hp;
+
+ if (is_root) {
+ *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
+ *hp++ = n;
+ } else {
+ *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+ }
+
+ *hp++ = res; sz--;
+ while (sz--) { *hp++ = ESTACK_POP(stack); }
+
+ res = make_hashmap(nhp);
+
+ ASSERT(ESTACK_COUNT(stack) == 0);
+ DESTROY_ESTACK(stack);
+ ERTS_HOLE_CHECK(p);
+ return res;
+}
+#undef HALLOC_EXTRA
+
+static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) {
+ return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
+}
+
+static int hxnodecmp(hxnode_t *a, hxnode_t *b) {
+ if (a->hx < b->hx)
+ return 1;
+ else if (a->hx == b->hx)
+ return 0;
+ else
+ return -1;
+}
/* maps:is_key/2
*/
@@ -1593,3 +2006,30 @@ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) {
}
BIF_ERROR(BIF_P, BADARG);
}
+
+/* implementation of builtin emulations */
+
+#if !defined(__GNUC__)
+/* Count leading zeros emulation */
+Uint32 hashmap_clz(Uint32 x) {
+ Uint32 y;
+ int n = 32;
+ y = x >>16; if (y != 0) {n = n -16; x = y;}
+ y = x >> 8; if (y != 0) {n = n - 8; x = y;}
+ y = x >> 4; if (y != 0) {n = n - 4; x = y;}
+ y = x >> 2; if (y != 0) {n = n - 2; x = y;}
+ y = x >> 1; if (y != 0) return n - 2;
+ return n - x;
+}
+const Uint32 SK5 = 0x55555555, SK3 = 0x33333333;
+const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF;
+
+/* CTPOP emulation */
+Uint32 hashmap_bitcount(Uint32 x) {
+ x -= ((x >> 1 ) & SK5);
+ x = (x & SK3 ) + ((x >> 2 ) & SK3 );
+ x = (x & SKF0) + ((x >> 4 ) & SKF0);
+ x += x >> 8;
+ return (x + (x >> 16)) & 0x3F;
+}
+#endif
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index 48bc316e3b..428cfe9b63 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -22,6 +22,16 @@
#define __ERL_MAP_H__
#include "sys.h"
+
+/* instrinsic wrappers */
+#if defined(__GNUC__)
+#define hashmap_clz(x) ((Uint32) __builtin_clz((unsigned int)(x)))
+#define hashmap_bitcount(x) ((Uint32) __builtin_popcount((unsigned int) (x)))
+#else
+Uint32 hashmap_clz(Uint32 x);
+Uint32 hashmap_bitcount(Uint32 x);
+#endif
+
/* MAP */
typedef struct map_s {
@@ -70,6 +80,7 @@ typedef struct map_s {
#define map_get_keys(x) (((Eterm *)tuple_val(((map_t *)(x))->keys)) + 1)
#define map_get_size(x) (((map_t*)(x))->size)
+#define MAP_SMALL_MAP_LIMIT (32)
#define MAP_HEADER _make_header(1,_TAG_HEADER_MAP)
#define MAP_HEADER_SIZE (sizeof(map_t) / sizeof(Eterm))
@@ -80,6 +91,8 @@ int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res);
int erts_validate_and_sort_map(map_t* map);
void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node);
Eterm* hashmap_iterator_next(struct ErtsWStack_* s);
+Eterm erts_hashmap_get(Eterm key, Eterm map);
+Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
#if HALFWORD_HEAP
const Eterm *