all structures are parameterized by the datatype for the key
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Thu, 4 Dec 2008 06:57:19 +0000 (06:57 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Thu, 4 Dec 2008 06:57:19 +0000 (06:57 +0000)
13 files changed:
datatype/nstring.c [moved from runtime/nstring.c with 86% similarity]
include/datatype.h [new file with mode: 0644]
include/map.h
include/nstring.h
makefile
map/hashtable.c
map/list.c
map/map.c
map/mlocal.h
map/skiplist.c
test/map_test1.c
test/map_test2.c
test/txn_test.c

similarity index 86%
rename from runtime/nstring.c
rename to datatype/nstring.c
index a3fdd1fb350c59622db4446c61c857b2d750e165..f4f6f3811474ad058438a9600b5526919c0af26b 100644 (file)
@@ -3,6 +3,8 @@
 #include "murmur.h"
 #include "mem.h"
 
+const datatype_t DATATYPE_NSTRING = { (cmp_fun_t)ns_cmp, (hash_fun_t)ns_hash, (clone_fun_t)ns_dup };
+
 nstring_t *ns_alloc (uint32_t len) {
     nstring_t *ns = nbd_malloc(sizeof(nstring_t) + len);
     ns->len = len;
diff --git a/include/datatype.h b/include/datatype.h
new file mode 100644 (file)
index 0000000..e0085be
--- /dev/null
@@ -0,0 +1,14 @@
+#ifndef DATATYPE_H
+#define DATATYPE_H
+
+typedef int      (*cmp_fun_t)   (void *, void *);
+typedef void *   (*clone_fun_t) (void *);
+typedef uint32_t (*hash_fun_t)  (void *);
+
+typedef struct datatype {
+    cmp_fun_t   cmp;
+    hash_fun_t  hash;
+    clone_fun_t clone;
+} datatype_t;
+
+#endif//DATATYPE_H
index 71d0ddee0b90e9c45547fb3576a1c58cb32736b3..42a5a1d2e8c2ebf1d2d196dc14506259e9aa466c 100644 (file)
@@ -1,19 +1,17 @@
 #ifndef MAP_H
 #define MAP_H
 
+#include "datatype.h"
+
 typedef struct map map_t;
 
 typedef const struct map_impl *map_type_t;
 
-typedef int      (*cmp_fun_t)   (void *, void *);
-typedef void *   (*clone_fun_t) (void *);
-typedef uint32_t (*hash_fun_t)  (void *);
-
 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, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun);
+map_t *  map_alloc  (map_type_t map_type, 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);
index 5d6fc89c390b83ac4ec8804135d775dd49df5621..6114171a51aa7dba234d7e4ece6408d9abdc8b0e 100644 (file)
@@ -1,6 +1,9 @@
 #ifndef NSTRING_H
 #define NSTRING_H
 
+#include "common.h"
+#include "datatype.h"
+
 typedef struct nstring {
     uint32_t len;
     char data[];
@@ -11,4 +14,6 @@ int         ns_cmp   (const nstring_t *ns1, const nstring_t *ns2);
 uint32_t    ns_hash  (const nstring_t *ns);
 nstring_t * ns_dup   (const nstring_t *ns);
 
+extern const datatype_t DATATYPE_NSTRING;
+
 #endif//NSTRING_H 
index 21fa6d9a53013ae17275d8e14f453ba1c084debb..ba6ad3184dc71b240a6ce50c0f5dcc4ae94ea17e 100644 (file)
--- a/makefile
+++ b/makefile
@@ -10,7 +10,7 @@ INCS   := $(addprefix -I, include)
 TESTS  := output/map_test1 output/map_test2 output/rcu_test output/txn_test
 EXES   := $(TESTS)
 
-RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c runtime/nstring.c 
+RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c datatype/nstring.c 
 MAP_SRCS     := map/map.c map/list.c map/skiplist.c map/hashtable.c
 
 rcu_test_SRCS  := $(RUNTIME_SRCS) test/rcu_test.c
index 1039ff014bf19d3deb246fcf98c79a6aef8f81f8..da5adae11b6e42da65c07c7a6e58399660a0b066 100644 (file)
@@ -37,10 +37,8 @@ typedef struct hti {
 } hti_t;
 
 struct ht {
-    hti_t      *hti;
-    cmp_fun_t   cmp_fun;
-    hash_fun_t  hash_fun;
-    clone_fun_t clone_fun;
+    hti_t *hti;
+    const datatype_t *key_type;
 };
 
 static const map_impl_t ht_map_impl = { 
@@ -93,13 +91,13 @@ static volatile entry_t *hti_lookup (hti_t *hti, void *key, uint32_t key_hash, i
             uint64_t ent_key = ent->key;
             if (ent_key == DOES_NOT_EXIST) {
                 TRACE("h1", "hti_lookup: entry %p for key %p is empty", ent, 
-                            (hti->ht->clone_fun == NULL) ? (void *)ent_key : GET_PTR(ent_key));
+                            (hti->ht->key_type == NULL) ? (void *)ent_key : GET_PTR(ent_key));
                 *is_empty = 1; // indicate an empty so the caller avoids an expensive key compare
                 return ent;
             }
 
             // Compare <key> with the key in the entry. 
-            if (EXPECT_TRUE(hti->ht->cmp_fun == NULL)) {
+            if (EXPECT_TRUE(hti->ht->key_type == NULL)) {
                 // fast path for integer keys
                 if (ent_key == (uint64_t)key) {
                     TRACE("h1", "hti_lookup: found entry %p with key %p", ent, ent_key);
@@ -109,7 +107,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, void *key, uint32_t key_hash, i
                 // The key in <ent> is made up of two parts. The 48 low-order bits are a pointer. The
                 // high-order 16 bits are taken from the hash. The bits from the hash are used as a
                 // quick check to rule out non-equal keys without doing a complete compare.
-                if ((key_hash >> 16) == (ent_key >> 48) && hti->ht->cmp_fun(GET_PTR(ent_key), key) == 0) {
+                if ((key_hash >> 16) == (ent_key >> 48) && hti->ht->key_type->cmp(GET_PTR(ent_key), key) == 0) {
                     TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key));
                     return ent;
                 }
@@ -187,7 +185,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
     assert(ht1->next);
     assert(ht2);
     assert(ht1_ent >= ht1->table && ht1_ent < ht1->table + (1 << ht1->scale));
-    assert(key_hash == 0 || ht1->ht->hash_fun == NULL || (key_hash >> 16) == (ht1_ent->key >> 48));
+    assert(key_hash == 0 || ht1->ht->key_type == NULL || (key_hash >> 16) == (ht1_ent->key >> 48));
 
     uint64_t ht1_ent_val = ht1_ent->val;
     if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) {
@@ -219,13 +217,13 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
 
     // Install the key in the new table.
     uint64_t ht1_ent_key = ht1_ent->key;
-    void *key = (ht1->ht->hash_fun == NULL) ? (void *)ht1_ent_key : GET_PTR(ht1_ent_key);
+    void *key = (ht1->ht->key_type == NULL) ? (void *)ht1_ent_key : GET_PTR(ht1_ent_key);
 
     // The old table's dead entries don't need to be copied to the new table, but their keys need to be freed.
     assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE));
     if (ht1_ent_val == TOMBSTONE) {
         TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_ent, key);
-        if (EXPECT_FALSE(ht1->ht->clone_fun != NULL)) {
+        if (EXPECT_FALSE(ht1->ht->key_type != NULL)) {
             nbd_defer_free(key);
         }
         return TRUE; 
@@ -234,7 +232,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h
     // We use 0 to indicate that <key_hash> is uninitiallized. Occasionally the key's hash will really be 0 and we
     // waste time recomputing it every time. It is rare enough (1 in 65k) that it won't hurt performance. 
     if (key_hash == 0) { 
-        key_hash = (ht1->ht->hash_fun == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->hash_fun(key);
+        key_hash = (ht1->ht->key_type == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->key_type->hash(key);
     }
 
     int ht2_ent_is_empty;
@@ -328,8 +326,8 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe
             return DOES_NOT_EXIST;
 
         // Allocate <new_key>.
-        uint64_t new_key = (uint64_t)((hti->ht->clone_fun == NULL) ? key : hti->ht->clone_fun(key));
-        if (EXPECT_FALSE(hti->ht->hash_fun != NULL)) {
+        uint64_t new_key = (uint64_t)((hti->ht->key_type == NULL) ? key : hti->ht->key_type->clone(key));
+        if (EXPECT_FALSE(hti->ht->key_type != NULL)) {
             // Combine <new_key> pointer with bits from its hash 
             new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key; 
         }
@@ -341,8 +339,8 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe
         if (old_ent_key != DOES_NOT_EXIST) {
             TRACE("h0", "hti_cas: lost race to install key %p in entry %p", new_key, ent);
             TRACE("h0", "hti_cas: found %p instead of NULL", 
-                        (hti->ht->clone_fun != NULL) ? (void *)old_ent_key : GET_PTR(old_ent_key), 0);
-            if (hti->ht->clone_fun != NULL) {
+                        (hti->ht->key_type == NULL) ? (void *)old_ent_key : GET_PTR(old_ent_key), 0);
+            if (hti->ht->key_type != NULL) {
                 nbd_free(GET_PTR(new_key));
             }
             return hti_cas(hti, key, key_hash, expected, new); // tail-call
@@ -351,7 +349,7 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe
     }
 
     TRACE("h0", "hti_cas: entry for key %p is %p", 
-                (hti->ht->clone_fun != NULL) ? (void *)ent->key : GET_PTR(ent->key), ent);
+                (hti->ht->key_type == NULL) ? (void *)ent->key : GET_PTR(ent->key), ent);
 
     // If the entry is in the middle of a copy, the copy must be completed first.
     uint64_t ent_val = ent->val;
@@ -437,7 +435,7 @@ static uint64_t hti_get (hti_t *hti, void *key, uint32_t key_hash) {
 
 //
 uint64_t ht_get (hashtable_t *ht, void *key) {
-    uint32_t hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key);
+    uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key);
     return hti_get(ht->hti, key, hash);
 }
 
@@ -498,7 +496,7 @@ uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t new
     }
 
     uint64_t old_val;
-    uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key);
+    uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key);
     while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;
@@ -512,7 +510,7 @@ uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t new
 uint64_t ht_remove (hashtable_t *ht, void *key) {
     hti_t *hti = ht->hti;
     uint64_t val;
-    uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key);
+    uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key);
     do {
         val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, TOMBSTONE);
         if (val != COPIED_VALUE)
@@ -535,11 +533,9 @@ uint64_t ht_count (hashtable_t *ht) {
 }
 
 // Allocate and initialize a new hash table.
-hashtable_t *ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) {
+hashtable_t *ht_alloc (const datatype_t *key_type) {
     hashtable_t *ht = nbd_malloc(sizeof(hashtable_t));
-    ht->cmp_fun = cmp_fun;
-    ht->hash_fun = hash_fun;
-    ht->clone_fun = clone_fun;
+    ht->key_type = key_type;
     ht->hti = (hti_t *)hti_alloc(ht, MIN_SCALE);
     return ht;
 }
@@ -550,7 +546,7 @@ void ht_free (hashtable_t *ht) {
     do {
         for (uint32_t i = 0; i < (1 << hti->scale); ++i) {
             assert(hti->table[i].val == COPIED_VALUE || !IS_TAGGED(hti->table[i].val));
-            if (ht->clone_fun != NULL && hti->table[i].key != DOES_NOT_EXIST) {
+            if (ht->key_type != NULL && hti->table[i].key != DOES_NOT_EXIST) {
                 nbd_free(GET_PTR(hti->table[i].key));
             }
         }
index 979c91e10477de67af9ebeadeea6e539527eb521..f7a9cd43cbaa2da9049be46bc791d11f81e92cda 100644 (file)
@@ -21,8 +21,7 @@ typedef struct node {
 
 struct ll {
     node_t *head;
-    cmp_fun_t cmp_fun;
-    clone_fun_t clone_fun;
+    const datatype_t *key_type;
 };
 
 static const map_impl_t ll_map_impl = { 
@@ -39,10 +38,9 @@ static node_t *node_alloc (void *key, uint64_t val) {
     return item;
 }
 
-list_t *ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) {
+list_t *ll_alloc (const datatype_t *key_type) {
     list_t *ll = (list_t *)nbd_malloc(sizeof(list_t));
-    ll->cmp_fun = cmp_fun;
-    ll->clone_fun = clone_fun;
+    ll->key_type = key_type;
     ll->head = node_alloc(NULL, 0);
     ll->head->next = NULL;
     return ll;
@@ -100,7 +98,7 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *ke
                 TRACE("l3", "find_pred: now current item is %p next is %p", item, next);
 
                 // The thread that completes the unlink should free the memory.
-                if (ll->clone_fun != NULL) {
+                if (ll->key_type != NULL) {
                     nbd_defer_free((void*)other->key);
                 }
                 nbd_defer_free(other);
@@ -123,10 +121,10 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *ke
         TRACE("l4", "find_pred: key %p val %p", item->key, item->val);
 
         int d;
-        if (EXPECT_TRUE(ll->cmp_fun == NULL)) {
+        if (EXPECT_TRUE(ll->key_type == NULL)) {
             d = (uint64_t)item->key - (uint64_t)key;
         } else {
-            d = ll->cmp_fun(item->key, key);
+            d = ll->key_type->cmp(item->key, key);
         }
 
         // If we reached the key (or passed where it should be), we found the right predesssor
@@ -195,7 +193,7 @@ uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val)
 
             // Create a new item and insert it into the list.
             TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
-            void *new_key  = (ll->clone_fun == NULL) ? key : ll->clone_fun(key);
+            void *new_key  = (ll->key_type == NULL) ? key : ll->key_type->clone(key);
             node_t *new_item = node_alloc(new_key, new_val);
             node_t *next = new_item->next = old_item;
             node_t *other = SYNC_CAS(&pred->next, next, new_item);
@@ -206,7 +204,7 @@ uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val)
 
             // Lost a race. Failed to insert the new item into the list.
             TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other);
-            if (ll->clone_fun != NULL) {
+            if (ll->key_type != NULL) {
                 nbd_free(new_key);
             }
             nbd_free(new_item);
@@ -284,7 +282,7 @@ uint64_t ll_remove (list_t *ll, void *key) {
     } 
 
     // The thread that completes the unlink should free the memory.
-    if (ll->clone_fun != NULL) {
+    if (ll->key_type != NULL) {
         nbd_defer_free(item->key);
     }
     nbd_defer_free(item);
index c4749b3cfc21f80eecfc43147f0000ee26ca52fd..6602a9be05fe7e1983307367453cd7b28dc598e7 100644 (file)
--- a/map/map.c
+++ b/map/map.c
@@ -15,11 +15,11 @@ struct map {
     void *data;
 };
 
-map_t *map_alloc (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { 
+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 = nbd_malloc(sizeof(map_t)); 
     map->impl  = map_impl;
-    map->data  = map->impl->alloc(cmp_fun, hash_fun, clone_fun);
+    map->data  = map->impl->alloc(key_type);
     return map;
 }
 
index 1dae928ebba16191e396734ce7f842e760fbb244..f7de2ac9b62c5442d47bfd6ceb2de76ef0380aa8 100644 (file)
@@ -1,13 +1,13 @@
 #ifndef MLOCAL_H
 #define MLOCAL_H
 
-#include "map.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)  (cmp_fun_t, hash_fun_t, clone_fun_t);
+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 *);
@@ -29,9 +29,9 @@ typedef struct ht hashtable_t;
 typedef struct sl skiplist_t;
 typedef struct ll list_t;
 
-hashtable_t * ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun);
-skiplist_t *  sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun);
-list_t *      ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun);
+hashtable_t * ht_alloc (const datatype_t *key_type);
+skiplist_t *  sl_alloc (const datatype_t *key_type);
+list_t *      ll_alloc (const datatype_t *key_type);
 
 uint64_t ht_cas    (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t val);
 uint64_t ht_get    (hashtable_t *ht, void *key);
index 66bfb2df4f21ada4ff55a8909ee8bfd2713d2312..ad05dd190f25bbae2e7df828d87fe340e3f53925 100644 (file)
@@ -9,9 +9,12 @@
  * See also Kir Fraser's dissertation "Practical Lock Freedom".
  * www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
  *
- * This code is written for the x86 memory-model. The algorithim depends on certain stores and
- * 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.
+ * I've generalized the data structure to support update operations like set() and CAS() in addition to 
+ * the normal add() and remove() operations.
+ *
+ * Warning: This code is written for the x86 memory-model. The algorithim depends on certain stores 
+ * and loads being ordered. 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>
@@ -25,8 +28,7 @@
 #include "mem.h"
 #include "tls.h"
 
-// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list
-// (in list.c).
+// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list (in list.c).
 #define MAX_LEVEL 31
 
 typedef struct node {
@@ -38,8 +40,7 @@ typedef struct node {
 
 struct sl {
     node_t *head;
-    cmp_fun_t cmp_fun;
-    clone_fun_t clone_fun;
+    const datatype_t *key_type;
 };
 
 static const map_impl_t sl_map_impl = { 
@@ -72,10 +73,9 @@ static node_t *node_alloc (int level, void *key, uint64_t val) {
     return item;
 }
 
-skiplist_t *sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) {
+skiplist_t *sl_alloc (const datatype_t *key_type) {
     skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t));
-    sl->cmp_fun = cmp_fun;
-    sl->clone_fun = clone_fun;
+    sl->key_type = key_type;
     sl->head = node_alloc(MAX_LEVEL, NULL, 0);
     memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *));
     return sl;
@@ -159,7 +159,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
 
                     // The thread that completes the unlink should free the memory.
                     if (level == 0) {
-                        if (sl->clone_fun != NULL) {
+                        if (sl->key_type != NULL) {
                             nbd_defer_free((void*)other->key);
                         }
                         nbd_defer_free(other);
@@ -182,10 +182,10 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
             TRACE("s4", "find_preds: visiting item %p (next is %p)", item, next);
             TRACE("s4", "find_preds: key %p val %p", STRIP_TAG(item->key), item->val);
 
-            if (EXPECT_TRUE(sl->cmp_fun == NULL)) {
+            if (EXPECT_TRUE(sl->key_type == NULL)) {
                 d = (uint64_t)item->key - (uint64_t)key;
             } else {
-                d = sl->cmp_fun(item->key, key);
+                d = sl->key_type->cmp(item->key, key);
             }
 
             if (d >= 0) {
@@ -264,7 +264,7 @@ uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expectation, uint64_t new_v
 
             // First insert <new_item> into the bottom level.
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
-            void *new_key  = (sl->clone_fun == NULL) ? key : sl->clone_fun(key);
+            void *new_key  = (sl->key_type == NULL) ? key : sl->key_type->clone(key);
             new_item = node_alloc(n, new_key, new_val);
             node_t *pred = preds[0];
             node_t *next = new_item->next[0] = nexts[0];
@@ -277,7 +277,7 @@ uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expectation, uint64_t new_v
                 break; // success
             }
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
-            if (sl->clone_fun != NULL) {
+            if (sl->key_type != NULL) {
                 nbd_free(new_key);
             }
             nbd_free(new_item);
@@ -381,10 +381,10 @@ uint64_t sl_remove (skiplist_t *sl, void *key) {
 
             int d = -1;
             if (!IS_TAGGED(other)) {
-                if (EXPECT_TRUE(sl->cmp_fun == NULL)) {
+                if (EXPECT_TRUE(sl->key_type == NULL)) {
                     d = (uint64_t)item->key - (uint64_t)other->key;
                 } else {
-                    d = sl->cmp_fun(item->key, other->key);
+                    d = sl->key_type->cmp(item->key, other->key);
                 }
             }
             if (d > 0) {
@@ -418,7 +418,7 @@ uint64_t sl_remove (skiplist_t *sl, void *key) {
     if (SYNC_CAS(&pred->next[0], item, STRIP_TAG(next))) {
         TRACE("s2", "sl_remove: unlinked item %p from the skiplist at level 0", item, 0);
         // The thread that completes the unlink should free the memory.
-        if (sl->clone_fun != NULL) {
+        if (sl->key_type != NULL) {
             nbd_defer_free(item->key);
         }
         nbd_defer_free(item);
@@ -445,7 +445,6 @@ void sl_print (skiplist_t *sl) {
         printf("\n");
         fflush(stdout);
     }
-
     node_t *item = sl->head;
     int i = 0;
     while (item) {
index 34d4ba74f17bb3aed31b00a089a2c6ddd546fa99..7c35b4592e9959acda072443a25135a13894032b 100644 (file)
@@ -10,7 +10,7 @@
 
 #define NUM_ITERATIONS 10000000
 
-//#define TEST_STRING_KEYS
+#define TEST_STRING_KEYS
 
 static volatile int wait_;
 static long num_threads_;
@@ -85,9 +85,9 @@ int main (int argc, char **argv) {
     map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE };
     for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
 #ifdef TEST_STRING_KEYS
-        map_ = map_alloc(map_types[i], (cmp_fun_t)ns_cmp, (hash_fun_t)ns_hash, (clone_fun_t)ns_dup);
+        map_ = map_alloc(map_types[i], &DATATYPE_NSTRING);
 #else
-        map_ = map_alloc(map_types[i], NULL, NULL, NULL);
+        map_ = map_alloc(map_types[i], NULL);
 #endif
 
         struct timeval tv1, tv2;
index 3e13a687b93af27b6aba29faabf8854afe2e5bc5..92a269ec4f81fdd699327e096aad2ed0e2048a60 100644 (file)
 
 #include "common.h"
 #include "runtime.h"
+#include "nstring.h"
 #include "map.h"
 #include "lwt.h"
 
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 
+#define TEST_STRING_KEYS
+
 typedef struct worker_data {
     int id;
     CuTest *tc;
@@ -27,54 +30,66 @@ static map_type_t map_type_;
 // Test some basic stuff; add a few keys, remove a few keys
 void simple (CuTest* tc) {
 
-    map_t *map = map_alloc(map_type_, NULL, NULL, NULL);
-
-    ASSERT_EQUAL( 0,              map_count(map)            );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'a',10)     );
-    ASSERT_EQUAL( 1,              map_count(map)            );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'b',20)     );
-    ASSERT_EQUAL( 2,              map_count(map)            );
-    ASSERT_EQUAL( 20,             map_get(map, (void *)'b')        );
-    ASSERT_EQUAL( 10,             map_set(map, (void *)'a',11)     );
-    ASSERT_EQUAL( 20,             map_set(map, (void *)'b',21)     );
-    ASSERT_EQUAL( 2,              map_count(map)            );
-    ASSERT_EQUAL( 21,             map_add(map, (void *)'b',22)     );
-    ASSERT_EQUAL( 11,             map_remove(map, (void *)'a')     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'a')        );
-    ASSERT_EQUAL( 1,              map_count(map)            );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'a')     );
-    ASSERT_EQUAL( 21,             map_remove(map, (void *)'b')     );
-    ASSERT_EQUAL( 0,              map_count(map)            );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'b')     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'c')     );
-    ASSERT_EQUAL( 0,              map_count(map)            );
+#ifdef TEST_STRING_KEYS
+    map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
+    nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
+    nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
+    nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
+    nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
+#else
+    map_t *map = map_alloc(map_type_, NULL);
+    void *k1 = (void *)1;
+    void *k2 = (void *)2;
+    void *k3 = (void *)3;
+    void *k4 = (void *)4;
+#endif
+
+    ASSERT_EQUAL( 0,              map_count  (map)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k1,10) );
+    ASSERT_EQUAL( 1,              map_count  (map)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k2,20) );
+    ASSERT_EQUAL( 2,              map_count  (map)        );
+    ASSERT_EQUAL( 20,             map_get    (map, k2)    );
+    ASSERT_EQUAL( 10,             map_set    (map, k1,11) );
+    ASSERT_EQUAL( 20,             map_set    (map, k2,21) );
+    ASSERT_EQUAL( 2,              map_count  (map)        );
+    ASSERT_EQUAL( 21,             map_add    (map, k2,22) );
+    ASSERT_EQUAL( 11,             map_remove (map, k1)    );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k1)    );
+    ASSERT_EQUAL( 1,              map_count  (map)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k1)    );
+    ASSERT_EQUAL( 21,             map_remove (map, k2)    );
+    ASSERT_EQUAL( 0,              map_count  (map)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k2)    );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k3)    );
+    ASSERT_EQUAL( 0,              map_count  (map)        );
     
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'d',40)     );
-    ASSERT_EQUAL( 40,             map_get(map, (void *)'d')        );
-    ASSERT_EQUAL( 1,              map_count(map)            );
-    ASSERT_EQUAL( 40,             map_remove(map, (void *)'d')     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d')        );
-    ASSERT_EQUAL( 0,              map_count(map)            );
-
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'d',10) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d')        );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'d',40)     );
-    ASSERT_EQUAL( 40,             map_replace(map, (void *)'d',41) );
-    ASSERT_EQUAL( 41,             map_get(map, (void *)'d')        );
-    ASSERT_EQUAL( 41,             map_remove(map, (void *)'d')     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d')        );
-    ASSERT_EQUAL( 0,              map_count(map)            );
-
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'b',20) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b')        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add    (map, k4,40) );
+    ASSERT_EQUAL( 40,             map_get    (map, k4)    );
+    ASSERT_EQUAL( 1,              map_count  (map)        );
+    ASSERT_EQUAL( 40,             map_remove (map, k4)    );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
+    ASSERT_EQUAL( 0,              map_count  (map)        );
+
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k4,10) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_set    (map, k4,40) );
+    ASSERT_EQUAL( 40,             map_replace(map, k4,41) );
+    ASSERT_EQUAL( 41,             map_get    (map, k4)    );
+    ASSERT_EQUAL( 41,             map_remove (map, k4)    );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k4)    );
+    ASSERT_EQUAL( 0,              map_count  (map)        );
+
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k2,20) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
 
     // In the end, all entries should be removed
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'b',20)     );
-    ASSERT_EQUAL( 20,             map_replace(map, (void *)'b',21) );
-    ASSERT_EQUAL( 21,             map_get(map, (void *)'b')        );
-    ASSERT_EQUAL( 21,             map_remove(map, (void *)'b')     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b')        );
-    ASSERT_EQUAL( 0,              map_count(map)            );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_set    (map, k2,20) );
+    ASSERT_EQUAL( 20,             map_replace(map, k2,21) );
+    ASSERT_EQUAL( 21,             map_get    (map, k2)    );
+    ASSERT_EQUAL( 21,             map_remove (map, k2)    );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get    (map, k2)    );
+    ASSERT_EQUAL( 0,              map_count  (map)        );
 
     map_free(map);
 
