diff options
-rw-r--r-- | erts/emulator/beam/erl_hashmap.c | 54 | ||||
-rw-r--r-- | erts/emulator/beam/erl_hashmap.h | 43 | ||||
-rw-r--r-- | erts/emulator/beam/erl_term.h | 24 | ||||
-rw-r--r-- | erts/emulator/beam/external.c | 1 | ||||
-rw-r--r-- | erts/emulator/beam/utils.c | 1 |
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__ |