diff options
| author | Björn-Egil Dahlberg <[email protected]> | 2014-01-29 11:15:46 +0100 |
|---|---|---|
| committer | Björn-Egil Dahlberg <[email protected]> | 2014-01-29 11:15:46 +0100 |
| commit | cb50354a9d3463cf07b830ecf28260adc5b361c0 (patch) | |
| tree | 4794bac549046c2b1039ec0ac559b955ad3b31fc /erts/emulator/beam | |
| parent | d960d54f75c51b81a99a1c5cf40c19f2e9d55068 (diff) | |
| parent | cf5bc2e917dbcb2c2841bf07b995efe105bea4be (diff) | |
| download | otp-cb50354a9d3463cf07b830ecf28260adc5b361c0.tar.gz otp-cb50354a9d3463cf07b830ecf28260adc5b361c0.tar.bz2 otp-cb50354a9d3463cf07b830ecf28260adc5b361c0.zip | |
Merge branch 'egil/maps/OTP-11616'
* egil/maps/OTP-11616: (112 commits)
compiler: Add core compile test for maps
compiler: Fix core parse for Maps
compiler: Fixup #map_pair{} spec
erts: Strengthen map_SUITE tests
erts: Update maps_fold test to respect maps:fold/3
stdlib: Make maps:fold/3 order-independent
erts: Fixup enif_make_map_put on windows
erts: Update preloaded erts_internal.beam
hipe: Fixup update cerl pretty printer
erts: Add map construction to driver API
dialyzer: Add maps tests
dialyzer: Remove dead code
dialyzer: Reflect map_pair core changes in dialyzer
hipe: Update cerl pretty printer
compiler: Update inliner tests
compiler: Squash #c_map_pair_*{} to #c_map_pair{}
compiler: Squash #k_map_pair_*{} to #k_map_pair{}
preloaded: Fixup export cmp_term in erts_internal
erts: Change 'size' argument of enif_get_map_size from int* to size_t*
erts: Fix compile error for halfword emulator
...
Diffstat (limited to 'erts/emulator/beam')
27 files changed, 2308 insertions, 111 deletions
diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c index 7fecdd5c5f..89d9442526 100644 --- a/erts/emulator/beam/beam_emu.c +++ b/erts/emulator/beam/beam_emu.c @@ -31,6 +31,7 @@ #include "big.h" #include "beam_load.h" #include "erl_binary.h" +#include "erl_map.h" #include "erl_bits.h" #include "dist.h" #include "beam_bp.h" @@ -701,6 +702,19 @@ extern int count_instructions; Fail; \ } +#define IsMap(Src, Fail) if (is_not_map(Src)) { Fail; } + +#define HasMapField(Src, Key, Fail) if (has_not_map_field(Src, Key)) { Fail; } + +#define GetMapElement(Src, Key, Dst, Fail) \ + do { \ + Eterm _res = get_map_element(Src, Key); \ + if (is_non_value(_res)) { \ + Fail; \ + } \ + Dst = _res; \ + } while (0) + #define IsFunction(X, Action) \ do { \ if ( !(is_any_fun(X)) ) { \ @@ -944,7 +958,13 @@ static BeamInstr* apply_fun(Process* p, Eterm fun, Eterm args, Eterm* reg) NOINLINE; static Eterm new_fun(Process* p, Eterm* reg, ErlFunEntry* fe, int num_free) NOINLINE; - +static Eterm new_map(Process* p, Eterm* reg, BeamInstr* I) NOINLINE; +static Eterm update_map_assoc(Process* p, Eterm* reg, + Eterm map, BeamInstr* I) NOINLINE; +static Eterm update_map_exact(Process* p, Eterm* reg, + Eterm map, BeamInstr* I) NOINLINE; +static int has_not_map_field(Eterm map, Eterm key); +static Eterm get_map_element(Eterm map, Eterm key); /* * Functions not directly called by process_main(). OK to inline. @@ -2323,6 +2343,55 @@ void process_main(void) Goto(*I); } + OpCase(new_map_jdII): { + Eterm res; + + x(0) = r(0); + SWAPOUT; + res = new_map(c_p, reg, I); + SWAPIN; + r(0) = x(0); + StoreResult(res, Arg(1)); + Next(4+Arg(3)); + } + + OpCase(update_map_assoc_jddII): { + Eterm res; + Eterm map; + + GetArg1(1, map); + x(0) = r(0); + SWAPOUT; + res = update_map_assoc(c_p, reg, map, I); + SWAPIN; + if (is_value(res)) { + r(0) = x(0); + StoreResult(res, Arg(2)); + Next(5+Arg(4)); + } else { + goto badarg; + } + } + + OpCase(update_map_exact_jddII): { + Eterm res; + Eterm map; + + GetArg1(1, map); + x(0) = r(0); + SWAPOUT; + res = update_map_exact(c_p, reg, map, I); + SWAPIN; + if (is_value(res)) { + r(0) = x(0); + StoreResult(res, Arg(2)); + Next(5+Arg(4)); + } else { + goto badarg; + } + } + + /* * All guards with zero arguments have special instructions: * self/0 @@ -5031,6 +5100,8 @@ translate_gc_bif(void* gcf) return bit_size_1; } else if (gcf == erts_gc_byte_size_1) { return byte_size_1; + } else if (gcf == erts_gc_map_size_1) { + return map_size_1; } else if (gcf == erts_gc_abs_1) { return abs_1; } else if (gcf == erts_gc_float_1) { @@ -6227,6 +6298,397 @@ new_fun(Process* p, Eterm* reg, ErlFunEntry* fe, int num_free) return make_fun(funp); } +static int has_not_map_field(Eterm map, Eterm key) +{ + map_t* mp; + Eterm* keys; + Uint i; + Uint n; + + mp = (map_t *)map_val(map); + keys = map_get_keys(mp); + n = map_get_size(mp); + if (is_immed(key)) { + for (i = 0; i < n; i++) { + if (keys[i] == key) { + return 0; + } + } + } else { + for (i = 0; i < n; i++) { + if (EQ(keys[i], key)) { + return 0; + } + } + } + return 1; +} + +static Eterm get_map_element(Eterm map, Eterm key) +{ + map_t *mp; + Eterm* ks, *vs; + Uint i; + Uint n; + + mp = (map_t *)map_val(map); + ks = map_get_keys(mp); + vs = map_get_values(mp); + n = map_get_size(mp); + if (is_immed(key)) { + for (i = 0; i < n; i++) { + if (ks[i] == key) { + return vs[i]; + } + } + } else { + for (i = 0; i < n; i++) { + if (EQ(ks[i], key)) { + return vs[i]; + } + } + } + return THE_NON_VALUE; +} + +#define GET_TERM(term, dest) \ +do { \ + Eterm src = (Eterm)(term); \ + switch (src & _TAG_IMMED1_MASK) { \ + case (R_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER: \ + dest = x(0); \ + break; \ + case (X_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER: \ + dest = x(src >> _TAG_IMMED1_SIZE); \ + break; \ + case (Y_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER: \ + dest = y(src >> _TAG_IMMED1_SIZE); \ + break; \ + default: \ + dest = src; \ + break; \ + } \ +} while(0) + + +static Eterm +new_map(Process* p, Eterm* reg, BeamInstr* I) +{ + Uint n = Arg(3); + Uint i; + Uint need = n + 1 /* hdr */ + 1 /*size*/ + 1 /* ptr */ + 1 /* arity */; + Eterm keys; + Eterm *mhp,*thp; + Eterm *E; + BeamInstr *ptr; + map_t *mp; + + if (HeapWordsLeft(p) < need) { + erts_garbage_collect(p, need, reg, Arg(2)); + } + + thp = p->htop; + mhp = thp + 1 + n/2; + E = p->stop; + ptr = &Arg(4); + keys = make_tuple(thp); + *thp++ = make_arityval(n/2); + + mp = (map_t *)mhp; mhp += MAP_HEADER_SIZE; + mp->thing_word = MAP_HEADER; + mp->size = n/2; + mp->keys = keys; + + for (i = 0; i < n/2; i++) { + GET_TERM(*ptr++, *thp++); + GET_TERM(*ptr++, *mhp++); + } + p->htop = mhp; + return make_map(mp); +} + +static Eterm +update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) +{ + Uint n; + Uint num_old; + Uint num_updates; + Uint need; + map_t *old_mp, *mp; + Eterm res; + Eterm* hp; + Eterm* E; + Eterm* old_keys; + Eterm* old_vals; + BeamInstr* new_p; + Eterm new_key; + Eterm* kp; + + if (is_not_map(map)) { + return THE_NON_VALUE; + } + + old_mp = (map_t *) map_val(map); + num_old = map_get_size(old_mp); + + /* + * If the old map is empty, create a new map. + */ + + if (num_old == 0) { + return new_map(p, reg, I+1); + } + + /* + * Allocate heap space for the worst case (i.e. all keys in the + * update list are new). + */ + + num_updates = Arg(4) / 2; + need = 2*(num_old+num_updates) + 1 + MAP_HEADER_SIZE; + if (HeapWordsLeft(p) < need) { + Uint live = Arg(3); + reg[live] = map; + erts_garbage_collect(p, need, reg, live+1); + map = reg[live]; + old_mp = (map_t *)map_val(map); + } + + /* + * Build the skeleton for the map, ready to be filled in. + * + * +-----------------------------------+ + * | (Space for aritvyal for keys) | <-----------+ + * +-----------------------------------+ | + * | (Space for key 1) | | <-- kp + * +-----------------------------------+ | + * . | + * . | + * . | + * +-----------------------------------+ | + * | (Space for last key) | | + * +-----------------------------------+ | + * | MAP_HEADER | | + * +-----------------------------------+ | + * | (Space for number of keys/values) | | + * +-----------------------------------+ | + * | Boxed tuple pointer >----------------+ + * +-----------------------------------+ + * | (Space for value 1) | <-- hp + * +-----------------------------------+ + */ + + E = p->stop; + kp = p->htop + 1; /* Point to first key */ + hp = kp + num_old + num_updates; + + res = make_map(hp); + mp = (map_t *)hp; + hp += MAP_HEADER_SIZE; + mp->thing_word = MAP_HEADER; + mp->keys = make_tuple(kp-1); + + old_vals = map_get_values(old_mp); + old_keys = map_get_keys(old_mp); + + new_p = &Arg(5); + GET_TERM(*new_p, new_key); + n = num_updates; + + /* + * Fill in keys and values, until we run out of either updates + * or old values and keys. + */ + + for (;;) { + Eterm key; + Sint c; + + ASSERT(kp < (Eterm *)mp); + key = *old_keys; + if ((c = CMP_TERM(key, new_key)) < 0) { + /* Copy old key and value */ + *kp++ = key; + *hp++ = *old_vals; + old_keys++, old_vals++, num_old--; + } else { /* Replace or insert new */ + GET_TERM(new_p[1], *hp++); + if (c > 0) { /* If new new key */ + *kp++ = new_key; + } else { /* If replacement */ + *kp++ = key; + old_keys++, old_vals++, num_old--; + } + n--; + if (n == 0) { + break; + } else { + new_p += 2; + GET_TERM(*new_p, new_key); + } + } + if (num_old == 0) { + break; + } + } + + /* + * At this point, we have run out of either old keys and values, + * or the update list. In other words, at least of one n and + * num_old must be zero. + */ + + if (n > 0) { + /* + * All old keys and values have been copied, but there + * are still new keys and values in the update list that + * must be copied. + */ + ASSERT(num_old == 0); + while (n-- > 0) { + GET_TERM(new_p[0], *kp++); + GET_TERM(new_p[1], *hp++); + new_p += 2; + } + } else { + /* + * All updates are now done. We may still have old + * keys and values that we must copy. + */ + ASSERT(n == 0); + while (num_old-- > 0) { + ASSERT(kp < (Eterm *)mp); + *kp++ = *old_keys++; + *hp++ = *old_vals++; + } + } + + /* + * Calculate how many values that are unused at the end of the + * key tuple and fill it out with a bignum header. + */ + if ((n = (Eterm *)mp - kp) > 0) { + *kp = make_pos_bignum_header(n-1); + } + + /* + * Fill in the size of the map in both the key tuple and in the map. + */ + + n = kp - p->htop - 1; /* Actual number of keys/values */ + *p->htop = make_arityval(n); + mp->size = n; + p->htop = hp; + return res; +} + +/* + * Update values for keys that already exist in the map. + */ + +static Eterm +update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I) +{ + Uint n; + Uint i; + Uint num_old; + Uint need; + map_t *old_mp, *mp; + Eterm res; + Eterm* hp; + Eterm* E; + Eterm* old_keys; + Eterm* old_vals; + BeamInstr* new_p; + Eterm new_key; + + if (is_not_map(map)) { + return THE_NON_VALUE; + } + + old_mp = (map_t *) map_val(map); + num_old = map_get_size(old_mp); + + /* + * If the old map is empty, create a new map. + */ + + if (num_old == 0) { + return new_map(p, reg, I+1); + } + + /* + * Allocate the exact heap space needed. + */ + + need = num_old + MAP_HEADER_SIZE; + if (HeapWordsLeft(p) < need) { + Uint live = Arg(3); + reg[live] = map; + erts_garbage_collect(p, need, reg, live+1); + map = reg[live]; + old_mp = (map_t *)map_val(map); + } + + /* + * Update map, keeping the old key tuple. + */ + + hp = p->htop; + E = p->stop; + + old_vals = map_get_values(old_mp); + old_keys = map_get_keys(old_mp); + + res = make_map(hp); + mp = (map_t *)hp; + hp += MAP_HEADER_SIZE; + mp->thing_word = MAP_HEADER; + mp->size = num_old; + mp->keys = old_mp->keys; + + /* Get array of key/value pairs to be updated */ + new_p = &Arg(5); + GET_TERM(*new_p, new_key); + + /* Update all values */ + n = Arg(4) / 2; /* Number of values to be updated */ + ASSERT(n > 0); + for (i = 0; i < num_old; i++) { + if (!EQ(*old_keys, new_key)) { + /* Not same keys */ + *hp++ = *old_vals; + } else { + GET_TERM(new_p[1], *hp); + hp++; + n--; + if (n == 0) { + /* + * All updates done. Copy remaining values + * and return the result. + */ + for (i++, old_vals++; i < num_old; i++) { + *hp++ = *old_vals++; + } + ASSERT(hp == p->htop + need); + p->htop = hp; + return res; + } else { + new_p += 2; + GET_TERM(*new_p, new_key); + } + } + old_vals++, old_keys++; + } + + /* + * Updates left. That means that at least one the keys in the + * update list did not previously exist. + */ + ASSERT(hp == p->htop + need); + return THE_NON_VALUE; +} +#undef GET_TERM int catchlevel(Process *p) { diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c index 938fd8f2c9..b589d1c930 100644 --- a/erts/emulator/beam/beam_load.c +++ b/erts/emulator/beam/beam_load.c @@ -3783,6 +3783,8 @@ gen_guard_bif1(LoaderState* stp, GenOpArg Fail, GenOpArg Live, GenOpArg Bif, op->a[1].val = (BeamInstr) (void *) erts_gc_bit_size_1; } else if (bf == byte_size_1) { op->a[1].val = (BeamInstr) (void *) erts_gc_byte_size_1; + } else if (bf == map_size_1) { + op->a[1].val = (BeamInstr) (void *) erts_gc_map_size_1; } else if (bf == abs_1) { op->a[1].val = (BeamInstr) (void *) erts_gc_abs_1; } else if (bf == float_1) { @@ -4376,6 +4378,7 @@ transform_engine(LoaderState* st) Uint* restart; /* Where to restart if current match fails. */ GenOpArg def_vars[TE_MAX_VARS]; /* Default buffer for variables. */ GenOpArg* var = def_vars; + int num_vars = 0; int i; /* General index. */ Uint mask; GenOp* instr; @@ -4578,9 +4581,9 @@ transform_engine(LoaderState* st) { int n = *pc++; int formal_arity = gen_opc[instr->op].arity; - int num_vars = n + (instr->arity - formal_arity); int j = formal_arity; + num_vars = n + (instr->arity - formal_arity); var = erts_alloc(ERTS_ALC_T_LOADER_TMP, num_vars * sizeof(GenOpArg)); for (i = 0; i < n; i++) { @@ -4592,7 +4595,6 @@ transform_engine(LoaderState* st) } break; #endif - case TOP_next_arg: ap++; break; @@ -4680,6 +4682,20 @@ transform_engine(LoaderState* st) instr->a[ap].val = var[i].val; ap++; break; +#if defined(TOP_store_rest_args) + case TOP_store_rest_args: + { + int n = *pc++; + int num_extra = num_vars - n; + + ASSERT(n <= num_vars); + GENOP_ARITY(instr, instr->arity+num_extra); + memcpy(instr->a, instr->def_args, ap*sizeof(GenOpArg)); + memcpy(instr->a+ap, var+n, num_extra*sizeof(GenOpArg)); + ap += num_extra; + } + break; +#endif case TOP_try_me_else: restart = pc + 1; restart += *pc++; diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c index 61c1abedb5..9c4801041f 100644 --- a/erts/emulator/beam/bif.c +++ b/erts/emulator/beam/bif.c @@ -4615,6 +4615,17 @@ BIF_RETTYPE bump_reductions_1(BIF_ALIST_1) BIF_RET2(am_true, reds); } +BIF_RETTYPE erts_internal_cmp_term_2(BIF_ALIST_2) { + int res = CMP_TERM(BIF_ARG_1,BIF_ARG_2); + + /* ensure -1, 0, 1 result */ + if (res < 0) { + BIF_RET(make_small(-1)); + } else if (res > 0) { + BIF_RET(make_small(1)); + } + BIF_RET(make_small(0)); +} /* * Processes doing yield on return in a bif ends up in bif_return_trap(). */ diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 3ec534f0bc..2d888862bf 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -578,6 +578,23 @@ bif os:unsetenv/1 bif re:inspect/2 +ubif erlang:is_map/1 +ubif erlang:map_size/1 +bif maps:to_list/1 +bif maps:find/2 +bif maps:get/2 +bif maps:from_list/1 +bif maps:is_key/2 +bif maps:keys/1 +bif maps:merge/2 +bif maps:new/0 +bif maps:put/3 +bif maps:remove/2 +bif maps:update/3 +bif maps:values/1 + +bif erts_internal:cmp_term/2 + # # Obsolete # diff --git a/erts/emulator/beam/copy.c b/erts/emulator/beam/copy.c index 23c0fca6aa..3a987e213b 100644 --- a/erts/emulator/beam/copy.c +++ b/erts/emulator/beam/copy.c @@ -27,6 +27,7 @@ #include "erl_process.h" #include "erl_gc.h" #include "big.h" +#include "erl_map.h" #include "erl_binary.h" #include "erl_bits.h" #include "dtrace-wrapper.h" @@ -150,6 +151,24 @@ Uint size_object(Eterm obj) goto pop_next; } break; + case MAP_SUBTAG: + { + Uint n; + map_t *mp; + mp = (map_t*)map_val_rel(obj,base); + ptr = (Eterm *)mp; + n = map_get_size(mp) + 1; + sum += n + 2; + ptr += 2; /* hdr + size words */ + while (n--) { + obj = *ptr++; + if (!IS_CONST(obj)) { + ESTACK_PUSH(s, obj); + } + } + goto pop_next; + } + break; case BIN_MATCHSTATE_SUBTAG: erl_exit(ERTS_ABORT_EXIT, "size_object: matchstate term not allowed"); @@ -318,6 +337,15 @@ Eterm copy_struct(Eterm obj, Uint sz, Eterm** hpp, ErlOffHeap* off_heap) } } break; + case MAP_SUBTAG: + { + i = map_get_size(objp) + 3; + *argp = make_map_rel(htop, dst_base); + while (i--) { + *htop++ = *objp++; + } + } + break; case REFC_BINARY_SUBTAG: { ProcBin* pb; @@ -537,6 +565,10 @@ Eterm copy_shallow(Eterm* ptr, Uint sz, Eterm** hpp, ErlOffHeap* off_heap) } goto off_heap_common; + case MAP_SUBTAG: + *hp++ = *tp++; + sz--; + break; case EXTERNAL_PID_SUBTAG: case EXTERNAL_PORT_SUBTAG: case EXTERNAL_REF_SUBTAG: diff --git a/erts/emulator/beam/erl_bif_guard.c b/erts/emulator/beam/erl_bif_guard.c index a715756c15..bbd8aa31d9 100644 --- a/erts/emulator/beam/erl_bif_guard.c +++ b/erts/emulator/beam/erl_bif_guard.c @@ -33,6 +33,7 @@ #include "bif.h" #include "big.h" #include "erl_binary.h" +#include "erl_map.h" static Eterm gc_double_to_integer(Process* p, double x, Eterm* reg, Uint live); @@ -455,6 +456,28 @@ Eterm erts_gc_byte_size_1(Process* p, Eterm* reg, Uint live) } } +Eterm erts_gc_map_size_1(Process* p, Eterm* reg, Uint live) +{ + Eterm arg = reg[live]; + if (is_map(arg)) { + map_t *mp = (map_t*)map_val(arg); + Uint size = map_get_size(mp); + if (IS_USMALL(0, size)) { + return make_small(size); + } else { + Eterm* hp; + if (ERTS_NEED_GC(p, BIG_UINT_HEAP_SIZE)) { + erts_garbage_collect(p, BIG_UINT_HEAP_SIZE, reg, live); + } + hp = p->htop; + p->htop += BIG_UINT_HEAP_SIZE; + return uint_to_big(size, hp); + } + } else { + BIF_ERROR(p, BADARG); + } +} + Eterm erts_gc_abs_1(Process* p, Eterm* reg, Uint live) { Eterm arg; diff --git a/erts/emulator/beam/erl_bif_op.c b/erts/emulator/beam/erl_bif_op.c index adac0052d6..37dd6457db 100644 --- a/erts/emulator/beam/erl_bif_op.c +++ b/erts/emulator/beam/erl_bif_op.c @@ -36,6 +36,7 @@ #include "dist.h" #include "erl_version.h" #include "erl_binary.h" +#include "erl_map.h" BIF_RETTYPE and_2(BIF_ALIST_2) { @@ -321,7 +322,10 @@ BIF_RETTYPE is_record_3(BIF_ALIST_3) BIF_RET(am_false); } - - - - +BIF_RETTYPE is_map_1(BIF_ALIST_1) +{ + if (is_map(BIF_ARG_1)) { + BIF_RET(am_true); + } + BIF_RET(am_false); +} diff --git a/erts/emulator/beam/erl_db_util.c b/erts/emulator/beam/erl_db_util.c index a358ecf326..3986ccd4d3 100644 --- a/erts/emulator/beam/erl_db_util.c +++ b/erts/emulator/beam/erl_db_util.c @@ -35,6 +35,7 @@ #include "bif.h" #include "big.h" #include "erl_binary.h" +#include "erl_map.h" #include "erl_thr_progress.h" #include "erl_db_util.h" @@ -565,6 +566,12 @@ static DMCGuardBif guard_tab[] = DBIF_ALL }, { + am_is_map, + &is_map_1, + 1, + DBIF_ALL + }, + { am_is_binary, &is_binary_1, 1, @@ -631,6 +638,12 @@ static DMCGuardBif guard_tab[] = DBIF_ALL }, { + am_map_size, + &map_size_1, + 1, + DBIF_ALL + }, + { am_bit_size, &bit_size_1, 1, diff --git a/erts/emulator/beam/erl_debug.c b/erts/emulator/beam/erl_debug.c index 873a9860da..50bdc79506 100644 --- a/erts/emulator/beam/erl_debug.c +++ b/erts/emulator/beam/erl_debug.c @@ -29,6 +29,7 @@ #include "bif.h" #include "beam_catches.h" #include "erl_debug.h" +#include "erl_map.h" #define WITHIN(ptr, x, y) ((x) <= (ptr) && (ptr) < (y)) diff --git a/erts/emulator/beam/erl_driver.h b/erts/emulator/beam/erl_driver.h index 2bd3181bdc..ab9ee63104 100644 --- a/erts/emulator/beam/erl_driver.h +++ b/erts/emulator/beam/erl_driver.h @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 1999-2013. All Rights Reserved. + * Copyright Ericsson AB 1999-2014. All Rights Reserved. * * The contents of this file are subject to the Erlang Public License, * Version 1.1, (the "License"); you may not use this file except in @@ -605,6 +605,8 @@ EXTERN int null_func(void); #define ERL_DRV_INT64 ((ErlDrvTermData) 15) /* ErlDrvSInt64 * */ #define ERL_DRV_UINT64 ((ErlDrvTermData) 16) /* ErlDrvUInt64 * */ +#define ERL_DRV_MAP ((ErlDrvTermData) 17) /* ErlDrvUInt */ + #ifndef ERL_DRIVER_TYPES_ONLY /* make terms for driver_output_term and driver_send_term */ diff --git a/erts/emulator/beam/erl_gc.c b/erts/emulator/beam/erl_gc.c index ab8448e8a1..2022f70cbb 100644 --- a/erts/emulator/beam/erl_gc.c +++ b/erts/emulator/beam/erl_gc.c @@ -28,6 +28,7 @@ #include "beam_catches.h" #include "erl_binary.h" #include "erl_bits.h" +#include "erl_map.h" #include "error.h" #include "big.h" #include "erl_gc.h" diff --git a/erts/emulator/beam/erl_gc.h b/erts/emulator/beam/erl_gc.h index 1801df359a..5203dda263 100644 --- a/erts/emulator/beam/erl_gc.h +++ b/erts/emulator/beam/erl_gc.h @@ -20,6 +20,8 @@ #ifndef __ERL_GC_H__ #define __ERL_GC_H__ +#include "erl_map.h" + /* GC declarations shared by beam/erl_gc.c and hipe/hipe_gc.c */ #if defined(DEBUG) && !ERTS_GLB_INLINE_INCL_FUNC_DEF @@ -42,23 +44,24 @@ do { \ HTOP += 2; /* update tospace htop */ \ } while(0) -#define MOVE_BOXED(PTR,HDR,HTOP,ORIG) \ -do { \ - Eterm gval; \ - Sint nelts; \ - \ - ASSERT(is_header(HDR)); \ - gval = make_boxed(HTOP); \ - *ORIG = gval; \ - *HTOP++ = HDR; \ - *PTR++ = gval; \ - nelts = header_arity(HDR); \ - switch ((HDR) & _HEADER_SUBTAG_MASK) { \ - case SUB_BINARY_SUBTAG: nelts++; break; \ - case FUN_SUBTAG: nelts+=((ErlFunThing*)(PTR-1))->num_free+1; break; \ - } \ - while (nelts--) \ - *HTOP++ = *PTR++; \ +#define MOVE_BOXED(PTR,HDR,HTOP,ORIG) \ +do { \ + Eterm gval; \ + Sint nelts; \ + \ + ASSERT(is_header(HDR)); \ + nelts = header_arity(HDR); \ + switch ((HDR) & _HEADER_SUBTAG_MASK) { \ + case SUB_BINARY_SUBTAG: nelts++; break; \ + case MAP_SUBTAG: nelts+=map_get_size(PTR) + 1; break; \ + case FUN_SUBTAG: nelts+=((ErlFunThing*)(PTR))->num_free+1; break; \ + } \ + gval = make_boxed(HTOP); \ + *ORIG = gval; \ + *HTOP++ = HDR; \ + *PTR++ = gval; \ + while (nelts--) *HTOP++ = *PTR++; \ + \ } while(0) #define in_area(ptr,start,nbytes) \ diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c new file mode 100644 index 0000000000..2fff7f9390 --- /dev/null +++ b/erts/emulator/beam/erl_map.c @@ -0,0 +1,819 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2014. All Rights Reserved. + * + * The contents of this file are subject to the Erlang Public License, + * Version 1.1, (the "License"); you may not use this file except in + * compliance with the License. You should have received a copy of the + * Erlang Public License along with this software. If not, it can be + * retrieved online at http://www.erlang.org/. + * + * Software distributed under the License is distributed on an "AS IS" + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See + * the License for the specific language governing rights and limitations + * under the License. + * + * %CopyrightEnd% + * + * Author: Björn-Egil Dahlberg + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include "sys.h" +#include "erl_vm.h" +#include "global.h" +#include "erl_process.h" +#include "error.h" +#include "bif.h" + +#include "erl_map.h" + +/* BIFs + * + * DONE: + * - erlang:is_map/1 + * - erlang:map_size/1 + * + * - maps:find/2 + * - maps:from_list/1 + * - maps:get/2 + * - maps:is_key/2 + * - maps:keys/1 + * - maps:merge/2 + * - maps:new/0 + * - maps:put/3 + * - maps:remove/2 + * - maps:to_list/1 + * - maps:update/3 + * - maps:values/1 + * + * TODO: + * - maps:foldl/3 + * - maps:foldr/3 + * - maps:map/3 + * - maps:size/1 + * - maps:without/2 + * + */ + +/* erlang:map_size/1 + * the corresponding instruction is implemented in: + * beam/erl_bif_guard.c + */ + +BIF_RETTYPE map_size_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Eterm *hp; + Uint hsz = 0; + map_t *mp = (map_t*)map_val(BIF_ARG_1); + Uint n = map_get_size(mp); + + erts_bld_uint(NULL, &hsz, n); + hp = HAlloc(BIF_P, hsz); + BIF_RET(erts_bld_uint(&hp, NULL, n)); + } + + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:to_list/1 + */ + +BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Uint n; + Eterm* hp; + Eterm *ks,*vs, res, tup; + map_t *mp = (map_t*)map_val(BIF_ARG_1); + + ks = map_get_keys(mp); + vs = map_get_values(mp); + n = map_get_size(mp); + hp = HAlloc(BIF_P, (2 + 3) * n); + res = NIL; + + while(n--) { + tup = TUPLE2(hp, ks[n], vs[n]); hp += 3; + res = CONS(hp, tup, res); hp += 2; + } + + BIF_RET(res); + } + + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:find/2 + * return value if key *matches* a key in the map + */ + +int erts_maps_find(Eterm key, Eterm map, Eterm *value) { + + Eterm *ks,*vs; + map_t *mp; + Uint n,i; + + mp = (map_t*)map_val(map); + n = map_get_size(mp); + ks = map_get_keys(mp); + vs = map_get_values(mp); + + for( i = 0; i < n; i++) { + if (EQ(ks[i], key)) { + *value = vs[i]; + return 1; + } + } + return 0; +} + +BIF_RETTYPE maps_find_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm *hp, value,res; + + if (erts_maps_find(BIF_ARG_1, BIF_ARG_2, &value)) { + hp = HAlloc(BIF_P, 3); + res = make_tuple(hp); + *hp++ = make_arityval(2); + *hp++ = am_ok; + *hp++ = value; + BIF_RET(res); + } + + BIF_RET(am_error); + } + BIF_ERROR(BIF_P, BADARG); +} +/* maps:get/2 + * return value if key *matches* a key in the map + * exception bad_key if none matches + */ + + +int erts_maps_get(Eterm key, Eterm map, Eterm *value) { + Eterm *ks,*vs; + map_t *mp; + Uint n,i; + + mp = (map_t*)map_val(map); + n = map_get_size(mp); + + if (n == 0) + return 0; + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + if (is_immed(key)) { + for( i = 0; i < n; i++) { + if (ks[i] == key) { + *value = vs[i]; + return 1; + } + } + } + + for( i = 0; i < n; i++) { + if (EQ(ks[i], key)) { + *value = vs[i]; + return 1; + } + } + return 0; +} + +BIF_RETTYPE maps_get_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm *hp; + Eterm value, error; + char *s_error; + + if (erts_maps_get(BIF_ARG_1, BIF_ARG_2, &value)) { + BIF_RET(value); + } + + s_error = "bad_key"; + error = am_atom_put(s_error, sys_strlen(s_error)); + + hp = HAlloc(BIF_P, 3); + BIF_P->fvalue = TUPLE2(hp, error, BIF_ARG_1); + BIF_ERROR(BIF_P, EXC_ERROR_2); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:from_list/1 + * List may be unsorted [{K,V}] + */ + +BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) { + Eterm *kv, item = BIF_ARG_1; + Eterm *hp, *thp,*vs, *ks, keys, res; + map_t *mp; + Uint size = 0, unused_size = 0; + Sint c = 0; + Sint idx = 0; + + if (is_list(item) || is_nil(item)) { + + /* Calculate size and check validity */ + + 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; + + size++; + item = CDR(list_val(item)); + } + + if (is_not_nil(item)) + goto error; + + hp = HAlloc(BIF_P, 3 + 1 + (2 * size)); + thp = hp; + keys = make_tuple(hp); + *hp++ = make_arityval(size); + ks = hp; + hp += size; + mp = (map_t*)hp; + res = make_map(mp); + hp += MAP_HEADER_SIZE; + vs = hp; + + mp->thing_word = MAP_HEADER; + mp->size = size; /* set later, might shrink*/ + mp->keys = keys; + + if (size == 0) + BIF_RET(res); + + item = BIF_ARG_1; + + /* first entry */ + kv = tuple_val(CAR(list_val(item))); + ks[0] = kv[1]; + vs[0] = kv[2]; + size = 1; + item = CDR(list_val(item)); + + /* insert sort key/value pairs */ + while(is_list(item)) { + + kv = tuple_val(CAR(list_val(item))); + + /* compare ks backwards + * idx represent word index to be written (hole position). + * We cannot copy the elements when searching since we might + * have an equal key. So we search for just the index first =( + * + * It is perhaps faster to move the values in the first pass. + * Check for uniqueness during insert phase and then have a + * second phace compacting the map if duplicates are found + * during insert. .. or do someother sort .. shell-sort perhaps. + */ + + idx = size; + + while(idx > 0 && (c = CMP_TERM(kv[1],ks[idx-1])) < 0) { idx--; } + + if (c == 0) { + /* last compare was equal, + * i.e. we have to release memory + * and overwrite that key/value + */ + ks[idx-1] = kv[1]; + vs[idx-1] = kv[2]; + unused_size++; + } else { + Uint i = size; + while(i > idx) { + ks[i] = ks[i-1]; + vs[i] = vs[i-1]; + i--; + } + ks[idx] = kv[1]; + vs[idx] = kv[2]; + size++; + } + item = CDR(list_val(item)); + } + + if (unused_size) { + /* the key tuple is embedded in the heap + * write a bignum to clear it. + */ + /* release values as normal since they are on the top of the heap */ + + ks[size] = make_pos_bignum_header(unused_size - 1); + HRelease(BIF_P, vs + size + unused_size, vs + size); + } + + *thp = make_arityval(size); + mp->size = size; + BIF_RET(res); + } + +error: + + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:is_key/2 + */ + +BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm *ks, key; + map_t *mp; + Uint n,i; + + mp = (map_t*)map_val(BIF_ARG_2); + key = BIF_ARG_1; + n = map_get_size(mp); + ks = map_get_keys(mp); + + if (n == 0) + BIF_RET(am_false); + + if (is_immed(key)) { + for( i = 0; i < n; i++) { + if (ks[i] == key) { + BIF_RET(am_true); + } + } + } + + for( i = 0; i < n; i++) { + if (EQ(ks[i], key)) { + BIF_RET(am_true); + } + } + BIF_RET(am_false); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:keys/1 + */ + +BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Eterm *hp, *ks, res = NIL; + map_t *mp; + Uint n; + + mp = (map_t*)map_val(BIF_ARG_1); + n = map_get_size(mp); + + if (n == 0) + BIF_RET(res); + + hp = HAlloc(BIF_P, (2 * n)); + ks = map_get_keys(mp); + + while(n--) { + res = CONS(hp, ks[n], res); hp += 2; + } + + BIF_RET(res); + } + BIF_ERROR(BIF_P, BADARG); +} +/* maps:merge/2 + */ + +BIF_RETTYPE maps_merge_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_1) && is_map(BIF_ARG_2)) { + Eterm *hp,*thp; + Eterm tup; + Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2; + map_t *mp1,*mp2,*mp_new; + Uint n1,n2,i1,i2,need,unused_size=0; + int c = 0; + + mp1 = (map_t*)map_val(BIF_ARG_1); + mp2 = (map_t*)map_val(BIF_ARG_2); + n1 = map_get_size(mp1); + n2 = map_get_size(mp2); + + need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2); + + hp = HAlloc(BIF_P, need); + thp = hp; + tup = make_tuple(thp); + ks = hp + 1; hp += 1 + n1 + n2; + mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE; + vs = hp; hp += n1 + n2; + + mp_new->thing_word = MAP_HEADER; + mp_new->size = 0; + mp_new->keys = tup; + + i1 = 0; i2 = 0; + ks1 = map_get_keys(mp1); + vs1 = map_get_values(mp1); + ks2 = map_get_keys(mp2); + vs2 = map_get_values(mp2); + + while(i1 < n1 && i2 < n2) { + c = CMP_TERM(ks1[i1],ks2[i2]); + if ( c == 0) { + /* use righthand side arguments map value, + * but advance both maps */ + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i1++, i2++, unused_size++; + } else if ( c < 0) { + *ks++ = ks1[i1]; + *vs++ = vs1[i1]; + i1++; + } else { + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i2++; + } + } + + /* copy remaining */ + while (i1 < n1) { + *ks++ = ks1[i1]; + *vs++ = vs1[i1]; + i1++; + } + + while (i2 < n2) { + *ks++ = ks2[i2]; + *vs++ = vs2[i2]; + i2++; + } + + if (unused_size) { + /* the key tuple is embedded in the heap, write a bignum to clear it. + * + * release values as normal since they are on the top of the heap + * size = n1 + n1 - unused_size + */ + + *ks = make_pos_bignum_header(unused_size - 1); + HRelease(BIF_P, vs + unused_size, vs); + } + + mp_new->size = n1 + n2 - unused_size; + *thp = make_arityval(n1 + n2 - unused_size); + + BIF_RET(make_map(mp_new)); + } + BIF_ERROR(BIF_P, BADARG); +} +/* maps:new/2 + */ + +BIF_RETTYPE maps_new_0(BIF_ALIST_0) { + Eterm* hp; + Eterm tup; + map_t *mp; + + hp = HAlloc(BIF_P, (MAP_HEADER_SIZE + 1)); + tup = make_tuple(hp); + *hp++ = make_arityval(0); + + mp = (map_t*)hp; + mp->thing_word = MAP_HEADER; + mp->size = 0; + mp->keys = tup; + + BIF_RET(make_map(mp)); +} + +/* maps:put/3 + */ + +Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) { + Sint n,i; + Sint c = 0; + Eterm* hp, *shp; + Eterm *ks,*vs, res, tup; + map_t *mp = (map_t*)map_val(map); + + n = map_get_size(mp); + + if (n == 0) { + hp = HAlloc(p, MAP_HEADER_SIZE + 1 + 2); + tup = make_tuple(hp); + *hp++ = make_arityval(1); + *hp++ = key; + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = 1; + *hp++ = tup; + *hp++ = value; + + return res; + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* only allocate for values, + * assume key-tuple will be intact + */ + + hp = HAlloc(p, MAP_HEADER_SIZE + n); + shp = hp; /* save hp, used if optimistic update fails */ + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = n; + *hp++ = mp->keys; + + if (is_immed(key)) { + for( i = 0; i < n; i ++) { + if (ks[i] == key) { + *hp++ = value; + vs++; + c = 1; + } else { + *hp++ = *vs++; + } + } + } else { + for( i = 0; i < n; i ++) { + if (EQ(ks[i], key)) { + *hp++ = value; + vs++; + c = 1; + } else { + *hp++ = *vs++; + } + } + } + + if (c) + return res; + + /* need to make a new tuple, + * use old hp since it needs to be recreated anyway. + */ + tup = make_tuple(shp); + *shp++ = make_arityval(n+1); + + hp = HAlloc(p, 3 + n + 1); + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = n + 1; + *hp++ = tup; + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + ASSERT(n >= 0); + + /* copy map in order */ + while (n && ((c = CMP_TERM(*ks, key)) < 0)) { + *shp++ = *ks++; + *hp++ = *vs++; + n--; + } + + *shp++ = key; + *hp++ = value; + + ASSERT(n >= 0); + + while(n--) { + *shp++ = *ks++; + *hp++ = *vs++; + } + /* we have one word remaining + * this will work out fine once we get the size word + * in the header. + */ + *shp = make_pos_bignum_header(0); + return res; +} + +BIF_RETTYPE maps_put_3(BIF_ALIST_3) { + if (is_map(BIF_ARG_3)) { + BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3)); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:remove/3 + */ + +int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) { + Sint n; + Uint need; + Eterm *hp_start; + Eterm *thp, *mhp; + Eterm *ks, *vs, tup; + map_t *mp = (map_t*)map_val(map); + + n = map_get_size(mp); + + if (n == 0) { + *res = map; + return 1; + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* Assume key exists. + * Release allocated if it didn't. + * Allocate key tuple first. + */ + + need = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */ + hp_start = HAlloc(p, need); + thp = hp_start; + mhp = thp + n; /* offset with tuple heap size */ + + tup = make_tuple(thp); + *thp++ = make_arityval(n - 1); + + *res = make_map(mhp); + *mhp++ = MAP_HEADER; + *mhp++ = n - 1; + *mhp++ = tup; + + if (is_immed(key)) { + while(n--) { + if (*ks == key) { + goto found_key; + } else { + *mhp++ = *vs++; + *thp++ = *ks++; + } + } + } else { + while(n--) { + if (EQ(*ks, key)) { + goto found_key; + } else { + *mhp++ = *vs++; + *thp++ = *ks++; + } + } + } + + /* Not found, remove allocated memory + * and return previous map. + */ + HRelease(p, hp_start + need, hp_start); + + *res = map; + return 1; + +found_key: + /* Copy rest of keys and values */ + if (n) { + sys_memcpy(mhp, vs+1, n*sizeof(Eterm)); + sys_memcpy(thp, ks+1, n*sizeof(Eterm)); + } + return 1; +} + +BIF_RETTYPE maps_remove_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm res; + if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) { + BIF_RET(res); + } + } + BIF_ERROR(BIF_P, BADARG); +} + +/* maps:update/3 + */ + +int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) { + Sint n,i; + Eterm* hp,*shp; + Eterm *ks,*vs; + map_t *mp = (map_t*)map_val(map); + + if ((n = map_get_size(mp)) == 0) { + return 0; + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + /* only allocate for values, + * assume key-tuple will be intact + */ + + hp = HAlloc(p, MAP_HEADER_SIZE + n); + shp = hp; + *hp++ = MAP_HEADER; + *hp++ = n; + *hp++ = mp->keys; + + if (is_immed(key)) { + for( i = 0; i < n; i ++) { + if (ks[i] == key) { + goto found_key; + } else { + *hp++ = *vs++; + } + } + } else { + for( i = 0; i < n; i ++) { + if (EQ(ks[i], key)) { + goto found_key; + } else { + *hp++ = *vs++; + } + } + } + + HRelease(p, shp + MAP_HEADER_SIZE + n, shp); + return 0; + +found_key: + *hp++ = value; + vs++; + if (++i < n) + sys_memcpy(hp, vs, (n - i)*sizeof(Eterm)); + *res = make_map(shp); + return 1; +} + +BIF_RETTYPE maps_update_3(BIF_ALIST_3) { + if (is_map(BIF_ARG_3)) { + Eterm res; + if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) { + BIF_RET(res); + } + } + BIF_ERROR(BIF_P, BADARG); +} + + +/* maps:values/1 + */ + +BIF_RETTYPE maps_values_1(BIF_ALIST_1) { + if (is_map(BIF_ARG_1)) { + Eterm *hp, *vs, res = NIL; + map_t *mp; + Uint n; + + mp = (map_t*)map_val(BIF_ARG_1); + n = map_get_size(mp); + + if (n == 0) + BIF_RET(res); + + hp = HAlloc(BIF_P, (2 * n)); + vs = map_get_values(mp); + + while(n--) { + res = CONS(hp, vs[n], res); hp += 2; + } + + BIF_RET(res); + } + BIF_ERROR(BIF_P, BADARG); +} + +int erts_validate_and_sort_map(map_t* mp) +{ + Eterm *ks = map_get_keys(mp); + Eterm *vs = map_get_values(mp); + Uint sz = map_get_size(mp); + Uint ix,jx; + Eterm tmp; + int c; + + /* sort */ + + for (ix = 1; ix < sz; ix++) { + jx = ix; + while( jx > 0 && (c = CMP_TERM(ks[jx],ks[jx-1])) <= 0 ) { + /* identical key -> error */ + if (c == 0) return 0; + + tmp = ks[jx]; + ks[jx] = ks[jx - 1]; + ks[jx - 1] = tmp; + + tmp = vs[jx]; + vs[jx] = vs[jx - 1]; + vs[jx - 1] = tmp; + + jx--; + } + } + return 1; +} diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h new file mode 100644 index 0000000000..cfacb2ec28 --- /dev/null +++ b/erts/emulator/beam/erl_map.h @@ -0,0 +1,72 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2014. All Rights Reserved. + * + * The contents of this file are subject to the Erlang Public License, + * Version 1.1, (the "License"); you may not use this file except in + * compliance with the License. You should have received a copy of the + * Erlang Public License along with this software. If not, it can be + * retrieved online at http://www.erlang.org/. + * + * Software distributed under the License is distributed on an "AS IS" + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See + * the License for the specific language governing rights and limitations + * under the License. + * + * %CopyrightEnd% + */ + + +#ifndef __ERL_MAP_H__ +#define __ERL_MAP_H__ + +#include "sys.h" +/* MAP */ + +typedef struct map_s { + Eterm thing_word; + Uint size; + Eterm keys; /* tuple */ +} map_t; +/* map node + * + * ----------- + * Eterm THING + * Uint size + * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = size + * ---- + * Eterm V1 + * ... + * Eterm Vn, where n = size + * ----------- + */ + + + +/* erl_term.h stuff */ +#define make_map(x) make_boxed((Eterm*)(x)) +#define make_map_rel(x, BASE) make_boxed_rel((Eterm*)(x),(BASE)) +#define is_map(x) (is_boxed((x)) && is_map_header(*boxed_val((x)))) +#define is_map_rel(RTERM,BASE) is_map(rterm2wterm(RTERM,BASE)) +#define is_not_map(x) (!is_map((x))) +#define is_map_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_MAP) +#define header_is_map(x) ((((x) & (_HEADER_SUBTAG_MASK)) == MAP_SUBTAG)) +#define map_val(x) (_unchecked_boxed_val((x))) +#define map_val_rel(RTERM, BASE) map_val(rterm2wterm(RTERM, BASE)) + +#define map_get_values(x) (((Eterm *)(x)) + 3) +#define map_get_keys(x) (((Eterm *)tuple_val(((map_t *)(x))->keys)) + 1) +#define map_get_size(x) (((map_t*)(x))->size) + +#define MAP_HEADER _make_header(1,_TAG_HEADER_MAP) +#define MAP_HEADER_SIZE (sizeof(map_t) / sizeof(Eterm)) + +Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map); +int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res); +int erts_maps_find(Eterm key, Eterm map, Eterm *value); +int erts_maps_get(Eterm key, Eterm map, Eterm *value); +int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res); +int erts_validate_and_sort_map(map_t* map); +#endif + diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index e1e213c4eb..c35f1fc2c6 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2009-2013. All Rights Reserved. + * Copyright Ericsson AB 2009-2014. All Rights Reserved. * * The contents of this file are subject to the Erlang Public License, * Version 1.1, (the "License"); you may not use this file except in @@ -31,6 +31,7 @@ #include "bif.h" #include "error.h" #include "big.h" +#include "erl_map.h" #include "beam_bp.h" #include "erl_thr_progress.h" #include "dtrace-wrapper.h" @@ -1602,6 +1603,197 @@ enif_have_dirty_schedulers() #endif /* ERL_NIF_DIRTY_SCHEDULER_SUPPORT */ +/* Maps */ + +int enif_is_map(ErlNifEnv* env, ERL_NIF_TERM term) +{ + return is_map(term); +} + +int enif_get_map_size(ErlNifEnv* env, ERL_NIF_TERM term, size_t *size) +{ + if (is_map(term)) { + map_t *mp; + mp = (map_t*)map_val(term); + *size = map_get_size(mp); + return 1; + } + return 0; +} + +ERL_NIF_TERM enif_make_new_map(ErlNifEnv* env) +{ + Eterm* hp = alloc_heap(env,MAP_HEADER_SIZE+1); + Eterm tup; + map_t *mp; + + tup = make_tuple(hp); + *hp++ = make_arityval(0); + mp = (map_t*)hp; + mp->thing_word = MAP_HEADER; + mp->size = 0; + mp->keys = tup; + + return make_map(mp); +} + +int enif_make_map_put(ErlNifEnv* env, + Eterm map_in, + Eterm key, + Eterm value, + Eterm *map_out) +{ + if (is_not_map(map_in)) { + return 0; + } + flush_env(env); + *map_out = erts_maps_put(env->proc, key, value, map_in); + cache_env(env); + return 1; +} + +int enif_get_map_value(ErlNifEnv* env, + Eterm map, + Eterm key, + Eterm *value) +{ + if (is_not_map(map)) { + return 0; + } + return erts_maps_get(key, map, value); +} + +int enif_make_map_update(ErlNifEnv* env, + Eterm map_in, + Eterm key, + Eterm value, + Eterm *map_out) +{ + int res; + if (is_not_map(map_in)) { + return 0; + } + + flush_env(env); + res = erts_maps_update(env->proc, key, value, map_in, map_out); + cache_env(env); + return res; +} + +int enif_make_map_remove(ErlNifEnv* env, + Eterm map_in, + Eterm key, + Eterm *map_out) +{ + int res; + if (is_not_map(map_in)) { + return 0; + } + flush_env(env); + res = erts_maps_remove(env->proc, key, map_in, map_out); + cache_env(env); + return res; +} + +int enif_map_iterator_create(ErlNifEnv *env, + Eterm map, + ErlNifMapIterator *iter, + ErlNifMapIteratorEntry entry) +{ + if (is_map(map)) { + map_t *mp = (map_t*)map_val(map); + size_t offset; + + switch (entry) { + case ERL_NIF_MAP_ITERATOR_HEAD: offset = 0; break; + case ERL_NIF_MAP_ITERATOR_TAIL: offset = map_get_size(mp) - 1; break; + default: goto error; + } + + /* empty maps are ok but will leave the iterator + * in bad shape. + */ + + iter->map = map; + iter->ks = ((Eterm *)map_get_keys(mp)) + offset; + iter->vs = ((Eterm *)map_get_values(mp)) + offset; + iter->t_limit = map_get_size(mp) + 1; + iter->idx = offset + 1; + + return 1; + } + +error: +#ifdef DEBUG + iter->map = THE_NON_VALUE; +#endif + return 0; +} + +void enif_map_iterator_destroy(ErlNifEnv *env, ErlNifMapIterator *iter) +{ + /* not used */ +#ifdef DEBUG + iter->map = THE_NON_VALUE; +#endif + +} + +int enif_map_iterator_is_tail(ErlNifEnv *env, ErlNifMapIterator *iter) +{ + ASSERT(iter && is_map(iter->map)); + ASSERT(iter->idx >= 0 && (iter->idx <= map_get_size(map_val(iter->map)) + 1)); + return (iter->t_limit == 1 || iter->idx == iter->t_limit); +} + +int enif_map_iterator_is_head(ErlNifEnv *env, ErlNifMapIterator *iter) +{ + ASSERT(iter && is_map(iter->map)); + ASSERT(iter->idx >= 0 && (iter->idx <= map_get_size(map_val(iter->map)) + 1)); + return (iter->t_limit == 1 || iter->idx == 0); +} + + +int enif_map_iterator_next(ErlNifEnv *env, ErlNifMapIterator *iter) +{ + ASSERT(iter && is_map(iter->map)); + if (iter->idx < iter->t_limit) { + iter->idx++; + iter->ks++; + iter->vs++; + } + return (iter->idx != iter->t_limit); +} + +int enif_map_iterator_prev(ErlNifEnv *env, ErlNifMapIterator *iter) +{ + ASSERT(iter && is_map(iter->map)); + if (iter->idx > 0) { + iter->idx--; + iter->ks--; + iter->vs--; + } + return (iter->idx > 0); +} + +int enif_map_iterator_get_pair(ErlNifEnv *env, + ErlNifMapIterator *iter, + Eterm *key, + Eterm *value) +{ + ASSERT(iter && is_map(iter->map)); + if (iter->idx > 0 && iter->idx < iter->t_limit) { + ASSERT(iter->ks >= map_get_keys(map_val(iter->map)) && + iter->ks < (map_get_keys(map_val(iter->map)) + map_get_size(map_val(iter->map)))); + ASSERT(iter->vs >= map_get_values(map_val(iter->map)) && + iter->vs < (map_get_values(map_val(iter->map)) + map_get_size(map_val(iter->map)))); + *key = *(iter->ks); + *value = *(iter->vs); + return 1; + } + return 0; +} + /*************************************************************************** ** load_nif/2 ** ***************************************************************************/ @@ -1798,7 +1990,8 @@ BIF_RETTYPE load_nif_2(BIF_ALIST_2) ret = load_nif_error(BIF_P, bad_lib, "Library init-call unsuccessful"); } else if (entry->major != ERL_NIF_MAJOR_VERSION - || entry->minor > ERL_NIF_MINOR_VERSION) { + || entry->minor > ERL_NIF_MINOR_VERSION + || (entry->major==2 && entry->minor == 5)) { /* experimental maps */ ret = load_nif_error(BIF_P, bad_lib, "Library version (%d.%d) not compatible (with %d.%d).", entry->major, entry->minor, ERL_NIF_MAJOR_VERSION, ERL_NIF_MINOR_VERSION); diff --git a/erts/emulator/beam/erl_nif.h b/erts/emulator/beam/erl_nif.h index fb3c359ec9..7613446f64 100644 --- a/erts/emulator/beam/erl_nif.h +++ b/erts/emulator/beam/erl_nif.h @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2009-2013. All Rights Reserved. + * Copyright Ericsson AB 2009-2014. All Rights Reserved. * * The contents of this file are subject to the Erlang Public License, * Version 1.1, (the "License"); you may not use this file except in @@ -38,14 +38,13 @@ ** 2.2: R14B03 enif_is_exception ** 2.3: R15 enif_make_reverse_list, enif_is_number ** 2.4: R16 enif_consume_timeslice -** 2.5: R17 dirty schedulers +** 2.5: First experimental maps API additions (libs of this version is not compatible with any other VM) +** 2.5: R17 Maps API additions +** 2.6: R17 with maps +** R17 dirty schedulers */ #define ERL_NIF_MAJOR_VERSION 2 -#ifdef ERL_NIF_DIRTY_SCHEDULER_SUPPORT -#define ERL_NIF_MINOR_VERSION 5 -#else -#define ERL_NIF_MINOR_VERSION 4 -#endif +#define ERL_NIF_MINOR_VERSION 6 #include <stdlib.h> @@ -104,6 +103,8 @@ typedef unsigned long long ERL_NIF_TERM; # endif #endif +typedef ERL_NIF_TERM ERL_NIF_UINT; + struct enif_environment_t; typedef struct enif_environment_t ErlNifEnv; @@ -176,6 +177,21 @@ typedef enum }ErlNifDirtyTaskFlags; #endif +typedef struct /* All fields all internal and may change */ +{ + ERL_NIF_TERM map; + ERL_NIF_UINT t_limit; + ERL_NIF_UINT idx; + ERL_NIF_TERM *ks; + ERL_NIF_TERM *vs; + void* __spare__[2]; /* for future additions to be ABI compatible (same struct size) */ +} ErlNifMapIterator; + +typedef enum { + ERL_NIF_MAP_ITERATOR_HEAD = 1, + ERL_NIF_MAP_ITERATOR_TAIL = 2 +} ErlNifMapIteratorEntry; + #if (defined(__WIN32__) || defined(_WIN32) || defined(_WIN32_)) # define ERL_NIF_API_FUNC_DECL(RET_TYPE, NAME, ARGS) RET_TYPE (*NAME) ARGS typedef struct { diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index f5b27dfdfa..d7c554e60b 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2009-2013. All Rights Reserved. + * Copyright Ericsson AB 2009-2014. All Rights Reserved. * * The contents of this file are subject to the Erlang Public License, * Version 1.1, (the "License"); you may not use this file except in @@ -149,6 +149,22 @@ ERL_NIF_API_FUNC_DECL(int,enif_is_on_dirty_scheduler,(ErlNifEnv*)); ERL_NIF_API_FUNC_DECL(int,enif_have_dirty_schedulers,(void)); #endif +ERL_NIF_API_FUNC_DECL(int, enif_is_map, (ErlNifEnv* env, ERL_NIF_TERM term)); +ERL_NIF_API_FUNC_DECL(int, enif_get_map_size, (ErlNifEnv* env, ERL_NIF_TERM term, size_t *size)); +ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM, enif_make_new_map, (ErlNifEnv* env)); +ERL_NIF_API_FUNC_DECL(int, enif_make_map_put, (ErlNifEnv* env, ERL_NIF_TERM map_in, ERL_NIF_TERM key, ERL_NIF_TERM value, ERL_NIF_TERM* map_out)); +ERL_NIF_API_FUNC_DECL(int, enif_get_map_value, (ErlNifEnv* env, ERL_NIF_TERM map, ERL_NIF_TERM key, ERL_NIF_TERM* value)); +ERL_NIF_API_FUNC_DECL(int, enif_make_map_update, (ErlNifEnv* env, ERL_NIF_TERM map_in, ERL_NIF_TERM key, ERL_NIF_TERM value, ERL_NIF_TERM* map_out)); +ERL_NIF_API_FUNC_DECL(int, enif_make_map_remove, (ErlNifEnv* env, ERL_NIF_TERM map_in, ERL_NIF_TERM key, ERL_NIF_TERM* map_out)); +ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_create, (ErlNifEnv *env, ERL_NIF_TERM map, ErlNifMapIterator *iter, ErlNifMapIteratorEntry entry)); +ERL_NIF_API_FUNC_DECL(void, enif_map_iterator_destroy, (ErlNifEnv *env, ErlNifMapIterator *iter)); +ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_is_head, (ErlNifEnv *env, ErlNifMapIterator *iter)); +ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_is_tail, (ErlNifEnv *env, ErlNifMapIterator *iter)); +ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_next, (ErlNifEnv *env, ErlNifMapIterator *iter)); +ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_prev, (ErlNifEnv *env, ErlNifMapIterator *iter)); +ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_get_pair, (ErlNifEnv *env, ErlNifMapIterator *iter, ERL_NIF_TERM *key, ERL_NIF_TERM *value)); + + /* ** Add new entries here to keep compatibility on Windows!!! */ @@ -281,6 +297,21 @@ ERL_NIF_API_FUNC_DECL(int,enif_have_dirty_schedulers,(void)); # define enif_have_dirty_schedulers ERL_NIF_API_FUNC_MACRO(enif_have_dirty_schedulers) #endif +# define enif_is_map ERL_NIF_API_FUNC_MACRO(enif_is_map) +# define enif_get_map_size ERL_NIF_API_FUNC_MACRO(enif_get_map_size) +# define enif_make_new_map ERL_NIF_API_FUNC_MACRO(enif_make_new_map) +# define enif_make_map_put ERL_NIF_API_FUNC_MACRO(enif_make_map_put) +# define enif_get_map_value ERL_NIF_API_FUNC_MACRO(enif_get_map_value) +# define enif_make_map_update ERL_NIF_API_FUNC_MACRO(enif_make_map_update) +# define enif_make_map_remove ERL_NIF_API_FUNC_MACRO(enif_make_map_remove) +# define enif_map_iterator_create ERL_NIF_API_FUNC_MACRO(enif_map_iterator_create) +# define enif_map_iterator_destroy ERL_NIF_API_FUNC_MACRO(enif_map_iterator_destroy) +# define enif_map_iterator_is_head ERL_NIF_API_FUNC_MACRO(enif_map_iterator_is_head) +# define enif_map_iterator_is_tail ERL_NIF_API_FUNC_MACRO(enif_map_iterator_is_tail) +# define enif_map_iterator_next ERL_NIF_API_FUNC_MACRO(enif_map_iterator_next) +# define enif_map_iterator_prev ERL_NIF_API_FUNC_MACRO(enif_map_iterator_prev) +# define enif_map_iterator_get_pair ERL_NIF_API_FUNC_MACRO(enif_map_iterator_get_pair) + /* ** Add new entries here */ diff --git a/erts/emulator/beam/erl_printf_term.c b/erts/emulator/beam/erl_printf_term.c index 436147749e..d18760dc43 100644 --- a/erts/emulator/beam/erl_printf_term.c +++ b/erts/emulator/beam/erl_printf_term.c @@ -24,6 +24,7 @@ #include "erl_printf_term.h" #include "sys.h" #include "big.h" +#include "erl_map.h" #define PRINT_CHAR(CNT, FN, ARG, C) \ do { \ @@ -216,14 +217,15 @@ static int print_atom_name(fmtfn_t fn, void* arg, Eterm atom, long *dcount) } -#define PRT_BAR ((Eterm) 0) -#define PRT_COMMA ((Eterm) 1) -#define PRT_CLOSE_LIST ((Eterm) 2) -#define PRT_CLOSE_TUPLE ((Eterm) 3) -#define PRT_TERM ((Eterm) 4) -#define PRT_ONE_CONS ((Eterm) 5) -#define PRT_PATCH_FUN_SIZE ((Eterm) 6) -#define PRT_LAST_ARRAY_ELEMENT ((Eterm) 7) /* Note! Must be last... */ +#define PRT_BAR ((Eterm) 0) +#define PRT_COMMA ((Eterm) 1) +#define PRT_CLOSE_LIST ((Eterm) 2) +#define PRT_CLOSE_TUPLE ((Eterm) 3) +#define PRT_ASSOC ((Eterm) 4) +#define PRT_TERM ((Eterm) 5) +#define PRT_ONE_CONS ((Eterm) 6) +#define PRT_PATCH_FUN_SIZE ((Eterm) 7) +#define PRT_LAST_ARRAY_ELEMENT ((Eterm) 8) /* Note! Must be last... */ static int print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount, @@ -260,6 +262,9 @@ print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount, case PRT_CLOSE_TUPLE: PRINT_CHAR(res, fn, arg, '}'); goto L_outer_loop; + case PRT_ASSOC: + PRINT_STRING(res, fn, arg, "=>"); + goto L_outer_loop; default: popped.word = WSTACK_POP(s); @@ -483,6 +488,37 @@ print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount, PRINT_CHAR(res, fn, arg, '>'); } break; + case MAP_DEF: + { + Uint n; + Eterm *ks, *vs; + map_t *mp = (map_t *)map_val(wobj); + n = map_get_size(mp); + ks = map_get_keys(mp); + vs = map_get_values(mp); + + PRINT_CHAR(res, fn, arg, '#'); + PRINT_CHAR(res, fn, arg, '{'); + WSTACK_PUSH(s, PRT_CLOSE_TUPLE); + if (n > 0) { + n--; + WSTACK_PUSH(s, vs[n]); + WSTACK_PUSH(s, PRT_TERM); + WSTACK_PUSH(s, PRT_ASSOC); + WSTACK_PUSH(s, ks[n]); + WSTACK_PUSH(s, PRT_TERM); + + while (n--) { + WSTACK_PUSH(s, PRT_COMMA); + WSTACK_PUSH(s, vs[n]); + WSTACK_PUSH(s, PRT_TERM); + WSTACK_PUSH(s, PRT_ASSOC); + WSTACK_PUSH(s, ks[n]); + WSTACK_PUSH(s, PRT_TERM); + } + } + } + break; default: PRINT_STRING(res, fn, arg, "<unknown:"); PRINT_POINTER(res, fn, arg, wobj); diff --git a/erts/emulator/beam/erl_term.c b/erts/emulator/beam/erl_term.c index 2f206ffbec..28cbe7004f 100644 --- a/erts/emulator/beam/erl_term.c +++ b/erts/emulator/beam/erl_term.c @@ -23,6 +23,7 @@ #include "sys.h" #include "erl_vm.h" #include "global.h" +#include "erl_map.h" #include <stdlib.h> #include <stdio.h> @@ -85,7 +86,10 @@ unsigned tag_val_def(Wterm x) case (_TAG_HEADER_EXTERNAL_PID >> _TAG_PRIMARY_SIZE): return EXTERNAL_PID_DEF; case (_TAG_HEADER_EXTERNAL_PORT >> _TAG_PRIMARY_SIZE): return EXTERNAL_PORT_DEF; case (_TAG_HEADER_EXTERNAL_REF >> _TAG_PRIMARY_SIZE): return EXTERNAL_REF_DEF; - default: return BINARY_DEF; + case (_TAG_HEADER_REFC_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; + case (_TAG_HEADER_HEAP_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; + case (_TAG_HEADER_SUB_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; + case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE): return MAP_DEF; } break; } diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h index 50d3e63c58..f10a3a9d38 100644 --- a/erts/emulator/beam/erl_term.h +++ b/erts/emulator/beam/erl_term.h @@ -135,11 +135,12 @@ struct erl_node_; /* Declared in erl_node_tables.h */ #define REF_SUBTAG (0x4 << _TAG_PRIMARY_SIZE) /* REF */ #define FUN_SUBTAG (0x5 << _TAG_PRIMARY_SIZE) /* FUN */ #define FLOAT_SUBTAG (0x6 << _TAG_PRIMARY_SIZE) /* FLOAT */ -#define EXPORT_SUBTAG (0x7 << _TAG_PRIMARY_SIZE) /* FLOAT */ +#define EXPORT_SUBTAG (0x7 << _TAG_PRIMARY_SIZE) /* FLOAT */ #define _BINARY_XXX_MASK (0x3 << _TAG_PRIMARY_SIZE) #define REFC_BINARY_SUBTAG (0x8 << _TAG_PRIMARY_SIZE) /* BINARY */ #define HEAP_BINARY_SUBTAG (0x9 << _TAG_PRIMARY_SIZE) /* BINARY */ #define SUB_BINARY_SUBTAG (0xA << _TAG_PRIMARY_SIZE) /* BINARY */ +#define MAP_SUBTAG (0xB << _TAG_PRIMARY_SIZE) /* MAP */ #define EXTERNAL_PID_SUBTAG (0xC << _TAG_PRIMARY_SIZE) /* EXTERNAL_PID */ #define EXTERNAL_PORT_SUBTAG (0xD << _TAG_PRIMARY_SIZE) /* EXTERNAL_PORT */ #define EXTERNAL_REF_SUBTAG (0xE << _TAG_PRIMARY_SIZE) /* EXTERNAL_REF */ @@ -155,6 +156,7 @@ struct erl_node_; /* Declared in erl_node_tables.h */ #define _TAG_HEADER_REFC_BIN (TAG_PRIMARY_HEADER|REFC_BINARY_SUBTAG) #define _TAG_HEADER_HEAP_BIN (TAG_PRIMARY_HEADER|HEAP_BINARY_SUBTAG) #define _TAG_HEADER_SUB_BIN (TAG_PRIMARY_HEADER|SUB_BINARY_SUBTAG) +#define _TAG_HEADER_MAP (TAG_PRIMARY_HEADER|MAP_SUBTAG) #define _TAG_HEADER_EXTERNAL_PID (TAG_PRIMARY_HEADER|EXTERNAL_PID_SUBTAG) #define _TAG_HEADER_EXTERNAL_PORT (TAG_PRIMARY_HEADER|EXTERNAL_PORT_SUBTAG) #define _TAG_HEADER_EXTERNAL_REF (TAG_PRIMARY_HEADER|EXTERNAL_REF_SUBTAG) @@ -354,7 +356,10 @@ _ET_DECLARE_CHECKED(Uint,thing_subtag,Eterm) #define is_value(x) ((x) != THE_NON_VALUE) /* binary object access methods */ -#define is_binary_header(x) (((x) & (_TAG_HEADER_MASK-_BINARY_XXX_MASK)) == _TAG_HEADER_REFC_BIN) +#define is_binary_header(x) \ + ((((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_REFC_BIN) || \ + (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HEAP_BIN) || \ + (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_SUB_BIN)) #define make_binary(x) make_boxed((Eterm*)(x)) #define is_binary(x) (is_boxed((x)) && is_binary_header(*boxed_val((x)))) #define is_not_binary(x) (!is_binary((x))) @@ -1064,8 +1069,8 @@ _ET_DECLARE_CHECKED(Uint,y_reg_index,Uint) /* * Backwards compatibility definitions: - * - #define virtal *_DEF constants with values that fit term order: - * number < atom < ref < fun < port < pid < tuple < nil < cons < binary + * - #define virtual *_DEF constants with values that fit term order: + * number < atom < ref < fun < port < pid < tuple < map < nil < cons < binary * - tag_val_def() function generates virtual _DEF tag * - not_eq_tags() and NUMBER_CODE() defined in terms * of the tag_val_def() function @@ -1074,19 +1079,20 @@ _ET_DECLARE_CHECKED(Uint,y_reg_index,Uint) #define BINARY_DEF 0x0 #define LIST_DEF 0x1 #define NIL_DEF 0x2 -#define TUPLE_DEF 0x3 -#define PID_DEF 0x4 -#define EXTERNAL_PID_DEF 0x5 -#define PORT_DEF 0x6 -#define EXTERNAL_PORT_DEF 0x7 -#define EXPORT_DEF 0x8 -#define FUN_DEF 0x9 -#define REF_DEF 0xa -#define EXTERNAL_REF_DEF 0xb -#define ATOM_DEF 0xc -#define FLOAT_DEF 0xd -#define BIG_DEF 0xe -#define SMALL_DEF 0xf +#define MAP_DEF 0x3 +#define TUPLE_DEF 0x4 +#define PID_DEF 0x5 +#define EXTERNAL_PID_DEF 0x6 +#define PORT_DEF 0x7 +#define EXTERNAL_PORT_DEF 0x8 +#define EXPORT_DEF 0x9 +#define FUN_DEF 0xa +#define REF_DEF 0xb +#define EXTERNAL_REF_DEF 0xc +#define ATOM_DEF 0xd +#define FLOAT_DEF 0xe +#define BIG_DEF 0xf +#define SMALL_DEF 0x10 #if ET_DEBUG extern unsigned tag_val_def_debug(Wterm, const char*, unsigned); @@ -1096,8 +1102,8 @@ extern unsigned tag_val_def(Wterm); #endif #define not_eq_tags(X,Y) (tag_val_def((X)) ^ tag_val_def((Y))) -#define NUMBER_CODE(x,y) ((tag_val_def(x) << 4) | tag_val_def(y)) -#define _NUMBER_CODE(TX,TY) ((TX << 4) | TY) +#define NUMBER_CODE(x,y) ((tag_val_def(x) << 5) | tag_val_def(y)) +#define _NUMBER_CODE(TX,TY) ((TX << 5) | TY) #define SMALL_SMALL _NUMBER_CODE(SMALL_DEF,SMALL_DEF) #define SMALL_BIG _NUMBER_CODE(SMALL_DEF,BIG_DEF) #define SMALL_FLOAT _NUMBER_CODE(SMALL_DEF,FLOAT_DEF) diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index 292d135946..5b81d814c6 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2012-2013. All Rights Reserved. + * Copyright Ericsson AB 2012-2014. All Rights Reserved. * * The contents of this file are subject to the Erlang Public License, * Version 1.1, (the "License"); you may not use this file except in @@ -202,23 +202,37 @@ int eq(Eterm, Eterm); #define EQ(x,y) (((x) == (y)) || (is_not_both_immed((x),(y)) && eq((x),(y)))) #if HALFWORD_HEAP -Sint cmp_rel(Eterm, Eterm*, Eterm, Eterm*); -#define CMP(A,B) cmp_rel(A,NULL,B,NULL) +Sint cmp_rel_opt(Eterm, Eterm*, Eterm, Eterm*, int); +#define cmp_rel(A,A_BASE,B,B_BASE) cmp_rel_opt(A,A_BASE,B,B_BASE,0) +#define cmp_rel_term(A,A_BASE,B,B_BASE) cmp_rel_opt(A,A_BASE,B,B_BASE,1) +#define CMP(A,B) cmp_rel_opt(A,NULL,B,NULL,0) +#define CMP_TERM(A,B) cmp_rel_opt(A,NULL,B,NULL,1) #else -Sint cmp(Eterm, Eterm); -#define cmp_rel(A,A_BASE,B,B_BASE) cmp(A,B) -#define CMP(A,B) cmp(A,B) +Sint cmp(Eterm, Eterm, int); +#define cmp_rel(A,A_BASE,B,B_BASE) cmp(A,B,0) +#define cmp_rel_term(A,A_BASE,B,B_BASE) cmp(A,B,1) +#define CMP(A,B) cmp(A,B,0) +#define CMP_TERM(A,B) cmp(A,B,1) #endif -#define cmp_lt(a,b) (CMP((a),(b)) < 0) -#define cmp_le(a,b) (CMP((a),(b)) <= 0) -#define cmp_eq(a,b) (CMP((a),(b)) == 0) -#define cmp_ne(a,b) (CMP((a),(b)) != 0) -#define cmp_ge(a,b) (CMP((a),(b)) >= 0) -#define cmp_gt(a,b) (CMP((a),(b)) > 0) - -#define CMP_LT(a,b) ((a) != (b) && cmp_lt((a),(b))) -#define CMP_GE(a,b) ((a) == (b) || cmp_ge((a),(b))) -#define CMP_EQ(a,b) ((a) == (b) || cmp_eq((a),(b))) -#define CMP_NE(a,b) ((a) != (b) && cmp_ne((a),(b))) + +#define cmp_lt(a,b) (CMP((a),(b)) < 0) +#define cmp_le(a,b) (CMP((a),(b)) <= 0) +#define cmp_eq(a,b) (CMP((a),(b)) == 0) +#define cmp_ne(a,b) (CMP((a),(b)) != 0) +#define cmp_ge(a,b) (CMP((a),(b)) >= 0) +#define cmp_gt(a,b) (CMP((a),(b)) > 0) + +#define cmp_lt_term(a,b) (CMP_TERM((a),(b)) < 0) +#define cmp_le_term(a,b) (CMP_TERM((a),(b)) <= 0) +#define cmp_ge_term(a,b) (CMP_TERM((a),(b)) >= 0) +#define cmp_gt_term(a,b) (CMP_TERM((a),(b)) > 0) + +#define CMP_LT(a,b) ((a) != (b) && cmp_lt((a),(b))) +#define CMP_GE(a,b) ((a) == (b) || cmp_ge((a),(b))) +#define CMP_EQ(a,b) ((a) == (b) || cmp_eq((a),(b))) +#define CMP_NE(a,b) ((a) != (b) && cmp_ne((a),(b))) + +#define CMP_LT_TERM(a,b) ((a) != (b) && cmp_lt_term((a),(b))) +#define CMP_GE_TERM(a,b) ((a) == (b) || cmp_ge_term((a),(b))) #endif diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index 5e7a5cab6e..a4cc3435c3 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -42,6 +42,7 @@ #include "erl_binary.h" #include "erl_bits.h" #include "erl_zlib.h" +#include "erl_map.h" #ifdef HIPE #include "hipe_mode_switch.h" @@ -2555,6 +2556,38 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, } break; + case MAP_DEF: + { + map_t *mp = (map_t*)map_val(obj); + Uint size = map_get_size(mp); + Eterm *mptr; + + *ep++ = MAP_EXT; + put_int32(size, ep); ep += 4; + + /* Push values first */ + if (size > 0) { + mptr = map_get_values(mp); + for (i = size-1; i >= 1; i--) { + WSTACK_PUSH(s, ENC_TERM); + WSTACK_PUSH(s, (UWord) mptr[i]); + } + + WSTACK_PUSH(s, ENC_TERM); + WSTACK_PUSH(s, (UWord) mptr[0]); + + mptr = map_get_keys(mp); + for (i = size-1; i >= 1; i--) { + WSTACK_PUSH(s, ENC_TERM); + WSTACK_PUSH(s, (UWord) mptr[i]); + } + + obj = mptr[0]; + goto L_jump_start; + } + } + break; + case FLOAT_DEF: GET_DOUBLE(obj, f); if (dflags & DFLAG_NEW_FLOATS) { @@ -2845,6 +2878,7 @@ dec_term(ErtsDistExternal *edep, Eterm** hpp, byte* ep, ErlOffHeap* off_heap, int n; ErtsAtomEncoding char_enc; register Eterm* hp; /* Please don't take the address of hp */ + Eterm *maps_head = NULL; /* for validation of maps */ Eterm* next; SWord reds; @@ -3469,6 +3503,65 @@ dec_term_atom_common: break; } break; + case MAP_EXT: + { + map_t *mp; + Uint32 size,n; + Eterm *kptr,*vptr; + Eterm keys; + + size = get_int32(ep); ep += 4; + + keys = make_tuple(hp); + *hp++ = make_arityval(size); + kptr = hp; + hp += size; + + mp = (map_t*)hp; + hp += MAP_HEADER_SIZE; + vptr = hp; + hp += size; + + /* kptr, first word for keys + * vptr, first word for values + */ + + /* + * Use thing_word to link through decoded maps. + * The list of maps is for later validation. + */ + + mp->thing_word = (Eterm) COMPRESS_POINTER(maps_head); + maps_head = (Eterm *) mp; + + mp->size = size; + mp->keys = keys; + *objp = make_map(mp); + + /* We assume the map is wellformed, meaning: + * - ascending key order + * - unique keys + */ + + objp = vptr + size - 1; + n = size; + + while (n-- > 0) { + *objp = (Eterm) COMPRESS_POINTER(next); + next = objp; + objp--; + } + + objp = kptr + size - 1; + n = size; + + while (n-- > 0) { + *objp = (Eterm) COMPRESS_POINTER(next); + next = objp; + objp--; + } + } + break; case NEW_FUN_EXT: { ErlFunThing* funp = (ErlFunThing *) hp; @@ -3678,21 +3771,7 @@ dec_term_atom_common: } default: - error: - /* UNDO: - * Must unlink all off-heap objects that may have been - * linked into the process. - */ - if (hp < *hpp) { /* Sometimes we used hp and sometimes *hpp */ - hp = *hpp; /* the largest must be the freshest */ - } - undo_offheap_in_area(off_heap, hp_saved, hp); - *hpp = hp_saved; - if (ctx) { - ctx->state = B2TDecodeFail; - ctx->reds = reds; - } - return NULL; + goto error; } if (--reds <= 0) { @@ -3710,12 +3789,43 @@ dec_term_atom_common: } } } + + /* Iterate through all the maps and check for validity and sort keys + * - done here for when we know it is complete. + */ + + while (maps_head) { + next = (Eterm *)(EXPAND_POINTER(*maps_head)); + *maps_head = MAP_HEADER; + if (!erts_validate_and_sort_map((map_t*)maps_head)) + goto error; + maps_head = next; + } + if (ctx) { ctx->state = B2TDone; ctx->reds = reds; } + *hpp = hp; return ep; + +error: + /* UNDO: + * Must unlink all off-heap objects that may have been + * linked into the process. + */ + if (hp < *hpp) { /* Sometimes we used hp and sometimes *hpp */ + hp = *hpp; /* the largest must be the freshest */ + } + undo_offheap_in_area(off_heap, hp_saved, hp); + *hpp = hp_saved; + if (ctx) { + ctx->state = B2TDecodeFail; + ctx->reds = reds; + } + + return NULL; } /* returns the number of bytes needed to encode an object @@ -3885,6 +3995,46 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, goto outer_loop; } break; + case MAP_DEF: + { + map_t *mp = (map_t*)map_val(obj); + Uint size = map_get_size(mp); + Uint i; + Eterm *ptr; + + result += 1 + 4; /* tag + 4 bytes size */ + + /* push values first */ + ptr = map_get_values(mp); + i = size; + while(i--) { + if (is_list(*ptr)) { + if ((m = is_string(*ptr)) && (m < MAX_STRING_LEN)) { + result += m + 2 + 1; + } else { + result += 5; + } + } + ESTACK_PUSH(s,*ptr); + ++ptr; + } + + ptr = map_get_keys(mp); + i = size; + while(i--) { + if (is_list(*ptr)) { + if ((m = is_string(*ptr)) && (m < MAX_STRING_LEN)) { + result += m + 2 + 1; + } else { + result += 5; + } + } + ESTACK_PUSH(s,*ptr); + ++ptr; + } + goto outer_loop; + } + break; case FLOAT_DEF: if (dflags & DFLAG_NEW_FLOATS) { result += 9; @@ -4175,6 +4325,13 @@ init_done: ADDTERMS(n); heap_size += n + 1; break; + case MAP_EXT: + CHKSIZE(4); + n = get_int32(ep); + ep += 4; + ADDTERMS(2*n); + heap_size += 3 + n + 1 + n; + break; case STRING_EXT: CHKSIZE(2); n = get_int16(ep); diff --git a/erts/emulator/beam/external.h b/erts/emulator/beam/external.h index 83001b2c7e..bf00958eb1 100644 --- a/erts/emulator/beam/external.h +++ b/erts/emulator/beam/external.h @@ -50,6 +50,7 @@ #define LARGE_BIG_EXT 'o' #define NEW_FUN_EXT 'p' #define EXPORT_EXT 'q' +#define MAP_EXT 't' #define FUN_EXT 'u' #define ATOM_UTF8_EXT 'v' #define SMALL_ATOM_UTF8_EXT 'w' diff --git a/erts/emulator/beam/global.h b/erts/emulator/beam/global.h index 83a8911a36..8fcb95d0e2 100755 --- a/erts/emulator/beam/global.h +++ b/erts/emulator/beam/global.h @@ -998,6 +998,7 @@ Eterm erts_gc_length_1(Process* p, Eterm* reg, Uint live); Eterm erts_gc_size_1(Process* p, Eterm* reg, Uint live); Eterm erts_gc_bit_size_1(Process* p, Eterm* reg, Uint live); Eterm erts_gc_byte_size_1(Process* p, Eterm* reg, Uint live); +Eterm erts_gc_map_size_1(Process* p, Eterm* reg, Uint live); Eterm erts_gc_abs_1(Process* p, Eterm* reg, Uint live); Eterm erts_gc_float_1(Process* p, Eterm* reg, Uint live); Eterm erts_gc_round_1(Process* p, Eterm* reg, Uint live); diff --git a/erts/emulator/beam/io.c b/erts/emulator/beam/io.c index 49af86b36a..3b16cdeb4a 100644 --- a/erts/emulator/beam/io.c +++ b/erts/emulator/beam/io.c @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 1996-2013. All Rights Reserved. + * Copyright Ericsson AB 1996-2014. All Rights Reserved. * * The contents of this file are subject to the Erlang Public License, * Version 1.1, (the "License"); you may not use this file except in @@ -46,6 +46,7 @@ #define ERTS_WANT_EXTERNAL_TAGS #include "external.h" #include "dtrace-wrapper.h" +#include "erl_map.h" extern ErlDrvEntry fd_driver_entry; extern ErlDrvEntry vanilla_driver_entry; @@ -5293,6 +5294,17 @@ driver_deliver_term(Eterm to, ErlDrvTermData* data, int len) depth++; break; } + case ERL_DRV_MAP: { /* int */ + ERTS_DDT_CHK_ENOUGH_ARGS(1); + if ((int) ptr[0] < 0) ERTS_DDT_FAIL; + need += MAP_HEADER_SIZE + 1 + 2*ptr[0]; + depth -= 2*ptr[0]; + if (depth < 0) ERTS_DDT_FAIL; + ptr++; + depth++; + break; + } + default: ERTS_DDT_FAIL; } @@ -5529,6 +5541,36 @@ driver_deliver_term(Eterm to, ErlDrvTermData* data, int len) ptr += 2; break; + case ERL_DRV_MAP: { /* int */ + int size = (int)ptr[0]; + Eterm* tp = hp; + Eterm* vp; + map_t *mp; + + *tp = make_arityval(size); + + hp += 1 + size; + mp = (map_t*)hp; + mp->thing_word = MAP_HEADER; + mp->size = size; + mp->keys = make_tuple(tp); + mess = make_map(mp); + + hp += MAP_HEADER_SIZE + size; /* advance "heap" pointer */ + + tp += size; /* point at last key */ + vp = hp - 1; /* point at last value */ + + while(size--) { + *vp-- = ESTACK_POP(stack); + *tp-- = ESTACK_POP(stack); + } + if (!erts_validate_and_sort_map(mp)) + ERTS_DDT_FAIL; + ptr++; + break; + } + } ESTACK_PUSH(stack, mess); } diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab index c29f3f9b1b..f35997efee 100644 --- a/erts/emulator/beam/ops.tab +++ b/erts/emulator/beam/ops.tab @@ -1466,6 +1466,75 @@ apply I apply_last I P # +# Map instructions in R17. +# + +# put_map Fail Src Dst Live Size Rest=* => jump Fail +# is_map Fail Src => jump Fail +# has_map_field Fail Src Key => jump Fail +# get_map_element Fail Src Key Dst => jump Fail + +put_map_assoc F n Dst Live Size Rest=* => new_map F Dst Live Size Rest +put_map_exact F n Dst Live Size Rest=* => new_map F Dst Live Size Rest +put_map_assoc F Src Dst Live Size Rest=* => \ + update_map_assoc F Src Dst Live Size Rest +put_map_exact F Src Dst Live Size Rest=* => \ + update_map_exact F Src Dst Live Size Rest + +new_map j d I I +update_map_assoc j d d I I +update_map_exact j d d I I + +is_map Fail cq => jump Fail + +%macro: is_map IsMap -fail_action +is_map f r +is_map f x +is_map f y + +has_map_field Fail Src=rxy Key=arxy => i_has_map_field Fail Src Key +has_map_field Fail Src Key => move Key x | i_has_map_field Fail Src x + +%macro: i_has_map_field HasMapField -fail_action +i_has_map_field f r a +i_has_map_field f x a +i_has_map_field f y a +i_has_map_field f r r +i_has_map_field f x r +i_has_map_field f y r +i_has_map_field f r x +i_has_map_field f x x +i_has_map_field f y x +i_has_map_field f r y +i_has_map_field f x y +i_has_map_field f y y + +get_map_element Fail Src=rxy Key=ax Dst => i_get_map_element Fail Src Key Dst +get_map_element Fail Src=rxy Key=rycq Dst => \ + move Key x | i_get_map_element Fail Src x Dst +get_map_element Fail Src Key Dst => jump Fail + +%macro: i_get_map_element GetMapElement -fail_action +i_get_map_element f r a r +i_get_map_element f x a r +i_get_map_element f y a r +i_get_map_element f r a x +i_get_map_element f x a x +i_get_map_element f y a x +i_get_map_element f r a y +i_get_map_element f x a y +i_get_map_element f y a y +i_get_map_element f r x r +i_get_map_element f x x r +i_get_map_element f y x r +i_get_map_element f r x x +i_get_map_element f x x x +i_get_map_element f y x x +i_get_map_element f r x y +i_get_map_element f x x y +i_get_map_element f y x y + +# # Optimize addition and subtraction of small literals using # the i_increment/4 instruction (in bodies, not in guards). # diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index e0776cf67d..bc4a05d385 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -31,6 +31,7 @@ #include "bif.h" #include "erl_binary.h" #include "erl_bits.h" +#include "erl_map.h" #include "packet_parser.h" #include "erl_gc.h" #define ERTS_WANT_DB_INTERNAL__ @@ -734,6 +735,8 @@ erts_bld_atom_2uint_3tup_list(Uint **hpp, Uint *szp, Sint length, #define FUNNY_NUMBER10 268440479 #define FUNNY_NUMBER11 268440577 #define FUNNY_NUMBER12 268440581 +#define FUNNY_NUMBER13 268440593 +#define FUNNY_NUMBER14 268440611 static Uint32 hash_binary_bytes(Eterm bin, Uint sz, Uint32 hash) @@ -785,10 +788,10 @@ Uint32 make_hash(Eterm term_arg) unsigned op; /* Must not collide with the real tag_val_def's: */ -#define MAKE_HASH_TUPLE_OP 0x10 -#define MAKE_HASH_FUN_OP 0x11 -#define MAKE_HASH_CDR_PRE_OP 0x12 -#define MAKE_HASH_CDR_POST_OP 0x13 +#define MAKE_HASH_TUPLE_OP 0x11 +#define MAKE_HASH_TERM_ARRAY_OP 0x12 +#define MAKE_HASH_CDR_PRE_OP 0x13 +#define MAKE_HASH_CDR_POST_OP 0x14 /* ** Convenience macro for calculating a bytewise hash on an unsigned 32 bit @@ -877,7 +880,7 @@ tail_recur: hash = hash*FUNNY_NUMBER2 + funp->fe->old_uniq; if (num_free > 0) { if (num_free > 1) { - WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_FUN_OP); + WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_TERM_ARRAY_OP); } term = funp->env[0]; goto tail_recur; @@ -967,6 +970,24 @@ tail_recur: hash *= is_neg ? FUNNY_NUMBER4 : FUNNY_NUMBER3; break; } + case MAP_DEF: + { + map_t *mp = (map_t *)map_val(term); + int size = map_get_size(mp); + Eterm *ks = map_get_keys(mp); + Eterm *vs = map_get_values(mp); + + /* Use a prime with size to remedy some of + * the {} and <<>> hash problems */ + hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + size; + if (size == 0) + break; + + /* push values first */ + WSTACK_PUSH3(stack, (UWord)vs, (UWord) size, MAKE_HASH_TERM_ARRAY_OP); + WSTACK_PUSH3(stack, (UWord)ks, (UWord) size, MAKE_HASH_TERM_ARRAY_OP); + break; + } case TUPLE_DEF: { Eterm* ptr = tuple_val(term); @@ -976,7 +997,7 @@ tail_recur: op = MAKE_HASH_TUPLE_OP; }/*fall through*/ case MAKE_HASH_TUPLE_OP: - case MAKE_HASH_FUN_OP: + case MAKE_HASH_TERM_ARRAY_OP: { Uint i = (Uint) WSTACK_POP(stack); Eterm* ptr = (Eterm*) WSTACK_POP(stack); @@ -1070,9 +1091,11 @@ Uint32 make_hash2(Eterm term) { Uint32 hash; + Uint32 hash_xor_keys = 0; + Uint32 hash_xor_values = 0; DeclareTmpHeapNoproc(tmp_big,2); -/* (HCONST * {2, ..., 14}) mod 2^32 */ +/* (HCONST * {2, ..., 16}) mod 2^32 */ #define HCONST_2 0x3c6ef372UL #define HCONST_3 0xdaa66d2bUL #define HCONST_4 0x78dde6e4UL @@ -1087,6 +1110,11 @@ make_hash2(Eterm term) #define HCONST_13 0x08d12e65UL #define HCONST_14 0xa708a81eUL #define HCONST_15 0x454021d7UL +#define HCONST_16 0xe3779b90UL + +#define HASH_MAP_TAIL (_make_header(1,_TAG_HEADER_REF)) +#define HASH_MAP_KEY (_make_header(2,_TAG_HEADER_REF)) +#define HASH_MAP_VAL (_make_header(3,_TAG_HEADER_REF)) #define UINT32_HASH_2(Expr1, Expr2, AConst) \ do { \ @@ -1182,11 +1210,45 @@ make_hash2(Eterm term) UINT32_HASH(arity, HCONST_9); if (arity == 0) /* Empty tuple */ goto hash2_common; - for (i = arity; i >= 2; i--) { + for (i = arity; i >= 1; i--) { tmp = elem[i]; ESTACK_PUSH(s, tmp); } - term = elem[1]; + goto hash2_common; + } + break; + case MAP_SUBTAG: + { + map_t *mp = (map_t *)map_val(term); + int i; + int size = map_get_size(mp); + Eterm *ks = map_get_keys(mp); + Eterm *vs = map_get_values(mp); + UINT32_HASH(size, HCONST_16); + if (size == 0) { + goto hash2_common; + } + ESTACK_PUSH(s, hash_xor_values); + ESTACK_PUSH(s, hash_xor_keys); + ESTACK_PUSH(s, hash); + ESTACK_PUSH(s, HASH_MAP_TAIL); + hash = 0; + hash_xor_keys = 0; + hash_xor_values = 0; + for (i = size - 1; i >= 0; i--) { + tmp = vs[i]; + ESTACK_PUSH(s, HASH_MAP_VAL); + ESTACK_PUSH(s, tmp); + } + /* We do not want to expose the tuple representation. + * Do not push the keys as a tuple. + */ + for (i = size - 1; i >= 0; i--) { + tmp = ks[i]; + ESTACK_PUSH(s, HASH_MAP_KEY); + ESTACK_PUSH(s, tmp); + } + goto hash2_common; } break; case EXPORT_SUBTAG: @@ -1380,15 +1442,47 @@ make_hash2(Eterm term) default: erl_exit(1, "Invalid tag in make_hash2(0x%X)\n", term); hash2_common: + + /* Uint32 hash always has the hash value of the previous term, + * compounded or otherwise. + */ + if (ESTACK_ISEMPTY(s)) { DESTROY_ESTACK(s); UnUseTmpHeapNoproc(2); return hash; } + term = ESTACK_POP(s); + + switch (term) { + case HASH_MAP_TAIL: { + hash = (Uint32) ESTACK_POP(s); + UINT32_HASH(hash_xor_keys, HCONST_16); + UINT32_HASH(hash_xor_values, HCONST_16); + hash_xor_keys = (Uint32) ESTACK_POP(s); + hash_xor_values = (Uint32) ESTACK_POP(s); + goto hash2_common; + } + case HASH_MAP_KEY: + hash_xor_keys ^= hash; + hash = 0; + goto hash2_common; + case HASH_MAP_VAL: + hash_xor_values ^= hash; + hash = 0; + goto hash2_common; + default: + break; + } } } } + +#undef HASH_MAP_TAIL +#undef HASH_MAP_KEY +#undef HASH_MAP_VAL + #undef UINT32_HASH_2 #undef UINT32_HASH #undef SINT32_HASH @@ -1490,7 +1584,7 @@ tail_recur: hash = hash*FUNNY_NUMBER2 + funp->fe->old_uniq; if (num_free > 0) { if (num_free > 1) { - WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_FUN_OP); + WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_TERM_ARRAY_OP); } term = funp->env[0]; goto tail_recur; @@ -1603,6 +1697,24 @@ tail_recur: } break; + case MAP_DEF: + { + map_t *mp = (map_t *)map_val(term); + int size = map_get_size(mp); + Eterm *ks = map_get_keys(mp); + Eterm *vs = map_get_values(mp); + + /* Use a prime with size to remedy some of + * the {} and <<>> hash problems */ + hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + size; + if (size == 0) + break; + + /* push values first */ + WSTACK_PUSH3(stack, (UWord)vs, (UWord) size, MAKE_HASH_TERM_ARRAY_OP); + WSTACK_PUSH3(stack, (UWord)ks, (UWord) size, MAKE_HASH_TERM_ARRAY_OP); + break; + } case TUPLE_DEF: { Eterm* ptr = tuple_val(term); @@ -1612,7 +1724,7 @@ tail_recur: op = MAKE_HASH_TUPLE_OP; }/*fall through*/ case MAKE_HASH_TUPLE_OP: - case MAKE_HASH_FUN_OP: + case MAKE_HASH_TERM_ARRAY_OP: { Uint i = (Uint) WSTACK_POP(stack); Eterm* ptr = (Eterm*) WSTACK_POP(stack); @@ -1640,7 +1752,7 @@ tail_recur: return hash; #undef MAKE_HASH_TUPLE_OP -#undef MAKE_HASH_FUN_OP +#undef MAKE_HASH_TERM_ARRAY_OP #undef MAKE_HASH_CDR_PRE_OP #undef MAKE_HASH_CDR_POST_OP } @@ -2007,6 +2119,18 @@ tailrecur_ne: ++bb; goto term_array; } + case MAP_SUBTAG: + { + aa = map_val_rel(a, a_base); + if (!is_boxed(b) || *boxed_val_rel(b,b_base) != *aa) + goto not_equal; + bb = map_val_rel(b,b_base); + if ((sz = map_get_size((map_t*)aa)) == 0) goto pop_next; + aa += 2; + bb += 2; + sz += 1; /* increment for tuple-keys */ + goto term_array; + } case REFC_BINARY_SUBTAG: case HEAP_BINARY_SUBTAG: case SUB_BINARY_SUBTAG: @@ -2281,7 +2405,7 @@ static int cmpbytes(byte *s1, int l1, byte *s2, int l2) * * According to the Erlang Standard, types are orderered as follows: * numbers < (characters) < atoms < refs < funs < ports < pids < - * tuples < [] < conses < binaries. + * tuples < maps < [] < conses < binaries. * * Note that characters are currently not implemented. * @@ -2301,10 +2425,14 @@ static int cmp_atoms(Eterm a, Eterm b) bb->name+3, bb->len-3); } +/* cmp(Eterm a, Eterm b, int exact) + * exact = 1 -> term-based compare + * exact = 0 -> arith-based compare + */ #if HALFWORD_HEAP -Sint cmp_rel(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base) +Sint cmp_rel_opt(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base, int exact) #else -Sint cmp(Eterm a, Eterm b) +Sint cmp(Eterm a, Eterm b, int exact) #endif { DECLARE_WSTACK(stack); @@ -2464,7 +2592,25 @@ tailrecur_ne: ++aa; ++bb; goto term_array; + case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE) : + if (!is_map_rel(b,b_base)) { + a_tag = MAP_DEF; + goto mixed_types; + } + aa = (Eterm *)map_val_rel(a,a_base); + bb = (Eterm *)map_val_rel(b,b_base); + i = map_get_size((map_t*)aa); + if (i != map_get_size((map_t*)bb)) { + RETURN_NEQ((int)(i - map_get_size((map_t*)bb))); + } + if (i == 0) { + goto pop_next; + } + aa += 2; + bb += 2; + i += 1; /* increment for tuple-keys */ + goto term_array; case (_TAG_HEADER_FLOAT >> _TAG_PRIMARY_SIZE): if (!is_float_rel(b,b_base)) { a_tag = FLOAT_DEF; @@ -2710,6 +2856,7 @@ tailrecur_ne: j = big_sign(aw) ? -1 : 1; break; case SMALL_FLOAT: + if (exact) goto exact_fall_through; GET_DOUBLE(bw, f2); if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { /* Float is within the no loss limit */ @@ -2735,12 +2882,14 @@ tailrecur_ne: #endif /* ERTS_SIZEOF_ETERM == 8 */ break; case FLOAT_BIG: + if (exact) goto exact_fall_through; { Wterm tmp = aw; aw = bw; bw = tmp; }/* fall through */ case BIG_FLOAT: + if (exact) goto exact_fall_through; GET_DOUBLE(bw, f2); if ((f2.fd < (double) (MAX_SMALL + 1)) && (f2.fd > (double) (MIN_SMALL - 1))) { @@ -2770,6 +2919,7 @@ tailrecur_ne: } break; case FLOAT_SMALL: + if (exact) goto exact_fall_through; GET_DOUBLE(aw, f1); if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) { /* Float is within the no loss limit */ @@ -2794,6 +2944,7 @@ tailrecur_ne: } #endif /* ERTS_SIZEOF_ETERM == 8 */ break; +exact_fall_through: default: j = b_tag - a_tag; } |