Line data Source code
1 : /* 2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 : * 4 : * Redistribution and use in source and binary forms, with or without 5 : * modification, are permitted provided that the following conditions 6 : * are met: 7 : * 8 : * 1. Redistributions of source code must retain the above copyright 9 : * notice, this list of conditions and the following disclaimer. 10 : * 11 : * 2. Redistributions in binary form must reproduce the above copyright 12 : * notice, this list of conditions and the following disclaimer in the 13 : * documentation and/or other materials provided with the distribution. 14 : * 15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 : * POSSIBILITY OF SUCH DAMAGE. 26 : */ 27 : 28 : /** \file 29 : * Hash functions for the use with ::tommy_hashtable, ::tommy_hashdyn and ::tommy_hashlin. 30 : */ 31 : 32 : #ifndef __TOMMYHASH_H 33 : #define __TOMMYHASH_H 34 : 35 : #include "tommytypes.h" 36 : 37 : /******************************************************************************/ 38 : /* hash */ 39 : 40 : /** 41 : * Hash function with a 32 bits result. 42 : * Implementation of the Robert Jenkins "lookup3" hash 32 bits version, 43 : * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle(). 44 : * 45 : * This hash is designed to provide a good overall performance in all platforms, 46 : * including 32 bits. If you target only 64 bits, you can use faster hashes, 47 : * like SpookyHash or FarmHash. 48 : * 49 : * \param init_val Initialization value. 50 : * Using a different initialization value, you can generate a completely different set of hash values. 51 : * Use 0 if not relevant. 52 : * \param void_key Pointer to the data to hash. 53 : * \param key_len Size of the data to hash. 54 : * \note 55 : * This function is endianness independent. 56 : * \return The hash value of 32 bits. 57 : */ 58 : tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len); 59 : 60 : /** 61 : * Hash function with a 64 bits result. 62 : * Implementation of the Robert Jenkins "lookup3" hash 64 bits versions, 63 : * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle2(). 64 : * 65 : * This hash is designed to provide a good overall performance in all platforms, 66 : * including 32 bits. If you target only 64 bits, you can use faster hashes, 67 : * like SpookyHash or FarmHash. 68 : * 69 : * \param init_val Initialization value. 70 : * Using a different initialization value, you can generate a completely different set of hash values. 71 : * Use 0 if not relevant. 72 : * \param void_key Pointer to the data to hash. 73 : * \param key_len Size of the data to hash. 74 : * \note 75 : * This function is endianness independent. 76 : * \return The hash value of 64 bits. 77 : */ 78 : tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len); 79 : 80 : /** 81 : * String hash function with a 32 bits result. 82 : * Implementation is based on Robert Jenkins "lookup3" hash 32 bits version, 83 : * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle(). 84 : * 85 : * This hash is designed to handle strings with an unknown length. If you 86 : * know the string length, the other hash functions are surely faster. 87 : * 88 : * \param init_val Initialization value. 89 : * Using a different initialization value, you can generate a completely different set of hash values. 90 : * Use 0 if not relevant. 91 : * \param void_key Pointer to the string to hash. It has to be 0 terminated. 92 : * \note 93 : * This function is endianness independent. 94 : * \return The hash value of 32 bits. 95 : */ 96 : tommy_uint32_t tommy_strhash_u32(tommy_uint32_t init_val, const void* void_key); 97 : 98 : /** 99 : * Integer reversible hash function for 32 bits. 100 : * Implementation of the Robert Jenkins "4-byte Integer Hashing", 101 : * from http://burtleburtle.net/bob/hash/integer.html 102 : */ 103 18833871 : tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key) 104 : { 105 18833871 : key -= key << 6; 106 18833871 : key ^= key >> 17; 107 18833871 : key -= key << 9; 108 18833871 : key ^= key << 4; 109 18833871 : key -= key << 3; 110 18833871 : key ^= key << 10; 111 18833871 : key ^= key >> 15; 112 : 113 18833871 : return key; 114 : } 115 : 116 : /** 117 : * Integer reversible hash function for 64 bits. 118 : * Implementation of the Thomas Wang "Integer Hash Function", 119 : * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm 120 : */ 121 5050478 : tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key) 122 : { 123 5050478 : key = ~key + (key << 21); 124 5050478 : key = key ^ (key >> 24); 125 5050478 : key = key + (key << 3) + (key << 8); 126 5050478 : key = key ^ (key >> 14); 127 5050478 : key = key + (key << 2) + (key << 4); 128 5050478 : key = key ^ (key >> 28); 129 5050478 : key = key + (key << 31); 130 : 131 5050478 : return key; 132 : } 133 : 134 : #endif 135 :
