src/include/common/hashfn.h

   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
  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
  43 hash_uint32(uint32 k)
  44 {
  45         return UInt32GetDatum(hash_bytes_uint32(k));
  46 }
  47
  48 static inline Datum
  49 hash_uint32_extended(uint32 k, uint64 seed)
  50 {
  51         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
  68 hash_combine(uint32 a, uint32 b)
  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
  92 murmurhash32(uint32 data)
  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 */
 105 static inline uint64
 106 murmurhash64(uint64 data)
 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 */