more header file refactoring
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Fri, 5 Dec 2008 03:07:10 +0000 (03:07 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Fri, 5 Dec 2008 03:07:10 +0000 (03:07 +0000)
15 files changed:
include/hashtable.h
include/list.h
include/map.h
include/skiplist.h
include/txn.h
map/hashtable.c
map/list.c
map/map.c
map/mlocal.h [deleted file]
map/skiplist.c
test/map_test1.c
test/map_test2.c
test/txn_test.c
todo
txn/txn.c

index 9cffb7f9362e9dff409531516fa72818adf811fd..9a32abc94746fc2bb966013572f7b209c688af4f 100644 (file)
@@ -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
index 7eeda46aff1e65ffa30accecd26713b9644f40cd..fed7fcda72962865db5db16afcb6943307e55f38 100644 (file)
@@ -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
index 357b66895f3b16ace6ae137226ab2599818e938a..4d8b78f39ab22147ee12b7db5fd0f28eaa727ef6 100644 (file)
@@ -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
index 11824f8f747cbb6c3e0e68cb8569c9a1539f5990..ca6b5143d224db0cd37957b5c80859b56cfbf59a 100644 (file)
@@ -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
index 635a3692d20fdb8c58bffbcf9715c27918167f7a..fc6b6912e0eb464abeacedb4c1b269981a7f9975 100644 (file)
@@ -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);
index 3471af4db05410e5e6775f9e0d328be96587ecd6..17339415cc44cd0030ddba4f804a12a7d101494d 100644 (file)
@@ -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);
 
index e900f0203229c8d52618b6d2fa1c499b096d0c53..ac6b6a570feebffd751b5795e588b3903269747b 100644 (file)
@@ -10,7 +10,6 @@
 #include <string.h>
 
 #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;
index 6602a9be05fe7e1983307367453cd7b28dc598e7..0db50bdbcd3185ee275089f2ea6aef97b301fa4d 100644 (file)
--- 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 (file)
index c422ec1..0000000
+++ /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
index a0e9c60769a2ce5847471fbbaf9fc6894c8828db..52d7f1a622a40242029e0e15cf273b3b875970a4 100644 (file)
@@ -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)
index 27226d6bb2a52dbe0396869f255ca36ba22e885b..6639359c69340c497b97bc5d3c56e15ca9ad08ca 100644 (file)
@@ -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);
index 897fe8e295d6619539be6335dbb77da09ecff03b..51b17b3f10cbf7f75eabdb8cbc7ea1260198f216 100644 (file)
@@ -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];
 
index a8684da41b5140ccb25f0b362631a7f11f82c27a..a898e9f69e9ad286bdb0949d8511336ab5142922 100644 (file)
@@ -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 b198f920596e2ecae48341924ad86d82fccaebcd..75f997c80febca3be18b2056d1db31eda83fb289 100644 (file)
--- 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)
index e05d332386fe8284727fc0ced57c107d26a59cf2..a6366b34a1d3f12b1596a98d0591db5883385917 100644 (file)
--- 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 <key>. Validation fails for a key we have written to if there is a