--- a/ucx/map.h Fri Aug 16 12:41:30 2013 +0200
+++ b/ucx/map.h Sat Aug 17 12:04:04 2013 +0200
@@ -50,36 +50,81 @@
extern "C" {
#endif
-#define UCX_MAP_FOREACH(key,elm,iter) \
- for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&elm)==0;)
+/**
+ * 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 an 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 an UcxMap. @see UcxKey */
typedef struct UcxKey UcxKey;
+
+/** Type for an element of an UcxMap. @see UcxMapElement */
typedef struct UcxMapElement UcxMapElement;
+
+/** Type for an iterator over an 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 an 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 an 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 an 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;
};
@@ -108,14 +153,83 @@
*/
void ucx_map_free(UcxMap *map);
-/* you cannot clone maps with more than 390 mio entries */
+/**
+ * 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 *restrict from, UcxMap *restrict 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);
-int ucx_map_put(UcxMap *map, UcxKey key, void *data);
+/**
+ * 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);
/**
@@ -123,84 +237,151 @@
* @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 an 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 an 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.
+ *
+ * <b>Note:</b> An 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 an 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);
-int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm);
+/**
+ * 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