use a vtable approach for generic map interface
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Sun, 30 Nov 2008 03:57:35 +0000 (03:57 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Sun, 30 Nov 2008 03:57:35 +0000 (03:57 +0000)
include/map.h
makefile
map/hashtable.c
map/list.c
map/map.c
map/mlocal.h
map/skiplist.c
test/ht_test.c
todo

index d670c35d17d877191fadd55938e8c87974c00575..44b9d27ea979570be69760a4cc7afb6d368f6a4c 100644 (file)
@@ -2,19 +2,22 @@
 #define MAP_H
 
 typedef struct map map_t;
-typedef enum stat { MAP_STAT_COUNT } map_stat_e;
-typedef enum { MAP_TYPE_HASHTABLE, MAP_TYPE_SKIPLIST, MAP_TYPE_LIST } map_type_e;
 
-map_t *  map_alloc  (map_type_e map_type);
-void     map_free   (map_t *map);
-void     map_print  (map_t *map);
-uint64_t map_stat   (map_t *map, map_stat_e stat_type);
+typedef const struct map_impl *map_type_t;
+
+extern map_type_t MAP_TYPE_HASHTABLE;
+extern map_type_t MAP_TYPE_SKIPLIST;
+extern map_type_t MAP_TYPE_LIST;
 
+map_t *  map_alloc  (map_type_t map_type);
 uint64_t map_get    (map_t *map, const void *key_data, uint32_t key_len);
 uint64_t map_set    (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
 uint64_t map_add    (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
 uint64_t map_cas    (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
 uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
 uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len);
+uint64_t map_count  (map_t *map);
+void     map_print  (map_t *map);
+void     map_free   (map_t *map);
 
 #endif//MAP_H
index 0e22b60a769555141ffd9b556d5fae5a6ff2799e..13364a88a8df4074ee6cb153832069542bcd2021 100644 (file)
--- a/makefile
+++ b/makefile
@@ -11,13 +11,13 @@ TESTS  := output/ll_test output/sl_test output/ht_test output/rcu_test
 EXES   := $(TESTS)
 
 RUNTIME_SRCS  := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c
-MAP_SRCS      := map/map.c map/hashtable.c map/list.c map/skiplist.c map/nstring.c 
+MAP_SRCS      := map/map.c map/nstring.c 
 TEST_SRCS     := $(RUNTIME_SRCS) $(MAP_SRCS)
 rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c
-txn_test_SRCS := $(TEST_SRCS) txn/txn.c 
-ll_test_SRCS  := $(TEST_SRCS) test/ll_test.c 
-sl_test_SRCS  := $(TEST_SRCS) test/sl_test.c
-ht_test_SRCS  := $(TEST_SRCS) test/ht_test.c test/CuTest.c
+txn_test_SRCS := $(TEST_SRCS) txn/txn.c map/hashtable.c 
+ll_test_SRCS  := $(TEST_SRCS) test/ll_test.c map/list.c 
+sl_test_SRCS  := $(TEST_SRCS) test/sl_test.c map/skiplist.c 
+ht_test_SRCS  := $(TEST_SRCS) test/ht_test.c map/hashtable.c test/CuTest.c
 
 tests: $(TESTS)
 
index 69583acf0c11e15b8534262d940d878276d3624b..42ab07e4b9b06adcddef75493fb58728f7e0b9f1 100644 (file)
@@ -41,6 +41,13 @@ struct ht {
     hashtable_i_t *hti;
 };
 
+static const map_impl_t ht_map_impl = { 
+    (map_alloc_t)ht_alloc, (map_cas_t)ht_cas, (map_get_t)ht_get, (map_remove_t)ht_remove, 
+    (map_count_t)ht_count, (map_print_t)ht_print, (map_free_t)ht_free
+};
+
+const map_impl_t *MAP_TYPE_HASHTABLE = &ht_map_impl;
+
 static const uint64_t COPIED_VALUE           = -1;
 static const uint64_t TOMBSTONE              = STRIP_TAG(-1);
 
index a0f52a57d573a7efb7ce74f32987ce22657a0d8e..e726cb15f34c20375aab355ec0967ba4d4439157 100644 (file)
@@ -5,6 +5,7 @@
  * Harris-Michael lock-free list-based set
  * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
  */
+
 #include <stdio.h>
 #include <string.h>
 
@@ -23,6 +24,13 @@ struct ll {
     node_t *head;
 };
 
+static const map_impl_t ll_map_impl = { 
+    (map_alloc_t)ll_alloc, (map_cas_t)ll_cas, (map_get_t)ll_lookup, (map_remove_t)ll_remove, 
+    (map_count_t)ll_count, (map_print_t)ll_print, (map_free_t)ll_free
+};
+
+const map_impl_t *MAP_TYPE_LIST = &ll_map_impl;
+
 static node_t *node_alloc (const void *key_data, uint32_t key_len, uint64_t val) {
     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
     memset(item, 0, sizeof(node_t));
@@ -56,6 +64,22 @@ list_t *ll_alloc (void) {
 }
 
 void ll_free (list_t *ll) {
+    node_t *item = ll->head->next;
+    while (item) {
+        node_t *next = (node_t *)STRIP_TAG(item->next);
+        nbd_free(item);
+        item = next;
+    }
+}
+
+uint64_t ll_count (list_t *ll) {
+    uint64_t count = 0;
+    node_t *item = ll->head->next;
+    while (item) {
+        count++;
+        item = (node_t *)STRIP_TAG(item->next);
+    }
+    return count;
 }
 
 static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
index a8a7068c6e88f3e208dc758b250a624d2f849447..cb761ef3cddfb7b28f2dd80c67157e8bdcfb1033 100644 (file)
--- a/map/map.c
+++ b/map/map.c
 #include "map.h"
 
 struct map {
-    map_type_e type;
-    void *impl;
+    const map_impl_t *impl;
+    void *data;
 };
 
-map_t *map_alloc (map_type_e map_type) {
-    void *impl = NULL;
-    switch (map_type) {
-        case MAP_TYPE_HASHTABLE: impl = ht_alloc(); break;
-        case MAP_TYPE_SKIPLIST:  impl = sl_alloc(); break;
-        case MAP_TYPE_LIST:      impl = ll_alloc(); break;
-    }
-    map_t *map = NULL;
-    if (impl) {
-        map = nbd_malloc(sizeof(map_t));
-        map->type = map_type;
-        map->impl = impl;
-    }
+map_t *map_alloc (map_type_t map_type) { 
+    const map_impl_t *map_impl = map_type;
+    map_t *map = nbd_malloc(sizeof(map_t)); 
+    map->impl  = map_impl;
+    map->data  = map->impl->alloc();
     return map;
 }
 
 void map_free (map_t *map) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: ht_free(map->impl); break;
-        case MAP_TYPE_SKIPLIST:  sl_free(map->impl); break;
-        case MAP_TYPE_LIST:      ll_free(map->impl); break;
-    }
+    map->impl->free_(map->data);
 }
 
 void map_print (map_t *map) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: ht_print(map->impl); break;
-        case MAP_TYPE_SKIPLIST:  sl_print(map->impl); break;
-        case MAP_TYPE_LIST:      ll_print(map->impl); break;
-    }
+    map->impl->print(map->data);
 }
 
-uint64_t map_stat (map_t *map, map_stat_e stat_type) {
-    switch (stat_type) {
-        case MAP_STAT_COUNT: 
-            if (map->type != MAP_TYPE_HASHTABLE)
-                return ERROR_UNSUPPORTED_FEATURE;
-            return ht_count(map->impl);
-    }
-    return ERROR_INVALID_OPTION;
+uint64_t map_count (map_t *map) {
+    return map->impl->count(map->data);
 }
 
 uint64_t map_get (map_t *map, const void *key_data, uint32_t key_len) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: return ht_get(map->impl, key_data, key_len);
-        case MAP_TYPE_SKIPLIST:  return sl_lookup(map->impl, key_data, key_len);
-        case MAP_TYPE_LIST:      return ll_lookup(map->impl, key_data, key_len);
-    }
-    return ERROR_INVALID_ARGUMENT;
+    return map->impl->get(map->data, key_data, key_len);
 }
 
 uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
