X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=struct%2Fskiplist.c;h=0b49fd4937b9c2170ed4c7d20816d51c691bbcea;hp=5e9066c280165b078ddc3cbd5a7613d442df4502;hb=53d171373819e921da8f8648eea236a08ff6a702;hpb=052506ff082f134f00834f666653819e18d9bddf diff --git a/struct/skiplist.c b/struct/skiplist.c index 5e9066c..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,15 +28,15 @@ #define MAX_LEVEL 31 typedef struct node { - uint64_t key; + nstring_t *key; uint64_t value; int top_level; struct node *next[]; } node_t; -typedef struct skiplist { +struct sl { node_t *head; -} skiplist_t; +}; static int random_level (void) { unsigned r = nbd_rand(); @@ -50,32 +51,34 @@ 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; } skiplist_t *sl_alloc (void) { - skiplist_t *skiplist = (skiplist_t *)nbd_malloc(sizeof(skiplist_t)); - skiplist->head = node_alloc(MAX_LEVEL, 0, 0); - memset(skiplist->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *)); - return skiplist; + skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t)); + 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 *skiplist, uint64_t key, int help_remove) { - node_t *pred = skiplist->head; +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 skiplist (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 // Optimization for small lists. No need to traverse empty higher levels. - assert(MAX_LEVEL > 2); - int start_level = 2; + start_level = 2; while (pred->next[start_level+1] != NULL) { start_level += start_level - 1; if (EXPECT_FALSE(start_level >= MAX_LEVEL)) { @@ -86,24 +89,25 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *skipli if (EXPECT_FALSE(start_level < n)) { start_level = n; } +#endif - // Traverse the levels of the skiplist from the top level to the bottom + // Traverse the levels of from the top level to the bottom for (int level = start_level; level >= 0; --level) { TRACE("s3", "find_preds: level %llu", level, 0); 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, skiplist, 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)) @@ -112,7 +116,7 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *skipli 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); @@ -127,7 +131,7 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *skipli } 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, skiplist, 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; @@ -139,7 +143,11 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *skipli 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; } @@ -154,39 +162,41 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *skipli if (n == -1 && item != NULL) { assert(preds != NULL); for (int level = start_level + 1; level <= item->top_level; ++level) { - preds[level] = skiplist->head; + preds[level] = sl->head; } } return item; } // Fast find that does not help unlink partially removed nodes and does not return the node's predecessors. -uint64_t sl_lookup (skiplist_t *skiplist, uint64_t key) { - TRACE("s3", "sl_lookup: searching for key %p in skiplist %p", key, skiplist); - node_t *item = find_preds(NULL, 0, skiplist, key, FALSE); +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); + 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 the -uint64_t sl_add (skiplist_t *skiplist, uint64_t key, uint64_t value) { +// Insert the if it doesn't already exist in +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, skiplist, 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 the skiplist, return its value. - if (next != NULL && next->key == key) { + // If a node matching already exists in , return its value. + 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) { @@ -203,7 +213,7 @@ uint64_t sl_add (skiplist_t *skiplist, uint64_t key, uint64_t value) { } while (1); - // Insert into the skiplist from the bottom level up. + // Insert into from the bottom level up. for (int level = 1; level <= item->top_level; ++level) { do { node_t *pred; @@ -213,9 +223,10 @@ uint64_t sl_add (skiplist_t *skiplist, 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, skiplist, key, TRUE); + int found; + find_preds(&found, preds, item->top_level, sl, key_data, key_len, TRUE); } while (1); do { @@ -242,16 +253,17 @@ uint64_t sl_add (skiplist_t *skiplist, uint64_t key, uint64_t value) { return value; } -uint64_t sl_remove (skiplist_t *skiplist, uint64_t key) { - TRACE("s3", "sl_remove: removing item with key %p from skiplist %p", key, skiplist); +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, skiplist, key, TRUE); - if (item == NULL || item->key != key) { - TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the skiplist", 0, 0); + 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; } - // Mark removed at each level of the skiplist from the top down. This must be atomic. If multiple threads + // Mark removed at each level of 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) { @@ -282,7 +294,7 @@ uint64_t sl_remove (skiplist_t *skiplist, uint64_t key) { if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) != item) { TRACE("s3", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other); // By marking the item earlier, we logically removed it. It is safe to leave the item partially - // unlinked. Another thread will finish physically removing it from the skiplist. + // unlinked. Another thread will finish physically removing it from . return value; } --level; @@ -293,9 +305,9 @@ uint64_t sl_remove (skiplist_t *skiplist, uint64_t key) { return value; } -void sl_print (skiplist_t *skiplist) { +void sl_print (skiplist_t *sl) { for (int level = MAX_LEVEL; level >= 0; --level) { - node_t *item = skiplist->head; + node_t *item = sl->head; if (item->next[level] == NULL) continue; printf("(%d) ", level); @@ -309,15 +321,20 @@ void sl_print (skiplist_t *skiplist) { } printf("\n"); - node_t *item = skiplist->head; + node_t *item = sl->head; while (item) { int is_marked = IS_TAGGED(item->next[0]); - printf("%s%p:0x%llx [%d]", is_marked ? "*" : "", item, item->key, item->top_level); + printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)ns_data(item->key)); + if (item != sl->head) { + printf("[%d]", item->top_level); + } else { + printf("[*]"); + } for (int level = 1; level <= item->top_level; ++level) { node_t *next = (node_t *)STRIP_TAG(item->next[level]); is_marked = IS_TAGGED(item->next[0]); printf(" %p%s", next, is_marked ? "*" : ""); - if (item == skiplist->head && item->next[level] == NULL) + if (item == sl->head && item->next[level] == NULL) break; } printf("\n"); @@ -325,93 +342,3 @@ void sl_print (skiplist_t *skiplist) { item = (node_t *)STRIP_TAG(item->next[0]); } } - -#ifdef MAKE_skiplist_test -#include -#include -#include - -#include "runtime.h" - -#define NUM_ITERATIONS 10000000 - -static volatile int wait_; -static long num_threads_; -static skiplist_t *sl_; - -void *worker (void *arg) { - - // Wait for all the worker threads to be ready. - SYNC_ADD(&wait_, -1); - do {} while (wait_); - - for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { - unsigned r = nbd_rand(); - int key = (r & 0xF) + 1; - if (r & (1 << 8)) { - sl_add(sl_, key, 1); - } else { - sl_remove(sl_, key); - } - - rcu_update(); - } - - return NULL; -} - -int main (int argc, char **argv) { - nbd_init(); - lwt_set_trace_level("s3"); - - char* program_name = argv[0]; - pthread_t thread[MAX_NUM_THREADS]; - - if (argc > 2) { - fprintf(stderr, "Usage: %s num_threads\n", program_name); - return -1; - } - - num_threads_ = 2; - if (argc == 2) - { - errno = 0; - num_threads_ = strtol(argv[1], NULL, 10); - if (errno) { - fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name); - return -1; - } - if (num_threads_ <= 0) { - fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name); - return -1; - } - if (num_threads_ > MAX_NUM_THREADS) { - fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS); - return -1; - } - } - - sl_ = sl_alloc(); - - struct timeval tv1, tv2; - gettimeofday(&tv1, NULL); - - wait_ = num_threads_; - - for (int i = 0; i < num_threads_; ++i) { - int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i); - if (rc != 0) { perror("pthread_create"); return rc; } - } - - for (int i = 0; i < num_threads_; ++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; - sl_print(sl_); - printf("Th:%ld Time:%dms\n", num_threads_, ms); - - return 0; -} -#endif//skiplist_test