/*
Copyright (C)2003 Barry Dunne (http://www.emule-project.net)

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.


This work is based on the java implementation of the Kademlia protocol.
Kademlia: Peer-to-peer routing based on the XOR metric
Copyright (C) 2002  Petar Maymounkov [petar@post.harvard.edu]
http://kademlia.scs.cs.nyu.edu
*/

// Note To Mods //
/*
Please do not change anything here and release it..
There is going to be a new forum created just for the Kademlia side of the client..
If you feel there is an error or a way to improve something, please
post it in the forum first and let us look at it.. If it is a real improvement,
it will be added to the offical client.. Changing something without knowing
what all it does can cause great harm to the network if released in mass form..
Any mod that changes anything within the Kademlia side will not be allowed to advertise
there client on the eMule forum..
*/

/**
 * The *Zone* is just a node in a binary tree of *Zone*s.
 * Each zone is either an internal node or a leaf node.
 * Internal nodes have "bin == null" and "subZones[i] != null",
 * leaf nodes have "subZones[i] == null" and "bin != null".
 *
 * All key unique id's are relative to the center (self), which
 * is considered to be 000..000
 */

#include "stdafx.h"
#include <math.h>
#include "./RoutingZone.h"
#include "./RoutingBin.h"
#include "../utils/MiscUtils.h"
#include "../kademlia/Kademlia.h"
#include "../kademlia/Prefs.h"
#include "../kademlia/SearchManager.h"
#include "../kademlia/Defines.h"
#include "../net/KademliaUDPListener.h"
#include "../../Opcodes.h"
#include "../../emule.h"
#include "../../emuledlg.h"
#include "../../KadContactListCtrl.h"
#include "../../kademliawnd.h"
#include "../../SafeFile.h"
#include "../../Log.h"
#include "../../ipfilter.h"

// By Taz - Safe KAD
#include "NetF/SafeKad.h" // netfinity: Enable tracking of bad nodes
// <------- Safe KAD

// By Taz - Kad Helper
#include "../utils/KadHelper.h" //>>> WiZaRd::Kad Helper
// <------- Kad Helper

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

using namespace Kademlia;

void DebugSend(LPCTSTR pszMsg, uint32 uIP, uint16 uUDPPort);

CString CRoutingZone::m_sFilename;

// By Taz - UpdateNodesDat
DWORD CRoutingZone::m_tLastWrite; // NEO: MOD - [UpdateNodesDat] <-- Xanatos --
// <------- UpdateNodesDat

CUInt128 CRoutingZone::uMe = (ULONG)0;

CRoutingZone::CRoutingZone()
{
	// Can only create routing zone after prefs
	// Set our KadID for creating the contact tree
	CKademlia::GetPrefs()->GetKadID(&uMe);
	// Set the preference file name.

// By Taz - Fix
// dir vista officla fix (godlaugh2007)
	/*
	m_sFilename = CMiscUtils::GetAppDir();
	m_sFilename.Append(CONFIGFOLDER);
	m_sFilename.Append(_T("nodes.dat"));
	*/
	m_sFilename =thePrefs.GetMuleDirectory(EMULE_CONFIGDIR) + _T("nodes.dat");
// <------- Fix

	// Init our root node.
	Init(NULL, 0, CUInt128((ULONG)0));
}

CRoutingZone::CRoutingZone(LPCSTR szFilename)
{
	// Can only create routing zone after prefs
	// Set our KadID for creating the contact tree
	CKademlia::GetPrefs()->GetKadID(&uMe);
	m_sFilename = szFilename;
	// Init our root node.
	Init(NULL, 0, CUInt128((ULONG)0));
}

CRoutingZone::CRoutingZone(CRoutingZone *pSuper_zone, int iLevel, const CUInt128 &uZone_index)
{
	// Create a new leaf.
	Init(pSuper_zone, iLevel, uZone_index);
}

