erts: Implement maps path iterator

10 files changed, 553 insertions, 105 deletions

diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 4ee5af14bc..f2c8331850 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -689,6 +689,10 @@ bif erts_internal:maps_to_list/2
 #
 # New in 20.1
 #
-
 bif erlang:iolist_to_iovec/1
-bif erts_internal:map_get_index/2
\ No newline at end of file
+
+#
+# New in 21.0
+#
+
+bif erts_internal:map_next/2
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 37fcedbc6d..a5fda7b86d 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -90,6 +90,7 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_
                                  struct HashmapMergeContext_*);
 static Export hashmap_merge_trap_export;
 static BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1);
+static Uint hashmap_subtree_size(Eterm node);
 static Eterm hashmap_to_list(Process *p, Eterm map, Sint n);
 static Eterm hashmap_keys(Process *p, Eterm map);
 static Eterm hashmap_values(Process *p, Eterm map);
@@ -1518,7 +1519,7 @@ trap:  /* Yield */
     return trap_ret;
 }
 
-Uint hashmap_subtree_size(Eterm node) {
+static Uint hashmap_subtree_size(Eterm node) {
     DECLARE_WSTACK(stack);
     Uint size = 0;
 
@@ -3059,74 +3060,247 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
     return res;
 }
 
-static Uint32
-index_to_hash(Sint idx, Uint32 hval)
-{
-    Uint32 new_hval = 1;
-    while (1) {
-        if (hval & 0x1) {
-            idx--;
-            if (!idx) break;
-        }
-        new_hval = new_hval << 1;
-        hval = hval >> 1;
-    }
-    return new_hval;
-}
 
-BIF_RETTYPE erts_internal_map_get_index_2(BIF_ALIST_2) {
-    Sint idx;
-    Uint32 hval, sz;
-    Eterm *ptr, hdr;
+/*
+ * The iterator work in about the same way for both
+ * flat- and hash-maps. It consists of a Path, Map
+ * term where Path describes where to find the
+ * term to get.
+ *
+ * In flatmap Path is just the index of the element
+ * in the flatmap array.
+ *
+ * In hashmap the Path is a bit pattern that describes
+ * which slot we should traverse in each hashmap node.
+ * Since each hashmap node can only be up to 16 elements
+ * large we use 4 bits per level in the path.
+ *
+ * So a Path with value 0x110 will first get the 0:th
+ * slot in the head node, and then the 1:st slot in the
+ * resulting node and then finally the 1:st slot in the
+ * node beneath. If that slot is not a leaf, then the path
+ * continues down the 0:th slot until it finds a leaf and
+ * returns that leaf.
+ *
+ * Once the leaf has been found, the Path to the next leaf
+ * is built using a stack that was created while traversing
+ * the tree down.
+ *
+ * The index can become a bignum, which complicates the code
+ * a bit. However it should be very rare that this happens
+ * even on a 32bit system as you would need a tree of depth
+ * 7 or more.
+ */
 
-    if (!is_hashmap(BIF_ARG_2) || is_not_small(BIF_ARG_1))
-        BIF_ERROR(BIF_P, BADARG);
+#define PATH_ELEM_SIZE 4
+#define PATH_ELEM_MASK 0xf
+#define PATH_ELEM(PATH) ((PATH) & PATH_ELEM_MASK)
+#define PATH_ELEMS_PER_DIGIT (sizeof(ErtsDigit) * 8 / PATH_ELEM_SIZE)
 
-    idx = signed_val(BIF_ARG_1);
+BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
 
-    if (idx < 1 || idx > 17)
+    Eterm *hp = NULL, *lst,
+        iter, path, map, k, v;
+
+    path = BIF_ARG_1;
+    map  = BIF_ARG_2;
+
+    if (!is_map(map))
         BIF_ERROR(BIF_P, BADARG);
 
-    ASSERT(is_boxed(BIF_ARG_2));
+    if (path == am_none)
+        BIF_RET(am_none);
 
-    ptr = boxed_val(BIF_ARG_2);
-again:
-    hdr = *ptr;
+    if (is_flatmap(map)) {
+        flatmap_t *mp = (flatmap_t *)flatmap_val(map);
+        Uint idx, sz = flatmap_get_size(mp);
 
-    switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-    case HAMT_SUBTAG_HEAD_ARRAY:
-        ptr++;
-        sz = 16;
-        hval = 0xffff;
-        break;
-    case HAMT_SUBTAG_HEAD_BITMAP:
-        ptr++;
-        if (ptr[0] == -1) {
-            ptr = boxed_val(ptr[1]);
-            goto again;
+        if (is_not_small(path))
+            BIF_ERROR(BIF_P, BADARG);
+
+        idx = unsigned_val(path);
+
+        if (sz == 0) {
+            if (idx == 0)
+                BIF_RET(am_none);
+            else
+                BIF_ERROR(BIF_P, BADARG);
         }
-    case HAMT_SUBTAG_NODE_BITMAP:
-        hval = MAP_HEADER_VAL(hdr);
-        sz = hashmap_bitcount(hval);
-        ASSERT(sz < 17);
-        break;
-    default:
-        erts_exit(ERTS_ABORT_EXIT, "bad header");
-    }
-
-    if (idx <= sz) {
-        if (is_list(ptr[idx]))
-            return ptr[idx];
-        else {
-            Eterm *hp = HAlloc(BIF_P, HAMT_HEAD_BITMAP_SZ(1));
-            hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(index_to_hash(idx, hval));
-            hp[1] = -1;
-            hp[2] = ptr[idx];
-            return make_hashmap(hp);
+
+        k = flatmap_get_keys(mp)[idx];
+        v = flatmap_get_values(mp)[idx];
+
+        if (idx + 1 < sz) {
+            path = make_small(idx + 1);
+        } else if (idx < sz) {
+            path = am_none;
+        } else {
+            BIF_ERROR(BIF_P, BADARG);
         }
     } else {
-        return am_none;
+        Uint curr_path;
+        Uint path_length = 0;
+        Uint *path_rest = NULL;
+        int i;
+        Eterm node = map;
+        DECLARE_WSTACK(stack);
+
+        ASSERT(is_hashmap(node));
+
+        if (is_small(path)) {
+            curr_path = unsigned_val(path);
+        } else if (is_big(path)) {
+            Eterm *big = big_val(path);
+            if (bignum_header_is_neg(*big))
+                BIF_ERROR(BIF_P, BADARG);
+            path_length = BIG_ARITY(big) - 1;
+            curr_path = BIG_DIGIT(big,  0);
+            path_rest = BIG_V(big) + 1;
+        } else {
+            BIF_ERROR(BIF_P, BADARG);
+        }
+
+        /* First we look for the K and V to return using the
+           path given. While doing so, we push each map node
+           and the index onto the stack so use later when
+           building the next index. */
+        for (i = 1; ; i++) {
+            Eterm *ptr = hashmap_val(node),
+                hdr = *ptr;
+            Uint sz;
+
+            ptr++;
+
+            switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
+	    case HAMT_SUBTAG_HEAD_ARRAY:
+		ptr++;
+		sz = 16;
+		break;
+	    case HAMT_SUBTAG_HEAD_BITMAP:
+		ptr++;
+	    case HAMT_SUBTAG_NODE_BITMAP:
+		sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
+		ASSERT(sz < 17);
+		break;
+            default:
+		erts_exit(ERTS_ABORT_EXIT, "bad header");
+	    }
+
+            if (PATH_ELEM(curr_path) >= sz)
+                BIF_ERROR(BIF_P, BADARG);
+
+            WSTACK_PUSH2(stack, node, PATH_ELEM(curr_path));
+
+            /* We have found a leaf, return it and calculate the path to next */
+            if (is_list(ptr[PATH_ELEM(curr_path)])) {
+                lst = list_val(ptr[PATH_ELEM(curr_path)]);
+                k = CAR(lst);
+                v = CDR(lst);
+                break;
+            }
+
+            node = ptr[PATH_ELEM(curr_path)];
+
+            curr_path >>= PATH_ELEM_SIZE;
+
+            if (i == PATH_ELEMS_PER_DIGIT) {
+                /* Switch to next bignum word if available,
+                   otherwise just follow 0 path */
+                i = 0;
+                if (path_length) {
+                    curr_path = *path_rest;
+                    path_length--;
+                    path_rest++;
+                } else {
+                    curr_path = 0;
+                }
+            }
+        }
+
+        /* We pop the stack until we come to the next leaf to return */
+        while (1) {
+            Uint idx = (Uint)WSTACK_POP(stack);
+            Eterm node = (Eterm)WSTACK_POP(stack);
+            Eterm *ptr = hashmap_val(node),
+                hdr = *ptr;
+            Uint sz;
+
+            ptr++;
+
+            switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
+	    case HAMT_SUBTAG_HEAD_ARRAY:
+		ptr++;
+		sz = 16;
+		break;
+	    case HAMT_SUBTAG_HEAD_BITMAP:
+		ptr++;
+	    case HAMT_SUBTAG_NODE_BITMAP:
+		sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
+		ASSERT(sz < 17);
+		break;
+            default:
+		erts_exit(ERTS_ABORT_EXIT, "bad header");
+	    }
+
+            if (idx + 1 < sz) {
+                curr_path = idx + 1;
+                break;
+            }
+
+            /* We have reached the end of the iteration */
+            if (WSTACK_ISEMPTY(stack)) {
+                path = am_none;
+                break;
+            }
+
+        }
+
+        if (path != am_none) {
+            Uint depth = WSTACK_COUNT(stack) / 2 + 1;
+            /* +1 because we already have the first element in curr_path */
+            Eterm *path_digits = NULL;
+
+            /* If the path cannot fit in a small, we allocate a bignum */
+            if (depth >= PATH_ELEMS_PER_DIGIT) {
+                /* We need multiple ErtsDigit's to represent the path */
+                int big_size = BIG_NEED_FOR_BITS(depth * PATH_ELEM_SIZE);
+                hp = HAlloc(BIF_P, big_size);
+                hp[0] = make_pos_bignum_header(big_size - BIG_NEED_SIZE(0));
+                path_digits = hp + big_size - 1;
+            }
+
+            /* Pop the stack to create the complete path to the next leaf */
+            while(!WSTACK_ISEMPTY(stack)) {
+                Uint idx = (Uint)WSTACK_POP(stack);
+                (void)WSTACK_POP(stack);
+
+                depth--;
+                if (depth % PATH_ELEMS_PER_DIGIT == 0) {
+                    path_digits[0] = curr_path;
+                    path_digits--;
+                    curr_path = 0;
+                }
+
+                curr_path <<= PATH_ELEM_SIZE;
+                curr_path |= idx;
+            }
+
+            if (path_digits) {
+                path_digits[0] = curr_path;
+                path = make_big(hp);
+            } else {
+                /* The Uint could be too large for a small */
+                path = erts_make_integer(curr_path, BIF_P);
+            }
+        }
+
+        DESTROY_WSTACK(stack);
     }
+
+    hp = HAlloc(BIF_P, 4 + 3 /* 3-tuple + 2-tuple */);
+    iter = TUPLE2(hp, path, map);
+    hp += 3;
+    BIF_RET(TUPLE3(hp, k, v, iter));
 }
 
 /* implementation of builtin emulations */
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index d910e98398..718d400e22 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -56,7 +56,7 @@ typedef struct flatmap_s {
 /* the head-node is a bitmap or array with an untagged size */
 
 
-#define hashmap_size(x)               (((hashmap_head_t*) hashmap_val(x))->size == -1 ? hashmap_subtree_size(x) : ((hashmap_head_t*) hashmap_val(x))->size)
+#define hashmap_size(x)               (((hashmap_head_t*) hashmap_val(x))->size)
 #define hashmap_make_hash(Key)        make_internal_hash(Key, 0)
 
 #define hashmap_restore_hash(Heap,Lvl,Key) \
@@ -64,7 +64,6 @@ typedef struct flatmap_s {
 #define hashmap_shift_hash(Heap,Hx,Lvl,Key) \
     (((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key)))
 
-
 /* erl_term.h stuff */
 #define flatmap_get_values(x)        (((Eterm *)(x)) + sizeof(flatmap_t)/sizeof(Eterm))
 #define flatmap_get_keys(x)          (((Eterm *)tuple_val(((flatmap_t *)(x))->keys)) + 1)
@@ -106,7 +105,6 @@ Eterm  erts_hashmap_from_ks_and_vs_extra(ErtsHeapFactory *factory,
                                          Eterm *ks, Eterm *vs, Uint n,
 					 Eterm k, Eterm v);
 
-Uint hashmap_subtree_size(Eterm node);
 const Eterm *erts_maps_get(Eterm key, Eterm map);
 
 const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm map);
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 02f3c89318..3cf071b590 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -53,6 +53,7 @@
          t_bif_map_to_list/1,
          t_bif_map_from_list/1,
          t_bif_erts_internal_maps_to_list/1,
+         t_bif_map_next/1,
 
          %% erlang
          t_erlang_hash/1,
@@ -120,6 +121,7 @@ all() -> [t_build_and_match_literals, t_build_and_match_literals_large,
           t_bif_map_values,
           t_bif_map_to_list, t_bif_map_from_list,
           t_bif_erts_internal_maps_to_list,
+          t_bif_map_next,
 
           %% erlang
           t_erlang_hash, t_map_encode_decode,
@@ -2399,6 +2401,55 @@ t_bif_erts_internal_maps_to_list(Config) when is_list(Config) ->
     {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{1=>2}),id(<<>>))),
     ok.
 
+t_bif_map_next(Config) when is_list(Config) ->
+
+    erts_debug:set_internal_state(available_internal_state, true),
+
+    try
+
+        none = maps:next(maps:iterator(id(#{}))),
+
+        verify_iterator(#{}),
+        verify_iterator(#{a => 1, b => 2, c => 3}),
+
+        %% Use fatmap in order to test iterating in very deep maps
+        FM = fatmap(43),
+        verify_iterator(FM),
+
+        {'EXIT', {{badmap,[{a,b},b]},_}} = (catch maps:iterator(id([{a,b},b]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id(a))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([a|FM]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([1|#{}]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([16#FFFFFFF|FM]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([16#F0F0F0F|FM]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([16#1234567890ABCDEF|FM]))),
+
+        ok
+    after
+            erts_debug:set_internal_state(available_internal_state, false)
+    end.
+
+verify_iterator(Map) ->
+    KVs = t_fold(fun(K, V, A) -> [{K, V} | A] end, [], Map),
+
+    %% Verify that KVs created by iterating Map is of
+    %% correct size and contains all elements
+    true = length(KVs) == maps:size(Map),
+    [maps:get(K, Map) || {K, _} <- KVs],
+    ok.
+
+
+t_fold(Fun, Init, Map) ->
+    t_fold_1(Fun, Init, maps:iterator(Map)).
+
+t_fold_1(Fun, Acc, Iter) ->
+    case maps:next(Iter) of
+        {K, V, NextIter} ->
+            t_fold_1(Fun, Fun(K,V,Acc), NextIter);
+        none ->
+            Acc
+    end.
+
 t_bif_build_and_check(Config) when is_list(Config) ->
     ok = check_build_and_remove(750,[fun(K) -> [K,K] end,
 				     fun(K) -> [float(K),K] end,
diff --git a/erts/preloaded/ebin/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam
index 5416826f19..015508d326 100644
--- a/erts/preloaded/ebin/erts_internal.beam
+++ b/erts/preloaded/ebin/erts_internal.beam
diff --git a/erts/preloaded/src/erts_internal.erl b/erts/preloaded/src/erts_internal.erl
index bb1824ecd4..46bdeaad30 100644
--- a/erts/preloaded/src/erts_internal.erl
+++ b/erts/preloaded/src/erts_internal.erl
@@ -32,7 +32,7 @@
 -export([await_port_send_result/3]).
 -export([cmp_term/2]).
 -export([map_to_tuple_keys/1, term_type/1, map_hashmap_children/1,
-         maps_to_list/2]).
+         maps_to_list/2, map_next/2]).
 -export([open_port/2, port_command/3, port_connect/2, port_close/1,
 	 port_control/3, port_call/3, port_info/1, port_info/2]).
 
@@ -381,6 +381,17 @@ map_hashmap_children(_M) ->
 maps_to_list(_M, _N) ->
     erlang:nif_error(undefined).
 
+%% return the next assoc in the iterator and a new iterator
+-spec map_next(I, M) -> {K,V,NI} when
+      I :: non_neg_integer(),
+      M :: map(),
+      K :: term(),
+      V :: term(),
+      NI :: maps:iterator().
+
+map_next(_I, _M) ->
+    erlang:nif_error(undefined).
+
 %% erlang:demonitor(Ref, [flush]) traps to
 %% erts_internal:flush_monitor_messages(Ref, Res) when
 %% it needs to flush monitor messages.
diff --git a/lib/dialyzer/test/small_SUITE_data/results/maps_sum b/lib/dialyzer/test/small_SUITE_data/results/maps_sum
index bd192bdb93..b29ac77d88 100644
--- a/lib/dialyzer/test/small_SUITE_data/results/maps_sum
+++ b/lib/dialyzer/test/small_SUITE_data/results/maps_sum
@@ -1,4 +1,4 @@
 
-maps_sum.erl:15: Invalid type specification for function maps_sum:wrong1/1. The success typing is (map()) -> any()
+maps_sum.erl:15: Invalid type specification for function maps_sum:wrong1/1. The success typing is (maps:iterator() | map()) -> any()
 maps_sum.erl:26: Function wrong2/1 has no local return
 maps_sum.erl:27: The call lists:foldl(fun((_,_,_) -> any()),0,Data::any()) will never return since it differs in the 1st argument from the success typing arguments: (fun((_,_) -> any()),any(),[any()])
diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index 8c7270816b..a3afbf8e7f 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -33,16 +33,32 @@
     <p>This module contains functions for maps processing.</p>
   </description>
 
+  <datatypes>
+    <datatype>
+      <name name="iterator"/>
+      <desc>
+        <p>An iterator representing the key value associations in a map.</p>
+        <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>
+        and <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>.</p>
+        <p>Consumed by <seealso marker="#next-1"><c>maps:next/1</c></seealso>,
+          <seealso marker="#filter-2"><c>maps:filter/2</c></seealso>,
+          <seealso marker="#fold-3"><c>maps:fold/3</c></seealso> and
+          <seealso marker="#map-2"><c>maps:map/2</c></seealso>.</p>
+      </desc>
+    </datatype>
+  </datatypes>
+
   <funcs>
     <func>
       <name name="filter" arity="2"/>
       <fsummary>Select pairs that satisfy a predicate.</fsummary>
       <desc>
-        <p>Returns a map <c><anno>Map2</anno></c> for which predicate
-          <c><anno>Pred</anno></c> holds true in <c><anno>Map1</anno></c>.</p>
+        <p>Returns a map <c><anno>Map</anno></c> for which predicate
+          <c><anno>Pred</anno></c> holds true in <c><anno>MapOrIter</anno></c>.</p>
         <p>The call fails with a <c>{badmap,Map}</c> exception if
-          <c><anno>Map1</anno></c> is not a map, or with <c>badarg</c> if
-          <c><anno>Pred</anno></c> is not a function of arity 2.</p>
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Pred</anno></c> is not a
+          function of arity 2.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > M = #{a => 2, b => 3, c=> 4, "a" => 1, "b" => 2, "c" => 4},
@@ -76,12 +92,16 @@
       <fsummary></fsummary>
       <desc>
         <p>Calls <c>F(K, V, AccIn)</c> for every <c><anno>K</anno></c> to value
-          <c><anno>V</anno></c> association in <c><anno>Map</anno></c> in
+          <c><anno>V</anno></c> association in <c><anno>MapOrIter</anno></c> in
           any order. Function <c>fun F/3</c> must return a new
           accumulator, which is passed to the next successive call.
           This function returns the final value of the accumulator. The initial
           accumulator value <c><anno>Init</anno></c> is returned if the map is
           empty.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Fun</anno></c> is not a
+          function of arity 3.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > Fun = fun(K,V,AccIn) when is_list(K) -> AccIn + V end,
@@ -169,6 +189,75 @@ false</code>
     </func>
 
     <func>
+      <name name="iterator" arity="1"/>
+      <fsummary>Create a map iterator.</fsummary>
+      <desc>
+        <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
+          be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
+          to traverse the keys and values in a map. This call is equivalent
+          to calling <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>
+          with an empty map as the options.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>Map</anno></c> is not a map.</p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> M = #{ a => 1, b => 2 }.
+#{a => 1,b => 2}
+> I = maps:iterator(M).
+[{a,1},{b,2}]
+> {K1, V1, I2} = maps:next(I).
+{a,1,[{b,2}]}
+> {K2, V2, I3} = maps:next(I2).
+{b,2,[]}
+> maps:next(I3).
+none</code>
+      </desc>
+    </func>
+
+    <func>
+      <name name="iterator" arity="2"/>
+      <fsummary>Create a map iterator.</fsummary>
+      <desc>
+        <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
+          be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
+          to traverse the keys and values in a map. The iterator will behave
+          according to the given <c><anno>Opts</anno></c>.</p>
+        <taglist>
+          <tag>optimize</tag>
+          <item>
+            Configures whether the iterator should be optimized for <c>speed</c>
+            or for <c>memory</c> consumption. Default is <c>speed</c>.
+          </item>
+          <tag>ordered</tag>
+          <item>
+            Configures whether the iterator should return the key value
+            associations ordered on the keys according to erlang term order
+            or not. The default is <c>false</c>.
+          </item>
+        </taglist>
+        <p>Both options can be configured at the same time.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>Map</anno></c> is not a map.</p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> M = maps:from_list([{I,I} || I &lt;- lists:seq(1,50)]).
+#{45 => 45,6 => 6,2 => 2,49 => 49,41 => 41,33 => 33,42 => 42,
+  43 => 43,10 => 10,9 => 9,19 => 19,14 => 14,5 => 5,18 => 18,
+  31 => 31,22 => 22,29 => 29,21 => 21,27 => 27,24 => 24,
+  47 => 47,40 => 40,30 => 30,23 => 23,28 => 28,46 => 46,
+  16 => 16,38 => 38,4 => 4,...}
+> MemoryIter = maps:iterator(M, #{ optimize => memory }), ok.
+ok
+> {K1, V1, _} = maps:next(MemoryIter), {K1, V1}.
+{46,46}
+> OrderedIter = maps:iterator(M, #{ ordered => true, optimize => memory }), ok.
+ok
+> {K2, V2, _} = maps:next(OrderedIter), {K2, V2}.
+{1,1}</code>
+      </desc>
+    </func>
+
+    <func>
       <name name="keys" arity="1"/>
       <fsummary></fsummary>
       <desc>
@@ -188,12 +277,16 @@ false</code>
       <name name="map" arity="2"/>
       <fsummary></fsummary>
       <desc>
-        <p>Produces a new map <c><anno>Map2</anno></c> by calling function
+        <p>Produces a new map <c><anno>Map</anno></c> by calling function
           <c>fun F(K, V1)</c> for every <c><anno>K</anno></c> to value
-          <c><anno>V1</anno></c> association in <c><anno>Map1</anno></c> in
+          <c><anno>V1</anno></c> association in <c><anno>MapOrIter</anno></c> in
           any order. Function <c>fun F/2</c> must return value
           <c><anno>V2</anno></c> to be associated with key <c><anno>K</anno></c>
-          for the new map <c><anno>Map2</anno></c>.</p>
+          for the new map <c><anno>Map</anno></c>.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Fun</anno></c> is not a
+          function of arity 2.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > Fun = fun(K,V1) when is_list(K) -> V1*2 end,
@@ -234,6 +327,35 @@ false</code>
     </func>
 
     <func>
+      <name name="next" arity="1"/>
+      <fsummary>Get the next key and value from an iterator.</fsummary>
+      <desc>
+        <p>Returns the next key-value association in
+          <c><anno>Iterator</anno></c> and a new iterator for the
+          remaining associations in the iterator.
+        </p>
+        <p>
+          If there are no more associations in the iterator,
+          <c>none</c> is returned.
+        </p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> Map = #{a => 1, b => 2, c => 3}.
+#{a => 1,b => 2,c => 3}
+> Iter = maps:iterator(Map).
+[{a,1},{b,2},{c,3}]
+> {_, _, Iter1} = maps:next(Iter).
+{a,1,[{b,2},{c,3}]}
+> {_, _, Iter2} = maps:next(Iter1).
+{b,2,[{c,3}]}
+> {_, _, Iter3} = maps:next(Iter2).
+{c,3,[]}
+> maps:next(Iter3).
+none</code>
+      </desc>
+    </func>
+
+    <func>
       <name name="put" arity="3"/>
       <fsummary></fsummary>
       <desc>
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 0da12cf8e2..2f2dd41979 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -24,7 +24,7 @@
          map/2, size/1,
          update_with/3, update_with/4,
          without/2, with/2,
-         iterator/1, next/1]).
+         iterator/1, iterator/2, next/1]).
 
 %% BIFs
 -export([get/2, find/2, from_list/1,
@@ -32,10 +32,13 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
--opaque iterator() :: [{term(), term()}] | [[pos_integer() | map()]].
+-opaque iterator() :: {non_neg_integer() | none | list(term()), map()}
+                    | list({term(), term()}).
 
 -export_type([iterator/0]).
 
+-define(IS_ITERATOR(I), (is_list(I) orelse (is_map(element(2,I) andalso (is_list(element(1,I) orelse is_integer(element(1,I)))))))).
+
 %% Shadowed by erl_bif_types: maps:get/2
 -spec get(Key,Map) -> Value when
     Key :: term(),
@@ -44,7 +47,6 @@
 
 get(_,_) -> erlang:nif_error(undef).
 
-
 -spec find(Key,Map) -> {ok, Value} | error when
     Key :: term(),
     Map :: map(),
@@ -197,15 +199,17 @@ get(Key,Map,Default) ->
     erlang:error({badmap,Map},[Key,Map,Default]).
 
 
--spec filter(Pred,Map1) -> Map2 when
+-spec filter(Pred,MapOrIter) -> Map when
       Pred :: fun((Key, Value) -> boolean()),
       Key  :: term(),
       Value :: term(),
-      Map1 :: map(),
-      Map2 :: map().
+      MapOrIter :: map() | iterator(),
+      Map :: map().
 
 filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
-    maps:from_list(filter_1(Pred, iterator(Map)));
+    maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+filter(Pred,Iterator) when is_function(Pred,2), ?IS_ITERATOR(Iterator) ->
+    maps:from_list(filter_1(Pred, Iterator));
 filter(Pred,Map) ->
     erlang:error(error_type(Map),[Pred,Map]).
 
@@ -222,18 +226,20 @@ filter_1(Pred, Iter) ->
             []
     end.
 
--spec fold(Fun,Init,Map) -> Acc when
+-spec fold(Fun,Init,MapOrIter) -> Acc when
     Fun :: fun((K, V, AccIn) -> AccOut),
     Init :: term(),
     Acc :: term(),
     AccIn :: term(),
     AccOut :: term(),
-    Map :: map(),
+    MapOrIter :: map() | iterator(),
     K :: term(),
     V :: term().
 
 fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
-    fold_1(Fun, Init, iterator(Map));
+    lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+fold(Fun,Init,Iterator) when is_function(Fun,3), ?IS_ITERATOR(Iterator) ->
+    fold_1(Fun,Init,Iterator);
 fold(Fun,Init,Map) ->
     erlang:error(error_type(Map),[Fun,Init,Map]).
 
@@ -245,16 +251,18 @@ fold_1(Fun, Acc, Iter) ->
             Acc
     end.
 
--spec map(Fun,Map1) -> Map2 when
+-spec map(Fun,MapOrIter) -> Map when
     Fun :: fun((K, V1) -> V2),
-    Map1 :: map(),
-    Map2 :: map(),
+    MapOrIter :: map() | iterator(),
+    Map :: map(),
     K :: term(),
     V1 :: term(),
     V2 :: term().
 
 map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
-    maps:from_list(map_1(Fun, iterator(Map)));
+    maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+map(Fun,Iterator) when is_function(Fun, 2), ?IS_ITERATOR(Iterator) ->
+    maps:from_list(map_1(Fun, Iterator));
 map(Fun,Map) ->
     erlang:error(error_type(Map),[Fun,Map]).
 
@@ -278,28 +286,45 @@ size(Val) ->
       Map :: map(),
       Iterator :: iterator().
 
-iterator(Map) when is_map(Map) ->
-    case maps:size(Map) < 42 of
-        true -> maps:to_list(Map);
-        false -> [[1 | Map]]
+iterator(M) when is_map(M) -> iterator(M, #{});
+iterator(M) -> erlang:error({badmap, M}, [M]).
+
+-spec iterator(Map, Opts) -> Iterator when
+      Map :: map(),
+      Opts :: #{ ordered => boolean(), optimize => speed | memory },
+      Iterator :: iterator().
+iterator(M, Opts) when is_map(M), is_map(Opts) ->
+    case maps:merge(default_iterator_opts(), Opts) of
+        #{ ordered := true, optimize := speed} -> lists:sort(maps:to_list(M));
+        #{ ordered := false, optimize := speed} -> maps:to_list(M);
+        #{ ordered := true, optimize := memory} -> {lists:sort(maps:keys(M)), M};
+        #{ ordered := false, optimize := memory} -> {0, M}
     end;
-iterator(M) ->
-    erlang:error(error_type(M),[M]).
+iterator(M, Opts) when is_map(M) ->
+    erlang:error({badmap, M}, [M, Opts]);
+iterator(M, Opts) ->
+    erlang:error(error_type(M), [M, Opts]).
+
+default_iterator_opts() ->
+    #{ ordered => false, optimize => speed }.
 
--spec next(Iterator) -> {K,V,NextIterator} | 'none' when
+-spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when
       Iterator :: iterator(),
-      K :: term(),
-      V :: term(),
+      Key :: term(),
+      Value :: term(),
       NextIterator :: iterator().
-next([]) -> none;
-next([[Index | Map] | St]) ->
-    case erts_internal:map_get_index(Index, Map) of
-        SubMap when is_map(SubMap) -> next([[1 | SubMap], [Index+1|Map] | St]);
-        [K|V] -> {K,V,[[Index+1 | Map] | St]};
-        none -> next(St)
-    end;
-next([{K, V} | I]) ->
-    {K, V, I}.
+next([{K, V} | T]) ->
+    {K, V, T};
+next([]) ->
+    none;
+next({I, M}) when is_map(M), is_integer(I) orelse is_atom(I) ->
+    erts_internal:map_next(I, M);
+next({[K | T], M}) when is_map(M) ->
+    {K, maps:get(K, M), {T, M}};
+next({[], M}) when is_map(M) ->
+    none;
+next(Iter) ->
+    erlang:error(badarg, [Iter]).
 
 -spec without(Ks,Map1) -> Map2 when
     Ks :: [K],
@@ -332,5 +357,5 @@ with(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
 
-error_type(M) when is_map(M) -> badarg;
+error_type(M) when is_map(M); ?IS_ITERATOR(M) -> badarg;
 error_type(V) -> {badmap, V}.
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 42e669a799..0021dd0657 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,6 +30,7 @@
 -export([t_update_with_3/1, t_update_with_4/1,
          t_get_3/1, t_filter_2/1,
          t_fold_3/1,t_map_2/1,t_size_1/1,
+         t_iterator_1/1, t_iterator_2/1,
          t_with_2/1,t_without_2/1]).
 
 %%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -47,6 +48,7 @@ all() ->
     [t_update_with_3,t_update_with_4,
      t_get_3,t_filter_2,
      t_fold_3,t_map_2,t_size_1,
+     t_iterator_1, t_iterator_2,
      t_with_2,t_without_2].
 
 t_update_with_3(Config) when is_list(Config) ->
@@ -127,6 +129,8 @@ t_filter_2(Config) when is_list(Config) ->
     Pred2 = fun(K,V) -> is_list(K) andalso (V rem 2) =:= 0 end,
     #{a := 2,c := 4} = maps:filter(Pred1,M),
     #{"b" := 2,"c" := 4} = maps:filter(Pred2,M),
+    #{a := 2,c := 4} = maps:filter(Pred1,maps:iterator(M)),
+    #{"b" := 2,"c" := 4} = maps:filter(Pred2,maps:iterator(M)),
     %% error case
     ?badmap(a,filter,[_,a]) = (catch maps:filter(fun(_,_) -> ok end,id(a))),
     ?badarg(filter,[<<>>,#{}]) = (catch maps:filter(id(<<>>),#{})),
@@ -139,6 +143,8 @@ t_fold_3(Config) when is_list(Config) ->
     Tot0 = lists:sum(Vs),
     Tot1 = maps:fold(fun({k,_},V,A) -> A + V end, 0, M0),
     true = Tot0 =:= Tot1,
+    Tot2 = maps:fold(fun({k,_},V,A) -> A + V end, 0, maps:iterator(M0)),
+    true = Tot0 =:= Tot2,
 
     %% error case
     ?badmap(a,fold,[_,0,a]) = (catch maps:fold(fun(_,_,_) -> ok end,0,id(a))),
@@ -151,12 +157,69 @@ t_map_2(Config) when is_list(Config) ->
     #{ {k,1} := 1, {k,200} := 200} = M0,
     M1 = maps:map(fun({k,_},V) -> V + 42 end, M0),
     #{ {k,1} := 43, {k,200} := 242} = M1,
+    M2 = maps:map(fun({k,_},V) -> V + 42 end, maps:iterator(M0)),
+    #{ {k,1} := 43, {k,200} := 242} = M2,
 
     %% error case
     ?badmap(a,map,[_,a]) = (catch maps:map(fun(_,_) -> ok end, id(a))),
     ?badarg(map,[<<>>,#{}]) = (catch maps:map(id(<<>>),#{})),
     ok.
 
+t_iterator_1(Config) when is_list(Config) ->
+
+    %% Small map test
+    M0 = #{ a => 1, b => 2 },
+    I0 = maps:iterator(M0),
+    {K1,V1,I1} = maps:next(I0),
+    {K2,V2,I2} = maps:next(I1),
+    none = maps:next(I2),
+
+    KVList = lists:sort([{K1,V1},{K2,V2}]),
+    KVList = lists:sort(maps:to_list(M0)),
+
+    %% Large map test
+
+    Vs = lists:seq(1,200),
+    M2 = maps:from_list([{{k,I},I}||I<-Vs]),
+    KVList2 = lists:sort(iter_kv(maps:iterator(M2))),
+    KVList2 = lists:sort(maps:to_list(M2)),
+    ok.
+
+t_iterator_2(Config) when is_list(Config) ->
+
+    Vs = lists:seq(1,200),
+    Maps = [#{ a => 1, b => 2 }, maps:from_list([{{k,I},I}||I<-Vs])],
+    Optimize = [speed, memory],
+    Ordered = [true, false],
+
+    [test_iterator(Map, Opt, Ord) || Map <- Maps,
+                                     Opt <- Optimize,
+                                     Ord <- Ordered],
+
+    ok.
+
+test_iterator(Map, Opt, Ord) ->
+    Opts = #{ optimize => Opt, ordered => Ord },
+    test_iterator_1(maps:iterator(Map, Opts), Map, Opts).
+
+test_iterator_1(Iter, OrigMap, Opts) ->
+    erlang:display(Opts),
+    KVs = iter_kv(Iter),
+    case Opts of
+        #{ ordered := true } ->
+            KVs = lists:sort(maps:to_list(OrigMap));
+        #{ ordered := false } ->
+            OrderedKVs = lists:sort(KVs),
+            OrderedKVs = lists:sort(maps:to_list(OrigMap))
+    end.
+
+iter_kv(I) ->
+    case maps:next(I) of
+        none ->
+            [];
+        {K,V,NI} ->
+            [{K,V} | iter_kv(NI)]
+    end.
 
 t_size_1(Config) when is_list(Config) ->
       0 = maps:size(#{}),