Line data    Source code

       1              : /*
       2              :  * Utilities for working with hash values.
       3              :  *
       4              :  * Portions Copyright (c) 2017-2026, 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       545972 : hash_any(const unsigned char *k, int keylen)
      32              : {
      33       545972 :         return UInt32GetDatum(hash_bytes(k, keylen));
      34              : }
      35              : 
      36              : static inline Datum
      37          825 : hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
      38              : {
      39          825 :         return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
      40              : }
      41              : 
      42              : static inline Datum
      43      6297361 : hash_uint32(uint32 k)
      44              : {
      45      6297361 :         return UInt32GetDatum(hash_bytes_uint32(k));
      46              : }
      47              : 
      48              : static inline Datum
      49          252 : hash_uint32_extended(uint32 k, uint64 seed)
      50              : {
      51          252 :         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       108578 : hash_combine(uint32 a, uint32 b)
      69              : {
      70       108578 :         a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
      71       108578 :         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       144209 : hash_combine64(uint64 a, uint64 b)
      81              : {
      82              :         /* 0x49a0f4dd15e5a8e3 is 64bit random data */
      83       144209 :         a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
      84       144209 :         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     17119529 : murmurhash32(uint32 data)
      93              : {
      94     17119529 :         uint32          h = data;
      95              : 
      96     17119529 :         h ^= h >> 16;
      97     17119529 :         h *= 0x85ebca6b;
      98     17119529 :         h ^= h >> 13;
      99     17119529 :         h *= 0xc2b2ae35;
     100     17119529 :         h ^= h >> 16;
     101     34239058 :         return h;
     102     17119529 : }
     103              : 
     104              : /* 64-bit variant */
     105              : static inline uint64
     106       143350 : murmurhash64(uint64 data)
     107              : {
     108       143350 :         uint64          h = data;
     109              : 
     110       143350 :         h ^= h >> 33;
     111       143350 :         h *= 0xff51afd7ed558ccd;
     112       143350 :         h ^= h >> 33;
     113       143350 :         h *= 0xc4ceb9fe1a85ec53;
     114       143350 :         h ^= h >> 33;
     115              : 
     116       286700 :         return h;
     117       143350 : }
     118              : 
     119              : #endif                                                  /* HASHFN_H */