Line data    Source code

       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    12162620 : hash_any(const unsigned char *k, int keylen)
      32             : {
      33    12162620 :     return UInt32GetDatum(hash_bytes(k, keylen));
      34             : }
      35             : 
      36             : static inline Datum
      37     5641332 : hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
      38             : {
      39     5641332 :     return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
      40             : }
      41             : 
      42             : static inline Datum
      43    47813730 : hash_uint32(uint32 k)
      44             : {
      45    47813730 :     return UInt32GetDatum(hash_bytes_uint32(k));
      46             : }
      47             : 
      48             : static inline Datum
      49      213994 : hash_uint32_extended(uint32 k, uint64 seed)
      50             : {
      51      213994 :     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     5179360 : hash_combine(uint32 a, uint32 b)
      69             : {
      70     5179360 :     a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
      71     5179360 :     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     3511696 : hash_combine64(uint64 a, uint64 b)
      81             : {
      82             :     /* 0x49a0f4dd15e5a8e3 is 64bit random data */
      83     3511696 :     a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
      84     3511696 :     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   128878972 : murmurhash32(uint32 data)
      93             : {
      94   128878972 :     uint32      h = data;
      95             : 
      96   128878972 :     h ^= h >> 16;
      97   128878972 :     h *= 0x85ebca6b;
      98   128878972 :     h ^= h >> 13;
      99   128878972 :     h *= 0xc2b2ae35;
     100   128878972 :     h ^= h >> 16;
     101   128878972 :     return h;
     102             : }
     103             : 
     104             : /* 64-bit variant */
     105             : static inline uint64
     106     3294114 : murmurhash64(uint64 data)
     107             : {
     108     3294114 :     uint64      h = data;
     109             : 
     110     3294114 :     h ^= h >> 33;
     111     3294114 :     h *= 0xff51afd7ed558ccd;
     112     3294114 :     h ^= h >> 33;
     113     3294114 :     h *= 0xc4ceb9fe1a85ec53;
     114     3294114 :     h ^= h >> 33;
     115             : 
     116     3294114 :     return h;
     117             : }
     118             : 
     119             : #endif                          /* HASHFN_H */