all structures now support arbitrary type keys with a fast path for integers
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Thu, 4 Dec 2008 05:00:44 +0000 (05:00 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Thu, 4 Dec 2008 05:00:44 +0000 (05:00 +0000)
19 files changed:
include/map.h
include/murmur.h
include/nstring.h [new file with mode: 0644]
include/txn.h
makefile
map/hashtable.c
map/list.c
map/map.c
map/mlocal.h
map/nstring.c [deleted file]
map/nstring.h [deleted file]
map/skiplist.c
runtime/nstring.c [new file with mode: 0644]
test/CuTest.c
test/map_test1.c
test/map_test2.c
test/txn_test.c
todo
txn/txn.c

index 44b9d27ea979570be69760a4cc7afb6d368f6a4c..71d0ddee0b90e9c45547fb3576a1c58cb32736b3 100644 (file)
@@ -5,17 +5,21 @@ 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);
-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);
+map_t *  map_alloc  (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun);
+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);
+uint64_t map_cas    (map_t *map, void *key, uint64_t expected_val, uint64_t new_val);
+uint64_t map_replace(map_t *map, void *key, uint64_t new_val);
+uint64_t map_remove (map_t *map, void *key);
 uint64_t map_count  (map_t *map);
 void     map_print  (map_t *map);
 void     map_free   (map_t *map);
index fcb4cb642a9f08285d968135ca67f59712270e8e..84d713580015d474a5c2d3a035b7f8cf3c9b4013 100644 (file)
@@ -61,3 +61,8 @@ static inline unsigned int murmur32 (const char *key, int len)
 
        return h;
 } 
+
+static inline unsigned int murmur32_8b (uint64_t key)
+{
+    return murmur32((char *)&key, 8);
+}
diff --git a/include/nstring.h b/include/nstring.h
new file mode 100644 (file)
index 0000000..5d6fc89
--- /dev/null
@@ -0,0 +1,14 @@
+#ifndef NSTRING_H
+#define NSTRING_H
+
+typedef struct nstring {
+    uint32_t len;
+    char data[];
+} nstring_t;
+
+nstring_t * ns_alloc (uint32_t len);
+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);
+
+#endif//NSTRING_H 
index b2d6a1027cbd2d5a1591bc0fd6bf1c20a379be4a..56144e93086d0a15ee96c4e909b80e7a7ac6e55f 100644 (file)
@@ -17,7 +17,7 @@ txn_t *     txn_begin  (txn_access_e access, txn_isolation_e isolation, map_t *m
 void        txn_abort  (txn_t *txn);
 txn_state_e txn_commit (txn_t *txn);
 
-uint64_t tm_get (txn_t *txn, const char *key, uint32_t key_len);
-void     tm_set (txn_t *txn, const char *key, uint32_t key_len, uint64_t value);
+uint64_t tm_get (txn_t *txn, void *key);
+void     tm_set (txn_t *txn, void *key, uint64_t value);
 
 #endif//TXN_H
index edd67354881390afbcca8daa8827a4feec23e902..21fa6d9a53013ae17275d8e14f453ba1c084debb 100644 (file)
--- a/makefile
+++ b/makefile
@@ -10,8 +10,8 @@ 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
-MAP_SRCS     := map/map.c map/nstring.c map/list.c map/skiplist.c map/hashtable.c
+RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c runtime/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
 txn_test_SRCS  := $(RUNTIME_SRCS) $(MAP_SRCS) test/txn_test.c test/CuTest.c txn/txn.c
index 42ab07e4b9b06adcddef75493fb58728f7e0b9f1..1039ff014bf19d3deb246fcf98c79a6aef8f81f8 100644 (file)
  * weaker operations which would still do the job.
  */
 
+#include <stdio.h>
 #include "common.h"
 #include "murmur.h"
 #include "mem.h"
 #include "mlocal.h"
-#include "nstring.h"
 
-#define GET_PTR(x) ((nstring_t *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
+#define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
 
 typedef struct ht_entry {
-    uint64_t key; // ptr to nstring_t
-    uint64_t value;
+    uint64_t key;
+    uint64_t val;
 } entry_t;
 
 typedef struct hti {
     volatile entry_t *table;
     hashtable_t *ht; // parent ht;
     struct hti *next;
-    struct hti *next_free;
     unsigned int scale;
     int max_probe;
     int count; // TODO: make these counters distributed
     int num_entries_copied;
     int scan;
-} hashtable_i_t;
+} hti_t;
 
 struct ht {
-    hashtable_i_t *hti;
+    hti_t      *hti;
+    cmp_fun_t   cmp_fun;
+    hash_fun_t  hash_fun;
+    clone_fun_t clone_fun;
 };
 
 static const map_impl_t ht_map_impl = { 
@@ -56,7 +58,7 @@ static const unsigned ENTRIES_PER_COPY_CHUNK = CACHE_LINE_SIZE/sizeof(entry_t)*2
 static const unsigned MIN_SCALE              = 4; // min 16 entries (4 buckets)
 static const unsigned MAX_BUCKETS_TO_PROBE   = 250;
 
-static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *e, uint32_t e_key_hash, hashtable_i_t *ht2);
+static int hti_copy_entry (hti_t *ht1, volatile entry_t *ent, uint32_t ent_key_hash, hti_t *ht2);
 
 // Choose the next bucket to probe using the high-order bits of <key_hash>.
 static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) {
@@ -65,27 +67,16 @@ static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) {
     return (old_ndx + incr) & MASK(ht_scale);
 }
 
-// Compare two keys.
-//
-// A key is made up of two parts. The 48 low-order bits are a pointer to a null terminated string.
-// The high-order 16 bits are taken from the hash of that string. The bits from the hash are used 
-// as a quick check to rule out non-equal keys without doing a complete string compare.
-static inline int ht_key_equals (uint64_t a, uint32_t b_hash, const char *b_value, uint32_t b_len) {
-    if ((b_hash >> 16) != (a >> 48)) // high-order 16 bits are from the hash value
-        return FALSE;
-    return ns_cmp_raw(GET_PTR(a), b_value, b_len) == 0;
-}
-
 // Lookup <key> in <hti>. 
 //
 // Return the entry that <key> is in, or if <key> isn't in <hti> return the entry that it would be 
 // in if it were inserted into <hti>. If there is no room for <key> in <hti> then return NULL, to 
 // indicate that the caller should look in <hti->next>.
 //
-// Record if the entry being returned is empty. Otherwise the caller will have to waste time with
-// ht_key_equals() to confirm that it did not lose a race to fill an empty entry.
-static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len, int *is_empty) {
-    TRACE("h2", "hti_lookup(key %p in hti %p)", key_data, hti);
+// Record if the entry being returned is empty. Otherwise the caller will have to waste time 
+// re-comparing the keys to confirm that it did not lose a race to fill an empty entry.
+static volatile entry_t *hti_lookup (hti_t *hti, void *key, uint32_t key_hash, int *is_empty) {
+    TRACE("h2", "hti_lookup(key %p in hti %p)", key, hti);
     *is_empty = 0;
 
     // Probe one cache line at a time
@@ -97,19 +88,31 @@ static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, cons
 
         // Start searching at the indexed entry. Then loop around to the begining of the cache line.
         for (int j = 0; j < ENTRIES_PER_BUCKET; ++j) {
-            volatile entry_t *e = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1));
-
-            uint64_t e_key = e->key;
-            if (e_key == DOES_NOT_EXIST) {
-                TRACE("h1", "hti_lookup: entry %p for key \"%s\" is empty", e, GET_PTR(e_key)->data);
-                *is_empty = 1; // indicate an empty so the caller avoids an expensive ht_key_equals
-                return e;
+            volatile entry_t *ent = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1));
+
+            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));
+                *is_empty = 1; // indicate an empty so the caller avoids an expensive key compare
+                return ent;
             }
 
-            if (ht_key_equals(e_key, key_hash, key_data, key_len)) {
-                TRACE("h1", "hti_lookup: entry %p key \"%s\"", e, GET_PTR(e_key)->data);
-                TRACE("h2", "hti_lookup: entry key len %llu, value %p", GET_PTR(e_key)->len, e->value);
-                return e;
+            // Compare <key> with the key in the entry. 
+            if (EXPECT_TRUE(hti->ht->cmp_fun == 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);
+                    return ent;
+                }
+            } else {
+                // 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) {
+                    TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key));
+                    return ent;
+                }
             }
         }
 
@@ -121,22 +124,22 @@ static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, cons
     return NULL;
 }
 
