Mercurial > hg > bitcoin
changeset 303:2a6087751e66 draft
efficiently sort transaction dependencies in one pass
git-svn-id: https://bitcoin.svn.sourceforge.net/svnroot/bitcoin/trunk@184 1a98c847-1fd6-4fd8-948a-caf3550aa51b
| author | s_nakamoto <s_nakamoto@1a98c847-1fd6-4fd8-948a-caf3550aa51b> |
|---|---|
| date | Fri, 19 Nov 2010 20:22:46 +0000 |
| parents | 364320c61656 |
| children | 1d96e129710e |
| files | main.cpp net.cpp serialize.h |
| diffstat | 3 files changed, 106 insertions(+), 57 deletions(-) [+] |
line wrap: on
line diff
--- a/main.cpp +++ b/main.cpp @@ -598,6 +598,8 @@ if (i != 0) return false; ptxOld = mapNextTx[outpoint].ptx; + if (ptxOld->IsFinal()) + return false; if (!IsNewerThan(*ptxOld)) return false; for (int i = 0; i < vin.size(); i++) @@ -3031,6 +3033,28 @@ +class COrphan +{ +public: + CTransaction* ptx; + set<uint256> setDependsOn; + double dPriority; + + COrphan(CTransaction* ptxIn) + { + ptx = ptxIn; + dPriority = 0; + } + + void print() const + { + printf("COrphan(hash=%s, dPriority=%.1f)\n", ptx->GetHash().ToString().substr(0,10).c_str(), dPriority); + foreach(uint256 hash, setDependsOn) + printf(" setDependsOn %s\n", hash.ToString().substr(0,10).c_str()); + } +}; + + void BitcoinMiner() { @@ -3098,6 +3122,8 @@ CTxDB txdb("r"); // Priority order to process transactions + list<COrphan> vOrphan; // list memory doesn't move + map<uint256, vector<COrphan*> > mapDependers; multimap<double, CTransaction*> mapPriority; for (map<uint256, CTransaction>::iterator mi = mapTransactions.begin(); mi != mapTransactions.end(); ++mi) { @@ -3105,6 +3131,7 @@ if (tx.IsCoinBase() || !tx.IsFinal()) continue; + COrphan* porphan = NULL; double dPriority = 0; foreach(const CTxIn& txin, tx.vin) { @@ -3112,7 +3139,18 @@ CTransaction txPrev; CTxIndex txindex; if (!txPrev.ReadFromDisk(txdb, txin.prevout, txindex)) + { + // Has to wait for dependencies + if (!porphan) + { + // Use list for automatic deletion + vOrphan.push_back(COrphan(&tx)); + porphan = &vOrphan.back(); + } + mapDependers[txin.prevout.hash].push_back(porphan); + porphan->setDependsOn.insert(txin.prevout.hash); continue; + } int64 nValueIn = txPrev.vout[txin.prevout.n].nValue; // Read block header @@ -3138,55 +3176,66 @@ // Priority is sum(valuein * age) / txsize dPriority /= ::GetSerializeSize(tx, SER_NETWORK); - mapPriority.insert(make_pair(-dPriority, &(*mi).second)); + if (porphan) + porphan->dPriority = dPriority; + else + mapPriority.insert(make_pair(-dPriority, &(*mi).second)); if (fDebug && mapArgs.count("-printpriority")) - printf("priority %-20.1f %s\n%s\n", dPriority, tx.GetHash().ToString().substr(0,10).c_str(), tx.ToString().c_str()); + { + printf("priority %-20.1f %s\n%s", dPriority, tx.GetHash().ToString().substr(0,10).c_str(), tx.ToString().c_str()); + if (porphan) + porphan->print(); + printf("\n"); + } } // Collect transactions into block map<uint256, CTxIndex> mapTestPool; uint64 nBlockSize = 1000; int nBlockSigOps = 100; - bool fFoundSomething = true; - while (fFoundSomething) + while (!mapPriority.empty()) { - fFoundSomething = false; - for (multimap<double, CTransaction*>::iterator mi = mapPriority.begin(); mi != mapPriority.end();) + // Take highest priority transaction off priority queue + CTransaction& tx = *(*mapPriority.begin()).second; + mapPriority.erase(mapPriority.begin()); + + // Size limits + unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK); + if (nBlockSize + nTxSize >= MAX_BLOCK_SIZE_GEN) + continue; + int nTxSigOps = tx.GetSigOpCount(); + if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS) + continue; + + // Transaction fee based on block size + int64 nMinFee = tx.GetMinFee(nBlockSize); + + // Connecting shouldn't fail due to dependency on other memory pool transactions + // because we're already processing them in order of dependency + map<uint256, CTxIndex> mapTestPoolTmp(mapTestPool); + if (!tx.ConnectInputs(txdb, mapTestPoolTmp, CDiskTxPos(1,1,1), pindexPrev, nFees, false, true, nMinFee)) + continue; + swap(mapTestPool, mapTestPoolTmp); + + // Added + pblock->vtx.push_back(tx); + nBlockSize += nTxSize; + nBlockSigOps += nTxSigOps; + + // Add transactions that depend on this one to the priority queue + uint256 hash = tx.GetHash(); + if (mapDependers.count(hash)) { - CTransaction& tx = *(*mi).second; - unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK); - if (nBlockSize + nTxSize >= MAX_BLOCK_SIZE_GEN) + foreach(COrphan* porphan, mapDependers[hash]) { - mapPriority.erase(mi++); - continue; - } - int nTxSigOps = tx.GetSigOpCount(); - if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS) - { - mapPriority.erase(mi++); - continue; + if (!porphan->setDependsOn.empty()) + { + porphan->setDependsOn.erase(hash); + if (porphan->setDependsOn.empty()) + mapPriority.insert(make_pair(-porphan->dPriority, porphan->ptx)); + } } - - // Transaction fee based on block size - int64 nMinFee = tx.GetMinFee(nBlockSize); - - // Connecting can fail due to dependency on other memory pool transactions - // that aren't in the block yet, so keep trying in later passes - map<uint256, CTxIndex> mapTestPoolTmp(mapTestPool); - if (!tx.ConnectInputs(txdb, mapTestPoolTmp, CDiskTxPos(1,1,1), pindexPrev, nFees, false, true, nMinFee)) - { - mi++; - continue; - } - swap(mapTestPool, mapTestPoolTmp); - - // Added - pblock->vtx.push_back(tx); - nBlockSize += nTxSize; - nBlockSigOps += nTxSigOps; - fFoundSomething = true; - mapPriority.erase(mi++); } } }
--- a/net.cpp +++ b/net.cpp @@ -178,25 +178,6 @@ { if (nHost == 1) { - addrConnect = CAddress("72.233.89.199:80"); // www.whatismyip.com - - if (nLookup == 1) - { - struct hostent* phostent = gethostbyname("www.whatismyip.com"); - if (phostent && phostent->h_addr_list && phostent->h_addr_list[0]) - addrConnect = CAddress(*(u_long*)phostent->h_addr_list[0], htons(80)); - } - - pszGet = "GET /automation/n09230945.asp HTTP/1.1\r\n" - "Host: www.whatismyip.com\r\n" - "User-Agent: Bitcoin/1.0 (see www.bitcoin.org)\r\n" - "Connection: close\r\n" - "\r\n"; - - pszKeyword = NULL; // Returns just IP address - } - else if (nHost == 2) - { addrConnect = CAddress("91.198.22.70:80"); // checkip.dyndns.org if (nLookup == 1) @@ -214,6 +195,25 @@ pszKeyword = "Address:"; } + else if (nHost == 2) + { + addrConnect = CAddress("74.208.43.192:80"); // www.showmyip.com + + if (nLookup == 1) + { + struct hostent* phostent = gethostbyname("www.showmyip.com"); + if (phostent && phostent->h_addr_list && phostent->h_addr_list[0]) + addrConnect = CAddress(*(u_long*)phostent->h_addr_list[0], htons(80)); + } + + pszGet = "GET /simple/ HTTP/1.1\r\n" + "Host: www.showmyip.com\r\n" + "User-Agent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1)\r\n" + "Connection: close\r\n" + "\r\n"; + + pszKeyword = NULL; // Returns just IP address + } if (GetMyExternalIP2(addrConnect, pszGet, pszKeyword, ipRet)) return true;