aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorLukas Larsson <[email protected]>2017-09-19 14:37:59 +0200
committerLukas Larsson <[email protected]>2017-10-13 15:44:33 +0200
commit513a322941d208d9dcdc4c39db2966ae4c707fe7 (patch)
tree05662bd1e66cd34b373f2b69fd7f26649610ecb3 /lib
parentd945d6f1c71d5442a25e4be60f84fc49ae8b6b4e (diff)
downloadotp-513a322941d208d9dcdc4c39db2966ae4c707fe7.tar.gz
otp-513a322941d208d9dcdc4c39db2966ae4c707fe7.tar.bz2
otp-513a322941d208d9dcdc4c39db2966ae4c707fe7.zip
erts: Implement map iterator using a stack
This version does not work great as the subtrees created are not proper hash maps. Also it is not all that performant as the extra allocations to keep the stack there is expensive.
Diffstat (limited to 'lib')
-rw-r--r--lib/stdlib/src/maps.erl13
1 files changed, 11 insertions, 2 deletions
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 7ed32a3988..0da12cf8e2 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -32,7 +32,7 @@
new/0, put/3, remove/2, take/2,
to_list/1, update/3, values/1]).
--opaque iterator() :: [{term(), term()}].
+-opaque iterator() :: [{term(), term()}] | [[pos_integer() | map()]].
-export_type([iterator/0]).
@@ -279,7 +279,10 @@ size(Val) ->
Iterator :: iterator().
iterator(Map) when is_map(Map) ->
- maps:to_list(Map);
+ case maps:size(Map) < 42 of
+ true -> maps:to_list(Map);
+ false -> [[1 | Map]]
+ end;
iterator(M) ->
erlang:error(error_type(M),[M]).
@@ -289,6 +292,12 @@ iterator(M) ->
V :: 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}.