-        case MAP_TYPE_SKIPLIST:  return sl_cas(map->impl, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
-        case MAP_TYPE_LIST:      return ll_cas(map->impl, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
-    }
-    return ERROR_INVALID_ARGUMENT;
+    return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
 }
 
 uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
-        case MAP_TYPE_SKIPLIST:  return sl_cas(map->impl, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
-        case MAP_TYPE_LIST:      return ll_cas(map->impl, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
-    }
-    return ERROR_INVALID_ARGUMENT;
+    return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
 }
 
 uint64_t map_cas (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, expected_val, new_val);
-        case MAP_TYPE_SKIPLIST:  return sl_cas(map->impl, key_data, key_len, expected_val, new_val);
-        case MAP_TYPE_LIST:      return ll_cas(map->impl, key_data, key_len, expected_val, new_val);
-    }
-    return ERROR_INVALID_ARGUMENT;
+    return map->impl->cas(map->data, key_data, key_len, expected_val, new_val);
 }
 
 uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
-        case MAP_TYPE_SKIPLIST:  return sl_cas(map->impl, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
-        case MAP_TYPE_LIST:      return ll_cas(map->impl, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
-    }
-    return ERROR_INVALID_ARGUMENT;
+    return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
 }
 
 uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len) {
-    switch (map->type) {
-        case MAP_TYPE_HASHTABLE: return ht_remove(map->impl, key_data, key_len);
-        case MAP_TYPE_SKIPLIST:  return sl_remove(map->impl, key_data, key_len);
-        case MAP_TYPE_LIST:      return ll_remove(map->impl, key_data, key_len);
-    }
-    return ERROR_INVALID_ARGUMENT;
+    return map->impl->remove(map->data, key_data, key_len);
 }
