From 0149a73d15df1f80cb46752ec3829f48c38dd230 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 21 Sep 2017 09:20:30 +0200 Subject: erts: Implement maps path iterator --- lib/stdlib/doc/src/maps.xml | 138 ++++++++++++++++++++++++++++++++++++++--- lib/stdlib/src/maps.erl | 91 +++++++++++++++++---------- lib/stdlib/test/maps_SUITE.erl | 63 +++++++++++++++++++ 3 files changed, 251 insertions(+), 41 deletions(-) (limited to 'lib/stdlib') 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 @@

This module contains functions for maps processing.

+ + + + +

An iterator representing the key value associations in a map.

+

Created using maps:iterator/1 + and maps:iterator/2.

+

Consumed by maps:next/1, + maps:filter/2, + maps:fold/3 and + maps:map/2.

+ + + + Select pairs that satisfy a predicate. -

Returns a map Map2 for which predicate - Pred holds true in Map1.

+

Returns a map Map for which predicate + Pred holds true in MapOrIter.

The call fails with a {badmap,Map} exception if - Map1 is not a map, or with badarg if - Pred is not a function of arity 2.

+ MapOrIter is not a map or valid iterator, + or with badarg if Pred is not a + function of arity 2.

Example:

> M = #{a => 2, b => 3, c=> 4, "a" => 1, "b" => 2, "c" => 4}, @@ -76,12 +92,16 @@

Calls F(K, V, AccIn) for every K to value - V association in Map in + V association in MapOrIter in any order. Function fun F/3 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 Init is returned if the map is empty.

+

The call fails with a {badmap,Map} exception if + MapOrIter is not a map or valid iterator, + or with badarg if Fun is not a + function of arity 3.

Example:

> Fun = fun(K,V,AccIn) when is_list(K) -> AccIn + V end, @@ -168,6 +188,75 @@ false + + + Create a map iterator. + +

Returns a map iterator Iterator that can + be used by maps:next/1 + to traverse the keys and values in a map. This call is equivalent + to calling maps:iterator/2 + with an empty map as the options.

+

The call fails with a {badmap,Map} exception if + Map is not a map.

+

Example:

+ +> 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 + + + + + + Create a map iterator. + +

Returns a map iterator Iterator that can + be used by maps:next/1 + to traverse the keys and values in a map. The iterator will behave + according to the given Opts.

+ + optimize + + Configures whether the iterator should be optimized for speed + or for memory consumption. Default is speed. + + ordered + + Configures whether the iterator should return the key value + associations ordered on the keys according to erlang term order + or not. The default is false. + + +

Both options can be configured at the same time.

+

The call fails with a {badmap,Map} exception if + Map is not a map.

+

Example:

+ +> M = maps:from_list([{I,I} || I <- 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} + + + @@ -188,12 +277,16 @@ false -

Produces a new map Map2 by calling function +

Produces a new map Map by calling function fun F(K, V1) for every K to value - V1 association in Map1 in + V1 association in MapOrIter in any order. Function fun F/2 must return value V2 to be associated with key K - for the new map Map2.

+ for the new map Map.

+

The call fails with a {badmap,Map} exception if + MapOrIter is not a map or valid iterator, + or with badarg if Fun is not a + function of arity 2.

Example:

> Fun = fun(K,V1) when is_list(K) -> V1*2 end, @@ -233,6 +326,35 @@ false + + + Get the next key and value from an iterator. + +

Returns the next key-value association in + Iterator and a new iterator for the + remaining associations in the iterator. +

+

+ If there are no more associations in the iterator, + none is returned. +

+

Example:

+ +> 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 + + + 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(#{}), -- cgit v1.2.3