+// Validate the updates for <key>. Validation fails if there is a write-write conflict. That is if after our
+// read version another transaction committed a change to an entry we are also trying to change.
+//
+// If we encounter a potential conflict with a transaction that is in the process of validating, we help it
+// complete validating. It must be finished before we can decide to rollback or commit.
+//
+static txn_state_e validate_key (txn_t *txn, map_key_t key) {
+ assert(txn->state != TXN_RUNNING);
+
+ map_val_t val = map_get(txn->map, key);
+ update_t *update = NULL;
+ for (; val != DOES_NOT_EXIST; val = update->next) {
+
+ // If the update or its version is not tagged it means the update is committed.
+ //
+ // We can stop at the first committed record we find that is at least as old as our read version. All
+ // the other committed records following it will be older. And all the uncommitted records following it
+ // will eventually conflict with it and abort.
+ if (!IS_TAGGED(val, TAG2))
+ return TXN_VALIDATED;
+ update = (update_t *)STRIP_TAG(val, TAG2);
+ if (!IS_TAGGED(update->version, TAG1))
+ return (update->version <= txn->rv) ? TXN_VALIDATED : TXN_ABORTED;
+
+ // If the update's version is tagged then either the update was aborted or the the version number is
+ // actually a pointer to a running transaction's txn_t.
+
+ // Skip aborted transactions.
+ if (EXPECT_FALSE(update->version == ABORTED_VERSION))
+ continue;
+
+ // The update's transaction is still in progress. Access its txn_t.
+ txn_t *writer = (txn_t *)STRIP_TAG(update->version, TAG1);
+ if (writer == txn)
+ continue; // Skip our own updates.
+ txn_state_e writer_state = writer->state;
+
+ // Any running transaction will only be able to acquire a wv greater than ours. A transaction changes its
+ // state to validating before aquiring a wv. We can ignore an unvalidated transaction if its version is
+ // greater than ours. See next comment below for why.
+ if (writer_state == TXN_RUNNING)
+ continue;
+
+ // If <writer> has a later version than us we can safely ignore its updates. It will not commit until
+ // we have completed validation (in order to remain non-blocking it will help us validate if necessary).
+ // This protocol ensures a deterministic resolution to every conflict and avoids infinite ping-ponging
+ // between validating two conflicting transactions.
+ if (writer_state == TXN_VALIDATING) {
+ if (writer->wv > txn->wv)