-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);
- }
-}
-