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 type used in hashtables.
42 : */
43 : typedef tommy_key_t tommy_hash_t;
44 :
45 : /**
46 : * Hash function with a 32 bits result.
47 : * Implementation of the Robert Jenkins "lookup3" hash 32 bits version,
48 : * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle().
49 : *
50 : * This hash is designed to provide a good overall performance in all platforms,
51 : * including 32 bits. If you target only 64 bits, you can use faster hashes,
52 : * like SpookyHash or FarmHash.
53 : *
54 : * \param init_val Initialization value.
55 : * Using a different initialization value, you can generate a completely different set of hash values.
56 : * Use 0 if not relevant.
57 : * \param void_key Pointer to the data to hash.
58 : * \param key_len Size of the data to hash.
59 : * \note
60 : * This function is endianess independent.
61 : * \return The hash value of 32 bits.
62 : */
63 : tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len);
64 :
65 : /**
66 : * Hash function with a 64 bits result.
67 : * Implementation of the Robert Jenkins "lookup3" hash 64 bits versions,
68 : * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle2().
69 : *
70 : * This hash is designed to provide a good overall performance in all platforms,
71 : * including 32 bits. If you target only 64 bits, you can use faster hashes,
72 : * like SpookyHash or FarmHash.
73 : *
74 : * \param init_val Initialization value.
75 : * Using a different initialization value, you can generate a completely different set of hash values.
76 : * Use 0 if not relevant.
77 : * \param void_key Pointer to the data to hash.
78 : * \param key_len Size of the data to hash.
79 : * \note
80 : * This function is endianess independent.
81 : * \return The hash value of 64 bits.
82 : */
83 : tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len);
84 :
85 : /**
86 : * String hash function with a 32 bits result.
87 : * Implementation is based on the the Robert Jenkins "lookup3" hash 32 bits version,
88 : * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle().
89 : *
90 : * This hash is designed to handle strings with an unknown length. If you
91 : * know the string length, the other hash functions are surely faster.
92 : *
93 : * \param init_val Initialization value.
94 : * Using a different initialization value, you can generate a completely different set of hash values.
95 : * Use 0 if not relevant.
96 : * \param void_key Pointer to the string to hash. It has to be 0 terminated.
97 : * \note
98 : * This function is endianess independent.
99 : * \return The hash value of 32 bits.
100 : */
101 : tommy_uint32_t tommy_strhash_u32(tommy_uint64_t init_val, const void* void_key);
102 :
103 : /**
104 : * Integer reversible hash function for 32 bits.
105 : * Implementation of the Robert Jenkins "4-byte Integer Hashing",
106 : * from http://burtleburtle.net/bob/hash/integer.html
107 : */
108 18827544 : tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key)
109 : {
110 18827544 : key -= key << 6;
111 18827544 : key ^= key >> 17;
112 18827544 : key -= key << 9;
113 18827544 : key ^= key << 4;
114 18827544 : key -= key << 3;
115 18827544 : key ^= key << 10;
116 18827544 : key ^= key >> 15;
117 :
118 18827544 : return key;
119 : }
120 :
121 : /**
122 : * Integer reversible hash function for 64 bits.
123 : * Implementation of the Thomas Wang "Integer Hash Function",
124 : * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
125 : */
126 5055426 : tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
127 : {
128 5055426 : key = ~key + (key << 21);
129 5055426 : key = key ^ (key >> 24);
130 5055426 : key = key + (key << 3) + (key << 8);
131 5055426 : key = key ^ (key >> 14);
132 5055426 : key = key + (key << 2) + (key << 4);
133 5055426 : key = key ^ (key >> 28);
134 5055426 : key = key + (key << 31);
135 :
136 5055426 : return key;
137 : }
138 :
139 : #endif
140 :
|
