# HG changeset patch # User Mike Becker # Date 1376311191 -7200 # Node ID 7800811078b86710d6202e1fd48bf963dca01f9b # Parent b798f2eed26ac3f8196d03c61a7e435b4986d6fa documented map.h + changed return value of ucx_map_iter_next() diff -r b798f2eed26a -r 7800811078b8 ucx/logging.c --- a/ucx/logging.c Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/logging.c Mon Aug 12 14:39:51 2013 +0200 @@ -64,7 +64,7 @@ void ucx_logger_logf(UcxLogger *logger, unsigned int level, const char* file, const unsigned int line, const char *format, ...) { if (level <= logger->level) { - const size_t max = 4096; // estimated maximum message length + const size_t max = 4096; // estimated max. message length (documented) char msg[max]; char *text; size_t k = 0; diff -r b798f2eed26a -r 7800811078b8 ucx/logging.h --- a/ucx/logging.h Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/logging.h Mon Aug 12 14:39:51 2013 +0200 @@ -148,6 +148,9 @@ * * [LEVEL] [TIMESTAMP] [SOURCEFILE]:[LINENO] message * + * Attention: the message (including automatically generated information) + * MUST NOT exceed the size of 4 KB. + * * @param logger the logger to use * @param level the level to log on * @param file information about the source file diff -r b798f2eed26a -r 7800811078b8 ucx/map.c --- a/ucx/map.c Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/map.c Mon Aug 12 14:39:51 2013 +0200 @@ -89,8 +89,7 @@ UcxMapIterator i = ucx_map_iterator(from); void *value; UCX_MAP_FOREACH(key, value, i) { - int ret = ucx_map_put(to, i.cur->key, fnc ? fnc(value, data) : value); - if(ret != 0) { + if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { return 1; } } @@ -100,7 +99,7 @@ UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { size_t bs = (map->count * 5) >> 1; UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); - if(newmap == NULL) { + if (!newmap) { return NULL; } ucx_map_copy(map, newmap, fnc, data); @@ -121,7 +120,7 @@ map->allocator->pool, map->size, sizeof(UcxMapElement*)); - if(map->map == NULL) { + if (!map->map) { *map = oldmap; return 1; } @@ -137,7 +136,7 @@ int ucx_map_put(UcxMap *map, UcxKey key, void *data) { UcxAllocator *allocator = map->allocator; - if(key.hash == 0) { + if (key.hash == 0) { key.hash = ucx_hash((char*)key.data, key.len); } @@ -145,16 +144,16 @@ UcxMapElement *restrict elm = map->map[slot]; UcxMapElement *restrict prev = NULL; - while (elm != NULL && elm->key.hash < key.hash) { + while (elm && elm->key.hash < key.hash) { prev = elm; elm = elm->next; } - if (elm == NULL || elm->key.hash != key.hash) { + if (!elm || elm->key.hash != key.hash) { UcxMapElement *e = (UcxMapElement*)allocator->malloc( allocator->pool, sizeof(UcxMapElement)); - if(e == NULL) { + if (!e) { return -1; } e->key.data = NULL; @@ -167,9 +166,9 @@ elm = e; } - if(elm->key.data == NULL) { + if (!elm->key.data) { void *kd = allocator->malloc(allocator->pool, key.len); - if (kd == NULL) { + if (!kd) { return -1; } memcpy(kd, key.data, key.len); @@ -285,31 +284,31 @@ int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) { UcxMapElement *e = i->cur; - if(e == NULL) { + if (e) { + e = e->next; + } else { e = i->map->map[0]; - } else { - e = e->next; } - while(i->index < i->map->size) { - if(e != NULL) { - if(e->data != NULL) { + while (i->index < i->map->size) { + if (e) { + if (e->data) { i->cur = e; *elm = e->data; *key = e->key; - return 0; + return 1; } e = e->next; } else { i->index++; - if(i->index < i->map->size) { + if (i->index < i->map->size) { e = i->map->map[i->index]; } } } - return 1; + return 0; } diff -r b798f2eed26a -r 7800811078b8 ucx/map.h --- a/ucx/map.h Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/map.h Mon Aug 12 14:39:51 2013 +0200 @@ -50,36 +50,74 @@ 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 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 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. + * 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; }; @@ -108,14 +146,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. + * + * 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 *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 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 *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,6 +230,7 @@ * @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) \ @@ -132,6 +240,7 @@ * @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) \ @@ -141,6 +250,7 @@ * @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) \ @@ -151,12 +261,16 @@ * 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) \ @@ -165,6 +279,7 @@ * 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) \ @@ -173,6 +288,7 @@ * 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) \ @@ -181,6 +297,7 @@ * 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) \ @@ -189,18 +306,69 @@ * 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. + * + * Note: 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 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 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 diff -r b798f2eed26a -r 7800811078b8 ucx/mempool.c --- a/ucx/mempool.c Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/mempool.c Mon Aug 12 14:39:51 2013 +0200 @@ -36,13 +36,23 @@ #include "mempool.h" +/** Capsule for destructible memory chunks. */ typedef struct { + /** The destructor for the memory chunk. */ ucx_destructor destructor; + /** + * First byte of the memory chunk. + * Note, that the address &c is also the address + * of the whole memory chunk. + */ char c; } ucx_memchunk; +/** Capsule for data and its destructor. */ typedef struct { + /** The destructor for the data. */ ucx_destructor destructor; + /** A pointer to the data. */ void *ptr; } ucx_regdestr; diff -r b798f2eed26a -r 7800811078b8 ucx/test.c --- a/ucx/test.c Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/test.c Mon Aug 12 14:39:51 2013 +0200 @@ -28,12 +28,6 @@ #include "test.h" - -struct UcxTestList{ - UcxTest test; - UcxTestList *next; -}; - UcxTestSuite* ucx_test_suite_new() { UcxTestSuite* suite = (UcxTestSuite*) malloc(sizeof(UcxTestSuite)); if (suite != NULL) { diff -r b798f2eed26a -r 7800811078b8 ucx/test.h --- a/ucx/test.h Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/test.h Mon Aug 12 14:39:51 2013 +0200 @@ -90,12 +90,20 @@ #define __FUNCTION__ __func__ #endif -/** Type for the internal list of test cases. */ -typedef struct UcxTestList UcxTestList; /** Type for the UcxTestSuite. */ typedef struct UcxTestSuite UcxTestSuite; /** Pointer to a test function. */ typedef void(*UcxTest)(UcxTestSuite*,FILE*); +/** Type for the internal list of test cases. */ +typedef struct UcxTestList UcxTestList; + +/** Structure for the internal list of test cases. */ +struct UcxTestList { + /** Test case. */ + UcxTest test; + /** Pointer to the next list element. */ + UcxTestList *next; +}; /** * A test suite containing multiple test cases. @@ -119,7 +127,7 @@ UcxTestSuite* ucx_test_suite_new(); /** * Destroys a test suite. - * @param the test suite to destroy + * @param suite the test suite to destroy */ void ucx_test_suite_free(UcxTestSuite* suite); diff -r b798f2eed26a -r 7800811078b8 ucx/utils.h --- a/ucx/utils.h Fri Aug 09 15:29:26 2013 +0200 +++ b/ucx/utils.h Mon Aug 12 14:39:51 2013 +0200 @@ -95,7 +95,7 @@ * Compares two real numbers of type float. * @param f1 pointer to float one * @param f2 pointer to float two - * @param if provided: a pointer to precision (default: 1e-6f) + * @param data if provided: a pointer to precision (default: 1e-6f) * @return -1, if *f1 is less than *f2, 0 if both are equal, * 1 if *f1 is greater than *f2 */ @@ -104,9 +104,9 @@ /** * Compares two real numbers of type double. - * @param f1 pointer to double one - * @param f2 pointer to double two -* @param if provided: a pointer to precision (default: 1e-14) + * @param d1 pointer to double one + * @param d2 pointer to double two + * @param data if provided: a pointer to precision (default: 1e-14) * @return -1, if *d1 is less than *d2, 0 if both are equal, * 1 if *d1 is greater than *d2 */