Method FindHash

src/SHAHashSet.cpp:102–150

recursive

// recursive
CAICHHashTree* CAICHHashTree::FindHash(uint64 nStartPos, uint64 nSize, uint8* nLevel)
{
	(*nLevel)++;

	wxCHECK(*nLevel <= 22, NULL);
	wxCHECK(nStartPos + nSize <= m_nDataSize, NULL);
	wxCHECK(nSize <= m_nDataSize, NULL);

	if (nStartPos == 0 && nSize == m_nDataSize) {
		// this is the searched hash
		return this;
	} else if (m_nDataSize <= m_nBaseSize) { // sanity
		// this is already the last level, can't go deeper
		wxFAIL;
		return NULL;
	} else {
		uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0);
		uint64 nLeft = (((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
		uint64 nRight = m_nDataSize - nLeft;
		if (nStartPos < nLeft) {
			if (nStartPos + nSize > nLeft) { // sanity
				wxFAIL;
				return NULL;
			}

			if (m_pLeftTree == NULL) {
				m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
			} else {
				wxASSERT( m_pLeftTree->m_nDataSize == nLeft );
			}

			return m_pLeftTree->FindHash(nStartPos, nSize, nLevel);
		} else {
			nStartPos -= nLeft;
			if (nStartPos + nSize > nRight) { // sanity
				wxFAIL;
				return NULL;
			}

			if (m_pRightTree == NULL) {
				m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
			} else {
				wxASSERT( m_pRightTree->m_nDataSize == nRight );
			}

			return m_pRightTree->FindHash(nStartPos, nSize, nLevel);
		}
	}
}


// recursive