aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib
diff options
context:
space:
mode:
Diffstat (limited to 'lib/stdlib')
-rw-r--r--lib/stdlib/doc/src/maps.xml52
-rw-r--r--lib/stdlib/src/maps.erl61
-rw-r--r--lib/stdlib/test/maps_SUITE.erl39
3 files changed, 36 insertions, 116 deletions
diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index a3afbf8e7f..987d92989d 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -38,8 +38,7 @@
<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>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</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
@@ -194,9 +193,9 @@ false</code>
<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>
+ to traverse the key-value associations in a map. When iterating
+ over a map, the memory usage is guaranteed to be bounded no matter
+ the size of the map.</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>
@@ -215,49 +214,6 @@ none</code>
</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>
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 2f2dd41979..a13f340709 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, iterator/2, next/1]).
+ iterator/1, next/1]).
%% BIFs
-export([get/2, find/2, from_list/1,
@@ -32,12 +32,14 @@
new/0, put/3, remove/2, take/2,
to_list/1, update/3, values/1]).
--opaque iterator() :: {non_neg_integer() | none | list(term()), map()}
- | list({term(), term()}).
+-opaque iterator() :: {term(), term(), iterator()}
+ | none | nonempty_improper_list(integer(),map()).
-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)))))))).
+-dialyzer({no_improper_lists, iterator/1}).
+
+-define(IS_ITERATOR(I), is_tuple(I) andalso tuple_size(I) == 3; I == none; is_integer(hd(I)) andalso is_map(tl(I))).
%% Shadowed by erl_bif_types: maps:get/2
-spec get(Key,Map) -> Value when
@@ -121,14 +123,20 @@ remove(_,_) -> erlang:nif_error(undef).
take(_,_) -> erlang:nif_error(undef).
-%% Shadowed by erl_bif_types: maps:to_list/1
-spec to_list(Map) -> [{Key,Value}] when
Map :: map(),
Key :: term(),
Value :: term().
-to_list(_) -> erlang:nif_error(undef).
+to_list(Map) when is_map(Map) ->
+ to_list_internal(erts_internal:map_next(0, Map, []));
+to_list(Map) ->
+ erlang:error({badmap,Map},[Map]).
+to_list_internal([Iter, Map | Acc]) when is_integer(Iter) ->
+ to_list_internal(erts_internal:map_next(Iter, Map, Acc));
+to_list_internal(Acc) ->
+ Acc.
%% Shadowed by erl_bif_types: maps:update/3
-spec update(Key,Value,Map1) -> Map2 when
@@ -207,7 +215,7 @@ get(Key,Map,Default) ->
Map :: map().
filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
- maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+ maps:from_list(filter_1(Pred, iterator(Map)));
filter(Pred,Iterator) when is_function(Pred,2), ?IS_ITERATOR(Iterator) ->
maps:from_list(filter_1(Pred, Iterator));
filter(Pred,Map) ->
@@ -237,7 +245,7 @@ filter_1(Pred, Iter) ->
V :: term().
fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
- lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+ fold_1(Fun,Init,iterator(Map));
fold(Fun,Init,Iterator) when is_function(Fun,3), ?IS_ITERATOR(Iterator) ->
fold_1(Fun,Init,Iterator);
fold(Fun,Init,Map) ->
@@ -260,7 +268,7 @@ fold_1(Fun, Acc, Iter) ->
V2 :: term().
map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
- maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+ maps:from_list(map_1(Fun, iterator(Map)));
map(Fun,Iterator) when is_function(Fun, 2), ?IS_ITERATOR(Iterator) ->
maps:from_list(map_1(Fun, Iterator));
map(Fun,Map) ->
@@ -286,42 +294,19 @@ size(Val) ->
Map :: map(),
Iterator :: iterator().
-iterator(M) when is_map(M) -> iterator(M, #{});
+iterator(M) when is_map(M) -> [0 | 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, 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) -> {Key, Value, NextIterator} | 'none' when
Iterator :: iterator(),
Key :: term(),
Value :: term(),
NextIterator :: iterator().
-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) ->
+next({K, V, I}) ->
+ {K, V, I};
+next([Path | Map]) when is_integer(Path), is_map(Map) ->
+ erts_internal:map_next(Path, Map, iterator);
+next(none) ->
none;
next(Iter) ->
erlang:error(badarg, [Iter]).
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 0021dd0657..a75751b31d 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,7 +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_iterator_1/1,
t_with_2/1,t_without_2/1]).
%%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -48,7 +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_iterator_1,
t_with_2,t_without_2].
t_update_with_3(Config) when is_list(Config) ->
@@ -179,40 +179,19 @@ t_iterator_1(Config) when is_list(Config) ->
%% Large map test
- Vs = lists:seq(1,200),
- M2 = maps:from_list([{{k,I},I}||I<-Vs]),
+ Vs2 = lists:seq(1,200),
+ M2 = maps:from_list([{{k,I},I}||I<-Vs2]),
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],
+ %% Larger map test
+ Vs3 = lists:seq(1,10000),
+ M3 = maps:from_list([{{k,I},I}||I<-Vs3]),
+ KVList3 = lists:sort(iter_kv(maps:iterator(M3))),
+ KVList3 = lists:sort(maps:to_list(M3)),
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 ->
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-03 04:57:32 +0000