Mercurial > hg > ucx / changeset

--- 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);

--- 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 <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
 #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
+}

--- 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

--- 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;
             }
         }

--- 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);