Merge branch 'egil/maps/OTP-11616'

* egil/maps/OTP-11616: (112 commits)
  compiler: Add core compile test for maps
  compiler: Fix core parse for Maps
  compiler: Fixup #map_pair{} spec
  erts: Strengthen map_SUITE tests
  erts: Update maps_fold test to respect maps:fold/3
  stdlib: Make maps:fold/3 order-independent
  erts: Fixup enif_make_map_put on windows
  erts: Update preloaded erts_internal.beam
  hipe: Fixup update cerl pretty printer
  erts: Add map construction to driver API
  dialyzer: Add maps tests
  dialyzer: Remove dead code
  dialyzer: Reflect map_pair core changes in dialyzer
  hipe: Update cerl pretty printer
  compiler: Update inliner tests
  compiler: Squash #c_map_pair_*{} to #c_map_pair{}
  compiler: Squash #k_map_pair_*{} to #k_map_pair{}
  preloaded: Fixup export cmp_term in erts_internal
  erts: Change 'size' argument of enif_get_map_size from int* to size_t*
  erts: Fix compile error for halfword emulator
  ...

37 files changed, 3668 insertions, 130 deletions

diff --git a/erts/emulator/Makefile.in b/erts/emulator/Makefile.in
index 9125a8024f..f88a4ccc24 100644
--- a/erts/emulator/Makefile.in
+++ b/erts/emulator/Makefile.in
@@ -779,7 +779,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..89d9442526 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -31,6 +31,7 @@
 #include "big.h"
 #include "beam_load.h"
 #include "erl_binary.h"
+#include "erl_map.h"
 #include "erl_bits.h"
 #include "dist.h"
 #include "beam_bp.h"
@@ -701,6 +702,19 @@ extern int count_instructions;
         Fail; 								  \
     }
 
+#define IsMap(Src, Fail) if (is_not_map(Src)) { Fail; }
+
+#define HasMapField(Src, Key, Fail) if (has_not_map_field(Src, Key)) { Fail; }
+
+#define GetMapElement(Src, Key, Dst, Fail)	\
+  do {						\
+     Eterm _res = get_map_element(Src, Key);	\
+     if (is_non_value(_res)) {			\
+        Fail;					\
+     }						\
+     Dst = _res;				\
+  } while (0)
+
 #define IsFunction(X, Action)			\
   do {						\
      if ( !(is_any_fun(X)) ) {			\
@@ -944,7 +958,13 @@ static BeamInstr* apply_fun(Process* p, Eterm fun,
 			    Eterm args, Eterm* reg) NOINLINE;
 static Eterm new_fun(Process* p, Eterm* reg,
 		     ErlFunEntry* fe, int num_free) NOINLINE;
-
+static Eterm new_map(Process* p, Eterm* reg, BeamInstr* I) NOINLINE;
+static Eterm update_map_assoc(Process* p, Eterm* reg,
+			      Eterm map, BeamInstr* I) NOINLINE;
+static Eterm update_map_exact(Process* p, Eterm* reg,
+			      Eterm map, BeamInstr* I) NOINLINE;
+static int has_not_map_field(Eterm map, Eterm key);
+static Eterm get_map_element(Eterm map, Eterm key);
 
 /*
  * Functions not directly called by process_main(). OK to inline.
@@ -2323,6 +2343,55 @@ void process_main(void)
      Goto(*I);
  }
 
+ OpCase(new_map_jdII): {
+     Eterm res;
+
+     x(0) = r(0);
+     SWAPOUT;
+     res = new_map(c_p, reg, I);
+     SWAPIN;
+     r(0) = x(0);
+     StoreResult(res, Arg(1));
+     Next(4+Arg(3));
+ }
+
+ OpCase(update_map_assoc_jddII): {
+     Eterm res;
+     Eterm map;
+
+     GetArg1(1, map);
+     x(0) = r(0);
+     SWAPOUT;
+     res = update_map_assoc(c_p, reg, map, I);
+     SWAPIN;
+     if (is_value(res)) {
+	 r(0) = x(0);
+	 StoreResult(res, Arg(2));
+	 Next(5+Arg(4));
+     } else {
+	 goto badarg;
+     }
+ }
+
+ OpCase(update_map_exact_jddII): {
+     Eterm res;
+     Eterm map;
+
+     GetArg1(1, map);
+     x(0) = r(0);
+     SWAPOUT;
+     res = update_map_exact(c_p, reg, map, I);
+     SWAPIN;
+     if (is_value(res)) {
+	 r(0) = x(0);
+	 StoreResult(res, Arg(2));
+	 Next(5+Arg(4));
+     } else {
+	 goto badarg;
+     }
+ }
+
+
     /*
      * All guards with zero arguments have special instructions:
      * 	self/0
@@ -5031,6 +5100,8 @@ translate_gc_bif(void* gcf)
 	return bit_size_1;
     } else if (gcf == erts_gc_byte_size_1) {
 	return byte_size_1;
+    } else if (gcf == erts_gc_map_size_1) {
+	return map_size_1;
     } else if (gcf == erts_gc_abs_1) {
 	return abs_1;
     } else if (gcf == erts_gc_float_1) {
@@ -6227,6 +6298,397 @@ new_fun(Process* p, Eterm* reg, ErlFunEntry* fe, int num_free)
     return make_fun(funp);
 }
 
+static int has_not_map_field(Eterm map, Eterm key)
+{
+    map_t* mp;
+    Eterm* keys;
+    Uint i;
+    Uint n;
+
+    mp   = (map_t *)map_val(map);
+    keys = map_get_keys(mp);
+    n    = map_get_size(mp);
+    if (is_immed(key)) {
+	for (i = 0; i < n; i++) {
+	    if (keys[i] == key) {
+		return 0;
+	    }
+	}
+    } else {
+	for (i = 0; i <  n; i++) {
+	    if (EQ(keys[i], key)) {
+		return 0;
+	    }
+	}
+    }
+    return 1;
+}
+
+static Eterm get_map_element(Eterm map, Eterm key)
+{
+    map_t *mp;
+    Eterm* ks, *vs;
+    Uint i;
+    Uint n;
+
+    mp = (map_t *)map_val(map);
+    ks = map_get_keys(mp);
+    vs = map_get_values(mp);
+    n  = map_get_size(mp);
+    if (is_immed(key)) {
+	for (i = 0; i < n; i++) {
+	    if (ks[i] == key) {
+		return vs[i];
+	    }
+	}
+    } else {
+	for (i = 0; i < n; i++) {
+	    if (EQ(ks[i], key)) {
+		return vs[i];
+	    }
+	}
+    }
+    return THE_NON_VALUE;
+}
+
+#define GET_TERM(term, dest)					\
+do {								\
+    Eterm src = (Eterm)(term);					\
+    switch (src & _TAG_IMMED1_MASK) {				\
+    case (R_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER:	\
+	dest = x(0);						\
+	break;							\
+    case (X_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER:	\
+	dest = x(src >> _TAG_IMMED1_SIZE);			\
+	break;							\
+    case (Y_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER:	\
+	dest = y(src >> _TAG_IMMED1_SIZE);			\
+	break;							\
+    default:							\
+	dest = src;						\
+	break;							\
+    }								\
+} while(0)
+
+
+static Eterm
+new_map(Process* p, Eterm* reg, BeamInstr* I)
+{
+    Uint n = Arg(3);
+    Uint i;
+    Uint need = n + 1 /* hdr */ + 1 /*size*/ + 1 /* ptr */ + 1 /* arity */;
+    Eterm keys;
+    Eterm *mhp,*thp;
+    Eterm *E;
+    BeamInstr *ptr;
+    map_t *mp;
+
+    if (HeapWordsLeft(p) < need) {
+	erts_garbage_collect(p, need, reg, Arg(2));
+    }
+
+    thp    = p->htop;
+    mhp    = thp + 1 + n/2;
+    E      = p->stop;
+    ptr    = &Arg(4);
+    keys   = make_tuple(thp);
+    *thp++ = make_arityval(n/2);
+
+    mp = (map_t *)mhp; mhp += MAP_HEADER_SIZE;
+    mp->thing_word = MAP_HEADER;
+    mp->size = n/2;
+    mp->keys = keys;
+
+    for (i = 0; i < n/2; i++) {
+	GET_TERM(*ptr++, *thp++);
+	GET_TERM(*ptr++, *mhp++);
+    }
+    p->htop = mhp;
+    return make_map(mp);
+}
+
+static Eterm
+update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
+{
+    Uint n;
+    Uint num_old;
+    Uint num_updates;
+    Uint need;
+    map_t *old_mp, *mp;
+    Eterm res;
+    Eterm* hp;
+    Eterm* E;
+    Eterm* old_keys;
+    Eterm* old_vals;
+    BeamInstr* new_p;
+    Eterm new_key;
+    Eterm* kp;
+
+    if (is_not_map(map)) {
+	return THE_NON_VALUE;
+    }
+
+    old_mp = (map_t *) map_val(map);
+    num_old = map_get_size(old_mp);
+
+    /*
+     * If the old map is empty, create a new map.
+     */
+
+    if (num_old == 0) {
+	return new_map(p, reg, I+1);
+    }
+
+    /*
+     * Allocate heap space for the worst case (i.e. all keys in the
+     * update list are new).
+     */
+
+    num_updates = Arg(4) / 2;
+    need = 2*(num_old+num_updates) + 1 + MAP_HEADER_SIZE;
+    if (HeapWordsLeft(p) < need) {
+	Uint live = Arg(3);
+	reg[live] = map;
+	erts_garbage_collect(p, need, reg, live+1);
+	map      = reg[live];
+	old_mp   = (map_t *)map_val(map);
+    }
+
+    /*
+     * Build the skeleton for the map, ready to be filled in.
+     *
+     * +-----------------------------------+
+     * | (Space for aritvyal for keys)     | <-----------+
+     * +-----------------------------------+		 |
+     * | (Space for key 1)		   |		 |    <-- kp
+     * +-----------------------------------+		 |
+     *        .				    		 |
+     *        .				    		 |
+     *        .				    		 |
+     * +-----------------------------------+		 |
+     * | (Space for last key)		   |		 |
+     * +-----------------------------------+		 |
+     * | MAP_HEADER			   |		 |
+     * +-----------------------------------+		 |
+     * | (Space for number of keys/values) |		 |
+     * +-----------------------------------+		 |
+     * | Boxed tuple pointer            >----------------+
+     * +-----------------------------------+
+     * | (Space for value 1)		   |                  <-- hp
+     * +-----------------------------------+
+     */
+
+    E = p->stop;
+    kp = p->htop + 1;		/* Point to first key */
+    hp = kp + num_old + num_updates;
+
+    res = make_map(hp);
+    mp = (map_t *)hp;
+    hp += MAP_HEADER_SIZE;
+    mp->thing_word = MAP_HEADER;
+    mp->keys = make_tuple(kp-1);
+
+    old_vals = map_get_values(old_mp);
+    old_keys = map_get_keys(old_mp);
+
+    new_p = &Arg(5);
+    GET_TERM(*new_p, new_key);
+    n = num_updates;
+
+    /*
+     * Fill in keys and values, until we run out of either updates
+     * or old values and keys.
+     */
+
+    for (;;) {
+	Eterm key;
+	Sint c;
+
+	ASSERT(kp < (Eterm *)mp);
+	key = *old_keys;
+	if ((c = CMP_TERM(key, new_key)) < 0) {
+	    /* Copy old key and value */
+	    *kp++ = key;
+	    *hp++ = *old_vals;
+	    old_keys++, old_vals++, num_old--;
+	} else {		/* Replace or insert new */
+	    GET_TERM(new_p[1], *hp++);
+	    if (c > 0) {	/* If new new key */
+		*kp++ = new_key;
+	    } else {		/* If replacement */
+		*kp++ = key;
+		old_keys++, old_vals++, num_old--;
+	    }
+	    n--;
+	    if (n == 0) {
+		break;
+	    } else {
+		new_p += 2;
+		GET_TERM(*new_p, new_key);
+	    }
+	}
+	if (num_old == 0) {
+	    break;
+	}
+    }
+
+    /*
+     * At this point, we have run out of either old keys and values,
+     * or the update list. In other words, at least of one n and
+     * num_old must be zero.
+     */
+
+    if (n > 0) {
+	/*
+	 * All old keys and values have been copied, but there
+	 * are still new keys and values in the update list that
+	 * must be copied.
+	 */
+	ASSERT(num_old == 0);
+	while (n-- > 0) {
+	    GET_TERM(new_p[0], *kp++);
+	    GET_TERM(new_p[1], *hp++);
+	    new_p += 2;
+	}
+    } else {
+	/*
+	 * All updates are now done. We may still have old
+	 * keys and values that we must copy.
+	 */
+	ASSERT(n == 0);
+	while (num_old-- > 0) {
+	    ASSERT(kp < (Eterm *)mp);
+	    *kp++ = *old_keys++;
+	    *hp++ = *old_vals++;
+	}
+    }
+
+    /*
+     * Calculate how many values that are unused at the end of the
+     * key tuple and fill it out with a bignum header.
+     */
+    if ((n = (Eterm *)mp - kp) > 0) {
+	*kp = make_pos_bignum_header(n-1);
+    }
+
+    /*
+     * Fill in the size of the map in both the key tuple and in the map.
+     */
+
+    n = kp - p->htop - 1;	/* Actual number of keys/values */
+    *p->htop = make_arityval(n);
+    mp->size = n;
+    p->htop = hp;
+    return res;
+}
+
+/*
+ * Update values for keys that already exist in the map.
+ */
+
+static Eterm
+update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
+{
+    Uint n;
+    Uint i;
+    Uint num_old;
+    Uint need;
+    map_t *old_mp, *mp;
+    Eterm res;
+    Eterm* hp;
+    Eterm* E;
+    Eterm* old_keys;
+    Eterm* old_vals;
+    BeamInstr* new_p;
+    Eterm new_key;
+
+    if (is_not_map(map)) {
+	return THE_NON_VALUE;
+    }
+
+    old_mp = (map_t *) map_val(map);
+    num_old = map_get_size(old_mp);
+
+    /*
+     * If the old map is empty, create a new map.
+     */
+
+    if (num_old == 0) {
+	return new_map(p, reg, I+1);
+    }
+
+    /*
+     * Allocate the exact heap space needed.
+     */
+
+    need = num_old + MAP_HEADER_SIZE;
+    if (HeapWordsLeft(p) < need) {
+	Uint live = Arg(3);
+	reg[live] = map;
+	erts_garbage_collect(p, need, reg, live+1);
+	map      = reg[live];
+	old_mp   = (map_t *)map_val(map);
+    }
+
+    /*
+     * Update map, keeping the old key tuple.
+     */
+
+    hp = p->htop;
+    E = p->stop;
+
+    old_vals = map_get_values(old_mp);
+    old_keys = map_get_keys(old_mp);
+
+    res = make_map(hp);
+    mp = (map_t *)hp;
+    hp += MAP_HEADER_SIZE;
+    mp->thing_word = MAP_HEADER;
+    mp->size = num_old;
+    mp->keys = old_mp->keys;
+
+    /* Get array of key/value pairs to be updated */
+    new_p = &Arg(5);
+    GET_TERM(*new_p, new_key);
+
+    /* Update all values */
+    n = Arg(4) / 2;		/* Number of values to be updated */
+    ASSERT(n > 0);
+    for (i = 0; i < num_old; i++) {
+	if (!EQ(*old_keys, new_key)) {
+	    /* Not same keys */
+	    *hp++ = *old_vals;
+	} else {
+	    GET_TERM(new_p[1], *hp);
+	    hp++;
+	    n--;
+	    if (n == 0) {
+		/*
+		 * All updates done. Copy remaining values
+		 * and return the result.
+		 */
+		for (i++, old_vals++; i < num_old; i++) {
+		    *hp++ = *old_vals++;
+		}
+		ASSERT(hp == p->htop + need);
+		p->htop = hp;
+		return res;
+	    } else {
+		new_p += 2;
+		GET_TERM(*new_p, new_key);
+	    }
+	}
+	old_vals++, old_keys++;
+    }
+
+    /*
+     * Updates left. That means that at least one the keys in the
+     * update list did not previously exist.
+     */
+    ASSERT(hp == p->htop + need);
+    return THE_NON_VALUE;
+}
+#undef GET_TERM
 
 int catchlevel(Process *p)
 {
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 938fd8f2c9..b589d1c930 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -3783,6 +3783,8 @@ gen_guard_bif1(LoaderState* stp, GenOpArg Fail, GenOpArg Live, GenOpArg Bif,
 	op->a[1].val = (BeamInstr) (void *) erts_gc_bit_size_1;
     } else if (bf == byte_size_1) {
 	op->a[1].val = (BeamInstr) (void *) erts_gc_byte_size_1;
+    } else if (bf == map_size_1) {
+	op->a[1].val = (BeamInstr) (void *) erts_gc_map_size_1;
     } else if (bf == abs_1) {
 	op->a[1].val = (BeamInstr) (void *) erts_gc_abs_1;
     } else if (bf == float_1) {
@@ -4376,6 +4378,7 @@ transform_engine(LoaderState* st)
     Uint* restart;		/* Where to restart if current match fails. */
     GenOpArg def_vars[TE_MAX_VARS]; /* Default buffer for variables. */
     GenOpArg* var = def_vars;
+    int num_vars = 0;
     int i;			/* General index. */
     Uint mask;
     GenOp* instr;
@@ -4578,9 +4581,9 @@ transform_engine(LoaderState* st)
 	    {
 		int n = *pc++;
 		int formal_arity = gen_opc[instr->op].arity;
-		int num_vars = n + (instr->arity - formal_arity);
 		int j = formal_arity;
 
+		num_vars = n + (instr->arity - formal_arity);
 		var = erts_alloc(ERTS_ALC_T_LOADER_TMP,
 				 num_vars * sizeof(GenOpArg));
 		for (i = 0; i < n; i++) {
@@ -4592,7 +4595,6 @@ transform_engine(LoaderState* st)
 	    }
 	    break;
 #endif
-
 	case TOP_next_arg:
 	    ap++;
 	    break;
@@ -4680,6 +4682,20 @@ transform_engine(LoaderState* st)
 	    instr->a[ap].val = var[i].val;
 	    ap++;
 	    break;
+#if defined(TOP_store_rest_args)
+	case TOP_store_rest_args:
+	    {
+		int n = *pc++;
+		int num_extra = num_vars - n;
+
+		ASSERT(n <= num_vars);
+		GENOP_ARITY(instr, instr->arity+num_extra);
+		memcpy(instr->a, instr->def_args, ap*sizeof(GenOpArg));
+		memcpy(instr->a+ap, var+n, num_extra*sizeof(GenOpArg));
+		ap += num_extra;
+	    }
+	    break;
+#endif
 	case TOP_try_me_else:
 	    restart = pc + 1;
 	    restart += *pc++;
diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c
index 61c1abedb5..9c4801041f 100644
--- a/erts/emulator/beam/bif.c
+++ b/erts/emulator/beam/bif.c
@@ -4615,6 +4615,17 @@ BIF_RETTYPE bump_reductions_1(BIF_ALIST_1)
     BIF_RET2(am_true, reds);
 }
 
+BIF_RETTYPE erts_internal_cmp_term_2(BIF_ALIST_2) {
+    int res = CMP_TERM(BIF_ARG_1,BIF_ARG_2);
+
+    /* ensure -1, 0, 1 result */
+    if (res < 0) {
+	BIF_RET(make_small(-1));
+    } else if (res > 0) {
+	BIF_RET(make_small(1));
+    }
+    BIF_RET(make_small(0));
+}
 /*
  * Processes doing yield on return in a bif ends up in bif_return_trap().
  */
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 3ec534f0bc..2d888862bf 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -578,6 +578,23 @@ bif os:unsetenv/1
 
 bif re:inspect/2
 
+ubif erlang:is_map/1
+ubif erlang:map_size/1
+bif maps:to_list/1
+bif maps:find/2
+bif maps:get/2
+bif maps:from_list/1
+bif maps:is_key/2
+bif maps:keys/1
+bif maps:merge/2
+bif maps:new/0
+bif maps:put/3
+bif maps:remove/2
+bif maps:update/3
+bif maps:values/1
+
+bif erts_internal:cmp_term/2
+
 #
 # Obsolete
 #
diff --git a/erts/emulator/beam/copy.c b/erts/emulator/beam/copy.c
index 23c0fca6aa..3a987e213b 100644
--- a/erts/emulator/beam/copy.c
+++ b/erts/emulator/beam/copy.c
@@ -27,6 +27,7 @@
 #include "erl_process.h"
 #include "erl_gc.h"
 #include "big.h"
+#include "erl_map.h"
 #include "erl_binary.h"
 #include "erl_bits.h"
 #include "dtrace-wrapper.h"
@@ -150,6 +151,24 @@ Uint size_object(Eterm obj)
 			goto pop_next;
 		    }
 		    break;
+		case MAP_SUBTAG:
+		    {
+			Uint n;
+			map_t *mp;
+			mp  = (map_t*)map_val_rel(obj,base);
+			ptr = (Eterm *)mp;
+			n   = map_get_size(mp) + 1;
+			sum += n + 2;
+			ptr += 2; /* hdr + size words */
+			while (n--) {
+			    obj = *ptr++;
+			    if (!IS_CONST(obj)) {
+				ESTACK_PUSH(s, obj);
+			    }
+			}
+			goto pop_next;
+		    }
+		    break;
 		case BIN_MATCHSTATE_SUBTAG:
 		    erl_exit(ERTS_ABORT_EXIT,
 			     "size_object: matchstate term not allowed");
@@ -318,6 +337,15 @@ Eterm copy_struct(Eterm obj, Uint sz, Eterm** hpp, ErlOffHeap* off_heap)
 		    }
 		}
 		break;
+	    case MAP_SUBTAG:
+		{
+		    i = map_get_size(objp) + 3;
+		    *argp = make_map_rel(htop, dst_base);
+		    while (i--) {
+			*htop++ = *objp++;
+		    }
+		}
+		break;
 	    case REFC_BINARY_SUBTAG:
 		{
 		    ProcBin* pb;
@@ -537,6 +565,10 @@ Eterm copy_shallow(Eterm* ptr, Uint sz, Eterm** hpp, ErlOffHeap* off_heap)
 		}
 		goto off_heap_common;
 
+	    case MAP_SUBTAG:
+		*hp++ = *tp++;
+		sz--;
+		break;
 	    case EXTERNAL_PID_SUBTAG:
 	    case EXTERNAL_PORT_SUBTAG:
 	    case EXTERNAL_REF_SUBTAG:
diff --git a/erts/emulator/beam/erl_bif_guard.c b/erts/emulator/beam/erl_bif_guard.c
index a715756c15..bbd8aa31d9 100644
--- a/erts/emulator/beam/erl_bif_guard.c
+++ b/erts/emulator/beam/erl_bif_guard.c
@@ -33,6 +33,7 @@
 #include "bif.h"
 #include "big.h"
 #include "erl_binary.h"
