aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/erl_map.c41
-rw-r--r--erts/emulator/beam/erl_term.h1
-rw-r--r--erts/emulator/beam/utils.c29
-rw-r--r--erts/emulator/test/hash_SUITE.erl27
-rw-r--r--erts/emulator/test/map_SUITE.erl25
5 files changed, 105 insertions, 18 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index cca287c753..98023bbb47 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -568,14 +568,14 @@ static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory,
while(ix < jx) {
lx = ix;
- while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) {
+ while(++ix < jx && EQ(CAR(list_val(hxns[ix].val)),
+ CAR(list_val(hxns[lx].val)))) {
if (reject_dupkeys)
return THE_NON_VALUE;
if (hxns[ix].i > hxns[lx].i) {
lx = ix;
}
- ix++;
}
hxns[cx].hx = hxns[lx].hx;
hxns[cx].val = hxns[lx].val;
@@ -679,7 +679,35 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns
DECLARE_ESTACK(stack);
Eterm res = NIL, *hp = NULL, *nhp;
- ASSERT(n > 1);
+
+ /* if we get here with only one element then
+ * we have eight levels of collisions
+ */
+
+ if (n == 1) {
+ res = hxns[0].val;
+ v = hxns[0].hx;
+ for (d = 7; d > 0; d--) {
+ slot = maskval(v,d);
+ hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << slot);
+ hp[1] = res;
+ res = make_hashmap(hp);
+ }
+
+ slot = maskval(v,0);
+ hp = erts_produce_heap(factory, (is_root ? 3 : 2), 0);
+
+ if (is_root) {
+ hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << slot);
+ hp[1] = size;
+ hp[2] = res;
+ } else {
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << slot);
+ hp[1] = res;
+ }
+ return make_hashmap(hp);
+ }
/* push initial nodes on the stack,
* this is the starting depth */
@@ -860,7 +888,12 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns
#undef HALLOC_EXTRA
static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) {
- return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
+ Sint c = CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
+#if ERTS_SIZEOF_ETERM <= SIZEOF_INT
+ return c;
+#else
+ return c > 0 ? 1 : (c < 0 ? -1 : 0);
+#endif
}
static int hxnodecmp(hxnode_t *a, hxnode_t *b) {
diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h
index 095aa54ddd..cff012d5d1 100644
--- a/erts/emulator/beam/erl_term.h
+++ b/erts/emulator/beam/erl_term.h
@@ -298,7 +298,6 @@ _ET_DECLARE_CHECKED(Uint,atom_val,Eterm)
/* header (arityval or thing) access methods */
#define _make_header(sz,tag) ((Uint)(((Uint)(sz) << _HEADER_ARITY_OFFS) + (tag)))
#define is_header(x) (((x) & _TAG_PRIMARY_MASK) == TAG_PRIMARY_HEADER)
-//#define _unchecked_header_arity(x) ((x) >> _HEADER_ARITY_OFFS)
#define _unchecked_header_arity(x) \
(is_map_header(x) ? MAP_HEADER_ARITY(x) : ((x) >> _HEADER_ARITY_OFFS))
_ET_DECLARE_CHECKED(Uint,header_arity,Eterm)
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index bf6d9fff50..aecfe04a75 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -955,12 +955,14 @@ tail_recur:
UINT32_HASH_RET(external_ref_numbers(term)[0],FUNNY_NUMBER9,FUNNY_NUMBER10);
case FLOAT_DEF:
{
- FloatDef ff;
- GET_DOUBLE(term, ff);
- hash = hash*FUNNY_NUMBER6 + (ff.fw[0] ^ ff.fw[1]);
- break;
+ FloatDef ff;
+ GET_DOUBLE(term, ff);
+ if (ff.fd == 0.0f) {
+ ff.fd = 0.0f; /* ensure pos. 0.0 */
+ }
+ hash = hash*FUNNY_NUMBER6 + (ff.fw[0] ^ ff.fw[1]);
+ break;
}
-
case MAKE_HASH_CDR_PRE_OP:
term = (Eterm) WSTACK_POP(stack);
if (is_not_list(term)) {
@@ -1474,6 +1476,9 @@ make_hash2(Eterm term)
{
FloatDef ff;
GET_DOUBLE(term, ff);
+ if (ff.fd == 0.0f) {
+ ff.fd = 0.0f; /* ensure pos. 0.0 */
+ }
#if defined(WORDS_BIGENDIAN) || defined(DOUBLE_MIDDLE_ENDIAN)
UINT32_HASH_2(ff.fw[0], ff.fw[1], HCONST_12);
#else
@@ -1893,8 +1898,8 @@ make_internal_hash(Eterm term)
{
FloatDef ff;
GET_DOUBLE(term, ff);
- if (ff.fd == 0.0) {
- ff.fd = 0.0; /* ensure pos. 0.0 */
+ if (ff.fd == 0.0f) {
+ ff.fd = 0.0f; /* ensure pos. 0.0 */
}
UINT32_HASH_2(ff.fw[0], ff.fw[1], HCONST_12);
goto pop_next;
@@ -2079,12 +2084,14 @@ tail_recur:
break;
case FLOAT_DEF:
{
- FloatDef ff;
- GET_DOUBLE(term, ff);
- hash = hash*FUNNY_NUMBER6 + (ff.fw[0] ^ ff.fw[1]);
+ FloatDef ff;
+ GET_DOUBLE(term, ff);
+ if (ff.fd == 0.0f) {
+ ff.fd = 0.0f; /* ensure pos. 0.0 */
+ }
+ hash = hash*FUNNY_NUMBER6 + (ff.fw[0] ^ ff.fw[1]);
}
break;
-
case MAKE_HASH_CDR_PRE_OP:
term = (Eterm) WSTACK_POP(stack);
if (is_not_list(term)) {
diff --git a/erts/emulator/test/hash_SUITE.erl b/erts/emulator/test/hash_SUITE.erl
index 647bb45049..5fa45f772d 100644
--- a/erts/emulator/test/hash_SUITE.erl
+++ b/erts/emulator/test/hash_SUITE.erl
@@ -73,6 +73,7 @@ config(priv_dir,_) ->
init_per_group/2,end_per_group/2,
test_basic/1,test_cmp/1,test_range/1,test_spread/1,
test_phash2/1,otp_5292/1,bit_level_binaries/1,otp_7127/1,
+ test_hash_zero/1,
end_per_testcase/2,init_per_testcase/2]).
init_per_testcase(_Case, Config) ->
Dog=test_server:timetrap(test_server:minutes(10)),
@@ -86,7 +87,9 @@ suite() -> [{ct_hooks,[ts_install_cth]}].
all() ->
[test_basic, test_cmp, test_range, test_spread,
- test_phash2, otp_5292, bit_level_binaries, otp_7127].
+ test_phash2, otp_5292, bit_level_binaries, otp_7127,
+ test_hash_zero
+ ].
groups() ->
[].
@@ -160,6 +163,8 @@ otp_7127(doc) ->
otp_7127(Config) when is_list(Config) ->
otp_7127_test().
+test_hash_zero(Config) when is_list(Config) ->
+ hash_zero_test().
-endif.
@@ -591,6 +596,26 @@ otp_7127_test() ->
38990304 = erlang:phash2(<<"Scott9">>),
ok.
+hash_zero_test() ->
+ Zs = [0.0, -0.0, 0/-1, 0.0/-1, 0/-(1 bsl 65),
+ binary_to_term(<<131,70,0,0,0,0,0,0,0,0>>), %% +0.0
+ binary_to_term(<<131,70,128,0,0,0,0,0,0,0>>)], %% -0.0
+ ok = hash_zero_test(Zs,fun(T) -> erlang:phash2(T, 1 bsl 32) end),
+ ok = hash_zero_test(Zs,fun(T) -> erlang:phash(T, 1 bsl 32) end),
+ ok = hash_zero_test(Zs,fun(T) -> erlang:hash(T, (1 bsl 27) - 1) end),
+ ok.
+
+hash_zero_test([Z|Zs],F) ->
+ hash_zero_test(Zs,Z,F(Z),F).
+hash_zero_test([Z|Zs],Z0,V,F) ->
+ true = Z0 =:= Z, %% assert exact equal
+ Z0 = Z, %% assert matching
+ V = F(Z), %% assert hash
+ hash_zero_test(Zs,Z0,V,F);
+hash_zero_test([],_,_,_) ->
+ ok.
+
+
%%
%% Reference implementation of integer hashing
%%
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index dc6286fdb6..ad8411cd68 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -1888,11 +1888,19 @@ t_bif_map_merge(Config) when is_list(Config) ->
M8 = maps:merge(M7,M8),
M8 = maps:merge(M8,M8),
+ %% maps:merge/2 and mixed
+
+ Ks1 = [764492191,2361333849], %% deep collision
+ Ks2 = lists:seq(1,33),
+ M9 = maps:from_list([{K,K}||K <- Ks1]),
+ M10 = maps:from_list([{K,K}||K <- Ks2]),
+ M11 = maps:merge(M9,M10),
+ ok = check_keys_exist(Ks1 ++ Ks2, M11),
+
%% error case
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(id(#{ a => 2}), <<>> )),
-
ok.
@@ -2026,6 +2034,14 @@ t_bif_map_values(Config) when is_list(Config) ->
true = is_members([number,3,"hello2",<<"value2">>],maps:values(M2)),
true = is_members([number,3,"hello",<<"value">>],maps:values(M1)),
+ Vs = lists:seq(1000,20000),
+ M3 = maps:from_list([{K,K}||K<-Vs]),
+ M4 = maps:merge(M1,M3),
+ M5 = maps:merge(M2,M3),
+ true = is_members(Vs,maps:values(M3)),
+ true = is_members([number,3,"hello",<<"value">>]++Vs,maps:values(M4)),
+ true = is_members([number,3,"hello2",<<"value2">>]++Vs,maps:values(M5)),
+
%% error case
{'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(1 bsl 65 + 3)),
{'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(atom)),
@@ -2252,6 +2268,13 @@ t_bif_map_from_list(Config) when is_list(Config) ->
maps:from_list([ {{hi,3},v3}, {"hi",v0},{3,v1}, {<<"hi">>,v4}, {hi,v2},
{<<"hi">>,v6}, {{hi,3},v10},{"hi",v11}, {hi,v9}, {3,v8}]),
+ %% repeated keys (large -> small)
+ Ps1 = [{a,I}|| I <- lists:seq(1,32)],
+ Ps2 = [{a,I}|| I <- lists:seq(33,64)],
+
+ M = maps:from_list(Ps1 ++ [{b,1},{c,1}] ++ Ps2),
+ #{ a := 64, b := 1, c := 1 } = M,
+
%% error cases
{'EXIT', {badarg,_}} = (catch maps:from_list(id([{a,b},b]))),
{'EXIT', {badarg,_}} = (catch maps:from_list(id([{a,b},{b,b,3}]))),
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-17 10:59:41 +0000