aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn-Egil Dahlberg <[email protected]>2013-05-21 18:09:55 +0200
committerBjörn-Egil Dahlberg <[email protected]>2014-01-28 15:56:26 +0100
commit03d5bb0d1bd5d7c4e09ee793a680f2d538fe0122 (patch)
tree31901126a576691551cfb030cb2aef89243b4089
parent345bf9d4634f81ad0343e8c60442bdd293e41835 (diff)
downloadotp-03d5bb0d1bd5d7c4e09ee793a680f2d538fe0122.tar.gz
otp-03d5bb0d1bd5d7c4e09ee793a680f2d538fe0122.tar.bz2
otp-03d5bb0d1bd5d7c4e09ee793a680f2d538fe0122.zip
erts: Initial Map instructions, type and structure
-rw-r--r--erts/emulator/Makefile.in2
-rw-r--r--erts/emulator/beam/beam_emu.c341
-rw-r--r--erts/emulator/beam/bif.tab6
-rw-r--r--erts/emulator/beam/copy.c32
-rw-r--r--erts/emulator/beam/erl_bif_op.c12
-rw-r--r--erts/emulator/beam/erl_db_util.c1
-rw-r--r--erts/emulator/beam/erl_debug.c1
-rw-r--r--erts/emulator/beam/erl_gc.c1
-rw-r--r--erts/emulator/beam/erl_gc.h37
-rw-r--r--erts/emulator/beam/erl_map.c225
-rw-r--r--erts/emulator/beam/erl_map.h64
-rw-r--r--erts/emulator/beam/erl_printf_term.c52
-rw-r--r--erts/emulator/beam/erl_term.c6
-rw-r--r--erts/emulator/beam/erl_term.h44
-rw-r--r--erts/emulator/beam/utils.c41
-rw-r--r--erts/emulator/hipe/hipe_bif2.c1
-rw-r--r--erts/emulator/hipe/hipe_debug.c1
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] = '-'