void CRoutingZone::Init(CRoutingZone *pSuper_zone, int iLevel, const CUInt128 &uZone_index)
{
	// Init all Zone vars
	// Set this zones parent
	m_pSuperZone = pSuper_zone;
	// Set this zones level
	m_uLevel = iLevel;
	// Set this zones CUInt128 Index
	m_uZoneIndex = uZone_index;
	// Mark this zone has having now leafs.
	m_pSubZones[0] = NULL;
	m_pSubZones[1] = NULL;
	// Create a new contact bin as this is a leaf.
	m_pBin = new CRoutingBin();

	// Set timer so that zones closer to the root are processed earlier.
	m_tNextSmallTimer = time(NULL) + m_uZoneIndex.Get32BitChunk(3);

	// Start this zone.
	StartTimer();

	// If we are initializing the root node, read in our saved contact list.
	if ((m_pSuperZone == NULL) && (m_sFilename.GetLength() > 0))
		ReadFile();

// By Taz - UpdateNodesDat
	m_tLastWrite = time(NULL); // NEO: MOD - [UpdateNodesDat] <-- Xanatos --
// <------- UpdateNodesDat

}

CRoutingZone::~CRoutingZone()
{
	// Root node is processed first so that we can write our contact list and delete all branches.
	if ((m_pSuperZone == NULL) && (m_sFilename.GetLength() > 0))
	{
		// Hide contacts in the GUI
		theApp.emuledlg->kademliawnd->HideContacts();
		WriteFile();
	}
	// If this zone is a leaf, delete our contact bin.
	if (IsLeaf())
		delete m_pBin;
	else
	{
		// If this zone is branch, delete it's leafs.
		delete m_pSubZones[0];
		delete m_pSubZones[1];
	}
	// All branches are deleted, show the contact list in the GUI.
	if (m_pSuperZone == NULL)
		theApp.emuledlg->kademliawnd->ShowContacts();
}

// By Taz - KadBootStrap
//void CRoutingZone::ReadFile()
void CRoutingZone::ReadFile(LPCTSTR sFilename) // NEO: KBS - [KadBootStrap] <-- Xanatos --
// <------- KadBootStrap

