aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--erts/emulator/beam/erl_map.c10
-rw-r--r--erts/emulator/test/map_SUITE.erl45
2 files changed, 50 insertions, 5 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index ab40f47919..a8e8ad346b 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -89,7 +89,7 @@ static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size);
static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size);
static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys);
static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
-static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
+static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, Uint size, int is_root);
static Eterm hashmap_info(Process *p, Eterm node);
static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
static int hxnodecmp(hxnode_t* a, hxnode_t* b);
@@ -661,7 +661,7 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
ix++;
}
- res = hashmap_from_chunked_array(factory, hxns, elems, !lvl);
+ res = hashmap_from_chunked_array(factory, hxns, elems, n, !lvl);
ERTS_FACTORY_HOLE_CHECK(factory);
@@ -669,8 +669,8 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
}
#define HALLOC_EXTRA 200
-static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
- hxnode_t *hxns, Uint n, int is_root) {
+static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns, Uint n,
+ Uint size, int is_root) {
Uint ix, d, dn, dc, slot, elems;
Uint32 v, vp, vn, hdr;
Uint bp, sz;
@@ -840,7 +840,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
if (is_root) {
*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
- *hp++ = n;
+ *hp++ = size;
} else {
*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
}
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 04c12d3e14..bc649d5808 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -650,6 +650,17 @@ t_map_size(Config) when is_list(Config) ->
Ks = [build_key(fun(K) -> <<1,K:32,1>> end,I)||I<-lists:seq(1,100)],
ok = build_and_check_size(Ks,0,#{}),
+ %% try deep collisions
+ %% statistically we get another subtree at 50k -> 100k elements
+ %% Try to be nice and don't use too much memory in the testcase,
+
+ N = 500000,
+ Is = lists:seq(1,N),
+ N = map_size(maps:from_list([{I,I}||I<-Is])),
+ N = map_size(maps:from_list([{<<I:32>>,I}||I<-Is])),
+ N = map_size(maps:from_list([{integer_to_list(I),I}||I<-Is])),
+ N = map_size(maps:from_list([{float(I),I}||I<-Is])),
+
%% Error cases.
{'EXIT',{badarg,_}} = (catch map_size([])),
{'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
@@ -1820,6 +1831,40 @@ t_bif_map_merge(Config) when is_list(Config) ->
#{4 := integer, 18446744073709551629 := wat, float := 3.3, int := 3,
{1,2} := "tuple", "hi" := "hello again", <<"key">> := <<"value">>} = maps:merge(M0,M1),
+ %% try deep collisions
+ N = 150000,
+ Is = lists:seq(1,N),
+ M2 = maps:from_list([{I,I}||I<-Is]),
+ 150000 = maps:size(M2),
+ M3 = maps:from_list([{<<I:32>>,I}||I<-Is]),
+ 150000 = maps:size(M3),
+ M4 = maps:merge(M2,M3),
+ 300000 = maps:size(M4),
+ M5 = maps:from_list([{integer_to_list(I),I}||I<-Is]),
+ 150000 = maps:size(M5),
+ M6 = maps:merge(M4,M5),
+ 450000 = maps:size(M6),
+ M7 = maps:from_list([{float(I),I}||I<-Is]),
+ 150000 = maps:size(M7),
+ M8 = maps:merge(M7,M6),
+ 600000 = maps:size(M8),
+
+ #{ 1 := 1, "1" := 1, <<1:32>> := 1 } = M8,
+ #{ 10 := 10, "10" := 10, <<10:32>> := 10 } = M8,
+ #{ 100 := 100, "100" := 100, <<100:32>> := 100 } = M8,
+ #{ 1000 := 1000, "1000" := 1000, <<1000:32>> := 1000 } = M8,
+ #{ 10000 := 10000, "10000" := 10000, <<10000:32>> := 10000 } = M8,
+ #{ 100000 := 100000, "100000" := 100000, <<100000:32>> := 100000 } = M8,
+
+ %% overlapping
+ M8 = maps:merge(M2,M8),
+ M8 = maps:merge(M3,M8),
+ M8 = maps:merge(M4,M8),
+ M8 = maps:merge(M5,M8),
+ M8 = maps:merge(M6,M8),
+ M8 = maps:merge(M7,M8),
+ M8 = maps:merge(M8,M8),
+
%% error case
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),