1/*
2 * Utilities for working with hash values.
3 *
4 * Portions Copyright (c) 2017-2019, PostgreSQL Global Development Group
5 */
6
7#ifndef HASHUTILS_H
8#define HASHUTILS_H
9
10
11/*
12 * Rotate the high 32 bits and the low 32 bits separately. The standard
13 * hash function sometimes rotates the low 32 bits by one bit when
14 * combining elements. We want extended hash functions to be compatible with
15 * that algorithm when the seed is 0, so we can't just do a normal rotation.
16 * This works, though.
17 */
18#define ROTATE_HIGH_AND_LOW_32BITS(v) \
19 ((((v) << 1) & UINT64CONST(0xfffffffefffffffe)) | \
20 (((v) >> 31) & UINT64CONST(0x100000001)))
21
22
23extern Datum hash_any(register const unsigned char *k, register int keylen);
24extern Datum hash_any_extended(register const unsigned char *k,
25 register int keylen, uint64 seed);
26extern Datum hash_uint32(uint32 k);
27extern Datum hash_uint32_extended(uint32 k, uint64 seed);
28
29/*
30 * Combine two 32-bit hash values, resulting in another hash value, with
31 * decent bit mixing.
32 *
33 * Similar to boost's hash_combine().
34 */
35static inline uint32
36hash_combine(uint32 a, uint32 b)
37{
38 a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
39 return a;
40}
41
42/*
43 * Combine two 64-bit hash values, resulting in another hash value, using the
44 * same kind of technique as hash_combine(). Testing shows that this also
45 * produces good bit mixing.
46 */
47static inline uint64
48hash_combine64(uint64 a, uint64 b)
49{
50 /* 0x49a0f4dd15e5a8e3 is 64bit random data */
51 a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
52 return a;
53}
54
55/*
56 * Simple inline murmur hash implementation hashing a 32 bit integer, for
57 * performance.
58 */
59static inline uint32
60murmurhash32(uint32 data)
61{
62 uint32 h = data;
63
64 h ^= h >> 16;
65 h *= 0x85ebca6b;
66 h ^= h >> 13;
67 h *= 0xc2b2ae35;
68 h ^= h >> 16;
69 return h;
70}
71
72#endif /* HASHUTILS_H */
73