diff options
-rw-r--r-- | erts/emulator/beam/bif.tab | 8 | ||||
-rw-r--r-- | erts/emulator/beam/erl_map.c | 288 | ||||
-rw-r--r-- | erts/emulator/beam/erl_map.h | 4 | ||||
-rw-r--r-- | erts/emulator/test/map_SUITE.erl | 51 | ||||
-rw-r--r-- | erts/preloaded/ebin/erts_internal.beam | bin | 11872 -> 12100 bytes | |||
-rw-r--r-- | erts/preloaded/src/erts_internal.erl | 13 | ||||
-rw-r--r-- | lib/dialyzer/test/small_SUITE_data/results/maps_sum | 2 | ||||
-rw-r--r-- | lib/stdlib/doc/src/maps.xml | 138 | ||||
-rw-r--r-- | lib/stdlib/src/maps.erl | 91 | ||||
-rw-r--r-- | lib/stdlib/test/maps_SUITE.erl | 63 |
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 Binary files differindex 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 <- 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(#{}), |