PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
hashfn.h
Go to the documentation of this file.
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
23extern uint32 hash_bytes(const unsigned char *k, int keylen);
24extern uint64 hash_bytes_extended(const unsigned char *k,
25 int keylen, uint64 seed);
28
29#ifndef FRONTEND
30static inline Datum
31hash_any(const unsigned char *k, int keylen)
32{
33 return UInt32GetDatum(hash_bytes(k, keylen));
34}
35
36static inline Datum
37hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
38{
39 return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
40}
41
42static inline Datum
44{
46}
47
48static inline Datum
50{
52}
53#endif
54
55extern uint32 string_hash(const void *key, Size keysize);
56extern uint32 tag_hash(const void *key, Size keysize);
57extern 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 */
67static 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 */
79static inline uint64
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 */
91static 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/* 64-bit variant */
105static inline uint64
107{
108 uint64 h = data;
109
110 h ^= h >> 33;
111 h *= 0xff51afd7ed558ccd;
112 h ^= h >> 33;
113 h *= 0xc4ceb9fe1a85ec53;
114 h ^= h >> 33;
115
116 return h;
117}
118
119#endif /* HASHFN_H */
uint64_t uint64
Definition: c.h:486
uint32_t uint32
Definition: c.h:485
#define UINT64CONST(x)
Definition: c.h:500
size_t Size
Definition: c.h:559
static uint64 hash_combine64(uint64 a, uint64 b)
Definition: hashfn.h:80
uint32 hash_bytes_uint32(uint32 k)
Definition: hashfn.c:610
uint64 hash_bytes_extended(const unsigned char *k, int keylen, uint64 seed)
Definition: hashfn.c:372
static uint64 murmurhash64(uint64 data)
Definition: hashfn.h:106
static Datum hash_uint32(uint32 k)
Definition: hashfn.h:43
static uint32 hash_combine(uint32 a, uint32 b)
Definition: hashfn.h:68
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
uint32 hash_bytes(const unsigned char *k, int keylen)
Definition: hashfn.c:146
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:677
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631
static Datum hash_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.h:49
uint32 uint32_hash(const void *key, Size keysize)
Definition: hashfn.c:688
uint32 string_hash(const void *key, Size keysize)
Definition: hashfn.c:660
int b
Definition: isn.c:69
int a
Definition: isn.c:68
const void * data
uintptr_t Datum
Definition: postgres.h:64
static Datum UInt64GetDatum(uint64 X)
Definition: postgres.h:436
static Datum UInt32GetDatum(uint32 X)
Definition: postgres.h:232