2 * Copyright (c) 2012 Adam Hraska
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - 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 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 /** @addtogroup genericadt
38 #include <libarch/types.h>
40 /** Produces a uniform hash affecting all output bits from the skewed input. */
41 static inline uint32_t hash_mix32(uint32_t hash
)
44 * Thomas Wang's modification of Bob Jenkin's hash mixing function:
45 * http://www.concentric.net/~Ttwang/tech/inthash.htm
48 hash
= ~hash
+ (hash
<< 15);
49 hash
= hash
^ (hash
>> 12);
50 hash
= hash
+ (hash
<< 2);
51 hash
= hash
^ (hash
>> 4);
53 hash
= hash
^ (hash
>> 16);
57 /** Produces a uniform hash affecting all output bits from the skewed input. */
58 static inline uint64_t hash_mix64(uint64_t hash
)
61 * Thomas Wang's public domain 64-bit hash mixing function:
62 * http://www.concentric.net/~Ttwang/tech/inthash.htm
64 hash
= (hash
^ 61) ^ (hash
>> 16);
65 hash
= hash
+ (hash
<< 3);
66 hash
= hash
^ (hash
>> 4);
67 hash
= hash
* 0x27d4eb2d;
68 hash
= hash
^ (hash
>> 15);
70 * Lower order bits are mixed more thoroughly. Swap them with
71 * the higher order bits and make the resulting higher order bits
74 return (hash
<< 32) | (hash
>> 32);
77 /** Produces a uniform hash affecting all output bits from the skewed input. */
78 static inline size_t hash_mix(size_t hash
)
81 return hash_mix32(hash
);
82 #elif defined(__64_BITS__)
83 return hash_mix64(hash
);
85 #error Unknown size_t size - cannot select proper hash mix function.
89 /** Use to create a hash from multiple values.
94 * bool car_convertible;
97 * hash = hash_combine(hash, car_id);
98 * hash = hash_combine(hash, car_convertible);
99 * // Now use hash as a hash of both car_id and car_convertible.
102 static inline size_t hash_combine(size_t seed
, size_t hash
)
105 * todo: use Bob Jenkin's proper mixing hash pass:
106 * http://burtleburtle.net/bob/c/lookup3.c
108 seed
^= hash
+ 0x9e3779b9
109 + ((seed
<< 5) | (seed
>> (sizeof(size_t) * 8 - 5)));