+#include "erl_map.h"
 
 static Eterm gc_double_to_integer(Process* p, double x, Eterm* reg, Uint live);
 
@@ -455,6 +456,28 @@ Eterm erts_gc_byte_size_1(Process* p, Eterm* reg, Uint live)
     }
 }
 
+Eterm erts_gc_map_size_1(Process* p, Eterm* reg, Uint live)
+{
+    Eterm arg = reg[live];
+    if (is_map(arg)) {
+	map_t *mp = (map_t*)map_val(arg);
+	Uint size = map_get_size(mp);
+	if (IS_USMALL(0, size)) {
+	    return make_small(size);
+	} else {
+	    Eterm* hp;
+	    if (ERTS_NEED_GC(p, BIG_UINT_HEAP_SIZE)) {
+		erts_garbage_collect(p, BIG_UINT_HEAP_SIZE, reg, live);
+	    }
+	    hp = p->htop;
+	    p->htop += BIG_UINT_HEAP_SIZE;
+	    return uint_to_big(size, hp);
+	}
+    } else {
+	BIF_ERROR(p, BADARG);
+    }
+}
+
 Eterm erts_gc_abs_1(Process* p, Eterm* reg, Uint live)
 {
     Eterm arg;
diff --git a/erts/emulator/beam/erl_bif_op.c b/erts/emulator/beam/erl_bif_op.c
index adac0052d6..37dd6457db 100644
--- a/erts/emulator/beam/erl_bif_op.c
+++ b/erts/emulator/beam/erl_bif_op.c
@@ -36,6 +36,7 @@
 #include "dist.h"
 #include "erl_version.h"
 #include "erl_binary.h"
+#include "erl_map.h"
 
 BIF_RETTYPE and_2(BIF_ALIST_2)
 {
@@ -321,7 +322,10 @@ BIF_RETTYPE is_record_3(BIF_ALIST_3)
     BIF_RET(am_false);
 }
 	
-
-    
-
-
+BIF_RETTYPE is_map_1(BIF_ALIST_1)
+{
+    if (is_map(BIF_ARG_1)) {
+	BIF_RET(am_true);
+    }
+    BIF_RET(am_false);
+}
diff --git a/erts/emulator/beam/erl_db_util.c b/erts/emulator/beam/erl_db_util.c
index a358ecf326..3986ccd4d3 100644
--- a/erts/emulator/beam/erl_db_util.c
+++ b/erts/emulator/beam/erl_db_util.c
@@ -35,6 +35,7 @@
 #include "bif.h"
 #include "big.h"
 #include "erl_binary.h"
+#include "erl_map.h"
 #include "erl_thr_progress.h"
 
 #include "erl_db_util.h"
@@ -565,6 +566,12 @@ static DMCGuardBif guard_tab[] =
 	DBIF_ALL
     },
     {
+	am_is_map,
+	&is_map_1,
+	1,
+	DBIF_ALL
+    },
+    {
 	am_is_binary,
 	&is_binary_1,
 	1,
@@ -631,6 +638,12 @@ static DMCGuardBif guard_tab[] =
 	DBIF_ALL
     },
     {
+	am_map_size,
+	&map_size_1,
+	1,
+	DBIF_ALL
+    },
+    {
 	am_bit_size,
 	&bit_size_1,
 	1,
diff --git a/erts/emulator/beam/erl_debug.c b/erts/emulator/beam/erl_debug.c
index 873a9860da..50bdc79506 100644
--- a/erts/emulator/beam/erl_debug.c
+++ b/erts/emulator/beam/erl_debug.c
@@ -29,6 +29,7 @@
 #include "bif.h"
 #include "beam_catches.h"
 #include "erl_debug.h"
+#include "erl_map.h"
 
 #define WITHIN(ptr, x, y) ((x) <= (ptr) && (ptr) < (y))
 
diff --git a/erts/emulator/beam/erl_driver.h b/erts/emulator/beam/erl_driver.h
index 2bd3181bdc..ab9ee63104 100644
--- a/erts/emulator/beam/erl_driver.h
+++ b/erts/emulator/beam/erl_driver.h
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 1999-2013. All Rights Reserved.
+ * Copyright Ericsson AB 1999-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -605,6 +605,8 @@ EXTERN int null_func(void);
 #define ERL_DRV_INT64       ((ErlDrvTermData) 15) /* ErlDrvSInt64 * */
 #define ERL_DRV_UINT64      ((ErlDrvTermData) 16) /* ErlDrvUInt64 * */
 
+#define ERL_DRV_MAP         ((ErlDrvTermData) 17) /* ErlDrvUInt */
+
 #ifndef ERL_DRIVER_TYPES_ONLY
 
 /* make terms for driver_output_term and driver_send_term */
diff --git a/erts/emulator/beam/erl_gc.c b/erts/emulator/beam/erl_gc.c
index ab8448e8a1..2022f70cbb 100644
--- a/erts/emulator/beam/erl_gc.c
+++ b/erts/emulator/beam/erl_gc.c
@@ -28,6 +28,7 @@
 #include "beam_catches.h"
 #include "erl_binary.h"
 #include "erl_bits.h"
+#include "erl_map.h"
 #include "error.h"
 #include "big.h"
 #include "erl_gc.h"
diff --git a/erts/emulator/beam/erl_gc.h b/erts/emulator/beam/erl_gc.h
index 1801df359a..5203dda263 100644
--- a/erts/emulator/beam/erl_gc.h
+++ b/erts/emulator/beam/erl_gc.h
@@ -20,6 +20,8 @@
 #ifndef __ERL_GC_H__
 #define __ERL_GC_H__
 
+#include "erl_map.h"
+
 /* GC declarations shared by beam/erl_gc.c and hipe/hipe_gc.c */
 
 #if defined(DEBUG) && !ERTS_GLB_INLINE_INCL_FUNC_DEF
@@ -42,23 +44,24 @@ do {									\
     HTOP += 2;			/* update tospace htop */		\
 } while(0)
 
-#define MOVE_BOXED(PTR,HDR,HTOP,ORIG)					\
-do {									\
-    Eterm gval;								\
-    Sint nelts;								\
-									\
-    ASSERT(is_header(HDR));						\
-    gval = make_boxed(HTOP);						\
-    *ORIG = gval;							\
-    *HTOP++ = HDR;							\
-    *PTR++ = gval;							\
-    nelts = header_arity(HDR);						\
-    switch ((HDR) & _HEADER_SUBTAG_MASK) {				\
-    case SUB_BINARY_SUBTAG: nelts++; break;				\
-    case FUN_SUBTAG: nelts+=((ErlFunThing*)(PTR-1))->num_free+1; break;	\
-    }									\
-    while (nelts--)							\
-	*HTOP++ = *PTR++;						\
+#define MOVE_BOXED(PTR,HDR,HTOP,ORIG)                                   \
+do {                                                                    \
+    Eterm gval;                                                         \
+    Sint nelts;                                                         \
+                                                                        \
+    ASSERT(is_header(HDR));                                             \
+    nelts = header_arity(HDR);                                          \
+    switch ((HDR) & _HEADER_SUBTAG_MASK) {                              \
+    case SUB_BINARY_SUBTAG: nelts++; break;                             \
+    case MAP_SUBTAG: nelts+=map_get_size(PTR) + 1; break;               \
+    case FUN_SUBTAG: nelts+=((ErlFunThing*)(PTR))->num_free+1; break;   \
+    }                                                                   \
+    gval    = make_boxed(HTOP);                                         \
+    *ORIG   = gval;                                                     \
+    *HTOP++ = HDR;                                                      \
+    *PTR++  = gval;                                                     \
+    while (nelts--) *HTOP++ = *PTR++;                                   \
+                                                                        \
 } while(0)
 
 #define in_area(ptr,start,nbytes) \
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
new file mode 100644
index 0000000000..2fff7f9390
--- /dev/null
+++ b/erts/emulator/beam/erl_map.c
@@ -0,0 +1,819 @@
+/*
+ * %CopyrightBegin%
+ *
+ * Copyright Ericsson AB 2014. All Rights Reserved.
+ *
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * %CopyrightEnd%
+ *
+ * Author: Björn-Egil Dahlberg
+ */
+
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif
+
+#include "sys.h"
+#include "erl_vm.h"
+#include "global.h"
+#include "erl_process.h"
+#include "error.h"
+#include "bif.h"
+
+#include "erl_map.h"
+
+/* BIFs
+ *
+ * DONE:
+ * - erlang:is_map/1
+ * - erlang:map_size/1
+ *
+ * - maps:find/2
+ * - maps:from_list/1
+ * - maps:get/2
+ * - maps:is_key/2
+ * - maps:keys/1
+ * - maps:merge/2
+ * - maps:new/0
+ * - maps:put/3
+ * - maps:remove/2
+ * - maps:to_list/1
+ * - maps:update/3
+ * - maps:values/1
+ *
+ * TODO:
+ * - maps:foldl/3
+ * - maps:foldr/3
+ * - maps:map/3
+ * - maps:size/1
+ * - maps:without/2
+ *
+ */
+
+/* erlang:map_size/1
+ * the corresponding instruction is implemented in:
+ *     beam/erl_bif_guard.c
+ */
+
+BIF_RETTYPE map_size_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Eterm *hp;
+	Uint hsz  = 0;
+	map_t *mp = (map_t*)map_val(BIF_ARG_1);
+	Uint n    = map_get_size(mp);
+
+	erts_bld_uint(NULL, &hsz, n);
+	hp = HAlloc(BIF_P, hsz);
+	BIF_RET(erts_bld_uint(&hp, NULL, n));
+    }
+
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:to_list/1
+ */
+
+BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Uint n;
+	Eterm* hp;
+	Eterm *ks,*vs, res, tup;
+	map_t *mp = (map_t*)map_val(BIF_ARG_1);
+
+	ks  = map_get_keys(mp);
+	vs  = map_get_values(mp);
+	n   = map_get_size(mp);
+	hp  = HAlloc(BIF_P, (2 + 3) * n);
+	res = NIL;
+
+	while(n--) {
+	    tup = TUPLE2(hp, ks[n], vs[n]); hp += 3;
+	    res = CONS(hp, tup, res); hp += 2;
+	}
+
+	BIF_RET(res);
+    }
+
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:find/2
+ * return value if key *matches* a key in the map
+ */
+
+int erts_maps_find(Eterm key, Eterm map, Eterm *value) {
+
+    Eterm *ks,*vs;
+    map_t *mp;
+    Uint n,i;
+
+    mp  = (map_t*)map_val(map);
+    n   = map_get_size(mp);
+    ks  = map_get_keys(mp);
+    vs  = map_get_values(mp);
+
+    for( i = 0; i < n; i++) {
+	if (EQ(ks[i], key)) {
+	    *value = vs[i];
+	    return 1;
+	}
+    }
+    return 0;
+}
+
+BIF_RETTYPE maps_find_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Eterm *hp, value,res;
+
+	if (erts_maps_find(BIF_ARG_1, BIF_ARG_2, &value)) {
+	    hp    = HAlloc(BIF_P, 3);
+	    res   = make_tuple(hp);
+	    *hp++ = make_arityval(2);
+	    *hp++ = am_ok;
+	    *hp++ = value;
+	    BIF_RET(res);
+	}
+
+	BIF_RET(am_error);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+/* maps:get/2
+ * return value if key *matches* a key in the map
+ * exception bad_key if none matches
+ */
+
+
+int erts_maps_get(Eterm key, Eterm map, Eterm *value) {
+    Eterm *ks,*vs;
+    map_t *mp;
+    Uint n,i;
+
+    mp  = (map_t*)map_val(map);
+    n   = map_get_size(mp);
+
+    if (n == 0)
+	return 0;
+
+    ks  = map_get_keys(mp);
+    vs  = map_get_values(mp);
+
+    if (is_immed(key)) {
+	for( i = 0; i < n; i++) {
+	    if (ks[i] == key) {
+		*value = vs[i];
+		return 1;
+	    }
+	}
+    }
+
+    for( i = 0; i < n; i++) {
+	if (EQ(ks[i], key)) {
+	    *value = vs[i];
+	    return 1;
+	}
+    }
+    return 0;
+}
+
+BIF_RETTYPE maps_get_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Eterm *hp;
+	Eterm value, error;
+	char *s_error;
+
+	if (erts_maps_get(BIF_ARG_1, BIF_ARG_2, &value)) {
+	    BIF_RET(value);
+	}
+
+	s_error = "bad_key";
+	error = am_atom_put(s_error, sys_strlen(s_error));
+
+	hp = HAlloc(BIF_P, 3);
+	BIF_P->fvalue = TUPLE2(hp, error, BIF_ARG_1);
+	BIF_ERROR(BIF_P, EXC_ERROR_2);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:from_list/1
+ * List may be unsorted [{K,V}]
+ */
+
+BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) {
+    Eterm *kv, item = BIF_ARG_1;
+    Eterm *hp, *thp,*vs, *ks, keys, res;
+    map_t *mp;
+    Uint  size = 0, unused_size = 0;
+    Sint  c = 0;
+    Sint  idx = 0;
+
+    if (is_list(item) || is_nil(item)) {
+
+	/* Calculate size and check validity */
+
+	while(is_list(item)) {
+	    res = CAR(list_val(item));
+	    if (is_not_tuple(res))
+		goto error;
+
+	    kv = tuple_val(res);
+	    if (*kv != make_arityval(2))
+		goto error;
+
+	    size++;
+	    item = CDR(list_val(item));
+	}
+
+	if (is_not_nil(item))
+	    goto error;
+
+	hp    = HAlloc(BIF_P, 3 + 1 + (2 * size));
+	thp   = hp;
+	keys  = make_tuple(hp);
+	*hp++ = make_arityval(size);
+	ks    = hp;
+	hp   += size;
+	mp    = (map_t*)hp;
+	res   = make_map(mp);
+	hp   += MAP_HEADER_SIZE;
+	vs    = hp;
+
+	mp->thing_word = MAP_HEADER;
+	mp->size = size; /* set later, might shrink*/
+	mp->keys = keys;
+
+	if (size == 0)
+	    BIF_RET(res);
+
+	item  = BIF_ARG_1;
+
+	/* first entry */
+	kv    = tuple_val(CAR(list_val(item)));
+	ks[0] = kv[1];
+	vs[0] = kv[2];
+	size  = 1;
+	item  = CDR(list_val(item));
+
+	/* insert sort key/value pairs */
+	while(is_list(item)) {
+
+	    kv = tuple_val(CAR(list_val(item)));
+
+	    /* compare ks backwards
+	     * idx represent word index to be written (hole position).
+	     * We cannot copy the elements when searching since we might
+	     * have an equal key. So we search for just the index first =(
+	     *
+	     * It is perhaps faster to move the values in the first pass.
+	     * Check for uniqueness during insert phase and then have a
+	     * second phace compacting the map if duplicates are found
+	     * during insert. .. or do someother sort .. shell-sort perhaps.
+	     */
+
+	    idx = size;
+
+	    while(idx > 0 && (c = CMP_TERM(kv[1],ks[idx-1])) < 0) { idx--; }
+
+	    if (c == 0) {
+		/* last compare was equal,
+		 * i.e. we have to release memory
+		 * and overwrite that key/value
+		 */
+		ks[idx-1] = kv[1];
+		vs[idx-1] = kv[2];
+		unused_size++;
+	    } else {
+		Uint i = size;
+		while(i > idx) {
+		    ks[i] = ks[i-1];
+		    vs[i] = vs[i-1];
+		    i--;
+		}
+		ks[idx] = kv[1];
+		vs[idx] = kv[2];
+		size++;
+	    }
+	    item = CDR(list_val(item));
+	}
+
+	if (unused_size) {
+	    /* the key tuple is embedded in the heap
+	     * write a bignum to clear it.
+	     */
+	    /* release values as normal since they are on the top of the heap */
+
+	    ks[size] = make_pos_bignum_header(unused_size - 1);
+	    HRelease(BIF_P, vs + size + unused_size, vs + size);
+	}
+
+	*thp = make_arityval(size);
+	mp->size = size;
+	BIF_RET(res);
+    }
+
+error:
+
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:is_key/2
+ */
+
+BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Eterm *ks, key;
+	map_t *mp;
+	Uint n,i;
+
+	mp  = (map_t*)map_val(BIF_ARG_2);
+	key = BIF_ARG_1;
+	n   = map_get_size(mp);
+	ks  = map_get_keys(mp);
+
+	if (n == 0)
+	    BIF_RET(am_false);
+
+	if (is_immed(key)) {
+	    for( i = 0; i < n; i++) {
+		if (ks[i] == key) {
+		    BIF_RET(am_true);
+		}
+	    }
+	}
+
+	for( i = 0; i < n; i++) {
+	    if (EQ(ks[i], key)) {
+		BIF_RET(am_true);
+	    }
+	}
+	BIF_RET(am_false);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:keys/1
+ */
+
+BIF_RETTYPE maps_keys_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Eterm *hp, *ks, res = NIL;
+	map_t *mp;
+	Uint n;
+
+	mp  = (map_t*)map_val(BIF_ARG_1);
+	n   = map_get_size(mp);
+
+	if (n == 0)
+	    BIF_RET(res);
+
+	hp  = HAlloc(BIF_P, (2 * n));
+	ks  = map_get_keys(mp);
+
+	while(n--) {
+	    res = CONS(hp, ks[n], res); hp += 2;
+	}
+
+	BIF_RET(res);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+/* maps:merge/2
+ */
+
+BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_1) && is_map(BIF_ARG_2)) {
+	Eterm *hp,*thp;
+	Eterm tup;
+	Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2;
+	map_t *mp1,*mp2,*mp_new;
+	Uint n1,n2,i1,i2,need,unused_size=0;
+	int c = 0;
+
+	mp1  = (map_t*)map_val(BIF_ARG_1);
+	mp2  = (map_t*)map_val(BIF_ARG_2);
+	n1   = map_get_size(mp1);
+	n2   = map_get_size(mp2);
+
+	need = MAP_HEADER_SIZE + 1 + 2*(n1 + n2);
+
+	hp     = HAlloc(BIF_P, need);
+	thp    = hp;
+	tup    = make_tuple(thp);
+	ks     = hp + 1; hp += 1 + n1 + n2;
+	mp_new = (map_t*)hp; hp += MAP_HEADER_SIZE;
+	vs     = hp; hp += n1 + n2;
+
+	mp_new->thing_word = MAP_HEADER;
+	mp_new->size = 0;
+	mp_new->keys = tup;
+
+	i1  = 0; i2 = 0;
+	ks1 = map_get_keys(mp1);
+	vs1 = map_get_values(mp1);
+	ks2 = map_get_keys(mp2);
+	vs2 = map_get_values(mp2);
+
+	while(i1 < n1 && i2 < n2) {
+	    c = CMP_TERM(ks1[i1],ks2[i2]);
+	    if ( c == 0) {
+		/* use righthand side arguments map value,
+		 * but advance both maps */
+		*ks++ = ks2[i2];
+		*vs++ = vs2[i2];
+		i1++, i2++, unused_size++;
+	    } else if ( c < 0) {
+		*ks++ = ks1[i1];
+		*vs++ = vs1[i1];
+		i1++;
+	    } else {
+		*ks++ = ks2[i2];
+		*vs++ = vs2[i2];
+		i2++;
+	    }
+	}
+
+	/* copy remaining */
+	while (i1 < n1) {
+	    *ks++ = ks1[i1];
+	    *vs++ = vs1[i1];
+	    i1++;
+	}
+
+	while (i2 < n2) {
+	    *ks++ = ks2[i2];
+	    *vs++ = vs2[i2];
+	    i2++;
+	}
+
+	if (unused_size) {
+	    /* the key tuple is embedded in the heap, write a bignum to clear it.
+	     *
+	     * release values as normal since they are on the top of the heap
+	     * size = n1 + n1 - unused_size
+	     */
+
+	    *ks = make_pos_bignum_header(unused_size - 1);
+	    HRelease(BIF_P, vs + unused_size, vs);
+	}
+
+	mp_new->size = n1 + n2 - unused_size;
+	*thp = make_arityval(n1 + n2 - unused_size);
+
+	BIF_RET(make_map(mp_new));
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+/* maps:new/2
+ */
+
+BIF_RETTYPE maps_new_0(BIF_ALIST_0) {
+    Eterm* hp;
+    Eterm tup;
+    map_t *mp;
+
+    hp    = HAlloc(BIF_P, (MAP_HEADER_SIZE + 1));
+    tup   = make_tuple(hp);
+    *hp++ = make_arityval(0);
+
+    mp    = (map_t*)hp;
+    mp->thing_word = MAP_HEADER;
+    mp->size = 0;
+    mp->keys = tup;
+
+    BIF_RET(make_map(mp));
+}
+
+/* maps:put/3
+ */
+
+Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
+    Sint n,i;
+    Sint c = 0;
+    Eterm* hp, *shp;
+    Eterm *ks,*vs, res, tup;
+    map_t *mp = (map_t*)map_val(map);
+
+    n = map_get_size(mp);
+
+    if (n == 0) {
+	hp    = HAlloc(p, MAP_HEADER_SIZE + 1 + 2);
+	tup   = make_tuple(hp);
+	*hp++ = make_arityval(1);
+	*hp++ = key;
+	res   = make_map(hp);
+	*hp++ = MAP_HEADER;
+	*hp++ = 1;
+	*hp++ = tup;
+	*hp++ = value;
+
+	return res;
+    }
+
+    ks  = map_get_keys(mp);
+    vs  = map_get_values(mp);
+
+    /* only allocate for values,
+     * assume key-tuple will be intact
+     */
+
+    hp  = HAlloc(p, MAP_HEADER_SIZE + n);
+    shp = hp; /* save hp, used if optimistic update fails */
+    res = make_map(hp);
+    *hp++ = MAP_HEADER;
+    *hp++ = n;
+    *hp++ = mp->keys;
+
+    if (is_immed(key)) {
+	for( i = 0; i < n; i ++) {
+	    if (ks[i] == key) {
+		*hp++ = value;
+		vs++;
+		c = 1;
+	    } else {
+		*hp++ = *vs++;
+	    }
+	}
+    } else {
+	for( i = 0; i < n; i ++) {
+	    if (EQ(ks[i], key)) {
+		*hp++ = value;
+		vs++;
+		c = 1;
+	    } else {
+		*hp++ = *vs++;
+	    }
+	}
+    }
+
+    if (c)
+	return res;
+
+    /* need to make a new tuple,
+     * use old hp since it needs to be recreated anyway.
+     */
+    tup    = make_tuple(shp);
+    *shp++ = make_arityval(n+1);
+
+    hp    = HAlloc(p, 3 + n + 1);
+    res   = make_map(hp);
+    *hp++ = MAP_HEADER;
+    *hp++ = n + 1;
+    *hp++ = tup;
+
+    ks  = map_get_keys(mp);
+    vs  = map_get_values(mp);
+
+    ASSERT(n >= 0);
+
+    /* copy map in order */
+    while (n && ((c = CMP_TERM(*ks, key)) < 0)) {
+	*shp++ = *ks++;
+	*hp++  = *vs++;
+	n--;
+    }
+
+    *shp++ = key;
+    *hp++  = value;
+
+    ASSERT(n >= 0);
+
+    while(n--) {
+	*shp++ = *ks++;
+	*hp++  = *vs++;
+    }
+    /* we have one word remaining
+     * this will work out fine once we get the size word
+     * in the header.
+     */
+    *shp = make_pos_bignum_header(0);
+    return res;
+}
+
+BIF_RETTYPE maps_put_3(BIF_ALIST_3) {
+    if (is_map(BIF_ARG_3)) {
+	BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3));
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:remove/3
+ */
+
+int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) {
+    Sint n;
+    Uint need;
+    Eterm *hp_start;
+    Eterm *thp, *mhp;
+    Eterm *ks, *vs, tup;
+    map_t *mp = (map_t*)map_val(map);
+
+    n = map_get_size(mp);
+
+    if (n == 0) {
+	*res = map;
+	return 1;
+    }
+
+    ks = map_get_keys(mp);
+    vs = map_get_values(mp);
+
+    /* Assume key exists.
+     * Release allocated if it didn't.
+     * Allocate key tuple first.
+     */
+
+    need   = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */
+    hp_start = HAlloc(p, need);
+    thp    = hp_start;
+    mhp    = thp + n;               /* offset with tuple heap size */
+
+    tup    = make_tuple(thp);
+    *thp++ = make_arityval(n - 1);
+
+    *res   = make_map(mhp);
+    *mhp++ = MAP_HEADER;
+    *mhp++ = n - 1;
+    *mhp++ = tup;
+
+    if (is_immed(key)) {
+	while(n--) {
+	    if (*ks == key) {
+		goto found_key;
+	    } else {
+		*mhp++ = *vs++;
+		*thp++ = *ks++;
+	    }
+	}
+    } else {
+	while(n--) {
+	    if (EQ(*ks, key)) {
+		goto found_key;
+	    } else {
+		*mhp++ = *vs++;
+		*thp++ = *ks++;
+	    }
+	}
+    }
+
+    /* Not found, remove allocated memory
+     * and return previous map.
+     */
+    HRelease(p, hp_start + need, hp_start);
+
+    *res = map;
+    return 1;
+
+found_key:
+    /* Copy rest of keys and values */
+    if (n) {
+	sys_memcpy(mhp, vs+1, n*sizeof(Eterm));
+	sys_memcpy(thp, ks+1, n*sizeof(Eterm));
+    }
+    return 1;
+}
+
+BIF_RETTYPE maps_remove_2(BIF_ALIST_2) {
+    if (is_map(BIF_ARG_2)) {
+	Eterm res;
+	if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) {
+	    BIF_RET(res);
+	}
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+/* maps:update/3
+ */
+
+int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) {
+	Sint n,i;
+	Eterm* hp,*shp;
+	Eterm *ks,*vs;
+	map_t *mp = (map_t*)map_val(map);
+
+	if ((n = map_get_size(mp)) == 0) {
+	    return 0;
+	}
+
+	ks  = map_get_keys(mp);
+	vs  = map_get_values(mp);
+
+	/* only allocate for values,
+	 * assume key-tuple will be intact
+	 */
+
+	hp  = HAlloc(p, MAP_HEADER_SIZE + n);
+	shp = hp;
+	*hp++ = MAP_HEADER;
+	*hp++ = n;
+	*hp++ = mp->keys;
+
+	if (is_immed(key)) {
+	    for( i = 0; i < n; i ++) {
+		if (ks[i] == key) {
+		    goto found_key;
+		} else {
+		    *hp++ = *vs++;
+		}
+	    }
+	} else {
+	    for( i = 0; i < n; i ++) {
+		if (EQ(ks[i], key)) {
+		    goto found_key;
+		} else {
+		    *hp++ = *vs++;
+		}
+	    }
+	}
+
+	HRelease(p, shp + MAP_HEADER_SIZE + n, shp);
+	return 0;
+
+found_key:
+	*hp++ = value;
+	vs++;
+	if (++i < n)
+	    sys_memcpy(hp, vs, (n - i)*sizeof(Eterm));
+	*res = make_map(shp);
+	return 1;
+}
+
+BIF_RETTYPE maps_update_3(BIF_ALIST_3) {
+    if (is_map(BIF_ARG_3)) {
+	Eterm res;
+	if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) {
+	    BIF_RET(res);
+	}
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+
+/* maps:values/1
+ */
+
+BIF_RETTYPE maps_values_1(BIF_ALIST_1) {
+    if (is_map(BIF_ARG_1)) {
+	Eterm *hp, *vs, res = NIL;
+	map_t *mp;
+	Uint n;
+
+	mp  = (map_t*)map_val(BIF_ARG_1);
+	n   = map_get_size(mp);
+
+	if (n == 0)
+	    BIF_RET(res);
+
+	hp  = HAlloc(BIF_P, (2 * n));
+	vs  = map_get_values(mp);
+
+	while(n--) {
+	    res = CONS(hp, vs[n], res); hp += 2;
+	}
+
+	BIF_RET(res);
+    }
+    BIF_ERROR(BIF_P, BADARG);
+}
+
+int erts_validate_and_sort_map(map_t* mp)
+{
+    Eterm *ks  = map_get_keys(mp);
+    Eterm *vs  = map_get_values(mp);
+    Uint   sz  = map_get_size(mp);
+    Uint   ix,jx;
+    Eterm  tmp;
+    int c;
+
+    /* sort */
+
+    for (ix = 1; ix < sz; ix++) {
+	jx = ix;
+	while( jx > 0 && (c = CMP_TERM(ks[jx],ks[jx-1])) <= 0 ) {
+	    /* identical key -> error */
+	    if (c == 0) return 0;
+
+	    tmp = ks[jx];
+	    ks[jx] = ks[jx - 1];
+	    ks[jx - 1] = tmp;
+
+	    tmp = vs[jx];
+	    vs[jx] = vs[jx - 1];
+	    vs[jx - 1] = tmp;
+
+	    jx--;
+	}
+    }
+    return 1;
+}
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
new file mode 100644
index 0000000000..cfacb2ec28
--- /dev/null
+++ b/erts/emulator/beam/erl_map.h
@@ -0,0 +1,72 @@
+/*
+ * %CopyrightBegin%
+ * 
+ * Copyright Ericsson AB 2014. All Rights Reserved.
+ * 
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ * 
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ * 
+ * %CopyrightEnd%
+ */
+
+
+#ifndef __ERL_MAP_H__
+#define __ERL_MAP_H__
+
+#include "sys.h"
+/* MAP */
+
+typedef struct map_s {
+    Eterm thing_word;
+    Uint  size;
+    Eterm keys;      /* tuple */
+} map_t;
+/* map node
+ *
+ * -----------
+ * Eterm   THING	
+ * Uint    size
+ * Eterm   Keys -> {K1, K2, K3, ..., Kn} where n = size
+ * ----
+ * Eterm   V1
+ * ...
+ * Eterm   Vn, where n = size
+ * -----------
+ */
+
+
+
+/* erl_term.h stuff */
+#define make_map(x)		make_boxed((Eterm*)(x))
+#define make_map_rel(x, BASE)   make_boxed_rel((Eterm*)(x),(BASE))
+#define is_map(x)		(is_boxed((x)) && is_map_header(*boxed_val((x))))
+#define is_map_rel(RTERM,BASE)  is_map(rterm2wterm(RTERM,BASE))
+#define is_not_map(x)           (!is_map((x)))
+#define is_map_header(x)	(((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_MAP)
+#define header_is_map(x)        ((((x) & (_HEADER_SUBTAG_MASK)) == MAP_SUBTAG))
+#define map_val(x)		(_unchecked_boxed_val((x)))
+#define map_val_rel(RTERM, BASE) map_val(rterm2wterm(RTERM, BASE))
+
+#define map_get_values(x)      (((Eterm *)(x)) + 3)
+#define map_get_keys(x)        (((Eterm *)tuple_val(((map_t *)(x))->keys)) + 1)
+#define map_get_size(x)        (((map_t*)(x))->size)
+
+#define MAP_HEADER             _make_header(1,_TAG_HEADER_MAP)
+#define MAP_HEADER_SIZE        (sizeof(map_t) / sizeof(Eterm))
+
+Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map);
+int   erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res);
+int   erts_maps_find(Eterm key, Eterm map, Eterm *value);
+int   erts_maps_get(Eterm key, Eterm map, Eterm *value);
+int   erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res);
+int   erts_validate_and_sort_map(map_t* map);
+#endif
+
diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c
index e1e213c4eb..c35f1fc2c6 100644
--- a/erts/emulator/beam/erl_nif.c
+++ b/erts/emulator/beam/erl_nif.c
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 2009-2013. All Rights Reserved.
+ * Copyright Ericsson AB 2009-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -31,6 +31,7 @@
 #include "bif.h"
 #include "error.h"
 #include "big.h"
