-uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expectation, uint64_t new_val) {
- TRACE("s1", "sl_cas: key %p skiplist %p", key_data, sl);
+static map_val_t update_item (node_t *item, map_val_t expectation, map_val_t new_val) {
+ map_val_t old_val = item->val;
+
+ // If the item's value is DOES_NOT_EXIST it means another thread removed the node out from under us.
+ if (EXPECT_FALSE(old_val == DOES_NOT_EXIST)) {
+ TRACE("s2", "update_item: lost a race to another thread removing the item. retry", 0, 0);
+ return DOES_NOT_EXIST; // retry
+ }
+
+ if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) {
+ TRACE("s1", "update_item: the expectation was not met; the skiplist was not changed", 0, 0);
+ return old_val; // failure
+ }
+
+ // Use a CAS and not a SWAP. If the CAS fails it means another thread removed the node or updated its
+ // value. If another thread removed the node but it is not unlinked yet and we used a SWAP, we could
+ // replace DOES_NOT_EXIST with our value. Then another thread that is updating the value could think it
+ // succeeded and return our value even though it should return DOES_NOT_EXIST.
+ if (old_val == SYNC_CAS(&item->val, old_val, new_val)) {
+ TRACE("s1", "update_item: the CAS succeeded. updated the value of the item", 0, 0);
+ return old_val; // success
+ }
+ TRACE("s2", "update_item: lost a race. the CAS failed. another thread changed the item's value", 0, 0);
+
+ // retry
+ return update_item(item, expectation, new_val); // tail call
+}
+
+map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_t new_val) {
+ TRACE("s1", "sl_cas: key %p skiplist %p", key, sl);