@@ -87,20 +102,38 @@ void *add_remove_worker (void *arg) {
     map_t *map = wd->map;
     CuTest* tc = wd->tc;
     uint64_t d = wd->id;
-    int iters = (map_type_ == MAP_TYPE_LIST) ? 5000 : 500000;
+    int iters = 10000;
 
     SYNC_ADD(wd->wait, -1);
     do { } while (*wd->wait); // wait for all workers to be ready
 
+#ifdef TEST_STRING_KEYS
+    nstring_t *key = ns_alloc(9);
+#else
+    void *key;
+#endif
+
     for (int j = 0; j < 10; ++j) {
         for (uint64_t i = d+1; i < iters; i+=2) {
+#ifdef TEST_STRING_KEYS
+            memset(key->data, 0, key->len);
+            snprintf(key->data, key->len, "%llu", i);
+#else
+            key = (void *)i;
+#endif
             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
-            CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, (void *)i, d+1) );
+            CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, key, d+1) );
             rcu_update();
         }
         for (uint64_t i = d+1; i < iters; i+=2) {
+#ifdef TEST_STRING_KEYS
+            memset(key->data, 0, key->len);
+            snprintf(key->data, key->len, "%llu", i);
+#else
+            key = (void *)i;
+#endif
             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
-            CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, (void *)i) );
+            CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, key) );
             rcu_update();
         }
     }
@@ -113,7 +146,11 @@ void add_remove (CuTest* tc) {
     pthread_t thread[2];
     worker_data_t wd[2];
     volatile int wait = 2;
-    map_t *map = map_alloc(map_type_, NULL, NULL, NULL);
+#ifdef TEST_STRING_KEYS
+    map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
+#else
+    map_t *map = map_alloc(map_type_, NULL);
+#endif
 
     struct timeval tv1, tv2;
     gettimeofday(&tv1, NULL);
index dee5151cf4092f3fb0cf669581db8973147432cc..018f19e3657f5406fc6903d7925d4fb251d447b7 100644 (file)
@@ -8,7 +8,7 @@
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 
 void test1 (CuTest* tc) {
-    map_t *map = map_alloc(MAP_TYPE_LIST, NULL, NULL, NULL);
+    map_t *map = map_alloc(MAP_TYPE_LIST, NULL);
     txn_t *t1 = txn_begin(TXN_READ_WRITE, TXN_REPEATABLE_READ, map);
     txn_t *t2 = txn_begin(TXN_READ_WRITE, TXN_REPEATABLE_READ, map);
     tm_set(t1, "abc", 2);