index 548a49fdaa05ac918be10397ba1eb132f4babb31..9336ab7ae2e6213385820500c24fd61ca529a339 100644 (file)
@@ -1,12 +1,36 @@
-#ifndef STRUCT_H
-#define STRUCT_H
+#ifndef MLOCAL_H
+#define MLOCAL_H
 
 #define CAS_EXPECT_DOES_NOT_EXIST ( 0)
 #define CAS_EXPECT_EXISTS         (-1)
 #define CAS_EXPECT_WHATEVER       (-2)
 
+typedef void *   (*map_alloc_t)  (void);
+typedef uint64_t (*map_cas_t)    (void *, const void *, uint32_t, uint64_t, uint64_t);
+typedef uint64_t (*map_get_t)    (void *, const void *, uint32_t);
+typedef uint64_t (*map_remove_t) (void *, const void *, uint32_t);
+typedef uint64_t (*map_count_t)  (void *);
+typedef void     (*map_print_t)  (void *);
+typedef void     (*map_free_t)   (void *);
+
+typedef struct map_impl {
+    map_alloc_t  alloc;
+    map_cas_t    cas;
+    map_get_t    get;
+    map_remove_t remove;
+    map_count_t  count;
+    map_print_t  print;
+    map_free_t   free_;
+} map_impl_t;
+
 typedef struct ht hashtable_t;
-hashtable_t *ht_alloc (void);
+typedef struct sl skiplist_t;
+typedef struct ll list_t;
+
+hashtable_t * ht_alloc (void);
+skiplist_t *  sl_alloc (void);
+list_t *      ll_alloc (void);
+
 uint64_t ht_cas    (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);
 uint64_t ht_get    (hashtable_t *ht, const char *key, uint32_t len);
 uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len);