{

// By Taz - KAD Guard
	uint32 uValidContacts = 0;
// <------- KAD Guard

	// Read in the saved contact list.
	try
	{
		// Hide contact list in the GUI
		theApp.emuledlg->kademliawnd->HideContacts();
		CSafeBufferedFile file;
		CFileException fexp;

// By Taz - KadBootStrap
//		if (file.Open(m_sFilename, CFile::modeRead | CFile::osSequentialScan|CFile::typeBinary|CFile::shareDenyWrite, &fexp))
		// NEO: KBS - [KadBootStrap] -- Xanatos -->
		if(!sFilename)
			sFilename = m_sFilename;
		if (file.Open(sFilename, CFile::modeRead | CFile::osSequentialScan|CFile::typeBinary|CFile::shareDenyWrite, &fexp))
		// NEO: KBS END <-- Xanatos --
// <------- KadBootStrap

		{
			setvbuf(file.m_pStream, NULL, _IOFBF, 32768);

			// Get how many contacts in the saved list.
			// NOTE: Older clients put the number of contacts here..
			//       Newer clients always have 0 here to prevent older clients from reading it.
			uint32 uNumContacts = file.ReadUInt32();
			uint32 uVersion = 0;
			if (uNumContacts == 0)
			{
				try
				{
					uVersion = file.ReadUInt32();
					if(uVersion == 1)
						uNumContacts = file.ReadUInt32();
				}
				catch(...)
				{
					AddDebugLogLine( false, GetResString(IDS_ERR_KADCONTACTS));
				}
			}
			if (uNumContacts != 0)
			{

// By Taz - KAD Guard
//				uint32 uValidContacts = 0;
// <------- KAD Guard

				CUInt128 uID;
				while ( uNumContacts )
				{
					file.ReadUInt128(&uID);
					uint32 uIP = file.ReadUInt32();
					uint16 uUDPPort = file.ReadUInt16();
					uint16 uTCPPort = file.ReadUInt16();
					uint8 uContactVersion = 0;
					byte byType = 0;
					if(uVersion == 1)
						uContactVersion = file.ReadUInt8();
					else
						byType = file.ReadUInt8();
					// IP Appears valid
					if( byType < 4)
					{
						uint32 uhostIP = ntohl(uIP);
						if (::IsGoodIPPort(uhostIP, uUDPPort))
						{

// By Taz - Kad Helper
//>>> WiZaRd::Kad Helper
							UINT ourIP = CKademlia::GetPrefs()->GetIPAddress();
							if (ourIP != 0 && ourIP == uIP && thePrefs.GetUDPPort() == uUDPPort)
							{
								if (::thePrefs.GetLogFilteredIPs())
									AddDebugLogLine(false, _T("Ignored kad contact (IP=%s:%u) -- read known.dat -- IP is identical to our OWN IP") , ipstr(uhostIP), uUDPPort);
								continue;
							}
//<<< WiZaRd::Kad Helper
// <------- Kad Helper

							if (::theApp.ipfilter->IsFiltered(uhostIP))
							{
								if (::thePrefs.GetLogFilteredIPs())
									AddDebugLogLine(false, _T("Ignored kad contact (IP=%s)--read known.dat -- - IP filter (%s)") , ipstr(uhostIP), ::theApp.ipfilter->GetLastHit());
							}
							else
							{

// By Taz - Kad Helper
//>>> WiZaRd::Kad Helper
								if(IsBadContact(uIP, uUDPPort, uTCPPort))
								{
									if (::thePrefs.GetLogFilteredIPs())
										AddDebugLogLine(false, _T("Ignored blacklisted kad contact (IP=%s)  -- read known.dat --"), ipstr(uhostIP));
								}
								else
//<<< WiZaRd::Kad Helper
// <------- Kad Helper

								// This was not a dead contact, Inc counter if add was successful
								if (AddUnfiltered(uID, uIP, uUDPPort, uTCPPort, uContactVersion, false))
									uValidContacts++;

// By Taz - Safe KAD
// BEGIN netfinity: Safe KAD - Loaded nodes are expected to be useful
								CContact* pStoredContact = GetContact(uID);
								if (pStoredContact != NULL)
									pStoredContact->SetCandidate(false); // We already know this contact is useful
// END netfinity: Safe KAD - Loaded nodes are expected to be useful
// <------- Safe KAD

							}
						}
					}
					uNumContacts--;
				}
				AddLogLine( false, GetResString(IDS_KADCONTACTSREAD), uValidContacts);
			}
			file.Close();
		}
	}
	catch (CFileException* e)
	{
		e->Delete();
		AddDebugLogLine(false, _T("CFileException in CRoutingZone::readFile"));
	}

// By Taz - KAD Guard
	if (uValidContacts == 0 && !theApp.emuledlg->kademliawnd->AutoUpdateNodesDatFromUrl())
		ReadFile();
	else
// <------- KAD Guard

	// Show contact list in GUI
	theApp.emuledlg->kademliawnd->ShowContacts();
}

void CRoutingZone::WriteFile()
{
	try
	{
		// Write a saved contact list.
		CUInt128 uID;
		CSafeBufferedFile file;
		CFileException fexp;
		if (file.Open(m_sFilename, CFile::modeWrite | CFile::modeCreate | CFile::typeBinary|CFile::shareDenyWrite, &fexp))
		{
			setvbuf(file.m_pStream, NULL, _IOFBF, 32768);

			// The bootstrap method gets a very nice sample of contacts to save.
			ContactList listContacts;
			GetBootstrapContacts(&listContacts, 200);
			// Start file with 0 to prevent older clients from reading it.
			file.WriteUInt32(0);
			// Now tag it with a version which happens to be 1.
			file.WriteUInt32(1);
			file.WriteUInt32((uint32)listContacts.size());
			for (ContactList::const_iterator itContactList = listContacts.begin(); itContactList != listContacts.end(); ++itContactList)
			{
				CContact* pContact = *itContactList;
				pContact->GetClientID(&uID);
				file.WriteUInt128(&uID);
				file.WriteUInt32(pContact->GetIPAddress());
				file.WriteUInt16(pContact->GetUDPPort());
				file.WriteUInt16(pContact->GetTCPPort());
				file.WriteUInt8(pContact->GetVersion());
			}
			file.Close();
			AddDebugLogLine( false, _T("Wrote %ld contact%s to file."), listContacts.size(), ((listContacts.size() == 1) ? _T("") : _T("s")));

// By Taz - UpdateNodesDat
			m_tLastWrite = time(NULL); // NEO: MOD - [UpdateNodesDat] <-- Xanatos --
// <------- UpdateNodesDat

		}
	}
	catch (CFileException* e)
	{
		e->Delete();
		AddDebugLogLine(false, _T("CFileException in CRoutingZone::writeFile"));
	}
}

