diff -r 92e482410453 -r d345541018fa src/ucx/map.h --- a/src/ucx/map.h Mon Dec 30 09:54:10 2019 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,549 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -/** - * @file map.h - * - * Hash map implementation. - * - * This implementation uses murmur hash 2 and separate chaining with linked - * lists. - * - * @author Mike Becker - * @author Olaf Wintermann - */ - -#ifndef UCX_MAP_H -#define UCX_MAP_H - -#include "ucx.h" -#include "string.h" -#include "allocator.h" -#include - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Loop statement for UCX maps. - * - * The key variable is implicitly defined, but the - * value variable must be already declared as type information - * cannot be inferred. - * - * @param key the variable name for the key - * @param value the variable name for the value - * @param iter a UcxMapIterator - * @see ucx_map_iterator() - */ -#define UCX_MAP_FOREACH(key,value,iter) \ - for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);) - -/** Type for the UCX map. @see UcxMap */ -typedef struct UcxMap UcxMap; - -/** Type for a key of a UcxMap. @see UcxKey */ -typedef struct UcxKey UcxKey; - -/** Type for an element of a UcxMap. @see UcxMapElement */ -typedef struct UcxMapElement UcxMapElement; - -/** Type for an iterator over a UcxMap. @see UcxMapIterator */ -typedef struct UcxMapIterator UcxMapIterator; - -/** Structure for the UCX map. */ -struct UcxMap { - /** An allocator that is used for the map elements. */ - UcxAllocator *allocator; - /** The array of map element lists. */ - UcxMapElement **map; - /** The size of the map is the length of the element list array. */ - size_t size; - /** The count of elements currently stored in this map. */ - size_t count; -}; - -/** Structure to publicly denote a key of a UcxMap. */ -struct UcxKey { - /** The key data. */ - const void *data; - /** The length of the key data. */ - size_t len; - /** A cache for the hash value of the key data. */ - int hash; -}; - -/** Internal structure for a key of a UcxMap. */ -struct UcxMapKey { - /** The key data. */ - void *data; - /** The length of the key data. */ - size_t len; - /** The hash value of the key data. */ - int hash; -}; - -/** Structure for an element of a UcxMap. */ -struct UcxMapElement { - /** The value data. */ - void *data; - - /** A pointer to the next element in the current list. */ - UcxMapElement *next; - - /** The corresponding key. */ - struct UcxMapKey key; -}; - -/** Structure for an iterator over a UcxMap. */ -struct UcxMapIterator { - /** The map to iterate over. */ - UcxMap const *map; - - /** The current map element. */ - UcxMapElement *cur; - - /** - * The current index of the element list array. - * Attention: this is NOT the element index! Do NOT - * manually iterate over the map by increasing this index. Use - * ucx_map_iter_next(). - * @see UcxMap.map*/ - size_t index; -}; - -/** - * Creates a new hash map with the specified size. - * @param size the size of the hash map - * @return a pointer to the new hash map - */ -UcxMap *ucx_map_new(size_t size); - -/** - * Creates a new hash map with the specified size using a UcxAllocator. - * @param allocator the allocator to use - * @param size the size of the hash map - * @return a pointer to the new hash map - */ -UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size); - -/** - * Frees a hash map. - * - * Note: the contents are not freed, use ucx_map_free_content() - * before calling this function to achieve that. - * - * @param map the map to be freed - * @see ucx_map_free_content() - */ -void ucx_map_free(UcxMap *map); - -/** - * Frees the contents of a hash map. - * - * This is a convenience function that iterates over the map and passes all - * values to the specified destructor function. - * - * If no destructor is specified (NULL), the free() function of - * the map's own allocator is used. - * - * You must ensure, that it is valid to pass each value in the map to the same - * destructor function. - * - * You should free or clear the map afterwards, as the contents will be invalid. - * - * @param map for which the contents shall be freed - * @param destr optional pointer to a destructor function - * @see ucx_map_free() - * @see ucx_map_clear() - */ -void ucx_map_free_content(UcxMap *map, ucx_destructor destr); - -/** - * Clears a hash map. - * - * Note: the contents are not freed, use ucx_map_free_content() - * before calling this function to achieve that. - * - * @param map the map to be cleared - * @see ucx_map_free_content() - */ -void ucx_map_clear(UcxMap *map); - - -/** - * Copies contents from a map to another map using a copy function. - * - * Note: The destination map does not need to be empty. However, if it - * contains data with keys that are also present in the source map, the contents - * are overwritten. - * - * @param from the source map - * @param to the destination map - * @param fnc the copy function or NULL if the pointer address - * shall be copied - * @param data additional data for the copy function - * @return 0 on success or a non-zero value on memory allocation errors - */ -int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data); - -/** - * Clones the map and rehashes if necessary. - * - * Note: In contrast to ucx_map_rehash() the load factor is irrelevant. - * This function always ensures a new UcxMap.size of at least - * 2.5*UcxMap.count. - * - * @param map the map to clone - * @param fnc the copy function to use or NULL if the new and - * the old map shall share the data pointers - * @param data additional data for the copy function - * @return the cloned map - * @see ucx_map_copy() - */ -UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data); - -/** - * Clones the map and rehashes if necessary. - * - * Note: In contrast to ucx_map_rehash() the load factor is irrelevant. - * This function always ensures a new UcxMap.size of at least - * 2.5*UcxMap.count. - * - * @param allocator the allocator to use for the cloned map - * @param map the map to clone - * @param fnc the copy function to use or NULL if the new and - * the old map shall share the data pointers - * @param data additional data for the copy function - * @return the cloned map - * @see ucx_map_copy() - */ -UcxMap *ucx_map_clone_a(UcxAllocator *allocator, - UcxMap const *map, copy_func fnc, void *data); - -/** - * Increases size of the hash map, if necessary. - * - * The load value is 0.75*UcxMap.size. If the element count exceeds the load - * value, the map needs to be rehashed. Otherwise no action is performed and - * this function simply returns 0. - * - * The rehashing process ensures, that the UcxMap.size is at least - * 2.5*UcxMap.count. So there is enough room for additional elements without - * the need of another soon rehashing. - * - * You can use this function to dramatically increase access performance. - * - * @param map the map to rehash - * @return 1, if a memory allocation error occurred, 0 otherwise - */ -int ucx_map_rehash(UcxMap *map); - -/** - * Puts a key/value-pair into the map. - * - * @param map the map - * @param key the key - * @param value the value - * @return 0 on success, non-zero value on failure - */ -int ucx_map_put(UcxMap *map, UcxKey key, void *value); - -/** - * Retrieves a value by using a key. - * - * @param map the map - * @param key the key - * @return the value - */ -void* ucx_map_get(UcxMap const *map, UcxKey key); - -/** - * Removes a key/value-pair from the map by using the key. - * - * @param map the map - * @param key the key - * @return the removed value - */ -void* ucx_map_remove(UcxMap *map, UcxKey key); - -/** - * Shorthand for putting data with a sstr_t key into the map. - * @param map the map - * @param key the key - * @param value the value - * @return 0 on success, non-zero value on failure - * @see ucx_map_put() - */ -#define ucx_map_sstr_put(map, key, value) \ - ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value) - -/** - * Shorthand for putting data with a C string key into the map. - * @param map the map - * @param key the key - * @param value the value - * @return 0 on success, non-zero value on failure - * @see ucx_map_put() - */ -#define ucx_map_cstr_put(map, key, value) \ - ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value) - -/** - * Shorthand for putting data with an integer key into the map. - * @param map the map - * @param key the key - * @param value the value - * @return 0 on success, non-zero value on failure - * @see ucx_map_put() - */ -#define ucx_map_int_put(map, key, value) \ - ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value) - -/** - * Shorthand for getting data from the map with a sstr_t key. - * @param map the map - * @param key the key - * @return the value - * @see ucx_map_get() - */ -#define ucx_map_sstr_get(map, key) \ - ucx_map_get(map, ucx_key(key.ptr, key.length)) - -/** - * Shorthand for getting data from the map with a C string key. - * @param map the map - * @param key the key - * @return the value - * @see ucx_map_get() - */ -#define ucx_map_cstr_get(map, key) \ - ucx_map_get(map, ucx_key(key, strlen(key))) - -/** - * Shorthand for getting data from the map with an integer key. - * @param map the map - * @param key the key - * @return the value - * @see ucx_map_get() - */ -#define ucx_map_int_get(map, key) \ - ucx_map_get(map, ucx_key(&key, sizeof(int))) - -/** - * Shorthand for removing data from the map with a sstr_t key. - * @param map the map - * @param key the key - * @return the removed value - * @see ucx_map_remove() - */ -#define ucx_map_sstr_remove(map, key) \ - ucx_map_remove(map, ucx_key(key.ptr, key.length)) - -/** - * Shorthand for removing data from the map with a C string key. - * @param map the map - * @param key the key - * @return the removed value - * @see ucx_map_remove() - */ -#define ucx_map_cstr_remove(map, key) \ - ucx_map_remove(map, ucx_key(key, strlen(key))) - -/** - * Shorthand for removing data from the map with an integer key. - * @param map the map - * @param key the key - * @return the removed value - * @see ucx_map_remove() - */ -#define ucx_map_int_remove(map, key) \ - ucx_map_remove(map, ucx_key(&key, sizeof(key))) - -/** - * Creates a UcxKey based on the given data. - * - * This function implicitly computes the hash. - * - * @param data the data for the key - * @param len the length of the data - * @return a UcxKey with implicitly computed hash - * @see ucx_hash() - */ -UcxKey ucx_key(const void *data, size_t len); - -/** - * Computes a murmur hash-2. - * - * @param data the data to hash - * @param len the length of the data - * @return the murmur hash-2 of the data - */ -int ucx_hash(const char *data, size_t len); - -/** - * Creates an iterator for a map. - * - * Note: A UcxMapIterator iterates over all elements in all element - * lists successively. Therefore the order highly depends on the key hashes and - * may vary under different map sizes. So generally you may NOT rely on - * the iteration order. - * - * Note: The iterator is NOT initialized. You need to call - * ucx_map_iter_next() at least once before accessing any information. However, - * it is not recommended to access the fields of a UcxMapIterator directly. - * - * @param map the map to create the iterator for - * @return an iterator initialized on the first element of the - * first element list - * @see ucx_map_iter_next() - */ -UcxMapIterator ucx_map_iterator(UcxMap const *map); - -/** - * Proceeds to the next element of the map (if any). - * - * Subsequent calls on the same iterator proceed to the next element and - * store the key/value-pair into the memory specified as arguments of this - * function. - * - * If no further elements are found, this function returns zero and leaves the - * last found key/value-pair in memory. - * - * @param iterator the iterator to use - * @param key a pointer to the memory where to store the key - * @param value a pointer to the memory where to store the value - * @return 1, if another element was found, 0 if all elements has been processed - * @see ucx_map_iterator() - */ -int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value); - -/** - * Returns the union of two maps. - * - * The union is a fresh map which is filled by two successive calls of - * ucx_map_copy() on the two input maps. - * - * @param first the first source map - * @param second the second source map - * @param cpfnc a function to copy the elements - * @param cpdata additional data for the copy function - * @return a new map containing the union - */ -UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second, - copy_func cpfnc, void* cpdata); - -/** - * Returns the union of two maps. - * - * The union is a fresh map which is filled by two successive calls of - * ucx_map_copy() on the two input maps. - * - * @param allocator the allocator that shall be used by the new map - * @param first the first source map - * @param second the second source map - * @param cpfnc a function to copy the elements - * @param cpdata additional data for the copy function - * @return a new map containing the union - */ -UcxMap* ucx_map_union_a(UcxAllocator *allocator, - const UcxMap *first, const UcxMap *second, - copy_func cpfnc, void* cpdata); - -/** - * Returns the intersection of two maps. - * - * The intersection is defined as a copy of the first map with every element - * removed that has no valid key in the second map. - * - * @param first the first source map - * @param second the second source map - * @param cpfnc a function to copy the elements - * @param cpdata additional data for the copy function - * @return a new map containing the intersection - */ -UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second, - copy_func cpfnc, void* cpdata); - -/** - * Returns the intersection of two maps. - * - * The intersection is defined as a copy of the first map with every element - * removed that has no valid key in the second map. - * - * @param allocator the allocator that shall be used by the new map - * @param first the first source map - * @param second the second source map - * @param cpfnc a function to copy the elements - * @param cpdata additional data for the copy function - * @return a new map containing the intersection - */ -UcxMap* ucx_map_intersection_a(UcxAllocator *allocator, - const UcxMap *first, const UcxMap *second, - copy_func cpfnc, void* cpdata); - -/** - * Returns the difference of two maps. - * - * The difference contains a copy of all elements of the first map - * for which the corresponding keys cannot be found in the second map. - * - * @param first the first source map - * @param second the second source map - * @param cpfnc a function to copy the elements - * @param cpdata additional data for the copy function - * @return a new list containing the difference - */ -UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second, - copy_func cpfnc, void* cpdata); - -/** - * Returns the difference of two maps. - * - * The difference contains a copy of all elements of the first map - * for which the corresponding keys cannot be found in the second map. - * - * @param allocator the allocator that shall be used by the new map - * @param first the first source map - * @param second the second source map - * @param cpfnc a function to copy the elements - * @param cpdata additional data for the copy function - * @return a new list containing the difference - */ -UcxMap* ucx_map_difference_a(UcxAllocator *allocator, - const UcxMap *first, const UcxMap *second, - copy_func cpfnc, void* cpdata); - - -#ifdef __cplusplus -} -#endif - -#endif /* UCX_MAP_H */ -