+
+ uint64_t value = update->value;
+
+ // collect some garbage
+ update_t *last = update;
+ update_t *next = update->next;
+ uint64_t min_active = 0;
+ if (IS_TAGGED(next, TAG2)) {
+ next = (update_t *)STRIP_TAG(next, TAG2);
+ min_active = (uint64_t)sl_min_key(active_);
+ if (next->version < min_active) {
+
+ // Skip over aborted versions to verify the chain of updates is old enough for collection
+ update_t *temp = next;
+ while (temp->version == ABORTED_VERSION) {
+ assert(!IS_TAGGED(temp->version, TAG1));
+ update_t *temp = next->next;
+ if (!IS_TAGGED(temp, TAG2))
+ break;
+ temp = (update_t *)STRIP_TAG(temp, TAG2);
+ if (temp->version >= min_active)
+ return value;
+ temp = temp->next;
+ }
+
+ // collect <next> and all the update records following it
+ do {
+ next = SYNC_SWAP(&update->next, NULL);
+
+ // if we find ourself in a race just back off and let the other thread take care of it
+ if (next == NULL)
+ return value;
+
+ update = next;
+ next = next->next;
+ nbd_free(update);
+ } while (IS_TAGGED(next, TAG2));
+ }
+ }
+
+ // If there is one item left and it is visible by all active transactions we can merge it into the map itself.
+ // There is no need for an update record.
+ if (next == NULL && last == (update_t *)STRIP_TAG(newest_update, TAG2)) {
+ if (min_active == UNDETERMINED_VERSION) {
+ min_active = (uint64_t)sl_min_key(active_);
+ }
+ if (last->version <= min_active) {
+ if (map_cas(txn->map, key, TAG_VALUE(last, TAG2), value) == TAG_VALUE(last, TAG2)) {
+ nbd_defer_free(last);
+ }
+ }
+ }
+
+ return value;