@@ -14,21 +38,18 @@ uint64_t ht_count  (hashtable_t *ht);
 void     ht_print  (hashtable_t *ht);
 void     ht_free   (hashtable_t *ht);
 
-typedef struct ll list_t;
-list_t * ll_alloc  (void);
-uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len);
-uint64_t ll_cas    (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
-uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
-void     ll_print  (list_t *ll);
-void     ll_free   (list_t *ll);
-
-typedef struct sl skiplist_t;
-skiplist_t * sl_alloc (void);
-uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len);
 uint64_t sl_cas    (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
+uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len);
 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len);
+uint64_t sl_count  (skiplist_t *sl);
 void     sl_print  (skiplist_t *sl);
-void     sl_free   (list_t *sl);
+void     sl_free   (skiplist_t *sl);
 
+uint64_t ll_cas    (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
+uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len);
+uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
+uint64_t ll_count  (list_t *ll);
+void     ll_print  (list_t *ll);
+void     ll_free   (list_t *ll);
 
-#endif//STRUCT_H
+#endif//MLOCAL_H
index c0e869c25e584656c33cf452d50bcacd1797b8f6..d18ee3df4a18a954e53631774616e32f9763da3b 100644 (file)
@@ -13,6 +13,7 @@
  * loads being ordered. Be careful, this code won't work correctly on platforms with weaker memory
  * models if you don't add memory barriers in the right places.
  */
+
 #include <stdio.h>
 #include <string.h>
 
@@ -38,6 +39,13 @@ struct sl {
     node_t *head;
 };
 
