1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * @file hash_key.h
30 * @brief Interface for map implementations.
31 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36
37 #ifndef UCX_HASH_KEY_H
38 #define UCX_HASH_KEY_H
39
40 #include "common.h"
41 #include "string.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46
47 /** Internal structure for a key within a hash map. */
48 struct cx_hash_key_s {
49 /**
50 * The key data.
51 * May be NULL when the hash is collision-free.
52 */
53 const void *data;
54 /**
55 * The key data length.
56 */
57 size_t len;
58 /** The hash value of the key data. */
59 uint64_t hash;
60 };
61
62 /**
63 * Type for a hash key.
64 */
65 typedef struct cx_hash_key_s CxHashKey;
66
67 /**
68 * Computes a murmur2 32-bit hash.
69 *
70 * You need to initialize @c data and @c len in the key struct.
71 * The hash is then directly written to that struct.
72 *
73 * Usually you should not need this function.
74 * Use cx_hash_key(), instead.
75 *
76 * @note If @c data is @c NULL, the hash is defined as 1574210520.
77 *
78 * @param key the key, the hash shall be computed for
79 * @see cx_hash_key()
80 */
81 cx_attr_nonnull
82 CX_EXPORT void cx_hash_murmur(CxHashKey *key);
83
84 /**
85 * Mixes up a 32-bit integer to be used as a hash.
86 *
87 * This function produces no collisions and has a good statistical distribution.
88 *
89 * @param x the integer
90 * @return the hash
91 */
92 CX_EXPORT uint32_t cx_hash_u32(uint32_t x);
93
94 /**
95 * Mixes up a 64-bit integer to be used as a hash.
96 *
97 * This function produces no collisions and has a good statistical distribution.
98 *
99 * @param x the integer
100 * @return the hash
101 */
102 CX_EXPORT uint64_t cx_hash_u64(uint64_t x);
103
104 /**
105 * Computes a hash key from a 32-bit integer.
106 *
107 * @param x the integer
108 * @return the hash key
109 */
110 cx_attr_nodiscard
111 CX_EXPORT CxHashKey cx_hash_key_u32(uint32_t x);
112
113 /**
114 * Computes a hash key from a 64-bit integer.
115 *
116 * @param x the integer
117 * @return the hash key
118 */
119 cx_attr_nodiscard
120 CX_EXPORT CxHashKey cx_hash_key_u64(uint64_t x);
121
122 /**
123 * Computes a hash key from a string.
124 *
125 * The string needs to be zero-terminated.
126 *
127 * @param str the string
128 * @return the hash key
129 */
130 cx_attr_nodiscard cx_attr_cstr_arg(1)
131 CX_EXPORT CxHashKey cx_hash_key_str(const char *str);
132
133 /**
134 * Computes a hash key from a string.
135 *
136 * Use this function when the string is represented
137 * as an unsigned char array.
138 *
139 * The string needs to be zero-terminated.
140 *
141 * @param str the string
142 * @return the hash key
143 */
144 cx_attr_nodiscard cx_attr_cstr_arg(1)
145 CX_EXPORT CxHashKey cx_hash_key_ustr(const unsigned char *str);
146
147 /**
148 * Computes a hash key from a byte array.
149 *
150 * @param bytes the array
151 * @param len the length
152 * @return the hash key
153 */
154 cx_attr_nodiscard cx_attr_access_r(1, 2)
155 CX_EXPORT CxHashKey cx_hash_key_bytes(const unsigned char *bytes, size_t len);
156
157 /**
158 * Computes a hash key for an arbitrary object.
159 *
160 * The computation uses the in-memory representation that might not be
161 * the same on different platforms. Therefore, this hash should not be
162 * used for data exchange with different machines.
163 *
164 * @param obj a pointer to an arbitrary object
165 * @param len the length of the object in memory
166 * @return the hash key
167 */
168 cx_attr_nodiscard
169 cx_attr_access_r(1, 2)
170 CX_EXPORT CxHashKey cx_hash_key(const void *obj, size_t len);
171
172 /**
173 * Computes a hash key from a UCX string.
174 *
175 * @param str the string
176 * @return the hash key
177 */
178 cx_attr_nodiscard
179 CX_EXPORT CxHashKey cx_hash_key_cxstr(cxstring str);
180
181 /**
182 * Computes a hash key from a UCX string.
183 *
184 * @param str the string
185 * @return the hash key
186 */
187 cx_attr_nodiscard
188 CX_EXPORT CxHashKey cx_hash_key_mutstr(cxmutstr str);
189
190 /**
191 * The identity function for the CX_HASH_KEY() macro.
192 * You should never need to use this manually.
193 *
194 * @param key the key
195 * @return a copy of the key
196 */
197 cx_attr_nodiscard
198 CX_INLINE CxHashKey cx_hash_key_identity(CxHashKey key) {
199 return key;
200 }
201
202 #ifndef __cplusplus
203 /**
204 * Creates a hash key from any of the supported types with implicit length.
205 *
206 * Does nothing when passing a CxHashkey.
207 *
208 * Supported types are UCX strings, zero-terminated C strings,
209 * and 32-bit or 64-bit unsigned integers.
210 *
211 * @param key the key data
212 * @returns the @c CxHashKey
213 */
214 #define CX_HASH_KEY(key) _Generic((key), \
215 CxHashKey: cx_hash_key_identity, \
216 cxstring: cx_hash_key_cxstr, \
217 cxmutstr: cx_hash_key_mutstr, \
218 char*: cx_hash_key_str, \
219 const char*: cx_hash_key_str, \
220 unsigned char*: cx_hash_key_ustr, \
221 const unsigned char*: cx_hash_key_ustr, \
222 uint32_t: cx_hash_key_u32, \
223 uint64_t: cx_hash_key_u64) \
224 (key)
225 #endif // __cplusplus
226
227 /**
228 * Compare function for hash keys.
229 *
230 * The pointers are untyped to be compatible with the cx_compare_func signature.
231 *
232 * @param left (@c CxHashKey*) the first key
233 * @param right (@c CxHashKey*) the second key
234 * @return zero when the keys equal, non-zero when they differ
235 */
236 cx_attr_nodiscard cx_attr_nonnull
237 CX_EXPORT int cx_hash_key_cmp(const void *left, const void *right);
238
239 #ifdef __cplusplus
240 } // extern "C"
241
242 // ----------------------------------------------------------
243 // Overloads of CX_HASH_KEY (the C++ version of a _Generic)
244 // ----------------------------------------------------------
245
246 CX_CPPDECL CxHashKey CX_HASH_KEY(CxHashKey key) {
247 return key;
248 }
249
250 CX_CPPDECL CxHashKey CX_HASH_KEY(cxstring str) {
251 return cx_hash_key_cxstr(str);
252 }
253
254 CX_CPPDECL CxHashKey CX_HASH_KEY(cxmutstr str) {
255 return cx_hash_key_mutstr(str);
256 }
257
258 CX_CPPDECL CxHashKey CX_HASH_KEY(const char *str) {
259 return cx_hash_key_str(str);
260 }
261
262 CX_CPPDECL CxHashKey CX_HASH_KEY(const unsigned char *str) {
263 return cx_hash_key_ustr(str);
264 }
265
266 CX_CPPDECL CxHashKey CX_HASH_KEY(uint32_t key) {
267 return cx_hash_key_u32(key);
268 }
269
270 CX_CPPDECL CxHashKey CX_HASH_KEY(uint64_t key) {
271 return cx_hash_key_u64(key);
272 }
273 #endif
274
275 #endif // UCX_HASH_KEY_H
276