PostgreSQL Source Code  git master
hashutils.h
Go to the documentation of this file.
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 
23 extern Datum hash_any(const unsigned char *k, int keylen);
24 extern Datum hash_any_extended(const unsigned char *k,
25  int keylen, uint64 seed);
26 extern Datum hash_uint32(uint32 k);
27 extern 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  */
35 static inline uint32
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  */
47 static inline uint64
48 hash_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  */
59 static inline uint32
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 */
Datum hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
Definition: hashfn.c:374
static uint32 hash_combine(uint32 a, uint32 b)
Definition: hashutils.h:36
Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.c:148
Datum hash_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:634
Datum hash_uint32(uint32 k)
Definition: hashfn.c:613
unsigned int uint32
Definition: c.h:358
static uint64 hash_combine64(uint64 a, uint64 b)
Definition: hashutils.h:48
uintptr_t Datum
Definition: postgres.h:367
static uint32 murmurhash32(uint32 data)
Definition: hashutils.h:60