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