+#include "erl_map.h"
 #include "beam_bp.h"
 #include "erl_thr_progress.h"
 #include "dtrace-wrapper.h"
@@ -1602,6 +1603,197 @@ enif_have_dirty_schedulers()
 
 #endif /* ERL_NIF_DIRTY_SCHEDULER_SUPPORT */
 
+/* Maps */
+
+int enif_is_map(ErlNifEnv* env, ERL_NIF_TERM term)
+{
+    return is_map(term);
+}
+
+int enif_get_map_size(ErlNifEnv* env, ERL_NIF_TERM term, size_t *size)
+{
+    if (is_map(term)) {
+	map_t *mp;
+	mp    = (map_t*)map_val(term);
+	*size = map_get_size(mp);
+	return 1;
+    }
+    return 0;
+}
+
+ERL_NIF_TERM enif_make_new_map(ErlNifEnv* env)
+{
+    Eterm* hp = alloc_heap(env,MAP_HEADER_SIZE+1);
+    Eterm tup;
+    map_t *mp;
+
+    tup   = make_tuple(hp);
+    *hp++ = make_arityval(0);
+    mp    = (map_t*)hp;
+    mp->thing_word = MAP_HEADER;
+    mp->size = 0;
+    mp->keys = tup;
+
+    return make_map(mp);
+}
+
+int enif_make_map_put(ErlNifEnv* env,
+	              Eterm map_in,
+		      Eterm key,
+		      Eterm value,
+		      Eterm *map_out)
+{
+    if (is_not_map(map_in)) {
+	return 0;
+    }
+    flush_env(env);
+    *map_out = erts_maps_put(env->proc, key, value, map_in);
+    cache_env(env);
+    return 1;
+}
+
+int enif_get_map_value(ErlNifEnv* env,
+	               Eterm map,
+		       Eterm key,
+		       Eterm *value)
+{
+    if (is_not_map(map)) {
+	return 0;
+    }
+    return erts_maps_get(key, map, value);
+}
+
+int enif_make_map_update(ErlNifEnv* env,
+	                 Eterm map_in,
+			 Eterm key,
+			 Eterm value,
+			 Eterm *map_out)
+{
+    int res;
+    if (is_not_map(map_in)) {
+	return 0;
+    }
+
+    flush_env(env);
+    res = erts_maps_update(env->proc, key, value, map_in, map_out);
+    cache_env(env);
+    return res;
+}
+
+int enif_make_map_remove(ErlNifEnv* env,
+	                 Eterm map_in,
+			 Eterm key,
+			 Eterm *map_out)
+{
+    int res;
+    if (is_not_map(map_in)) {
+	return 0;
+    }
+    flush_env(env);
+    res = erts_maps_remove(env->proc, key, map_in, map_out);
+    cache_env(env);
+    return res;
+}
+
+int enif_map_iterator_create(ErlNifEnv *env,
+	                     Eterm map,
+			     ErlNifMapIterator *iter,
+			     ErlNifMapIteratorEntry entry)
+{
+    if (is_map(map)) {
+	map_t *mp = (map_t*)map_val(map);
+	size_t offset;
+
+	switch (entry) {
+	    case ERL_NIF_MAP_ITERATOR_HEAD: offset = 0; break;
+	    case ERL_NIF_MAP_ITERATOR_TAIL: offset = map_get_size(mp) - 1; break;
+	    default: goto error;
+	}
+
+	/* empty maps are ok but will leave the iterator
+	 * in bad shape.
+	 */
+
+	iter->map     = map;
+	iter->ks      = ((Eterm *)map_get_keys(mp)) + offset;
+	iter->vs      = ((Eterm *)map_get_values(mp)) + offset;
+	iter->t_limit = map_get_size(mp) + 1;
+	iter->idx     = offset + 1;
+
+	return 1;
+    }
+
+error:
+#ifdef DEBUG
+    iter->map = THE_NON_VALUE;
+#endif
+    return 0;
+}
+
+void enif_map_iterator_destroy(ErlNifEnv *env, ErlNifMapIterator *iter)
+{
+    /* not used */
+#ifdef DEBUG
+    iter->map = THE_NON_VALUE;
+#endif
+
+}
+
+int enif_map_iterator_is_tail(ErlNifEnv *env, ErlNifMapIterator *iter)
+{
+    ASSERT(iter && is_map(iter->map));
+    ASSERT(iter->idx >= 0 && (iter->idx <= map_get_size(map_val(iter->map)) + 1));
+    return (iter->t_limit == 1 || iter->idx == iter->t_limit);
+}
+
+int enif_map_iterator_is_head(ErlNifEnv *env, ErlNifMapIterator *iter)
+{
+    ASSERT(iter && is_map(iter->map));
+    ASSERT(iter->idx >= 0 && (iter->idx <= map_get_size(map_val(iter->map)) + 1));
+    return (iter->t_limit == 1 || iter->idx == 0);
+}
+
+
+int enif_map_iterator_next(ErlNifEnv *env, ErlNifMapIterator *iter)
+{
+    ASSERT(iter && is_map(iter->map));
+    if (iter->idx < iter->t_limit) {
+	iter->idx++;
+	iter->ks++;
+	iter->vs++;
+    }
+    return (iter->idx != iter->t_limit);
+}
+
+int enif_map_iterator_prev(ErlNifEnv *env, ErlNifMapIterator *iter)
+{
+    ASSERT(iter && is_map(iter->map));
+    if (iter->idx > 0) {
+	iter->idx--;
+	iter->ks--;
+	iter->vs--;
+    }
+    return (iter->idx > 0);
+}
+
+int enif_map_iterator_get_pair(ErlNifEnv *env,
+			       ErlNifMapIterator *iter,
+			       Eterm *key,
+			       Eterm *value)
+{
+    ASSERT(iter && is_map(iter->map));
+    if (iter->idx > 0 && iter->idx < iter->t_limit) {
+	ASSERT(iter->ks >= map_get_keys(map_val(iter->map)) &&
+	       iter->ks  < (map_get_keys(map_val(iter->map)) + map_get_size(map_val(iter->map))));
+	ASSERT(iter->vs >= map_get_values(map_val(iter->map)) &&
+	       iter->vs  < (map_get_values(map_val(iter->map)) + map_get_size(map_val(iter->map))));
+	*key   = *(iter->ks);
+	*value = *(iter->vs);
+	return 1;
+    }
+    return 0;
+}
+
 /***************************************************************************
  **                              load_nif/2                               **
  ***************************************************************************/
@@ -1798,7 +1990,8 @@ BIF_RETTYPE load_nif_2(BIF_ALIST_2)
 	ret = load_nif_error(BIF_P, bad_lib, "Library init-call unsuccessful");
     }
     else if (entry->major != ERL_NIF_MAJOR_VERSION
-	     || entry->minor > ERL_NIF_MINOR_VERSION) {
+	     || entry->minor > ERL_NIF_MINOR_VERSION
+	     || (entry->major==2 && entry->minor == 5)) { /* experimental maps */
 	
 	ret = load_nif_error(BIF_P, bad_lib, "Library version (%d.%d) not compatible (with %d.%d).",
 			     entry->major, entry->minor, ERL_NIF_MAJOR_VERSION, ERL_NIF_MINOR_VERSION);
diff --git a/erts/emulator/beam/erl_nif.h b/erts/emulator/beam/erl_nif.h
index fb3c359ec9..7613446f64 100644
--- a/erts/emulator/beam/erl_nif.h
+++ b/erts/emulator/beam/erl_nif.h
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 2009-2013. All Rights Reserved.
+ * Copyright Ericsson AB 2009-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -38,14 +38,13 @@
 ** 2.2: R14B03 enif_is_exception
 ** 2.3: R15 enif_make_reverse_list, enif_is_number
 ** 2.4: R16 enif_consume_timeslice
-** 2.5: R17 dirty schedulers
+** 2.5: First experimental maps API additions (libs of this version is not compatible with any other VM)
+** 2.5: R17 Maps API additions
+** 2.6: R17 with maps
+**      R17 dirty schedulers
 */
 #define ERL_NIF_MAJOR_VERSION 2
-#ifdef ERL_NIF_DIRTY_SCHEDULER_SUPPORT
-#define ERL_NIF_MINOR_VERSION 5
-#else
-#define ERL_NIF_MINOR_VERSION 4
-#endif
+#define ERL_NIF_MINOR_VERSION 6
 
 #include <stdlib.h>
 
@@ -104,6 +103,8 @@ typedef unsigned long long ERL_NIF_TERM;
 #  endif
 #endif
 
+typedef ERL_NIF_TERM ERL_NIF_UINT;
+
 struct enif_environment_t;
 typedef struct enif_environment_t ErlNifEnv;
 
@@ -176,6 +177,21 @@ typedef enum
 }ErlNifDirtyTaskFlags;
 #endif
 
+typedef struct /* All fields all internal and may change */
+{
+    ERL_NIF_TERM map;
+    ERL_NIF_UINT t_limit;
+    ERL_NIF_UINT idx;
+    ERL_NIF_TERM *ks;
+    ERL_NIF_TERM *vs;
+    void* __spare__[2]; /* for future additions to be ABI compatible (same struct size) */
+} ErlNifMapIterator;
+
+typedef enum {
+    ERL_NIF_MAP_ITERATOR_HEAD = 1,
+    ERL_NIF_MAP_ITERATOR_TAIL = 2
+} ErlNifMapIteratorEntry;
+
 #if (defined(__WIN32__) || defined(_WIN32) || defined(_WIN32_))
 #  define ERL_NIF_API_FUNC_DECL(RET_TYPE, NAME, ARGS) RET_TYPE (*NAME) ARGS
 typedef struct {
diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h
index f5b27dfdfa..d7c554e60b 100644
--- a/erts/emulator/beam/erl_nif_api_funcs.h
+++ b/erts/emulator/beam/erl_nif_api_funcs.h
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 2009-2013. All Rights Reserved.
+ * Copyright Ericsson AB 2009-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -149,6 +149,22 @@ ERL_NIF_API_FUNC_DECL(int,enif_is_on_dirty_scheduler,(ErlNifEnv*));
 ERL_NIF_API_FUNC_DECL(int,enif_have_dirty_schedulers,(void));
 #endif
 
+ERL_NIF_API_FUNC_DECL(int, enif_is_map, (ErlNifEnv* env, ERL_NIF_TERM term));
+ERL_NIF_API_FUNC_DECL(int, enif_get_map_size, (ErlNifEnv* env, ERL_NIF_TERM term, size_t *size));
+ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM, enif_make_new_map, (ErlNifEnv* env));
+ERL_NIF_API_FUNC_DECL(int, enif_make_map_put, (ErlNifEnv* env, ERL_NIF_TERM map_in, ERL_NIF_TERM key, ERL_NIF_TERM value, ERL_NIF_TERM* map_out));
+ERL_NIF_API_FUNC_DECL(int, enif_get_map_value, (ErlNifEnv* env, ERL_NIF_TERM map, ERL_NIF_TERM key, ERL_NIF_TERM* value));
+ERL_NIF_API_FUNC_DECL(int, enif_make_map_update, (ErlNifEnv* env, ERL_NIF_TERM map_in, ERL_NIF_TERM key, ERL_NIF_TERM value, ERL_NIF_TERM* map_out));
+ERL_NIF_API_FUNC_DECL(int, enif_make_map_remove, (ErlNifEnv* env, ERL_NIF_TERM map_in, ERL_NIF_TERM key, ERL_NIF_TERM* map_out));
+ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_create, (ErlNifEnv *env, ERL_NIF_TERM map, ErlNifMapIterator *iter, ErlNifMapIteratorEntry entry));
+ERL_NIF_API_FUNC_DECL(void, enif_map_iterator_destroy, (ErlNifEnv *env, ErlNifMapIterator *iter));
+ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_is_head, (ErlNifEnv *env, ErlNifMapIterator *iter));
+ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_is_tail, (ErlNifEnv *env, ErlNifMapIterator *iter));
+ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_next, (ErlNifEnv *env, ErlNifMapIterator *iter));
+ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_prev, (ErlNifEnv *env, ErlNifMapIterator *iter));
+ERL_NIF_API_FUNC_DECL(int, enif_map_iterator_get_pair, (ErlNifEnv *env, ErlNifMapIterator *iter, ERL_NIF_TERM *key, ERL_NIF_TERM *value));
+
+
 /*
 ** Add new entries here to keep compatibility on Windows!!!
 */
@@ -281,6 +297,21 @@ ERL_NIF_API_FUNC_DECL(int,enif_have_dirty_schedulers,(void));
 #  define enif_have_dirty_schedulers ERL_NIF_API_FUNC_MACRO(enif_have_dirty_schedulers)
 #endif
 
+#  define enif_is_map ERL_NIF_API_FUNC_MACRO(enif_is_map)
+#  define enif_get_map_size ERL_NIF_API_FUNC_MACRO(enif_get_map_size)
+#  define enif_make_new_map ERL_NIF_API_FUNC_MACRO(enif_make_new_map)
+#  define enif_make_map_put ERL_NIF_API_FUNC_MACRO(enif_make_map_put)
+#  define enif_get_map_value ERL_NIF_API_FUNC_MACRO(enif_get_map_value)
+#  define enif_make_map_update ERL_NIF_API_FUNC_MACRO(enif_make_map_update)
+#  define enif_make_map_remove ERL_NIF_API_FUNC_MACRO(enif_make_map_remove)
+#  define enif_map_iterator_create ERL_NIF_API_FUNC_MACRO(enif_map_iterator_create)
+#  define enif_map_iterator_destroy ERL_NIF_API_FUNC_MACRO(enif_map_iterator_destroy)
+#  define enif_map_iterator_is_head ERL_NIF_API_FUNC_MACRO(enif_map_iterator_is_head)
+#  define enif_map_iterator_is_tail ERL_NIF_API_FUNC_MACRO(enif_map_iterator_is_tail)
+#  define enif_map_iterator_next ERL_NIF_API_FUNC_MACRO(enif_map_iterator_next)
+#  define enif_map_iterator_prev ERL_NIF_API_FUNC_MACRO(enif_map_iterator_prev)
+#  define enif_map_iterator_get_pair ERL_NIF_API_FUNC_MACRO(enif_map_iterator_get_pair)
+
 /*
 ** Add new entries here
 */
