map.h - UNIXwork Code

1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3 * 4 * Copyright 2016 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 /** 30 * @file map.h 31 * 32 * Hash map implementation. 33 * 34 * This implementation uses murmur hash 2 and separate chaining with linked 35 * lists. 36 * 37 * @author Mike Becker 38 * @author Olaf Wintermann 39 */ 40 41 #ifndef UCX_MAP_H 42 #define UCX_MAP_H 43 44 #include "ucx.h" 45 #include "string.h" 46 #include "allocator.h" 47 #include <stdio.h> 48 49 #ifdef __cplusplus 50 extern "C" { 51 #endif 52 53 /** 54 * Loop statement for UCX maps. 55 * 56 * The <code>key</code> variable is implicitly defined, but the 57 * <code>value</code> variable must be already declared as type information 58 * cannot be inferred. 59 * 60 * @param key the variable name for the key 61 * @param value the variable name for the value 62 * @param iter a UcxMapIterator 63 * @see ucx_map_iterator() 64 */ 65 #define UCX_MAP_FOREACH(key,value,iter) \ 66 for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);) 67 68 /** Type for the UCX map. @see UcxMap */ 69 typedef struct UcxMap UcxMap; 70 71 /** Type for a key of a UcxMap. @see UcxKey */ 72 typedef struct UcxKey UcxKey; 73 74 /** Type for an element of a UcxMap. @see UcxMapElement */ 75 typedef struct UcxMapElement UcxMapElement; 76 77 /** Type for an iterator over a UcxMap. @see UcxMapIterator */ 78 typedef struct UcxMapIterator UcxMapIterator; 79 80 /** Structure for the UCX map. */ 81 struct UcxMap { 82 /** An allocator that is used for the map elements. */ 83 UcxAllocator *allocator; 84 /** The array of map element lists. */ 85 UcxMapElement **map; 86 /** The size of the map is the length of the element list array. */ 87 size_t size; 88 /** The count of elements currently stored in this map. */ 89 size_t count; 90 }; 91 92 /** Structure for a key of a UcxMap. */ 93 struct UcxKey { 94 /** The key data. */ 95 void *data; 96 /** The length of the key data. */ 97 size_t len; 98 /** The hash value of the key data. */ 99 int hash; 100 }; 101 102 /** Structure for an element of a UcxMap. */ 103 struct UcxMapElement { 104 /** The value data. */ 105 void *data; 106 107 /** A pointer to the next element in the current list. */ 108 UcxMapElement *next; 109 110 /** The corresponding key. */ 111 UcxKey key; 112 }; 113 114 /** Structure for an iterator over a UcxMap. */ 115 struct UcxMapIterator { 116 /** The map to iterate over. */ 117 UcxMap *map; 118 119 /** The current map element. */ 120 UcxMapElement *cur; 121 122 /** 123 * The current index of the element list array. 124 * Attention: this is NOT the element index! Do NOT 125 * manually iterate over the map by increasing this index. Use 126 * ucx_map_iter_next(). 127 * @see UcxMap.map*/ 128 size_t index; 129 }; 130 131 /** 132 * Creates a new hash map with the specified size. 133 * @param size the size of the hash map 134 * @return a pointer to the new hash map 135 */ 136 UcxMap *ucx_map_new(size_t size); 137 138 /** 139 * Creates a new hash map with the specified size using a UcxAllocator. 140 * @param allocator the allocator to use 141 * @param size the size of the hash map 142 * @return a pointer to the new hash map 143 */ 144 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size); 145 146 /** 147 * Frees a hash map. 148 * 149 * Note: the contents are not freed, use ucx_map_free_content() 150 * before calling this function to achieve that. 151 * 152 * @param map the map to be freed 153 * @see ucx_map_free_content() 154 */ 155 void ucx_map_free(UcxMap *map); 156 157 /** 158 * Frees the contents of a hash map. 159 * 160 * This is a convenience function that iterates over the map and passes all 161 * values to the specified destructor function (e.g. stdlib free()). 162 * 163 * You must ensure, that it is valid to pass each value in the map to the same 164 * destructor function. 165 * 166 * You should free or clear the map afterwards, as the contents will be invalid. 167 * 168 * @param map for which the contents shall be freed 169 * @param destr pointer to the destructor function 170 * @see ucx_map_free() 171 * @see ucx_map_clear() 172 */ 173 void ucx_map_free_content(UcxMap *map, ucx_destructor destr); 174 175 /** 176 * Clears a hash map. 177 * 178 * Note: the contents are not freed, use ucx_map_free_content() 179 * before calling this function to achieve that. 180 * 181 * @param map the map to be cleared 182 * @see ucx_map_free_content() 183 */ 184 void ucx_map_clear(UcxMap *map); 185 186 187 /** 188 * Copies contents from a map to another map using a copy function. 189 * 190 * Note: The destination map does not need to be empty. However, if it 191 * contains data with keys that are also present in the source map, the contents 192 * are overwritten. 193 * 194 * @param from the source map 195 * @param to the destination map 196 * @param fnc the copy function or <code>NULL</code> if the pointer address 197 * shall be copied 198 * @param data additional data for the copy function 199 * @return 0 on success or a non-zero value on memory allocation errors 200 */ 201 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, 202 copy_func fnc, void *data); 203 204 /** 205 * Clones the map and rehashes if necessary. 206 * 207 * Note: In contrast to ucx_map_rehash() the load factor is irrelevant. 208 * This function always ensures a new UcxMap.size of at least 209 * 2.5*UcxMap.count. 210 * 211 * @param map the map to clone 212 * @param fnc the copy function to use or <code>NULL</code> if the new and 213 * the old map shall share the data pointers 214 * @param data additional data for the copy function 215 * @return the cloned map 216 * @see ucx_map_copy() 217 */ 218 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data); 219 220 /** 221 * Increases size of the hash map, if necessary. 222 * 223 * The load value is 0.75*UcxMap.size. If the element count exceeds the load 224 * value, the map needs to be rehashed. Otherwise no action is performed and 225 * this function simply returns 0. 226 * 227 * The rehashing process ensures, that the UcxMap.size is at least 228 * 2.5*UcxMap.count. So there is enough room for additional elements without 229 * the need of another soon rehashing. 230 * 231 * You can use this function to dramatically increase access performance. 232 * 233 * @param map the map to rehash 234 * @return 1, if a memory allocation error occurred, 0 otherwise 235 */ 236 int ucx_map_rehash(UcxMap *map); 237 238 /** 239 * Puts a key/value-pair into the map. 240 * 241 * @param map the map 242 * @param key the key 243 * @param value the value 244 * @return 0 on success, non-zero value on failure 245 */ 246 int ucx_map_put(UcxMap *map, UcxKey key, void *value); 247 248 /** 249 * Retrieves a value by using a key. 250 * 251 * @param map the map 252 * @param key the key 253 * @return the value 254 */ 255 void* ucx_map_get(UcxMap *map, UcxKey key); 256 257 /** 258 * Removes a key/value-pair from the map by using the key. 259 * 260 * @param map the map 261 * @param key the key 262 * @return the removed value 263 */ 264 void* ucx_map_remove(UcxMap *map, UcxKey key); 265 266 /** 267 * Shorthand for putting data with a sstr_t key into the map. 268 * @param map the map 269 * @param key the key 270 * @param value the value 271 * @return 0 on success, non-zero value on failure 272 * @see ucx_map_put() 273 */ 274 #define ucx_map_sstr_put(map, key, value) \ 275 ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value) 276 277 /** 278 * Shorthand for putting data with a C string key into the map. 279 * @param map the map 280 * @param key the key 281 * @param value the value 282 * @return 0 on success, non-zero value on failure 283 * @see ucx_map_put() 284 */ 285 #define ucx_map_cstr_put(map, key, value) \ 286 ucx_map_put(map, ucx_key((void*)key, strlen(key)), (void*)value) 287 288 /** 289 * Shorthand for putting data with an integer key into the map. 290 * @param map the map 291 * @param key the key 292 * @param value the value 293 * @return 0 on success, non-zero value on failure 294 * @see ucx_map_put() 295 */ 296 #define ucx_map_int_put(map, key, value) \ 297 ucx_map_put(map, ucx_key((void*)&key, sizeof(key)), (void*)value) 298 299 /** 300 * Shorthand for getting data from the map with a sstr_t key. 301 * @param map the map 302 * @param key the key 303 * @return the value 304 * @see ucx_map_get() 305 */ 306 #define ucx_map_sstr_get(map, key) \ 307 ucx_map_get(map, ucx_key(key.ptr, key.length)) 308 309 /** 310 * Shorthand for getting data from the map with a C string key. 311 * @param map the map 312 * @param key the key 313 * @return the value 314 * @see ucx_map_get() 315 */ 316 #define ucx_map_cstr_get(map, key) \ 317 ucx_map_get(map, ucx_key((void*)key, strlen(key))) 318 319 /** 320 * Shorthand for getting data from the map with an integer key. 321 * @param map the map 322 * @param key the key 323 * @return the value 324 * @see ucx_map_get() 325 */ 326 #define ucx_map_int_get(map, key) \ 327 ucx_map_get(map, ucx_key((void*)&key, sizeof(int))) 328 329 /** 330 * Shorthand for removing data from the map with a sstr_t key. 331 * @param map the map 332 * @param key the key 333 * @return the removed value 334 * @see ucx_map_remove() 335 */ 336 #define ucx_map_sstr_remove(map, key) \ 337 ucx_map_remove(map, ucx_key(key.ptr, key.length)) 338 339 /** 340 * Shorthand for removing data from the map with a C string key. 341 * @param map the map 342 * @param key the key 343 * @return the removed value 344 * @see ucx_map_remove() 345 */ 346 #define ucx_map_cstr_remove(map, key) \ 347 ucx_map_remove(map, ucx_key((void*)key, strlen(key))) 348 349 /** 350 * Shorthand for removing data from the map with an integer key. 351 * @param map the map 352 * @param key the key 353 * @return the removed value 354 * @see ucx_map_remove() 355 */ 356 #define ucx_map_int_remove(map, key) \ 357 ucx_map_remove(map, ucx_key((void*)&key, sizeof(key))) 358 359 /** 360 * Creates a UcxKey based on the given data. 361 * 362 * This function implicitly computes the hash. 363 * 364 * @param data the data for the key 365 * @param len the length of the data 366 * @return a UcxKey with implicitly computed hash 367 * @see ucx_hash() 368 */ 369 UcxKey ucx_key(void *data, size_t len); 370 371 /** 372 * Computes a murmur hash-2. 373 * 374 * @param data the data to hash 375 * @param len the length of the data 376 * @return the murmur hash-2 of the data 377 */ 378 int ucx_hash(const char *data, size_t len); 379 380 /** 381 * Creates an iterator for a map. 382 * 383 * Note: A UcxMapIterator iterates over all elements in all element 384 * lists successively. Therefore the order highly depends on the key hashes and 385 * may vary under different map sizes. So generally you may NOT rely on 386 * the iteration order. 387 * 388 * Note: The iterator is NOT initialized. You need to call 389 * ucx_map_iter_next() at least once before accessing any information. However, 390 * it is not recommended to access the fields of a UcxMapIterator directly. 391 * 392 * @param map the map to create the iterator for 393 * @return an iterator initialized on the first element of the 394 * first element list 395 * @see ucx_map_iter_next() 396 */ 397 UcxMapIterator ucx_map_iterator(UcxMap *map); 398 399 /** 400 * Proceeds to the next element of the map (if any). 401 * 402 * Subsequent calls on the same iterator proceed to the next element and 403 * store the key/value-pair into the memory specified as arguments of this 404 * function. 405 * 406 * If no further elements are found, this function returns zero and leaves the 407 * last found key/value-pair in memory. 408 * 409 * @param iterator the iterator to use 410 * @param key a pointer to the memory where to store the key 411 * @param value a pointer to the memory where to store the value 412 * @return 1, if another element was found, 0 if all elements has been processed 413 * @see ucx_map_iterator() 414 */ 415 int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value); 416 417 418 #ifdef __cplusplus 419 } 420 #endif 421 422 #endif /* UCX_MAP_H */ 423 424

UNIXworkcode

UNIXwork`code`