- node_t *pred;
- node_t *next;
- do {
- pred = preds[level];
- next = pred->next[level];
- if (next == NULL) // item goes at the end of the list
- break;
- if (!IS_TAGGED(next) && ns_cmp_raw(next->key, key_data, key_len) > 0) // pred's link changed
- break;
- int found;
- find_preds(&found, preds, item->top_level, sl, key_data, key_len, TRUE);
- } while (1);
-
- do {
- // There in no need to continue linking in the item if another thread removed it.
- node_t *old_next = ((volatile node_t *)item)->next[level];
- if (IS_TAGGED(old_next))
- return DOES_NOT_EXIST; // success
-
- // Use a CAS so we to not inadvertantly remove a mark another thread placed on the item.
- if (next == old_next || SYNC_CAS(&item->next[level], old_next, next) == old_next)
- break;
- } while (1);
-