bool CRoutingZone::CanSplit() const
{
	// Max levels allowed.
	if (m_uLevel >= 127)
		return false;

	// Check if this zone is allowed to split.
	if ( (m_uZoneIndex < KK || m_uLevel < KBASE) && m_pBin->GetSize() == K)
		return true;
	return false;
}

// By Taz - Safe KAD
//bool CRoutingZone::Add(const CUInt128 &uID, uint32 uIP, uint16 uUDPPort, uint16 uTCPPort, uint8 uVersion, bool bUpdate)
bool CRoutingZone::Add(const CUInt128 &uID, uint32 uIP, uint16 uUDPPort, uint16 uTCPPort, uint8 uVersion, bool bUpdate, bool bAdd) // netfinity: Safe KAD
// <------- Safe KAD

{
	uint32 uhostIP = ntohl(uIP);
	if (::IsGoodIPPort(uhostIP, uUDPPort))
	{

// By Taz - Kad Helper
//>>> WiZaRd::Kad Helper
		UINT ourIP = CKademlia::GetPrefs()->GetIPAddress();
		if (ourIP != 0 && ourIP == uIP && thePrefs.GetUDPPort() == uUDPPort)
		{
			if (::thePrefs.GetLogFilteredIPs())
				AddDebugLogLine(false, _T("Ignored kad contact (IP=%s:%u) - IP is identical to our OWN IP") , ipstr(uhostIP), uUDPPort);
			return false;
		}
//<<< WiZaRd::Kad Helper
// <------- Kad Helper

		if (!::theApp.ipfilter->IsFiltered(uhostIP)) {

// By Taz - Kad Helper
//>>> WiZaRd::Kad Helper
			if(IsBadContact(uIP, uUDPPort, uTCPPort))
			{
				if (::thePrefs.GetLogFilteredIPs())
				 AddDebugLogLine(false, _T("Ignored blacklisted kad contact (IP=%s)"), ipstr(uhostIP));
			}
			else
//<<< WiZaRd::Kad Helper
// <------- Kad Helper

// By Taz - Safe KAD
//			return AddUnfiltered(uID, uIP, uUDPPort, uTCPPort, uVersion, bUpdate);
			return AddUnfiltered(uID, uIP, uUDPPort, uTCPPort, uVersion, bUpdate, bAdd); // netfinity: Safe KAD
// <------- Safe KAD

		}
		else if (::thePrefs.GetLogFilteredIPs())
			AddDebugLogLine(false, _T("Ignored kad contact (IP=%s) - IP filter (%s)"), ipstr(uhostIP), ::theApp.ipfilter->GetLastHit());
	}
	else if (::thePrefs.GetLogFilteredIPs())
		AddDebugLogLine(false, _T("Ignored kad contact (IP=%s) - Bad IP"), ipstr(uhostIP));
	return false;
}


// By Taz - Safe KAD
//bool CRoutingZone::AddUnfiltered(const CUInt128 &uID, uint32 uIP, uint16 uUDPPort, uint16 uTCPPort, uint8 uVersion, bool bUpdate)
bool CRoutingZone::AddUnfiltered(const CUInt128 &uID, uint32 uIP, uint16 uUDPPort, uint16 uTCPPort, uint8 uVersion, bool bUpdate, bool bAdd) // netfinity: Safe KAD
// <------- Safe KAD

{
	if (uID != uMe)
	{
		// JOHNTODO -- How do these end up leaking at times?
		CContact* pContact = new CContact(uID, uIP, uUDPPort, uTCPPort, uVersion);

// By Taz - Safe KAD
//		if (Add(pContact, bUpdate))
		if (Add(pContact, bUpdate, bAdd)) // netfinity: Safe KAD
// <------- Safe KAD

			return true;
		delete pContact;
	}
	return false;
}


