diff options
| author | Björn-Egil Dahlberg <[email protected]> | 2013-12-16 17:07:54 +0100 |
|---|---|---|
| committer | Björn-Egil Dahlberg <[email protected]> | 2014-01-28 15:56:30 +0100 |
| commit | ab54731c41f28a21bce526249e582b56106d4965 (patch) | |
| tree | 8be1c6789780e227fda7ec474fcdc2848f910209 | |
| parent | 912f0f2aae82ee4316a2ee1863775bcf1d8a3ba2 (diff) | |
| download | otp-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.c | 63 |
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 |