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 endianess 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 endianess 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 the the 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 endianess independent.
94 : * \return The hash value of 32 bits.
95 : */
96 : tommy_uint32_t tommy_strhash_u32(tommy_uint64_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 250065 : tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key)
104 : {
105 250065 : key -= key << 6;
106 250065 : key ^= key >> 17;
107 250065 : key -= key << 9;
108 250065 : key ^= key << 4;
109 250065 : key -= key << 3;
110 250065 : key ^= key << 10;
111 250065 : key ^= key >> 15;
112 :
113 250065 : 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 97 : tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
122 : {
123 97 : key = ~key + (key << 21);
124 97 : key = key ^ (key >> 24);
125 97 : key = key + (key << 3) + (key << 8);
126 97 : key = key ^ (key >> 14);
127 97 : key = key + (key << 2) + (key << 4);
128 97 : key = key ^ (key >> 28);
129 97 : key = key + (key << 31);
130 :
131 97 : return key;
132 : }
133 :
134 : #endif
135 :
|
