routingzone.cpp

电驴下载工具eMule0.47aVeryCD的源代码,可作分析测试也可用于P2P软件的开发研究.

				if (theApp.emuledlg->kademliawnd->ContactAdd(pContact))
					pContact->SetGuiRefs(true);
				return true;
			}
			return false;
		}
		else if (CanSplit())
		{
			// This bin was full and split, call add on the correct branch.
			Split();
			return m_pSubZones[pContact->GetDistance().GetBitNumber(m_uLevel)]->Add(pContact);
		}
		else
			return false;
	}
}

void CRoutingZone::SetAlive(uint32 uIP, uint16 uUDPPort)
{
	if (IsLeaf())
		m_pBin->SetAlive(uIP, uUDPPort);
	else
	{
		m_pSubZones[0]->SetAlive(uIP, uUDPPort);
		m_pSubZones[1]->SetAlive(uIP, uUDPPort);
	}
}

CContact *CRoutingZone::GetContact(const CUInt128 &uID) const
{
	if (IsLeaf())
		return m_pBin->GetContact(uID);
	else
		return m_pSubZones[uID.GetBitNumber(m_uLevel)]->GetContact(uID);
}

uint32 CRoutingZone::GetClosestTo(uint32 uMaxType, const CUInt128 &uTarget, const CUInt128 &uDistance, uint32 uMaxRequired, ContactMap *pmapResult, bool bEmptyFirst, bool bInUse) const
{
	// If leaf zone, do it here
	if (IsLeaf())
		return m_pBin->GetClosestTo(uMaxType, uTarget, uMaxRequired, pmapResult, bEmptyFirst, bInUse);

	// otherwise, recurse in the closer-to-the-target subzone first
	int iCloser = uDistance.GetBitNumber(m_uLevel);
	uint32 uFound = m_pSubZones[iCloser]->GetClosestTo(uMaxType, uTarget, uDistance, uMaxRequired, pmapResult, bEmptyFirst, bInUse);

	// if still not enough tokens found, recurse in the other subzone too
	if (uFound < uMaxRequired)
		uFound += m_pSubZones[1-iCloser]->GetClosestTo(uMaxType, uTarget, uDistance, uMaxRequired-uFound, pmapResult, false, bInUse);

	return uFound;
}

void CRoutingZone::GetAllEntries(ContactList *pmapResult, bool bEmptyFirst)
{
	if (IsLeaf())
		m_pBin->GetEntries(pmapResult, bEmptyFirst);
	else
	{
		m_pSubZones[0]->GetAllEntries(pmapResult, bEmptyFirst);
		m_pSubZones[1]->GetAllEntries(pmapResult, false);
	}
}

void CRoutingZone::TopDepth(int iDepth, ContactList *pmapResult, bool bEmptyFirst)
{
	if (IsLeaf())
		m_pBin->GetEntries(pmapResult, bEmptyFirst);
	else if (iDepth <= 0)
		RandomBin(pmapResult, bEmptyFirst);
	else
	{
		m_pSubZones[0]->TopDepth(iDepth-1, pmapResult, bEmptyFirst);
		m_pSubZones[1]->TopDepth(iDepth-1, pmapResult, false);
	}
}

void CRoutingZone::RandomBin(ContactList *pmapResult, bool bEmptyFirst)
{
	if (IsLeaf())
		m_pBin->GetEntries(pmapResult, bEmptyFirst);
	else
		m_pSubZones[rand()&1]->RandomBin(pmapResult, bEmptyFirst);
}

uint32 CRoutingZone::GetMaxDepth() const
{
	if (IsLeaf())
		return 0;
	return 1 + max(m_pSubZones[0]->GetMaxDepth(), m_pSubZones[1]->GetMaxDepth());
}

void CRoutingZone::Split()
{
	StopTimer();

	m_pSubZones[0] = GenSubZone(0);
	m_pSubZones[1] = GenSubZone(1);

	ContactList listEntries;
	m_pBin->GetEntries(&listEntries);
	for (ContactList::const_iterator itContactList = listEntries.begin(); itContactList != listEntries.end(); ++itContactList)
	{
		int iSuperZone = (*itContactList)->m_uDistance.GetBitNumber(m_uLevel);
		m_pSubZones[iSuperZone]->m_pBin->AddContact(*itContactList);
	}
	m_pBin->m_bDontDeleteContacts = true;
	delete m_pBin;
	m_pBin = NULL;
}

uint32 CRoutingZone::Consolidate()
{
	uint32 uMergeCount = 0;
	if( IsLeaf() )
		return uMergeCount;
	ASSERT(m_pBin==NULL);
	if( !m_pSubZones[0]->IsLeaf() )
		uMergeCount += m_pSubZones[0]->Consolidate();
	if( !m_pSubZones[1]->IsLeaf() )
		uMergeCount += m_pSubZones[1]->Consolidate();
	if( m_pSubZones[0]->IsLeaf() && m_pSubZones[1]->IsLeaf() && GetNumContacts() < K/2 )
	{
		m_pBin = new CRoutingBin();
		m_pSubZones[0]->StopTimer();
		m_pSubZones[1]->StopTimer();
		if (GetNumContacts() > 0)
		{
			ContactList list0;
			ContactList list1;
			m_pSubZones[0]->m_pBin->GetEntries(&list0);
			m_pSubZones[1]->m_pBin->GetEntries(&list1);
			for (ContactList::const_iterator itContactList = list0.begin(); itContactList != list0.end(); ++itContactList)
				m_pBin->AddContact(*itContactList);
			for (ContactList::const_iterator itContactList = list1.begin(); itContactList != list1.end(); ++itContactList)
				m_pBin->AddContact(*itContactList);
		}
		m_pSubZones[0]->m_pSuperZone = NULL;
		m_pSubZones[1]->m_pSuperZone = NULL;
		m_pSubZones[0]->m_pBin->m_bDontDeleteContacts = true;
		m_pSubZones[1]->m_pBin->m_bDontDeleteContacts = true;
		delete m_pSubZones[0];
		delete m_pSubZones[1];
		m_pSubZones[0] = NULL;
		m_pSubZones[1] = NULL;
		StartTimer();
		uMergeCount++;
	}
	return uMergeCount;
}

