granicus.if.org Git - postgresql/blob - src/include/utils/hashutils.h

   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
  36 hash_combine(uint32 a, uint32 b)
  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
  60 murmurhash32(uint32 data)
  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 */