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 --- erts/emulator/beam/bif.tab | 8 +- erts/emulator/beam/erl_map.c | 288 +++++++++++++++++---- erts/emulator/beam/erl_map.h | 4 +- erts/emulator/test/map_SUITE.erl | 51 ++++ erts/preloaded/ebin/erts_internal.beam | Bin 11872 -> 12100 bytes erts/preloaded/src/erts_internal.erl | 13 +- .../test/small_SUITE_data/results/maps_sum | 2 +- lib/stdlib/doc/src/maps.xml | 138 +++++++++- lib/stdlib/src/maps.erl | 91 ++++--- 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 index 5416826f19..015508d326 100644 Binary files a/erts/preloaded/ebin/erts_internal.beam and b/erts/preloaded/ebin/erts_internal.beam differ 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 @@

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