aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--erts/emulator/beam/erl_hashmap.c54
-rw-r--r--erts/emulator/beam/erl_hashmap.h43
-rw-r--r--erts/emulator/beam/erl_term.h24
-rw-r--r--erts/emulator/beam/external.c1
-rw-r--r--erts/emulator/beam/utils.c1
5 files changed, 74 insertions, 49 deletions
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index ddb55c53ce..5646820ae1 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -84,7 +84,7 @@ 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);
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);
@@ -831,7 +831,7 @@ static Eterm hashmap_from_list(Process *p, Eterm list) {
Eterm *hp;
Eterm tmp[2];
Uint32 sw, hx;
- Uint jx = 0, ix = 0, lx, cx, n = 0;
+ Uint ix = 0, n = 0;
hxnode_t *hxns;
/* Calculate size and check validity */
@@ -880,6 +880,47 @@ static Eterm hashmap_from_list(Process *p, Eterm list) {
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);
@@ -931,6 +972,7 @@ static Eterm hashmap_from_list(Process *p, Eterm list) {
/* 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));
@@ -940,15 +982,9 @@ static Eterm hashmap_from_list(Process *p, Eterm list) {
res = make_hashmap(hp);
}
- erts_free(ERTS_ALC_T_TMP, (void *) hxns);
- ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-
- BIF_RET(res);
-error:
- BIF_ERROR(p, BADARG);
+ 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;
diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h
index f05505bae0..b5fbc636e6 100644
--- a/erts/emulator/beam/erl_hashmap.h
+++ b/erts/emulator/beam/erl_hashmap.h
@@ -22,21 +22,14 @@
#define __ERL_HASH_H__
#include "sys.h"
+#include "erl_term.h"
Eterm erts_hashmap_get(Eterm key, Eterm map);
struct ErtsWStack_;
void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node);
Eterm* hashmap_iterator_next(struct ErtsWStack_* s);
int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp);
-
-/* erl_term.h stuff */
-#define make_hashmap(x) make_boxed((Eterm*)(x))
-#define make_hashmap_rel make_boxed_rel
-#define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x))))
-#define is_hashmap_rel(RTERM,BASE) is_hashmap(rterm2wterm(RTERM,BASE))
-#define is_hashmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HASHMAP)
-#define hashmap_val(x) _unchecked_boxed_val((x))
-#define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE))
+Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
/* HASH */
@@ -54,8 +47,8 @@ Uint32 hashmap_bitcount(Uint32 x);
* head
*/
-/* the head-node is a bitmap or array with an untagged size
- */
+/* the head-node is a bitmap or array with an untagged size */
+
typedef struct hashmap_head_s {
Eterm thing_word;
Uint size;
@@ -65,21 +58,6 @@ typedef struct hashmap_head_s {
#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size)
#define hashmap_size_rel(RTERM, BASE) hashmap_size(rterm2wterm(RTERM, BASE))
-/* the bitmap-node
- * typedef struct hashmap_bitmap_node_s {
- * Eterm thing_word;
- * Eterm items[1];
- * } hashmap_bitmap_node_t;
- *
- * the array-node is a tuple
- * typedef struct hashmap_bitmap_node_s {
- * Eterm thing_word;
- * Eterm items[1];
- * } hashmap_bitmap_node_t;
- *
- * the leaf-node
- * cons-cell
- */
/* thing_word tagscheme
* Need two bits for map subtags
@@ -103,19 +81,6 @@ typedef struct hashmap_head_s {
/* erl_map.h stuff */
-#define MAP_HEADER_TAG_SZ (2)
-#define MAP_HEADER_ARITY_SZ (8)
-#define MAP_HEADER_VAL_SZ (16)
-
-#define MAP_HEADER_TAG_FLAT (0x0)
-#define MAP_HEADER_TAG_HAMT_NODE_BITMAP (0x1)
-#define MAP_HEADER_TAG_HAMT_HEAD_ARRAY (0x2)
-#define MAP_HEADER_TAG_HAMT_HEAD_BITMAP (0x3)
-
-#define MAP_HEADER_TYPE(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS)) & (0x3))
-#define MAP_HEADER_ARITY(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ)) & (0xff))
-#define MAP_HEADER_VAL(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ + MAP_HEADER_ARITY_SZ)) & (0xffff))
-
#define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2)))
#define MAKE_MAP_HEADER(Type,Arity,Val) \
diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h
index 72946d9ddf..7605a41cd8 100644
--- a/erts/emulator/beam/erl_term.h
+++ b/erts/emulator/beam/erl_term.h
@@ -21,7 +21,6 @@
#define __ERL_TERM_H
#include "sys.h" /* defines HALFWORD_HEAP */
-#include "erl_hashmap.h"
typedef UWord Wterm; /* Full word terms */
@@ -996,6 +995,29 @@ _ET_DECLARE_CHECKED(Uint32*,external_ref_data,Wterm)
_ET_DECLARE_CHECKED(struct erl_node_*,external_ref_node,Eterm)
#define external_ref_node(x) _ET_APPLY(external_ref_node,(x))
+/* maps */
+
+#define MAP_HEADER_TAG_SZ (2)
+#define MAP_HEADER_ARITY_SZ (8)
+#define MAP_HEADER_VAL_SZ (16)
+
+#define MAP_HEADER_TAG_FLAT (0x0)
+#define MAP_HEADER_TAG_HAMT_NODE_BITMAP (0x1)
+#define MAP_HEADER_TAG_HAMT_HEAD_ARRAY (0x2)
+#define MAP_HEADER_TAG_HAMT_HEAD_BITMAP (0x3)
+
+#define MAP_HEADER_TYPE(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS)) & (0x3))
+#define MAP_HEADER_ARITY(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ)) & (0xff))
+#define MAP_HEADER_VAL(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ + MAP_HEADER_ARITY_SZ)) & (0xffff))
+
+#define make_hashmap(x) make_boxed((Eterm*)(x))
+#define make_hashmap_rel make_boxed_rel
+#define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x))))
+#define is_hashmap_rel(RTERM,BASE) is_hashmap(rterm2wterm(RTERM,BASE))
+#define is_hashmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HASHMAP)
+#define hashmap_val(x) _unchecked_boxed_val((x))
+#define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE))
+
/* number tests */
#define is_integer(x) (is_small(x) || is_big(x))
diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index af8db4c265..9030b528a4 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -45,6 +45,7 @@
#include "erl_bits.h"
#include "erl_zlib.h"
#include "erl_map.h"
+#include "erl_hashmap.h"
#define in_area(ptr,start,nbytes) ((UWord)((char*)(ptr) - (char*)(start)) < (nbytes))
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index d234e8fc68..f595cfbacd 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -32,6 +32,7 @@
#include "erl_binary.h"
#include "erl_bits.h"
#include "erl_map.h"
+#include "erl_hashmap.h"
#include "packet_parser.h"
#include "erl_gc.h"
#define ERTS_WANT_DB_INTERNAL__