efficiently sort transaction dependencies in one pass

git-svn-id: https://bitcoin.svn.sourceforge.net/svnroot/bitcoin/trunk@184 1a98c847-1fd6-4fd8-948a-caf3550aa51b

3 files changed, 97 insertions, 48 deletions

diff --git a/main.cpp b/main.cpp
index 190cd4b296..6848342b71 100644
--- a/main.cpp
+++ b/main.cpp
@@ -598,6 +598,8 @@ bool CTransaction::AcceptToMemoryPool(CTxDB& txdb, bool fCheckInputs, bool* pfMi
             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 @@ extern unsigned int ScanHash_4WaySSE2(char* pmidstate, char* pblock, char* phash
 
 
 
+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 @@ void BitcoinMiner()
             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 @@ void BitcoinMiner()
                 if (tx.IsCoinBase() || !tx.IsFinal())
                     continue;
 
+                COrphan* porphan = NULL;
                 double dPriority = 0;
                 foreach(const CTxIn& txin, tx.vin)
                 {
@@ -3112,7 +3139,18 @@ void BitcoinMiner()
                     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 @@ void BitcoinMiner()
                 // 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();)
-                {
-                    CTransaction& tx = *(*mi).second;
-                    unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK);
-                    if (nBlockSize + nTxSize >= MAX_BLOCK_SIZE_GEN)
-                    {
-                        mapPriority.erase(mi++);
-                        continue;
-                    }
-                    int nTxSigOps = tx.GetSigOpCount();
-                    if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS)
-                    {
-                        mapPriority.erase(mi++);
-                        continue;
-                    }
+                // 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);
+                // 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))
+                // 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))
+                {
+                    foreach(COrphan* porphan, mapDependers[hash])
                     {
-                        mi++;
-                        continue;
+                        if (!porphan->setDependsOn.empty())
+                        {
+                            porphan->setDependsOn.erase(hash);
+                            if (porphan->setDependsOn.empty())
+                                mapPriority.insert(make_pair(-porphan->dPriority, porphan->ptx));
+                        }
                     }
-                    swap(mapTestPool, mapTestPoolTmp);
-
-                    // Added
-                    pblock->vtx.push_back(tx);
-                    nBlockSize += nTxSize;
-                    nBlockSigOps += nTxSigOps;
-                    fFoundSomething = true;
-                    mapPriority.erase(mi++);
                 }
             }
         }
diff --git a/net.cpp b/net.cpp
index 7cc21be398..3c80644a49 100644
--- a/net.cpp
+++ b/net.cpp
@@ -178,41 +178,41 @@ bool GetMyExternalIP(unsigned int& ipRet)
     {
         if (nHost == 1)
         {
-            addrConnect = CAddress("72.233.89.199:80"); // www.whatismyip.com
+            addrConnect = CAddress("91.198.22.70:80"); // checkip.dyndns.org
 
             if (nLookup == 1)
             {
-                struct hostent* phostent = gethostbyname("www.whatismyip.com");
+                struct hostent* phostent = gethostbyname("checkip.dyndns.org");
                 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"
+            pszGet = "GET / HTTP/1.1\r\n"
+                     "Host: checkip.dyndns.org\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
+            pszKeyword = "Address:";
         }
         else if (nHost == 2)
         {
-            addrConnect = CAddress("91.198.22.70:80"); // checkip.dyndns.org
+            addrConnect = CAddress("74.208.43.192:80"); // www.showmyip.com
 
             if (nLookup == 1)
             {
-                struct hostent* phostent = gethostbyname("checkip.dyndns.org");
+                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 / HTTP/1.1\r\n"
-                     "Host: checkip.dyndns.org\r\n"
+            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 = "Address:";
+            pszKeyword = NULL; // Returns just IP address
         }
 
         if (GetMyExternalIP2(addrConnect, pszGet, pszKeyword, ipRet))
diff --git a/serialize.h b/serialize.h
index 43122078d5..342a03941e 100644
--- a/serialize.h
+++ b/serialize.h
@@ -22,7 +22,7 @@ class CDataStream;
 class CAutoFile;
 static const unsigned int MAX_SIZE = 0x02000000;
 
-static const int VERSION = 31501;
+static const int VERSION = 31502;
 static const char* pszSubVer = "";