diff --git a/erts/emulator/beam/erl_printf_term.c b/erts/emulator/beam/erl_printf_term.c
index 436147749e..d18760dc43 100644
--- a/erts/emulator/beam/erl_printf_term.c
+++ b/erts/emulator/beam/erl_printf_term.c
@@ -24,6 +24,7 @@
 #include "erl_printf_term.h"
 #include "sys.h"
 #include "big.h"
+#include "erl_map.h"
 
 #define PRINT_CHAR(CNT, FN, ARG, C)					\
 do {									\
@@ -216,14 +217,15 @@ static int print_atom_name(fmtfn_t fn, void* arg, Eterm atom, long *dcount)
 }
 
 
-#define PRT_BAR ((Eterm) 0)
-#define PRT_COMMA ((Eterm) 1)
-#define PRT_CLOSE_LIST ((Eterm) 2)
-#define PRT_CLOSE_TUPLE ((Eterm) 3)
-#define PRT_TERM ((Eterm) 4)
-#define PRT_ONE_CONS ((Eterm) 5)
-#define PRT_PATCH_FUN_SIZE ((Eterm) 6)
-#define PRT_LAST_ARRAY_ELEMENT ((Eterm) 7) /* Note! Must be last... */
+#define PRT_BAR                ((Eterm) 0)
+#define PRT_COMMA              ((Eterm) 1)
+#define PRT_CLOSE_LIST         ((Eterm) 2)
+#define PRT_CLOSE_TUPLE        ((Eterm) 3)
+#define PRT_ASSOC              ((Eterm) 4)
+#define PRT_TERM               ((Eterm) 5)
+#define PRT_ONE_CONS           ((Eterm) 6)
+#define PRT_PATCH_FUN_SIZE     ((Eterm) 7)
+#define PRT_LAST_ARRAY_ELEMENT ((Eterm) 8) /* Note! Must be last... */
 
 static int
 print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount,
@@ -260,6 +262,9 @@ print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount,
 	case PRT_CLOSE_TUPLE:
 	    PRINT_CHAR(res, fn, arg, '}');
 	    goto L_outer_loop;
+	case PRT_ASSOC:
+	    PRINT_STRING(res, fn, arg, "=>");
+	    goto L_outer_loop;
 	default:
 	    popped.word = WSTACK_POP(s);
 
@@ -483,6 +488,37 @@ print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount,
 		PRINT_CHAR(res, fn, arg, '>');
 	    }
 	    break;
+	case MAP_DEF:
+	    {
+		Uint n;
+		Eterm *ks, *vs;
+		map_t *mp = (map_t *)map_val(wobj);
+		n  = map_get_size(mp);
+		ks = map_get_keys(mp);
+		vs = map_get_values(mp);
+
+		PRINT_CHAR(res, fn, arg, '#');
+		PRINT_CHAR(res, fn, arg, '{');
+		WSTACK_PUSH(s, PRT_CLOSE_TUPLE);
+		if (n > 0) {
+		    n--;
+		    WSTACK_PUSH(s, vs[n]);
+		    WSTACK_PUSH(s, PRT_TERM);
+		    WSTACK_PUSH(s, PRT_ASSOC);
+		    WSTACK_PUSH(s, ks[n]);
+		    WSTACK_PUSH(s, PRT_TERM);
+
+		    while (n--) {
+			WSTACK_PUSH(s, PRT_COMMA);
+			WSTACK_PUSH(s, vs[n]);
+			WSTACK_PUSH(s, PRT_TERM);
+			WSTACK_PUSH(s, PRT_ASSOC);
+			WSTACK_PUSH(s, ks[n]);
+			WSTACK_PUSH(s, PRT_TERM);
+		    }
+		}
+	    }
+	    break;
 	default:
 	    PRINT_STRING(res, fn, arg, "<unknown:");
 	    PRINT_POINTER(res, fn, arg, wobj);
diff --git a/erts/emulator/beam/erl_term.c b/erts/emulator/beam/erl_term.c
index 2f206ffbec..28cbe7004f 100644
--- a/erts/emulator/beam/erl_term.c
+++ b/erts/emulator/beam/erl_term.c
@@ -23,6 +23,7 @@
 #include "sys.h"
 #include "erl_vm.h"
 #include "global.h"
+#include "erl_map.h"
 #include <stdlib.h>
 #include <stdio.h>
 
@@ -85,7 +86,10 @@ unsigned tag_val_def(Wterm x)
 	    case (_TAG_HEADER_EXTERNAL_PID >> _TAG_PRIMARY_SIZE):	return EXTERNAL_PID_DEF;
 	    case (_TAG_HEADER_EXTERNAL_PORT >> _TAG_PRIMARY_SIZE):	return EXTERNAL_PORT_DEF;
 	    case (_TAG_HEADER_EXTERNAL_REF >> _TAG_PRIMARY_SIZE):	return EXTERNAL_REF_DEF;
-	    default:						return BINARY_DEF;
+	    case (_TAG_HEADER_REFC_BIN >> _TAG_PRIMARY_SIZE):	return BINARY_DEF;
+	    case (_TAG_HEADER_HEAP_BIN >> _TAG_PRIMARY_SIZE):	return BINARY_DEF;
+	    case (_TAG_HEADER_SUB_BIN >> _TAG_PRIMARY_SIZE):	return BINARY_DEF;
+	    case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE):	return MAP_DEF;
 	  }
 	  break;
       }
diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h
index 50d3e63c58..f10a3a9d38 100644
--- a/erts/emulator/beam/erl_term.h
+++ b/erts/emulator/beam/erl_term.h
@@ -135,11 +135,12 @@ struct erl_node_; /* Declared in erl_node_tables.h */
 #define REF_SUBTAG		(0x4 << _TAG_PRIMARY_SIZE) /* REF */
 #define FUN_SUBTAG		(0x5 << _TAG_PRIMARY_SIZE) /* FUN */
 #define FLOAT_SUBTAG		(0x6 << _TAG_PRIMARY_SIZE) /* FLOAT */
-#define EXPORT_SUBTAG	(0x7 << _TAG_PRIMARY_SIZE) /* FLOAT */
+#define EXPORT_SUBTAG		(0x7 << _TAG_PRIMARY_SIZE) /* FLOAT */
 #define _BINARY_XXX_MASK	(0x3 << _TAG_PRIMARY_SIZE)
 #define REFC_BINARY_SUBTAG	(0x8 << _TAG_PRIMARY_SIZE) /* BINARY */
 #define HEAP_BINARY_SUBTAG	(0x9 << _TAG_PRIMARY_SIZE) /* BINARY */
 #define SUB_BINARY_SUBTAG	(0xA << _TAG_PRIMARY_SIZE) /* BINARY */
+#define MAP_SUBTAG		(0xB << _TAG_PRIMARY_SIZE) /* MAP */
 #define EXTERNAL_PID_SUBTAG	(0xC << _TAG_PRIMARY_SIZE) /* EXTERNAL_PID */
 #define EXTERNAL_PORT_SUBTAG	(0xD << _TAG_PRIMARY_SIZE) /* EXTERNAL_PORT */
 #define EXTERNAL_REF_SUBTAG	(0xE << _TAG_PRIMARY_SIZE) /* EXTERNAL_REF */
@@ -155,6 +156,7 @@ struct erl_node_; /* Declared in erl_node_tables.h */
 #define _TAG_HEADER_REFC_BIN	(TAG_PRIMARY_HEADER|REFC_BINARY_SUBTAG)
 #define _TAG_HEADER_HEAP_BIN	(TAG_PRIMARY_HEADER|HEAP_BINARY_SUBTAG)
 #define _TAG_HEADER_SUB_BIN	(TAG_PRIMARY_HEADER|SUB_BINARY_SUBTAG)
+#define _TAG_HEADER_MAP	 	(TAG_PRIMARY_HEADER|MAP_SUBTAG)
 #define _TAG_HEADER_EXTERNAL_PID  (TAG_PRIMARY_HEADER|EXTERNAL_PID_SUBTAG)
 #define _TAG_HEADER_EXTERNAL_PORT (TAG_PRIMARY_HEADER|EXTERNAL_PORT_SUBTAG)
 #define _TAG_HEADER_EXTERNAL_REF  (TAG_PRIMARY_HEADER|EXTERNAL_REF_SUBTAG)
@@ -354,7 +356,10 @@ _ET_DECLARE_CHECKED(Uint,thing_subtag,Eterm)
 #define is_value(x)	((x) != THE_NON_VALUE)
 
 /* binary object access methods */
-#define is_binary_header(x)	(((x) & (_TAG_HEADER_MASK-_BINARY_XXX_MASK)) == _TAG_HEADER_REFC_BIN)
+#define is_binary_header(x) \
+	((((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_REFC_BIN) || \
+	 (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HEAP_BIN) || \
+	 (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_SUB_BIN))
 #define make_binary(x)	make_boxed((Eterm*)(x))
 #define is_binary(x)	(is_boxed((x)) && is_binary_header(*boxed_val((x))))
 #define is_not_binary(x) (!is_binary((x)))
@@ -1064,8 +1069,8 @@ _ET_DECLARE_CHECKED(Uint,y_reg_index,Uint)
 
 /*
  * Backwards compatibility definitions:
- * - #define virtal *_DEF constants with values that fit term order:
- *   number < atom < ref < fun < port < pid < tuple < nil < cons < binary
+ * - #define virtual *_DEF constants with values that fit term order:
+ *   number < atom < ref < fun < port < pid < tuple < map < nil < cons < binary
  * - tag_val_def() function generates virtual _DEF tag
  * - not_eq_tags() and NUMBER_CODE() defined in terms
  *   of the tag_val_def() function
@@ -1074,19 +1079,20 @@ _ET_DECLARE_CHECKED(Uint,y_reg_index,Uint)
 #define BINARY_DEF		0x0
 #define LIST_DEF		0x1
 #define NIL_DEF			0x2
-#define TUPLE_DEF		0x3
-#define PID_DEF			0x4
-#define EXTERNAL_PID_DEF	0x5
-#define PORT_DEF		0x6
-#define EXTERNAL_PORT_DEF	0x7
-#define EXPORT_DEF		0x8
-#define FUN_DEF			0x9
-#define REF_DEF			0xa
-#define EXTERNAL_REF_DEF	0xb
-#define ATOM_DEF		0xc
-#define FLOAT_DEF		0xd
-#define BIG_DEF			0xe
-#define SMALL_DEF		0xf
+#define MAP_DEF			0x3
+#define TUPLE_DEF		0x4
+#define PID_DEF			0x5
+#define EXTERNAL_PID_DEF	0x6
+#define PORT_DEF		0x7
+#define EXTERNAL_PORT_DEF	0x8
+#define EXPORT_DEF		0x9
+#define FUN_DEF			0xa
+#define REF_DEF			0xb
+#define EXTERNAL_REF_DEF	0xc
+#define ATOM_DEF		0xd
+#define FLOAT_DEF		0xe
+#define BIG_DEF			0xf
+#define SMALL_DEF		0x10
 
 #if ET_DEBUG
 extern unsigned tag_val_def_debug(Wterm, const char*, unsigned);
@@ -1096,8 +1102,8 @@ extern unsigned tag_val_def(Wterm);
 #endif
 #define not_eq_tags(X,Y)	(tag_val_def((X)) ^ tag_val_def((Y)))
 
-#define NUMBER_CODE(x,y)	((tag_val_def(x) << 4) | tag_val_def(y))
-#define _NUMBER_CODE(TX,TY)	((TX << 4) | TY)
+#define NUMBER_CODE(x,y)	((tag_val_def(x) << 5) | tag_val_def(y))
+#define _NUMBER_CODE(TX,TY)	((TX << 5) | TY)
 #define SMALL_SMALL	_NUMBER_CODE(SMALL_DEF,SMALL_DEF)
 #define SMALL_BIG 	_NUMBER_CODE(SMALL_DEF,BIG_DEF)
 #define SMALL_FLOAT 	_NUMBER_CODE(SMALL_DEF,FLOAT_DEF)
diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h
index 292d135946..5b81d814c6 100644
--- a/erts/emulator/beam/erl_utils.h
+++ b/erts/emulator/beam/erl_utils.h
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 2012-2013. All Rights Reserved.
+ * Copyright Ericsson AB 2012-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -202,23 +202,37 @@ int eq(Eterm, Eterm);
 #define EQ(x,y) (((x) == (y)) || (is_not_both_immed((x),(y)) && eq((x),(y))))
 
 #if HALFWORD_HEAP
-Sint cmp_rel(Eterm, Eterm*, Eterm, Eterm*);
-#define CMP(A,B) cmp_rel(A,NULL,B,NULL)
+Sint cmp_rel_opt(Eterm, Eterm*, Eterm, Eterm*, int);
+#define cmp_rel(A,A_BASE,B,B_BASE)       cmp_rel_opt(A,A_BASE,B,B_BASE,0)
+#define cmp_rel_term(A,A_BASE,B,B_BASE)  cmp_rel_opt(A,A_BASE,B,B_BASE,1)
+#define CMP(A,B)                         cmp_rel_opt(A,NULL,B,NULL,0)
+#define CMP_TERM(A,B)                    cmp_rel_opt(A,NULL,B,NULL,1)
 #else
-Sint cmp(Eterm, Eterm);
-#define cmp_rel(A,A_BASE,B,B_BASE) cmp(A,B)
-#define CMP(A,B) cmp(A,B)
+Sint cmp(Eterm, Eterm, int);
+#define cmp_rel(A,A_BASE,B,B_BASE)       cmp(A,B,0)
+#define cmp_rel_term(A,A_BASE,B,B_BASE)  cmp(A,B,1)
+#define CMP(A,B)                         cmp(A,B,0)
+#define CMP_TERM(A,B)                    cmp(A,B,1)
 #endif
-#define cmp_lt(a,b)	(CMP((a),(b)) < 0)
-#define cmp_le(a,b)	(CMP((a),(b)) <= 0)
-#define cmp_eq(a,b)	(CMP((a),(b)) == 0)
-#define cmp_ne(a,b)	(CMP((a),(b)) != 0)
-#define cmp_ge(a,b)	(CMP((a),(b)) >= 0)
-#define cmp_gt(a,b)	(CMP((a),(b)) > 0)
-
-#define CMP_LT(a,b)	((a) != (b) && cmp_lt((a),(b)))
-#define CMP_GE(a,b)	((a) == (b) || cmp_ge((a),(b)))
-#define CMP_EQ(a,b)	((a) == (b) || cmp_eq((a),(b)))
-#define CMP_NE(a,b)	((a) != (b) && cmp_ne((a),(b)))
+
+#define cmp_lt(a,b)          (CMP((a),(b)) <  0)
+#define cmp_le(a,b)          (CMP((a),(b)) <= 0)
+#define cmp_eq(a,b)          (CMP((a),(b)) == 0)
+#define cmp_ne(a,b)          (CMP((a),(b)) != 0)
+#define cmp_ge(a,b)          (CMP((a),(b)) >= 0)
+#define cmp_gt(a,b)          (CMP((a),(b)) >  0)
+
+#define cmp_lt_term(a,b)     (CMP_TERM((a),(b)) <  0)
+#define cmp_le_term(a,b)     (CMP_TERM((a),(b)) <= 0)
+#define cmp_ge_term(a,b)     (CMP_TERM((a),(b)) >= 0)
+#define cmp_gt_term(a,b)     (CMP_TERM((a),(b)) >  0)
+
+#define CMP_LT(a,b)          ((a) != (b) && cmp_lt((a),(b)))
+#define CMP_GE(a,b)          ((a) == (b) || cmp_ge((a),(b)))
+#define CMP_EQ(a,b)          ((a) == (b) || cmp_eq((a),(b)))
+#define CMP_NE(a,b)          ((a) != (b) && cmp_ne((a),(b)))
+
+#define CMP_LT_TERM(a,b)     ((a) != (b) && cmp_lt_term((a),(b)))
+#define CMP_GE_TERM(a,b)     ((a) == (b) || cmp_ge_term((a),(b)))
 
 #endif
diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index 5e7a5cab6e..a4cc3435c3 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -42,6 +42,7 @@
 #include "erl_binary.h"
 #include "erl_bits.h"
 #include "erl_zlib.h"
+#include "erl_map.h"
 
 #ifdef HIPE
 #include "hipe_mode_switch.h"
@@ -2555,6 +2556,38 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep,
 	    }
 	    break;
 
+	case MAP_DEF:
+	    {
+		map_t *mp = (map_t*)map_val(obj);
+		Uint size = map_get_size(mp);
+		Eterm *mptr;
+
+		*ep++ = MAP_EXT;
+		put_int32(size, ep); ep += 4;
+
+		/* Push values first */
+		if (size > 0) {
+		    mptr = map_get_values(mp);
+		    for (i = size-1; i >= 1; i--) {
+			WSTACK_PUSH(s, ENC_TERM);
+			WSTACK_PUSH(s, (UWord) mptr[i]);
+		    }
+
+		    WSTACK_PUSH(s, ENC_TERM);
+		    WSTACK_PUSH(s, (UWord) mptr[0]);
+
+		    mptr = map_get_keys(mp);
+		    for (i = size-1; i >= 1; i--) {
+			WSTACK_PUSH(s, ENC_TERM);
+			WSTACK_PUSH(s, (UWord) mptr[i]);
+		    }
+
+		    obj = mptr[0];
+		    goto L_jump_start;
+		}
+	    }
+	    break;
+
 	case FLOAT_DEF:
 	    GET_DOUBLE(obj, f);
 	    if (dflags & DFLAG_NEW_FLOATS) {
@@ -2845,6 +2878,7 @@ dec_term(ErtsDistExternal *edep, Eterm** hpp, byte* ep, ErlOffHeap* off_heap,
     int n;
     ErtsAtomEncoding char_enc;
     register Eterm* hp;        /* Please don't take the address of hp */
+    Eterm *maps_head = NULL; /* for validation of maps */
     Eterm* next;
     SWord reds;
 
@@ -3469,6 +3503,65 @@ dec_term_atom_common:
 		break;
 	    }
 	    break;
+	case MAP_EXT:
+	    {
+		map_t *mp;
+		Uint32 size,n;
+		Eterm *kptr,*vptr;
+		Eterm keys;
+
+		size = get_int32(ep); ep += 4;
+
+		keys  = make_tuple(hp);
+		*hp++ = make_arityval(size);
+		kptr  = hp;
+		hp   += size;
+
+		mp    = (map_t*)hp;
+		hp   += MAP_HEADER_SIZE;
+		vptr  = hp;
+		hp   += size;
+
+		/* kptr, first word for keys
+		 * vptr, first word for values
+		 */
+
+		/*
+		 * Use thing_word to link through decoded maps.
+		 * The list of maps is for later validation.
+		 */
+
+		mp->thing_word = (Eterm) COMPRESS_POINTER(maps_head);
+		maps_head      = (Eterm *) mp;
+
+		mp->size       = size;
+		mp->keys       = keys;
+		*objp          = make_map(mp);
+
+		/* We assume the map is wellformed, meaning:
+		 * - ascending key order
+		 * - unique keys
+		 */
+
+		objp  = vptr + size - 1;
+		n     = size;
+
+		while (n-- > 0) {
+		    *objp = (Eterm) COMPRESS_POINTER(next);
+		    next  = objp;
+		    objp--;
+		}
+
+		objp  = kptr + size - 1;
+		n     = size;
+
+		while (n-- > 0) {
+		    *objp = (Eterm) COMPRESS_POINTER(next);
+		    next  = objp;
+		    objp--;
+		}
+	    }
+	    break;
 	case NEW_FUN_EXT:
 	    {
 		ErlFunThing* funp = (ErlFunThing *) hp;
@@ -3678,21 +3771,7 @@ dec_term_atom_common:
 	    }
 
 	default:
-	error:
-	    /* UNDO:
-	     * Must unlink all off-heap objects that may have been
-	     * linked into the process. 
-	     */
-	    if (hp < *hpp) { /* Sometimes we used hp and sometimes *hpp */
-		hp = *hpp;   /* the largest must be the freshest */
-	    }
-	    undo_offheap_in_area(off_heap, hp_saved, hp);
-	    *hpp = hp_saved;
-            if (ctx) {
-                ctx->state = B2TDecodeFail;
-		ctx->reds = reds;
-            }
-            return NULL;
+	    goto error;
 	}
 
         if (--reds <= 0) {
@@ -3710,12 +3789,43 @@ dec_term_atom_common:
             }
         }
     }
+
+    /* Iterate through all the maps and check for validity and sort keys
+     * - done here for when we know it is complete.
+     */
+
+    while (maps_head) {
+	next  = (Eterm *)(EXPAND_POINTER(*maps_head));
+	*maps_head = MAP_HEADER;
+	if (!erts_validate_and_sort_map((map_t*)maps_head))
+	    goto error;
+	maps_head  = next;
+    }
+
     if (ctx) {
         ctx->state = B2TDone;
 	ctx->reds = reds;
     }
+
     *hpp = hp;
     return ep;
