From 9d72edf41ce3a2ddbbe2d44afc23ef5ec53339c3 Mon Sep 17 00:00:00 2001 From: jdybnis Date: Fri, 5 Dec 2008 03:07:10 +0000 Subject: [PATCH] more header file refactoring --- include/hashtable.h | 7 ++++++- include/list.h | 8 +++++--- include/map.h | 31 ++++++++++++++++++++++++++----- include/skiplist.h | 8 +++++--- include/txn.h | 2 ++ map/hashtable.c | 8 -------- map/list.c | 8 -------- map/map.c | 6 ++---- map/mlocal.h | 28 ---------------------------- map/skiplist.c | 8 -------- test/map_test1.c | 2 +- test/map_test2.c | 4 ++-- test/txn_test.c | 3 ++- todo | 1 + txn/txn.c | 2 +- 15 files changed, 53 insertions(+), 73 deletions(-) delete mode 100644 map/mlocal.h diff --git a/include/hashtable.h b/include/hashtable.h index 9cffb7f..9a32abc 100644 --- a/include/hashtable.h +++ b/include/hashtable.h @@ -1,7 +1,7 @@ #ifndef HASHTABLE_H #define HASHTABLE_H -#include "datatype.h" +#include "map.h" typedef struct ht hashtable_t; @@ -13,4 +13,9 @@ uint64_t ht_count (hashtable_t *ht); void ht_print (hashtable_t *ht); void ht_free (hashtable_t *ht); +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 +}; + #endif//HASHTABLE_H diff --git a/include/list.h b/include/list.h index 7eeda46..fed7fcd 100644 --- a/include/list.h +++ b/include/list.h @@ -1,13 +1,10 @@ #ifndef LIST_H #define LIST_H -#include "datatype.h" #include "map.h" typedef struct ll list_t; -extern map_type_t MAP_TYPE_LIST; - list_t * ll_alloc (const datatype_t *key_type); uint64_t ll_cas (list_t *ll, void *key, uint64_t expected_val, uint64_t new_val); uint64_t ll_lookup (list_t *ll, void *key); @@ -16,4 +13,9 @@ uint64_t ll_count (list_t *ll); void ll_print (list_t *ll); void ll_free (list_t *ll); +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 +}; + #endif//LIST_H diff --git a/include/map.h b/include/map.h index 357b668..4d8b78f 100644 --- a/include/map.h +++ b/include/map.h @@ -4,12 +4,9 @@ #include "datatype.h" typedef struct map map_t; +typedef struct map_impl map_impl_t; -typedef const struct map_impl *map_type_t; - -extern map_type_t MAP_TYPE_HASHTABLE; - -map_t * map_alloc (map_type_t map_type, const datatype_t *key_type); +map_t * map_alloc (const map_impl_t *map_impl, const datatype_t *key_type); uint64_t map_get (map_t *map, void *key); uint64_t map_set (map_t *map, void *key, uint64_t new_val); uint64_t map_add (map_t *map, void *key, uint64_t new_val); @@ -20,4 +17,28 @@ uint64_t map_count (map_t *map); void map_print (map_t *map); void map_free (map_t *map); +///////////////////////////////////////////////////////////////////////////////////// + +#define CAS_EXPECT_DOES_NOT_EXIST ( 0) +#define CAS_EXPECT_EXISTS (-1) +#define CAS_EXPECT_WHATEVER (-2) + +typedef void * (*map_alloc_t) (const datatype_t *); +typedef uint64_t (*map_cas_t) (void *, void *, uint64_t, uint64_t); +typedef uint64_t (*map_get_t) (void *, void *); +typedef uint64_t (*map_remove_t) (void *, void *); +typedef uint64_t (*map_count_t) (void *); +typedef void (*map_print_t) (void *); +typedef void (*map_free_t) (void *); + +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_; +}; + #endif//MAP_H diff --git a/include/skiplist.h b/include/skiplist.h index 11824f8..ca6b514 100644 --- a/include/skiplist.h +++ b/include/skiplist.h @@ -1,13 +1,10 @@ #ifndef SKIPLIST_H #define SKIPLIST_H -#include "datatype.h" #include "map.h" typedef struct sl skiplist_t; -extern map_type_t MAP_TYPE_SKIPLIST; - skiplist_t *sl_alloc (const datatype_t *key_type); uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expected_val, uint64_t new_val); uint64_t sl_lookup (skiplist_t *sl, void *key); @@ -16,4 +13,9 @@ uint64_t sl_count (skiplist_t *sl); void sl_print (skiplist_t *sl); void sl_free (skiplist_t *sl); +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 +}; + #endif//SKIPLIST_H diff --git a/include/txn.h b/include/txn.h index 635a369..fc6b691 100644 --- a/include/txn.h +++ b/include/txn.h @@ -12,6 +12,8 @@ typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_sta typedef struct txn txn_t; +void txn_init (void); + txn_t * txn_begin (txn_type_e type, map_t *map); void txn_abort (txn_t *txn); txn_state_e txn_commit (txn_t *txn); diff --git a/map/hashtable.c b/map/hashtable.c index 3471af4..1733941 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -16,7 +16,6 @@ #include "common.h" #include "murmur.h" #include "mem.h" -#include "mlocal.h" #include "hashtable.h" #define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t @@ -42,13 +41,6 @@ struct ht { const datatype_t *key_type; }; -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 e900f02..ac6b6a5 100644 --- a/map/list.c +++ b/map/list.c @@ -10,7 +10,6 @@ #include #include "common.h" -#include "mlocal.h" #include "list.h" #include "mem.h" @@ -25,13 +24,6 @@ struct ll { const datatype_t *key_type; }; -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 (void *key, uint64_t val) { node_t *item = (node_t *)nbd_malloc(sizeof(node_t)); item->key = key; diff --git a/map/map.c b/map/map.c index 6602a9b..0db50bd 100644 --- a/map/map.c +++ b/map/map.c @@ -6,17 +6,15 @@ */ #include "common.h" -#include "mlocal.h" -#include "mem.h" #include "map.h" +#include "mem.h" struct map { const map_impl_t *impl; void *data; }; -map_t *map_alloc (map_type_t map_type, const datatype_t *key_type) { - const map_impl_t *map_impl = map_type; +map_t *map_alloc (const map_impl_t *map_impl, const datatype_t *key_type) { map_t *map = nbd_malloc(sizeof(map_t)); map->impl = map_impl; map->data = map->impl->alloc(key_type); diff --git a/map/mlocal.h b/map/mlocal.h deleted file mode 100644 index c422ec1..0000000 --- a/map/mlocal.h +++ /dev/null @@ -1,28 +0,0 @@ -#ifndef MLOCAL_H -#define MLOCAL_H - -#include "datatype.h" - -#define CAS_EXPECT_DOES_NOT_EXIST ( 0) -#define CAS_EXPECT_EXISTS (-1) -#define CAS_EXPECT_WHATEVER (-2) - -typedef void * (*map_alloc_t) (const datatype_t *); -typedef uint64_t (*map_cas_t) (void *, void *, uint64_t, uint64_t); -typedef uint64_t (*map_get_t) (void *, void *); -typedef uint64_t (*map_remove_t) (void *, void *); -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; - -#endif//MLOCAL_H diff --git a/map/skiplist.c b/map/skiplist.c index a0e9c60..52d7f1a 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -22,7 +22,6 @@ #include "common.h" #include "runtime.h" -#include "mlocal.h" #include "skiplist.h" #include "mem.h" @@ -41,13 +40,6 @@ struct sl { const datatype_t *key_type; }; -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) diff --git a/test/map_test1.c b/test/map_test1.c index 27226d6..6639359 100644 --- a/test/map_test1.c +++ b/test/map_test1.c @@ -85,7 +85,7 @@ int main (int argc, char **argv) { } } - map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; + static const map_impl_t *map_types[] = { &ll_map_impl, &sl_map_impl, &ht_map_impl }; for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { #ifdef TEST_STRING_KEYS map_ = map_alloc(map_types[i], &DATATYPE_NSTRING); diff --git a/test/map_test2.c b/test/map_test2.c index 897fe8e..51b17b3 100644 --- a/test/map_test2.c +++ b/test/map_test2.c @@ -28,7 +28,7 @@ typedef struct worker_data { volatile int *wait; } worker_data_t; -static map_type_t map_type_; +static const map_impl_t *map_type_; // Test some basic stuff; add a few keys, remove a few keys void simple (CuTest* tc) { @@ -202,7 +202,7 @@ int main (void) { nbd_init(); lwt_set_trace_level("h3"); - map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; + static const map_impl_t *map_types[] = { &ll_map_impl, &sl_map_impl, &ht_map_impl }; for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { map_type_ = map_types[i]; diff --git a/test/txn_test.c b/test/txn_test.c index a8684da..a898e9f 100644 --- a/test/txn_test.c +++ b/test/txn_test.c @@ -10,7 +10,7 @@ #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) void test1 (CuTest* tc) { - map_t *map = map_alloc(MAP_TYPE_HASHTABLE, NULL); + map_t *map = map_alloc(&ht_map_impl, NULL); txn_t *t1 = txn_begin(TXN_REPEATABLE_READ, map); txn_t *t2 = txn_begin(TXN_REPEATABLE_READ, map); tm_set(t1, "abc", 2); @@ -26,6 +26,7 @@ void test1 (CuTest* tc) { int main (void) { nbd_init(); + txn_init(); CuString *output = CuStringNew(); CuSuite* suite = CuSuiteNew(); diff --git a/todo b/todo index b198f92..75f997c 100644 --- a/todo +++ b/todo @@ -14,3 +14,4 @@ - characterize performance of data structures - experiment with the performance impact of not passing the hash between functions - experiment with embedding keys in the list/skiplist nodes +- allow values of 0 to be inserted into maps (change DOES_NOT_EXIST to something else) diff --git a/txn/txn.c b/txn/txn.c index e05d332..a6366b3 100644 --- a/txn/txn.c +++ b/txn/txn.c @@ -45,7 +45,7 @@ static txn_state_e txn_validate (txn_t *txn); static map_t *active_ = NULL; void txn_init (void) { - active_ = map_alloc(MAP_TYPE_SKIPLIST, NULL); + active_ = map_alloc(&sl_map_impl, NULL); } // Validate the updates for . Validation fails for a key we have written to if there is a -- 2.40.0