+static const map_impl_t sl_map_impl = { 
+    (map_alloc_t)sl_alloc, (map_cas_t)sl_cas, (map_get_t)sl_lookup, (map_remove_t)sl_remove, 
+    (map_count_t)sl_count, (map_print_t)sl_print, (map_free_t)sl_free
+};
+
+const map_impl_t *MAP_TYPE_SKIPLIST = &sl_map_impl;
+
 static int random_level (void) {
     unsigned r = nbd_rand();
     if (r & 1)
@@ -85,7 +93,23 @@ skiplist_t *sl_alloc (void) {
     return sl;
 }
 
-void ll_free (list_t *ll) {
+void sl_free (skiplist_t *sl) {
+    node_t *item = sl->head->next[0];
+    while (item) {
+        node_t *next = (node_t *)STRIP_TAG(item->next[0]);
+        nbd_free(item);
+        item = next;
+    }
+}
+
+uint64_t sl_count (skiplist_t *sl) {
+    uint64_t count = 0;
+    node_t *item = sl->head->next[0];
+    while (item) {
+        count++;
+        item = (node_t *)STRIP_TAG(item->next[0]);
+    }
+    return count;
 }
 
 static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
index f90caeda9120a38112909390818107719dce9c38..e6ec9ff46727993a3a983d01b18678621663fc74 100644 (file)
@@ -25,51 +25,52 @@ void basic_test (CuTest* tc) {
 
     map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
 
-    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10)         );
-    ASSERT_EQUAL( 1,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"b",2,20)         );
-    ASSERT_EQUAL( 2,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( 20,             map_get(ht,"b",2)            );
-    ASSERT_EQUAL( 10,             map_set(ht,"a",2,11)         );
-    ASSERT_EQUAL( 20,             map_set(ht,"b",2,21)         );
-    ASSERT_EQUAL( 2,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( 21,             map_add(ht,"b",2,22)         );
-    ASSERT_EQUAL( 11,             map_remove(ht,"a",2)         );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"a",2)            );
-    ASSERT_EQUAL( 1,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"a",2)         );
-    ASSERT_EQUAL( 21,             map_remove(ht,"b",2)         );
-    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"b",2)         );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"c",2)         );
-    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( 0,              map_count(ht)            );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10)     );
+    ASSERT_EQUAL( 1,              map_count(ht)            );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"b",2,20)     );
+    ASSERT_EQUAL( 2,              map_count(ht)            );
+    ASSERT_EQUAL( 20,             map_get(ht,"b",2)        );
+    ASSERT_EQUAL( 10,             map_set(ht,"a",2,11)     );
+    ASSERT_EQUAL( 20,             map_set(ht,"b",2,21)     );
+    ASSERT_EQUAL( 2,              map_count(ht)            );
+    ASSERT_EQUAL( 21,             map_add(ht,"b",2,22)     );
+    ASSERT_EQUAL( 11,             map_remove(ht,"a",2)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"a",2)        );
+    ASSERT_EQUAL( 1,              map_count(ht)            );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"a",2)     );
+    ASSERT_EQUAL( 21,             map_remove(ht,"b",2)     );
+    ASSERT_EQUAL( 0,              map_count(ht)            );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"b",2)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"c",2)     );
+    ASSERT_EQUAL( 0,              map_count(ht)            );
     
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"d",2,40)         );
-    ASSERT_EQUAL( 40,             map_get(ht,"d",2)            );
-    ASSERT_EQUAL( 1,              map_stat(ht, MAP_STAT_COUNT) );
-    ASSERT_EQUAL( 40,             map_remove(ht,"d",2)         );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)            );
-    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
-
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"d",2,10)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)            );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"d",2,40)         );
-    ASSERT_EQUAL( 40,             map_replace(ht,"d",2,41)     );
-    ASSERT_EQUAL( 41,             map_get(ht,"d",2)            );
-    ASSERT_EQUAL( 41,             map_remove(ht,"d",2)         );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)            );
-    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
-
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"b",2,20)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2)            );
-    // In the end, all members should be removed
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"b",2,20)         );
-    ASSERT_EQUAL( 20,             map_replace(ht,"b",2,21)     );
-    ASSERT_EQUAL( 21,             map_get(ht,"b",2)            );
-    ASSERT_EQUAL( 21,             map_remove(ht,"b",2)         );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2)            );
-    ASSERT_EQUAL( 0,              map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"d",2,40)     );
+    ASSERT_EQUAL( 40,             map_get(ht,"d",2)        );
+    ASSERT_EQUAL( 1,              map_count(ht)            );
+    ASSERT_EQUAL( 40,             map_remove(ht,"d",2)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)        );
+    ASSERT_EQUAL( 0,              map_count(ht)            );
+
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"d",2,10) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"d",2,40)     );
+    ASSERT_EQUAL( 40,             map_replace(ht,"d",2,41) );
+    ASSERT_EQUAL( 41,             map_get(ht,"d",2)        );
+    ASSERT_EQUAL( 41,             map_remove(ht,"d",2)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2)        );
+    ASSERT_EQUAL( 0,              map_count(ht)            );
+
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"b",2,20) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2)        );
+
+    // In the end, all entries should be removed
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"b",2,20)     );
+    ASSERT_EQUAL( 20,             map_replace(ht,"b",2,21) );
+    ASSERT_EQUAL( 21,             map_get(ht,"b",2)        );
+    ASSERT_EQUAL( 21,             map_remove(ht,"b",2)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2)        );
+    ASSERT_EQUAL( 0,              map_count(ht)            );
 
     map_free(ht);
 
@@ -128,7 +129,7 @@ void simple_add_remove (CuTest* tc) {
     }
 
     // In the end, all members should be removed
-    ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+    ASSERT_EQUAL( 0, map_count(ht) );
 
     // In a quiecent state; it is safe to free.
     map_free(ht);
diff --git a/todo b/todo
index 956736ae4a078732fba04ae085fd63787c218cb4..372b4f7623b3141cb86dd286e95632239bc522f9 100644 (file)
--- a/todo
+++ b/todo
@@ -7,4 +7,4 @@
 - make interfaces for all data structures consistent 
 + make list and skiplist use string keys
 + optimize integer keys
-- sl_free() ll_free() ht_print()
+- ht_print()