+
+error:
+    /* UNDO:
+     * Must unlink all off-heap objects that may have been
+     * linked into the process. 
+     */
+    if (hp < *hpp) { /* Sometimes we used hp and sometimes *hpp */
+	hp = *hpp;   /* the largest must be the freshest */
+    }
+    undo_offheap_in_area(off_heap, hp_saved, hp);
+    *hpp = hp_saved;
+    if (ctx) {
+	ctx->state = B2TDecodeFail;
+	ctx->reds = reds;
+    }
+        
+    return NULL;
 }
 
 /* returns the number of bytes needed to encode an object
@@ -3885,6 +3995,46 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj,
 		goto outer_loop;
 	    }
 	    break;
+	case MAP_DEF:
+	    {
+		map_t *mp = (map_t*)map_val(obj);
+		Uint size = map_get_size(mp);
+		Uint i;
+		Eterm *ptr;
+
+		result += 1 + 4; /* tag + 4 bytes size */
+
+		/* push values first */
+		ptr = map_get_values(mp);
+		i   = size;
+		while(i--) {
+		    if (is_list(*ptr)) {
+			if ((m = is_string(*ptr)) && (m < MAX_STRING_LEN)) {
+			    result += m + 2 + 1;
+			} else {
+			    result += 5;
+			}
+		    }
+		    ESTACK_PUSH(s,*ptr);
+		    ++ptr;
+		}
+
+		ptr = map_get_keys(mp);
+		i   = size;
+		while(i--) {
+		    if (is_list(*ptr)) {
+			if ((m = is_string(*ptr)) && (m < MAX_STRING_LEN)) {
+			    result += m + 2 + 1;
+			} else {
+			    result += 5;
+			}
+		    }
+		    ESTACK_PUSH(s,*ptr);
+		    ++ptr;
+		}
+		goto outer_loop;
+	    }
+	    break;
 	case FLOAT_DEF:
 	    if (dflags & DFLAG_NEW_FLOATS) {
 		result += 9;
@@ -4175,6 +4325,13 @@ init_done:
 	    ADDTERMS(n);
 	    heap_size += n + 1;
 	    break;
+	case MAP_EXT:
+	    CHKSIZE(4);
+	    n = get_int32(ep);
+	    ep += 4;
+	    ADDTERMS(2*n);
+	    heap_size += 3 + n + 1 + n;
+	    break;
 	case STRING_EXT:
 	    CHKSIZE(2);
 	    n = get_int16(ep);
diff --git a/erts/emulator/beam/external.h b/erts/emulator/beam/external.h
index 83001b2c7e..bf00958eb1 100644
--- a/erts/emulator/beam/external.h
+++ b/erts/emulator/beam/external.h
@@ -50,6 +50,7 @@
 #define LARGE_BIG_EXT     'o'
 #define NEW_FUN_EXT       'p'
 #define EXPORT_EXT        'q'
+#define MAP_EXT           't'
 #define FUN_EXT           'u'
 #define ATOM_UTF8_EXT     'v'
 #define SMALL_ATOM_UTF8_EXT 'w'
diff --git a/erts/emulator/beam/global.h b/erts/emulator/beam/global.h
index 83a8911a36..8fcb95d0e2 100755
--- a/erts/emulator/beam/global.h
+++ b/erts/emulator/beam/global.h
@@ -998,6 +998,7 @@ Eterm erts_gc_length_1(Process* p, Eterm* reg, Uint live);
 Eterm erts_gc_size_1(Process* p, Eterm* reg, Uint live);
 Eterm erts_gc_bit_size_1(Process* p, Eterm* reg, Uint live);
 Eterm erts_gc_byte_size_1(Process* p, Eterm* reg, Uint live);
+Eterm erts_gc_map_size_1(Process* p, Eterm* reg, Uint live);
 Eterm erts_gc_abs_1(Process* p, Eterm* reg, Uint live);
 Eterm erts_gc_float_1(Process* p, Eterm* reg, Uint live);
 Eterm erts_gc_round_1(Process* p, Eterm* reg, Uint live);
diff --git a/erts/emulator/beam/io.c b/erts/emulator/beam/io.c
index 49af86b36a..3b16cdeb4a 100644
--- a/erts/emulator/beam/io.c
+++ b/erts/emulator/beam/io.c
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 1996-2013. All Rights Reserved.
+ * Copyright Ericsson AB 1996-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -46,6 +46,7 @@
 #define ERTS_WANT_EXTERNAL_TAGS
 #include "external.h"
 #include "dtrace-wrapper.h"
+#include "erl_map.h"
 
 extern ErlDrvEntry fd_driver_entry;
 extern ErlDrvEntry vanilla_driver_entry;
@@ -5293,6 +5294,17 @@ driver_deliver_term(Eterm to, ErlDrvTermData* data, int len)
 	    depth++;
 	    break;
 	}
+	case ERL_DRV_MAP: { /* int */
+	    ERTS_DDT_CHK_ENOUGH_ARGS(1);
+	    if ((int) ptr[0] < 0) ERTS_DDT_FAIL;
+	    need += MAP_HEADER_SIZE + 1 + 2*ptr[0];
+	    depth -= 2*ptr[0];
+	    if (depth < 0) ERTS_DDT_FAIL;
+	    ptr++;
+	    depth++;
+	    break;
+	}
+
 	default:
 	    ERTS_DDT_FAIL;
 	}
@@ -5529,6 +5541,36 @@ driver_deliver_term(Eterm to, ErlDrvTermData* data, int len)
 	    ptr += 2;
 	    break;
 
+	case ERL_DRV_MAP: { /* int */
+	    int size = (int)ptr[0];
+	    Eterm* tp = hp;
+	    Eterm* vp;
+	    map_t *mp;
+
+	    *tp = make_arityval(size);
+
+	    hp += 1 + size;
+	    mp = (map_t*)hp;
+	    mp->thing_word = MAP_HEADER;
+	    mp->size = size;
+	    mp->keys = make_tuple(tp);
+	    mess = make_map(mp);
+
+	    hp += MAP_HEADER_SIZE + size;   /* advance "heap" pointer */
+
+	    tp += size;    /* point at last key */
+	    vp = hp - 1;   /* point at last value */
+
+	    while(size--) {
+		*vp-- = ESTACK_POP(stack);
+		*tp-- = ESTACK_POP(stack);
+	    }
+	    if (!erts_validate_and_sort_map(mp))
+		ERTS_DDT_FAIL;
+	    ptr++;
+	    break;
+	}
+
 	}
 	ESTACK_PUSH(stack, mess);
     }
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index c29f3f9b1b..f35997efee 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1466,6 +1466,75 @@ apply I
 apply_last I P
 
 #
+# Map instructions in R17.
+#
+
+# put_map Fail Src Dst Live Size Rest=* => jump Fail
+# is_map Fail Src => jump Fail
+# has_map_field Fail Src Key => jump Fail
+# get_map_element Fail Src Key Dst => jump Fail
+
+put_map_assoc F n Dst Live Size Rest=* => new_map F Dst Live Size Rest
+put_map_exact F n Dst Live Size Rest=* => new_map F Dst Live Size Rest
+put_map_assoc F Src Dst Live Size Rest=* => \
+	       update_map_assoc F Src Dst Live Size Rest
+put_map_exact F Src Dst Live Size Rest=* => \
+	      update_map_exact F Src Dst Live Size Rest
+
+new_map j d I I
+update_map_assoc j d d I I
+update_map_exact j d d I I
+
+is_map Fail cq => jump Fail
+
+%macro: is_map IsMap -fail_action
+is_map f r
+is_map f x
+is_map f y
+
+has_map_field Fail Src=rxy Key=arxy => i_has_map_field Fail Src Key
+has_map_field Fail Src Key => move Key x | i_has_map_field Fail Src x
+
+%macro: i_has_map_field HasMapField -fail_action
+i_has_map_field f r a
+i_has_map_field f x a
+i_has_map_field f y a
+i_has_map_field f r r
+i_has_map_field f x r
+i_has_map_field f y r
+i_has_map_field f r x
+i_has_map_field f x x
+i_has_map_field f y x
+i_has_map_field f r y
+i_has_map_field f x y
+i_has_map_field f y y
+
+get_map_element Fail Src=rxy Key=ax Dst => i_get_map_element Fail Src Key Dst
+get_map_element Fail Src=rxy Key=rycq Dst => \
+    move Key x | i_get_map_element Fail Src x Dst
+get_map_element Fail Src Key Dst => jump Fail
+
+%macro: i_get_map_element GetMapElement -fail_action
+i_get_map_element f r a r
+i_get_map_element f x a r
+i_get_map_element f y a r
+i_get_map_element f r a x
+i_get_map_element f x a x
+i_get_map_element f y a x
+i_get_map_element f r a y
+i_get_map_element f x a y
+i_get_map_element f y a y
+i_get_map_element f r x r
+i_get_map_element f x x r
+i_get_map_element f y x r
+i_get_map_element f r x x
+i_get_map_element f x x x
+i_get_map_element f y x x
+i_get_map_element f r x y
+i_get_map_element f x x y
+i_get_map_element f y x y
+
+#
 # Optimize addition and subtraction of small literals using
 # the i_increment/4 instruction (in bodies, not in guards).
 #
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index e0776cf67d..bc4a05d385 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -31,6 +31,7 @@
 #include "bif.h"
 #include "erl_binary.h"
 #include "erl_bits.h"
+#include "erl_map.h"
 #include "packet_parser.h"
 #include "erl_gc.h"
 #define ERTS_WANT_DB_INTERNAL__
@@ -734,6 +735,8 @@ erts_bld_atom_2uint_3tup_list(Uint **hpp, Uint *szp, Sint length,
 #define FUNNY_NUMBER10 268440479
 #define FUNNY_NUMBER11 268440577
 #define FUNNY_NUMBER12 268440581
+#define FUNNY_NUMBER13 268440593
+#define FUNNY_NUMBER14 268440611
 
 static Uint32
 hash_binary_bytes(Eterm bin, Uint sz, Uint32 hash)
@@ -785,10 +788,10 @@ Uint32 make_hash(Eterm term_arg)
     unsigned op;
 
     /* Must not collide with the real tag_val_def's: */
-#define MAKE_HASH_TUPLE_OP 0x10
-#define MAKE_HASH_FUN_OP 0x11
-#define MAKE_HASH_CDR_PRE_OP 0x12
-#define	MAKE_HASH_CDR_POST_OP 0x13
+#define MAKE_HASH_TUPLE_OP 0x11
+#define MAKE_HASH_TERM_ARRAY_OP 0x12
+#define MAKE_HASH_CDR_PRE_OP 0x13
+#define	MAKE_HASH_CDR_POST_OP 0x14
 
     /* 
     ** Convenience macro for calculating a bytewise hash on an unsigned 32 bit 
@@ -877,7 +880,7 @@ tail_recur:
 	    hash = hash*FUNNY_NUMBER2 + funp->fe->old_uniq;
 	    if (num_free > 0) {
 		if (num_free > 1) {
-		    WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_FUN_OP);
+		    WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_TERM_ARRAY_OP);
 		}
 		term = funp->env[0];
 		goto tail_recur;
@@ -967,6 +970,24 @@ tail_recur:
 	    hash *= is_neg ? FUNNY_NUMBER4 : FUNNY_NUMBER3;
 	    break;
 	}	
+    case MAP_DEF:
+	{
+	    map_t *mp = (map_t *)map_val(term);
+	    int size  = map_get_size(mp);
+	    Eterm *ks = map_get_keys(mp);
+	    Eterm *vs = map_get_values(mp);
+
+	    /* Use a prime with size to remedy some of
+	     * the {} and <<>> hash problems */
+	    hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + size;
+	    if (size == 0)
+		break;
+
+	    /* push values first */
+	    WSTACK_PUSH3(stack, (UWord)vs, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+	    WSTACK_PUSH3(stack, (UWord)ks, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+	    break;
+	}
     case TUPLE_DEF: 
 	{
 	    Eterm* ptr = tuple_val(term);
@@ -976,7 +997,7 @@ tail_recur:
 	    op = MAKE_HASH_TUPLE_OP;	    
 	}/*fall through*/
     case MAKE_HASH_TUPLE_OP:
-    case MAKE_HASH_FUN_OP:
+    case MAKE_HASH_TERM_ARRAY_OP:
 	{
 	    Uint i = (Uint) WSTACK_POP(stack);
 	    Eterm* ptr = (Eterm*) WSTACK_POP(stack);
@@ -1070,9 +1091,11 @@ Uint32
 make_hash2(Eterm term)
 {
     Uint32 hash;
+    Uint32 hash_xor_keys   = 0;
+    Uint32 hash_xor_values = 0;
     DeclareTmpHeapNoproc(tmp_big,2);
 
-/* (HCONST * {2, ..., 14}) mod 2^32 */
+/* (HCONST * {2, ..., 16}) mod 2^32 */
 #define HCONST_2 0x3c6ef372UL
 #define HCONST_3 0xdaa66d2bUL
 #define HCONST_4 0x78dde6e4UL
@@ -1087,6 +1110,11 @@ make_hash2(Eterm term)
 #define HCONST_13 0x08d12e65UL
 #define HCONST_14 0xa708a81eUL
 #define HCONST_15 0x454021d7UL
+#define HCONST_16 0xe3779b90UL
+
+#define HASH_MAP_TAIL (_make_header(1,_TAG_HEADER_REF))
+#define HASH_MAP_KEY  (_make_header(2,_TAG_HEADER_REF))
+#define HASH_MAP_VAL  (_make_header(3,_TAG_HEADER_REF))
 
 #define UINT32_HASH_2(Expr1, Expr2, AConst)       \
          do {                                     \
@@ -1182,11 +1210,45 @@ make_hash2(Eterm term)
 		UINT32_HASH(arity, HCONST_9);
 		if (arity == 0) /* Empty tuple */ 
 		    goto hash2_common;
-		for (i = arity; i >= 2; i--) {
+		for (i = arity; i >= 1; i--) {
 		    tmp = elem[i];
 		    ESTACK_PUSH(s, tmp);
 		}
-		term = elem[1];
+		goto hash2_common;
+	    }
+	    break;
+	    case MAP_SUBTAG:
+	    {
+		map_t *mp = (map_t *)map_val(term);
+		int i;
+		int size  = map_get_size(mp);
+		Eterm *ks = map_get_keys(mp);
+		Eterm *vs = map_get_values(mp);
+		UINT32_HASH(size, HCONST_16);
+		if (size == 0) {
+		    goto hash2_common;
+		}
+		ESTACK_PUSH(s, hash_xor_values);
+		ESTACK_PUSH(s, hash_xor_keys);
+		ESTACK_PUSH(s, hash);
+		ESTACK_PUSH(s, HASH_MAP_TAIL);
+		hash = 0;
+		hash_xor_keys = 0;
+		hash_xor_values = 0;
+		for (i = size - 1; i >= 0; i--) {
+		    tmp = vs[i];
+		    ESTACK_PUSH(s, HASH_MAP_VAL);
+		    ESTACK_PUSH(s, tmp);
+		}
+		/* We do not want to expose the tuple representation.
+		 * Do not push the keys as a tuple.
+		 */
+		for (i = size - 1; i >= 0; i--) {
+		    tmp = ks[i];
+		    ESTACK_PUSH(s, HASH_MAP_KEY);
+		    ESTACK_PUSH(s, tmp);
+		}
+		goto hash2_common;
 	    }
 	    break;
 	    case EXPORT_SUBTAG:
@@ -1380,15 +1442,47 @@ make_hash2(Eterm term)
 	default:
 	    erl_exit(1, "Invalid tag in make_hash2(0x%X)\n", term);
 	hash2_common:
+
+	    /* Uint32 hash always has the hash value of the previous term,
+	     * compounded or otherwise.
+	     */
+
 	    if (ESTACK_ISEMPTY(s)) {
 		DESTROY_ESTACK(s);
 		UnUseTmpHeapNoproc(2);
 		return hash;
 	    }
+
 	    term = ESTACK_POP(s);
+
+	    switch (term) {
+		case HASH_MAP_TAIL: {
+		    hash = (Uint32) ESTACK_POP(s);
+		    UINT32_HASH(hash_xor_keys, HCONST_16);
+		    UINT32_HASH(hash_xor_values, HCONST_16);
+		    hash_xor_keys = (Uint32) ESTACK_POP(s);
+		    hash_xor_values = (Uint32) ESTACK_POP(s);
+		    goto hash2_common;
+		}
+		case HASH_MAP_KEY:
+		    hash_xor_keys ^= hash;
+		    hash = 0;
+		    goto hash2_common;
+		case HASH_MAP_VAL:
+		    hash_xor_values ^= hash;
+		    hash = 0;
+		    goto hash2_common;
+		default:
+		    break;
+	    }
 	}
     }
     }
+
+#undef HASH_MAP_TAIL
+#undef HASH_MAP_KEY
+#undef HASH_MAP_VAL
+
 #undef UINT32_HASH_2
 #undef UINT32_HASH
 #undef SINT32_HASH
@@ -1490,7 +1584,7 @@ tail_recur:
 	    hash = hash*FUNNY_NUMBER2 + funp->fe->old_uniq;
 	    if (num_free > 0) {
 		if (num_free > 1) {
-		    WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_FUN_OP);
+		    WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_TERM_ARRAY_OP);
 		}
 		term = funp->env[0];
 		goto tail_recur;
@@ -1603,6 +1697,24 @@ tail_recur:
 	}
 	break;
 
+    case MAP_DEF:
+	{
+	    map_t *mp = (map_t *)map_val(term);
+	    int size  = map_get_size(mp);
+	    Eterm *ks = map_get_keys(mp);
+	    Eterm *vs = map_get_values(mp);
+
+	    /* Use a prime with size to remedy some of
+	     * the {} and <<>> hash problems */
+	    hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + size;
+	    if (size == 0)
+		break;
+
+	    /* push values first */
+	    WSTACK_PUSH3(stack, (UWord)vs, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+	    WSTACK_PUSH3(stack, (UWord)ks, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+	    break;
+	}
     case TUPLE_DEF: 
 	{
 	    Eterm* ptr = tuple_val(term);
@@ -1612,7 +1724,7 @@ tail_recur:
 	    op = MAKE_HASH_TUPLE_OP;
 	}/*fall through*/ 
     case MAKE_HASH_TUPLE_OP:
-    case MAKE_HASH_FUN_OP:
+    case MAKE_HASH_TERM_ARRAY_OP:
 	{
 	    Uint i = (Uint) WSTACK_POP(stack);
 	    Eterm* ptr = (Eterm*) WSTACK_POP(stack);
@@ -1640,7 +1752,7 @@ tail_recur:
     return hash;
     
 #undef MAKE_HASH_TUPLE_OP
-#undef MAKE_HASH_FUN_OP
+#undef MAKE_HASH_TERM_ARRAY_OP
 #undef MAKE_HASH_CDR_PRE_OP
 #undef MAKE_HASH_CDR_POST_OP
 }
@@ -2007,6 +2119,18 @@ tailrecur_ne:
 		    ++bb;
 		    goto term_array;
 		}
+	    case MAP_SUBTAG:
+		{
+		    aa = map_val_rel(a, a_base);
+		    if (!is_boxed(b) || *boxed_val_rel(b,b_base) != *aa)
+			goto not_equal;
+		    bb = map_val_rel(b,b_base);
+		    if ((sz = map_get_size((map_t*)aa)) == 0) goto pop_next;
+		    aa += 2;
+		    bb += 2;
+		    sz += 1; /* increment for tuple-keys */
+		    goto term_array;
+		}
 	    case REFC_BINARY_SUBTAG:
 	    case HEAP_BINARY_SUBTAG:
 	    case SUB_BINARY_SUBTAG:
@@ -2281,7 +2405,7 @@ static int cmpbytes(byte *s1, int l1, byte *s2, int l2)
  *
  * According to the Erlang Standard, types are orderered as follows:
  *   numbers < (characters) < atoms < refs < funs < ports < pids <
- *   tuples < [] < conses < binaries.
+ *   tuples < maps < [] < conses < binaries.
  *
  * Note that characters are currently not implemented.
  *
@@ -2301,10 +2425,14 @@ static int cmp_atoms(Eterm a, Eterm b)
 		    bb->name+3, bb->len-3);
 }
 
+/* cmp(Eterm a, Eterm b, int exact)
+ * exact = 1 -> term-based compare
+ * exact = 0 -> arith-based compare
+ */
 #if HALFWORD_HEAP
-Sint cmp_rel(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base)
+Sint cmp_rel_opt(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base, int exact)
 #else
-Sint cmp(Eterm a, Eterm b)
+Sint cmp(Eterm a, Eterm b, int exact)
 #endif
 {
     DECLARE_WSTACK(stack);
@@ -2464,7 +2592,25 @@ tailrecur_ne:
 		++aa;
 		++bb;
 		goto term_array;
+	    case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE) :
+		if (!is_map_rel(b,b_base)) {
+		    a_tag = MAP_DEF;
+		    goto mixed_types;
+		}
+		aa = (Eterm *)map_val_rel(a,a_base);
+		bb = (Eterm *)map_val_rel(b,b_base);
 
+		i = map_get_size((map_t*)aa);
+		if (i != map_get_size((map_t*)bb)) {
+		    RETURN_NEQ((int)(i - map_get_size((map_t*)bb)));
+		}
+		if (i == 0) {
+		    goto pop_next;
+		}
+		aa += 2;
+		bb += 2;
+		i  += 1; /* increment for tuple-keys */
+		goto term_array;
 	    case (_TAG_HEADER_FLOAT >> _TAG_PRIMARY_SIZE):
 		if (!is_float_rel(b,b_base)) {
 		    a_tag = FLOAT_DEF;
@@ -2710,6 +2856,7 @@ tailrecur_ne:
 	    j = big_sign(aw) ? -1 : 1;
 	    break;
 	case SMALL_FLOAT:
+	    if (exact) goto exact_fall_through;
 	    GET_DOUBLE(bw, f2);
 	    if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) {
 		/* Float is within the no loss limit */
@@ -2735,12 +2882,14 @@ tailrecur_ne:
 #endif /* ERTS_SIZEOF_ETERM == 8 */
 	    break;
         case FLOAT_BIG:
+	    if (exact) goto exact_fall_through;
 	{
 	    Wterm tmp = aw;
 	    aw = bw;
 	    bw = tmp;
 	}/* fall through */
 	case BIG_FLOAT:
+	    if (exact) goto exact_fall_through;
 	    GET_DOUBLE(bw, f2);
 	    if ((f2.fd < (double) (MAX_SMALL + 1))
 		    && (f2.fd > (double) (MIN_SMALL - 1))) {
@@ -2770,6 +2919,7 @@ tailrecur_ne:
 	    }
 	    break;
 	case FLOAT_SMALL:
+	    if (exact) goto exact_fall_through;
 	    GET_DOUBLE(aw, f1);
 	    if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) {
 		/* Float is within the no loss limit */
@@ -2794,6 +2944,7 @@ tailrecur_ne:
 	    }
 #endif /* ERTS_SIZEOF_ETERM == 8 */
 	    break;
+exact_fall_through:
 	default:
 	    j = b_tag - a_tag;
 	}
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] = '-'
diff --git a/erts/emulator/test/Makefile b/erts/emulator/test/Makefile
index f02ca3cb98..0b0568c31a 100644
--- a/erts/emulator/test/Makefile
+++ b/erts/emulator/test/Makefile
@@ -68,6 +68,7 @@ MODULES= \
 	hash_SUITE \
 	hibernate_SUITE \
 	list_bif_SUITE \
