diff options
| -rw-r--r-- | erts/emulator/Makefile.in | 2 | ||||
| -rw-r--r-- | erts/emulator/beam/beam_emu.c | 341 | ||||
| -rw-r--r-- | erts/emulator/beam/bif.tab | 6 | ||||
| -rw-r--r-- | erts/emulator/beam/copy.c | 32 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_bif_op.c | 12 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_db_util.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_debug.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_gc.c | 1 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_gc.h | 37 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.c | 225 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.h | 64 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_printf_term.c | 52 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_term.c | 6 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_term.h | 44 | ||||
| -rw-r--r-- | erts/emulator/beam/utils.c | 41 | ||||
| -rw-r--r-- | erts/emulator/hipe/hipe_bif2.c | 1 | ||||
| -rw-r--r-- | erts/emulator/hipe/hipe_debug.c | 1 |
17 files changed, 811 insertions, 56 deletions
diff --git a/erts/emulator/Makefile.in b/erts/emulator/Makefile.in index b270099566..54365f279c 100644 --- a/erts/emulator/Makefile.in +++ b/erts/emulator/Makefile.in @@ -780,7 +780,7 @@ RUN_OBJS = \ $(OBJDIR)/erl_zlib.o $(OBJDIR)/erl_nif.o \ $(OBJDIR)/erl_bif_binary.o $(OBJDIR)/erl_ao_firstfit_alloc.o \ $(OBJDIR)/erl_thr_queue.o $(OBJDIR)/erl_sched_spec_pre_alloc.o \ - $(OBJDIR)/erl_ptab.o + $(OBJDIR)/erl_ptab.o $(OBJDIR)/erl_map.o ifeq ($(TARGET),win32) DRV_OBJS = \ diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c index 7fecdd5c5f..5c955b9566 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,11 @@ 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(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 +2341,37 @@ 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_jddII): { + Eterm res; + Eterm map; + + GetArg1(1, map); + x(0) = r(0); + SWAPOUT; + res = update_map(c_p, reg, map, I); + SWAPIN; + if (res) { + r(0) = x(0); + StoreResult(res, Arg(2)); + Next(5+Arg(4)); + } else { + goto lb_Cl_error; + } + } + + /* * All guards with zero arguments have special instructions: * self/0 @@ -6227,6 +6276,296 @@ 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 = 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; + Eterm *tp; + 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; + tp = &Arg(4); + keys = make_tuple(thp); + *thp++ = make_arityval(n/2); + + mp = (map_t *)mhp; mhp += 3; + mp->thing_word = MAP_HEADER; + mp->size = n/2; + mp->keys = keys; + + for (i = 0; i < n/2; i++) { + GET_TERM(*tp++, *thp++); + GET_TERM(*tp++, *mhp++); + } + p->htop = mhp; + return make_map(mp); +} + + +/* This entire instruction will be split into two. + * 1) update_map_exact (literals) <- this can be much more optimized + * 2) update_map_assoc (literals) + * Also update_map is pretty bad code as it stands now. + */ + +static Eterm +update_map(Process* p, Eterm* reg, Eterm map, BeamInstr* I) +{ + Uint n; + Uint i; + 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; + Eterm* new_p; + Eterm new_key; + Eterm* kp; + + if (is_not_map(map)) { + return 0; + } + + 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 are new). + */ + + num_updates = Arg(4) / 2; + need = 2*(num_old+num_updates) + 4; + 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, optimistically assuming that there are no + * new keys, allowing us to keep 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 += 3; + mp->thing_word = MAP_HEADER; + mp->size = num_old; + mp->keys = old_mp->keys; + + ASSERT(num_updates > 0); + + /* Get array of key/value pairs to be updated */ + new_p = &Arg(5); + GET_TERM(*new_p, new_key); + + n = num_updates; + + for (i = 0; i < num_old; i++) { + if (new_key == THE_NON_VALUE || !eq(*old_keys, new_key)) { + /* not same keys */ + *hp++ = *old_vals; + } else { + GET_TERM(new_p[1], *hp); + hp++; + n--; + if (n == 0) { + new_key = THE_NON_VALUE; + } else { + new_p += 2; + GET_TERM(*new_p, new_key); + } + } + old_vals++, old_keys++; + } + + /* + * If we have exhausted the update list we are done. + */ + + if (n == 0) { + p->htop = hp; + return res; + } + + /* + * There were some new keys. We'll have to start over and rebuild + * the key tuple too. + */ + + kp = p->htop; + *kp++ = make_arityval(0); + + res = make_map(hp); + mp = (map_t *)hp; hp += 3; + 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; + + for (;;) { + Eterm key; + Sint c; + + ASSERT(kp < (Eterm *)mp); + key = *old_keys; + if ((c = cmp(key, new_key)) < 0) { + *kp++ = key; + *hp++ = *old_vals; + old_keys++, old_vals++, num_old--; + } else { /* Replace or insert new */ + *kp++ = new_key; + GET_TERM(new_p[1], *hp++); + if (c == 0) { /* If replacement */ + 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; + } + } + + while (n-- > 0) { + GET_TERM(new_p[0], *kp++); + GET_TERM(new_p[1], *hp++); + new_p += 2; + } + + /* + * All updates done. Now copy the remaining part of the frame's + * keys and values. + */ + + while (num_old-- > 0) { + ASSERT(kp < (Eterm *)mp); + *kp++ = *old_keys++; + *hp++ = *old_vals++; + } + if ((n = (Eterm *)mp - kp) > 0) { + *kp = make_pos_bignum_header(n-1); + } + n = kp - p->htop - 1; /* Actual number of keys/values */ + *p->htop = make_arityval(n); + mp->thing_word = MAP_HEADER; + mp->size = n; + p->htop = hp; + return res; +} +#undef GET_TERM int catchlevel(Process *p) { diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 3ec534f0bc..42515d0494 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -578,6 +578,12 @@ bif os:unsetenv/1 bif re:inspect/2 +ubif erlang:is_map/1 +bif map:to_list/1 +bif map:new/0 +bif map:get/2 +bif map:put/3 + # # 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_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..d903053aa4 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" 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_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..1fd7943c30 --- /dev/null +++ b/erts/emulator/beam/erl_map.c @@ -0,0 +1,225 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2013. 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" + + +BIF_RETTYPE map_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); +} + +BIF_RETTYPE map_new_0(BIF_ALIST_0) { + Eterm* hp; + Eterm tup; + map_t *mp; + + hp = HAlloc(BIF_P, (3 + 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)); +} + +BIF_RETTYPE map_get_2(BIF_ALIST_2) { + if (is_map(BIF_ARG_2)) { + Eterm *hp, *ks,*vs, key, error; + map_t *mp; + Uint n,i; + char *s_error; + + mp = (map_t*)map_val(BIF_ARG_2); + key = BIF_ARG_1; + n = map_get_size(mp); + + if (n == 0) + goto error; + + ks = map_get_keys(mp); + vs = map_get_values(mp); + + if (is_immed(key)) { + for( i = 0; i < n; i++) { + if (ks[i] == key) { + BIF_RET(vs[i]); + } + } + } + + for( i = 0; i < n; i++) { + if (eq(ks[i], key)) { + BIF_RET(vs[i]); + } + } +error: + + 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, key); + BIF_ERROR(BIF_P, EXC_ERROR_2); + } + BIF_ERROR(BIF_P, BADARG); +} + +BIF_RETTYPE map_put_3(BIF_ALIST_3) { + if (is_map(BIF_ARG_3)) { + Sint n,i; + Sint c = 0; + Eterm* hp, *shp; + Eterm *ks,*vs, res, key, tup; + map_t *mp = (map_t*)map_val(BIF_ARG_3); + + key = BIF_ARG_1; + n = map_get_size(mp); + + if (n == 0) { + hp = HAlloc(BIF_P, 4 + 2); + tup = make_tuple(hp); + *hp++ = make_arityval(1); + *hp++ = key; + res = make_map(hp); + *hp++ = MAP_HEADER; + *hp++ = 1; + *hp++ = tup; + *hp++ = BIF_ARG_2; + + BIF_RET(res); + } + + ks = map_get_keys(mp); + vs = map_get_values(mp); + /* only allocate for values, + * assume key-tuple will be intact + */ + + hp = HAlloc(BIF_P, 3 + 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++ = BIF_ARG_2; + vs++; + c = 1; + } else { + *hp++ = *vs++; + } + } + } else { + for( i = 0; i < n; i ++) { + if (eq(ks[i], key)) { + *hp++ = BIF_ARG_2; + vs++; + c = 1; + } else { + *hp++ = *vs++; + } + } + } + + if (c) + BIF_RET(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(BIF_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(*ks, key)) < 0)) { + *shp++ = *ks++; + *hp++ = *vs++; + n--; + } + + *shp++ = key; + *hp++ = BIF_ARG_2; + + 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); + BIF_RET(res); + } + + BIF_ERROR(BIF_P, BADARG); +} diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h new file mode 100644 index 0000000000..ca8ce0f974 --- /dev/null +++ b/erts/emulator/beam/erl_map.h @@ -0,0 +1,64 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2013. 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 + * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = arity + * ---- + * Eterm V1 + * ... + * Eterm Vn, where n = arity + * ----------- + */ + + + +/* 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) + +#endif + 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/utils.c b/erts/emulator/beam/utils.c index e0776cf67d..6cdfd1c989 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__ @@ -785,10 +786,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_FUN_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 @@ -2007,6 +2008,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 +2294,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. * @@ -2464,7 +2477,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; diff --git a/erts/emulator/hipe/hipe_bif2.c b/erts/emulator/hipe/hipe_bif2.c index e09988e2c5..c3687681cf 100644 --- a/erts/emulator/hipe/hipe_bif2.c +++ b/erts/emulator/hipe/hipe_bif2.c @@ -31,6 +31,7 @@ #include "erl_process.h" #include "bif.h" #include "big.h" +#include "erl_map.h" #include "hipe_debug.h" #include "hipe_mode_switch.h" #include "hipe_arch.h" diff --git a/erts/emulator/hipe/hipe_debug.c b/erts/emulator/hipe/hipe_debug.c index bf25ba82af..32694a8f97 100644 --- a/erts/emulator/hipe/hipe_debug.c +++ b/erts/emulator/hipe/hipe_debug.c @@ -36,6 +36,7 @@ #include "beam_load.h" #include "hipe_mode_switch.h" #include "hipe_debug.h" +#include "erl_map.h" static const char dashes[2*sizeof(long)+5] = { [0 ... 2*sizeof(long)+3] = '-' |