make skiplist and list use strings for keys (slower by 2x...sigh)
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Wed, 26 Nov 2008 00:56:49 +0000 (00:56 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Wed, 26 Nov 2008 00:56:49 +0000 (00:56 +0000)
include/struct.h
struct/hashtable.c
struct/list.c
struct/nstring.c [new file with mode: 0644]
struct/nstring.h [new file with mode: 0644]
struct/skiplist.c
test/ll_test.c
test/sl_test.c
todo

index 3dec0fac440c253b54e331e0cb4cc3ea23580119..513c126099401f5621ed78eb5829464b7e68e3ef 100644 (file)
@@ -19,17 +19,17 @@ uint64_t ht_count  (hashtable_t *ht);
 typedef struct ll list_t;
 list_t * ll_alloc (void);
 
-uint64_t ll_lookup (list_t *ll, uint64_t key);
-uint64_t ll_add    (list_t *ll, uint64_t key, uint64_t value);
-uint64_t ll_remove (list_t *ll, uint64_t key);
+uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len);
+uint64_t ll_add    (list_t *ll, const void *key_data, uint32_t key_len, uint64_t value);
+uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
 void     ll_print  (list_t *ll);
 
 typedef struct sl skiplist_t;
 skiplist_t * sl_alloc (void);
 
-uint64_t sl_lookup (skiplist_t *sl, uint64_t key);
-uint64_t sl_add    (skiplist_t *sl, uint64_t key, uint64_t value);
-uint64_t sl_remove (skiplist_t *sl, uint64_t key);
+uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len);
+uint64_t sl_add    (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t value);
+uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len);
 void     sl_print  (skiplist_t *sl);
 
 #endif//STRUCT_H
index cea12326cae2b7dea34e1cb8b3b0543d50ce48d5..0e9c57e4fdfb4ce71a477c271bb72a0b85cd72b7 100644 (file)
@@ -62,7 +62,7 @@ static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) {
 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_equalsc(GET_PTR(a), b_value, b_len);
+    return ns_cmp_raw(GET_PTR(a), b_value, b_len) == 0;
 }
 
 // Lookup <key> in <hti>. 
@@ -73,8 +73,8 @@ static inline int ht_key_equals (uint64_t a, uint32_t b_hash, const char *b_valu
 //
 // 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_val, uint32_t key_len, int *is_empty) {
-    TRACE("h2", "hti_lookup(key %p in hti %p)", key_val, hti);
+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);
     *is_empty = 0;
 
     // Probe one cache line at a time
@@ -90,13 +90,13 @@ static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, cons
 
             uint64_t e_key = e->key;
             if (e_key == DOES_NOT_EXIST) {
-                TRACE("h1", "hti_lookup: entry %p for key \"%s\" is empty", e, ns_val(GET_PTR(e_key)));
+                TRACE("h1", "hti_lookup: entry %p for key \"%s\" is empty", e, ns_data(GET_PTR(e_key)));
                 *is_empty = 1; // indicate an empty so the caller avoids an expensive ht_key_equals
                 return e;
             }
 
-            if (ht_key_equals(e_key, key_hash, key_val, key_len)) {
-                TRACE("h1", "hti_lookup: entry %p key \"%s\"", e, ns_val(GET_PTR(e_key)));
+            if (ht_key_equals(e_key, key_hash, key_data, key_len)) {
+                TRACE("h1", "hti_lookup: entry %p key \"%s\"", e, ns_data(GET_PTR(e_key)));
                 TRACE("h2", "hti_lookup: entry key len %llu, value %p", ns_len(GET_PTR(e_key)), e->value);
                 return e;
             }
@@ -222,11 +222,11 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
     // 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. 
     if (key_hash == 0) { 
-        key_hash = murmur32(ns_val(key_string), ns_len(key_string));
+        key_hash = murmur32(ns_data(key_string), ns_len(key_string));
     }
 
     int is_empty;
-    volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, ns_val(key_string), ns_len(key_string), &is_empty);
+    volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, ns_data(key_string), ns_len(key_string), &is_empty);
     TRACE("h0", "hti_copy_entry: copy entry %p to entry %p", ht1_e, ht2_e);
 
     // it is possible that there is not any room in the new table either
