routingzone.cpp

电驴的源代码

	else
	{
		m_subZones[0]->topDepth(depth-1, result, emptyFirst);
		m_subZones[1]->topDepth(depth-1, result, false);
	}
}

void CRoutingZone::randomBin(ContactList *result, bool emptyFirst)
{
	if (isLeaf())
	{
		try
		{
			m_bin->getEntries(result, emptyFirst);
		} 
		catch (...) 
		{
			AddDebugLogLine(false, _T("Exception in CRoutingZone::randomBin"));
		}
	}
	else
		m_subZones[rand()&1]->randomBin(result, emptyFirst);
}

uint32 CRoutingZone::getMaxDepth(void) const
{
	if (isLeaf())
		return 0;
	return 1 + max(m_subZones[0]->getMaxDepth(), m_subZones[1]->getMaxDepth());
}

void CRoutingZone::split(void)
{
	try
	{
		stopTimer();
		
		m_subZones[0] = genSubZone(0);
		m_subZones[1] = genSubZone(1);

		ContactList entries;
		m_bin->getEntries(&entries);
		ContactList::const_iterator it;
		for (it = entries.begin(); it != entries.end(); it++)
		{
			int sz = (*it)->m_distance.getBitNumber(m_level);
			m_subZones[sz]->m_bin->add(*it);
		}
		m_bin->m_dontDeleteContacts = true;
		delete m_bin;
		m_bin = NULL;
	} 
	catch (...)
	{
		AddDebugLogLine(false, _T("Exception in CRoutingZone::split"));
	}
}

void CRoutingZone::merge(void)
{
	try
	{
        if (isLeaf() && m_superZone != NULL)
			m_superZone->merge();
		else if ((!isLeaf())
			&& (m_subZones[0]->isLeaf() && m_subZones[1]->isLeaf()) 
			&&	(getNumContacts()) < (K/2) )
		{
			m_bin = new CRoutingBin();
			
			m_subZones[0]->stopTimer();
			m_subZones[1]->stopTimer();

			if (getNumContacts() > 0)
			{
				ContactList list0;
				ContactList list1;
				m_subZones[0]->m_bin->getEntries(&list0);
				m_subZones[1]->m_bin->getEntries(&list1);
				ContactList::const_iterator it;
				for (it = list0.begin(); it != list0.end(); it++)
					m_bin->add(*it);
				for (it = list1.begin(); it != list1.end(); it++)
					m_bin->add(*it);
			}

			m_subZones[0]->m_superZone = NULL;
			m_subZones[1]->m_superZone = NULL;

			delete m_subZones[0];
			delete m_subZones[1];

			m_subZones[0] = NULL;
			m_subZones[1] = NULL;

			startTimer();
			
			if (m_superZone != NULL)
				m_superZone->merge();
		}
	} 
	catch (...) 
	{
		AddDebugLogLine(false, _T("Exception in CRoutingZone::merge"));
	}
}

bool CRoutingZone::isLeaf(void) const
{
	return (m_bin != NULL);
}

CRoutingZone *CRoutingZone::genSubZone(int side) 
{
	CUInt128 newIndex(m_zoneIndex);
	newIndex.shiftLeft(1);
	if (side != 0)
		newIndex.add(1);
	CRoutingZone *retVal = new CRoutingZone(this, m_level+1, newIndex);
	return retVal;
}

void CRoutingZone::startTimer(void)
{
	time_t now = time(NULL);
	// Start filling the tree, closest bins first.
	m_nextBigTimer = now + (MIN2S(1)*m_zoneIndex.get32BitChunk(3)) + SEC(10);
	CKademlia::addEvent(this);
}

void CRoutingZone::stopTimer(void)
{
	CKademlia::removeEvent(this);
}

bool CRoutingZone::onBigTimer(void)
{
	if (!isLeaf())
		return false;

	if ( (m_zoneIndex < KK || m_level < KBASE || m_bin->getRemaining() >= (K*.4)))
	{
		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_level < KBASE )
		return (pow(2, m_level)*10);
	CRoutingZone* curZone = m_superZone->m_superZone->m_superZone;

	float modify = ((float)curZone->getNumContacts())/20.0F;
	return (pow( 2, m_level-2))*10*(modify);
}

void CRoutingZone::onSmallTimer(void)
{
	if (!isLeaf())
		return;

	CString test;
	m_zoneIndex.toBinaryString(&test);

	CContact *c = NULL;
	time_t now = time(NULL);
	ContactList entries;
	ContactList::iterator it;

	try
	{
		// Remove dead entries
		m_bin->getEntries(&entries);
		for (it = entries.begin(); it != entries.end(); it++)
		{
			c = *it;
			if ( c->getType() > 1)
			{
				if (((c->m_expires > 0) && (c->m_expires <= now)))
				{
					if(!c->inUse())
					{
						m_bin->remove(c);
						delete c;
					}
					continue;
				}
			}
			if(c->m_expires == 0 && c->madeContact() == false)
				c->m_expires = now;
		}
		c = NULL;
		//Ping only contacts that are in the branches that meet the set level and are not close to our ID.
		//The other contacts are checked with the big timer.
		if( m_bin->getRemaining() < (K*(.4)) )
			c = m_bin->getOldest();
		if( c != NULL )
		{
			if ( c->m_expires >= now || c->getType() == 2)
			{
				m_bin->remove(c);
				m_bin->m_entries.push_back(c);
				c = NULL;
			}
		}
	} 
	catch (...) 
	{
		AddDebugLogLine(false, _T("Exception in CRoutingZone::onSmallTimer"));
	}
	if(c != NULL)
	{
		c->setType(c->getType()+1);
		CKademliaUDPListener *udpListner = CKademlia::getUDPListener();
		ASSERT(udpListner != NULL); 
		if (thePrefs.GetDebugClientKadUDPLevel() > 0)
			DebugSend("KadHelloReq", c->getIPAddress(), c->getUDPPort());
		udpListner->sendMyDetails(KADEMLIA_HELLO_REQ, c->getIPAddress(), c->getUDPPort());
	}
}

