+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 <sl> from the top level to the bottom
+ for (int level = sl->high_water; level >= 0; --level) {
+ markable_t next = pred->next[level];
+ if (next == DOES_NOT_EXIST)
+ continue;
+ TRACE("s3", "sl_unlink: traversing level %p starting at %p", level, pred);
+ if (EXPECT_FALSE(HAS_MARK(next))) {
+ TRACE("s2", "sl_unlink: lost a race; pred %p is marked for removal (next %p); retry", pred, next);
+ ASSERT(level == pred->top_level || HAS_MARK(pred->next[level+1]));
+ return sl_unlink(sl, key); // retry
+ }
+ item = GET_NODE(next);
+ while (item != NULL) {
+ next = item->next[level];
+
+ while (HAS_MARK(next)) {
+ TRACE("s3", "sl_unlink: found marked item %p (next is %p)", item, next);
+
+ markable_t other = SYNC_CAS(&pred->next[level], item, STRIP_MARK(next));
+ if (other == (markable_t)item) {
+ TRACE("s3", "sl_unlink: unlinked item from pred %p", pred, 0);
+ item = STRIP_MARK(next);
+ } else {
+ TRACE("s3", "sl_unlink: lost race to unlink item, pred %p's link changed to %p", pred, other);
+ if (HAS_MARK(other))
+ return sl_unlink(sl, key); // retry
+ item = GET_NODE(other);
+ }
+ next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
+ }
+
+ if (EXPECT_FALSE(item == NULL)) {
+ TRACE("s3", "sl_unlink: past the last item in the skiplist", 0, 0);
+ break;
+ }
+
+ TRACE("s4", "sl_unlink: visiting item %p (next is %p)", item, next);
+ TRACE("s4", "sl_unlink: key %p val %p", STRIP_MARK(item->key), item->val);
+
+ 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)
+ break;
+
+ pred = item;
+ item = GET_NODE(next);
+ }
+
+ TRACE("s3", "sl_unlink: at pred %p next %p", pred, item);
+ }
+}
+