bool CRoutingZone::IsLeaf() const
{
	return (m_pBin != NULL);
}

CRoutingZone *CRoutingZone::GenSubZone(int iSide)
{
	CUInt128 uNewIndex(m_uZoneIndex);
	uNewIndex.ShiftLeft(1);
	if (iSide != 0)
		uNewIndex.Add(1);
	return new CRoutingZone(this, m_uLevel+1, uNewIndex);
}

void CRoutingZone::StartTimer()
{
	time_t tNow = time(NULL);
	// Start filling the tree, closest bins first.
	m_tNextBigTimer = tNow + SEC(10);
	CKademlia::AddEvent(this);
}

void CRoutingZone::StopTimer()
{
	CKademlia::RemoveEvent(this);
}

bool CRoutingZone::OnBigTimer()
{
	if ( IsLeaf() && (m_uZoneIndex < KK || m_uLevel < KBASE || m_pBin->GetRemaining() >= (K*.8)))
	{
		RandomLookup();
		return true;
	}

	return false;
}

//This is used when we find a leaf and want to know what this sample looks like.
//We fall back two levels and take a sample to try to minimize any areas of the
//tree that will give very bad results.
uint32 CRoutingZone::EstimateCount()
{
	if( !IsLeaf() )
		return 0;
	if( m_uLevel < KBASE )
		return (UINT)(pow(2, m_uLevel)*K);
	CRoutingZone* pCurZone = m_pSuperZone->m_pSuperZone->m_pSuperZone;
	// Find out how full this part of the tree is.
	float fModify = ((float)pCurZone->GetNumContacts())/(float)(K*2);
	// First calculate users assuming the tree is full.
	// Modify count by bin size.
	// Modify count by how full the tree is.
	// Modify count by assuming 20% of the users are firewalled and can't be a contact.
	return (UINT)((pow( 2, m_uLevel-2))*(float)K*fModify*(1.20F));
}

void CRoutingZone::OnSmallTimer()
{
	if (!IsLeaf())
		return;

	CContact *pContact = NULL;
	time_t tNow = time(NULL);
	ContactList listEntries;
	// Remove dead entries
	m_pBin->GetEntries(&listEntries);
	for (ContactList::iterator itContactList = listEntries.begin(); itContactList != listEntries.end(); ++itContactList)
	{
		pContact = *itContactList;
		if ( pContact->GetType() == 4)
		{
			if (((pContact->m_tExpires > 0) && (pContact->m_tExpires <= tNow)))
			{
				if(!pContact->InUse())
				{
					m_pBin->RemoveContact(pContact);
					delete pContact;
				}
				continue;
			}
		}
		if(pContact->m_tExpires == 0)
			pContact->m_tExpires = tNow;
	}
	pContact = m_pBin->GetOldest();
	if( pContact != NULL )
	{
		if ( pContact->m_tExpires >= tNow || pContact->GetType() == 4)
		{
			m_pBin->RemoveContact(pContact);
			m_pBin->m_listEntries.push_back(pContact);
			pContact = NULL;
		}
	}
	if(pContact != NULL)
	{
		pContact->CheckingType();
		if(pContact->GetVersion() != 0)
		{
			if (thePrefs.GetDebugClientKadUDPLevel() > 0)
				DebugSend("KADEMLIA2_HELLO_REQ", pContact->GetIPAddress(), pContact->GetUDPPort());
			CKademlia::GetUDPListener()->SendMyDetails_KADEMLIA2(KADEMLIA2_HELLO_REQ, pContact->GetIPAddress(), pContact->GetUDPPort());
		}
		else
		{
			if (thePrefs.GetDebugClientKadUDPLevel() > 0)
				DebugSend("KADEMLIA_HELLO_REQ", pContact->GetIPAddress(), pContact->GetUDPPort());
			CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA_HELLO_REQ, pContact->GetIPAddress(), pContact->GetUDPPort());
		}
	}
}

void CRoutingZone::RandomLookup()
{
	// Look-up a random client in this zone
	CUInt128 uPrefix(m_uZoneIndex);
	uPrefix.ShiftLeft(128 - m_uLevel);
	CUInt128 uRandom(uPrefix, m_uLevel);
	uRandom.Xor(uMe);
	CSearchManager::FindNode(uRandom, false);
}

uint32 CRoutingZone::GetNumContacts() const
{
	if (IsLeaf())
		return m_pBin->GetSize();
	else
		return m_pSubZones[0]->GetNumContacts() + m_pSubZones[1]->GetNumContacts();
}

uint32 CRoutingZone::GetBootstrapContacts(ContactList *plistResult, uint32 uMaxRequired)
{
	ASSERT(m_pSuperZone == NULL);
	plistResult->clear();
	uint32 uRetVal = 0;
	try
	{
		ContactList top;
		TopDepth(LOG_BASE_EXPONENT, &top);
		if (top.size() > 0)
		{
			for (ContactList::const_iterator itContactList = top.begin(); itContactList != top.end(); ++itContactList)
			{
				plistResult->push_back(*itContactList);
				uRetVal++;
				if (uRetVal == uMaxRequired)
					break;
			}
		}
	}
	catch (...)
	{
		AddDebugLogLine(false, _T("Exception in CRoutingZone::getBoostStrapContacts"));
	}
	return uRetVal;
}