From 53d171373819e921da8f8648eea236a08ff6a702 Mon Sep 17 00:00:00 2001 From: jdybnis Date: Wed, 26 Nov 2008 00:56:49 +0000 Subject: [PATCH] make skiplist and list use strings for keys (slower by 2x...sigh) --- include/struct.h | 12 ++++----- struct/hashtable.c | 66 +++++++++++++++++++++++----------------------- struct/list.c | 63 ++++++++++++++++++++++--------------------- struct/nstring.c | 24 +++++++++++++++++ struct/nstring.h | 11 ++++++++ struct/skiplist.c | 64 +++++++++++++++++++++++++------------------- test/ll_test.c | 6 +++-- test/sl_test.c | 6 +++-- todo | 3 ++- 9 files changed, 154 insertions(+), 101 deletions(-) create mode 100644 struct/nstring.c create mode 100644 struct/nstring.h diff --git a/include/struct.h b/include/struct.h index 3dec0fa..513c126 100644 --- a/include/struct.h +++ b/include/struct.h @@ -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 diff --git a/struct/hashtable.c b/struct/hashtable.c index cea1232..0e9c57e 100644 --- a/struct/hashtable.c +++ b/struct/hashtable.c @@ -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 in . @@ -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 isn't initiallized. Occasionally the 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 is in the table. If // 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 , 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 . - nstring_t *key = ns_alloc(key_val, key_len); + nstring_t *key = ns_alloc(key_data, key_len); // Combine 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 associated with . Returns the value removed, or +// Remove the value in associated with . 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); diff --git a/struct/list.c b/struct/list.c index 29784a9..02a7c2d 100644 --- a/struct/list.c +++ b/struct/list.c @@ -10,10 +10,11 @@ #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 matching the return its value. - return (item && item->key == key) ? item->value : DOES_NOT_EXIST; + // If we found an matching the key return its value. + return item != NULL ? item->value : DOES_NOT_EXIST; } -// Insert the , if it doesn't already exist in -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 +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 already exists in , return its value. - if (next != NULL && next->key == key) { + // If a node matching the key already exists in 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 index 0000000..840c6df --- /dev/null +++ b/struct/nstring.c @@ -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 index 0000000..ba0d6ec --- /dev/null +++ b/struct/nstring.h @@ -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 diff --git a/struct/skiplist.c b/struct/skiplist.c index df8e98a..0b49fd4 100644 --- a/struct/skiplist.c +++ b/struct/skiplist.c @@ -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 matching the return its value. - return (item && item->key == key) ? item->value : DOES_NOT_EXIST; + return found ? item->value : DOES_NOT_EXIST; } // Insert the if it doesn't already exist in -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 already exists in , 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 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 { diff --git a/test/ll_test.c b/test/ll_test.c index e7c9337..54ad96b 100644 --- a/test/ll_test.c +++ b/test/ll_test.c @@ -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(); diff --git a/test/sl_test.c b/test/sl_test.c index 9fc6466..c06becb 100644 --- a/test/sl_test.c +++ b/test/sl_test.c @@ -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 4640dd6..bf4dc21 100644 --- 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 -- 2.40.0