Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * Utilities for working with hash values.
3 : : *
4 : : * Portions Copyright (c) 2017-2024, PostgreSQL Global Development Group
5 : : */
6 : :
7 : : #ifndef HASHFN_H
8 : : #define HASHFN_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 : :
23 : : extern uint32 hash_bytes(const unsigned char *k, int keylen);
24 : : extern uint64 hash_bytes_extended(const unsigned char *k,
25 : : int keylen, uint64 seed);
26 : : extern uint32 hash_bytes_uint32(uint32 k);
27 : : extern uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed);
28 : :
29 : : #ifndef FRONTEND
30 : : static inline Datum
1511 rhaas@postgresql.org 31 :CBC 6230596 : hash_any(const unsigned char *k, int keylen)
32 : : {
33 : 6230596 : return UInt32GetDatum(hash_bytes(k, keylen));
34 : : }
35 : :
36 : : static inline Datum
37 : 2819437 : hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
38 : : {
39 : 2819437 : return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
40 : : }
41 : :
42 : : static inline Datum
43 : 25033758 : hash_uint32(uint32 k)
44 : : {
45 : 25033758 : return UInt32GetDatum(hash_bytes_uint32(k));
46 : : }
47 : :
48 : : static inline Datum
49 : 104997 : hash_uint32_extended(uint32 k, uint64 seed)
50 : : {
51 : 104997 : return UInt64GetDatum(hash_bytes_uint32_extended(k, seed));
52 : : }
53 : : #endif
54 : :
55 : : extern uint32 string_hash(const void *key, Size keysize);
56 : : extern uint32 tag_hash(const void *key, Size keysize);
57 : : extern uint32 uint32_hash(const void *key, Size keysize);
58 : :
59 : : #define oid_hash uint32_hash /* Remove me eventually */
60 : :
61 : : /*
62 : : * Combine two 32-bit hash values, resulting in another hash value, with
63 : : * decent bit mixing.
64 : : *
65 : : * Similar to boost's hash_combine().
66 : : */
67 : : static inline uint32
2427 andres@anarazel.de 68 : 2903524 : hash_combine(uint32 a, uint32 b)
69 : : {
70 : 2903524 : a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
71 : 2903524 : return a;
72 : : }
73 : :
74 : : /*
75 : : * Combine two 64-bit hash values, resulting in another hash value, using the
76 : : * same kind of technique as hash_combine(). Testing shows that this also
77 : : * produces good bit mixing.
78 : : */
79 : : static inline uint64
2359 rhaas@postgresql.org 80 : 1756717 : hash_combine64(uint64 a, uint64 b)
81 : : {
82 : : /* 0x49a0f4dd15e5a8e3 is 64bit random data */
2350 tgl@sss.pgh.pa.us 83 : 1756717 : a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
2359 rhaas@postgresql.org 84 : 1756717 : return a;
85 : : }
86 : :
87 : : /*
88 : : * Simple inline murmur hash implementation hashing a 32 bit integer, for
89 : : * performance.
90 : : */
91 : : static inline uint32
2396 andres@anarazel.de 92 : 66214934 : murmurhash32(uint32 data)
93 : : {
94 : 66214934 : uint32 h = data;
95 : :
96 : 66214934 : h ^= h >> 16;
97 : 66214934 : h *= 0x85ebca6b;
98 : 66214934 : h ^= h >> 13;
99 : 66214934 : h *= 0xc2b2ae35;
100 : 66214934 : h ^= h >> 16;
101 : 66214934 : return h;
102 : : }
103 : :
104 : : /* 64-bit variant */
105 : : static inline uint64
158 heikki.linnakangas@i 106 :GNC 1647926 : murmurhash64(uint64 data)
107 : : {
108 : 1647926 : uint64 h = data;
109 : :
110 : 1647926 : h ^= h >> 33;
111 : 1647926 : h *= 0xff51afd7ed558ccd;
112 : 1647926 : h ^= h >> 33;
113 : 1647926 : h *= 0xc4ceb9fe1a85ec53;
114 : 1647926 : h ^= h >> 33;
115 : :
116 : 1647926 : return h;
117 : : }
118 : :
119 : : #endif /* HASHFN_H */
|