-// Allocate and initialize a hashtable_i_t with 2^<scale> entries.
-static hashtable_i_t *hti_alloc (hashtable_t *parent, int scale) {
+// Allocate and initialize a hti_t with 2^<scale> entries.
+static hti_t *hti_alloc (hashtable_t *parent, int scale) {
     // Include enough slop to align the actual table on a cache line boundry
-    size_t n = sizeof(hashtable_i_t) 
+    size_t n = sizeof(hti_t) 
              + sizeof(entry_t) * (1 << scale) 
              + (CACHE_LINE_SIZE - 1);
-    hashtable_i_t *hti = (hashtable_i_t *)calloc(n, 1);
+    hti_t *hti = (hti_t *)calloc(n, 1);
 
     // Align the table of hash entries on a cache line boundry.
-    hti->table = (entry_t *)(((uint64_t)hti + sizeof(hashtable_i_t) + (CACHE_LINE_SIZE-1)) 
+    hti->table = (entry_t *)(((uint64_t)hti + sizeof(hti_t) + (CACHE_LINE_SIZE-1)) 
                             & ~(CACHE_LINE_SIZE-1));
 
     hti->scale = scale;
 
     // When searching for a key probe a maximum of 1/4 of the buckets up to 1000 buckets.
-    hti->max_probe = ((1 << (hti->scale - 2)) / ENTRIES_PER_BUCKET) + 2;
+    hti->max_probe = ((1 << (hti->scale - 2)) / ENTRIES_PER_BUCKET) + 4;
     if (hti->max_probe > MAX_BUCKETS_TO_PROBE) {
         hti->max_probe = MAX_BUCKETS_TO_PROBE;
     }
@@ -152,8 +155,8 @@ static hashtable_i_t *hti_alloc (hashtable_t *parent, int scale) {
 
 // Called when <hti> runs out of room for new keys.
 //
-// Initiates a copy by creating a larger hashtable_i_t and installing it in <hti->next>.
-static void hti_start_copy (hashtable_i_t *hti) {
+// Initiates a copy by creating a larger hti_t and installing it in <hti->next>.
+static void hti_start_copy (hti_t *hti) {
     TRACE("h0", "hti_start_copy(hti %p scale %llu)", hti, hti->scale);
 
     // heuristics to determine the size of the new table
@@ -163,8 +166,8 @@ static void hti_start_copy (hashtable_i_t *hti) {
     new_scale += (count > (1 << (new_scale - 2))); // double size again if more than 1/2 full
 
     // Allocate the new table and attempt to install it.
-    hashtable_i_t *next = hti_alloc(hti->ht, new_scale);
-    hashtable_i_t *old_next = SYNC_CAS(&hti->next, NULL, next);
+    hti_t *next = hti_alloc(hti->ht, new_scale);
+    hti_t *old_next = SYNC_CAS(&hti->next, NULL, next);
     if (old_next != NULL) {
         // Another thread beat us to it.
         TRACE("h0", "hti_start_copy: lost race to install new hti; found %p", old_next, 0);
@@ -174,113 +177,111 @@ static void hti_start_copy (hashtable_i_t *hti) {
     TRACE("h0", "hti_start_copy: new hti %p scale %llu", next, next->scale);
 }
 
-// Copy the key and value stored in <ht1_e> (which must be an entry in <ht1>) to <ht2>. 
+// Copy the key and value stored in <ht1_ent> (which must be an entry in <ht1>) to <ht2>. 
 //
-// Return 1 unless <ht1_e> is already copied (then return 0), so the caller can account for the total
+// Return 1 unless <ht1_ent> is already copied (then return 0), so the caller can account for the total
 // number of entries left to copy.
-static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t key_hash, 
-                           hashtable_i_t *ht2) {
-    TRACE("h2", "hti_copy_entry: entry %p to table %p", ht1_e, ht2);
+static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_hash, hti_t *ht2) {
+    TRACE("h2", "hti_copy_entry: entry %p to table %p", ht1_ent, ht2);
     assert(ht1);
     assert(ht1->next);
     assert(ht2);
-    assert(ht1_e >= ht1->table && ht1_e < ht1->table + (1 << ht1->scale));
-    assert(key_hash == 0 || (key_hash >> 16) == (ht1_e->key >> 48));
+    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));
 
-    uint64_t ht1_e_value = ht1_e->value;
-    if (EXPECT_FALSE(ht1_e_value == COPIED_VALUE)) {
-        TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_e, ht2);
+    uint64_t ht1_ent_val = ht1_ent->val;
+    if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) {
+        TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_ent, ht2);
         return FALSE; // already copied
     }
 
     // Kill empty entries.
-    if (EXPECT_FALSE(ht1_e_value == DOES_NOT_EXIST)) {
-        uint64_t ht1_e_value = SYNC_CAS(&ht1_e->value, DOES_NOT_EXIST, COPIED_VALUE);
-        if (ht1_e_value == DOES_NOT_EXIST) {
-            TRACE("h1", "hti_copy_entry: empty entry %p killed", ht1_e, 0);
+    if (EXPECT_FALSE(ht1_ent_val == DOES_NOT_EXIST)) {
+        uint64_t ht1_ent_val = SYNC_CAS(&ht1_ent->val, DOES_NOT_EXIST, COPIED_VALUE);
+        if (ht1_ent_val == DOES_NOT_EXIST) {
+            TRACE("h1", "hti_copy_entry: empty entry %p killed", ht1_ent, 0);
             return TRUE;
         }
-        if (ht1_e_value == COPIED_VALUE) {
-            TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p", ht1_e, 0);
+        if (ht1_ent_val == COPIED_VALUE) {
+            TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p; the entry is already killed", ht1_ent, 0);
             return FALSE; // another thread beat us to it
         }
-        TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p; the entry is now"
-                    "in use and should be copied", ht1_e, 0);
+        TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p; the entry is not empty", ht1_ent, 0);
     }
 
     // Tag the value in the old entry to indicate a copy is in progress.
-    ht1_e_value = SYNC_FETCH_AND_OR(&ht1_e->value, TAG_VALUE(0));
-    TRACE("h2", "hti_copy_entry: tagged the value %p in old entry %p", ht1_e_value, ht1_e);
-    if (ht1_e_value == COPIED_VALUE) {
-        TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_e, ht2);
+    ht1_ent_val = SYNC_FETCH_AND_OR(&ht1_ent->val, TAG_VALUE(0));
+    TRACE("h2", "hti_copy_entry: tagged the value %p in old entry %p", ht1_ent_val, ht1_ent);
+    if (ht1_ent_val == COPIED_VALUE) {
+        TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_ent, ht2);
         return FALSE; // <value> was already copied by another thread.
     }
 
-    // The old table's deleted entries don't need to be copied to the new table, but their keys need
-    // to be freed.
+    // 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);
+
+    // 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_e_value == TOMBSTONE) {
-        TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_e, GET_PTR(ht1_e->key));
-        nbd_defer_free(GET_PTR(ht1_e->key));
+    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)) {
+            nbd_defer_free(key);
+        }
         return TRUE; 
     }
 
-    // Install the key in the new table.
-    uint64_t key = ht1_e->key;
-    nstring_t *key_string = GET_PTR(key);
-    uint64_t value = STRIP_TAG(ht1_e_value);
-
-    // We use 0 to indicate that <key_hash> isn't initiallized. Occasionally the <key_hash> will
-    // really be 0 and we will waste time recomputing it. That is rare enough that it is OK. 
+    // 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 = murmur32(key_string->data, key_string->len);
+        key_hash = (ht1->ht->hash_fun == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->hash_fun(key);
     }
 
-    int is_empty;
-    volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, key_string->data, key_string->len, &is_empty);
-    TRACE("h0", "hti_copy_entry: copy entry %p to entry %p", ht1_e, ht2_e);
+    int ht2_ent_is_empty;
+    volatile entry_t *ht2_ent = hti_lookup(ht2, key, key_hash, &ht2_ent_is_empty);
+    TRACE("h0", "hti_copy_entry: copy entry %p to entry %p", ht1_ent, ht2_ent);
 