@@ -262,7 +262,7 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
 
     // 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", ns_val(key_string), value);
+        TRACE("h0", "hti_copy_entry: key \"%s\" value %p copied to new entry", ns_data(key_string), value);
         SYNC_ADD(&ht1->count, -1);
         SYNC_ADD(&ht2->count, 1);
         return TRUE;
@@ -287,16 +287,16 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t
 // real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If
 // <expected> is EXPECT_WHATEVER then skip the test entirely.
 //
-static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, const char *key_val
+static uint64_t hti_compare_and_set (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_compare_and_set: hti %p key %p", hti, key_val);
+    TRACE("h1", "hti_compare_and_set: hti %p key %p", hti, key_data);
     TRACE("h1", "hti_compare_and_set: value %p expect %p", new, expected);
     assert(hti);
     assert(new != DOES_NOT_EXIST && !IS_TAGGED(new));
-    assert(key_val);
+    assert(key_data);
 
     int is_empty;
-    volatile entry_t *e = hti_lookup(hti, key_hash, key_val, key_len, &is_empty);
+    volatile entry_t *e = hti_lookup(hti, key_hash, key_data, key_len, &is_empty);
 
     // There is no room for <key>, grow the table and try again.
     if (e == NULL) {
@@ -317,7 +317,7 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
             return DOES_NOT_EXIST;
 
         // Allocate <key>.
-        nstring_t *key = ns_alloc(key_val, key_len);
+        nstring_t *key = ns_alloc(key_data, key_len);
 
         // 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; 
@@ -328,12 +328,12 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
             TRACE("h0", "hti_compare_and_set: lost race to install key %p in entry %p", key, e);
             TRACE("h0", "hti_compare_and_set: found %p instead of NULL", GET_PTR(e_key), 0);
             nbd_free(key);
-            return hti_compare_and_set(hti, key_hash, key_val, key_len, expected, new); // tail-call
+            return hti_compare_and_set(hti, key_hash, key_data, key_len, expected, new); // tail-call
         }
         TRACE("h2", "hti_compare_and_set: installed key %p in entry %p", key, e);
     }
 
-    TRACE("h0", "hti_compare_and_set: entry for key \"%s\" is %p", ns_val(GET_PTR(e->key)), e);
+    TRACE("h0", "hti_compare_and_set: entry for key \"%s\" is %p", ns_data(GET_PTR(e->key)), e);
 
     // If the entry is in the middle of a copy, the copy must be completed first.
     uint64_t e_value = e->value;
@@ -370,7 +370,7 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
     uint64_t v = SYNC_CAS(&e->value, e_value, new);
     if (EXPECT_FALSE(v != e_value)) {
         TRACE("h0", "hti_compare_and_set: value CAS failed; expected %p found %p", e_value, v);
-        return hti_compare_and_set(hti, key_hash, key_val, key_len, expected, new); // recursive tail-call
+        return hti_compare_and_set(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call
     }
 
     // The set succeeded. Adjust the value count.
@@ -386,18 +386,18 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons
 }
 
 //
-static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_val, uint32_t key_len) {
-    assert(key_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);
 
     int is_empty;
-    volatile entry_t *e = hti_lookup(hti, key_hash, key_val, key_len, &is_empty);
+    volatile entry_t *e = hti_lookup(hti, key_hash, key_data, key_len, &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_val, key_len); // recursive tail-call
+            return hti_get(hti->next, key_hash, key_data, key_len); // recursive tail-call
         return DOES_NOT_EXIST;
     }
 
@@ -413,24 +413,24 @@ static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_
                 SYNC_ADD(&hti->num_entries_copied, 1);
             }
         }
-        return hti_get(((volatile hashtable_i_t *)hti)->next, key_hash, key_val, key_len); // tail-call
+        return hti_get(((volatile hashtable_i_t *)hti)->next, key_hash, key_data, key_len); // tail-call
     }
 
     return (e_value == TOMBSTONE) ? DOES_NOT_EXIST : e_value;
 }
 
 //
