Mercurial > hg > ucx / changeset

     1.1 --- a/test/main.c	Fri Oct 05 16:59:14 2012 +0200
     1.2 +++ b/test/main.c	Mon Oct 08 12:29:27 2012 +0200
     1.3 @@ -145,6 +145,7 @@
     1.4          ucx_test_register(suite, test_ucx_key);
     1.5          ucx_test_register(suite, test_ucx_map_put);
     1.6          ucx_test_register(suite, test_ucx_map_get);
     1.7 +        ucx_test_register(suite, test_ucx_map_remove);
     1.8          ucx_test_register(suite, test_ucx_map_iterator);
     1.9          ucx_test_register(suite, test_ucx_map_iterator_chain);
    1.10          ucx_test_register(suite, test_ucx_map_store_load);

     2.1 --- a/test/map_tests.c	Fri Oct 05 16:59:14 2012 +0200
     2.2 +++ b/test/map_tests.c	Mon Oct 08 12:29:27 2012 +0200
     2.3 @@ -95,6 +95,47 @@
     2.4      UCX_TEST_ASSERT(td[3] == 11200, "failed key 3");
     2.5      UCX_TEST_ASSERT(td[4] == 80000, "failed key 4");
     2.6  
     2.7 +    UCX_TEST_ASSERT(map->count == 5, "expected 5 remaining values");
     2.8 +    UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key0") != NULL, "element removed");
     2.9 +
    2.10 +    UCX_TEST_END
    2.11 +    ucx_map_free(map);
    2.12 +}
    2.13 +
    2.14 +UCX_TEST_IMPLEMENT(test_ucx_map_remove) {
    2.15 +    UcxMap *map = ucx_map_new(4);
    2.16 +
    2.17 +    int td[5];
    2.18 +    td[0] = 10; td[1] = 42; td[2] = 70; td[3] = 11200; td[4] = 80000;
    2.19 +
    2.20 +    ucx_map_cstr_put(map, "Key2", &td[2]); /* 0 */
    2.21 +    ucx_map_cstr_put(map, "Key0", &td[0]); /* 0 */
    2.22 +    ucx_map_cstr_put(map, "Key1", &td[1]); /* 3 */
    2.23 +    ucx_map_cstr_put(map, "KeY3", &td[3]); /* 2 */
    2.24 +    ucx_map_cstr_put(map, "KEY4", &td[4]); /* 0 */
    2.25 +    UCX_TEST_BEGIN
    2.26 +
    2.27 +    td[0] = *((int*)ucx_map_cstr_remove(map, "Key0"));
    2.28 +    td[1] = *((int*)ucx_map_cstr_get(map, "Key1"));
    2.29 +    td[2] = *((int*)ucx_map_cstr_remove(map, "Key2"));
    2.30 +    td[3] = *((int*)ucx_map_cstr_get(map, "KeY3"));
    2.31 +    td[4] = *((int*)ucx_map_cstr_get(map, "KEY4"));
    2.32 +    UCX_TEST_ASSERT(td[0] == 10, "failed key 0");
    2.33 +    UCX_TEST_ASSERT(td[1] == 42, "failed key 1");
    2.34 +    UCX_TEST_ASSERT(td[2] == 70, "failed key 2");
    2.35 +    UCX_TEST_ASSERT(td[3] == 11200, "failed key 3");
    2.36 +    UCX_TEST_ASSERT(td[4] == 80000, "failed key 4");
    2.37 +
    2.38 +    UCX_TEST_ASSERT(map->count == 3, "expected 3 remaining values");
    2.39 +    UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key0")==NULL, "element not removed");
    2.40 +    UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key1")!=NULL, "element removed");
    2.41 +    UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key2")==NULL, "element not removed");
    2.42 +    UCX_TEST_ASSERT(ucx_map_cstr_get(map, "KeY3")!=NULL, "element removed");
    2.43 +    UCX_TEST_ASSERT(ucx_map_cstr_get(map, "KEY4")!=NULL, "element removed");
    2.44 +
    2.45 +    UCX_TEST_ASSERT(ucx_map_cstr_remove(map, "Key2") == NULL,
    2.46 +            "subsequent remove call shall return NULL");
    2.47 +
    2.48      UCX_TEST_END
    2.49      ucx_map_free(map);
    2.50  }

     3.1 --- a/test/map_tests.h	Fri Oct 05 16:59:14 2012 +0200
     3.2 +++ b/test/map_tests.h	Mon Oct 08 12:29:27 2012 +0200
     3.3 @@ -16,6 +16,7 @@
     3.4  UCX_TEST_DECLARE(test_ucx_key)
     3.5  UCX_TEST_DECLARE(test_ucx_map_put)
     3.6  UCX_TEST_DECLARE(test_ucx_map_get)
     3.7 +UCX_TEST_DECLARE(test_ucx_map_remove)
     3.8  UCX_TEST_DECLARE(test_ucx_map_iterator)
     3.9  UCX_TEST_DECLARE(test_ucx_map_iterator_chain)
    3.10  UCX_TEST_DECLARE(test_ucx_map_store_load)

     4.1 --- a/ucx/map.c	Fri Oct 05 16:59:14 2012 +0200
     4.2 +++ b/ucx/map.c	Mon Oct 08 12:29:27 2012 +0200
     4.3 @@ -106,10 +106,10 @@
     4.4              return -1;
     4.5          }
     4.6          e->key.data = NULL;
     4.7 -        if (prev == NULL) {
     4.8 +        if (prev) {
     4.9 +            prev->next = e;
    4.10 +        } else {
    4.11              map->map[slot] = e;
    4.12 -        } else {
    4.13 -            prev->next = e;
    4.14          }
    4.15          e->next = elm;
    4.16          elm = e;
    4.17 @@ -130,25 +130,47 @@
    4.18      return 0;
    4.19  }
    4.20  
    4.21 -void* ucx_map_get(UcxMap *map, UcxKey key) {
    4.22 +void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {
    4.23      if(key.hash == 0) {
    4.24          key.hash = ucx_hash((char*)key.data, key.len);
    4.25      }
    4.26      
    4.27 -    UcxMapElement *elm = map->map[key.hash%map->size];
    4.28 -    while (elm != NULL && elm->key.hash <= key.hash) {
    4.29 +    size_t slot = key.hash%map->size;
    4.30 +    UcxMapElement *elm = map->map[slot];
    4.31 +    UcxMapElement *pelm = NULL;
    4.32 +    while (elm && elm->key.hash <= key.hash) {
    4.33          if(elm->key.hash == key.hash) {
    4.34              int n = (key.len > elm->key.len) ? elm->key.len : key.len;
    4.35              if (memcmp(elm->key.data, key.data, n) == 0) {
    4.36 -                return elm->data;
    4.37 +                void *data = elm->data;
    4.38 +                if (remove) {
    4.39 +                    if (pelm) {
    4.40 +                        pelm->next = elm->next;
    4.41 +                    } else {
    4.42 +                        map->map[slot] = elm->next;
    4.43 +                    }
    4.44 +                    free(elm);
    4.45 +                    map->count--;
    4.46 +                }
    4.47 +
    4.48 +                return data;
    4.49              }
    4.50          }
    4.51 -        elm = elm->next;
    4.52 +        pelm = elm;
    4.53 +        elm = pelm->next;
    4.54      }
    4.55  
    4.56      return NULL;
    4.57  }
    4.58  
    4.59 +void *ucx_map_get(UcxMap *map, UcxKey key) {
    4.60 +    return ucx_map_get_and_remove(map, key, 0);
    4.61 +}
    4.62 +
    4.63 +void *ucx_map_remove(UcxMap *map, UcxKey key) {
    4.64 +    return ucx_map_get_and_remove(map, key, 1);
    4.65 +}
    4.66 +
    4.67  UcxKey ucx_key(void *data, size_t len) {
    4.68      UcxKey key;
    4.69      key.data = data;

     5.1 --- a/ucx/map.h	Fri Oct 05 16:59:14 2012 +0200
     5.2 +++ b/ucx/map.h	Mon Oct 08 12:29:27 2012 +0200
     5.3 @@ -64,11 +64,14 @@
     5.4  
     5.5  int ucx_map_put(UcxMap *map, UcxKey key, void *data);
     5.6  void* ucx_map_get(UcxMap *map, UcxKey key);
     5.7 +void* ucx_map_remove(UcxMap *map, UcxKey key);
     5.8  
     5.9  #define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, s.length), d)
    5.10  #define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, 1+strlen(s)), d)
    5.11  #define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, s.length))
    5.12  #define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, 1+strlen(s)))
    5.13 +#define ucx_map_sstr_remove(m, s) ucx_map_remove(m, ucx_key(s.ptr, s.length))
    5.14 +#define ucx_map_cstr_remove(m, s) ucx_map_remove(m, ucx_key(s, 1+strlen(s)))
    5.15  
    5.16  UcxKey ucx_key(void *data, size_t len);
    5.17