erts: Initial Map instructions, type and structure

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] = '-'