-uint64_t ht_get (hashtable_t *ht, const char *key_val, uint32_t key_len) {
-    return hti_get(*ht, murmur32(key_val, key_len), key_val, key_len);
+uint64_t ht_get (hashtable_t *ht, const char *key_data, uint32_t key_len) {
+    return hti_get(*ht, murmur32(key_data, key_len), key_data, key_len);
 }
 
 //
-uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_val, uint32_t key_len, 
+uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key_len, 
                             uint64_t expected_val, uint64_t new_val) {
 
-    TRACE("h2", "ht_compare_and_set: key %p len %u", key_val, key_len);
+    TRACE("h2", "ht_compare_and_set: key %p len %u", key_data, key_len);
     TRACE("h2", "ht_compare_and_set: expected val %p new val %p", expected_val, new_val);
-    assert(key_val);
+    assert(key_data);
     assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
 
     hashtable_i_t *hti = *ht;
@@ -482,8 +482,8 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_val, uint32_t key_
     }
 
     uint64_t old_val;
-    uint32_t key_hash = murmur32(key_val, key_len);
-    while ((old_val = hti_compare_and_set(hti, key_hash, key_val, key_len, expected_val, new_val)) 
+    uint32_t key_hash = murmur32(key_data, key_len);
+    while ((old_val = hti_compare_and_set(hti, key_hash, key_data, key_len, expected_val, new_val)) 
            == COPIED_VALUE) {
         assert(hti->next);
         hti = hti->next;
@@ -492,14 +492,14 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_val, uint32_t key_
     return old_val == TOMBSTONE ? DOES_NOT_EXIST : old_val;
 }
 
-// Remove the value in <ht> associated with <key_val>. Returns the value removed, or 
+// 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_val, uint32_t key_len) {
+uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) {
     hashtable_i_t *hti = *ht;
     uint64_t val;
-    uint32_t key_hash = murmur32(key_val, key_len);
+    uint32_t key_hash = murmur32(key_data, key_len);
     do {
-        val = hti_compare_and_set(hti, key_hash, key_val, key_len, EXPECT_WHATEVER, TOMBSTONE);
+        val = hti_compare_and_set(hti, key_hash, key_data, key_len, EXPECT_WHATEVER, TOMBSTONE);
         if (val != COPIED_VALUE)
             return val == TOMBSTONE ? DOES_NOT_EXIST : val;
         assert(hti->next);
index 29784a9dc61ba2f01286827e9b3e4cec2912b475..02a7c2dbfa206b9783e41ed586e610b157550af7 100644 (file)
 
 #include "common.h"
 #include "struct.h"
+#include "nstring.h"
 #include "mem.h"
 
 typedef struct node {
-    uint64_t key;
+    nstring_t *key;
     uint64_t value;
     struct node *next;
 } node_t;
@@ -22,35 +23,35 @@ struct ll {
     node_t *head;
 };
 
-static node_t *node_alloc (uint64_t key, uint64_t value) {
+static node_t *node_alloc (const void *key_data, uint32_t key_len, uint64_t value) {
     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
     memset(item, 0, sizeof(node_t));
-    item->key   = key;
+    item->key   = key_data ? ns_alloc(key_data, key_len) : NULL;
     item->value = value;
     return item;
 }
 
 list_t *ll_alloc (void) {
     list_t *ll = (list_t *)nbd_malloc(sizeof(list_t));
-    ll->head = node_alloc((uint64_t)-1, 0);
+    ll->head = node_alloc(" ", 0, 0);
     ll->head->next = NULL;
     return ll;
 }
 
-static node_t *find_pred (node_t **pred_ptr, list_t *ll, uint64_t key, int help_remove) {
+static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
     node_t *pred = ll->head;
     node_t *item = pred->next;
-    TRACE("l3", "find_pred: searching for key %p in ll (head is %p)", key, pred);
+    TRACE("l3", "find_pred: searching for key %p in ll (head is %p)", key_data, pred);
 
     while (item != NULL) {
         node_t *next = item->next;
         TRACE("l3", "find_pred: visiting item %p (next %p)", item, next);
-        TRACE("l3", "find_pred: key %p", item->key, item->value);
+        TRACE("l3", "find_pred: key \"%s\"", ns_data(item->key), item->value);
 
-        // Marked items are logically removed, but not unlinked yet.
+        // A tag means an item is logically removed but not physically unlinked yet.
         while (EXPECT_FALSE(IS_TAGGED(next))) {
 
-            // Skip over partially removed items.
+            // Skip over logically removed items.
             if (!help_remove) {
                 item = (node_t *)STRIP_TAG(item->next);
                 if (EXPECT_FALSE(item == NULL))
@@ -59,7 +60,7 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, uint64_t key, int help_
                 continue;
             }
 
-            // Unlink partially removed items.
+            // Unlink logically removed items.
             node_t *other;
             if ((other = SYNC_CAS(&pred->next, item, STRIP_TAG(next))) == item) {
                 item = (node_t *)STRIP_TAG(next);
@@ -74,7 +75,7 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, uint64_t key, int help_
             } else {
                 TRACE("l3", "find_pred: lost race to unlink from pred %p; its link changed to %p", pred, other);
                 if (IS_TAGGED(other))
-                    return find_pred(pred_ptr, ll, key, help_remove); // retry
+                    return find_pred(pred_ptr, ll, key_data, key_len, help_remove); // retry
                 item = other;
                 if (EXPECT_FALSE(item == NULL))
                     break;
@@ -86,12 +87,13 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, uint64_t key, int help_
             break;
 
         // If we reached the key (or passed where it should be), we found the right predesssor
-        if (item->key >= key) {
+        int x = ns_cmp_raw(item->key, key_data, key_len);
+        if (x >= 0) {
             TRACE("l3", "find_pred: found pred %p item %p", pred, item);
             if (pred_ptr != NULL) {
                 *pred_ptr = pred;
             }
-            return item;
+            return x == 0 ? item : NULL;
         }
 
         pred = item;
@@ -107,31 +109,32 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, uint64_t key, int help_
 }
 
 // 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, uint64_t key) {
-    TRACE("l3", "ll_lookup: searching for key %p in ll %p", key, ll);
-    node_t *item = find_pred(NULL, ll, key, FALSE);
+uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) {
+    TRACE("l3", "ll_lookup: searching for key %p in ll %p", key_data, ll);
+    node_t *item = find_pred(NULL, ll, key_data, key_len, FALSE);
 
-    // If we found an <item> matching the <key> return its value.
-    return (item && item->key == key) ? item->value : DOES_NOT_EXIST;
+    // If we found an <item> matching the key return its value.
+    return item != NULL ? item->value : DOES_NOT_EXIST;
 }
 
-// Insert the <key>, if it doesn't already exist in <ll>
-uint64_t ll_add (list_t *ll, uint64_t key, uint64_t value) {
-    TRACE("l3", "ll_add: inserting key %p value %p", key, value);
+// Insert a new item if a matching key doesn't already exist in <ll>
+uint64_t ll_add (list_t *ll, const void *key_data, uint32_t key_len, uint64_t value) {
+    TRACE("l3", "ll_add: inserting key %p value %p", key_data, value);
     node_t *pred;
     node_t *item = NULL;
     do {
-        node_t *next = find_pred(&pred, ll, key, TRUE);
+        node_t *next = find_pred(&pred, ll, key_data, key_len, TRUE);
 
-        // If a node matching <key> already exists in <ll>, return its value.
-        if (next != NULL && next->key == key) {
+        // If a node matching the key already exists in <ll> return its value.
+        if (next != NULL) {
             TRACE("l3", "ll_add: there is already an item %p (value %p) with the same key", next, next->value);
             if (EXPECT_FALSE(item != NULL)) { nbd_free(item); }
             return next->value;
         }
 
+        next = pred->next;
         TRACE("l3", "ll_add: attempting to insert item between %p and %p", pred, next);
-        if (EXPECT_TRUE(item == NULL)) { item = node_alloc(key, value); }
+        if (EXPECT_TRUE(item == NULL)) { item = node_alloc(key_data, key_len, value); }
         item->next = next;
         node_t *other = SYNC_CAS(&pred->next, next, item);
         if (other == next) {
@@ -143,11 +146,11 @@ uint64_t ll_add (list_t *ll, uint64_t key, uint64_t value) {
     } while (1);
 }
 
-uint64_t ll_remove (list_t *ll, uint64_t key) {
-    TRACE("l3", "ll_remove: removing item with key %p from ll %p", key, ll);
+uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) {
+    TRACE("l3", "ll_remove: removing item with key %p from ll %p", key_data, ll);
     node_t *pred;
-    node_t *item = find_pred(&pred, ll, key, TRUE);
-    if (item == NULL || item->key != key) {
+    node_t *item = find_pred(&pred, ll, key_data, key_len, TRUE);
+    if (item == NULL) {
         TRACE("l3", "ll_remove: remove failed, an item with a matching key does not exist in the ll", 0, 0);
         return DOES_NOT_EXIST;
     }
@@ -185,7 +188,7 @@ void ll_print (list_t *ll) {
     node_t *item;
     item = ll->head->next;
     while (item) {
-        printf("0x%llx ", item->key);
+        printf("%s ", (char *)ns_data(item->key));
         fflush(stdout);
         item = item->next;
     }
diff --git a/struct/nstring.c b/struct/nstring.c
new file mode 100644 (file)
index 0000000..840c6df
--- /dev/null
@@ -0,0 +1,24 @@
+#include "common.h"
+#include "nstring.h"
+#include "mem.h"
+
+struct nstring {
+    uint32_t len;
+    char data[];
+};
+
+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 rc = memcmp(ns->data, data, (len < ns->len) ? len : ns->len);
+    return (rc == 0) ? ns->len - len : rc;
+}
+
+const void *ns_data (nstring_t *ns) { return ns->data; }
+
+uint64_t    ns_len  (nstring_t *ns) { return ns->len; }
diff --git a/struct/nstring.h b/struct/nstring.h
new file mode 100644 (file)
index 0000000..ba0d6ec
--- /dev/null
@@ -0,0 +1,11 @@
+#ifndef NSTRING_H
+#define NSTRING_H
+
+typedef struct nstring 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);
+const void *ns_data    (nstring_t *ns);
+uint64_t    ns_len     (nstring_t *ns);
+#endif//NSTRING_H 
index df8e98a75ea6c2bafe77dec7ec6ddae1c50f16c9..0b49fd4937b9c2170ed4c7d20816d51c691bbcea 100644 (file)
@@ -19,6 +19,7 @@
 #include "common.h"
 #include "runtime.h"
 #include "struct.h"
+#include "nstring.h"
 #include "mem.h"
 #include "tls.h"
 
@@ -27,7 +28,7 @@
 #define MAX_LEVEL 31
 
 typedef struct node {
-    uint64_t key;
+    nstring_t *key;
     uint64_t value;
     int top_level;
     struct node *next[];
@@ -50,12 +51,12 @@ static int random_level (void) {
     return n;
 }
 
-node_t *node_alloc (int level, uint64_t key, uint64_t value) {
+node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t value) {
     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);
-    item->key   = key;
+    item->key   = ns_alloc(key_data, key_len);
     item->value = value;
     item->top_level = level;
     return item;
@@ -63,15 +64,16 @@ node_t *node_alloc (int level, uint64_t key, uint64_t value) {
 
 skiplist_t *sl_alloc (void) {
     skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t));
-    sl->head = node_alloc(MAX_LEVEL, 0, 0);
+    sl->head = node_alloc(MAX_LEVEL, " ", 0, 0);
     memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *));
     return sl;
 }
 
-static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, uint64_t key, int help_remove) {
+static node_t *find_preds (int *found, node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
     node_t *pred = sl->head;
     node_t *item = NULL;
-    TRACE("s3", "find_preds: searching for key %p in sl (head is %p)", key, pred);
+    TRACE("s3", "find_preds: searching for key %p in sl (head is %p)", key_data, pred);
+    *found = 0;
 
     int start_level = MAX_LEVEL;
 #if MAX_LEVEL > 2
@@ -95,17 +97,17 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, ui
         item = pred->next[level];
         if (EXPECT_FALSE(IS_TAGGED(item))) {
             TRACE("s3", "find_preds: pred %p is marked for removal (item %p); retry", pred, item);
-            return find_preds(preds, n, sl, key, help_remove); // retry
+            return find_preds(found, preds, n, sl, key_data, key_len, help_remove); // retry
         }
         while (item != NULL) {
             node_t *next = item->next[level];
             TRACE("s3", "find_preds: visiting item %p (next %p)", item, next);
             TRACE("s3", "find_preds: key %p", item->key, 0);
 
-            // Marked items are logically removed, but not fully unlinked yet.
+            // A tag means an item is logically removed but not physically unlinked yet.
             while (EXPECT_FALSE(IS_TAGGED(next))) {
 
-                // Skip over partially removed items.
+                // Skip over logically removed items.
                 if (!help_remove) {
                     item = (node_t *)STRIP_TAG(item->next);
                     if (EXPECT_FALSE(item == NULL))
@@ -114,7 +116,7 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, ui
                     continue;
                 }
 
-                // Unlink partially removed items.
+                // Unlink logically removed items.
                 node_t *other;
                 if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) == item) {
                     item = (node_t *)STRIP_TAG(next);
@@ -129,7 +131,7 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, ui
                 } else {
                     TRACE("s3", "find_preds: lost race to unlink from pred %p; its link changed to %p", pred, other);
                     if (IS_TAGGED(other))
-                        return find_preds(preds, n, sl, key, help_remove); // retry
+                        return find_preds(found, preds, n, sl, key_data, key_len, help_remove); // retry
                     item = other;
                     if (EXPECT_FALSE(item == NULL))
                         break;
@@ -141,7 +143,11 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, ui
                 break;
 
             // If we reached the key (or passed where it should be), we found a pred. Save it and continue down.
-            if (item->key >= key) {
+            int x = ns_cmp_raw(item->key, key_data, key_len);
+            if (x >= 0) {
+                if (level == 0 && x == 0) {
+                    *found = 1;
+                }
                 TRACE("s3", "find_preds: found pred %p item %p", pred, item);
                 break;
             }
@@ -163,32 +169,34 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, ui
 }
 
 // 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, uint64_t key) {
+uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) {
     TRACE("s3", "sl_lookup: searching for key %p in sl %p", key, sl);
-    node_t *item = find_preds(NULL, 0, sl, key, FALSE);
+    int found;
+    node_t *item = find_preds(&found, NULL, 0, sl, key_data, key_len, FALSE);
 
     // If we found an <item> matching the <key> return its value.
-    return (item && item->key == key) ? item->value : DOES_NOT_EXIST;
+    return found ? item->value : DOES_NOT_EXIST;
 }
 
 // Insert the <key> if it doesn't already exist in <sl>
-uint64_t sl_add (skiplist_t *sl, uint64_t key, uint64_t value) {
+uint64_t sl_add (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t value) {
     TRACE("s3", "sl_add: inserting key %p value %p", key, value);
     node_t *preds[MAX_LEVEL+1];
     node_t *item = NULL;
+    int n = random_level();
     do {
-        int n = random_level();
-        node_t *next = find_preds(preds, n, sl, key, TRUE);
+        int found;
+        node_t *next = find_preds(&found, preds, n, sl, key_data, key_len, TRUE);
 
         // If a node matching <key> already exists in <sl>, return its value.
-        if (next != NULL && next->key == key) {
+        if (found) {
             TRACE("s3", "sl_add: there is already an item %p (value %p) with the same key", next, next->value);
             if (EXPECT_FALSE(item != NULL)) { nbd_free(item); }
             return next->value;
         }
 
         // First insert <item> into the bottom level.
-        if (EXPECT_TRUE(item == NULL)) { item = node_alloc(n, key, value); }
+        if (EXPECT_TRUE(item == NULL)) { item = node_alloc(n, key_data, key_len, value); }
         TRACE("s3", "sl_add: attempting to insert item between %p and %p", preds[0], next);
         item->next[0] = next;
         for (int level = 1; level <= item->top_level; ++level) {
@@ -215,9 +223,10 @@ uint64_t sl_add (skiplist_t *sl, uint64_t key, uint64_t value) {
                 next = pred->next[level];
                 if (next == NULL) // item goes at the end of the list
                     break;
-                if (!IS_TAGGED(next) && next->key > key) // pred's link changed
+                if (!IS_TAGGED(next) && ns_cmp_raw(next->key, key_data, key_len) > 0) // pred's link changed
                     break;
-                find_preds(preds, item->top_level, sl, key, TRUE);
+                int found;
+                find_preds(&found, preds, item->top_level, sl, key_data, key_len, TRUE);
             } while (1);
 
             do {
@@ -244,11 +253,12 @@ uint64_t sl_add (skiplist_t *sl, uint64_t key, uint64_t value) {
     return value;
 }
 
-uint64_t sl_remove (skiplist_t *sl, uint64_t key) {
-    TRACE("s3", "sl_remove: removing item with key %p from sl %p", key, sl);
+uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
+    TRACE("s3", "sl_remove: removing item with key %p from sl %p", key_data, sl);
+    int found;
     node_t *preds[MAX_LEVEL+1];
-    node_t *item = find_preds(preds, -1, sl, key, TRUE);
-    if (item == NULL || item->key != key) {
+    node_t *item = find_preds(&found, preds, -1, sl, key_data, key_len, TRUE);
+    if (!found) {
         TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the sl", 0, 0);
         return DOES_NOT_EXIST;
     }
@@ -314,7 +324,7 @@ void sl_print (skiplist_t *sl) {
     node_t *item = sl->head;
     while (item) {
         int is_marked = IS_TAGGED(item->next[0]);
-        printf("%s%p:0x%llx ", is_marked ? "*" : "", item, item->key);
+        printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)ns_data(item->key));
         if (item != sl->head) {
             printf("[%d]", item->top_level);
         } else {
index e7c9337d4f7c02f7c402474209d4c46059ff1790..54ad96b9613015fa93f054433d86e175709841e6 100644 (file)
@@ -22,10 +22,12 @@ void *worker (void *arg) {
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();
         int key = r & 0xF;
+        char key_str[10];
+        sprintf(key_str, "%X", key);
         if (r & (1 << 8)) {
-            ll_add(ll_, key, 1);
+            ll_add(ll_, key_str, strlen(key_str) + 1, 1);
         } else {
-            ll_remove(ll_, key);
+            ll_remove(ll_, key_str, strlen(key_str) + 1);
         }
 
         rcu_update();
index 9fc6466fd6640f939328d823e0a18e1a0fff7b6d..c06becbbfb3009d6cb282fb88a73c7e87fcc8c70 100644 (file)
@@ -22,10 +22,12 @@ void *worker (void *arg) {
     for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
         unsigned r = nbd_rand();
         int key = r & 0xF;
+        char key_str[10];
+        sprintf(key_str, "%X", key);
         if (r & (1 << 8)) {
-            sl_add(sl_, key, 1);
+            sl_add(sl_, key_str, strlen(key_str) + 1, 1);
         } else {
-            sl_remove(sl_, key);
+            sl_remove(sl_, key_str, strlen(key_str) + 1);
         }
 
         rcu_update();
diff --git a/todo b/todo
index 4640dd6d46b6f820e1f6b47040c45b3d6fce898a..bf4dc2194608700faab3b459abc9b9bf747ebaff 100644 (file)
--- a/todo
+++ b/todo
@@ -5,4 +5,5 @@
 + optimize tracing code, still too much overhead
 + use NULL instead of a sentinal node in skiplist and list
 - make interfaces for all data structures consistent 
-- make list and skiplist use string keys
++ make list and skiplist use string keys
+- optimize short strings by embedding the data directly in their pointers