-    // it is possible that there is not any room in the new table either
-    if (EXPECT_FALSE(ht2_e == NULL)) {
+    // It is possible that there isn't any room in the new table either.
+    if (EXPECT_FALSE(ht2_ent == NULL)) {
         TRACE("h0", "hti_copy_entry: no room in table %p copy to next table %p", ht2, ht2->next);
         if (ht2->next == NULL) {
             hti_start_copy(ht2); // initiate nested copy, if not already started
         }
-        return hti_copy_entry(ht1, ht1_e, key_hash, ht2->next); // recursive tail-call
+        return hti_copy_entry(ht1, ht1_ent, key_hash, ht2->next); // recursive tail-call
     }
 
-    // a tagged entry returned from hti_lookup() means it is either empty or has a new key
-    if (is_empty) {
-        uint64_t old_ht2_e_key = SYNC_CAS(&ht2_e->key, DOES_NOT_EXIST, key);
-        if (old_ht2_e_key != DOES_NOT_EXIST) {
+    if (ht2_ent_is_empty) {
+        uint64_t old_ht2_ent_key = SYNC_CAS(&ht2_ent->key, DOES_NOT_EXIST, ht1_ent_key);
+        if (old_ht2_ent_key != DOES_NOT_EXIST) {
             TRACE("h0", "hti_copy_entry: lost race to CAS key %p into new entry; found %p",
-                    key, old_ht2_e_key);
-            return hti_copy_entry(ht1, ht1_e, key_hash, ht2); // recursive tail-call
+                    ht1_ent_key, old_ht2_ent_key);
+            return hti_copy_entry(ht1, ht1_ent, key_hash, ht2); // recursive tail-call
         }
     }
 
     // Copy the value to the entry in the new table.
-    uint64_t old_ht2_e_value = SYNC_CAS(&ht2_e->value, DOES_NOT_EXIST, value);
+    ht1_ent_val = STRIP_TAG(ht1_ent_val);
+    uint64_t old_ht2_ent_val = SYNC_CAS(&ht2_ent->val, DOES_NOT_EXIST, ht1_ent_val);
 
     // If there is a nested copy in progress, we might have installed the key into a dead entry.
-    if (old_ht2_e_value == COPIED_VALUE) {
-        TRACE("h0", "hti_copy_entry: nested copy in progress; copy %p to next table %p", ht2_e, ht2->next);
-        return hti_copy_entry(ht1, ht1_e, key_hash, ht2->next); // recursive tail-call
+    if (old_ht2_ent_val == COPIED_VALUE) {
+        TRACE("h0", "hti_copy_entry: nested copy in progress; copy %p to next table %p", ht2_ent, ht2->next);
+        return hti_copy_entry(ht1, ht1_ent, key_hash, ht2->next); // recursive tail-call
     }
 
     // Mark the old entry as dead.
-    ht1_e->value = COPIED_VALUE;
+    ht1_ent->val = COPIED_VALUE;
 
     // Update the count if we were the one that completed the copy.
-    if (old_ht2_e_value == DOES_NOT_EXIST) {
-        TRACE("h0", "hti_copy_entry: key \"%s\" value %p copied to new entry", key_string->data, value);
+    if (old_ht2_ent_val == DOES_NOT_EXIST) {
+        TRACE("h0", "hti_copy_entry: key %p value %p copied to new entry", key, ht1_ent_val);
         SYNC_ADD(&ht1->count, -1);
         SYNC_ADD(&ht2->count, 1);
         return TRUE;
     }
 
     TRACE("h0", "hti_copy_entry: lost race to install value %p in new entry; found value %p", 
-                value, old_ht2_e_value);
+                ht1_ent_val, old_ht2_ent_val);
     return FALSE; // another thread completed the copy
 }
 
@@ -295,22 +296,21 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
 // NOTE: the returned value matches <expected> iff the set succeeds
 //
 // Certain values of <expected> have special meaning. If <expected> is CAS_EXPECT_EXISTS then any 
-// real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If
+// real value matches (i.ent. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If
 // <expected> is CAS_EXPECT_WHATEVER then skip the test entirely.
 //
-static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len,
-                         uint64_t expected, uint64_t new) {
-    TRACE("h1", "hti_cas: hti %p key %p", hti, key_data);
+static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expected, uint64_t new) {
+    TRACE("h1", "hti_cas: hti %p key %p", hti, key);
     TRACE("h1", "hti_cas: value %p expect %p", new, expected);
     assert(hti);
     assert(new != DOES_NOT_EXIST && !IS_TAGGED(new));
-    assert(key_data);
+    assert(key);
 
     int is_empty;
-    volatile entry_t *e = hti_lookup(hti, key_hash, key_data, key_len, &is_empty);
+    volatile entry_t *ent = hti_lookup(hti, key, key_hash, &is_empty);
 
     // There is no room for <key>, grow the table and try again.
-    if (e == NULL) {
+    if (ent == NULL) {
         if (hti->next == NULL) {
             hti_start_copy(hti);
         }
@@ -319,7 +319,7 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_
 
     // Install <key> in the table if it doesn't exist.
     if (is_empty) {
-        TRACE("h0", "hti_cas: entry %p is empty", e, 0);
+        TRACE("h0", "hti_cas: entry %p is empty", ent, 0);
         if (expected != CAS_EXPECT_WHATEVER && expected != CAS_EXPECT_DOES_NOT_EXIST)
             return DOES_NOT_EXIST;
 
@@ -327,30 +327,37 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_
         if (new == TOMBSTONE)
             return DOES_NOT_EXIST;
 
-        // Allocate <key>.
-        nstring_t *key = ns_alloc(key_data, key_len);
+        // 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)) {
+            // Combine <new_key> pointer with bits from its hash 
+            new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key; 
+        }
 
-        // Combine <key> pointer with bits from its hash, CAS it into the table. 
-        uint64_t temp = ((uint64_t)(key_hash >> 16) << 48) | (uint64_t)key; 
-        uint64_t e_key = SYNC_CAS(&e->key, DOES_NOT_EXIST, temp);
+        // CAS the key into the table.
+        uint64_t old_ent_key = SYNC_CAS(&ent->key, DOES_NOT_EXIST, new_key);
 
         // Retry if another thread stole the entry out from under us.
-        if (e_key != DOES_NOT_EXIST) {
-            TRACE("h0", "hti_cas: lost race to install key %p in entry %p", key, e);
-            TRACE("h0", "hti_cas: found %p instead of NULL", GET_PTR(e_key), 0);
-            nbd_free(key);
-            return hti_cas(hti, key_hash, key_data, key_len, expected, new); // tail-call
+        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) {
+                nbd_free(GET_PTR(new_key));
+            }
+            return hti_cas(hti, key, key_hash, expected, new); // tail-call
         }
-        TRACE("h2", "hti_cas: installed key %p in entry %p", key, e);
+        TRACE("h2", "hti_cas: installed key %p in entry %p", new_key, ent);
     }
 
-    TRACE("h0", "hti_cas: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e);
+    TRACE("h0", "hti_cas: entry for key %p is %p", 
+                (hti->ht->clone_fun != 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 e_value = e->value;
-    if (EXPECT_FALSE(IS_TAGGED(e_value))) {
-        if (e_value != COPIED_VALUE) {
-            int did_copy = hti_copy_entry(hti, e, key_hash, ((volatile hashtable_i_t *)hti)->next);
+    uint64_t ent_val = ent->val;
+    if (EXPECT_FALSE(IS_TAGGED(ent_val))) {
+        if (ent_val != COPIED_VALUE) {
+            int did_copy = hti_copy_entry(hti, ent, key_hash, ((volatile hti_t *)hti)->next);
             if (did_copy) {
                 SYNC_ADD(&hti->num_entries_copied, 1);
             }
@@ -362,26 +369,26 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_
     }
 
     // Fail if the old value is not consistent with the caller's expectation.
-    int old_existed = (e_value != TOMBSTONE && e_value != DOES_NOT_EXIST);
-    if (EXPECT_FALSE(expected != CAS_EXPECT_WHATEVER && expected != e_value)) {
+    int old_existed = (ent_val != TOMBSTONE && ent_val != DOES_NOT_EXIST);
+    if (EXPECT_FALSE(expected != CAS_EXPECT_WHATEVER && expected != ent_val)) {
         if (EXPECT_FALSE(expected != (old_existed ? CAS_EXPECT_EXISTS : CAS_EXPECT_DOES_NOT_EXIST))) {
             TRACE("h1", "hti_cas: value %p expected by caller not found; found value %p",
-                        expected, e_value);
-            return e_value;
+                        expected, ent_val);
+            return ent_val;
         }
     }
 
     // No need to update if value is unchanged.
-    if ((new == TOMBSTONE && !old_existed) || e_value == new) {
+    if ((new == TOMBSTONE && !old_existed) || ent_val == new) {
         TRACE("h1", "hti_cas: old value and new value were the same", 0, 0);
-        return e_value;
+        return ent_val;
     }
 
     // CAS the value into the entry. Retry if it fails.
-    uint64_t v = SYNC_CAS(&e->value, e_value, new);
-    if (EXPECT_FALSE(v != e_value)) {
-        TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", e_value, v);
-        return hti_cas(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call
+    uint64_t v = SYNC_CAS(&ent->val, ent_val, new);
+    if (EXPECT_FALSE(v != ent_val)) {
+        TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", ent_val, v);
+        return hti_cas(hti, key, key_hash, expected, new); // recursive tail-call
     }
 
     // The set succeeded. Adjust the value count.
@@ -392,23 +399,21 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_
     }
 
     // Return the previous value.
-    TRACE("h0", "hti_cas: CAS succeeded; old value %p new value %p", e_value, new);
-    return e_value;
+    TRACE("h0", "hti_cas: CAS succeeded; old value %p new value %p", ent_val, new);
+    return ent_val;
 }
 
 //
-static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len) {
-    assert(key_data);
-
+static uint64_t hti_get (hti_t *hti, void *key, uint32_t key_hash) {
     int is_empty;
-    volatile entry_t *e = hti_lookup(hti, key_hash, key_data, key_len, &is_empty);
+    volatile entry_t *ent = hti_lookup(hti, key, key_hash, &is_empty);
 
     // When hti_lookup() returns NULL it means we hit the reprobe limit while
     // searching the table. In that case, if a copy is in progress the key 
     // might exist in the copy.
-    if (EXPECT_FALSE(e == NULL)) {
-        if (((volatile hashtable_i_t *)hti)->next != NULL)
-            return hti_get(hti->next, key_hash, key_data, key_len); // recursive tail-call
+    if (EXPECT_FALSE(ent == NULL)) {
+        if (((volatile hti_t *)hti)->next != NULL)
+            return hti_get(hti->next, key, key_hash); // recursive tail-call
         return DOES_NOT_EXIST;
     }
 
@@ -416,38 +421,39 @@ static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_
         return DOES_NOT_EXIST;
 
     // If the entry is being copied, finish the copy and retry on the next table.
-    uint64_t e_value = e->value;
-    if (EXPECT_FALSE(IS_TAGGED(e_value))) {
-        if (EXPECT_FALSE(e_value != COPIED_VALUE)) {
-            int did_copy = hti_copy_entry(hti, e, key_hash, ((volatile hashtable_i_t *)hti)->next);
+    uint64_t ent_val = ent->val;
+    if (EXPECT_FALSE(IS_TAGGED(ent_val))) {
+        if (EXPECT_FALSE(ent_val != COPIED_VALUE)) {
+            int did_copy = hti_copy_entry(hti, ent, key_hash, ((volatile hti_t *)hti)->next);
             if (did_copy) {
                 SYNC_ADD(&hti->num_entries_copied, 1);
             }
         }
-        return hti_get(((volatile hashtable_i_t *)hti)->next, key_hash, key_data, key_len); // tail-call
+        return hti_get(((volatile hti_t *)hti)->next, key, key_hash); // tail-call
     }
 
-    return (e_value == TOMBSTONE) ? DOES_NOT_EXIST : e_value;
+    return (ent_val == TOMBSTONE) ? DOES_NOT_EXIST : ent_val;
 }
 
 //
-uint64_t ht_get (hashtable_t *ht, const char *key_data, uint32_t key_len) {
-    return hti_get(ht->hti, murmur32(key_data, key_len), key_data, key_len);
+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);
+    return hti_get(ht->hti, key, hash);
 }
 
 //
-uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) {
+uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t new_val) {
 
-    TRACE("h2", "ht_cas: key %p len %u", key_data, key_len);
+    TRACE("h2", "ht_cas: key %p ht %p", key, ht);
     TRACE("h2", "ht_cas: expected val %p new val %p", expected_val, new_val);
-    assert(key_data);
-    assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
+    assert(key != DOES_NOT_EXIST);
+    assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST && new_val != TOMBSTONE);
 
-    hashtable_i_t *hti = ht->hti;
+    hti_t *hti = ht->hti;
 
     // Help with an ongoing copy.
     if (EXPECT_FALSE(hti->next != NULL)) {
-        volatile entry_t *e;
+        volatile entry_t *ent;
         uint64_t limit; 
         int num_copied = 0;
         int x = hti->scan; 
@@ -465,18 +471,18 @@ uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64
             // <hti->scan> might be larger than the size of the table, if some thread stalls while 
             // copying. In that case we just wrap around to the begining and make another pass through
             // the table.
-            e = hti->table + (x & MASK(hti->scale));
+            ent = hti->table + (x & MASK(hti->scale));
         } else {
             TRACE("h1", "ht_cas: help copy panic", 0, 0);
             // scan the whole table
             limit = (1 << hti->scale);
-            e = hti->table;
+            ent = hti->table;
         }
 
         // Copy the entries
         for (int i = 0; i < limit; ++i) {
-            num_copied += hti_copy_entry(hti, e++, 0, hti->next);
-            assert(e <= hti->table + (1 << hti->scale));
+            num_copied += hti_copy_entry(hti, ent++, 0, hti->next);
+            assert(ent <= hti->table + (1 << hti->scale));
         }
         if (num_copied != 0) {
             SYNC_ADD(&hti->num_entries_copied, num_copied);
@@ -492,9 +498,8 @@ uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64
     }
 
     uint64_t old_val;
-    uint32_t key_hash = murmur32(key_data, key_len);
-    while ((old_val = hti_cas(hti, key_hash, key_data, key_len, expected_val, new_val)) 
-           == COPIED_VALUE) {
+    uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key);
+    while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;
     }
@@ -502,14 +507,14 @@ uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64
     return old_val == TOMBSTONE ? DOES_NOT_EXIST : old_val;
 }
 
-// Remove the value in <ht> associated with <key_data>. Returns the value removed, or 
-// DOES_NOT_EXIST if there was no value for that key.
-uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) {
-    hashtable_i_t *hti = ht->hti;
+// Remove the value in <ht> associated with <key>. Returns the value removed, or DOES_NOT_EXIST if there was
+// no value for that key.
+uint64_t ht_remove (hashtable_t *ht, void *key) {
+    hti_t *hti = ht->hti;
     uint64_t val;
-    uint32_t key_hash = murmur32(key_data, key_len);
+    uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key);
     do {
-        val = hti_cas(hti, key_hash, key_data, key_len, CAS_EXPECT_WHATEVER, TOMBSTONE);
+        val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, TOMBSTONE);
         if (val != COPIED_VALUE)
             return val == TOMBSTONE ? DOES_NOT_EXIST : val;
         assert(hti->next);
@@ -520,7 +525,7 @@ uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) {
 
 // Returns the number of key-values pairs in <ht>
 uint64_t ht_count (hashtable_t *ht) {
-    hashtable_i_t *hti = ht->hti;
+    hti_t *hti = ht->hti;
     uint64_t count = 0;
     while (hti) {
         count += hti->count;
@@ -530,23 +535,26 @@ uint64_t ht_count (hashtable_t *ht) {
 }
 
 // Allocate and initialize a new hash table.
-hashtable_t *ht_alloc (void) {
+hashtable_t *ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) {
     hashtable_t *ht = nbd_malloc(sizeof(hashtable_t));
-    ht->hti = (hashtable_i_t *)hti_alloc(ht, MIN_SCALE);
+    ht->cmp_fun = cmp_fun;
+    ht->hash_fun = hash_fun;
+    ht->clone_fun = clone_fun;
+    ht->hti = (hti_t *)hti_alloc(ht, MIN_SCALE);
     return ht;
 }
 
 // Free <ht> and its internal structures.
 void ht_free (hashtable_t *ht) {
-    hashtable_i_t *hti = ht->hti;
+    hti_t *hti = ht->hti;
     do {
         for (uint32_t i = 0; i < (1 << hti->scale); ++i) {
-            assert(hti->table[i].value == COPIED_VALUE || !IS_TAGGED(hti->table[i].value));
-            if (hti->table[i].key != DOES_NOT_EXIST) {
+            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) {
                 nbd_free(GET_PTR(hti->table[i].key));
             }
         }
-        hashtable_i_t *next = hti->next;
+        hti_t *next = hti->next;
         nbd_free(hti);
         hti = next;
     } while (hti);
@@ -554,4 +562,17 @@ void ht_free (hashtable_t *ht) {
 }
 
 void ht_print (hashtable_t *ht) {
+    hti_t *hti = ht->hti;
+    while (hti) {
+        printf("hti:%p scale:%u count:%d copied:%d\n", hti, hti->scale, hti->count, hti->num_entries_copied);
+        for (int i = 0; i < (1 << hti->scale); ++i) {
+            volatile entry_t *ent = hti->table + i;
+            printf("[0x%x] %p:%p\n", i, (void *)ent->key, (void *)ent->val);
+            if (i > 30) {
+                printf("...\n");
+                break;
+            }
+        }
+        hti = hti->next;
+    }
 }
index e726cb15f34c20375aab355ec0967ba4d4439157..979c91e10477de67af9ebeadeea6e539527eb521 100644 (file)
 
 #include "common.h"
 #include "mlocal.h"
-#include "nstring.h"
 #include "mem.h"
 
 typedef struct node {
-    nstring_t *key;
+    void *key;
     uint64_t val;
     struct node *next;
 } node_t;
 
 struct ll {
     node_t *head;
+    cmp_fun_t cmp_fun;
+    clone_fun_t clone_fun;
 };
 
 static const map_impl_t ll_map_impl = { 
@@ -31,34 +32,18 @@ static const map_impl_t ll_map_impl = {
 
 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) {
+static node_t *node_alloc (void *key, uint64_t val) {
     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
-    memset(item, 0, sizeof(node_t));
-    // If <key_len> is -1 it indicates <key_data> is an integer and not a pointer
-    item->key = (key_len == (unsigned)-1) 
-              ? (void *)TAG_VALUE(key_data) 
-              : ns_alloc(key_data, key_len); 
+    item->key = key;
     item->val = val;
     return item;
 }
 
-static void node_free (node_t *item) {
-    if (!IS_TAGGED(item->key)) {
-        nbd_free(item->key);
-    }
-    nbd_free(item);
-}
-
-static void node_defer_free (node_t *item) {
-    if (!IS_TAGGED(item->key)) {
-        nbd_defer_free(item->key);
-    }
-    nbd_defer_free(item);
-}
-
-list_t *ll_alloc (void) {
+list_t *ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) {
     list_t *ll = (list_t *)nbd_malloc(sizeof(list_t));
-    ll->head = node_alloc(" ", 0, 0);
+    ll->cmp_fun = cmp_fun;
+    ll->clone_fun = clone_fun;
+    ll->head = node_alloc(NULL, 0);
     ll->head->next = NULL;
     return ll;
 }
@@ -82,10 +67,10 @@ uint64_t ll_count (list_t *ll) {
     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) {
+static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *key, int help_remove) {
     node_t *pred = ll->head;
     node_t *item = pred->next;
-    TRACE("l2", "find_pred: searching for key %p in ll (head is %p)", key_data, pred);
+    TRACE("l2", "find_pred: searching for key %p in list (head is %p)", key, pred);
 
     while (item != NULL) {
         node_t *next = item->next;
@@ -115,12 +100,15 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo
                 TRACE("l3", "find_pred: now current item is %p next is %p", item, next);
 
                 // The thread that completes the unlink should free the memory.
-                node_defer_free(other);
+                if (ll->clone_fun != NULL) {
+                    nbd_defer_free((void*)other->key);
+                }
+                nbd_defer_free(other);
             } else {
                 TRACE("l2", "find_pred: lost a race to unlink item %p from pred %p", item, pred);
                 TRACE("l2", "find_pred: pred's link changed to %p", other, 0);
                 if (IS_TAGGED(other))
-                    return find_pred(pred_ptr, item_ptr, ll, key_data, key_len, help_remove); // retry
+                    return find_pred(pred_ptr, item_ptr, ll, key, help_remove); // retry
                 item = other;
                 if (EXPECT_FALSE(item == NULL))
                     break;
@@ -132,17 +120,13 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo
             break;
 
         TRACE("l3", "find_pred: visiting item %p (next is %p)", item, next);
-        TRACE("l4", "find_pred: key %p val %p", STRIP_TAG(item->key), item->val);
+        TRACE("l4", "find_pred: key %p val %p", item->key, item->val);
 
-        // A tagged key is an integer, otherwise it is a pointer to a string
         int d;
-        if (IS_TAGGED(item->key)) {
-            d = (STRIP_TAG(item->key) - (uint64_t)key_data);
+        if (EXPECT_TRUE(ll->cmp_fun == NULL)) {
+            d = (uint64_t)item->key - (uint64_t)key;
         } else {
-            int item_key_len = item->key->len;
-            int len = (key_len < item_key_len) ? key_len : item_key_len;
-            d = memcmp(item->key->data, key_data, len);
-            if (d == 0) { d = item_key_len - key_len; }
+            d = ll->cmp_fun(item->key, key);
         }
 
         // If we reached the key (or passed where it should be), we found the right predesssor
@@ -155,7 +139,7 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo
                 TRACE("l2", "find_pred: found matching item %p in list, pred is %p", item, pred);
                 return TRUE;
             } 
-            TRACE("l2", "find_pred: found proper place for key %p in list, pred is %p", key_data, pred);
+            TRACE("l2", "find_pred: found proper place for key %p in list, pred is %p", key, pred);
             return FALSE;
         }
 
@@ -173,10 +157,10 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo
 }
 
 // Fast find. Do not help unlink partially removed nodes and do not return the found item's predecessor.
-uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) {
-    TRACE("l1", "ll_lookup: searching for key %p in list %p", key_data, ll);
+uint64_t ll_lookup (list_t *ll, void *key) {
+    TRACE("l1", "ll_lookup: searching for key %p in list %p", key, ll);
     node_t *item;
-    int found = find_pred(NULL, &item, ll, key_data, key_len, FALSE);
+    int found = find_pred(NULL, &item, ll, key, FALSE);
 
     // If we found an <item> matching the key return its value.
     if (found) {
@@ -191,14 +175,15 @@ uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) {
     return DOES_NOT_EXIST;
 }
 
-uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expectation, uint64_t new_val) {
-    TRACE("l1", "ll_cas: key %p list %p", key_data, ll);
+uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val) {
+    TRACE("l1", "ll_cas: key %p list %p", key, ll);
     TRACE("l1", "ll_cas: expectation %p new value %p", expectation, new_val);
     ASSERT((int64_t)new_val > 0);
 
     do {
         node_t *pred, *old_item;
-        if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) {
+        int found = find_pred(&pred, &old_item, ll, key, TRUE);
+        if (!found) {
 
             // There was not an item in the list that matches the key. 
             if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
@@ -210,7 +195,8 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex
 
             // 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);
-            node_t *new_item = node_alloc(key_data, key_len, new_val);
+            void *new_key  = (ll->clone_fun == NULL) ? key : ll->clone_fun(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);
             if (other == next) {
@@ -220,7 +206,10 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex
 
             // 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);
-            node_free(new_item);
+            if (ll->clone_fun != NULL) {
+                nbd_free(new_key);
+            }
+            nbd_free(new_item);
             continue; // retry
         }
 
@@ -255,11 +244,11 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex
     } while (1);
 }
 
-uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) {
-    TRACE("l1", "ll_remove: removing item with key %p from list %p", key_data, ll);
+uint64_t ll_remove (list_t *ll, void *key) {
+    TRACE("l1", "ll_remove: removing item with key %p from list %p", key, ll);
     node_t *pred;
     node_t *item;
-    int found = find_pred(&pred, &item, ll, key_data, key_len, TRUE);
+    int found = find_pred(&pred, &item, ll, key, TRUE);
     if (!found) {
         TRACE("l1", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0);
         return DOES_NOT_EXIST;
@@ -295,7 +284,10 @@ uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) {
     } 
 
     // The thread that completes the unlink should free the memory.
-    node_defer_free(item); 
+    if (ll->clone_fun != NULL) {
+        nbd_defer_free(item->key);
+    }
+    nbd_defer_free(item);
     TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0);
     return val;
 }
@@ -303,19 +295,19 @@ uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) {
 void ll_print (list_t *ll) {
     node_t *item;
     item = ll->head->next;
+    int i = 0;
     while (item) {
         node_t *next = item->next;
         if (IS_TAGGED(item)) {
             printf("*");
         }
-        printf("%p:", item);
-        if (IS_TAGGED(item->key)) {
-            printf("0x%llx ", STRIP_TAG(item->key));
-        } else {
-            printf("%s ", (char *)item->key->data);
-        }
+        printf("%p:%p ", item, item->key);
         fflush(stdout);
         item = (node_t *)STRIP_TAG(next);
+        if (i++ > 30) {
+            printf("...");
+            break;
+        }
     }
     printf("\n");
 }
index cb761ef3cddfb7b28f2dd80c67157e8bdcfb1033..c4749b3cfc21f80eecfc43147f0000ee26ca52fd 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) { 
+map_t *map_alloc (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { 
     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();
+    map->data  = map->impl->alloc(cmp_fun, hash_fun, clone_fun);
     return map;
 }
 
@@ -35,26 +35,26 @@ 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) {
-    return map->impl->get(map->data, key_data, key_len);
+uint64_t map_get (map_t *map, void *key) {
+    return map->impl->get(map->data, key);
 }
 
-uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
-    return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
+uint64_t map_set (map_t *map, void *key, uint64_t new_val) {
+    return map->impl->cas(map->data, key, CAS_EXPECT_WHATEVER, new_val);
 }
 
-uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
-    return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
+uint64_t map_add (map_t *map, void *key, uint64_t new_val) {
+    return map->impl->cas(map->data, key, 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) {
-    return map->impl->cas(map->data, key_data, key_len, expected_val, new_val);
+uint64_t map_cas (map_t *map, void *key, uint64_t expected_val, uint64_t new_val) {
+    return map->impl->cas(map->data, key, expected_val, new_val);
 }
 
-uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
-    return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
+uint64_t map_replace(map_t *map, void *key, uint64_t new_val) {
+    return map->impl->cas(map->data, key, CAS_EXPECT_EXISTS, new_val);
 }
 
-uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len) {
-    return map->impl->remove(map->data, key_data, key_len);
+uint64_t map_remove (map_t *map, void *key) {
+    return map->impl->remove(map->data, key);
 }
index 9336ab7ae2e6213385820500c24fd61ca529a339..1dae928ebba16191e396734ce7f842e760fbb244 100644 (file)
@@ -1,14 +1,16 @@
 #ifndef MLOCAL_H
 #define MLOCAL_H
 
+#include "map.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 void *   (*map_alloc_t)  (cmp_fun_t, hash_fun_t, clone_fun_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 *);
@@ -27,27 +29,27 @@ typedef struct ht hashtable_t;
 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);
+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);
 
-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);
+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);
+uint64_t ht_remove (hashtable_t *ht, void *key);
 uint64_t ht_count  (hashtable_t *ht);
 void     ht_print  (hashtable_t *ht);
 void     ht_free   (hashtable_t *ht);
 
-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_cas    (skiplist_t *sl, void *key, uint64_t expected_val, uint64_t new_val);
+uint64_t sl_lookup (skiplist_t *sl, void *key);
+uint64_t sl_remove (skiplist_t *sl, void *key);
 uint64_t sl_count  (skiplist_t *sl);
 void     sl_print  (skiplist_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_cas    (list_t *ll, void *key, uint64_t expected_val, uint64_t new_val);
+uint64_t ll_lookup (list_t *ll, void *key);
+uint64_t ll_remove (list_t *ll, void *key);
 uint64_t ll_count  (list_t *ll);
 void     ll_print  (list_t *ll);
 void     ll_free   (list_t *ll);
diff --git a/map/nstring.c b/map/nstring.c
deleted file mode 100644 (file)
index db35ee1..0000000
+++ /dev/null
@@ -1,15 +0,0 @@
-#include "common.h"
-#include "nstring.h"
-#include "mem.h"
-
-nstring_t *ns_alloc (const void *data, uint32_t len) {
-    nstring_t *ns = nbd_malloc(sizeof(nstring_t) + len);
-    ns->len = len;
-    memcpy(ns->data, data, len);
-    return ns;
-}
-
-int ns_cmp_raw (nstring_t *ns, const void *data, uint32_t len) {
-    int d = memcmp(ns->data, data, (len < ns->len) ? len : ns->len);
-    return (d == 0) ? ns->len - len : d;
-}
diff --git a/map/nstring.h b/map/nstring.h
deleted file mode 100644 (file)
index 9aa4ce4..0000000
+++ /dev/null
@@ -1,12 +0,0 @@
-#ifndef NSTRING_H
-#define NSTRING_H
-
-typedef struct nstring {
-    uint32_t len;
-    char data[];
-} nstring_t;
-
-nstring_t * ns_alloc (const void *data, uint32_t len);
-int ns_cmp_raw (nstring_t *ns, const void *data, uint32_t len);
-
-#endif//NSTRING_H 
index ec8a6ff012db11410894c67791c591990d39c07e..66bfb2df4f21ada4ff55a8909ee8bfd2713d2312 100644 (file)
 #include <stdio.h>
 #include <string.h>
 
+#define ENABLE_TRACE
+
 #include "common.h"
 #include "runtime.h"
 #include "mlocal.h"
-#include "nstring.h"
 #include "mem.h"
 #include "tls.h"
 
@@ -29,7 +30,7 @@
 #define MAX_LEVEL 31
 
 typedef struct node {
-    nstring_t *key;
+    void *key;
     uint64_t val;
     int top_level;
     struct node *next[];
@@ -37,6 +38,8 @@ typedef struct node {
 
 struct sl {
     node_t *head;
+    cmp_fun_t cmp_fun;
+    clone_fun_t clone_fun;
 };
 
 static const map_impl_t sl_map_impl = { 
@@ -58,37 +61,22 @@ static int random_level (void) {
     return n;
 }
 
-static node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t val) {
+static node_t *node_alloc (int level, void *key, uint64_t val) {
     assert(level >= 0 && level <= MAX_LEVEL);
     size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *);
     node_t *item = (node_t *)nbd_malloc(sz);
     memset(item, 0, sz);
-    // If <key_len> is -1 it indicates <key_data> is an integer and not a pointer
-    item->key = (key_len == (unsigned)-1) 
-              ? (void *)TAG_VALUE(key_data) 
-              : ns_alloc(key_data, key_len); 
+    item->key = key;
     item->val = val;
     item->top_level = level;
     return item;
 }
 
-static void node_free (node_t *item) {
-    if (!IS_TAGGED(item->key)) {
-        nbd_free(item->key);
-    }
-    nbd_free(item);
-}
-
-static void node_defer_free (node_t *item) {
-    if (!IS_TAGGED(item->key)) {
-        nbd_defer_free(item->key);
-    }
-    nbd_defer_free(item);
-}
-
-skiplist_t *sl_alloc (void) {
+skiplist_t *sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) {
     skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t));
-    sl->head = node_alloc(MAX_LEVEL, " ", 0, 0);
+    sl->cmp_fun = cmp_fun;
+    sl->clone_fun = clone_fun;
+    sl->head = node_alloc(MAX_LEVEL, NULL, 0);
     memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *));
     return sl;
 }
@@ -106,16 +94,18 @@ uint64_t sl_count (skiplist_t *sl) {
     uint64_t count = 0;
     node_t *item = sl->head->next[0];
     while (item) {
-        count++;
+        if (!IS_TAGGED(item->next[0])) {
+            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) {
+static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, void *key, int help_remove) {
     node_t *pred = sl->head;
     node_t *item = NULL;
-    TRACE("s2", "find_preds: searching for key %p in sl (head is %p)", key_data, pred);
+    TRACE("s2", "find_preds: searching for key %p in skiplist (head is %p)", key, pred);
     int d;
     int start_level = MAX_LEVEL;
 #if MAX_LEVEL > 2
@@ -139,7 +129,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
         item = pred->next[level];
         if (EXPECT_FALSE(IS_TAGGED(item))) {
             TRACE("s2", "find_preds: pred %p is marked for removal (item %p); retry", pred, item);
-            return find_preds(preds, succs, n, sl, key_data, key_len, help_remove); // retry
+            return find_preds(preds, succs, n, sl, key, help_remove); // retry
         }
         while (item != NULL) {
             node_t *next = item->next[level];
@@ -168,12 +158,17 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
                     TRACE("s3", "find_preds: now the current item is %p next is %p", item, next);
 
                     // The thread that completes the unlink should free the memory.
-                    if (level == 0) { node_defer_free(other); }
+                    if (level == 0) {
+                        if (sl->clone_fun != NULL) {
+                            nbd_defer_free((void*)other->key);
+                        }
+                        nbd_defer_free(other);
+                    }
                 } else {
-                    TRACE("s2", "find_preds: lost race to unlink item %p from pred %p", item, pred);
-                    TRACE("s2", "find_preds: pred's link changed to %p", other, 0);
+                    TRACE("s3", "find_preds: lost race to unlink item %p from pred %p", item, pred);
+                    TRACE("s3", "find_preds: pred's link changed to %p", other, 0);
                     if (IS_TAGGED(other))
-                        return find_preds(preds, succs, n, sl, key_data, key_len, help_remove); // retry
+                        return find_preds(preds, succs, n, sl, key, help_remove); // retry
                     item = other;
                     if (EXPECT_FALSE(item == NULL))
                         break;
@@ -184,21 +179,17 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
             if (EXPECT_FALSE(item == NULL))
                 break;
 
-            TRACE("s3", "find_preds: visiting item %p (next is %p)", item, next);
+            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);
 
-            // A tagged key is an integer, otherwise it is a pointer to a string
-            if (IS_TAGGED(item->key)) {
-                d = (STRIP_TAG(item->key) - (uint64_t)key_data);
+            if (EXPECT_TRUE(sl->cmp_fun == NULL)) {
+                d = (uint64_t)item->key - (uint64_t)key;
             } else {
-                int item_key_len = item->key->len;
-                int len = (key_len < item_key_len) ? key_len : item_key_len;
-                d = memcmp(item->key->data, key_data, len);
-                if (d == 0) { d = item_key_len - key_len; }
+                d = sl->cmp_fun(item->key, key);
             }
 
             if (d >= 0) {
-                TRACE("s2", "find_preds: found pred %p item %p", pred, item);
+                TRACE("s4", "find_preds: found pred %p item %p", pred, item);
                 break;
             }
 
@@ -217,25 +208,25 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
         }
     }
 
-    // fill in empty levels
-    if (n == -1 && item != NULL) {
-        for (int level = start_level + 1; level <= item->top_level; ++level) {
-            preds[level] = sl->head;
-        }
-    }
-
+     // fill in empty levels
+     if (n == -1 && item != NULL) {
+         for (int level = start_level + 1; level <= item->top_level; ++level) {
+             preds[level] = sl->head;
+         }
+     }
+    
     if (d == 0) {
         TRACE("s2", "find_preds: found matching item %p in skiplist, pred is %p", item, pred);
         return item;
     }
-    TRACE("s2", "find_preds: found proper place for key %p in skiplist, pred is %p. returning null", key_data, pred);
+    TRACE("s2", "find_preds: found proper place for key %p in skiplist, pred is %p. returning null", key, pred);
     return NULL;
 }
 
 // Fast find that does not help unlink partially removed nodes and does not return the node's predecessors.
-uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) {
-    TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key_data, sl);
-    node_t *item = find_preds(NULL, NULL, 0, sl, key_data, key_len, FALSE);
+uint64_t sl_lookup (skiplist_t *sl, void *key) {
+    TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key, sl);
+    node_t *item = find_preds(NULL, NULL, 0, sl, key, FALSE);
 
     // If we found an <item> matching the <key> return its value.
     if (item != NULL) {
@@ -250,8 +241,8 @@ uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) {
     return DOES_NOT_EXIST;
 }
 
-uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expectation, uint64_t new_val) {
-    TRACE("s1", "sl_cas: key %p skiplist %p", key_data, sl);
+uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expectation, uint64_t new_val) {
+    TRACE("s1", "sl_cas: key %p skiplist %p", key, sl);
     TRACE("s1", "sl_cas: expectation %p new value %p", expectation, new_val);
     ASSERT((int64_t)new_val > 0);
 
@@ -260,7 +251,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
     node_t *new_item = NULL;
     int n = random_level();
     do {
-        node_t *old_item = find_preds(preds, nexts, n, sl, key_data, key_len, TRUE);
+        node_t *old_item = find_preds(preds, nexts, n, sl, key, TRUE);
         if (old_item == NULL) {
 
             // There was not an item in the skiplist that matches the key. 
@@ -273,7 +264,8 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
 
             // First insert <new_item> into the bottom level.
             TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
-            new_item = node_alloc(n, key_data, key_len, new_val);
+            void *new_key  = (sl->clone_fun == NULL) ? key : sl->clone_fun(key);
+            new_item = node_alloc(n, new_key, new_val);
             node_t *pred = preds[0];
             node_t *next = new_item->next[0] = nexts[0];
             for (int level = 1; level <= new_item->top_level; ++level) {
@@ -285,7 +277,10 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
                 break; // success
             }
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
-            node_free(new_item);
+            if (sl->clone_fun != NULL) {
+                nbd_free(new_key);
+            }
+            nbd_free(new_item);
             continue;
         }
 
@@ -331,7 +326,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
                 break; // success
             }
             TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
-            find_preds(preds, nexts, new_item->top_level, sl, key_data, key_len, TRUE);
+            find_preds(preds, nexts, new_item->top_level, sl, key, TRUE);
             pred = preds[level];
             next = nexts[level];
 
@@ -351,62 +346,83 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
     return DOES_NOT_EXIST; // success
 }
 
-uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
-    TRACE("s1", "sl_remove: removing item with key %p from skiplist %p", key_data, sl);
+uint64_t sl_remove (skiplist_t *sl, void *key) {
+    TRACE("s1", "sl_remove: removing item with key %p from skiplist %p", key, sl);
     node_t *preds[MAX_LEVEL+1];
-    node_t *item = find_preds(preds, NULL, -1, sl, key_data, key_len, TRUE);
+    node_t *item = find_preds(preds, NULL, -1, sl, key, TRUE);
     if (item == NULL) {
         TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the skiplist", 0, 0);
         return DOES_NOT_EXIST;
     }
 
-    // Mark <item> removed at each level of <sl> from the top down. This must be atomic. If multiple threads
-    // try to remove the same item only one of them should succeed. Marking the bottom level establishes which of 
-    // them succeeds.
-    for (int level = item->top_level; level >= 0; --level) {
-        if (EXPECT_FALSE(IS_TAGGED(item->next[level]))) {
-            TRACE("s3", "sl_remove: %p is already marked for removal by another thread", item, 0);
-            if (level == 0)
-                return DOES_NOT_EXIST;
-            continue;
-        }
+    // Mark and unlink <item> at each level of <sl> from the top down. If multiple threads try to concurrently remove
+    // the same item only one of them should succeed. Marking the bottom level establishes which of them succeeds.
+    for (int level = item->top_level; level > 0; --level) {
         node_t *next;
         node_t *old_next = item->next[level];
         do {
             next = old_next;
             old_next = SYNC_CAS(&item->next[level], next, TAG_VALUE(next));
             if (IS_TAGGED(old_next)) {
-                TRACE("s2", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0);
-                if (level == 0)
-                    return DOES_NOT_EXIST;
+                TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level %llu", item, level);
                 break;
             }
         } while (next != old_next);
-    }
-
-    // This has to be an atomic swap in case another thread is updating the item while we are removing it. 
-    uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST); 
-    TRACE("s2", "sl_remove: replaced item's val %p with DOES_NOT_EXIT", val, 0);
 
-    // Unlink <item> from <sl>. If we lose a race to another thread just back off. It is safe to leave the
-    // item partially unlinked for a later call (or some other thread) to physically unlink. By marking the
-    // item earlier, we logically removed it. 
-    int level = item->top_level;
-    while (level >= 0) {
         node_t *pred = preds[level];
-        node_t *next = item->next[level];
-        TRACE("s2", "sl_remove: unlink the item by linking its pred %p to it's successor %p", pred, STRIP_TAG(next));
+        TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next));
         node_t *other = NULL;
         if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) != item) {
             TRACE("s1", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other);
-            return val;
+            // If our former predecessor now points past us we know another thread unlinked us. Otherwise, we need
+            // to search for a new set of preds.
+            if (other == NULL)
+                continue; // <pred> points past <item> to the end of the list; go on to the next level.
+
+            int d = -1;
+            if (!IS_TAGGED(other)) {
+                if (EXPECT_TRUE(sl->cmp_fun == NULL)) {
+                    d = (uint64_t)item->key - (uint64_t)other->key;
+                } else {
+                    d = sl->cmp_fun(item->key, other->key);
+                }
+            }
+            if (d > 0) {
+                node_t *temp = find_preds(preds, NULL, level, sl, key, TRUE);
+                if (temp != item)
+                    return DOES_NOT_EXIST; // Another thread removed the item we were targeting.
+                level++; // Redo this level.
+            }
         }
-        --level; 
     }
 
-    // The thread that completes the unlink should free the memory.
-    TRACE("s1", "sl_remove: successfully unlinked item %p from the skiplist", item, 0);
-    node_defer_free(item); 
+    node_t *next;
+    node_t *old_next = item->next[0];
+    do {
+        next = old_next;
+        old_next = SYNC_CAS(&item->next[0], next, TAG_VALUE(next));
+        if (IS_TAGGED(old_next)) {
+            TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level 0", item, 0);
+            return DOES_NOT_EXIST;
+        }
+    } while (next != old_next);
+    TRACE("s1", "sl_remove: marked item %p removed at level 0", item, 0);
+
+    // Atomically swap out the item's value in case another thread is updating the item while we are 
+    // removing it. This establishes which one occurs first, the update or the remove. 
+    uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST); 
+    TRACE("s2", "sl_remove: replaced item %p's value with DOES_NOT_EXIT", item, 0);
+
+    node_t *pred = preds[0];
+    TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next));
+    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) {
+            nbd_defer_free(item->key);
+        }
+        nbd_defer_free(item);
+    }
     return val;
 }
 
@@ -416,29 +432,29 @@ void sl_print (skiplist_t *sl) {
         if (item->next[level] == NULL)
             continue;
         printf("(%d) ", level);
+        int i = 0;
         while (item) {
             node_t *next = item->next[level];
             printf("%s%p ", IS_TAGGED(next) ? "*" : "", item);
             item = (node_t *)STRIP_TAG(next);
+            if (i++ > 30) {
+                printf("...");
+                break;
+            }
         }
         printf("\n");
         fflush(stdout);
     }
 
-    printf("\n");
     node_t *item = sl->head;
+    int i = 0;
     while (item) {
         int is_marked = IS_TAGGED(item->next[0]);
-
-        if (IS_TAGGED(item->key)) {
-            printf("%s%p:%llx ", is_marked ? "*" : "", item, STRIP_TAG(item->key));
-        } else {
-            printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)item->key->data);
-        }
+        printf("%s%p:%p ", is_marked ? "*" : "", item, item->key);
         if (item != sl->head) {
             printf("[%d]", item->top_level);
         } else {
-            printf("[*]");
+            printf("[HEAD]");
         }
         for (int level = 1; level <= item->top_level; ++level) {
             node_t *next = (node_t *)STRIP_TAG(item->next[level]);
@@ -450,5 +466,9 @@ void sl_print (skiplist_t *sl) {
         printf("\n");
         fflush(stdout);
         item = (node_t *)STRIP_TAG(item->next[0]);
+        if (i++ > 30) {
+            printf("...\n");
+            break;
+        }
     }
 }
