- 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);
+ TRACE("s3", "sl_add: attempting to insert item between %p and %p", pred, next);
+ node_t *other = SYNC_CAS(&pred->next[level], next, new_item);
+ if (other == next) {
+ TRACE("s3", "sl_add: successfully inserted item %p at level %llu", new_item, level);
+ break; // success
+ }
+ TRACE("s3", "sl_add: failed to change pred's link: expected %p found %p", next, other);
+ find_preds(preds, nexts, new_item->top_level, sl, key_data, key_len, TRUE);
+ pred = preds[level];
+ next = nexts[level];