aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn-Egil Dahlberg <[email protected]>2013-12-16 17:07:54 +0100
committerBjörn-Egil Dahlberg <[email protected]>2014-01-28 15:56:30 +0100
commitab54731c41f28a21bce526249e582b56106d4965 (patch)
tree8be1c6789780e227fda7ec474fcdc2848f910209
parent912f0f2aae82ee4316a2ee1863775bcf1d8a3ba2 (diff)
downloadotp-ab54731c41f28a21bce526249e582b56106d4965.tar.gz
otp-ab54731c41f28a21bce526249e582b56106d4965.tar.bz2
otp-ab54731c41f28a21bce526249e582b56106d4965.zip
erts: erlang:phash2 should hash Maps independent of order
-rw-r--r--erts/emulator/beam/utils.c63
1 files changed, 55 insertions, 8 deletions
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 3774f379cc..8958d334ae 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -1091,9 +1091,11 @@ Uint32
make_hash2(Eterm term)
{
Uint32 hash;
+ Uint32 hash_xor_keys = 0;
+ Uint32 hash_xor_values = 0;
DeclareTmpHeapNoproc(tmp_big,2);
-/* (HCONST * {2, ..., 14}) mod 2^32 */
+/* (HCONST * {2, ..., 16}) mod 2^32 */
#define HCONST_2 0x3c6ef372UL
#define HCONST_3 0xdaa66d2bUL
#define HCONST_4 0x78dde6e4UL
@@ -1110,6 +1112,10 @@ make_hash2(Eterm term)
#define HCONST_15 0x454021d7UL
#define HCONST_16 0xe3779b90UL
+#define HASH_MAP_TAIL (_make_header(1,_TAG_HEADER_REF))
+#define HASH_MAP_KEY (_make_header(2,_TAG_HEADER_REF))
+#define HASH_MAP_VAL (_make_header(3,_TAG_HEADER_REF))
+
#define UINT32_HASH_2(Expr1, Expr2, AConst) \
do { \
Uint32 a,b; \
@@ -1204,36 +1210,45 @@ make_hash2(Eterm term)
UINT32_HASH(arity, HCONST_9);
if (arity == 0) /* Empty tuple */
goto hash2_common;
- for (i = arity; i >= 2; i--) {
+ for (i = arity; i >= 1; i--) {
tmp = elem[i];
ESTACK_PUSH(s, tmp);
}
- term = elem[1];
+ goto hash2_common;
}
break;
case MAP_SUBTAG:
{
map_t *mp = (map_t *)map_val(term);
int i;
- int size = map_get_size(mp);
+ int size = map_get_size(mp);
Eterm *ks = map_get_keys(mp);
Eterm *vs = map_get_values(mp);
UINT32_HASH(size, HCONST_16);
- if (size == 0) /* Empty Map */
+ if (size == 0) {
goto hash2_common;
-
+ }
+ ESTACK_PUSH(s, hash_xor_values);
+ ESTACK_PUSH(s, hash_xor_keys);
+ ESTACK_PUSH(s, hash);
+ ESTACK_PUSH(s, HASH_MAP_TAIL);
+ hash = 0;
+ hash_xor_keys = 0;
+ hash_xor_values = 0;
for (i = size - 1; i >= 0; i--) {
tmp = vs[i];
+ ESTACK_PUSH(s, HASH_MAP_VAL);
ESTACK_PUSH(s, tmp);
}
/* We do not want to expose the tuple representation.
* Do not push the keys as a tuple.
*/
- for (i = size - 1; i >= 1; i--) {
+ for (i = size - 1; i >= 0; i--) {
tmp = ks[i];
+ ESTACK_PUSH(s, HASH_MAP_KEY);
ESTACK_PUSH(s, tmp);
}
- term = ks[0];
+ goto hash2_common;
}
break;
case EXPORT_SUBTAG:
@@ -1427,15 +1442,47 @@ make_hash2(Eterm term)
default:
erl_exit(1, "Invalid tag in make_hash2(0x%X)\n", term);
hash2_common:
+
+ /* Uint32 hash always has the hash value of the previous term,
+ * compounded or otherwise.
+ */
+
if (ESTACK_ISEMPTY(s)) {
DESTROY_ESTACK(s);
UnUseTmpHeapNoproc(2);
return hash;
}
+
term = ESTACK_POP(s);
+
+ switch (term) {
+ case HASH_MAP_TAIL: {
+ hash = (Uint32) ESTACK_POP(s);
+ UINT32_HASH(hash_xor_keys, HCONST_16);
+ UINT32_HASH(hash_xor_values, HCONST_16);
+ hash_xor_keys = (Uint32) ESTACK_POP(s);
+ hash_xor_values = (Uint32) ESTACK_POP(s);
+ goto hash2_common;
+ }
+ case HASH_MAP_KEY:
+ hash_xor_keys ^= hash;
+ hash = 0;
+ goto hash2_common;
+ case HASH_MAP_VAL:
+ hash_xor_values ^= hash;
+ hash = 0;
+ goto hash2_common;
+ default:
+ break;
+ }
}
}
}
+
+#undef HASH_MAP_TAIL
+#undef HASH_MAP_KEY
+#undef HASH_MAP_VAL
+
#undef UINT32_HASH_2
#undef UINT32_HASH
#undef SINT32_HASH