GCC Code Coverage Report

Directory: ./
File: cx/hash_key.h
Date: 2025-12-31 16:19:05
Exec Total Coverage
Lines: 3 3 100.0%
Functions: 0 0 -%
Branches: 0 0 -%
Line Branch Exec Source
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 /** Internal structure for a key within a hash map. */
44 struct cx_hash_key_s {
45 /**
46 * The key data.
47 * May be NULL when the hash is collision-free.
48 */
49 const void *data;
50 /**
51 * The key data length.
52 */
53 size_t len;
54 /** The hash value of the key data. */
55 uint64_t hash;
56 };
57
58 /**
59 * Type for a hash key.
60 */
61 typedef struct cx_hash_key_s CxHashKey;
62
63 /**
64 * Computes a murmur2 32-bit hash.
65 *
66 * You need to initialize @c data and @c len in the key struct.
67 * The hash is then directly written to that struct.
68 *
69 * Usually you should not need this function.
70 * Use cx_hash_key(), instead.
71 *
72 * @note If @c data is @c NULL, the hash is defined as 1574210520.
73 *
74 * @param key the key, the hash shall be computed for
75 * @see cx_hash_key()
76 */
77 CX_EXTERN CX_NONNULL
78 void cx_hash_murmur(CxHashKey *key);
79
80 /**
81 * Mixes up a 32-bit integer to be used as a hash.
82 *
83 * This function produces no collisions and has a good statistical distribution.
84 *
85 * @param x the integer
86 * @return the hash
87 */
88 CX_INLINE
89 uint32_t cx_hash_u32(uint32_t x) {
90 x = ((x >> 16) ^ x) * 0x45d9f3bu;
91 x = ((x >> 16) ^ x) * 0x45d9f3bu;
92 x = (x >> 16) ^ x;
93 return x;
94 }
95
96 /**
97 * Mixes up a 64-bit integer to be used as a hash.
98 *
99 * This function produces no collisions and has a good statistical distribution.
100 *
101 * @param x the integer
102 * @return the hash
103 */
104 CX_INLINE
105 uint64_t cx_hash_u64(uint64_t x){
106 x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
107 x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
108 x = x ^ (x >> 31);
109 return x;
110 }
111
112 /**
113 * Computes a hash key for an arbitrary object.
114 *
115 * The computation uses the in-memory representation that might not be
116 * the same on different platforms. Therefore, this hash should not be
117 * used for data exchange with different machines.
118 *
119 * @param obj a pointer to an arbitrary object
120 * @param len the length of the object in memory
121 * @return the hash key
122 */
123 CX_EXTERN CX_NODISCARD CX_ACCESS_R(1, 2)
124 CxHashKey cx_hash_key(const void *obj, size_t len);
125
126 /**
127 * Computes a hash key from a 32-bit integer.
128 *
129 * @param x the integer
130 * @return the hash key
131 */
132 CX_NODISCARD CX_INLINE
133 CxHashKey cx_hash_key_u32(uint32_t x) {
134 CxHashKey key;
135 key.data = NULL;
136 key.len = 0;
137 key.hash = cx_hash_u32(x);
138 return key;
139 }
140
141 /**
142 * Computes a hash key from a 64-bit integer.
143 *
144 * @param x the integer
145 * @return the hash key
146 */
147 CX_NODISCARD CX_INLINE
148 CxHashKey cx_hash_key_u64(uint64_t x) {
149 CxHashKey key;
150 key.data = NULL;
151 key.len = 0;
152 key.hash = cx_hash_u64(x);
153 return key;
154 }
155
156 /**
157 * Computes a hash key from a string.
158 *
159 * The string needs to be zero-terminated.
160 *
161 * @param str the string
162 * @return the hash key
163 */
164 CX_NODISCARD CX_CSTR_ARG(1) CX_INLINE
165 CxHashKey cx_hash_key_str(const char *str) {
166 return cx_hash_key((const void*)str, str == NULL ? 0 : strlen(str));
167 }
168
169 /**
170 * Computes a hash key from a string.
171 *
172 * Use this function when the string is represented
173 * as an unsigned char array.
174 *
175 * The string needs to be zero-terminated.
176 *
177 * @param str the string
178 * @return the hash key
179 */
180 CX_NODISCARD CX_CSTR_ARG(1) CX_INLINE
181 CxHashKey cx_hash_key_ustr(const unsigned char *str) {
182 return cx_hash_key((const void*)str, str == NULL ? 0 : strlen((const char*)str));
183 }
184
185 /**
186 * Computes a hash key from a byte array.
187 *
188 * @param bytes the array
189 * @param len the length
190 * @return the hash key
191 */
192 CX_NODISCARD CX_ACCESS_R(1, 2) CX_INLINE
193 CxHashKey cx_hash_key_bytes(const unsigned char *bytes, size_t len) {
194 return cx_hash_key((const void*)bytes, len);
195 }
196
197 /**
198 * Computes a hash key from a UCX string.
199 *
200 * @param str the string
201 * @return the hash key
202 */
203 CX_NODISCARD CX_INLINE
204 CxHashKey cx_hash_key_cxstr(cxstring str) {
205 649 return cx_hash_key((void*)str.ptr, str.length);
206 }
207
208 /**
209 * Computes a hash key from a UCX string.
210 *
211 * @param str the string
212 * @return the hash key
213 */
214 CX_NODISCARD CX_INLINE
215 CxHashKey cx_hash_key_mutstr(cxmutstr str) {
216 130 return cx_hash_key((void*)str.ptr, str.length);
217 }
218
219 /**
220 * The identity function for the CX_HASH_KEY() macro.
221 * You should never need to use this manually.
222 *
223 * @param key the key
224 * @return a copy of the key (not the data)
225 */
226 CX_NODISCARD CX_INLINE
227 CxHashKey cx_hash_key_identity(CxHashKey key) {
228 533 return key;
229 }
230
231 /**
232 * The dereference function for the CX_HASH_KEY() macro.
233 * You should never need to use this manually.
234 *
235 * @param key a pointer to a key
236 * @return a copy of the key (not the data)
237 */
238 CX_NODISCARD CX_INLINE
239 CxHashKey cx_hash_key_deref(const CxHashKey *key) {
240 return *key;
241 }
242
243 #ifndef __cplusplus
244 /**
245 * Creates a hash key from any of the supported types with implicit length.
246 *
247 * Does nothing when passing a CxHashKey and dereferences CxHashKey pointers.
248 *
249 * Supported types are UCX strings, zero-terminated C strings,
250 * and 32-bit or 64-bit unsigned integers.
251 *
252 * @param key the key data
253 * @returns the @c CxHashKey
254 */
255 #define CX_HASH_KEY(key) _Generic((key), \
256 CxHashKey*: cx_hash_key_deref, \
257 const CxHashKey*: cx_hash_key_deref, \
258 CxHashKey: cx_hash_key_identity, \
259 cxstring: cx_hash_key_cxstr, \
260 cxmutstr: cx_hash_key_mutstr, \
261 char*: cx_hash_key_str, \
262 const char*: cx_hash_key_str, \
263 unsigned char*: cx_hash_key_ustr, \
264 const unsigned char*: cx_hash_key_ustr, \
265 uint32_t: cx_hash_key_u32, \
266 uint64_t: cx_hash_key_u64) \
267 (key)
268 #endif // __cplusplus
269
270 /**
271 * Compare function for hash keys.
272 *
273 * The pointers are untyped to be compatible with the cx_compare_func signature.
274 *
275 * @param left (@c CxHashKey*) the first key
276 * @param right (@c CxHashKey*) the second key
277 * @return zero when the keys equal, non-zero when they differ
278 */
279 CX_EXTERN CX_NODISCARD CX_NONNULL
280 int cx_hash_key_cmp(const void *left, const void *right);
281
282 /**
283 * Interprets the key data as a string and returns it.
284 *
285 * @param key the key
286 * @return the key data as a string
287 */
288 CX_EXTERN
289 cxstring cx_hash_key_as_string(const CxHashKey *key);
290
291 #ifdef __cplusplus
292 // ----------------------------------------------------------
293 // Overloads of CX_HASH_KEY (the C++ version of a _Generic)
294 // ----------------------------------------------------------
295
296 CX_CPPDECL CxHashKey CX_HASH_KEY(CxHashKey key) {
297 return key;
298 }
299
300 CX_CPPDECL CxHashKey CX_HASH_KEY(const CxHashKey *key) {
301 return *key;
302 }
303
304 CX_CPPDECL CxHashKey CX_HASH_KEY(cxstring str) {
305 return cx_hash_key_cxstr(str);
306 }
307
308 CX_CPPDECL CxHashKey CX_HASH_KEY(cxmutstr str) {
309 return cx_hash_key_mutstr(str);
310 }
311
312 CX_CPPDECL CxHashKey CX_HASH_KEY(const char *str) {
313 return cx_hash_key_str(str);
314 }
315
316 CX_CPPDECL CxHashKey CX_HASH_KEY(const unsigned char *str) {
317 return cx_hash_key_ustr(str);
318 }
319
320 CX_CPPDECL CxHashKey CX_HASH_KEY(uint32_t key) {
321 return cx_hash_key_u32(key);
322 }
323
324 CX_CPPDECL CxHashKey CX_HASH_KEY(uint64_t key) {
325 return cx_hash_key_u64(key);
326 }
327 #endif
328
329 #endif // UCX_HASH_KEY_H
330