// By Taz - Safe KAD
//bool CRoutingZone::Add(CContact* pContact, bool bUpdate)
bool CRoutingZone::Add(CContact* pContact, bool bUpdate, bool bAdd) // netfinity: Safe KAD
// <------- Safe KAD

{
	// If we are not a leaf, call add on the correct branch.
	if (!IsLeaf())

// By Taz - Safe KAD
//		return m_pSubZones[pContact->GetDistance().GetBitNumber(m_uLevel)]->Add(pContact, bUpdate);
		return m_pSubZones[pContact->GetDistance().GetBitNumber(m_uLevel)]->Add(pContact, bUpdate, bAdd);
// <------- Safe KAD

	else
	{
		// Do we already have a contact with this KadID?
		CContact* pContactUpdate = m_pBin->GetContact(pContact->GetClientID());
		if (pContactUpdate)
		{
			if(bUpdate)
			{
				pContactUpdate->SetIPAddress(pContact->GetIPAddress());
				pContactUpdate->SetUDPPort(pContact->GetUDPPort());
				pContactUpdate->SetTCPPort(pContact->GetTCPPort());
				pContactUpdate->SetVersion(pContact->GetVersion());
				m_pBin->SetAlive(pContactUpdate);

// By Taz - Safe KAD
// BEGIN netfinity: Safe KAD - Check node usefulness
				if (pContactUpdate->GetCandidate() == true)
					CSearchManager::FindNode(pContactUpdate->GetClientID(), false);
// END netfinity: Safe KAD - Check node usefulness
// <------- Safe KAD

				theApp.emuledlg->kademliawnd->ContactRef(pContactUpdate);
			}

// By Taz - Safe KAD
// BEGIN netfinity: Safe KAD - Update version if not known even thought update is not allowed
			else if (pContactUpdate->GetVersion() == 0)
			{
				pContactUpdate->SetVersion(pContact->GetVersion());
			}
// END netfinity: Safe KAD - Update version if not known even thought update is not allowed
// <------- Safe KAD

			return false;
		}

// By Taz - Safe KAD
//		else if (m_pBin->GetRemaining())
		else if (m_pBin->GetRemaining() && bAdd) // netfinity: Safe KAD - Don't add if it was an update only call
// <------- Safe KAD

		{
			// This bin is not full, so add the new contact.
			if(m_pBin->AddContact(pContact))
			{
				// Add was successful, add to the GUI and let contact know it's listed in the gui.
				if (theApp.emuledlg->kademliawnd->ContactAdd(pContact))
					pContact->SetGuiRefs(true);
				return true;
			}
			return false;
		}

// By Taz - Safe KAD
//		else if (CanSplit())
		else if (CanSplit() && bAdd) // netfinity: Safe KAD - Don't add if it was an update only call
// <------- Safe KAD

		{
			// This bin was full and split, call add on the correct branch.
			Split();

// By Taz - Safe KAD
//			return m_pSubZones[pContact->GetDistance().GetBitNumber(m_uLevel)]->Add(pContact, bUpdate);
			return m_pSubZones[pContact->GetDistance().GetBitNumber(m_uLevel)]->Add(pContact, bUpdate, bAdd); // netfinity: Safe KAD - Just to be consequent
// <------- Safe KAD

		}
		else
			return false;
	}
}

// By Taz - Kad Helper
//>>> WiZaRd::Kad Helper
void CRoutingZone::RemoveContact(CContact* pContact)
{
	if (IsLeaf())
		m_pBin->RemoveContact(pContact);
	else
		m_pSubZones[pContact->GetClientID().GetBitNumber(m_uLevel)]->RemoveContact(pContact);
}

