+map_key_t sl_min_key (skiplist_t *sl) {
+ node_t *item = GET_NODE(sl->head->next[0]);
+ while (item != NULL) {
+ markable_t next = item->next[0];
+ if (!HAS_MARK(next))
+ return item->key;
+ item = STRIP_MARK(next);
+ }
+ return DOES_NOT_EXIST;
+}
+
+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);