PostgreSQL Source Code  git master
hashfn.h
Go to the documentation of this file.
1 /*
2  * Utilities for working with hash values.
3  *
4  * Portions Copyright (c) 2017-2020, 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);
27 extern uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed);
28 
29 #ifndef FRONTEND
30 static inline Datum
31 hash_any(const unsigned char *k, int keylen)
32 {
33  return UInt32GetDatum(hash_bytes(k, keylen));
34 }
35 
36 static inline Datum
37 hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
38 {
39  return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
40 }
41 
42 static inline Datum
44 {
46 }
47 
48 static inline Datum
50 {
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
69 {
70  a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
71  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
80 hash_combine64(uint64 a, uint64 b)
81 {
82  /* 0x49a0f4dd15e5a8e3 is 64bit random data */
83  a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
84  return a;
85 }
86 
87 /*
88  * Simple inline murmur hash implementation hashing a 32 bit integer, for
89  * performance.
90  */
91 static inline uint32
93 {
94  uint32 h = data;
95 
96  h ^= h >> 16;
97  h *= 0x85ebca6b;
98  h ^= h >> 13;
99  h *= 0xc2b2ae35;
100  h ^= h >> 16;
101  return h;
102 }
103 
104 #endif /* HASHFN_H */
uint64 hash_bytes_extended(const unsigned char *k, int keylen, uint64 seed)
Definition: hashfn.c:372
uint32 string_hash(const void *key, Size keysize)
Definition: hashfn.c:660
#define UInt64GetDatum(X)
Definition: postgres.h:648
static uint32 murmurhash32(uint32 data)
Definition: hashfn.h:92
static Datum hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
Definition: hashfn.h:37
static uint64 hash_combine64(uint64 a, uint64 b)
Definition: hashfn.h:80
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:677
unsigned int uint32
Definition: c.h:374
#define UInt32GetDatum(X)
Definition: postgres.h:493
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
uint32 hash_bytes(const unsigned char *k, int keylen)
Definition: hashfn.c:146
static uint32 hash_combine(uint32 a, uint32 b)
Definition: hashfn.h:68
uintptr_t Datum
Definition: postgres.h:367
uint32 uint32_hash(const void *key, Size keysize)
Definition: hashfn.c:688
static Datum hash_uint32(uint32 k)
Definition: hashfn.h:43
size_t Size
Definition: c.h:473
uint32 hash_bytes_uint32(uint32 k)
Definition: hashfn.c:610
static Datum hash_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.h:49
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631