1.1 --- a/src/ucx/map.h Mon Dec 30 09:54:10 2019 +0100 1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 1.3 @@ -1,549 +0,0 @@ 1.4 -/* 1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 - * 1.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. 1.8 - * 1.9 - * Redistribution and use in source and binary forms, with or without 1.10 - * modification, are permitted provided that the following conditions are met: 1.11 - * 1.12 - * 1. Redistributions of source code must retain the above copyright 1.13 - * notice, this list of conditions and the following disclaimer. 1.14 - * 1.15 - * 2. Redistributions in binary form must reproduce the above copyright 1.16 - * notice, this list of conditions and the following disclaimer in the 1.17 - * documentation and/or other materials provided with the distribution. 1.18 - * 1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 - * POSSIBILITY OF SUCH DAMAGE. 1.30 - */ 1.31 - 1.32 -/** 1.33 - * @file map.h 1.34 - * 1.35 - * Hash map implementation. 1.36 - * 1.37 - * This implementation uses murmur hash 2 and separate chaining with linked 1.38 - * lists. 1.39 - * 1.40 - * @author Mike Becker 1.41 - * @author Olaf Wintermann 1.42 - */ 1.43 - 1.44 -#ifndef UCX_MAP_H 1.45 -#define UCX_MAP_H 1.46 - 1.47 -#include "ucx.h" 1.48 -#include "string.h" 1.49 -#include "allocator.h" 1.50 -#include <stdio.h> 1.51 - 1.52 -#ifdef __cplusplus 1.53 -extern "C" { 1.54 -#endif 1.55 - 1.56 -/** 1.57 - * Loop statement for UCX maps. 1.58 - * 1.59 - * The <code>key</code> variable is implicitly defined, but the 1.60 - * <code>value</code> variable must be already declared as type information 1.61 - * cannot be inferred. 1.62 - * 1.63 - * @param key the variable name for the key 1.64 - * @param value the variable name for the value 1.65 - * @param iter a UcxMapIterator 1.66 - * @see ucx_map_iterator() 1.67 - */ 1.68 -#define UCX_MAP_FOREACH(key,value,iter) \ 1.69 - for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);) 1.70 - 1.71 -/** Type for the UCX map. @see UcxMap */ 1.72 -typedef struct UcxMap UcxMap; 1.73 - 1.74 -/** Type for a key of a UcxMap. @see UcxKey */ 1.75 -typedef struct UcxKey UcxKey; 1.76 - 1.77 -/** Type for an element of a UcxMap. @see UcxMapElement */ 1.78 -typedef struct UcxMapElement UcxMapElement; 1.79 - 1.80 -/** Type for an iterator over a UcxMap. @see UcxMapIterator */ 1.81 -typedef struct UcxMapIterator UcxMapIterator; 1.82 - 1.83 -/** Structure for the UCX map. */ 1.84 -struct UcxMap { 1.85 - /** An allocator that is used for the map elements. */ 1.86 - UcxAllocator *allocator; 1.87 - /** The array of map element lists. */ 1.88 - UcxMapElement **map; 1.89 - /** The size of the map is the length of the element list array. */ 1.90 - size_t size; 1.91 - /** The count of elements currently stored in this map. */ 1.92 - size_t count; 1.93 -}; 1.94 - 1.95 -/** Structure to publicly denote a key of a UcxMap. */ 1.96 -struct UcxKey { 1.97 - /** The key data. */ 1.98 - const void *data; 1.99 - /** The length of the key data. */ 1.100 - size_t len; 1.101 - /** A cache for the hash value of the key data. */ 1.102 - int hash; 1.103 -}; 1.104 - 1.105 -/** Internal structure for a key of a UcxMap. */ 1.106 -struct UcxMapKey { 1.107 - /** The key data. */ 1.108 - void *data; 1.109 - /** The length of the key data. */ 1.110 - size_t len; 1.111 - /** The hash value of the key data. */ 1.112 - int hash; 1.113 -}; 1.114 - 1.115 -/** Structure for an element of a UcxMap. */ 1.116 -struct UcxMapElement { 1.117 - /** The value data. */ 1.118 - void *data; 1.119 - 1.120 - /** A pointer to the next element in the current list. */ 1.121 - UcxMapElement *next; 1.122 - 1.123 - /** The corresponding key. */ 1.124 - struct UcxMapKey key; 1.125 -}; 1.126 - 1.127 -/** Structure for an iterator over a UcxMap. */ 1.128 -struct UcxMapIterator { 1.129 - /** The map to iterate over. */ 1.130 - UcxMap const *map; 1.131 - 1.132 - /** The current map element. */ 1.133 - UcxMapElement *cur; 1.134 - 1.135 - /** 1.136 - * The current index of the element list array. 1.137 - * <b>Attention: </b> this is <b>NOT</b> the element index! Do <b>NOT</b> 1.138 - * manually iterate over the map by increasing this index. Use 1.139 - * ucx_map_iter_next(). 1.140 - * @see UcxMap.map*/ 1.141 - size_t index; 1.142 -}; 1.143 - 1.144 -/** 1.145 - * Creates a new hash map with the specified size. 1.146 - * @param size the size of the hash map 1.147 - * @return a pointer to the new hash map 1.148 - */ 1.149 -UcxMap *ucx_map_new(size_t size); 1.150 - 1.151 -/** 1.152 - * Creates a new hash map with the specified size using a UcxAllocator. 1.153 - * @param allocator the allocator to use 1.154 - * @param size the size of the hash map 1.155 - * @return a pointer to the new hash map 1.156 - */ 1.157 -UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size); 1.158 - 1.159 -/** 1.160 - * Frees a hash map. 1.161 - * 1.162 - * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content() 1.163 - * before calling this function to achieve that. 1.164 - * 1.165 - * @param map the map to be freed 1.166 - * @see ucx_map_free_content() 1.167 - */ 1.168 -void ucx_map_free(UcxMap *map); 1.169 - 1.170 -/** 1.171 - * Frees the contents of a hash map. 1.172 - * 1.173 - * This is a convenience function that iterates over the map and passes all 1.174 - * values to the specified destructor function. 1.175 - * 1.176 - * If no destructor is specified (<code>NULL</code>), the free() function of 1.177 - * the map's own allocator is used. 1.178 - * 1.179 - * You must ensure, that it is valid to pass each value in the map to the same 1.180 - * destructor function. 1.181 - * 1.182 - * You should free or clear the map afterwards, as the contents will be invalid. 1.183 - * 1.184 - * @param map for which the contents shall be freed 1.185 - * @param destr optional pointer to a destructor function 1.186 - * @see ucx_map_free() 1.187 - * @see ucx_map_clear() 1.188 - */ 1.189 -void ucx_map_free_content(UcxMap *map, ucx_destructor destr); 1.190 - 1.191 -/** 1.192 - * Clears a hash map. 1.193 - * 1.194 - * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content() 1.195 - * before calling this function to achieve that. 1.196 - * 1.197 - * @param map the map to be cleared 1.198 - * @see ucx_map_free_content() 1.199 - */ 1.200 -void ucx_map_clear(UcxMap *map); 1.201 - 1.202 - 1.203 -/** 1.204 - * Copies contents from a map to another map using a copy function. 1.205 - * 1.206 - * <b>Note:</b> The destination map does not need to be empty. However, if it 1.207 - * contains data with keys that are also present in the source map, the contents 1.208 - * are overwritten. 1.209 - * 1.210 - * @param from the source map 1.211 - * @param to the destination map 1.212 - * @param fnc the copy function or <code>NULL</code> if the pointer address 1.213 - * shall be copied 1.214 - * @param data additional data for the copy function 1.215 - * @return 0 on success or a non-zero value on memory allocation errors 1.216 - */ 1.217 -int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data); 1.218 - 1.219 -/** 1.220 - * Clones the map and rehashes if necessary. 1.221 - * 1.222 - * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant. 1.223 - * This function <i>always</i> ensures a new UcxMap.size of at least 1.224 - * 2.5*UcxMap.count. 1.225 - * 1.226 - * @param map the map to clone 1.227 - * @param fnc the copy function to use or <code>NULL</code> if the new and 1.228 - * the old map shall share the data pointers 1.229 - * @param data additional data for the copy function 1.230 - * @return the cloned map 1.231 - * @see ucx_map_copy() 1.232 - */ 1.233 -UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data); 1.234 - 1.235 -/** 1.236 - * Clones the map and rehashes if necessary. 1.237 - * 1.238 - * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant. 1.239 - * This function <i>always</i> ensures a new UcxMap.size of at least 1.240 - * 2.5*UcxMap.count. 1.241 - * 1.242 - * @param allocator the allocator to use for the cloned map 1.243 - * @param map the map to clone 1.244 - * @param fnc the copy function to use or <code>NULL</code> if the new and 1.245 - * the old map shall share the data pointers 1.246 - * @param data additional data for the copy function 1.247 - * @return the cloned map 1.248 - * @see ucx_map_copy() 1.249 - */ 1.250 -UcxMap *ucx_map_clone_a(UcxAllocator *allocator, 1.251 - UcxMap const *map, copy_func fnc, void *data); 1.252 - 1.253 -/** 1.254 - * Increases size of the hash map, if necessary. 1.255 - * 1.256 - * The load value is 0.75*UcxMap.size. If the element count exceeds the load 1.257 - * value, the map needs to be rehashed. Otherwise no action is performed and 1.258 - * this function simply returns 0. 1.259 - * 1.260 - * The rehashing process ensures, that the UcxMap.size is at least 1.261 - * 2.5*UcxMap.count. So there is enough room for additional elements without 1.262 - * the need of another soon rehashing. 1.263 - * 1.264 - * You can use this function to dramatically increase access performance. 1.265 - * 1.266 - * @param map the map to rehash 1.267 - * @return 1, if a memory allocation error occurred, 0 otherwise 1.268 - */ 1.269 -int ucx_map_rehash(UcxMap *map); 1.270 - 1.271 -/** 1.272 - * Puts a key/value-pair into the map. 1.273 - * 1.274 - * @param map the map 1.275 - * @param key the key 1.276 - * @param value the value 1.277 - * @return 0 on success, non-zero value on failure 1.278 - */ 1.279 -int ucx_map_put(UcxMap *map, UcxKey key, void *value); 1.280 - 1.281 -/** 1.282 - * Retrieves a value by using a key. 1.283 - * 1.284 - * @param map the map 1.285 - * @param key the key 1.286 - * @return the value 1.287 - */ 1.288 -void* ucx_map_get(UcxMap const *map, UcxKey key); 1.289 - 1.290 -/** 1.291 - * Removes a key/value-pair from the map by using the key. 1.292 - * 1.293 - * @param map the map 1.294 - * @param key the key 1.295 - * @return the removed value 1.296 - */ 1.297 -void* ucx_map_remove(UcxMap *map, UcxKey key); 1.298 - 1.299 -/** 1.300 - * Shorthand for putting data with a sstr_t key into the map. 1.301 - * @param map the map 1.302 - * @param key the key 1.303 - * @param value the value 1.304 - * @return 0 on success, non-zero value on failure 1.305 - * @see ucx_map_put() 1.306 - */ 1.307 -#define ucx_map_sstr_put(map, key, value) \ 1.308 - ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value) 1.309 - 1.310 -/** 1.311 - * Shorthand for putting data with a C string key into the map. 1.312 - * @param map the map 1.313 - * @param key the key 1.314 - * @param value the value 1.315 - * @return 0 on success, non-zero value on failure 1.316 - * @see ucx_map_put() 1.317 - */ 1.318 -#define ucx_map_cstr_put(map, key, value) \ 1.319 - ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value) 1.320 - 1.321 -/** 1.322 - * Shorthand for putting data with an integer key into the map. 1.323 - * @param map the map 1.324 - * @param key the key 1.325 - * @param value the value 1.326 - * @return 0 on success, non-zero value on failure 1.327 - * @see ucx_map_put() 1.328 - */ 1.329 -#define ucx_map_int_put(map, key, value) \ 1.330 - ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value) 1.331 - 1.332 -/** 1.333 - * Shorthand for getting data from the map with a sstr_t key. 1.334 - * @param map the map 1.335 - * @param key the key 1.336 - * @return the value 1.337 - * @see ucx_map_get() 1.338 - */ 1.339 -#define ucx_map_sstr_get(map, key) \ 1.340 - ucx_map_get(map, ucx_key(key.ptr, key.length)) 1.341 - 1.342 -/** 1.343 - * Shorthand for getting data from the map with a C string key. 1.344 - * @param map the map 1.345 - * @param key the key 1.346 - * @return the value 1.347 - * @see ucx_map_get() 1.348 - */ 1.349 -#define ucx_map_cstr_get(map, key) \ 1.350 - ucx_map_get(map, ucx_key(key, strlen(key))) 1.351 - 1.352 -/** 1.353 - * Shorthand for getting data from the map with an integer key. 1.354 - * @param map the map 1.355 - * @param key the key 1.356 - * @return the value 1.357 - * @see ucx_map_get() 1.358 - */ 1.359 -#define ucx_map_int_get(map, key) \ 1.360 - ucx_map_get(map, ucx_key(&key, sizeof(int))) 1.361 - 1.362 -/** 1.363 - * Shorthand for removing data from the map with a sstr_t key. 1.364 - * @param map the map 1.365 - * @param key the key 1.366 - * @return the removed value 1.367 - * @see ucx_map_remove() 1.368 - */ 1.369 -#define ucx_map_sstr_remove(map, key) \ 1.370 - ucx_map_remove(map, ucx_key(key.ptr, key.length)) 1.371 - 1.372 -/** 1.373 - * Shorthand for removing data from the map with a C string key. 1.374 - * @param map the map 1.375 - * @param key the key 1.376 - * @return the removed value 1.377 - * @see ucx_map_remove() 1.378 - */ 1.379 -#define ucx_map_cstr_remove(map, key) \ 1.380 - ucx_map_remove(map, ucx_key(key, strlen(key))) 1.381 - 1.382 -/** 1.383 - * Shorthand for removing data from the map with an integer key. 1.384 - * @param map the map 1.385 - * @param key the key 1.386 - * @return the removed value 1.387 - * @see ucx_map_remove() 1.388 - */ 1.389 -#define ucx_map_int_remove(map, key) \ 1.390 - ucx_map_remove(map, ucx_key(&key, sizeof(key))) 1.391 - 1.392 -/** 1.393 - * Creates a UcxKey based on the given data. 1.394 - * 1.395 - * This function implicitly computes the hash. 1.396 - * 1.397 - * @param data the data for the key 1.398 - * @param len the length of the data 1.399 - * @return a UcxKey with implicitly computed hash 1.400 - * @see ucx_hash() 1.401 - */ 1.402 -UcxKey ucx_key(const void *data, size_t len); 1.403 - 1.404 -/** 1.405 - * Computes a murmur hash-2. 1.406 - * 1.407 - * @param data the data to hash 1.408 - * @param len the length of the data 1.409 - * @return the murmur hash-2 of the data 1.410 - */ 1.411 -int ucx_hash(const char *data, size_t len); 1.412 - 1.413 -/** 1.414 - * Creates an iterator for a map. 1.415 - * 1.416 - * <b>Note:</b> A UcxMapIterator iterates over all elements in all element 1.417 - * lists successively. Therefore the order highly depends on the key hashes and 1.418 - * may vary under different map sizes. So generally you may <b>NOT</b> rely on 1.419 - * the iteration order. 1.420 - * 1.421 - * <b>Note:</b> The iterator is <b>NOT</b> initialized. You need to call 1.422 - * ucx_map_iter_next() at least once before accessing any information. However, 1.423 - * it is not recommended to access the fields of a UcxMapIterator directly. 1.424 - * 1.425 - * @param map the map to create the iterator for 1.426 - * @return an iterator initialized on the first element of the 1.427 - * first element list 1.428 - * @see ucx_map_iter_next() 1.429 - */ 1.430 -UcxMapIterator ucx_map_iterator(UcxMap const *map); 1.431 - 1.432 -/** 1.433 - * Proceeds to the next element of the map (if any). 1.434 - * 1.435 - * Subsequent calls on the same iterator proceed to the next element and 1.436 - * store the key/value-pair into the memory specified as arguments of this 1.437 - * function. 1.438 - * 1.439 - * If no further elements are found, this function returns zero and leaves the 1.440 - * last found key/value-pair in memory. 1.441 - * 1.442 - * @param iterator the iterator to use 1.443 - * @param key a pointer to the memory where to store the key 1.444 - * @param value a pointer to the memory where to store the value 1.445 - * @return 1, if another element was found, 0 if all elements has been processed 1.446 - * @see ucx_map_iterator() 1.447 - */ 1.448 -int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value); 1.449 - 1.450 -/** 1.451 - * Returns the union of two maps. 1.452 - * 1.453 - * The union is a fresh map which is filled by two successive calls of 1.454 - * ucx_map_copy() on the two input maps. 1.455 - * 1.456 - * @param first the first source map 1.457 - * @param second the second source map 1.458 - * @param cpfnc a function to copy the elements 1.459 - * @param cpdata additional data for the copy function 1.460 - * @return a new map containing the union 1.461 - */ 1.462 -UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second, 1.463 - copy_func cpfnc, void* cpdata); 1.464 - 1.465 -/** 1.466 - * Returns the union of two maps. 1.467 - * 1.468 - * The union is a fresh map which is filled by two successive calls of 1.469 - * ucx_map_copy() on the two input maps. 1.470 - * 1.471 - * @param allocator the allocator that shall be used by the new map 1.472 - * @param first the first source map 1.473 - * @param second the second source map 1.474 - * @param cpfnc a function to copy the elements 1.475 - * @param cpdata additional data for the copy function 1.476 - * @return a new map containing the union 1.477 - */ 1.478 -UcxMap* ucx_map_union_a(UcxAllocator *allocator, 1.479 - const UcxMap *first, const UcxMap *second, 1.480 - copy_func cpfnc, void* cpdata); 1.481 - 1.482 -/** 1.483 - * Returns the intersection of two maps. 1.484 - * 1.485 - * The intersection is defined as a copy of the first map with every element 1.486 - * removed that has no valid key in the second map. 1.487 - * 1.488 - * @param first the first source map 1.489 - * @param second the second source map 1.490 - * @param cpfnc a function to copy the elements 1.491 - * @param cpdata additional data for the copy function 1.492 - * @return a new map containing the intersection 1.493 - */ 1.494 -UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second, 1.495 - copy_func cpfnc, void* cpdata); 1.496 - 1.497 -/** 1.498 - * Returns the intersection of two maps. 1.499 - * 1.500 - * The intersection is defined as a copy of the first map with every element 1.501 - * removed that has no valid key in the second map. 1.502 - * 1.503 - * @param allocator the allocator that shall be used by the new map 1.504 - * @param first the first source map 1.505 - * @param second the second source map 1.506 - * @param cpfnc a function to copy the elements 1.507 - * @param cpdata additional data for the copy function 1.508 - * @return a new map containing the intersection 1.509 - */ 1.510 -UcxMap* ucx_map_intersection_a(UcxAllocator *allocator, 1.511 - const UcxMap *first, const UcxMap *second, 1.512 - copy_func cpfnc, void* cpdata); 1.513 - 1.514 -/** 1.515 - * Returns the difference of two maps. 1.516 - * 1.517 - * The difference contains a copy of all elements of the first map 1.518 - * for which the corresponding keys cannot be found in the second map. 1.519 - * 1.520 - * @param first the first source map 1.521 - * @param second the second source map 1.522 - * @param cpfnc a function to copy the elements 1.523 - * @param cpdata additional data for the copy function 1.524 - * @return a new list containing the difference 1.525 - */ 1.526 -UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second, 1.527 - copy_func cpfnc, void* cpdata); 1.528 - 1.529 -/** 1.530 - * Returns the difference of two maps. 1.531 - * 1.532 - * The difference contains a copy of all elements of the first map 1.533 - * for which the corresponding keys cannot be found in the second map. 1.534 - * 1.535 - * @param allocator the allocator that shall be used by the new map 1.536 - * @param first the first source map 1.537 - * @param second the second source map 1.538 - * @param cpfnc a function to copy the elements 1.539 - * @param cpdata additional data for the copy function 1.540 - * @return a new list containing the difference 1.541 - */ 1.542 -UcxMap* ucx_map_difference_a(UcxAllocator *allocator, 1.543 - const UcxMap *first, const UcxMap *second, 1.544 - copy_func cpfnc, void* cpdata); 1.545 - 1.546 - 1.547 -#ifdef __cplusplus 1.548 -} 1.549 -#endif 1.550 - 1.551 -#endif /* UCX_MAP_H */ 1.552 -