From: jdybnis Date: Sun, 30 Nov 2008 03:57:35 +0000 (+0000) Subject: use a vtable approach for generic map interface X-Git-Url: https://pd.if.org/git/?p=nbds;a=commitdiff_plain;h=8143ca0acc36e19d004431952e3b6f9b3d337f49;ds=sidebyside use a vtable approach for generic map interface --- diff --git a/include/map.h b/include/map.h index d670c35..44b9d27 100644 --- a/include/map.h +++ b/include/map.h @@ -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 diff --git a/makefile b/makefile index 0e22b60..13364a8 100644 --- 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) diff --git a/map/hashtable.c b/map/hashtable.c index 69583ac..42ab07e 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -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); diff --git a/map/list.c b/map/list.c index a0f52a5..e726cb1 100644 --- a/map/list.c +++ b/map/list.c @@ -5,6 +5,7 @@ * Harris-Michael lock-free list-based set * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf */ + #include #include @@ -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) { diff --git a/map/map.c b/map/map.c index a8a7068..cb761ef 100644 --- a/map/map.c +++ b/map/map.c @@ -11,102 +11,50 @@ #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); } diff --git a/map/mlocal.h b/map/mlocal.h index 548a49f..9336ab7 100644 --- a/map/mlocal.h +++ b/map/mlocal.h @@ -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 diff --git a/map/skiplist.c b/map/skiplist.c index c0e869c..d18ee3d 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -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 #include @@ -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) { diff --git a/test/ht_test.c b/test/ht_test.c index f90caed..e6ec9ff 100644 --- a/test/ht_test.c +++ b/test/ht_test.c @@ -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 956736a..372b4f7 100644 --- 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()