void CRoutingZone::randomLookup(void) 
{
	// Look-up a random client in this zone
	CUInt128 prefix(m_zoneIndex);
	prefix.shiftLeft(128 - m_level);
	CUInt128 random(prefix, m_level);
	random.xor(me);
	CSearchManager::findNode(random);
}

uint32 CRoutingZone::getNumContacts(void) const
{
	if (isLeaf())
		return m_bin->getSize();
	else
		return m_subZones[0]->getNumContacts() + m_subZones[1]->getNumContacts();
}

uint32 CRoutingZone::getBootstrapContacts(ContactList *results, uint32 maxRequired)
{
	ASSERT(m_superZone == NULL);

	results->clear();

	uint32 retVal = 0;
	try
	{
		ContactList top;
		topDepth(LOG_BASE_EXPONENT, &top);
		if (top.size() > 0)
		{
			ContactList::const_iterator it;
			for (it = top.begin(); it != top.end(); it++)
			{
				results->push_back(*it);
				retVal++;
				if (retVal == maxRequired)
					break;
			}
		}
	} 
	catch (...) 
	{
		AddDebugLogLine(false, _T("Exception in CRoutingZone::getBoostStrapContacts"));
	}
	return retVal;
}

/*
uint64 CRoutingZone::getApproximateNodeCount(uint32 ourLevel) const
{
	if (isLeaf()) 
		return ((uint64)1 << ourLevel) * (uint64)m_bin->getSize();
	return (m_subZones[0]->getApproximateNodeCount(ourLevel+1) + m_subZones[1]->getApproximateNodeCount(ourLevel+1)) / 2;
}
*/

/*
void CRoutingZone::selfTest(void)
{
	// This is not intended to be a conclusive test of the routing zone, 
	// just a place to put some simple debugging tests

	CString msg;

	// Try storing a lot of random keys
	CUInt128 id;
	for (int i=0; i<100000; i++)
	{
		id.setValueRandom();
id.toHexString(&msg);
OutputDebugString(msg);
OutputDebugString(_T("\r\n"));

		if (!add(id, 0xC0A80001, 0x1234, 0x4321, 0))
			break;
//		if (i%20 == 0)
//			dumpContents();
	}
	dumpContents();

	// Should have good dispersion now

	// Try some close to me, should keep splitting
	CUInt128 *close = new CUInt128;
	for (int i=0; i<100000; i++)
	{
		delete close;
		close = new CUInt128(me, 1+i%128);
close->toHexString(&msg);
OutputDebugString(msg);
OutputDebugString(_T("\r\n"));
		if (!add(*close, 0xC0A80001, 0x1234, 0x4321, 0))
			break;
//		if (i%20 == 0)
//			root->dumpContents();
	}
	dumpContents();
	delete close;

	// Try to find the nearest

	id.setValueRandom();
	id.toHexString(&msg);
	OutputDebugString(_T("Trying to find nearest to : "));
	OutputDebugString(msg);
	OutputDebugString(_T("\r\n"));
	CUInt128 x(me);
	x.xor(id);
	OutputDebugString(_T("Distance from me                 : "));
	x.toBinaryString(&msg);
	OutputDebugString(msg);
	OutputDebugString(_T("\r\n"));

	ContactMap result;
	getClosestTo(0, id, 20, &result);

	CString line;
	CString hex;
	CString distance;
	CContact *c;
	ContactMap::const_iterator it;
	for (it = result.begin(); it != result.end(); it++)
	{
		c = it->second;
		c->m_clientID.toHexString(&hex);
		c->getDistance(&distance);
		line.Format(_T("%s : %s\r\n"), hex, distance);
		OutputDebugString(line);
	}
}
*/
/*
//Don't delete, just keep for future reference..
void CRoutingZone::dumpContents(LPCTSTR prefix) const
{
#ifdef DEBUG
	CString msg;
	CString ziStr;
	m_zoneIndex.toBinaryString(&ziStr, true);

	if (prefix == NULL)
		OutputDebugString(_T("------------------------------------------------------\r\n"));
	if (isLeaf()) 
	{
		msg.Format(_T("Zone level: %ld\tZone prefix: %s\tContacts: %ld\tZoneIndex: %s\r\n"), 
			m_level, (prefix == NULL) ? _T("ROOT") : prefix, getNumContacts(), ziStr);
		OutputDebugString(msg);
		m_bin->dumpContents();
	} 
	else 
	{
		msg.Format(_T("Zone level: %ld\tZone prefix: %s\tContacts: %ld\tZoneIndex: %s NODE\r\n"), 
					m_level, (prefix == NULL) ? _T("ROOT") : prefix, getNumContacts(), ziStr);
		OutputDebugString(msg);
		msg.Format(_T("%s0"), (prefix == NULL) ? _T("") : prefix);
		m_subZones[0]->dumpContents(msg.GetBuffer(0));
		msg.Format(_T("%s1"), (prefix == NULL) ? _T("") : prefix);
		m_subZones[1]->dumpContents(msg.GetBuffer(0));
	}
#endif
}
*/