+
+ if (update == NULL) {
+ TRACE("x1", "txn_map_get: key does not exist in map", key, 0);
+ return DOES_NOT_EXIST;
+ }
+
+ map_val_t value = update->value;
+ TRACE("x1", "txn_map_get: key found returning value %p", value, 0);
+
+ // collect some garbage
+ version_t min_active_version = UNDETERMINED_VERSION;
+ update_t *next_update = NULL;
+ if (IS_TAGGED(update->next, TAG2)) {
+ next_update = VAL_TO_PTR(update->next);
+
+ // If <next_update> (and all update records following it [execpt if it is aborted]) is old enough
+ // that it is not visible to any active transaction we can safely free it.
+ min_active_version = (version_t)sl_min_key(active_);
+ if (next_update->version < min_active_version) {
+
+ // If the <next_update> is aborted, skip over it to look for more recent ones that may follow
+ update_t *temp = next_update;
+ while (temp->version == ABORTED_VERSION) {
+ assert(!IS_TAGGED(temp->version, TAG1));
+ map_val_t next = temp->next;
+ if (!IS_TAGGED(next, TAG2))
+ break;
+
+ // Bail out of garbage collection if we find a record that might still be accessed by an
+ // ongoing transaction.
+ if (VAL_TO_PTR(next)->version >= min_active_version)
+ return value;
+
+ temp = VAL_TO_PTR(next);
+ }
+
+ // free the next update record and all the ones following it
+ temp = next_update;
+ map_val_t next;
+ do {
+ next = SYNC_SWAP(&temp->next, DOES_NOT_EXIST);
+
+ // if we find ourself in a race just back off and let the other thread take care of it
+ if (next == DOES_NOT_EXIST)
+ return value;
+
+ nbd_free(temp);
+
+ temp = VAL_TO_PTR(next);
+
+ } 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_update == NULL && val == newest_val) {
+ if (min_active_version == UNDETERMINED_VERSION) {
+ min_active_version = (version_t)sl_min_key(active_);
+ }
+ if (update->version <= min_active_version) {
+ if (map_cas(txn->map, key, TAG_VALUE(val, TAG2), value) == TAG_VALUE(val, TAG2)) {
+ rcu_defer_free(update);
+ }
+ }
+ }
+
+ return value;