1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/ucx/map.h Tue Oct 17 16:15:41 2017 +0200 1.3 @@ -0,0 +1,423 @@ 1.4 +/* 1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 + * 1.7 + * Copyright 2017 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/ucx.h> 1.48 +#include <ucx/string.h> 1.49 +#include <ucx/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 for a key of a UcxMap. */ 1.96 +struct UcxKey { 1.97 + /** The key data. */ 1.98 + void *data; 1.99 + /** The length of the key data. */ 1.100 + size_t len; 1.101 + /** The hash value of the key data. */ 1.102 + int hash; 1.103 +}; 1.104 + 1.105 +/** Structure for an element of a UcxMap. */ 1.106 +struct UcxMapElement { 1.107 + /** The value data. */ 1.108 + void *data; 1.109 + 1.110 + /** A pointer to the next element in the current list. */ 1.111 + UcxMapElement *next; 1.112 + 1.113 + /** The corresponding key. */ 1.114 + UcxKey key; 1.115 +}; 1.116 + 1.117 +/** Structure for an iterator over a UcxMap. */ 1.118 +struct UcxMapIterator { 1.119 + /** The map to iterate over. */ 1.120 + UcxMap *map; 1.121 + 1.122 + /** The current map element. */ 1.123 + UcxMapElement *cur; 1.124 + 1.125 + /** 1.126 + * The current index of the element list array. 1.127 + * <b>Attention: </b> this is <b>NOT</b> the element index! Do <b>NOT</b> 1.128 + * manually iterate over the map by increasing this index. Use 1.129 + * ucx_map_iter_next(). 1.130 + * @see UcxMap.map*/ 1.131 + size_t index; 1.132 +}; 1.133 + 1.134 +/** 1.135 + * Creates a new hash map with the specified size. 1.136 + * @param size the size of the hash map 1.137 + * @return a pointer to the new hash map 1.138 + */ 1.139 +UcxMap *ucx_map_new(size_t size); 1.140 + 1.141 +/** 1.142 + * Creates a new hash map with the specified size using a UcxAllocator. 1.143 + * @param allocator the allocator to use 1.144 + * @param size the size of the hash map 1.145 + * @return a pointer to the new hash map 1.146 + */ 1.147 +UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size); 1.148 + 1.149 +/** 1.150 + * Frees a hash map. 1.151 + * 1.152 + * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content() 1.153 + * before calling this function to achieve that. 1.154 + * 1.155 + * @param map the map to be freed 1.156 + * @see ucx_map_free_content() 1.157 + */ 1.158 +void ucx_map_free(UcxMap *map); 1.159 + 1.160 +/** 1.161 + * Frees the contents of a hash map. 1.162 + * 1.163 + * This is a convenience function that iterates over the map and passes all 1.164 + * values to the specified destructor function (e.g. stdlib free()). 1.165 + * 1.166 + * You must ensure, that it is valid to pass each value in the map to the same 1.167 + * destructor function. 1.168 + * 1.169 + * You should free or clear the map afterwards, as the contents will be invalid. 1.170 + * 1.171 + * @param map for which the contents shall be freed 1.172 + * @param destr pointer to the destructor function 1.173 + * @see ucx_map_free() 1.174 + * @see ucx_map_clear() 1.175 + */ 1.176 +void ucx_map_free_content(UcxMap *map, ucx_destructor destr); 1.177 + 1.178 +/** 1.179 + * Clears a hash map. 1.180 + * 1.181 + * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content() 1.182 + * before calling this function to achieve that. 1.183 + * 1.184 + * @param map the map to be cleared 1.185 + * @see ucx_map_free_content() 1.186 + */ 1.187 +void ucx_map_clear(UcxMap *map); 1.188 + 1.189 + 1.190 +/** 1.191 + * Copies contents from a map to another map using a copy function. 1.192 + * 1.193 + * <b>Note:</b> The destination map does not need to be empty. However, if it 1.194 + * contains data with keys that are also present in the source map, the contents 1.195 + * are overwritten. 1.196 + * 1.197 + * @param from the source map 1.198 + * @param to the destination map 1.199 + * @param fnc the copy function or <code>NULL</code> if the pointer address 1.200 + * shall be copied 1.201 + * @param data additional data for the copy function 1.202 + * @return 0 on success or a non-zero value on memory allocation errors 1.203 + */ 1.204 +int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, 1.205 + copy_func fnc, void *data); 1.206 + 1.207 +/** 1.208 + * Clones the map and rehashes if necessary. 1.209 + * 1.210 + * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant. 1.211 + * This function <i>always</i> ensures a new UcxMap.size of at least 1.212 + * 2.5*UcxMap.count. 1.213 + * 1.214 + * @param map the map to clone 1.215 + * @param fnc the copy function to use or <code>NULL</code> if the new and 1.216 + * the old map shall share the data pointers 1.217 + * @param data additional data for the copy function 1.218 + * @return the cloned map 1.219 + * @see ucx_map_copy() 1.220 + */ 1.221 +UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data); 1.222 + 1.223 +/** 1.224 + * Increases size of the hash map, if necessary. 1.225 + * 1.226 + * The load value is 0.75*UcxMap.size. If the element count exceeds the load 1.227 + * value, the map needs to be rehashed. Otherwise no action is performed and 1.228 + * this function simply returns 0. 1.229 + * 1.230 + * The rehashing process ensures, that the UcxMap.size is at least 1.231 + * 2.5*UcxMap.count. So there is enough room for additional elements without 1.232 + * the need of another soon rehashing. 1.233 + * 1.234 + * You can use this function to dramatically increase access performance. 1.235 + * 1.236 + * @param map the map to rehash 1.237 + * @return 1, if a memory allocation error occurred, 0 otherwise 1.238 + */ 1.239 +int ucx_map_rehash(UcxMap *map); 1.240 + 1.241 +/** 1.242 + * Puts a key/value-pair into the map. 1.243 + * 1.244 + * @param map the map 1.245 + * @param key the key 1.246 + * @param value the value 1.247 + * @return 0 on success, non-zero value on failure 1.248 + */ 1.249 +int ucx_map_put(UcxMap *map, UcxKey key, void *value); 1.250 + 1.251 +/** 1.252 + * Retrieves a value by using a key. 1.253 + * 1.254 + * @param map the map 1.255 + * @param key the key 1.256 + * @return the value 1.257 + */ 1.258 +void* ucx_map_get(UcxMap *map, UcxKey key); 1.259 + 1.260 +/** 1.261 + * Removes a key/value-pair from the map by using the key. 1.262 + * 1.263 + * @param map the map 1.264 + * @param key the key 1.265 + * @return the removed value 1.266 + */ 1.267 +void* ucx_map_remove(UcxMap *map, UcxKey key); 1.268 + 1.269 +/** 1.270 + * Shorthand for putting data with a sstr_t key into the map. 1.271 + * @param map the map 1.272 + * @param key the key 1.273 + * @param value the value 1.274 + * @return 0 on success, non-zero value on failure 1.275 + * @see ucx_map_put() 1.276 + */ 1.277 +#define ucx_map_sstr_put(map, key, value) \ 1.278 + ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value) 1.279 + 1.280 +/** 1.281 + * Shorthand for putting data with a C string key into the map. 1.282 + * @param map the map 1.283 + * @param key the key 1.284 + * @param value the value 1.285 + * @return 0 on success, non-zero value on failure 1.286 + * @see ucx_map_put() 1.287 + */ 1.288 +#define ucx_map_cstr_put(map, key, value) \ 1.289 + ucx_map_put(map, ucx_key((void*)key, strlen(key)), (void*)value) 1.290 + 1.291 +/** 1.292 + * Shorthand for putting data with an integer key into the map. 1.293 + * @param map the map 1.294 + * @param key the key 1.295 + * @param value the value 1.296 + * @return 0 on success, non-zero value on failure 1.297 + * @see ucx_map_put() 1.298 + */ 1.299 +#define ucx_map_int_put(map, key, value) \ 1.300 + ucx_map_put(map, ucx_key((void*)&key, sizeof(key)), (void*)value) 1.301 + 1.302 +/** 1.303 + * Shorthand for getting data from the map with a sstr_t key. 1.304 + * @param map the map 1.305 + * @param key the key 1.306 + * @return the value 1.307 + * @see ucx_map_get() 1.308 + */ 1.309 +#define ucx_map_sstr_get(map, key) \ 1.310 + ucx_map_get(map, ucx_key(key.ptr, key.length)) 1.311 + 1.312 +/** 1.313 + * Shorthand for getting data from the map with a C string key. 1.314 + * @param map the map 1.315 + * @param key the key 1.316 + * @return the value 1.317 + * @see ucx_map_get() 1.318 + */ 1.319 +#define ucx_map_cstr_get(map, key) \ 1.320 + ucx_map_get(map, ucx_key((void*)key, strlen(key))) 1.321 + 1.322 +/** 1.323 + * Shorthand for getting data from the map with an integer key. 1.324 + * @param map the map 1.325 + * @param key the key 1.326 + * @return the value 1.327 + * @see ucx_map_get() 1.328 + */ 1.329 +#define ucx_map_int_get(map, key) \ 1.330 + ucx_map_get(map, ucx_key((void*)&key, sizeof(int))) 1.331 + 1.332 +/** 1.333 + * Shorthand for removing 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 removed value 1.337 + * @see ucx_map_remove() 1.338 + */ 1.339 +#define ucx_map_sstr_remove(map, key) \ 1.340 + ucx_map_remove(map, ucx_key(key.ptr, key.length)) 1.341 + 1.342 +/** 1.343 + * Shorthand for removing 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 removed value 1.347 + * @see ucx_map_remove() 1.348 + */ 1.349 +#define ucx_map_cstr_remove(map, key) \ 1.350 + ucx_map_remove(map, ucx_key((void*)key, strlen(key))) 1.351 + 1.352 +/** 1.353 + * Shorthand for removing data from the map with an integer key. 1.354 + * @param map the map 1.355 + * @param key the key 1.356 + * @return the removed value 1.357 + * @see ucx_map_remove() 1.358 + */ 1.359 +#define ucx_map_int_remove(map, key) \ 1.360 + ucx_map_remove(map, ucx_key((void*)&key, sizeof(key))) 1.361 + 1.362 +/** 1.363 + * Creates a UcxKey based on the given data. 1.364 + * 1.365 + * This function implicitly computes the hash. 1.366 + * 1.367 + * @param data the data for the key 1.368 + * @param len the length of the data 1.369 + * @return a UcxKey with implicitly computed hash 1.370 + * @see ucx_hash() 1.371 + */ 1.372 +UcxKey ucx_key(void *data, size_t len); 1.373 + 1.374 +/** 1.375 + * Computes a murmur hash-2. 1.376 + * 1.377 + * @param data the data to hash 1.378 + * @param len the length of the data 1.379 + * @return the murmur hash-2 of the data 1.380 + */ 1.381 +int ucx_hash(const char *data, size_t len); 1.382 + 1.383 +/** 1.384 + * Creates an iterator for a map. 1.385 + * 1.386 + * <b>Note:</b> A UcxMapIterator iterates over all elements in all element 1.387 + * lists successively. Therefore the order highly depends on the key hashes and 1.388 + * may vary under different map sizes. So generally you may <b>NOT</b> rely on 1.389 + * the iteration order. 1.390 + * 1.391 + * <b>Note:</b> The iterator is <b>NOT</b> initialized. You need to call 1.392 + * ucx_map_iter_next() at least once before accessing any information. However, 1.393 + * it is not recommended to access the fields of a UcxMapIterator directly. 1.394 + * 1.395 + * @param map the map to create the iterator for 1.396 + * @return an iterator initialized on the first element of the 1.397 + * first element list 1.398 + * @see ucx_map_iter_next() 1.399 + */ 1.400 +UcxMapIterator ucx_map_iterator(UcxMap *map); 1.401 + 1.402 +/** 1.403 + * Proceeds to the next element of the map (if any). 1.404 + * 1.405 + * Subsequent calls on the same iterator proceed to the next element and 1.406 + * store the key/value-pair into the memory specified as arguments of this 1.407 + * function. 1.408 + * 1.409 + * If no further elements are found, this function returns zero and leaves the 1.410 + * last found key/value-pair in memory. 1.411 + * 1.412 + * @param iterator the iterator to use 1.413 + * @param key a pointer to the memory where to store the key 1.414 + * @param value a pointer to the memory where to store the value 1.415 + * @return 1, if another element was found, 0 if all elements has been processed 1.416 + * @see ucx_map_iterator() 1.417 + */ 1.418 +int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value); 1.419 + 1.420 + 1.421 +#ifdef __cplusplus 1.422 +} 1.423 +#endif 1.424 + 1.425 +#endif /* UCX_MAP_H */ 1.426 +