diff --git a/runtime/nstring.c b/runtime/nstring.c
new file mode 100644 (file)
index 0000000..a3fdd1f
--- /dev/null
@@ -0,0 +1,25 @@
+#include "common.h"
+#include "nstring.h"
+#include "murmur.h"
+#include "mem.h"
+
+nstring_t *ns_alloc (uint32_t len) {
+    nstring_t *ns = nbd_malloc(sizeof(nstring_t) + len);
+    ns->len = len;
+    return ns;
+}
+
+int ns_cmp (const nstring_t *ns1, const nstring_t *ns2) {
+    int d = memcmp(ns1->data, ns2->data, (ns1->len < ns2->len) ? ns1->len : ns1->len);
+    return (d == 0) ? ns1->len - ns2->len : d;
+}
+
+uint32_t ns_hash (const nstring_t *ns) {
+    return murmur32(ns->data, ns->len);
+}
+
+nstring_t *ns_dup (const nstring_t *ns1) {
+    nstring_t *ns2 = ns_alloc(ns1->len);
+    memcpy(ns2->data, ns1->data, ns1->len);
+    return ns2;
+}
index 2bcce6064fb37498ee4fd1b3b71ac44f8bb631ec..6eccb947a70f3a20592cded745d097c7bc0e9861 100644 (file)
@@ -140,10 +140,9 @@ static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* str
 
        tc->failed = 1;
        tc->message = string->buffer;
