--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/ucx/map.h Mon Feb 04 17:49:50 2019 +0100
@@ -0,0 +1,435 @@
+/*
+ * 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 <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 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 *map;
+
+ /** The current map element. */
+ UcxMapElement *cur;
+
+ /**
+ * The current index of the element list array.
+ * <b>Attention: </b> this is <b>NOT</b> the element index! Do <b>NOT</b>
+ * 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.
+ *
+ * <b>Note:</b> the contents are <b>not</b> 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 (<code>NULL</code>), 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.
+ *
+ * <b>Note:</b> the contents are <b>not</b> 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.
+ *
+ * <b>Note:</b> 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 *from, UcxMap *to, copy_func fnc, void *data);
+
+/**
+ * Clones the map and rehashes if necessary.
+ *
+ * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
+ * This function <i>always</i> 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(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.
+ *
+ * <b>Note:</b> 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 <b>NOT</b> rely on
+ * the iteration order.
+ *
+ * <b>Note:</b> The iterator is <b>NOT</b> 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 */
+