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 * \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 at 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 * \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 at the data to hash.
68 * \param key_len Size of the data to hash.
69 * \note
70 * This function is endianess independent.
71 * \return The hash value of 64 bits.
72 */
73 tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len);
74
75 /**
76 * Integer hash of 32 bits.
77 * Implementation of the Robert Jenkins "4-byte Integer Hashing",
78 * from http://burtleburtle.net/bob/hash/integer.html
79 */
tommy_inthash_u32(tommy_uint32_t key)80 tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key)
81 {
82 key -= key << 6;
83 key ^= key >> 17;
84 key -= key << 9;
85 key ^= key << 4;
86 key -= key << 3;
87 key ^= key << 10;
88 key ^= key >> 15;
89
90 return key;
91 }
92
93 /**
94 * Integer hash of 64 bits.
95 * Implementation of the Thomas Wang "Integer Hash Function",
96 * from http://www.cris.com/~Ttwang/tech/inthash.htm
97 */
tommy_inthash_u64(tommy_uint64_t key)98 tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
99 {
100 key = ~key + (key << 21);
101 key = key ^ (key >> 24);
102 key = key + (key << 3) + (key << 8);
103 key = key ^ (key >> 14);
104 key = key + (key << 2) + (key << 4);
105 key = key ^ (key >> 28);
106 key = key + (key << 31);
107
108 return key;
109 }
110
111 #endif
112
113