map.h - UNIXwork Code

/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2016 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 <stdio.h> #ifdef __cplusplus extern "C" { #endif /** * Loop statement for UCX maps. * * The <code>key</code> variable is implicitly defined, but the * <code>value</code> 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 for a key of a UcxMap. */ struct UcxKey { /** 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. */ UcxKey key; }; /** Structure for an iterator over a UcxMap. */ struct UcxMapIterator { /** The map to iterate over. */ UcxMap *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 (e.g. stdlib free()). * * 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 pointer to the 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 <code>NULL</code> 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 *restrict from, UcxMap *restrict 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 <code>NULL</code> 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 *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 *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((void*)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((void*)&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((void*)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((void*)&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((void*)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((void*)&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(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 *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); #ifdef __cplusplus } #endif #endif /* UCX_MAP_H */

UNIXworkcode

UNIXwork`code`