-
-
Save Amrt1n3zm/25f08d8643bc84359026413497d90a5f to your computer and use it in GitHub Desktop.
assignment1 snippet
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Handles each epoch by receiving an unordered array of proposed transactions, checking each | |
| * transaction for correctness, returning a mutually valid array of accepted transactions, and | |
| * updating the current UTXO pool as appropriate. | |
| */ | |
| public Transaction[] handleTxs(Transaction[] possibleTxs) { | |
| // The side effect is to advance the state of the pool. | |
| // Convert the unordered list into a graph, and perform topological sort | |
| /** Mapping from hash to corresponding transaction. */ | |
| HashMap<byte[], Transaction> T = new HashMap<byte[], Transaction>(); | |
| /** Mapping from txHash to all the claimed transaction. */ | |
| HashMap<byte[], ArrayList<byte[]>> M = new HashMap<byte[], ArrayList<byte[]>>(); | |
| ArrayList<Transaction> validTxs = new ArrayList<Transaction>(); | |
| for (Transaction tx: possibleTxs) { | |
| byte[] hash = tx.getHash(); | |
| T.put(hash, tx); | |
| for (Transaction.Input in : tx.getInputs()) { | |
| if (!M.containsKey(hash)) { | |
| M.put(tx.getHash(), new ArrayList<byte[]>()); | |
| } | |
| // NOTE: only add txHash within possibleTxs | |
| if (T.containsKey(in.prevTxHash)) { | |
| M.get(hash).add(in.prevTxHash); | |
| } | |
| } | |
| } | |
| // NOTE: This won't return the maximal number of transactions. | |
| // Process transaction in topological order, when there are two choices, pick one | |
| // according to the incoming order. | |
| while (M.size() != 0) { | |
| // TODO: This is just to mute compiler warnings for uninitialized variable. | |
| byte[] selectedHash = possibleTxs[0].getHash(); | |
| Transaction selectedTx = possibleTxs[0]; | |
| for (byte[] hash : M.keySet()) { | |
| // Found the first hash with no reference in this transaction batch. | |
| if (M.get(hash).size() == 0) { | |
| selectedHash = hash; | |
| selectedTx = T.get(hash); | |
| break; | |
| } | |
| } | |
| if (isValidTx(selectedTx)) { | |
| validTxs.add(selectedTx); | |
| pool = nextPool(selectedTx); | |
| } | |
| // remove selectedrent hash | |
| M.remove(selectedHash); | |
| // remove all the reference to selectedrent hash | |
| for (byte[] hash : M.keySet()) { | |
| M.get(hash).remove(hash); | |
| } | |
| } | |
| return validTxs.toArray(new Transaction[validTxs.size()]); | |
| } | |
| private UTXOPool nextPool(Transaction tx) { | |
| UTXOPool newpool = new UTXOPool(pool); | |
| for (int i = 0; i < tx.numInputs(); i++) { | |
| Transaction.Input in = tx.getInput(i); | |
| newpool.removeUTXO(new UTXO(in.prevTxHash, in.outputIndex)); | |
| } | |
| for (int i = 0; i < tx.numOutputs(); i++) { | |
| Transaction.Output out = tx.getOutput(i); | |
| newpool.addUTXO(new UTXO(tx.getHash(), i), out); | |
| } | |
| return newpool; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment