X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=struct%2Fskiplist.c;h=f7cdf332cc8793724b2a02821df86b93e684220a;hp=df8e98a75ea6c2bafe77dec7ec6ddae1c50f16c9;hb=bfb84a32cb183c37bf4c7a4522f65a1173dcecd4;hpb=b21e1c182a2e469240d2b1cbbda37f2dfeb880d9 diff --git a/struct/skiplist.c b/struct/skiplist.c index df8e98a..f7cdf33 100644 --- a/struct/skiplist.c +++ b/struct/skiplist.c @@ -19,15 +19,16 @@ #include "common.h" #include "runtime.h" #include "struct.h" +#include "nstring.h" #include "mem.h" #include "tls.h" // Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list -// in list.c +// (in list.c). #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,15 @@ 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; + // If is -1 it indicates 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->value = value; item->top_level = level; return item; @@ -63,16 +67,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 (node_t **preds, node_t **succs, 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); + int x; int start_level = MAX_LEVEL; #if MAX_LEVEL > 2 // Optimization for small lists. No need to traverse empty higher levels. @@ -95,17 +99,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(preds, succs, 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); + TRACE("s3", "find_preds: key %p", STRIP_TAG(item->key), item->value); - // 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 +118,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 +133,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(preds, succs, n, sl, key_data, key_len, help_remove); // retry item = other; if (EXPECT_FALSE(item == NULL)) break; @@ -141,7 +145,10 @@ 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) { + x = (IS_TAGGED(item->key)) + ? (STRIP_TAG(item->key) - (uint64_t)key_data) + : ns_cmp_raw(item->key, key_data, key_len); + if (x >= 0) { TRACE("s3", "find_preds: found pred %p item %p", pred, item); break; } @@ -149,53 +156,59 @@ static node_t *find_preds (node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, ui pred = item; item = next; } - if (preds != NULL) { - preds[level] = pred; + + // The cast to unsigned is for the case when n is -1. + if ((unsigned)level <= (unsigned)n) { + if (preds != NULL) { + preds[level] = pred; + } + if (succs != NULL) { + succs[level] = item; + } } } if (n == -1 && item != NULL) { - assert(preds != NULL); for (int level = start_level + 1; level <= item->top_level; ++level) { preds[level] = sl->head; } } - return item; + return x == 0 ? item : 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, 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); + node_t *item = find_preds(NULL, 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 item != NULL ? 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) { - TRACE("s3", "sl_add: inserting key %p value %p", key, 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_data, value); node_t *preds[MAX_LEVEL+1]; + node_t *nexts[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); + node_t *next = find_preds(preds, nexts, n, sl, key_data, key_len, TRUE); // If a node matching already exists in , return its value. - if (next != NULL && next->key == key) { - TRACE("s3", "sl_add: there is already an item %p (value %p) with the same key", next, next->value); + if (next != NULL) { + TRACE("s3", "sl_add: there is already an item %p (value %p) with the same key", nexts[0], nexts[0]->value); if (EXPECT_FALSE(item != NULL)) { nbd_free(item); } - return next->value; + return nexts[0]->value; } // First insert into the bottom level. - if (EXPECT_TRUE(item == NULL)) { item = node_alloc(n, key, value); } - TRACE("s3", "sl_add: attempting to insert item between %p and %p", preds[0], next); - item->next[0] = next; + if (EXPECT_TRUE(item == NULL)) { item = node_alloc(n, key_data, key_len, value); } + node_t *pred = preds[0]; + item->next[0] = next = nexts[0]; + TRACE("s3", "sl_add: attempting to insert item between %p and %p", pred, next); for (int level = 1; level <= item->top_level; ++level) { - node_t *pred = preds[level]; - item->next[level] = pred->next[level]; + item->next[level] = nexts[level]; } - node_t *pred = preds[0]; node_t *other = SYNC_CAS(&pred->next[0], next, item); if (other == next) { TRACE("s3", "sl_add: successfully inserted item %p at level 0", item, 0); @@ -207,30 +220,9 @@ uint64_t sl_add (skiplist_t *sl, uint64_t key, uint64_t value) { // Insert into from the bottom level up. for (int level = 1; level <= item->top_level; ++level) { + node_t *pred = preds[level]; + node_t *next = nexts[level]; do { - node_t *pred; - node_t *next; - do { - pred = preds[level]; - 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 - break; - find_preds(preds, item->top_level, sl, key, TRUE); - } while (1); - - do { - // There in no need to continue linking in the item if another thread removed it. - node_t *old_next = ((volatile node_t *)item)->next[level]; - if (IS_TAGGED(old_next)) - return DOES_NOT_EXIST; // success - - // Use a CAS so we to not inadvertantly remove a mark another thread placed on the item. - if (next == old_next || SYNC_CAS(&item->next[level], old_next, next) == old_next) - break; - } while (1); - TRACE("s3", "sl_add: attempting to insert item between %p and %p", pred, next); node_t *other = SYNC_CAS(&pred->next[level], next, item); if (other == next) { @@ -238,17 +230,31 @@ uint64_t sl_add (skiplist_t *sl, uint64_t key, uint64_t value) { break; // success } TRACE("s3", "sl_add: failed to change pred's link: expected %p found %p", next, other); + find_preds(preds, nexts, item->top_level, sl, key_data, key_len, TRUE); + pred = preds[level]; + next = nexts[level]; + // Update 's next pointer + do { + // There in no need to continue linking in the item if another thread removed it. + node_t *old_next = ((volatile node_t *)item)->next[level]; + if (IS_TAGGED(old_next)) + return value; + + // Use a CAS so we to not inadvertantly stomp on a mark another thread placed on the item. + if (old_next == next || SYNC_CAS(&item->next[level], old_next, next) == old_next) + break; + } while (1); } while (1); } 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); 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(preds, NULL, -1, sl, key_data, key_len, TRUE); + if (item == NULL) { 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 +320,12 @@ 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); + + 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 *)ns_data(item->key)); + } if (item != sl->head) { printf("[%d]", item->top_level); } else {