+	map_SUITE \
 	match_spec_SUITE \
 	module_info_SUITE \
 	monitor_SUITE \
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
new file mode 100644
index 0000000000..31c1486f1c
--- /dev/null
+++ b/erts/emulator/test/map_SUITE.erl
@@ -0,0 +1,1056 @@
+%% %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%
+%%
+-module(map_SUITE).
+-export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1, 
+	init_per_group/2,end_per_group/2
+    ]).
+
+-export([
+	t_build_and_match_literals/1,
+	t_update_literals/1,t_match_and_update_literals/1,
+	t_update_map_expressions/1,
+	t_update_assoc/1,t_update_exact/1,
+	t_guard_bifs/1, t_guard_sequence/1, t_guard_update/1,
+	t_guard_receive/1, t_guard_fun/1,
+	t_list_comprehension/1,
+	t_map_sort_literals/1,
+	%t_size/1,
+	t_map_size/1,
+
+	%% Specific Map BIFs
+	t_bif_map_get/1,
+	t_bif_map_find/1,
+	t_bif_map_is_key/1,
+	t_bif_map_keys/1,
+	t_bif_map_merge/1,
+	t_bif_map_new/1,
+	t_bif_map_put/1,
+	t_bif_map_remove/1,
+	t_bif_map_update/1,
+	t_bif_map_values/1,
+	t_bif_map_to_list/1,
+	t_bif_map_from_list/1,
+
+	%% erlang
+	t_erlang_hash/1,
+	t_map_encode_decode/1,
+
+	%% maps module not bifs
+	t_maps_fold/1,
+	t_maps_map/1,
+	t_maps_size/1,
+	t_maps_without/1,
+
+	%% misc
+	t_pdict/1,
+	t_ets/1,
+	t_dets/1,
+	t_tracing/1
+    ]).
+
+-include_lib("stdlib/include/ms_transform.hrl").
+
+suite() -> [].
+
+all() -> [
+	t_build_and_match_literals,
+	t_update_literals, t_match_and_update_literals,
+	t_update_map_expressions,
+	t_update_assoc,t_update_exact,
+	t_guard_bifs, t_guard_sequence, t_guard_update,
+	t_guard_receive,t_guard_fun, t_list_comprehension,
+	t_map_sort_literals,
+
+	%% Specific Map BIFs
+	t_bif_map_get,t_bif_map_find,t_bif_map_is_key,
+	t_bif_map_keys, t_bif_map_merge, t_bif_map_new,
+	t_bif_map_put,
+	t_bif_map_remove, t_bif_map_update,
+	t_bif_map_values,
+	t_bif_map_to_list, t_bif_map_from_list,
+
+	%% erlang
+	t_erlang_hash, t_map_encode_decode,
+	t_map_size,
+
+	%% maps module
+	t_maps_fold, t_maps_map,
+	t_maps_size, t_maps_without,
+
+
+        %% Other functions
+	t_pdict,
+	t_ets,
+	t_tracing
+    ].
+
+groups() -> [].
+
+init_per_suite(Config) -> Config.
+end_per_suite(_Config) -> ok.
+
+init_per_group(_GroupName, Config) -> Config.
+end_per_group(_GroupName, Config) -> Config.
+
+%% tests
+
+t_build_and_match_literals(Config) when is_list(Config) ->
+    #{} = id(#{}),
+    #{1:=a} = id(#{1=>a}),
+    #{1:=a,2:=b} = id(#{1=>a,2=>b}),
+    #{1:=a,2:=b,3:="c"} = id(#{1=>a,2=>b,3=>"c"}),
+    #{1:=a,2:=b,3:="c","4":="d"} = id(#{1=>a,2=>b,3=>"c","4"=>"d"}),
+    #{1:=a,2:=b,3:="c","4":="d",<<"5">>:=<<"e">>} =
+	id(#{1=>a,2=>b,3=>"c","4"=>"d",<<"5">>=><<"e">>}),
+    #{1:=a,2:=b,3:="c","4":="d",<<"5">>:=<<"e">>,{"6",7}:="f"} =
+	id(#{1=>a,2=>b,3=>"c","4"=>"d",<<"5">>=><<"e">>,{"6",7}=>"f"}),
+    #{1:=a,2:=b,3:="c","4":="d",<<"5">>:=<<"e">>,{"6",7}:="f",8:=g} =
+	id(#{1=>a,2=>b,3=>"c","4"=>"d",<<"5">>=><<"e">>,{"6",7}=>"f",8=>g}),
+
+    #{<<"hi all">> := 1} = id(#{<<"hi",32,"all">> => 1}),
+
+    #{a:=X,a:=X=3,b:=4} = id(#{a=>3,b=>4}), % weird but ok =)
+
+    #{ a:=#{ b:=#{c := third, b:=second}}, b:=first} =
+	id(#{ b=>first, a=>#{ b=>#{c => third, b=> second}}}),
+
+    M = #{ map_1=>#{ map_2=>#{value_3 => third}, value_2=> second}, value_1=>first},
+    M = #{ map_1:=#{ map_2:=#{value_3 := third}, value_2:= second}, value_1:=first} =
+	 id(#{ map_1=>#{ map_2=>#{value_3 => third}, value_2=> second}, value_1=>first}),
+
+    %% error case
+    %V = 32,
+    %{'EXIT',{{badmatch,_},_}} = (catch (#{<<"hi all">> => 1} = id(#{<<"hi",V,"all">> => 1}))),
+    {'EXIT',{{badmatch,_},_}} = (catch (#{x:=3,x:=2} = id(#{x=>3}))),
+    {'EXIT',{{badmatch,_},_}} = (catch (#{x:=2} = id(#{x=>3}))),
+    {'EXIT',{{badmatch,_},_}} = (catch (#{x:=3} = id({a,b,c}))),
+    {'EXIT',{{badmatch,_},_}} = (catch (#{x:=3} = id(#{y=>3}))),
+    {'EXIT',{{badmatch,_},_}} = (catch (#{x:=3} = id(#{x=>"three"}))),
+    ok.
+
+
+%% Tests size(Map).
+%% not implemented, perhaps it shouldn't be either
+
+%t_size(Config) when is_list(Config) ->
+%    0 = size(#{}),
+%    1 = size(#{a=>1}),
+%    1 = size(#{a=>#{a=>1}}),
+%    2 = size(#{a=>1, b=>2}),
+%    3 = size(#{a=>1, b=>2, b=>"3"}),
+%    ok.
+
+t_map_size(Config) when is_list(Config) ->
+    0 = map_size(id(#{})),
+    1 = map_size(id(#{a=>1})),
+    1 = map_size(id(#{a=>"wat"})),
+    2 = map_size(id(#{a=>1, b=>2})),
+    3 = map_size(id(#{a=>1, b=>2, b=>"3","33"=><<"n">>})),
+
+    true = map_is_size(#{a=>1}, 1),
+    true = map_is_size(#{a=>1, a=>2}, 1),
+    M = #{ "a" => 1, "b" => 2},
+    true  = map_is_size(M, 2),
+    false = map_is_size(M, 3),
+    true  = map_is_size(M#{ "a" => 2}, 2),
+    false = map_is_size(M#{ "c" => 2}, 2),
+
+    %% Error cases.
+    {'EXIT',{badarg,_}} = (catch map_size([])),
+    {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
+    {'EXIT',{badarg,_}} = (catch map_size(1)),
+    ok.
+
+map_is_size(M,N) when map_size(M) =:= N -> true;
+map_is_size(_,_) -> false.
+
+% test map updates without matching
+t_update_literals(Config) when is_list(Config) ->
+    Map = #{x=>1,y=>2,z=>3,q=>4},
+    #{x:="d",q:="4"} = loop_update_literals_x_q(Map, [
+		{"a","1"},{"b","2"},{"c","3"},{"d","4"}
+	]),
+    ok.
+
+loop_update_literals_x_q(Map, []) -> Map;
+loop_update_literals_x_q(Map, [{X,Q}|Vs]) ->
+    loop_update_literals_x_q(Map#{q=>Q,x=>X},Vs).
+
+% test map updates with matching
+t_match_and_update_literals(Config) when is_list(Config) ->
+    Map = #{x=>0,y=>"untouched",z=>"also untouched",q=>1},
+    #{x:=16,q:=21,y:="untouched",z:="also untouched"} = loop_match_and_update_literals_x_q(Map, [
+	    {1,2},{3,4},{5,6},{7,8}
+	]),
+    M0 = id(#{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	    4 => number, 18446744073709551629 => wat}),
+    M1 = id(#{}),
+    M2 = M1#{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	4 => number, 18446744073709551629 => wat},
+    M0 = M2,
+
+    #{ 4 := another_number, int := 3 } = M2#{ 4 => another_number },
+    ok.
+
+loop_match_and_update_literals_x_q(Map, []) -> Map;
+loop_match_and_update_literals_x_q(#{q:=Q0,x:=X0} = Map, [{X,Q}|Vs]) ->
+    loop_match_and_update_literals_x_q(Map#{q=>Q0+Q,x=>X0+X},Vs).
+
+
+t_update_map_expressions(Config) when is_list(Config) ->
+    M = maps:new(),
+    #{ a := 1 } = M#{a => 1},
+
+    #{ b := 2 } = (maps:new())#{ b => 2 },
+
+    #{ a :=42, b:=42, c:=42 } = (maps:from_list([{a,1},{b,2},{c,3}]))#{ a := 42, b := 42, c := 42 },
+    #{ "a" :=1, "b":=42, "c":=42 } = (maps:from_list([{"a",1},{"b",2}]))#{ "b" := 42, "c" => 42 },
+
+    %% Error cases, FIXME: should be 'badmap'?
+    {'EXIT',{badarg,_}} = (catch (id(<<>>))#{ a := 42, b => 2 }),
+    {'EXIT',{badarg,_}} = (catch (id([]))#{ a := 42, b => 2 }),
+    ok.
+
+
+t_update_assoc(Config) when is_list(Config) ->
+    M0 = id(#{1=>a,2=>b,3.0=>c,4=>d,5=>e}),
+
+    M1 = M0#{1=>42,2=>100,4=>[a,b,c]},
+    #{1:=42,2:=100,3.0:=c,4:=[a,b,c],5:=e} = M1,
+    #{1:=42,2:=b,4:=d,5:=e,2.0:=100,3.0:=c,4.0:=[a,b,c]} = M0#{1.0=>float,1:=42,2.0=>wrong,2.0=>100,4.0=>[a,b,c]},
+
+    M2 = M0#{3.0=>new},
+    #{1:=a,2:=b,3.0:=new,4:=d,5:=e} = M2,
+    M2 = M0#{3.0:=wrong,3.0=>new},
+
+    %% Errors cases.
+    BadMap = id(badmap),
+    {'EXIT',{badarg,_}} = (catch BadMap#{nonexisting=>val}),
+
+    ok.
+
+t_update_exact(Config) when is_list(Config) ->
+    M0 = id(#{1=>a,2=>b,3.0=>c,4=>d,5=>e}),
+
+    M1 = M0#{1:=42,2:=100,4:=[a,b,c]},
+    #{1:=42,2:=100,3.0:=c,4:=[a,b,c],5:=e} = M1,
+    M1 = M0#{1:=wrong,1=>42,2=>wrong,2:=100,4:=[a,b,c]},
+
+    M2 = M0#{3.0:=new},
+    #{1:=a,2:=b,3.0:=new,4:=d,5:=e} = M2,
+    M2 = M0#{3.0=>wrong,3.0:=new},
+    M2 = M0#{3=>wrong,3.0:=new},
+
+    %% Errors cases.
+    {'EXIT',{badarg,_}} = (catch M0#{nonexisting:=val}),
+    {'EXIT',{badarg,_}} = (catch M0#{1.0:=v,1.0=>v2}),
+    {'EXIT',{badarg,_}} = (catch M0#{42.0:=v,42:=v2}),
+    {'EXIT',{badarg,_}} = (catch M0#{42=>v1,42.0:=v2,42:=v3}),
+
+    ok.
+
+t_guard_bifs(Config) when is_list(Config) ->
+    true   = map_guard_head(#{a=>1}),
+    false  = map_guard_head([]),
+    true   = map_guard_body(#{a=>1}),
+    false  = map_guard_body({}),
+    true   = map_guard_pattern(#{a=>1, <<"hi">> => "hi" }),
+    false  = map_guard_pattern("list"),
+    ok.
+
+map_guard_head(M) when is_map(M) -> true;
+map_guard_head(_) -> false.
+
+map_guard_body(M) -> is_map(M).
+
+map_guard_pattern(#{}) -> true;
+map_guard_pattern(_)   -> false.
+
+t_guard_sequence(Config) when is_list(Config) ->
+	{1, "a"} = map_guard_sequence_1(#{seq=>1,val=>id("a")}),
+	{2, "b"} = map_guard_sequence_1(#{seq=>2,val=>id("b")}),
+	{3, "c"} = map_guard_sequence_1(#{seq=>3,val=>id("c")}),
+	{4, "d"} = map_guard_sequence_1(#{seq=>4,val=>id("d")}),
+	{5, "e"} = map_guard_sequence_1(#{seq=>5,val=>id("e")}),
+
+	{1,M1}       = map_guard_sequence_2(M1 = id(#{a=>3})),
+	{2,M2}       = map_guard_sequence_2(M2 = id(#{a=>4, b=>4})),
+	{3,gg,M3}    = map_guard_sequence_2(M3 = id(#{a=>gg, b=>4})),
+	{4,sc,sc,M4} = map_guard_sequence_2(M4 = id(#{a=>sc, b=>3, c=>sc2})),
+	{5,kk,kk,M5} = map_guard_sequence_2(M5 = id(#{a=>kk, b=>other, c=>sc2})),
+	
+	%% error case
+	{'EXIT',{function_clause,_}} = (catch map_guard_sequence_1(#{seq=>6,val=>id("e")})),
+	{'EXIT',{function_clause,_}} = (catch map_guard_sequence_2(#{b=>5})),
+	ok.
+
+map_guard_sequence_1(#{seq:=1=Seq, val:=Val}) -> {Seq,Val};
+map_guard_sequence_1(#{seq:=2=Seq, val:=Val}) -> {Seq,Val};
+map_guard_sequence_1(#{seq:=3=Seq, val:=Val}) -> {Seq,Val};
+map_guard_sequence_1(#{seq:=4=Seq, val:=Val}) -> {Seq,Val};
+map_guard_sequence_1(#{seq:=5=Seq, val:=Val}) -> {Seq,Val}.
+
+map_guard_sequence_2(#{ a:=3 }=M) -> {1, M};
+map_guard_sequence_2(#{ a:=4 }=M) -> {2, M};
+map_guard_sequence_2(#{ a:=X, a:=X, b:=4 }=M) -> {3,X,M};
+map_guard_sequence_2(#{ a:=X, a:=Y, b:=3 }=M) when X =:= Y -> {4,X,Y,M};
+map_guard_sequence_2(#{ a:=X, a:=Y }=M) when X =:= Y -> {5,X,Y,M}.
+
+
+t_guard_update(Config) when is_list(Config) ->
+    error  = map_guard_update(#{},#{}),
+    first  = map_guard_update(#{}, #{x=>first}),
+    second = map_guard_update(#{y=>old}, #{x=>second,y=>old}),
+    ok.
+
+map_guard_update(M1, M2) when M1#{x=>first}  =:= M2 -> first;
+map_guard_update(M1, M2) when M1#{x=>second} =:= M2 -> second;
+map_guard_update(_, _) -> error.
+
+t_guard_receive(Config) when is_list(Config) ->
+    M0  = #{ id => 0 },
+    Pid = spawn_link(fun() -> guard_receive_loop() end),
+    Big = 36893488147419103229,
+    B1  = <<"some text">>,
+    B2  = <<"was appended">>,
+    B3  = <<B1/binary, B2/binary>>,
+
+    #{id:=1, res:=Big} = M1 = call(Pid, M0#{op=>sub,in=>{1 bsl 65, 3}}),
+    #{id:=2, res:=26}  = M2 = call(Pid, M1#{op=>idiv,in=>{53,2}}),
+    #{id:=3, res:=832} = M3 = call(Pid, M2#{op=>imul,in=>{26,32}}),
+    #{id:=4, res:=4}   = M4 = call(Pid, M3#{op=>add,in=>{1,3}}),
+    #{id:=5, res:=Big} = M5 = call(Pid, M4#{op=>sub,in=>{1 bsl 65, 3}}),
+    #{id:=6, res:=B3}  = M6 = call(Pid, M5#{op=>"append",in=>{B1,B2}}),
+    #{id:=7, res:=4}   = _  = call(Pid, M6#{op=>add,in=>{1,3}}),
+
+
+    %% update old maps and check id update
+    #{id:=2, res:=B3} = call(Pid, M1#{op=>"append",in=>{B1,B2}}),
+    #{id:=5, res:=99} = call(Pid, M4#{op=>add,in=>{33, 66}}),
+
+    %% cleanup
+    done = call(Pid, done),
+    ok.
+
+call(Pid, M) ->
+    Pid ! {self(), M}, receive {Pid, Res} -> Res end.
+
+guard_receive_loop() ->
+    receive
+	{Pid, #{ id:=Id, op:="append", in:={X,Y}}=M} when is_binary(X), is_binary(Y) ->
+	    Pid ! {self(), M#{ id=>Id+1, res=><<X/binary,Y/binary>>}},
+	    guard_receive_loop();
+	{Pid, #{ id:=Id, op:=add, in:={X,Y}}} ->
+	    Pid ! {self(), #{ id=>Id+1, res=>X+Y}},
+	    guard_receive_loop();
+	{Pid, #{ id:=Id, op:=sub,  in:={X,Y}}=M} ->
+	    Pid ! {self(), M#{ id=>Id+1, res=>X-Y}},
+	    guard_receive_loop();
+	{Pid, #{ id:=Id, op:=idiv, in:={X,Y}}=M} ->
+	    Pid ! {self(), M#{ id=>Id+1, res=>X div Y}},
+	    guard_receive_loop();
+	{Pid, #{ id:=Id, op:=imul, in:={X,Y}}=M} ->
+	    Pid ! {self(), M#{ id=>Id+1, res=>X * Y}},
+	    guard_receive_loop();
+	{Pid, done} ->
+	    Pid ! {self(), done};
+	{Pid, Other} ->
+	    Pid ! {error, Other},
+	    guard_receive_loop()
+    end.
+
+
+t_list_comprehension(Config) when is_list(Config) ->
+    [#{k:=1},#{k:=2},#{k:=3}] = [#{k=>I} || I <- [1,2,3]],
+    ok.
+
+t_guard_fun(Config) when is_list(Config) ->
+    F1 = fun
+	    (#{s:=v,v:=V})     -> {v,V};
+	    (#{s:=t,v:={V,V}}) -> {t,V};
+	    (#{s:=l,v:=[V,V]}) -> {l,V}
+    end,
+    
+    F2 = fun
+	    (#{s:=T,v:={V,V}}) -> {T,V};
+	    (#{s:=T,v:=[V,V]}) -> {T,V};
+	    (#{s:=T,v:=V})     -> {T,V}
+    end,
+    V = <<"hi">>,
+
+    {v,V} = F1(#{s=>v,v=>V}),
+    {t,V} = F1(#{s=>t,v=>{V,V}}),
+    {l,V} = F1(#{s=>l,v=>[V,V]}),
+
+    {v,V} = F2(#{s=>v,v=>V}),
+    {t,V} = F2(#{s=>t,v=>{V,V}}),
+    {l,V} = F2(#{s=>l,v=>[V,V]}),
+
+    %% error case
+    {'EXIT', {function_clause,[{?MODULE,_,[#{s:=none,v:=none}],_}|_]}} = (catch F1(#{s=>none,v=>none})),
+    ok.
+
+
+t_map_sort_literals(Config) when is_list(Config) ->
+    % test relation
+
+    %% size order
+    true  = #{ a => 1, b => 2} < id(#{ a => 1, b => 1, c => 1}),
+    true  = #{ b => 1, a => 1} < id(#{ c => 1, a => 1, b => 1}),
+    false = #{ c => 1, b => 1, a => 1} < id(#{ c => 1, a => 1}),
+
+    %% key order
+    true  = #{ a => 1 } < id(#{ b => 1}),
+    false = #{ b => 1 } < id(#{ a => 1}),
+    true  = #{ a => 1, b => 1, c => 1 } < id(#{ b => 1, c => 1, d => 1}),
+    true  = #{ b => 1, c => 1, d => 1 } > id(#{ a => 1, b => 1, c => 1}),
+    true  = #{ c => 1, b => 1, a => 1 } < id(#{ b => 1, c => 1, d => 1}),
+    true  = #{ "a" => 1 } < id(#{ <<"a">> => 1}),
+    false = #{ <<"a">> => 1 } < id(#{ "a" => 1}),
+    false = #{ 1 => 1 } < id(#{ 1.0 => 1}),
+    false = #{ 1.0 => 1 } < id(#{ 1 => 1}),
+
+    %% value order
+    true  = #{ a => 1 } < id(#{ a => 2}),
+    false = #{ a => 2 } < id(#{ a => 1}),
+    false = #{ a => 2, b => 1 } < id(#{ a => 1, b => 3}),
+    true  = #{ a => 1, b => 1 } < id(#{ a => 1, b => 3}),
+
+    true  = #{ "a" => "hi", b => 134 } == id(#{ b => 134,"a" => "hi"}),
+
+    %% lists:sort
+
+    SortVs = [#{"a"=>1},#{a=>2},#{1=>3},#{<<"a">>=>4}],
+    [#{1:=ok},#{a:=ok},#{"a":=ok},#{<<"a">>:=ok}] = lists:sort([#{"a"=>ok},#{a=>ok},#{1=>ok},#{<<"a">>=>ok}]),
+    [#{1:=3},#{a:=2},#{"a":=1},#{<<"a">>:=4}] = lists:sort(SortVs),
+    [#{1:=3},#{a:=2},#{"a":=1},#{<<"a">>:=4}] = lists:sort(lists:reverse(SortVs)),
+
+    ok.
+
+%% BIFs
+t_bif_map_get(Config) when is_list(Config) ->
+
+    1    = maps:get(a, #{ a=> 1}),
+    2    = maps:get(b, #{ a=> 1, b => 2}),
+    "hi" = maps:get("hello", #{ a=>1, "hello" => "hi"}),
+    "tuple hi" = maps:get({1,1.0}, #{ a=>a, {1,1.0} => "tuple hi"}),
+
+    M    = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }),
+    "v4" = maps:get(<<"k2">>, M#{ <<"k2">> => "v4" }),
+
+    %% error case
+    {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,[])),
+    {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,<<>>)),
+    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get({1,1}, #{{1,1.0} => "tuple"})),
+    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{})),
+    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{ b=>1, c=>2})),
+    ok.
+
+t_bif_map_find(Config) when is_list(Config) ->
+
+    {ok, 1}     = maps:find(a, #{ a=> 1}),
+    {ok, 2}     = maps:find(b, #{ a=> 1, b => 2}),
+    {ok, "int"} = maps:find(1, #{ 1   => "int"}),
+    {ok, "float"} = maps:find(1.0, #{ 1.0=> "float"}),
+
+    {ok, "hi"} = maps:find("hello", #{ a=>1, "hello" => "hi"}),
+    {ok, "tuple hi"} = maps:find({1,1.0}, #{ a=>a, {1,1.0} => "tuple hi"}),
+
+    M = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }),
+    {ok, "v4"} = maps:find(<<"k2">>, M#{ <<"k2">> => "v4" }),
+
+    %% error case
+    error = maps:find(a,#{}),
+    error = maps:find(a,#{b=>1, c=>2}),
+    error = maps:find(1.0, #{ 1 => "int"}),
+    error = maps:find(1, #{ 1.0  => "float"}),
+    error = maps:find({1.0,1}, #{ a=>a, {1,1.0} => "tuple hi"}), % reverse types in tuple key
+
+
+    {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id([]))),
+    {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id(<<>>))),
+    ok.
+
+
+t_bif_map_is_key(Config) when is_list(Config) ->
+    M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
+
+    true  = maps:is_key("hi", M1),
+    true  = maps:is_key(int, M1),
+    true  = maps:is_key(<<"key">>, M1),
+    true  = maps:is_key(4, M1),
+
+    false = maps:is_key(5, M1),
+    false = maps:is_key(<<"key2">>, M1),
+    false = maps:is_key("h", M1),
+    false = maps:is_key("hello", M1),
+    false = maps:is_key(atom, M1),
+    false = maps:is_key(any, id(#{})),
+
+    false = maps:is_key("hi", maps:remove("hi", M1)),
+    true  = maps:is_key("hi", M1),
+    true  = maps:is_key(1, maps:put(1, "number", M1)),
+    false = maps:is_key(1.0, maps:put(1, "number", M1)),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a,id([]))),
+    {'EXIT',{badarg,[{maps,is_key,_,_}|_]}} = (catch maps:is_key(a,id(<<>>))),
+    ok.
+
+t_bif_map_keys(Config) when is_list(Config) ->
+    [] = maps:keys(#{}),
+
+    [1,2,3,4,5] = maps:keys(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e}),
+    [1,2,3,4,5] = maps:keys(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c}),
+
+    % values in key order: [4,int,"hi",<<"key">>]
+    M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
+    [4,int,"hi",<<"key">>] = maps:keys(M1),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(1 bsl 65 + 3)),
+    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(154)),
+    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(atom)),
+    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys([])),
+    {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(<<>>)),
+    ok.
+
+t_bif_map_new(Config) when is_list(Config) ->
+    #{} = maps:new(),
+    0   = erlang:map_size(maps:new()),
+    ok.
+
+t_bif_map_merge(Config) when is_list(Config) ->
+    0   = erlang:map_size(maps:merge(#{},#{})),
+
+    M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	4 => number, 18446744073709551629 => wat},
+
+    #{ "hi" := "hello", int := 3, <<"key">> := <<"value">>,
+	4 := number, 18446744073709551629 := wat} = maps:merge(#{}, M0),
+
+    #{ "hi" := "hello", int := 3, <<"key">> := <<"value">>,
+	4 := number, 18446744073709551629 := wat} = maps:merge(M0, #{}),
+
+    M1 = #{ "hi" => "hello again", float => 3.3, {1,2} => "tuple", 4 => integer },
+
+    #{4 := number, 18446744073709551629 := wat, float := 3.3, int := 3,
+	{1,2} := "tuple", "hi" := "hello", <<"key">> := <<"value">>} = maps:merge(M1,M0),
+
+    #{4 := integer, 18446744073709551629 := wat, float := 3.3, int := 3,
+	{1,2} := "tuple", "hi" := "hello again", <<"key">> := <<"value">>} = maps:merge(M0,M1),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
+    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),
+    {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(id(#{ a => 2}), <<>> )),
+
+    ok.
+
+
+t_bif_map_put(Config) when is_list(Config) ->
+    M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	4 => number, 18446744073709551629 => wat},
+
+    M1 = #{ "hi" := "hello"} = maps:put("hi", "hello", #{}),
+
+    ["hi"]    = maps:keys(M1),
+    ["hello"] = maps:values(M1),
+
+    M2 = #{ int := 3 } = maps:put(int, 3, M1),
+
+    [int,"hi"]  = maps:keys(M2),
+    [3,"hello"] = maps:values(M2),
+
+    M3 = #{ <<"key">> := <<"value">> } = maps:put(<<"key">>, <<"value">>, M2),
+
+    [int,"hi",<<"key">>]    = maps:keys(M3),
+    [3,"hello",<<"value">>] = maps:values(M3),
+
+    M4 = #{ 18446744073709551629 := wat } = maps:put(18446744073709551629, wat, M3),
+
+    [18446744073709551629,int,"hi",<<"key">>] = maps:keys(M4),
+    [wat,3,"hello",<<"value">>]               = maps:values(M4),
+
+    M0 = #{ 4 := number } = M5 = maps:put(4, number, M4),
+
+    [4,18446744073709551629,int,"hi",<<"key">>] = maps:keys(M5),
+    [number,wat,3,"hello",<<"value">>]          = maps:values(M5),
+
+    M6 = #{ <<"key">> := <<"other value">> } = maps:put(<<"key">>, <<"other value">>, M5),
+
+    [4,18446744073709551629,int,"hi",<<"key">>] = maps:keys(M6),
+    [number,wat,3,"hello",<<"other value">>]    = maps:values(M6),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,1 bsl 65 + 3)),
+    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,154)),
+    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,atom)),
+    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,[])),
+    {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,<<>>)),
+     ok.
+
+t_bif_map_remove(Config) when is_list(Config) ->
+    0  = erlang:map_size(maps:remove(some_key, #{})),
+
+    M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	4 => number, 18446744073709551629 => wat},
+
+    M1 = maps:remove("hi", M0),
+    [4,18446744073709551629,int,<<"key">>] = maps:keys(M1),
+    [number,wat,3,<<"value">>]             = maps:values(M1),
+
+    M2 = maps:remove(int, M1),
+    [4,18446744073709551629,<<"key">>] = maps:keys(M2),
+    [number,wat,<<"value">>]           = maps:values(M2),
+
+    M3 = maps:remove(<<"key">>, M2),
+    [4,18446744073709551629] = maps:keys(M3),
+    [number,wat]             = maps:values(M3),
+
+    M4 = maps:remove(18446744073709551629, M3),
+    [4]      = maps:keys(M4),
+    [number] = maps:values(M4),
+
+    M5 = maps:remove(4, M4),
+    [] = maps:keys(M5),
+    [] = maps:values(M5),
+
+    M0 = maps:remove(5,M0),
+    M0 = maps:remove("hi there",M0),
+
+    #{ "hi" := "hello", int := 3, 4 := number} = maps:remove(18446744073709551629,maps:remove(<<"key">>,M0)),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,1 bsl 65 + 3)),
+    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(1,154)),
+    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,atom)),
+    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(1,[])),
+    {'EXIT',{badarg,[{maps,remove,_,_}|_]}} = (catch maps:remove(a,<<>>)),
+     ok.
+
+t_bif_map_update(Config) when is_list(Config) ->
+    M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
+	4 => number, 18446744073709551629 => wat},
+
+    #{ "hi" := "hello again", int := 3, <<"key">> := <<"value">>,
+	4 := number, 18446744073709551629 := wat} = maps:update("hi", "hello again", M0),
+
+    #{ "hi" := "hello", int := 1337, <<"key">> := <<"value">>,
+	4 := number, 18446744073709551629 := wat} = maps:update(int, 1337, M0),
+
+    #{ "hi" := "hello", int := 3, <<"key">> := <<"new value">>,
+	4 := number, 18446744073709551629 := wat} = maps:update(<<"key">>, <<"new value">>, M0),
+
+    #{ "hi" := "hello", int := 3, <<"key">> := <<"value">>,
+	4 := integer, 18446744073709551629 := wat} = maps:update(4, integer, M0),
+
+    #{ "hi" := "hello", int := 3, <<"key">> := <<"value">>,
+	4 := number, 18446744073709551629 := wazzup} = maps:update(18446744073709551629, wazzup, M0),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(1,none,{})),
+    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(1,none,<<"value">>)),
+    {'EXIT',{badarg,[{maps,update,_,_}|_]}} = (catch maps:update(5,none,M0)),
+
+    ok.
+
+
+
+t_bif_map_values(Config) when is_list(Config) ->
+
+    [] = maps:values(#{}),
+
+    [a,b,c,d,e] = maps:values(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e}),
+    [a,b,c,d,e] = maps:values(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c}),
+
+    % values in key order: [4,int,"hi",<<"key">>]
+    M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
+    M2 = M1#{ "hi" => "hello2", <<"key">> => <<"value2">> },
+    [number,3,"hello2",<<"value2">>] = maps:values(M2),
+    [number,3,"hello",<<"value">>]   = maps:values(M1),
+
+    %% error case
+    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(1 bsl 65 + 3)),
+    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(atom)),
+    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values([])),
+    {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(<<>>)),
+    ok.
+
+t_erlang_hash(Config) when is_list(Config) ->
+
+    ok = t_bif_erlang_phash2(),
+    ok = t_bif_erlang_phash(),
+    ok = t_bif_erlang_hash(),
+
+    ok.
+
+t_bif_erlang_phash2() ->
+
+    39679005 = erlang:phash2(#{}),
+    78942764 = erlang:phash2(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 }),
+    37338230 = erlang:phash2(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} }),
+    14363616 = erlang:phash2(#{ 1 => a }),
+    51612236 = erlang:phash2(#{ a => 1 }),
+
+    37468437 = erlang:phash2(#{{} => <<>>}),
+    44049159 = erlang:phash2(#{<<>> => {}}),
+
+    M0 = #{ a => 1, "key" => <<"value">> },
+    M1 = maps:remove("key",M0),
+    M2 = M1#{ "key" => <<"value">> },
+
+    118679416 = erlang:phash2(M0),
+    51612236  = erlang:phash2(M1),
+    118679416 = erlang:phash2(M2),
+    ok.
+
+t_bif_erlang_phash() ->
+    Sz = 1 bsl 32,
+    268440612  = erlang:phash(#{},Sz),
+    1196461908 = erlang:phash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz),
+    3944426064 = erlang:phash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz),
+    1394238263 = erlang:phash(#{ 1 => a },Sz),
+    4066388227 = erlang:phash(#{ a => 1 },Sz),
+
+    1578050717 = erlang:phash(#{{} => <<>>},Sz),
+    1578050717 = erlang:phash(#{<<>> => {}},Sz), % yep, broken
+
+    M0 = #{ a => 1, "key" => <<"value">> },
+    M1 = maps:remove("key",M0),
+    M2 = M1#{ "key" => <<"value">> },
+
+    3590546636 = erlang:phash(M0,Sz),
+    4066388227 = erlang:phash(M1,Sz),
+    3590546636 = erlang:phash(M2,Sz),
+    ok.
+
+t_bif_erlang_hash() ->
+    Sz = 1 bsl 27 - 1,
+    5158      = erlang:hash(#{},Sz),
+    71555838  = erlang:hash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz),
+    5497225   = erlang:hash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz),
+    126071654 = erlang:hash(#{ 1 => a },Sz),
+    126426236 = erlang:hash(#{ a => 1 },Sz),
+
+    101655720 = erlang:hash(#{{} => <<>>},Sz),
+    101655720 = erlang:hash(#{<<>> => {}},Sz), % yep, broken
+
+    M0 = #{ a => 1, "key" => <<"value">> },
+    M1 = maps:remove("key",M0),
+    M2 = M1#{ "key" => <<"value">> },
+
+    38260486  = erlang:hash(M0,Sz),
+    126426236 = erlang:hash(M1,Sz),
+    38260486  = erlang:hash(M2,Sz),
+    ok.
+
+
+t_map_encode_decode(Config) when is_list(Config) ->
+    <<131,116,0,0,0,0>> = erlang:term_to_binary(#{}),
+    Pairs = [
+	{a,b},{"key","values"},{<<"key">>,<<"value">>},
+	{1,b},{[atom,1],{<<"wat">>,1,2,3}},
+	{aa,"values"},
+	{1 bsl 64 + (1 bsl 50 - 1), sc1},
+	{99, sc2},
+	{1 bsl 65 + (1 bsl 51 - 1), sc3},
+	{88, sc4},
+	{1 bsl 66 + (1 bsl 52 - 1), sc5},
+	{77, sc6},
+	{1 bsl 67 + (1 bsl 53 - 1), sc3},
+	{75, sc6}, {-10,sc8},
+	{<<>>, sc9}, {3.14158, sc10},
+	{[3.14158], sc11}, {more_atoms, sc12},
+	{{more_tuples}, sc13}, {self(), sc14},
+	{{},{}},{[],[]}
+    ],
+    ok = map_encode_decode_and_match(Pairs,[],#{}),
+
+    %% check sorting
+
+    %% literally #{ b=>2, a=>1 } in the internal order
+    #{ a:=1, b:=2 } =
+	erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,100,0,1,97,97,2,97,1>>),
+
+
+    %% literally #{ "hi" => "value", a=>33, b=>55 } in the internal order
+    #{ a:=33, b:=55, "hi" := "value"} = erlang:binary_to_term(<<131,116,0,0,0,3,
+	107,0,2,104,105, % "hi" :: list()
+	100,0,1,97, % a :: atom()
+	100,0,1,98, % b :: atom()
+	107,0,5,118,97,108,117,101, % "value" :: list()
+	97,33, % 33 :: integer()
+	97,55  % 55 :: integer()
+	>>),
+
+
+    %% error cases
+    %% template: <<131,116,0,0,0,2,100,0,1,97,100,0,1,98,97,1,97,1>>
+    %% which is: #{ a=>1, b=>1 }
+
+    %% uniqueness violation
+    %% literally #{ a=>1, "hi"=>"value", a=>2 }
+    {'EXIT',{badarg,[{_,_,_,_}|_]}} = (catch
+	erlang:binary_to_term(<<131,116,0,0,0,3,100,0,1,97,107,0,2,104,105,100,0,1,97,97,1,107,0,5,118,97,108,117,101,97,2>>)),
+
+    %% bad size (too large)
+    {'EXIT',{badarg,[{_,_,_,_}|_]}} = (catch
+	erlang:binary_to_term(<<131,116,0,0,0,12,100,0,1,97,100,0,1,98,97,1,97,1>>)),
+
+    %% bad size (too small) .. should fail just truncate it .. weird.
+    %% possibly change external format so truncated will be #{a:=1}
+    #{ a:=b } =
+	erlang:binary_to_term(<<131,116,0,0,0,1,100,0,1,97,100,0,1,98,97,1,97,1>>),
+
+    ok.
+
+map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, M0) ->
+    M1 = maps:put(K,V,M0),
+    B0 = erlang:term_to_binary(M1),
+    Ls = lists:sort(fun(A,B) -> erts_internal:cmp_term(A,B) < 0 end, [{K, erlang:term_to_binary(K), erlang:term_to_binary(V)}|EncodedPairs]),
+    %% sort Ks and Vs according to term spec, then match it
+    ok = match_encoded_map(B0, length(Ls), [Kbin||{_,Kbin,_}<-Ls] ++ [Vbin||{_,_,Vbin}<-Ls]),
+    %% decode and match it
+    M1 = erlang:binary_to_term(B0),
+    map_encode_decode_and_match(Pairs,Ls,M1);
+map_encode_decode_and_match([],_,_) -> ok.
+
+match_encoded_map(<<131,116,Size:32,Encoded/binary>>,Size,Items) ->
+    match_encoded_map(Encoded,Items);
+match_encoded_map(_,_,_) -> no_match_size.
+
+match_encoded_map(<<>>,[]) -> ok;
+match_encoded_map(Bin,[<<131,Item/binary>>|Items]) ->
+    Size = erlang:byte_size(Item),
+    <<EncodedTerm:Size/binary, Bin1/binary>> = Bin,
+    EncodedTerm = Item, %% Asssert
+    match_encoded_map(Bin1,Items).
+
+
+t_bif_map_to_list(Config) when is_list(Config) ->
+    [] = maps:to_list(#{}),
+    [{a,1},{b,2}] = maps:to_list(#{a=>1,b=>2}),
+    [{a,1},{b,2},{c,3}] = maps:to_list(#{c=>3,a=>1,b=>2}),
+    [{a,1},{b,2},{g,3}] = maps:to_list(#{g=>3,a=>1,b=>2}),
+    [{a,1},{b,2},{g,3},{"c",4}] = maps:to_list(#{g=>3,a=>1,b=>2,"c"=>4}),
+    [{3,v2},{hi,v4},{{hi,3},v5},{"hi",v3},{<<"hi">>,v1}] = maps:to_list(#{
+	    <<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5}),
+
+    [{3,v7},{hi,v9},{{hi,3},v10},{"hi",v8},{<<"hi">>,v6}] = maps:to_list(#{
+	    <<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5,
+	    <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10}),
+
+    %% error cases
+    {'EXIT', {badarg,_}} = (catch maps:to_list(id(a))),
+    {'EXIT', {badarg,_}} = (catch maps:to_list(id(42))),
+    ok.
+
+
+t_bif_map_from_list(Config) when is_list(Config) ->
+    #{} = maps:from_list([]),
+    A   = maps:from_list([]),
+    0   = erlang:map_size(A),
+
+    #{a:=1,b:=2}  = maps:from_list([{a,1},{b,2}]),
+    #{c:=3,a:=1,b:=2} = maps:from_list([{a,1},{b,2},{c,3}]),
+    #{g:=3,a:=1,b:=2} = maps:from_list([{a,1},{b,2},{g,3}]),
+
+    #{a:=2} = maps:from_list([{a,1},{a,3},{a,2}]),
+
+    #{ <<"hi">>:=v1,3:=v3,"hi":=v6,hi:=v4,{hi,3}:=v5} =
+	maps:from_list([{3,v3},{"hi",v6},{hi,v4},{{hi,3},v5},{<<"hi">>,v1}]),
+
+    #{<<"hi">>:=v6,3:=v8,"hi":=v11,hi:=v9,{hi,3}:=v10} =
+	maps:from_list([ {{hi,3},v3}, {"hi",v0},{3,v1}, {<<"hi">>,v4}, {hi,v2},
+	    {<<"hi">>,v6}, {{hi,3},v10},{"hi",v11}, {hi,v9}, {3,v8}]),
+
+    %% error cases
+    {'EXIT', {badarg,_}} = (catch maps:from_list(id([{a,b},b]))),
+    {'EXIT', {badarg,_}} = (catch maps:from_list(id([{a,b},{b,b,3}]))),
+    {'EXIT', {badarg,_}} = (catch maps:from_list(id([{a,b},<<>>]))),
+    {'EXIT', {badarg,_}} = (catch maps:from_list(id([{a,b}|{b,a}]))),
+    {'EXIT', {badarg,_}} = (catch maps:from_list(id(a))),
+    {'EXIT', {badarg,_}} = (catch maps:from_list(id(42))),
+    ok.
+
+%% Maps module, not BIFs
+t_maps_fold(_Config) ->
+    Vs = lists:seq(1,100),
+    M  = maps:from_list([{{k,I},{v,I}}||I<-Vs]),
+
+    %% fold
+    5050 = maps:fold(fun({k,_},{v,V},A) -> V + A end, 0, M),
+
+    ok.
+
+t_maps_map(_Config) ->
+    Vs = lists:seq(1,100),
+    M1 = maps:from_list([{I,I}||I<-Vs]),
+    M2 = maps:from_list([{I,{token,I}}||I<-Vs]),
+
+    M2 = maps:map(fun(_K,V) -> {token,V} end, M1),
+    ok.
+
+t_maps_size(_Config) ->
+    Vs = lists:seq(1,100),
+    lists:foldl(fun(I,M) ->
+		M1 = maps:put(I,I,M),
+		I  = maps:size(M1),
+		M1
+	end, #{}, Vs),
+    ok.
+
+
+t_maps_without(_Config) ->
+    Ki = [11,22,33,44,55,66,77,88,99],
+    M0 = maps:from_list([{{k,I},{v,I}}||I<-lists:seq(1,100)]),
+    M1 = maps:from_list([{{k,I},{v,I}}||I<-lists:seq(1,100) -- Ki]),
+    M1 = maps:without([{k,I}||I <- Ki],M0),
+    ok.
+
+
+%% MISC
+t_pdict(_Config) ->
+
+    put(#{ a => b, b => a},#{ c => d}),
+    put(get(#{ a => b, b => a}),1),
+    1 = get(#{ c => d}),
+    #{ c := d } = get(#{ a => b, b => a}).
+
+t_ets(_Config) ->
+
+    Tid = ets:new(map_table,[]),
+
+    [ets:insert(Tid,{maps:from_list([{I,-I}]),I}) || I <- lists:seq(1,100)],
+
+
+    [{#{ 2 := -2},2}] = ets:lookup(Tid,#{ 2 => -2 }),
+
+    %% Test equal
+    [3,4] = lists:sort(
+	      ets:select(Tid,[{{'$1','$2'},
+			       [{'or',{'==','$1',#{ 3 => -3 }},
+				 {'==','$1',#{ 4 => -4 }}}],
+			       ['$2']}])),
+    %% Test match
+    [30,50] = lists:sort(
+		ets:select(Tid,
+			   [{{#{ 30 => -30}, '$1'},[],['$1']},
+			    {{#{ 50 => -50}, '$1'},[],['$1']}]
+			  )),
+
+    ets:insert(Tid,{#{ a => b, b => c, c => a},transitivity}),
+
+    %% Test equal with map of different size
+    [] = ets:select(Tid,[{{'$1','_'},[{'==','$1',#{ b => c }}],['$_']}]),
+
+    %% Test match with map of different size
+    %[{#{ a := b },_}] = ets:select(Tid,[{{#{ b => c },'_'},[],['$_']}]),
+
+    %%% Test match with don't care value
+    %[{#{ a := b },_}] = ets:select(Tid,[{{#{ b => '_' },'_'},[],['$_']}]),
+
+    %% Test is_map bif
+    101 = length(ets:select(Tid,[{'$1',[{is_map,{element,1,'$1'}}],['$1']}])),
+    ets:insert(Tid,{not_a_map,2}),
+    101 = length(ets:select(Tid,[{'$1',[{is_map,{element,1,'$1'}}],['$1']}])),
+    ets:insert(Tid,{{nope,a,tuple},2}),
+    101 = length(ets:select(Tid,[{'$1',[{is_map,{element,1,'$1'}}],['$1']}])),
+
+    %% Test map_size bif
+    [3] = ets:select(Tid,[{{'$1','_'},[{'==',{map_size,'$1'},3}],
+			   [{map_size,'$1'}]}]),
+
+    true = ets:delete(Tid,#{50 => -50}),
+    [] = ets:lookup(Tid,#{50 => -50}),
+
+    ets:delete(Tid),
+    ok.
+
+t_dets(_Config) ->
+    ok.
+
+t_tracing(_Config) ->
+
+    dbg:stop_clear(),
+    {ok,Tracer} = dbg:tracer(process,{fun trace_collector/2, self()}),
+    dbg:p(self(),c),
+
+    %% Test basic map call
+    {ok,_} = dbg:tpl(?MODULE,id,x),
+    id(#{ a => b }),
+    {trace,_,call,{?MODULE,id,[#{ a := b }]}} = getmsg(Tracer),
+    {trace,_,return_from,{?MODULE,id,1},#{ a := b }} = getmsg(Tracer),
+    dbg:ctpl(),
+
+    %% Test equals in argument list
+    {ok,_} = dbg:tpl(?MODULE,id,[{['$1'],[{'==','$1',#{ b => c}}],
+				  [{return_trace}]}]),
+    id(#{ a => b }),
+    id(#{ b => c }),
+    {trace,_,call,{?MODULE,id,[#{ b := c }]}} = getmsg(Tracer),
+    {trace,_,return_from,{?MODULE,id,1},#{ b := c }} = getmsg(Tracer),
+    dbg:ctpl(),
+
+    %% Test match in head
+    {ok,_} = dbg:tpl(?MODULE,id,[{[#{b => c}],[],[]}]),
+    id(#{ a => b }),
+    id(#{ b => c }),
+    {trace,_,call,{?MODULE,id,[#{ b := c }]}} = getmsg(Tracer),
+    dbg:ctpl(),
+
+    % Test map guard bifs
+    {ok,_} = dbg:tpl(?MODULE,id,[{['$1'],[{is_map,{element,1,'$1'}}],[]}]),
+    id(#{ a => b }),
+    id({1,2}),
+    id({#{ a => b},2}),
+    {trace,_,call,{?MODULE,id,[{#{ a := b },2}]}} = getmsg(Tracer),
+    dbg:ctpl(),
+
+    {ok,_} = dbg:tpl(?MODULE,id,[{['$1'],[{'==',{map_size,{element,1,'$1'}},2}],[]}]),
+    id(#{ a => b }),
+    id({1,2}),
+    id({#{ a => b},2}),
+    id({#{ a => b, b => c},atom}),
+    {trace,_,call,{?MODULE,id,[{#{ a := b, b := c },atom}]}} = getmsg(Tracer),
+    dbg:ctpl(),
+
+    %MS = dbg:fun2ms(fun([A]) when A == #{ a => b} -> ok end),
+    %dbg:tpl(?MODULE,id,MS),
+    %id(#{ a => b }),
+    %id(#{ b => c }),
+    %{trace,_,call,{?MODULE,id,[#{ a := b }]}} = getmsg(Tracer),
+    %dbg:ctpl(),
+
+    %% Check to extra messages
+    timeout = getmsg(Tracer),
+
+    dbg:stop_clear(),
+    ok.
+
+getmsg(_Tracer) ->
+    receive V -> V after 100 -> timeout end.
+
+trace_collector(Msg,Parent) ->
+    io:format("~p~n",[Msg]),
+    Parent ! Msg,
+    Parent.
+
+%% Use this function to avoid compile-time evaluation of an expression.
+id(I) -> I.
diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl
index affb66289b..bcc1f9e5af 100644
--- a/erts/emulator/test/nif_SUITE.erl
+++ b/erts/emulator/test/nif_SUITE.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %%
-%% Copyright Ericsson AB 2010-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2010-2014. All Rights Reserved.
 %%
 %% The contents of this file are subject to the Erlang Public License,
 %% Version 1.1, (the "License"); you may not use this file except in
@@ -29,7 +29,8 @@
 	 init_per_group/2,end_per_group/2, 
 	 init_per_testcase/2, 
 	 end_per_testcase/2, basic/1, reload/1, upgrade/1, heap_frag/1,
-	 types/1, many_args/1, binaries/1, get_string/1, get_atom/1, 
+	 types/1, many_args/1, binaries/1, get_string/1, get_atom/1,
+	 maps/1,
 	 api_macros/1,
 	 from_array/1, iolist_as_binary/1, resource/1, resource_binary/1, 
 	 resource_takeover/1,
@@ -58,7 +59,7 @@ suite() -> [{ct_hooks,[ts_install_cth]}].
 
 all() -> 
     [basic, reload, upgrade, heap_frag, types, many_args,
-     binaries, get_string, get_atom, api_macros, from_array,
+     binaries, get_string, get_atom, maps, api_macros, from_array,
      iolist_as_binary, resource, resource_binary,
      resource_takeover, threading, send, send2, send3,
      send_threaded, neg, is_checks, get_length, make_atom,
@@ -435,6 +436,54 @@ get_atom(Config) when is_list(Config) ->
     ?line {0, <<>>} = atom_to_bin('',0),
     ok.
 
+maps(doc) -> ["Test NIF maps handling."];
+maps(suite) -> [];
+maps(Config) when is_list(Config) ->
+    TmpMem = tmpmem(),
+    Pairs = [{adam, "bert"}] ++
+            [{I,I}||I <- lists:seq(1,10)] ++
+	    [{a,value},{"a","value"},{<<"a">>,<<"value">>}],
+    ok = ensure_lib_loaded(Config, 1),
+    M  = maps_from_list_nif(Pairs),
+    R = {RIs,Is} = sorted_list_from_maps_nif(M),
+    io:format("Pairs: ~p~nMap: ~p~nReturned: ~p~n", [lists:sort(Pairs),M,R]),
+    Is = lists:sort(Pairs),
+    Is = lists:reverse(RIs),
+
+    #{} = maps_from_list_nif([]),
+    {[],[]} = sorted_list_from_maps_nif(#{}),
+
+    1 = is_map_nif(M),
+    0 = is_map_nif("no map"),
+
+    Msz = map_size(M),
+    {1,Msz} = get_map_size_nif(M),
+    {1,0} = get_map_size_nif(#{}),
+    {0,-123} = get_map_size_nif({#{}}),
+
+    #{} = M0 = make_new_map_nif(),
+
+    {1, #{key := value}=M1} = make_map_put_nif(M0, key, value),
+    {1, #{key := value, "key2" := "value2"}=M2} = make_map_put_nif(M1, "key2", "value2"),
+    {1, #{key := "value", "key2" := "value2"}=M3} = make_map_put_nif(M2, key, "value"),
+    {0, undefined} = make_map_put_nif(666, key, value),
+
+    {1, "value2"} = get_map_value_nif(M3,"key2"),
+    {0, undefined} = get_map_value_nif(M3,"key3"),
+    {0, undefined} = get_map_value_nif(false,key),
+
+    {0, undefined} = make_map_update_nif(M0, key, value),
+    {0, undefined} = make_map_update_nif(M1, "key2", "value2"),
+    {1, #{key := "value", "key2" := "value2"}} = make_map_update_nif(M2, key, "value"),
+    {0, undefined} = make_map_update_nif(666, key, value),
+
+    {1, #{}} = make_map_remove_nif(M1, key),
+    {1, M1} = make_map_remove_nif(M2, "key2"),
+    {1, M2} = make_map_remove_nif(M2, "key3"),
+    {0, undefined} = make_map_remove_nif(self(), key),
+
+    ok.
+ 
 api_macros(doc) -> ["Test macros enif_make_list<N> and enif_make_tuple<N>"];
 api_macros(suite) -> [];
 api_macros(Config) when is_list(Config) ->
@@ -1488,5 +1537,17 @@ otp_9668_nif(_) -> ?nif_stub.
 consume_timeslice_nif(_,_) -> ?nif_stub.
 call_dirty_nif(_,_,_) -> ?nif_stub.
 
+%% maps
+is_map_nif(_) -> ?nif_stub.
+get_map_size_nif(_) -> ?nif_stub.
+make_new_map_nif() -> ?nif_stub.
+make_map_put_nif(_,_,_) -> ?nif_stub.
+get_map_value_nif(_,_) -> ?nif_stub.
+make_map_update_nif(_,_,_) -> ?nif_stub.
+make_map_remove_nif(_,_) -> ?nif_stub.
+maps_from_list_nif(_) -> ?nif_stub.
+sorted_list_from_maps_nif(_) -> ?nif_stub.
+
+
 nif_stub_error(Line) ->
     exit({nif_not_loaded,module,?MODULE,line,Line}).
diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c
index 6f902e186d..b550d1f16d 100644
--- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c
+++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  *
- * Copyright Ericsson AB 2009-2013. All Rights Reserved.
+ * Copyright Ericsson AB 2009-2014. All Rights Reserved.
  *
  * The contents of this file are subject to the Erlang Public License,
  * Version 1.1, (the "License"); you may not use this file except in
@@ -1536,6 +1536,132 @@ static ERL_NIF_TERM call_dirty_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM
 }
 #endif
 
+static ERL_NIF_TERM is_map_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    return enif_make_int(env, enif_is_map(env,argv[0]));
+}
+static ERL_NIF_TERM get_map_size_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    size_t size = (size_t)-123;
+    int ret = enif_get_map_size(env, argv[0], &size);
+    return enif_make_tuple2(env, enif_make_int(env, ret), enif_make_int(env, (int)size));
+}
+static ERL_NIF_TERM make_new_map_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    return enif_make_new_map(env);
+}
+static ERL_NIF_TERM make_map_put_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    ERL_NIF_TERM map_out = enif_make_atom(env, "undefined");
+    int ret = enif_make_map_put(env, argv[0], argv[1], argv[2], &map_out);
+    return enif_make_tuple2(env, enif_make_int(env,ret), map_out);
+}
+static ERL_NIF_TERM get_map_value_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    ERL_NIF_TERM value = enif_make_atom(env, "undefined");
+    int ret = enif_get_map_value(env, argv[0], argv[1], &value);
+    return enif_make_tuple2(env, enif_make_int(env,ret), value);
+
+}
+static ERL_NIF_TERM make_map_update_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    ERL_NIF_TERM map_out = enif_make_atom(env, "undefined");
+    int ret = enif_make_map_update(env, argv[0], argv[1], argv[2], &map_out);
+    return enif_make_tuple2(env, enif_make_int(env,ret), map_out);
+}
+static ERL_NIF_TERM make_map_remove_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    ERL_NIF_TERM map_out = enif_make_atom(env, "undefined");
+    int ret = enif_make_map_remove(env, argv[0], argv[1], &map_out);
+    return enif_make_tuple2(env, enif_make_int(env,ret), map_out);
+}
+
+/* maps */
+static ERL_NIF_TERM maps_from_list_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+    ERL_NIF_TERM cell = argv[0];
+    ERL_NIF_TERM map  = enif_make_new_map(env);
+    ERL_NIF_TERM tuple;
+    const ERL_NIF_TERM *pair;
+    int arity = -1;
+
+    if (argc != 1 && !enif_is_list(env, cell)) return enif_make_badarg(env);
+
+    /* assume sorted keys */
+
+    while (!enif_is_empty_list(env,cell)) {
+	if (!enif_get_list_cell(env, cell, &tuple, &cell)) return enif_make_badarg(env);
+	if (enif_get_tuple(env,tuple,&arity,&pair)) {
+	    enif_make_map_put(env, map, pair[0], pair[1], &map);
+	}
+    }
+
+    return map;
+}
+
+static ERL_NIF_TERM sorted_list_from_maps_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
+
+    ERL_NIF_TERM map = argv[0];
+    ERL_NIF_TERM list_f = enif_make_list(env, 0); /* NIL */
+    ERL_NIF_TERM list_b = enif_make_list(env, 0); /* NIL */
+    ERL_NIF_TERM key, value, k2, v2;
+    ErlNifMapIterator iter_f;
+    ErlNifMapIterator iter_b;
+    int cnt, next_ret, prev_ret;
+
+    if (argc != 1 && !enif_is_map(env, map))
+	return enif_make_int(env, __LINE__);
+
+    if(!enif_map_iterator_create(env, map, &iter_f, ERL_NIF_MAP_ITERATOR_HEAD))
+	return enif_make_int(env, __LINE__);
+
+    cnt = 0;
+    while(enif_map_iterator_get_pair(env,&iter_f,&key,&value)) {
+	if (cnt && !next_ret)
+	    return enif_make_int(env, __LINE__);
+	list_f = enif_make_list_cell(env, enif_make_tuple2(env, key, value), list_f);
+	next_ret = enif_map_iterator_next(env,&iter_f);
+	cnt++;
+    }
+    if (cnt && next_ret)
+	return enif_make_int(env, __LINE__);
+
+    if(!enif_map_iterator_create(env, map, &iter_b, ERL_NIF_MAP_ITERATOR_TAIL))
+	return enif_make_int(env, __LINE__);
+
+    cnt = 0;
+    while(enif_map_iterator_get_pair(env,&iter_b,&key,&value)) {
+	if (cnt && !prev_ret)
+	    return enif_make_int(env, __LINE__);
+
+	/* Test that iter_f can step "backwards" */
+	if (!enif_map_iterator_prev(env,&iter_f)
+	    || !enif_map_iterator_get_pair(env,&iter_f,&k2,&v2)
+	    || k2 != key || v2 != value) {
+	    return enif_make_int(env, __LINE__);
+	}
+
+	list_b = enif_make_list_cell(env, enif_make_tuple2(env, key, value), list_b);
+	prev_ret = enif_map_iterator_prev(env,&iter_b);
+    }
+
+    if (cnt) {
+	if (prev_ret || enif_map_iterator_prev(env,&iter_f))
+	    return enif_make_int(env, __LINE__);
+
+	/* Test that iter_b can step "backwards" one step */
+	if (!enif_map_iterator_next(env, &iter_b)
+	    || !enif_map_iterator_get_pair(env,&iter_b,&k2,&v2)
+	    || k2 != key || v2 != value)
+	    return enif_make_int(env, __LINE__);
+    }
+
+    enif_map_iterator_destroy(env, &iter_f);
+    enif_map_iterator_destroy(env, &iter_b);
+
+    return enif_make_tuple2(env, list_f, list_b);
+}
+
 static ErlNifFunc nif_funcs[] =
 {
     {"lib_version", 0, lib_version},
@@ -1589,6 +1715,15 @@ static ErlNifFunc nif_funcs[] =
 #ifdef ERL_NIF_DIRTY_SCHEDULER_SUPPORT
     {"call_dirty_nif", 3, call_dirty_nif},
 #endif
+    {"is_map_nif", 1, is_map_nif},
+    {"get_map_size_nif", 1, get_map_size_nif},
+    {"make_new_map_nif", 0, make_new_map_nif},
+    {"make_map_put_nif", 3, make_map_put_nif},
+    {"get_map_value_nif", 2, get_map_value_nif},
+    {"make_map_update_nif", 3, make_map_update_nif},
+    {"make_map_remove_nif", 2, make_map_remove_nif},
+    {"maps_from_list_nif", 1, maps_from_list_nif},
+    {"sorted_list_from_maps_nif", 1, sorted_list_from_maps_nif}
 };
 
 ERL_NIF_INIT(nif_SUITE,nif_funcs,load,reload,upgrade,unload)
diff --git a/erts/emulator/test/send_term_SUITE.erl b/erts/emulator/test/send_term_SUITE.erl
index b631f55a03..8e1f8df43a 100644
--- a/erts/emulator/test/send_term_SUITE.erl
+++ b/erts/emulator/test/send_term_SUITE.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %% 
-%% Copyright Ericsson AB 2005-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2005-2014. All Rights Reserved.
 %% 
 %% The contents of this file are subject to the Erlang Public License,
 %% Version 1.1, (the "License"); you may not use this file except in
@@ -62,7 +62,19 @@ basic(Config) when is_list(Config) ->
 
     ?line [] = term(P, 0),
     ?line Self = self(),
-    ?line {blurf,42,[],[-42,{}|"abc"++P],"kalle",3.1416,Self} = term(P, 1),
+    {blurf,42,[],[-42,{}|"abc"++P],"kalle",3.1416,Self,#{}} = term(P, 1),
+
+    Map41 = maps:from_list([{blurf, 42},
+			    {[], [-42,{}|"abc"++P]},
+			    {"kalle", 3.1416},
+			    {Self, #{}}]),
+    Map41 = term(P, 41),
+
+    Map42 = maps:from_list([{42, []},
+			    {[-42,{}|"abc"++P], "kalle"},
+			    {3.1416, Self},
+			    {#{}, blurf}]),
+    Map42 = term(P, 42),
     ?line Deep = lists:seq(0, 199),
     ?line Deep = term(P, 2),
     ?line {B1,B2} = term(P, 3),
@@ -125,7 +137,8 @@ basic(Config) when is_list(Config) ->
                {-1, 36}, % ERL_DRV_INT64
                {-4711, 37}, % ERL_DRV_INT64
                {-20233590931456, 38}, % ERL_DRV_INT64
-               {-9223372036854775808, 39}], % ERL_DRV_INT64
+               {-9223372036854775808, 39},
+	       {#{}, 40}], % ERL_DRV_MAP
     ?line {Terms, Ops} = lists:unzip(Singles),
     ?line Terms = term(P,Ops),
 
diff --git a/erts/emulator/test/send_term_SUITE_data/send_term_drv.c b/erts/emulator/test/send_term_SUITE_data/send_term_drv.c
index f8613487b0..381a4f20d5 100644
--- a/erts/emulator/test/send_term_SUITE_data/send_term_drv.c
+++ b/erts/emulator/test/send_term_SUITE_data/send_term_drv.c
@@ -104,7 +104,7 @@ static void send_term_drv_run(ErlDrvData port, char *buf, ErlDrvSizeT count)
 	    double f = 3.1416;
 
 	    msg[0] = ERL_DRV_ATOM;
-	    msg[1] = driver_mk_atom("blurf"),
+	    msg[1] = driver_mk_atom("blurf");
 	    msg[2] = ERL_DRV_INT;
 	    msg[3] = (ErlDrvTermData) 42;
 	    msg[4] = ERL_DRV_NIL;
@@ -126,9 +126,11 @@ static void send_term_drv_run(ErlDrvData port, char *buf, ErlDrvSizeT count)
 	    msg[20] = (ErlDrvTermData) &f;
 	    msg[21] = ERL_DRV_PID;
 	    msg[22] = driver_connected(erlang_port);
-	    msg[23] = ERL_DRV_TUPLE;
-	    msg[24] = (ErlDrvTermData) 7;
-	    msg += 25;
+	    msg[23] = ERL_DRV_MAP;
+	    msg[24] = (ErlDrvTermData) 0;
+	    msg[25] = ERL_DRV_TUPLE;
+	    msg[26] = (ErlDrvTermData) 8;
+	    msg += 27;
 	}
 	break;
 
@@ -481,6 +483,52 @@ static void send_term_drv_run(ErlDrvData port, char *buf, ErlDrvSizeT count)
 	break;
     }
 
+    case 40: {
+	msg[0] = ERL_DRV_MAP;
+	msg[1] = (ErlDrvTermData) 0;
+	msg += 2;
+	break;
+    }
+
+    case 41:    /* Most term types inside a map */
+    case 42: {
+	double f = 3.1416;
+
+	if (buf[i] == 41) {
+	    *msg++ = ERL_DRV_ATOM;
+	    *msg++ = driver_mk_atom("blurf");
+	}
+	*msg++ = ERL_DRV_INT;
+	*msg++ = (ErlDrvTermData)42;
+	*msg++ = ERL_DRV_NIL;
+	*msg++ = ERL_DRV_INT;
+	*msg++ = (ErlDrvTermData)-42;
+	*msg++ = ERL_DRV_TUPLE;
+	*msg++ = (ErlDrvTermData)0;
+	*msg++ = ERL_DRV_PORT;
+	*msg++ = driver_mk_port(erlang_port);
+	*msg++ = ERL_DRV_STRING_CONS;
+	*msg++ = (ErlDrvTermData)"abc";
+	*msg++ = (ErlDrvTermData)3;
+	*msg++ = ERL_DRV_LIST;
+	*msg++ = (ErlDrvTermData)3;
+	*msg++ = ERL_DRV_STRING;
+	*msg++ = (ErlDrvTermData)"kalle";
+	*msg++ = (ErlDrvTermData)5;
+	*msg++ = ERL_DRV_FLOAT;
+	*msg++ = (ErlDrvTermData)&f;
+	*msg++ = ERL_DRV_PID;
+	*msg++ = driver_connected(erlang_port);
+	*msg++ = ERL_DRV_MAP;
+	*msg++ = (ErlDrvTermData)0;
+	if (buf[i] == 42) {
+	    *msg++ = ERL_DRV_ATOM;
+	    *msg++ = driver_mk_atom("blurf");
+	}
+	*msg++ = ERL_DRV_MAP;
+	*msg++ = (ErlDrvTermData)4;
+	break;
+    }
 
     case 127:			/* Error cases */
 	{
@@ -662,6 +710,22 @@ static void send_term_drv_run(ErlDrvData port, char *buf, ErlDrvSizeT count)
 		FAIL_TERM(msg, 2);
 	    }
 
+	    msg[0] = ERL_DRV_MAP;
+	    msg[1] = (ErlDrvTermData) 0;
+	    FAIL_TERM(msg, 1);
+
+	    /* map with duplicate key */
+	    msg[0] = ERL_DRV_ATOM;
+	    msg[1] = driver_mk_atom("key");
+	    msg[2] = ERL_DRV_NIL;
+	    msg[3] = ERL_DRV_ATOM;
+	    msg[4] = driver_mk_atom("key");
+	    msg[5] = ERL_DRV_INT;
+	    msg[6] = (ErlDrvTermData) -4711;
+	    msg[7] = ERL_DRV_MAP;
+	    msg[8] = 2;
+	    FAIL_TERM(msg, 9);
+
 	    /* Signal end of test case */
 	    msg[0] = ERL_DRV_NIL;
 	    erl_drv_output_term(driver_mk_port(erlang_port), msg, 1);
diff --git a/erts/emulator/utils/beam_makeops b/erts/emulator/utils/beam_makeops
index 16a949c2a6..0b7c16f606 100755
--- a/erts/emulator/utils/beam_makeops
+++ b/erts/emulator/utils/beam_makeops
@@ -1202,6 +1202,7 @@ sub parse_transformation {
 
     my($from, $to) = split(/\s*=>\s*/);
     my(@op);
+    my $rest_var;
 
     # The source instructions.
 
@@ -1212,7 +1213,7 @@ sub parse_transformation {
 	    $_ = (&compile_transform_function($name, split(/\s*,\s*/, $arglist)));
 	} else {
 	    (@op) = split;
-	    $_ = &compile_transform(1, @op);
+	    ($rest_var,$_) = compile_transform(1, $rest_var, @op);
 	}
     }
 
@@ -1230,7 +1231,7 @@ sub parse_transformation {
 	@to = split(/\s*\|\s*/, $to);
 	foreach (@to) {
 	    (@op) = split;
-	    $_ = &compile_transform(0, @op);
+	    (undef,$_) = compile_transform(0, $rest_var, @op);
 	}
     }
     push(@transformations, [$., $orig, [@from], [reverse @to]]);
@@ -1243,12 +1244,18 @@ sub compile_transform_function {
 }
 
 sub compile_transform {
-    my($src, $name, @ops) = @_;
+    my($src, $rest_var, $name, @ops) = @_;
     my $arity = 0;
-    
+
     foreach (@ops) {
 	my(@list) = &tr_parse_op($src, $_);
-	$arity++ unless $list[1] eq '*';
+	if ($list[1] eq '*') {
+	    $rest_var = $list[0];
+	} elsif (defined $rest_var and $list[0] eq $rest_var) {
+	    $list[1] = '*';
+	} else {
+	    $arity++;
+	}
 	$_ = [ @list ];
     }
     
@@ -1260,7 +1267,7 @@ sub compile_transform {
 	$is_transformed{$name,$arity} = 1;
     }
     
-    [$name,$arity,@ops];
+    ($rest_var,[$name,$arity,@ops]);
 }
 
 sub tr_parse_op {
@@ -1681,7 +1688,9 @@ sub tr_gen_to {
 	foreach $op (@ops) {
 	    my($var, $type, $type_val) = @$op;
 
-	    if ($var ne '') {
+	    if ($type eq '*') {
+		push(@code, make_op($var, 'store_rest_args', $var{$var}));
+	    } elsif ($var ne '') {
 		&error($where, "variable '$var' unbound")
 		    unless defined $var{$var};
 		push(@code, &make_op($var, 'store_var_next_arg', $var{$var}));