- node_t *item = list->head->next; // head is never removed
- TRACE("l3", "find_pred_and_item: searching for key %llu in list (head is %p)", key, pred);
-#ifndef NDEBUG
- int count = 0;
-#endif
- do {
- // skip removed items
- node_t *other, *next = item->next;
- TRACE("l3", "find_pred_and_item: visiting item %p (next is %p)", item, next);
- while (EXPECT_FALSE(IS_MARKED(next))) {
-
- // assist in unlinking partially removed items
- if ((other = SYNC_CAS(&pred->next, item, CLEAR_MARK(next))) != item)
- {
- TRACE("l3", "find_pred_and_item: failed to unlink item from pred %p, pred's next pointer was changed to %p", pred, other);
- return find_pred_and_item(pred_ptr, item_ptr, list, key); // retry
+ node_t *item = pred->next;
+ TRACE("l3", "find_pred: searching for key %p in list (head is %p)", key, pred);
+
+ while (item != NULL) {
+ node_t *next = item->next;
+ TRACE("l3", "find_pred: visiting item %p (next %p)", item, next);
+ TRACE("l3", "find_pred: key %p", item->key, item->value);
+
+ // Marked items are logically removed, but not unlinked yet.
+ while (EXPECT_FALSE(IS_TAGGED(next))) {
+
+ // Skip over partially removed items.
+ if (!help_remove) {
+ item = (node_t *)STRIP_TAG(item->next);
+ if (EXPECT_FALSE(item == NULL))
+ break;
+ next = item->next;
+ continue;