- // First insert <new_item> into the bottom level.
- TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
- void *new_key = (sl->key_type == NULL) ? key : sl->key_type->clone(key);
- new_item = node_alloc(n, new_key, new_val);
- node_t *pred = preds[0];
- node_t *next = new_item->next[0] = nexts[0];
- for (int level = 1; level <= new_item->top_level; ++level) {
- new_item->next[level] = nexts[level];
- }
- node_t *other = SYNC_CAS(&pred->next[0], next, new_item);
- if (other == next) {
- TRACE("s3", "sl_cas: successfully inserted item %p at level 0", new_item, 0);
- break; // success
- }
- TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
- if (sl->key_type != NULL) {
- nbd_free(new_key);
- }
- nbd_free(new_item);
- continue;
+ // If we lose a race with a thread removing the item we tried to update then we have to retry.
+ return sl_cas(sl, key, expectation, new_val); // tail call
+ }
+
+ if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {
+ 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 <key> to already exist
+ }
+
+ // Create a new node and insert it into the skiplist.
+ TRACE("s3", "sl_cas: attempting to insert a new item between %p and %p", preds[0], nexts[0]);
+ map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);
+ new_item = node_alloc(n, new_key, new_val);
+
+ // Set <new_item>'s next pointers to their proper values
+ markable_t next = new_item->next[0] = (markable_t)nexts[0];
+ for (int level = 1; level < new_item->num_levels; ++level) {
+ new_item->next[level] = (markable_t)nexts[level];
+ }
+
+ // Link <new_item> into <sl> from the bottom level up. After <new_item> is inserted into the bottom level
+ // it is officially part of the skiplist.
+ node_t *pred = preds[0];
+ markable_t other = SYNC_CAS(&pred->next[0], next, (markable_t)new_item);
+ if (other != next) {
+ TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
+
+ // Lost a race to another thread modifying the skiplist. Free the new item we allocated and retry.
+ if (sl->key_type != NULL) {
+ nbd_free((void *)new_key);