]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
c49d1dd1 | 2 | * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
064af421 | 7 | * |
a14bc59f BP |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
064af421 BP |
15 | */ |
16 | #ifndef HASH_H | |
17 | #define HASH_H 1 | |
18 | ||
8e542118 | 19 | #include <stdbool.h> |
064af421 BP |
20 | #include <stddef.h> |
21 | #include <stdint.h> | |
22 | #include <string.h> | |
cce1d8bd | 23 | #include "util.h" |
064af421 | 24 | |
43d1478b CB |
25 | #ifdef __cplusplus |
26 | extern "C" { | |
27 | #endif | |
28 | ||
d556327b BP |
29 | static inline uint32_t |
30 | hash_rot(uint32_t x, int k) | |
31 | { | |
32 | return (x << k) | (x >> (32 - k)); | |
33 | } | |
064af421 | 34 | |
c49d1dd1 BP |
35 | uint32_t hash_words(const uint32_t data[], size_t n_words, uint32_t basis); |
36 | uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis); | |
37 | ||
38 | static inline uint32_t hash_int(uint32_t x, uint32_t basis); | |
39 | static inline uint32_t hash_2words(uint32_t, uint32_t); | |
40 | uint32_t hash_3words(uint32_t, uint32_t, uint32_t); | |
41 | ||
42 | static inline uint32_t hash_boolean(bool x, uint32_t basis); | |
43 | uint32_t hash_double(double, uint32_t basis); | |
44 | ||
45 | static inline uint32_t hash_pointer(const void *, uint32_t basis); | |
46 | static inline uint32_t hash_string(const char *, uint32_t basis); | |
47 | ||
48 | /* Murmurhash by Austin Appleby, | |
49 | * from http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp. | |
50 | * | |
51 | * The upstream license there says: | |
52 | * | |
53 | * // MurmurHash3 was written by Austin Appleby, and is placed in the public | |
54 | * // domain. The author hereby disclaims copyright to this source code. | |
55 | * | |
56 | * See hash_words() for sample usage. */ | |
57 | ||
58 | static inline uint32_t mhash_add__(uint32_t hash, uint32_t data) | |
d556327b | 59 | { |
c49d1dd1 BP |
60 | data *= 0xcc9e2d51; |
61 | data = hash_rot(data, 15); | |
62 | data *= 0x1b873593; | |
63 | return hash ^ data; | |
d556327b | 64 | } |
064af421 | 65 | |
c49d1dd1 | 66 | static inline uint32_t mhash_add(uint32_t hash, uint32_t data) |
d556327b | 67 | { |
c49d1dd1 BP |
68 | hash = mhash_add__(hash, data); |
69 | hash = hash_rot(hash, 13); | |
70 | return hash * 5 + 0xe6546b64; | |
d556327b | 71 | } |
064af421 | 72 | |
c49d1dd1 BP |
73 | static inline uint32_t mhash_finish(uint32_t hash, size_t n_bytes) |
74 | { | |
75 | hash ^= n_bytes; | |
76 | hash ^= hash >> 16; | |
77 | hash *= 0x85ebca6b; | |
78 | hash ^= hash >> 13; | |
79 | hash *= 0xc2b2ae35; | |
80 | hash ^= hash >> 16; | |
81 | return hash; | |
82 | } | |
064af421 BP |
83 | |
84 | static inline uint32_t hash_string(const char *s, uint32_t basis) | |
85 | { | |
86 | return hash_bytes(s, strlen(s), basis); | |
87 | } | |
88 | ||
064af421 BP |
89 | static inline uint32_t hash_int(uint32_t x, uint32_t basis) |
90 | { | |
c49d1dd1 | 91 | return hash_2words(x, basis); |
064af421 BP |
92 | } |
93 | ||
8e542118 BP |
94 | /* An attempt at a useful 1-bit hash function. Has not been analyzed for |
95 | * quality. */ | |
96 | static inline uint32_t hash_boolean(bool x, uint32_t basis) | |
97 | { | |
43d1478b CB |
98 | const uint32_t P0 = 0xc2b73583; /* This is hash_int(1, 0). */ |
99 | const uint32_t P1 = 0xe90f1258; /* This is hash_int(2, 0). */ | |
d556327b | 100 | return (x ? P0 : P1) ^ hash_rot(basis, 1); |
8e542118 BP |
101 | } |
102 | ||
00644675 BP |
103 | static inline uint32_t hash_pointer(const void *p, uint32_t basis) |
104 | { | |
105 | /* Often pointers are hashed simply by casting to integer type, but that | |
106 | * has pitfalls since the lower bits of a pointer are often all 0 for | |
107 | * alignment reasons. It's hard to guess where the entropy really is, so | |
108 | * we give up here and just use a high-quality hash function. | |
109 | * | |
110 | * The double cast suppresses a warning on 64-bit systems about casting to | |
111 | * an integer to different size. That's OK in this case, since most of the | |
112 | * entropy in the pointer is almost certainly in the lower 32 bits. */ | |
113 | return hash_int((uint32_t) (uintptr_t) p, basis); | |
114 | } | |
115 | ||
c49d1dd1 | 116 | static inline uint32_t hash_2words(uint32_t x, uint32_t y) |
9879b94f | 117 | { |
c49d1dd1 | 118 | return mhash_finish(mhash_add(mhash_add(x, 0), y), 4); |
9879b94f BP |
119 | } |
120 | ||
43d1478b CB |
121 | #ifdef __cplusplus |
122 | } | |
123 | #endif | |
124 | ||
064af421 | 125 | #endif /* hash.h */ |