CContact* CRoutingZone::GetContact(const UINT uIP, const uint16 uUDPPort, const uint16 uTCPPort)
{
	if (IsLeaf())
		return m_pBin->GetContact(uIP, uUDPPort, uTCPPort);
	else
	{
		//performance?!
		CContact* pContact = m_pSubZones[0]->GetContact(uIP, uUDPPort, uTCPPort);
		if(pContact == NULL)
			pContact = m_pSubZones[1]->GetContact(uIP, uUDPPort, uTCPPort);
		return pContact;
	}
}
//<<< WiZaRd::Kad Helper
// <------- Kad Helper

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

void 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())
	{
		m_pBin->GetClosestTo(uMaxType, uTarget, uMaxRequired, pmapResult, bEmptyFirst, bInUse);
		return;
	}

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

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

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);

// By Taz - Safe KAD
//		m_pSubZones[iSuperZone]->m_pBin->AddContact(*itContactList);
		m_pSubZones[iSuperZone]->m_pBin->AddContact(*itContactList, false); // netfinity: Safe KAD - Split operations will be unreliable if the add operation fails
// <------- Safe KAD

	}
	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)

// By Taz - Safe KAD
//				m_pBin->AddContact(*itContactList);
				m_pBin->AddContact(*itContactList, false); // netfinity: Safe KAD - Consolidate operations will be unreliable if the add operation fails
// <------- Safe KAD

			for (ContactList::const_iterator itContactList = list1.begin(); itContactList != list1.end(); ++itContactList)

// By Taz - Safe KAD
//				m_pBin->AddContact(*itContactList);
				m_pBin->AddContact(*itContactList, false); // netfinity: Safe KAD - Consolidate operations will be unreliable if the add operation fails
// <------- Safe KAD

		}
		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.0F, (int)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.0F, (int)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);

// By Taz - Fix
/*
	for (ContactList::iterator itContactList = listEntries.begin(); itContactList != listEntries.end(); ++itContactList)
	{
		pContact = *itContactList;
*/
// infinity
	for (ContactList::iterator itContactList = listEntries.begin(); itContactList != listEntries.end();)
	{
		pContact = *(itContactList++); // netfinity: Deleting a list entry at the iterator position invalidates the iterator, therefore we increment it
// <------- Fix

// By Taz - Safe KAD
		// BEGIN netfinity: Safe KAD - Remove bad nodes
		// Check against node track list
		if (safeKad.IsBadNode(pContact->GetIPAddress(), pContact->GetUDPPort(), pContact->GetClientID()) && !pContact->InUse())
		{
			if (::thePrefs.GetLogFilteredIPs())
				AddDebugLogLine(false, _T("Removing contact(IP=%s) - Identified as bad node") , ipstr(ntohl(pContact->GetIPAddress())));
			m_pBin->RemoveContact(pContact);
			delete pContact;
			continue;
		}
		// END netfinity: Safe KAD - Remove bad nodes
// <------- Safe KAD

		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() >= 2/*47a*/)
		{
			if (thePrefs.GetDebugClientKadUDPLevel() > 0)
				DebugSend("KADEMLIA2_HELLO_REQ", pContact->GetIPAddress(), pContact->GetUDPPort());
			CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA2_HELLO_REQ, pContact->GetIPAddress(), pContact->GetUDPPort(), true);
		}
		else
		{
			if (thePrefs.GetDebugClientKadUDPLevel() > 0)
				DebugSend("KADEMLIA_HELLO_REQ", pContact->GetIPAddress(), pContact->GetUDPPort());
			CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA_HELLO_REQ, pContact->GetIPAddress(), pContact->GetUDPPort(), false);
			if (pContact->CheckIfKad2())
			{
				if (thePrefs.GetDebugClientKadUDPLevel() > 0)
					DebugSend("KADEMLIA2_HELLO_REQ", pContact->GetIPAddress(), pContact->GetUDPPort());
				CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA2_HELLO_REQ, pContact->GetIPAddress(), pContact->GetUDPPort(), true);
			}
		}
	}

// By Taz - UpdateNodesDat
	// NEO: MOD - [UpdateNodesDat] -- Xanatos -->
	if (tNow - m_tLastWrite > HR2S(4)) // Avi3k: update nodes.dat frequently
		WriteFile();
	// NEO: MOD END <-- Xanatos --
// <------- UpdateNodesDat

}

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;
}
