Mercurial > hg > ucx / changeset

     1.1 --- a/test/main.c	Mon Feb 20 15:30:45 2012 +0100
     1.2 +++ b/test/main.c	Tue Feb 21 01:13:17 2012 +0100
     1.3 @@ -106,10 +106,11 @@
     1.4          ucx_test_register(suite, test_ucx_mempool_reg_destr);
     1.5          ucx_test_register(suite, test_ucx_mempool_realloc);
     1.6  
     1.7 -        printf("\nUcxMap Tests\n");
     1.8 -        if(map_tests()) {
     1.9 -            fprintf(stderr, "map_tests failed\n");
    1.10 -        }
    1.11 +        /* UcxMap Tests */
    1.12 +        ucx_test_register(suite, test_ucx_map_new);
    1.13 +        ucx_test_register(suite, test_ucx_key);
    1.14 +        ucx_test_register(suite, test_ucx_map_put);
    1.15 +        ucx_test_register(suite, test_ucx_map_get);
    1.16          
    1.17          ucx_test_run(suite, stdout);
    1.18          ucx_test_suite_free(suite);

     2.1 --- a/test/map_tests.c	Mon Feb 20 15:30:45 2012 +0100
     2.2 +++ b/test/map_tests.c	Tue Feb 21 01:13:17 2012 +0100
     2.3 @@ -2,43 +2,72 @@
     2.4   *
     2.5   */
     2.6  
     2.7 -#include <stdio.h>
     2.8 -#include <stdlib.h>
     2.9 -#include <string.h>
    2.10 -
    2.11  #include "map_tests.h"
    2.12  
    2.13 -int map_tests() {
    2.14 -    printf("   Test ucx_map_new\n");
    2.15 +UCX_TEST_BEGIN(test_ucx_map_new) {
    2.16      UcxMap *map = ucx_map_new(16);
    2.17 -    if(map == NULL) {
    2.18 -        return -1;
    2.19 -    }
    2.20 +    
    2.21 +    UCX_TEST_ASSERT(map->size == 16, "wrong size")
    2.22 +    UCX_TEST_ASSERT(map->map != NULL, "failed")
    2.23 +    
    2.24 +    ucx_map_free(map);
    2.25 +    
    2.26 +    UCX_TEST_END
    2.27 +}
    2.28  
    2.29 -    printf("   Test ucx_map_put\n");
    2.30 -    char *txt = "text/plain";
    2.31 -    char *xml = "text/xml";
    2.32 -    ucx_map_cstr_put(map, "txt", txt);
    2.33 -    ucx_map_cstr_put(map, "xml", xml);
    2.34 +UCX_TEST_BEGIN(test_ucx_key) {
    2.35 +    
    2.36 +    UcxKey key = ucx_key("This is a text.", 15);
    2.37 +    UCX_TEST_ASSERT(strncmp(key.data, "This is a text.", 15) == 0, "failed")
    2.38 +    UCX_TEST_ASSERT(key.len == 15, "failed")
    2.39 +    UCX_TEST_ASSERT(key.hash == 1261186027, "hash failed")
    2.40 +    
    2.41 +    UCX_TEST_END
    2.42 +}
    2.43  
    2.44 -    printf("   Test ucx_map_get\n");
    2.45 -    if(ucx_map_cstr_get(map, "txt") != txt) {
    2.46 -        fprintf(stderr, "ucx_map_get failed\n");
    2.47 -        return -1;
    2.48 -    }
    2.49 -    char xmlkey[4];
    2.50 -    xmlkey[0] = 'x';
    2.51 -    xmlkey[1] = 'm';
    2.52 -    xmlkey[2] = 'l';
    2.53 -    xmlkey[3] = 0;
    2.54 -    if(ucx_map_cstr_get(map, xmlkey) != xml) {
    2.55 -        fprintf(stderr, "ucx_map_get failed\n");
    2.56 -        return -1;
    2.57 -    }
    2.58 -    if(ucx_map_cstr_get(map, "nokey") != NULL) {
    2.59 -        fprintf(stderr, "ucx_map_get failed\n");
    2.60 -        return -1;
    2.61 -    }
    2.62 +UCX_TEST_BEGIN(test_ucx_map_put) {
    2.63 +    
    2.64 +    UcxMap *map = ucx_map_new(4);
    2.65 +    
    2.66 +    int td[5];
    2.67 +    td[0] = 10; td[1] = 42; td[2] = 70; td[3] = 11200; td[4] = 80000;
    2.68  
    2.69 -    return 0;
    2.70 +    ucx_map_cstr_put(map, "Key2", &td[2]); /* 0 */
    2.71 +    ucx_map_cstr_put(map, "Key0", &td[0]); /* 0 */
    2.72 +    ucx_map_cstr_put(map, "Key1", &td[1]); /* 3 */
    2.73 +    ucx_map_cstr_put(map, "KeY3", &td[3]); /* 2 */
    2.74 +    ucx_map_cstr_put(map, "KEY4", &td[4]); /* 0 */
    2.75 +    
    2.76 +    UCX_TEST_ASSERT(*((int*)map->map[0]->data) == td[0], "failed Key0")
    2.77 +    UCX_TEST_ASSERT(map->map[0]->next != NULL, "no list at slot 0")
    2.78 +    UCX_TEST_ASSERT(*((int*)map->map[0]->next->data) == td[2], "failed Key2")
    2.79 +    UCX_TEST_ASSERT(map->map[0]->next->next != NULL, "list corrupt at slot 0")
    2.80 +    UCX_TEST_ASSERT(*((int*)map->map[0]->next->next->data) == td[4],
    2.81 +            "failed Key4")
    2.82 +    UCX_TEST_ASSERT(map->map[0]->next->next->next == NULL,
    2.83 +            "slot 0 not terminated")
    2.84 +
    2.85 +    UCX_TEST_ASSERT(map->map[1] == NULL, "slot 1 not terminated")
    2.86 +
    2.87 +    UCX_TEST_ASSERT(*((int*)map->map[2]->data) == td[3], "failed KeY3")
    2.88 +    UCX_TEST_ASSERT(map->map[2]->next == NULL, "slot 2 not terminated")
    2.89 +
    2.90 +    UCX_TEST_ASSERT(*((int*)map->map[3]->data) == td[1], "failed Key1")
    2.91 +
    2.92 +    ucx_map_cstr_put(map, "Key0", &td[3]); /* 0 */
    2.93 +    
    2.94 +    UCX_TEST_ASSERT(*((int*)map->map[0]->data) == td[3], "overwrite failed")
    2.95 +    UCX_TEST_ASSERT(*((int*)map->map[0]->next->data) == td[2],
    2.96 +            "overwrite failed")
    2.97 +    UCX_TEST_ASSERT(*((int*)map->map[0]->next->next->data) == td[4], 
    2.98 +            "overwrite failed")
    2.99 +    UCX_TEST_ASSERT(map->map[0]->next->next->next == NULL, "overwrite failed")
   2.100 +    
   2.101 +    ucx_map_free(map);
   2.102 +    
   2.103 +    UCX_TEST_END
   2.104  }
   2.105 +
   2.106 +UCX_TEST_BEGIN(test_ucx_map_get) {
   2.107 +    UCX_TEST_END
   2.108 +}

     3.1 --- a/test/map_tests.h	Mon Feb 20 15:30:45 2012 +0100
     3.2 +++ b/test/map_tests.h	Tue Feb 21 01:13:17 2012 +0100
     3.3 @@ -5,13 +5,17 @@
     3.4  #ifndef MAP_TESTS_H
     3.5  #define	MAP_TESTS_H
     3.6  
     3.7 +#include "ucx/test.h"
     3.8  #include "ucx/map.h"
     3.9  
    3.10  #ifdef	__cplusplus
    3.11  extern "C" {
    3.12  #endif
    3.13  
    3.14 -int map_tests();
    3.15 +UCX_TEST_DECLARE(test_ucx_map_new)
    3.16 +UCX_TEST_DECLARE(test_ucx_key)
    3.17 +UCX_TEST_DECLARE(test_ucx_map_put)
    3.18 +UCX_TEST_DECLARE(test_ucx_map_get)
    3.19  
    3.20  
    3.21  #ifdef	__cplusplus

     4.1 --- a/ucx/map.c	Mon Feb 20 15:30:45 2012 +0100
     4.2 +++ b/ucx/map.c	Tue Feb 21 01:13:17 2012 +0100
     4.3 @@ -13,7 +13,7 @@
     4.4          return NULL;
     4.5      }
     4.6  
     4.7 -    map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
     4.8 +    map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*));
     4.9      if(map->map == NULL) {
    4.10          free(map);
    4.11          return NULL;
    4.12 @@ -23,27 +23,54 @@
    4.13      return map;
    4.14  }
    4.15  
    4.16 +void ucx_map_free(UcxMap *map) {
    4.17 +    for (size_t n = 0 ; n < map->size ; n++) {
    4.18 +        UcxMapElement *elem = map->map[n];
    4.19 +        if (elem != NULL) {
    4.20 +            do {
    4.21 +                UcxMapElement *next = elem->next;
    4.22 +                free(elem);
    4.23 +                elem = next;
    4.24 +            } while (elem != NULL);
    4.25 +        }
    4.26 +    }
    4.27 +    free(map);
    4.28 +}
    4.29 +
    4.30  int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
    4.31      if(key.hash == 0) {
    4.32          key.hash = ucx_hash((char*)key.data, key.len);
    4.33      }
    4.34      void *kd = malloc(key.len);
    4.35 +    if (kd == NULL) {
    4.36 +        return -1;
    4.37 +    }
    4.38      memcpy(kd, key.data, key.len);
    4.39      key.data = kd;
    4.40  
    4.41 -    UcxMapElement *elm = &map->map[key.hash%map->size];
    4.42 -    if(elm->next != NULL) {
    4.43 -        while(elm->next != NULL) {
    4.44 -            elm = elm->next;
    4.45 -        }
    4.46 +    size_t slot = key.hash%map->size;
    4.47 +    UcxMapElement *elm = map->map[slot];
    4.48 +    UcxMapElement *prev = NULL;
    4.49 +
    4.50 +    while (elm != NULL && elm->key.hash < key.hash) {
    4.51 +        prev = elm;
    4.52 +        elm = elm->next;
    4.53 +    }
    4.54 +    
    4.55 +    if (elm == NULL || elm->key.hash != key.hash) {
    4.56          UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
    4.57          if(e == NULL) {
    4.58              return -1;
    4.59          }
    4.60 -        elm->next = e;
    4.61 +        if (prev == NULL) {
    4.62 +            map->map[slot] = e;
    4.63 +        } else {
    4.64 +            prev->next = e;
    4.65 +        }
    4.66 +        e->next = elm;
    4.67          elm = e;
    4.68      }
    4.69 -
    4.70 +    
    4.71      elm->key = key;
    4.72      elm->data = data;
    4.73  
    4.74 @@ -55,11 +82,11 @@
    4.75          key.hash = ucx_hash((char*)key.data, key.len);
    4.76      }
    4.77      
    4.78 -    UcxMapElement *elm = &map->map[key.hash%map->size];
    4.79 -    while(elm != NULL) {
    4.80 +    UcxMapElement *elm = map->map[key.hash%map->size];
    4.81 +    while (elm != NULL && elm->key.hash <= key.hash) {
    4.82          if(elm->key.hash == key.hash) {
    4.83              int n = (key.len > elm->key.len) ? elm->key.len : key.len;
    4.84 -            if(memcmp(elm->key.data, key.data, n) == 0) {
    4.85 +            if (memcmp(elm->key.data, key.data, n) == 0) {
    4.86                  return elm->data;
    4.87              }
    4.88          }

     5.1 --- a/ucx/map.h	Mon Feb 20 15:30:45 2012 +0100
     5.2 +++ b/ucx/map.h	Tue Feb 21 01:13:17 2012 +0100
     5.3 @@ -17,7 +17,7 @@
     5.4  typedef struct UcxMapElement UcxMapElement;
     5.5  
     5.6  struct UcxMap {
     5.7 -    UcxMapElement *map;
     5.8 +    UcxMapElement **map;
     5.9      size_t        size;
    5.10  };
    5.11  
    5.12 @@ -35,14 +35,15 @@
    5.13  
    5.14  
    5.15  UcxMap *ucx_map_new(size_t size);
    5.16 +void ucx_map_free(UcxMap *map);
    5.17  
    5.18  int ucx_map_put(UcxMap *map, UcxKey key, void *data);
    5.19  void* ucx_map_get(UcxMap *map, UcxKey key);
    5.20  
    5.21 -#define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, s.length), d)
    5.22 -#define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, strlen(s)), d)
    5.23 -#define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, s.length))
    5.24 -#define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, strlen(s)))
    5.25 +#define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, 1+s.length), d)
    5.26 +#define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, 1+strlen(s)), d)
    5.27 +#define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, 1+s.length))
    5.28 +#define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, 1+strlen(s)))
    5.29  
    5.30  UcxKey ucx_key(void *data, size_t len);
    5.31