-#ifdef ENABLE_TRACE
+    extern void lwt_halt(void);
     extern void lwt_dump(const char *);
     lwt_dump(tc->name);
-#endif
        if (tc->jumpBuf != 0) longjmp(*(tc->jumpBuf), 0);
 }
 
index 30d7ce0e4a7121d0e4349d33bf2417e8711a6b3c..34d4ba74f17bb3aed31b00a089a2c6ddd546fa99 100644 (file)
@@ -4,11 +4,14 @@
 #include <sys/time.h>
 
 #include "common.h"
+#include "nstring.h"
 #include "runtime.h"
 #include "map.h"
 
 #define NUM_ITERATIONS 10000000
 
+//#define TEST_STRING_KEYS
+
 static volatile int wait_;
 static long num_threads_;
 static map_t *map_;
@@ -19,22 +22,26 @@ void *worker (void *arg) {
     SYNC_ADD(&wait_, -1);
     do {} while (wait_); 
 
+#ifdef TEST_STRING_KEYS
+        nstring_t *key_str = ns_alloc(10);
+#endif
+
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();
         uint64_t key = r & 0xF;
-#if 1
-        char key_str[10];
-        sprintf(key_str, "%llX", key);
+#ifdef TEST_STRING_KEYS
+        key_str->len = sprintf(key_str->data, "%llX", key) + 1;
+        assert(key_str->len <= 10);
         if (r & (1 << 8)) {
-            map_set(map_, key_str, strlen(key_str) + 1, 1);
+            map_set(map_, key_str, 1);
         } else {
-            map_remove(map_, key_str, strlen(key_str) + 1);
+            map_remove(map_, key_str);
         }
 #else
         if (r & (1 << 8)) {
-            map_set(map_, (void *)key, -1, 1);
+            map_set(map_, (void *)(key + 1), 1);
         } else {
-            map_remove(map_, (void *)key, -1);
+            map_remove(map_, (void *)(key + 1));
         }
 #endif
 
@@ -46,7 +53,7 @@ void *worker (void *arg) {
 
 int main (int argc, char **argv) {
     nbd_init();
-    //lwt_set_trace_level("l3");
+    lwt_set_trace_level("l3");
 
     char* program_name = argv[0];
     pthread_t thread[MAX_NUM_THREADS];
@@ -77,7 +84,11 @@ 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) {
-        map_ = map_alloc(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);
+#else
+        map_ = map_alloc(map_types[i], NULL, NULL, NULL);
+#endif
 
         struct timeval tv1, tv2;
         gettimeofday(&tv1, NULL);
@@ -96,7 +107,7 @@ int main (int argc, char **argv) {
         gettimeofday(&tv2, NULL);
         int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
         map_print(map_);
-        printf("Th:%ld Time:%dms\n", num_threads_, ms);
+        printf("Th:%ld Time:%dms\n\n", num_threads_, ms);
         fflush(stdout);
     }
 
index b321a683b1daabee11595940143ec2312f328e0a..3e13a687b93af27b6aba29faabf8854afe2e5bc5 100644 (file)
@@ -4,6 +4,7 @@
  */
 #include <stdio.h>
 #include <pthread.h>
+#include <sys/time.h>
 
 #include "CuTest.h"
 
@@ -18,61 +19,61 @@ typedef struct worker_data {
     int id;
     CuTest *tc;
     map_t *map;
-    int *wait;
+    volatile int *wait;
 } worker_data_t;
 
 static map_type_t map_type_;
 
 // Test some basic stuff; add a few keys, remove a few keys
-void basic_test (CuTest* tc) {
+void simple (CuTest* tc) {
 
-    map_t *map = map_alloc(map_type_);
+    map_t *map = map_alloc(map_type_, NULL, NULL, NULL);
 
     ASSERT_EQUAL( 0,              map_count(map)            );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map,"a",2,10)     );
+    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,"b",2,20)     );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'b',20)     );
     ASSERT_EQUAL( 2,              map_count(map)            );
