erts: Move hashmap:from_list/1 to maps

1 files changed, 441 insertions, 1 deletions

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