| 93 | } |
| 94 | |
| 95 | uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) { |
| 96 | if (nBitsUsed >= vBits.size()) { |
| 97 | // overflowed the bits array - failure |
| 98 | fBad = true; |
| 99 | return uint256(); |
| 100 | } |
| 101 | bool fParentOfMatch = vBits[nBitsUsed++]; |
| 102 | if (height==0 || !fParentOfMatch) { |
| 103 | // if at height 0, or nothing interesting below, use stored hash and do not descend |
| 104 | if (nHashUsed >= vHash.size()) { |
| 105 | // overflowed the hash array - failure |
| 106 | fBad = true; |
| 107 | return uint256(); |
| 108 | } |
| 109 | const uint256 &hash = vHash[nHashUsed++]; |
| 110 | if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid |
| 111 | vMatch.push_back(hash); |
| 112 | vnIndex.push_back(pos); |
| 113 | } |
| 114 | return hash; |
| 115 | } else { |
| 116 | // otherwise, descend into the subtrees to extract matched txids and hashes |
| 117 | uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right; |
| 118 | if (pos*2+1 < CalcTreeWidth(height-1)) { |
| 119 | right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex); |
| 120 | if (right == left) { |
| 121 | // The left and right branches should never be identical, as the transaction |
| 122 | // hashes covered by them must each be unique. |
| 123 | fBad = true; |
| 124 | } |
| 125 | } else { |
| 126 | right = left; |
| 127 | } |
| 128 | // and combine them before returning |
| 129 | return Hash(left, right); |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) { |
| 134 | // reset state |