TLA  Line data    Source code

       1                 : /*
       2                 :  * Utilities for working with hash values.
       3                 :  *
       4                 :  * Portions Copyright (c) 2017-2023, 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 CBC    12179183 : hash_any(const unsigned char *k, int keylen)
      32                 : {
      33        12179183 :     return UInt32GetDatum(hash_bytes(k, keylen));
      34                 : }
      35                 : 
      36                 : static inline Datum
      37         2563029 : hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
      38                 : {
      39         2563029 :     return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
      40                 : }
      41                 : 
      42                 : static inline Datum
      43        27653513 : hash_uint32(uint32 k)
      44                 : {
      45        27653513 :     return UInt32GetDatum(hash_bytes_uint32(k));
      46                 : }
      47                 : 
      48                 : static inline Datum
      49          106947 : hash_uint32_extended(uint32 k, uint64 seed)
      50                 : {
      51          106947 :     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        12984643 : hash_combine(uint32 a, uint32 b)
      69                 : {
      70        12984643 :     a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
      71        12984643 :     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          108462 : hash_combine64(uint64 a, uint64 b)
      81                 : {
      82                 :     /* 0x49a0f4dd15e5a8e3 is 64bit random data */
      83          108462 :     a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
      84          108462 :     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       103423363 : murmurhash32(uint32 data)
      93                 : {
      94       103423363 :     uint32      h = data;
      95                 : 
      96       103423363 :     h ^= h >> 16;
      97       103423363 :     h *= 0x85ebca6b;
      98       103423363 :     h ^= h >> 13;
      99       103423363 :     h *= 0xc2b2ae35;
     100       103423363 :     h ^= h >> 16;
     101       103423363 :     return h;
     102                 : }
     103                 : 
     104                 : #endif                          /* HASHFN_H */