Line data    Source code

       1             : // SPDX-License-Identifier: BSD-2-Clause
       2             : // Copyright (C) 2010 Andrea Mazzoleni
       3             : 
       4             : /** \file
       5             :  * Hash functions for the use with ::tommy_hashtable, ::tommy_hashdyn and ::tommy_hashlin.
       6             :  */
       7             : 
       8             : #ifndef __TOMMYHASH_H
       9             : #define __TOMMYHASH_H
      10             : 
      11             : #include "tommytypes.h"
      12             : 
      13             : /******************************************************************************/
      14             : /* hash */
      15             : 
      16             : /**
      17             :  * Hash function with a 32 bits result.
      18             :  * Implementation of the Robert Jenkins "lookup3" hash 32 bits version,
      19             :  * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle().
      20             :  *
      21             :  * This hash is designed to provide a good overall performance on all platforms,
      22             :  * including 32 bits. If you target only 64 bits, you can use faster hashes,
      23             :  * like SpookyHash or FarmHash.
      24             :  *
      25             :  * \param init_val Initialization value.
      26             :  * Using a different initialization value, you can generate a completely different set of hash values.
      27             :  * Use 0 if not relevant.
      28             :  * \param void_key Pointer to the data to hash.
      29             :  * \param key_len Size of the data to hash.
      30             :  * \note
      31             :  * This function is endianness independent.
      32             :  * \return The hash value of 32 bits.
      33             :  */
      34             : TOMMY_API tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len);
      35             : 
      36             : /**
      37             :  * Hash function with a 64 bits result.
      38             :  * Implementation of the Robert Jenkins "lookup3" hash 64 bits version,
      39             :  * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle2().
      40             :  *
      41             :  * This hash is designed to provide a good overall performance on all platforms,
      42             :  * including 32 bits. If you target only 64 bits, you can use faster hashes,
      43             :  * like SpookyHash or FarmHash.
      44             :  *
      45             :  * \param init_val Initialization value.
      46             :  * Using a different initialization value, you can generate a completely different set of hash values.
      47             :  * Use 0 if not relevant.
      48             :  * \param void_key Pointer to the data to hash.
      49             :  * \param key_len Size of the data to hash.
      50             :  * \note
      51             :  * This function is endianness independent.
      52             :  * \return The hash value of 64 bits.
      53             :  */
      54             : TOMMY_API tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len);
      55             : 
      56             : /**
      57             :  * String hash function with a 32 bits result.
      58             :  * Implementation is based on Robert Jenkins "lookup3" hash 32 bits version,
      59             :  * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle().
      60             :  *
      61             :  * This hash is designed to handle strings with an unknown length. If you
      62             :  * know the string length, the other hash functions are surely faster.
      63             :  *
      64             :  * \param init_val Initialization value.
      65             :  * Using a different initialization value, you can generate a completely different set of hash values.
      66             :  * Use 0 if not relevant.
      67             :  * \param void_key Pointer to the string to hash. It has to be 0 terminated.
      68             :  * \note
      69             :  * This function is endianness independent.
      70             :  * \return The hash value of 32 bits.
      71             :  */
      72             : TOMMY_API tommy_uint32_t tommy_strhash_u32(tommy_uint32_t init_val, const void* void_key);
      73             : 
      74             : /**
      75             :  * Integer reversible hash function for 32 bits.
      76             :  * Implementation of the Robert Jenkins "4-byte Integer Hashing",
      77             :  * from http://burtleburtle.net/bob/hash/integer.html
      78             :  */
      79    20053035 : tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key)
      80             : {
      81    20053035 :         key -= key << 6;
      82    20053035 :         key ^= key >> 17;
      83    20053035 :         key -= key << 9;
      84    20053035 :         key ^= key << 4;
      85    20053035 :         key -= key << 3;
      86    20053035 :         key ^= key << 10;
      87    20053035 :         key ^= key >> 15;
      88             : 
      89    20053035 :         return key;
      90             : }
      91             : 
      92             : /**
      93             :  * Integer reversible hash function for 64 bits.
      94             :  * Implementation of the Thomas Wang "Integer Hash Function",
      95             :  * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
      96             :  */
      97     5567345 : tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
      98             : {
      99     5567345 :         key = ~key + (key << 21);
     100     5567345 :         key = key ^ (key >> 24);
     101     5567345 :         key = key + (key << 3) + (key << 8);
     102     5567345 :         key = key ^ (key >> 14);
     103     5567345 :         key = key + (key << 2) + (key << 4);
     104     5567345 :         key = key ^ (key >> 28);
     105     5567345 :         key = key + (key << 31);
     106             : 
     107     5567345 :         return key;
     108             : }
     109             : 
     110             : #endif