# HG changeset patch # User Mike Becker # Date 1329783197 -3600 # Node ID bce0d7f2912ba9abfef49dd8f441dd74f2c4cb1d # Parent 1666cbeb1db8f51befa1984379a5767ddebdf26e fixed map with the help of new tests diff -r 1666cbeb1db8 -r bce0d7f2912b test/main.c --- a/test/main.c Mon Feb 20 15:30:45 2012 +0100 +++ b/test/main.c Tue Feb 21 01:13:17 2012 +0100 @@ -106,10 +106,11 @@ ucx_test_register(suite, test_ucx_mempool_reg_destr); ucx_test_register(suite, test_ucx_mempool_realloc); - printf("\nUcxMap Tests\n"); - if(map_tests()) { - fprintf(stderr, "map_tests failed\n"); - } + /* UcxMap Tests */ + ucx_test_register(suite, test_ucx_map_new); + ucx_test_register(suite, test_ucx_key); + ucx_test_register(suite, test_ucx_map_put); + ucx_test_register(suite, test_ucx_map_get); ucx_test_run(suite, stdout); ucx_test_suite_free(suite); diff -r 1666cbeb1db8 -r bce0d7f2912b test/map_tests.c --- a/test/map_tests.c Mon Feb 20 15:30:45 2012 +0100 +++ b/test/map_tests.c Tue Feb 21 01:13:17 2012 +0100 @@ -2,43 +2,72 @@ * */ -#include -#include -#include - #include "map_tests.h" -int map_tests() { - printf(" Test ucx_map_new\n"); +UCX_TEST_BEGIN(test_ucx_map_new) { UcxMap *map = ucx_map_new(16); - if(map == NULL) { - return -1; - } + + UCX_TEST_ASSERT(map->size == 16, "wrong size") + UCX_TEST_ASSERT(map->map != NULL, "failed") + + ucx_map_free(map); + + UCX_TEST_END +} - printf(" Test ucx_map_put\n"); - char *txt = "text/plain"; - char *xml = "text/xml"; - ucx_map_cstr_put(map, "txt", txt); - ucx_map_cstr_put(map, "xml", xml); +UCX_TEST_BEGIN(test_ucx_key) { + + UcxKey key = ucx_key("This is a text.", 15); + UCX_TEST_ASSERT(strncmp(key.data, "This is a text.", 15) == 0, "failed") + UCX_TEST_ASSERT(key.len == 15, "failed") + UCX_TEST_ASSERT(key.hash == 1261186027, "hash failed") + + UCX_TEST_END +} + +UCX_TEST_BEGIN(test_ucx_map_put) { + + UcxMap *map = ucx_map_new(4); + + int td[5]; + td[0] = 10; td[1] = 42; td[2] = 70; td[3] = 11200; td[4] = 80000; - printf(" Test ucx_map_get\n"); - if(ucx_map_cstr_get(map, "txt") != txt) { - fprintf(stderr, "ucx_map_get failed\n"); - return -1; - } - char xmlkey[4]; - xmlkey[0] = 'x'; - xmlkey[1] = 'm'; - xmlkey[2] = 'l'; - xmlkey[3] = 0; - if(ucx_map_cstr_get(map, xmlkey) != xml) { - fprintf(stderr, "ucx_map_get failed\n"); - return -1; - } - if(ucx_map_cstr_get(map, "nokey") != NULL) { - fprintf(stderr, "ucx_map_get failed\n"); - return -1; - } + ucx_map_cstr_put(map, "Key2", &td[2]); /* 0 */ + ucx_map_cstr_put(map, "Key0", &td[0]); /* 0 */ + ucx_map_cstr_put(map, "Key1", &td[1]); /* 3 */ + ucx_map_cstr_put(map, "KeY3", &td[3]); /* 2 */ + ucx_map_cstr_put(map, "KEY4", &td[4]); /* 0 */ + + UCX_TEST_ASSERT(*((int*)map->map[0]->data) == td[0], "failed Key0") + UCX_TEST_ASSERT(map->map[0]->next != NULL, "no list at slot 0") + UCX_TEST_ASSERT(*((int*)map->map[0]->next->data) == td[2], "failed Key2") + UCX_TEST_ASSERT(map->map[0]->next->next != NULL, "list corrupt at slot 0") + UCX_TEST_ASSERT(*((int*)map->map[0]->next->next->data) == td[4], + "failed Key4") + UCX_TEST_ASSERT(map->map[0]->next->next->next == NULL, + "slot 0 not terminated") + + UCX_TEST_ASSERT(map->map[1] == NULL, "slot 1 not terminated") + + UCX_TEST_ASSERT(*((int*)map->map[2]->data) == td[3], "failed KeY3") + UCX_TEST_ASSERT(map->map[2]->next == NULL, "slot 2 not terminated") - return 0; + UCX_TEST_ASSERT(*((int*)map->map[3]->data) == td[1], "failed Key1") + + ucx_map_cstr_put(map, "Key0", &td[3]); /* 0 */ + + UCX_TEST_ASSERT(*((int*)map->map[0]->data) == td[3], "overwrite failed") + UCX_TEST_ASSERT(*((int*)map->map[0]->next->data) == td[2], + "overwrite failed") + UCX_TEST_ASSERT(*((int*)map->map[0]->next->next->data) == td[4], + "overwrite failed") + UCX_TEST_ASSERT(map->map[0]->next->next->next == NULL, "overwrite failed") + + ucx_map_free(map); + + UCX_TEST_END } + +UCX_TEST_BEGIN(test_ucx_map_get) { + UCX_TEST_END +} diff -r 1666cbeb1db8 -r bce0d7f2912b test/map_tests.h --- a/test/map_tests.h Mon Feb 20 15:30:45 2012 +0100 +++ b/test/map_tests.h Tue Feb 21 01:13:17 2012 +0100 @@ -5,13 +5,17 @@ #ifndef MAP_TESTS_H #define MAP_TESTS_H +#include "ucx/test.h" #include "ucx/map.h" #ifdef __cplusplus extern "C" { #endif -int map_tests(); +UCX_TEST_DECLARE(test_ucx_map_new) +UCX_TEST_DECLARE(test_ucx_key) +UCX_TEST_DECLARE(test_ucx_map_put) +UCX_TEST_DECLARE(test_ucx_map_get) #ifdef __cplusplus diff -r 1666cbeb1db8 -r bce0d7f2912b ucx/map.c --- a/ucx/map.c Mon Feb 20 15:30:45 2012 +0100 +++ b/ucx/map.c Tue Feb 21 01:13:17 2012 +0100 @@ -13,7 +13,7 @@ return NULL; } - map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement)); + map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*)); if(map->map == NULL) { free(map); return NULL; @@ -23,27 +23,54 @@ return map; } +void ucx_map_free(UcxMap *map) { + for (size_t n = 0 ; n < map->size ; n++) { + UcxMapElement *elem = map->map[n]; + if (elem != NULL) { + do { + UcxMapElement *next = elem->next; + free(elem); + elem = next; + } while (elem != NULL); + } + } + free(map); +} + int ucx_map_put(UcxMap *map, UcxKey key, void *data) { if(key.hash == 0) { key.hash = ucx_hash((char*)key.data, key.len); } void *kd = malloc(key.len); + if (kd == NULL) { + return -1; + } memcpy(kd, key.data, key.len); key.data = kd; - UcxMapElement *elm = &map->map[key.hash%map->size]; - if(elm->next != NULL) { - while(elm->next != NULL) { - elm = elm->next; - } + size_t slot = key.hash%map->size; + UcxMapElement *elm = map->map[slot]; + UcxMapElement *prev = NULL; + + while (elm != NULL && elm->key.hash < key.hash) { + prev = elm; + elm = elm->next; + } + + if (elm == NULL || elm->key.hash != key.hash) { UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement)); if(e == NULL) { return -1; } - elm->next = e; + if (prev == NULL) { + map->map[slot] = e; + } else { + prev->next = e; + } + e->next = elm; elm = e; } - + elm->key = key; elm->data = data; @@ -55,11 +82,11 @@ key.hash = ucx_hash((char*)key.data, key.len); } - UcxMapElement *elm = &map->map[key.hash%map->size]; - while(elm != NULL) { + UcxMapElement *elm = map->map[key.hash%map->size]; + while (elm != NULL && elm->key.hash <= key.hash) { if(elm->key.hash == key.hash) { int n = (key.len > elm->key.len) ? elm->key.len : key.len; - if(memcmp(elm->key.data, key.data, n) == 0) { + if (memcmp(elm->key.data, key.data, n) == 0) { return elm->data; } } diff -r 1666cbeb1db8 -r bce0d7f2912b ucx/map.h --- a/ucx/map.h Mon Feb 20 15:30:45 2012 +0100 +++ b/ucx/map.h Tue Feb 21 01:13:17 2012 +0100 @@ -17,7 +17,7 @@ typedef struct UcxMapElement UcxMapElement; struct UcxMap { - UcxMapElement *map; + UcxMapElement **map; size_t size; }; @@ -35,14 +35,15 @@ UcxMap *ucx_map_new(size_t size); +void ucx_map_free(UcxMap *map); int ucx_map_put(UcxMap *map, UcxKey key, void *data); void* ucx_map_get(UcxMap *map, UcxKey key); -#define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, s.length), d) -#define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, strlen(s)), d) -#define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, s.length)) -#define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, strlen(s))) +#define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, 1+s.length), d) +#define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, 1+strlen(s)), d) +#define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, 1+s.length)) +#define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, 1+strlen(s))) UcxKey ucx_key(void *data, size_t len);