-    ASSERT_EQUAL( 20,             map_get(map,"b",2)        );
-    ASSERT_EQUAL( 10,             map_set(map,"a",2,11)     );
-    ASSERT_EQUAL( 20,             map_set(map,"b",2,21)     );
+    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,"b",2,22)     );
-    ASSERT_EQUAL( 11,             map_remove(map,"a",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"a",2)        );
+    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,"a",2)     );
-    ASSERT_EQUAL( 21,             map_remove(map,"b",2)     );
+    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,"b",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map,"c",2)     );
+    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)            );
     
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map,"d",2,40)     );
-    ASSERT_EQUAL( 40,             map_get(map,"d",2)        );
+    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,"d",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"d",2)        );
+    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,"d",2,10) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"d",2)        );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map,"d",2,40)     );
-    ASSERT_EQUAL( 40,             map_replace(map,"d",2,41) );
-    ASSERT_EQUAL( 41,             map_get(map,"d",2)        );
-    ASSERT_EQUAL( 41,             map_remove(map,"d",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"d",2)        );
+    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,"b",2,20) );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"b",2)        );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'b',20) );
+    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b')        );
 
     // In the end, all entries should be removed
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map,"b",2,20)     );
-    ASSERT_EQUAL( 20,             map_replace(map,"b",2,21) );
-    ASSERT_EQUAL( 21,             map_get(map,"b",2)        );
-    ASSERT_EQUAL( 21,             map_remove(map,"b",2)     );
-    ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"b",2)        );
+    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)            );
 
     map_free(map);
