X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=map%2Funsafe_skiplist.c;fp=map%2Funsafe_skiplist.c;h=596dcde423da48c69399a7e02bb60c562ad5e681;hp=f54e10d53d7b55edf175641b093a161696a3b9ba;hb=86fd9c8abfbacea2902b4fe42a8a4664b2a531cf;hpb=778b8c8ca708b082a1192acfb114a6751b2ad7c9 diff --git a/map/unsafe_skiplist.c b/map/unsafe_skiplist.c index f54e10d..596dcde 100644 --- a/map/unsafe_skiplist.c +++ b/map/unsafe_skiplist.c @@ -13,12 +13,12 @@ #include "runtime.h" #include "mem.h" -#define MAX_LEVEL 31 +#define MAX_LEVELS 32 typedef struct node { map_key_t key; map_val_t val; - int top_level; + int num_levels; struct node *next[1]; } node_t; @@ -32,31 +32,38 @@ struct sl { int high_water; // max level of any item in the list }; -static int random_level (void) { +static int random_levels (skiplist_t *sl) { unsigned r = nbd_rand(); - int n = __builtin_ctz(r) / 2; - if (n > MAX_LEVEL) { n = MAX_LEVEL; } - return n; + int z = __builtin_ctz(r); + int levels = (int)(z / 1.5); + if (levels == 0) + return 1; + if (levels > sl->high_water) { + levels = SYNC_ADD(&sl->high_water, 1); + TRACE("s2", "random_levels: increased high water mark to %lld", sl->high_water, 0); + } + if (levels > MAX_LEVELS) { levels = MAX_LEVELS; } + return levels; } -static node_t *node_alloc (int level, map_key_t key, map_val_t val) { - assert(level >= 0 && level <= MAX_LEVEL); - size_t sz = sizeof(node_t) + level * sizeof(node_t *); +static node_t *node_alloc (int num_levels, map_key_t key, map_val_t val) { + assert(num_levels > 0 && num_levels <= MAX_LEVELS); + size_t sz = sizeof(node_t) + (num_levels - 1) * sizeof(node_t *); node_t *item = (node_t *)nbd_malloc(sz); memset(item, 0, sz); item->key = key; item->val = val; - item->top_level = level; - TRACE("s2", "node_alloc: new node %p (%llu levels)", item, level); + item->num_levels = num_levels; + TRACE("s2", "node_alloc: new node %p (%llu levels)", item, num_levels); return item; } skiplist_t *sl_alloc (const datatype_t *key_type) { skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t)); sl->key_type = key_type; - sl->high_water = 0; - sl->head = node_alloc(MAX_LEVEL, 0, 0); - memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *)); + sl->high_water = 1; + sl->head = node_alloc(MAX_LEVELS, 0, 0); + memset(sl->head->next, 0, MAX_LEVELS * sizeof(skiplist_t *)); return sl; } @@ -82,20 +89,16 @@ size_t sl_count (skiplist_t *sl) { return count; } -static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, map_key_t key, int help_remove) { +static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, map_key_t key, int unlink) { node_t *pred = sl->head; node_t *item = NULL; TRACE("s2", "find_preds: searching for key %p in skiplist (head is %p)", key, pred); int d = 0; - int start_level = sl->high_water; - if (EXPECT_FALSE(start_level < n)) { - start_level = n; - } // Traverse the levels of from the top level to the bottom - for (int level = start_level; level >= 0; --level) { + for (int level = sl->high_water - 1; level >= 0; --level) { node_t *next = pred->next[level]; - if (next == DOES_NOT_EXIST && level > n) + if (next == DOES_NOT_EXIST && level >= n) continue; TRACE("s3", "find_preds: traversing level %p starting at %p", level, pred); item = next; @@ -108,8 +111,15 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl d = sl->key_type->cmp((void *)item->key, (void *)key); } - if (d >= 0) + if (d >= 0) { + if (d == 0 && unlink) { + pred->next[level] = next; + TRACE("s3", "find_preds: unlinked item from pred %p", pred, 0); + item = next; + next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST; + } break; + } pred = item; item = next; @@ -117,8 +127,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl TRACE("s3", "find_preds: found pred %p next %p", pred, item); - // The cast to unsigned is for the case when n is -1. - if ((unsigned)level <= (unsigned)n) { + if (level < n) { if (preds != NULL) { preds[level] = pred; } @@ -128,14 +137,6 @@ 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 && preds != NULL) { - assert(item->top_level <= MAX_LEVEL); - 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; @@ -144,46 +145,6 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl return NULL; } -static void sl_unlink (skiplist_t *sl, map_key_t key) { - node_t *pred = sl->head; - node_t *item = NULL; - TRACE("s2", "sl_unlink: unlinking marked item with key %p", key, 0); - int d = 0; - - // Traverse the levels of - for (int level = sl->high_water; level >= 0; --level) { - node_t *next = pred->next[level]; - if (next == DOES_NOT_EXIST) - continue; - TRACE("s3", "sl_unlink: traversing level %p starting at %p", level, pred); - item = next; - while (item != NULL) { - next = item->next[level]; - - if (EXPECT_TRUE(sl->key_type == NULL)) { - d = item->key - key; - } else { - d = sl->key_type->cmp((void *)item->key, (void *)key); - } - - if (d == 0) { - pred->next[level] = next; - TRACE("s3", "sl_unlink: unlinked item from pred %p", pred, 0); - item = next; - next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST; - break; - } - if (d > 0) - break; - - pred = item; - item = next; - } - - TRACE("s3", "sl_unlink: at pred %p next %p", pred, item); - } -} - // Fast find that does not return the node's predecessors. map_val_t sl_lookup (skiplist_t *sl, map_key_t key) { TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key, sl); @@ -195,7 +156,7 @@ map_val_t sl_lookup (skiplist_t *sl, map_key_t key) { return val; } - TRACE("l1", "sl_lookup: no item in the skiplist matched the key", 0, 0); + TRACE("s1", "sl_lookup: no item in the skiplist matched the key", 0, 0); return DOES_NOT_EXIST; } @@ -211,19 +172,18 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_ TRACE("s1", "sl_cas: expectation %p new value %p", expectation, new_val); ASSERT((int64_t)new_val > 0); - node_t *preds[MAX_LEVEL+1]; - node_t *nexts[MAX_LEVEL+1]; + node_t *preds[MAX_LEVELS]; + node_t *nexts[MAX_LEVELS]; node_t *new_item = NULL; - int n = random_level(); - node_t *old_item = find_preds(preds, nexts, n, sl, key, TRUE); + int n = random_levels(sl); + node_t *old_item = find_preds(preds, nexts, n, sl, key, FALSE); // If there is already an item in the skiplist that matches the key just update its value. if (old_item != NULL) { map_val_t old_val = old_item->val; if (expectation == CAS_EXPECT_DOES_NOT_EXIST || (expectation != CAS_EXPECT_WHATEVER && expectation != CAS_EXPECT_EXISTS && expectation != old_val)) { - TRACE("s1", "update_item: found an item %p in the skiplist that matched the key. the expectation was " - "not met, the skiplist was not changed", item, old_val); + TRACE("s1", "sl_cas: the expectation was not met; the skiplist was not changed", 0, 0); return old_val; } old_item->val = new_val; @@ -231,7 +191,7 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_ } if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) { - TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0); + TRACE("s1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0); return DOES_NOT_EXIST; // failure, the caller expected an item for the to already exist } @@ -239,19 +199,15 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_ // Create a new node and insert it into the skiplist. map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key); - if (n > sl->high_water) { - n = ++sl->high_water; - TRACE("s2", "sl_cas: incremented high water mark to %p", sl->high_water, 0); - } new_item = node_alloc(n, new_key, new_val); // Set 's next pointers to their proper values - for (int level = 0; level <= new_item->top_level; ++level) { + for (int level = 0; level < new_item->num_levels; ++level) { new_item->next[level] = nexts[level]; } // Link into - for (int level = 0; level <= new_item->top_level; ++level) { + for (int level = 0; level < new_item->num_levels; ++level) { preds[level]->next[level] = new_item; } @@ -260,8 +216,8 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_ map_val_t sl_remove (skiplist_t *sl, map_key_t 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, TRUE); + node_t *preds[MAX_LEVELS]; + node_t *item = find_preds(preds, NULL, sl->high_water, sl, key, FALSE); 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; @@ -269,7 +225,7 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) { map_val_t val = item->val; // unlink the item - sl_unlink(sl, key); + find_preds(NULL, NULL, 0, sl, key, TRUE); // free the node if (sl->key_type != NULL) { @@ -283,7 +239,7 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t key) { void sl_print (skiplist_t *sl) { printf("high water: %d levels\n", sl->high_water); - for (int level = MAX_LEVEL; level >= 0; --level) { + for (int level = MAX_LEVELS - 1; level >= 0; --level) { node_t *item = sl->head; if (item->next[level] == DOES_NOT_EXIST) continue; @@ -306,11 +262,11 @@ void sl_print (skiplist_t *sl) { while (item) { printf("%p:0x%llx ", item, (uint64_t)item->key); if (item != sl->head) { - printf("[%d]", item->top_level); + printf("[%d]", item->num_levels); } else { printf("[HEAD]"); } - for (int level = 1; level <= item->top_level; ++level) { + for (int level = 1; level < item->num_levels; ++level) { node_t *next = item->next[level]; printf(" %p", next); if (item == sl->head && item->next[level] == DOES_NOT_EXIST) @@ -329,7 +285,7 @@ void sl_print (skiplist_t *sl) { sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) { sl_iter_t *iter = (sl_iter_t *)nbd_malloc(sizeof(sl_iter_t)); if (key != DOES_NOT_EXIST) { - find_preds(NULL, &iter->next, 0, sl, key, FALSE); + find_preds(NULL, &iter->next, 1, sl, key, FALSE); } else { iter->next = sl->head->next[0]; }