Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/hash_key.h

ucx/cx/hash_key.h

changeset 1040
473d8cb58a6c
parent 943
9b5948aa5b90
equal deleted inserted replaced
1039:6691e007cef7 1040:473d8cb58a6c
37 #ifndef UCX_HASH_KEY_H 37 #ifndef UCX_HASH_KEY_H
38 #define UCX_HASH_KEY_H 38 #define UCX_HASH_KEY_H
39 39
40 #include "common.h" 40 #include "common.h"
41 #include "string.h" 41 #include "string.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46 42
47 /** Internal structure for a key within a hash map. */ 43 /** Internal structure for a key within a hash map. */
48 struct cx_hash_key_s { 44 struct cx_hash_key_s {
49 /** 45 /**
50 * The key data. 46 * The key data.
76 * @note If @c data is @c NULL, the hash is defined as 1574210520. 72 * @note If @c data is @c NULL, the hash is defined as 1574210520.
77 * 73 *
78 * @param key the key, the hash shall be computed for 74 * @param key the key, the hash shall be computed for
79 * @see cx_hash_key() 75 * @see cx_hash_key()
80 */ 76 */
81 cx_attr_nonnull 77 CX_EXTERN CX_NONNULL
82 CX_EXPORT void cx_hash_murmur(CxHashKey *key); 78 void cx_hash_murmur(CxHashKey *key);
83 79
84 /** 80 /**
85 * Mixes up a 32-bit integer to be used as a hash. 81 * Mixes up a 32-bit integer to be used as a hash.
86 * 82 *
87 * This function produces no collisions and has a good statistical distribution. 83 * This function produces no collisions and has a good statistical distribution.
88 * 84 *
89 * @param x the integer 85 * @param x the integer
90 * @return the hash 86 * @return the hash
91 */ 87 */
92 CX_EXPORT uint32_t cx_hash_u32(uint32_t x); 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 }
93 95
94 /** 96 /**
95 * Mixes up a 64-bit integer to be used as a hash. 97 * Mixes up a 64-bit integer to be used as a hash.
96 * 98 *
97 * This function produces no collisions and has a good statistical distribution. 99 * This function produces no collisions and has a good statistical distribution.
98 * 100 *
99 * @param x the integer 101 * @param x the integer
100 * @return the hash 102 * @return the hash
101 */ 103 */
102 CX_EXPORT uint64_t cx_hash_u64(uint64_t x); 104 CX_INLINE
103 105 uint64_t cx_hash_u64(uint64_t x){
104 /** 106 x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
105 * Computes a hash key from a 32-bit integer. 107 x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
106 * 108 x = x ^ (x >> 31);
107 * @param x the integer 109 return x;
108 * @return the hash key 110 }
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 111
157 /** 112 /**
158 * Computes a hash key for an arbitrary object. 113 * Computes a hash key for an arbitrary object.
159 * 114 *
160 * The computation uses the in-memory representation that might not be 115 * The computation uses the in-memory representation that might not be
163 * 118 *
164 * @param obj a pointer to an arbitrary object 119 * @param obj a pointer to an arbitrary object
165 * @param len the length of the object in memory 120 * @param len the length of the object in memory
166 * @return the hash key 121 * @return the hash key
167 */ 122 */
168 cx_attr_nodiscard 123 CX_EXTERN CX_NODISCARD CX_ACCESS_R(1, 2)
169 cx_attr_access_r(1, 2) 124 CxHashKey cx_hash_key(const void *obj, size_t len);
170 CX_EXPORT 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 }
171 196
172 /** 197 /**
173 * Computes a hash key from a UCX string. 198 * Computes a hash key from a UCX string.
174 * 199 *
175 * @param str the string 200 * @param str the string
176 * @return the hash key 201 * @return the hash key
177 */ 202 */
178 cx_attr_nodiscard 203 CX_NODISCARD CX_INLINE
179 CX_EXPORT CxHashKey cx_hash_key_cxstr(cxstring str); 204 CxHashKey cx_hash_key_cxstr(cxstring str) {
205 return cx_hash_key((void*)str.ptr, str.length);
206 }
180 207
181 /** 208 /**
182 * Computes a hash key from a UCX string. 209 * Computes a hash key from a UCX string.
183 * 210 *
184 * @param str the string 211 * @param str the string
185 * @return the hash key 212 * @return the hash key
186 */ 213 */
187 cx_attr_nodiscard 214 CX_NODISCARD CX_INLINE
188 CX_EXPORT CxHashKey cx_hash_key_mutstr(cxmutstr str); 215 CxHashKey cx_hash_key_mutstr(cxmutstr str) {
216 return cx_hash_key((void*)str.ptr, str.length);
217 }
189 218
190 /** 219 /**
191 * The identity function for the CX_HASH_KEY() macro. 220 * The identity function for the CX_HASH_KEY() macro.
192 * You should never need to use this manually. 221 * You should never need to use this manually.
193 * 222 *
194 * @param key the key 223 * @param key the key
195 * @return a copy of the key 224 * @return a copy of the key (not the data)
196 */ 225 */
197 cx_attr_nodiscard 226 CX_NODISCARD CX_INLINE
198 CX_INLINE CxHashKey cx_hash_key_identity(CxHashKey key) { 227 CxHashKey cx_hash_key_identity(CxHashKey key) {
199 return key; 228 return key;
200 } 229 }
201 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
202 #ifndef __cplusplus 243 #ifndef __cplusplus
203 /** 244 /**
204 * Creates a hash key from any of the supported types with implicit length. 245 * Creates a hash key from any of the supported types with implicit length.
205 * 246 *
206 * Does nothing when passing a CxHashkey. 247 * Does nothing when passing a CxHashKey and dereferences CxHashKey pointers.
207 * 248 *
208 * Supported types are UCX strings, zero-terminated C strings, 249 * Supported types are UCX strings, zero-terminated C strings,
209 * and 32-bit or 64-bit unsigned integers. 250 * and 32-bit or 64-bit unsigned integers.
210 * 251 *
211 * @param key the key data 252 * @param key the key data
212 * @returns the @c CxHashKey 253 * @returns the @c CxHashKey
213 */ 254 */
214 #define CX_HASH_KEY(key) _Generic((key), \ 255 #define CX_HASH_KEY(key) _Generic((key), \
256 CxHashKey*: cx_hash_key_deref, \
257 const CxHashKey*: cx_hash_key_deref, \
215 CxHashKey: cx_hash_key_identity, \ 258 CxHashKey: cx_hash_key_identity, \
216 cxstring: cx_hash_key_cxstr, \ 259 cxstring: cx_hash_key_cxstr, \
217 cxmutstr: cx_hash_key_mutstr, \ 260 cxmutstr: cx_hash_key_mutstr, \
218 char*: cx_hash_key_str, \ 261 char*: cx_hash_key_str, \
219 const char*: cx_hash_key_str, \ 262 const char*: cx_hash_key_str, \
231 * 274 *
232 * @param left (@c CxHashKey*) the first key 275 * @param left (@c CxHashKey*) the first key
233 * @param right (@c CxHashKey*) the second key 276 * @param right (@c CxHashKey*) the second key
234 * @return zero when the keys equal, non-zero when they differ 277 * @return zero when the keys equal, non-zero when they differ
235 */ 278 */
236 cx_attr_nodiscard cx_attr_nonnull 279 CX_EXTERN CX_NODISCARD CX_NONNULL
237 CX_EXPORT int cx_hash_key_cmp(const void *left, const void *right); 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);
238 290
239 #ifdef __cplusplus 291 #ifdef __cplusplus
240 } // extern "C"
241
242 // ---------------------------------------------------------- 292 // ----------------------------------------------------------
243 // Overloads of CX_HASH_KEY (the C++ version of a _Generic) 293 // Overloads of CX_HASH_KEY (the C++ version of a _Generic)
244 // ---------------------------------------------------------- 294 // ----------------------------------------------------------
245 295
246 CX_CPPDECL CxHashKey CX_HASH_KEY(CxHashKey key) { 296 CX_CPPDECL CxHashKey CX_HASH_KEY(CxHashKey key) {
247 return key; 297 return key;
248 } 298 }
249 299
300 CX_CPPDECL CxHashKey CX_HASH_KEY(const CxHashKey *key) {
301 return *key;
302 }
303
250 CX_CPPDECL CxHashKey CX_HASH_KEY(cxstring str) { 304 CX_CPPDECL CxHashKey CX_HASH_KEY(cxstring str) {
251 return cx_hash_key_cxstr(str); 305 return cx_hash_key_cxstr(str);
252 } 306 }
253 307
254 CX_CPPDECL CxHashKey CX_HASH_KEY(cxmutstr str) { 308 CX_CPPDECL CxHashKey CX_HASH_KEY(cxmutstr str) {

Mercurial Repository: toolkit

mercurial