@@ -81,29 +82,25 @@ void basic_test (CuTest* tc) {
     rcu_update();
 }
 
-void *simple_worker (void *arg) {
+void *add_remove_worker (void *arg) {
     worker_data_t *wd = (worker_data_t *)arg;
     map_t *map = wd->map;
     CuTest* tc = wd->tc;
     uint64_t d = wd->id;
-    int iters = map_type_ == MAP_TYPE_LIST ? 100 : 1000000;
+    int iters = (map_type_ == MAP_TYPE_LIST) ? 5000 : 500000;
 
     SYNC_ADD(wd->wait, -1);
-    do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready
+    do { } while (*wd->wait); // wait for all workers to be ready
 
     for (int j = 0; j < 10; ++j) {
-        for (int i = d; i < iters; i+=2) {
-            char key[10];
-            sprintf(key, "k%u", i); 
+        for (uint64_t i = d+1; i < iters; i+=2) {
             TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
-            CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, map_add(map, key, strlen(key)+1, d+1) );
+            CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, (void *)i, d+1) );
             rcu_update();
         }
-        for (int i = d; i < iters; i+=2) {
-            char key[10];
-            sprintf(key, "k%u", i); 
+        for (uint64_t i = d+1; i < iters; i+=2) {
             TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
-            CuAssertIntEquals_Msg(tc, key, d+1, map_remove(map, key, strlen(key)+1) );
+            CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, (void *)i) );
             rcu_update();
         }
     }
@@ -111,12 +108,15 @@ void *simple_worker (void *arg) {
 }
 
 // Do some simple concurrent testing
-void simple_add_remove (CuTest* tc) {
+void add_remove (CuTest* tc) {
 
     pthread_t thread[2];
     worker_data_t wd[2];
-    int wait = 2;
-    map_t *map = map_alloc(map_type_);
+    volatile int wait = 2;
+    map_t *map = map_alloc(map_type_, NULL, NULL, NULL);
+
+    struct timeval tv1, tv2;
+    gettimeofday(&tv1, NULL);
 
     // In 2 threads, add & remove even & odd elements concurrently
     int i;
@@ -125,13 +125,20 @@ void simple_add_remove (CuTest* tc) {
         wd[i].tc = tc;
         wd[i].map = map;
         wd[i].wait = &wait;
-        int rc = nbd_thread_create(thread + i, i, simple_worker, wd + i);
+        int rc = nbd_thread_create(thread + i, i, add_remove_worker, wd + i);
         if (rc != 0) { perror("nbd_thread_create"); return; }
     }
+
     for (i = 0; i < 2; ++i) {
         pthread_join(thread[i], NULL);
     }
 
+    gettimeofday(&tv2, NULL);
+    int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
+    map_print(map);
+    printf("Th:%d Time:%dms\n", 2, ms);
+    fflush(stdout);
+
     // In the end, all members should be removed
     ASSERT_EQUAL( 0, map_count(map) );
 
@@ -139,7 +146,6 @@ void simple_add_remove (CuTest* tc) {
     map_free(map);
 }
 
-
 void *inserter_worker (void *arg) {
     //pthread_t thread[NUM_THREADS];
 
@@ -154,7 +160,7 @@ void concurrent_insert (CuTest* tc) {
 int main (void) {
 
     nbd_init();
-    //lwt_set_trace_level("h0");
+    lwt_set_trace_level("h3");
 
     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) {
@@ -164,8 +170,8 @@ int main (void) {
         CuString *output = CuStringNew();
         CuSuite* suite = CuSuiteNew();
 
-        SUITE_ADD_TEST(suite, basic_test);
-        SUITE_ADD_TEST(suite, simple_add_remove);
+        SUITE_ADD_TEST(suite, simple);
+        SUITE_ADD_TEST(suite, add_remove);
 
         CuSuiteRun(suite);
         CuSuiteDetails(suite, output);
index 6e9044fbbdf29c2e5eb8e227380a215414d048e8..dee5151cf4092f3fb0cf669581db8973147432cc 100644 (file)
@@ -8,15 +8,15 @@
 #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
 
 void test1 (CuTest* tc) {
-    map_t *map = map_alloc(MAP_TYPE_LIST);
+    map_t *map = map_alloc(MAP_TYPE_LIST, NULL, NULL, 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", 4, 2);
-    tm_set(t1, "abc", 4, 3);
-    ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, "abc", 4) );
-    tm_set(t2, "abc", 4, 4);
-    ASSERT_EQUAL( 3, tm_get(t1, "abc", 4) );
-    ASSERT_EQUAL( 4, tm_get(t2, "abc", 4) );
+    tm_set(t1, "abc", 2);
+    tm_set(t1, "abc", 3);
+    ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, "abc") );
+    tm_set(t2, "abc", 4);
+    ASSERT_EQUAL( 3, tm_get(t1, "abc") );
+    ASSERT_EQUAL( 4, tm_get(t2, "abc") );
     ASSERT_EQUAL( TXN_VALIDATED, txn_commit(t2));
     ASSERT_EQUAL( TXN_ABORTED, txn_commit(t1));
 }
diff --git a/todo b/todo
index e052f1c24e2f30711bade75f72ca32fe0622f584..9ed547fdfd6eb4faad1a05c8f89eba5dfe1d71d2 100644 (file)
--- a/todo
+++ b/todo
@@ -11,3 +11,6 @@
 + optimize integer keys
 - ht_print()
 - iterators
+- characterize performance of data structures
+- experiment with the performance impact of not passing the hash between functions
+- experiment with embedding key is the list/skiplist nodes
index 52758824e60dc3d9b7f2973364a12f81acccebf8..3edf666983962076dfb7110f3b3975241055ff63 100644 (file)
--- a/txn/txn.c
+++ b/txn/txn.c
@@ -21,7 +21,7 @@ struct update_rec {
 };
 
 typedef struct write_rec {
-    const char *key;
+    void *key;
     update_rec_t *rec; 
 } write_rec_t;
 
@@ -44,9 +44,9 @@ static uint64_t version_ = 1;
 
 // Validate the updates for <key>. Validation fails for a key we have written to if there is a 
 // write committed newer than our read version.
-static txn_state_e tm_validate_key (txn_t *txn, const char *key, uint32_t key_len) {
+static txn_state_e tm_validate_key (txn_t *txn, void *key) {
     
-    update_rec_t *update = (update_rec_t *) map_get(txn->map, key, key_len);
+    update_rec_t *update = (update_rec_t *) map_get(txn->map, key);
     for (; update != NULL; update = update->prev) {
         uint64_t writer_version = update->version;
         if (writer_version <= txn->rv)
@@ -102,7 +102,7 @@ static txn_state_e txn_validate (txn_t *txn) {
             }
 
             for (i = 0; i < txn->writes_count; ++i) {
-                txn_state_e s = tm_validate_key(txn, txn->writes[i].key, strlen(txn->writes[i].key));
+                txn_state_e s = tm_validate_key(txn, txn->writes[i].key);
                 if (s == TXN_ABORTED) {
                     txn->state = TXN_ABORTED;
                     break;
@@ -179,11 +179,11 @@ txn_state_e txn_commit (txn_t *txn) {
 }
 
 // Get most recent committed version prior to our read version.
-uint64_t tm_get (txn_t *txn, const char *key, uint32_t key_len) {
+uint64_t tm_get (txn_t *txn, void *key) {
 
     // Iterate through update records associated with <key> to find the latest committed version. 
     // We can use the first matching version. Older updates always come later in the list.
-    update_rec_t *update = (update_rec_t *) map_get(txn->map, key, key_len);
+    update_rec_t *update = (update_rec_t *) map_get(txn->map, key);
     for (; update != NULL; update = update->prev) {
         uint64_t writer_version = update->version;
         if (writer_version < txn->rv)
@@ -213,7 +213,7 @@ uint64_t tm_get (txn_t *txn, const char *key, uint32_t key_len) {
     return DOES_NOT_EXIST;
 }
 
-void tm_set (txn_t *txn, const char *key, uint32_t key_len, uint64_t value) {
+void tm_set (txn_t *txn, void *key, uint64_t value) {
 
     // create a new update record
     update_rec_t *update = alloc_update_rec();
@@ -224,9 +224,9 @@ void tm_set (txn_t *txn, const char *key, uint32_t key_len, uint64_t value) {
     // push the new update record onto <key>'s update list
     uint64_t update_prev;
     do {
-        update->prev = (update_rec_t *) map_get(txn->map, key, key_len);
+        update->prev = (update_rec_t *) map_get(txn->map, key);
         update_prev = (uint64_t)update->prev;
-    } while (map_cas(txn->map, key, key_len, update_prev, (uint64_t)update) != update_prev);
+    } while (map_cas(txn->map, key, update_prev, (uint64_t)update) != update_prev);
 
     // add <key> to the write set for commit-time validation
     if (txn->writes_count == txn->writes_size) {