/*
This Work is under GPL provided with this work.

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
and
This work is bassed on translation from Barry Dunne to C++
Copyright (C)2003 Barry Dunne (http://www.emule-project.net)
*/
#include "cygwin.h"
#include "misc.h"
#include "opcodes.h"
#include "cHash.h"
#include "cPeer.h"
#include "cBucket.h"
#include "cZone.h"
#include "sTag.h"
#include "kademlia.h"
#include "donkey.h"
#include "cSearchManager.h"

cZone::~cZone() {{{
	if (m_superZone == NULL) writeFile();
	if (isLeaf()) delete m_bin;
	else {
		delete m_subZones[0];
		delete m_subZones[1];
		}
	}}}

extern uint8_t this_hash[HASH_LEN];
//extern struct in_addr my_ip;
extern class cKademlia       *kademlia;

void cZone::writeFile(void) {{{
	cPeerList contacts;
	getAllEntries(&contacts);
	size_t count = 500;
	size_t avail = contacts.size();
	if (avail < count) count = avail;
	if (count == 0) return;
	size_t len, LEN = len = count * 23 + 4;
	unsigned char *buf, *BUF = buf = reinterpret_cast<unsigned char*>(alloca(LEN));
	ADD_U4(&buf, &len, count);
	cPeerList::const_iterator it;
	for (it = contacts.begin(); it != contacts.end(); it++) {
		class cPeer *c = *it;
		ADD_HASH (&buf, &len, c->get_Hash()->hash);
		ADD_U4   (&buf, &len, c->ip);
		ADD_U2	 (&buf, &len, c->udp);
		ADD_U1	 (&buf, &len, c->type);
		if (len == 0) break;
		count --;
		if (count == 0) break;
		}
	int fd = FD_create ("contact.dat", O_RDWR|O_BINARY|O_TRUNC|O_CREAT,0600);
	if (fd == -1) {
		free(BUF);
		return;
		}
	FD_WRITE2 (fd, BUF, LEN);
	ASSERT(fd != -1); FD_close(fd);
	}}}
void cZone::readFile(void) {{{
	int fd = FD_open ("contact.dat", O_RDONLY|O_BINARY);
	if (fd == -1) return;
	size_t len, LEN = len = FD_LSEEK(fd, 0, SEEK_END);
	FD_LSEEK(fd, 0, SEEK_SET);
	unsigned char *buf, *BUF = buf = reinterpret_cast<unsigned char*>(alloca(LEN));
	if(!FD_READ2 (fd, BUF, LEN)) assert(0);
	ASSERT(fd != -1); FD_close (fd);
	uint32_t count =  GET_U4(&buf, &len);
	while (count > 0) {
		uint8_t  HASH[HASH_LEN];
		uint32_t IP;
		uint16_t UDP;
		uint8_t  TYPE;
		GET_HASH(&buf, &len, HASH);
		IP   = GET_U4 (&buf, &len);
		UDP  = GET_U2 (&buf, &len);
		TYPE = GET_U1 (&buf, &len);
		add(HASH, IP, UDP, TYPE);
		if (len == 0) break;
		count--;
		}
	}}}

cZone:: cZone() {{{
	uint8_t zero[HASH_LEN];
	bzero(zero, HASH_LEN);
	init(NULL, 0, zero);
	smallTimer = currentTime + 600 + (rand() % 1800);
	}}}
cZone:: cZone(class cZone *super_zone, int level, const uint8_t *zone_index) {{{
	init(super_zone, level, zone_index);
	}}}
void   cZone::init(class cZone *super_zone, int level, const uint8_t *zone_index) {{{
	m_superZone   = super_zone;
	m_level       = level;
	memcpy(m_zoneIndex, zone_index, HASH_LEN);
	m_subZones[0] = NULL;
	m_subZones[1] = NULL;
	m_bin         = new cBucket();
//	if (super_zone == NULL) m_lastSmallTimer = time(NULL) + 20;
//	m_lastSmallTimer += 2;
//	m_nextSmallTimer = m_lastSmallTimer;
	if (m_superZone == NULL) readFile();
	}}}
bool   cZone::canSplit(void) const {{{
	if (m_level >= 127) return false;
	if (0 > memcmp(m_zoneIndex, acht, HASH_LEN)) return true;       // Check if we are close to the center
	return areWeInFirstSubtreeOfEnoughSize();   // Check if we need to split to keep the vicinity consistent
	}}}
bool   cZone::areWeInFirstSubtreeOfEnoughSize(void) const {{{
	if (0 == memcmp(m_zoneIndex, null, HASH_LEN)) {
		class cZone *z = m_subZones[0];
		if (z == NULL || z->getNumContacts() < OVERNET_BUCKET) return true;
		return false;
		} 
	ASSERT(m_superZone != NULL);
	return m_superZone->areWeInFirstSubtreeOfEnoughSize();
	}}}
size_t cZone::getNumContacts(void) const {{{
	if (isLeaf()) return m_bin->getSize();
	return m_subZones[0]->getNumContacts() + m_subZones[1]->getNumContacts();
	}}}
bool   cZone::add(const uint8_t *ID, uint32_t IP, uint16_t UDP, uint8_t TYPE) {{{
	struct in_addr ip;
	ip.s_addr = IP;
	if (!IP_is_OK(ip)) return false;
	if (0 == memcmp(ID, this_hash, HASH_LEN)) return false;
	uint8_t distance[HASH_LEN];
	memcpy(distance, this_hash, HASH_LEN);
	xor_128 (distance, ID);
	if (!isLeaf()) return m_subZones[getBit(distance, m_level)]->add(ID, IP, UDP, TYPE);
	class cPeer *c = m_bin->getContact(ID);
	if (c != NULL) {{{
		c->ip   = IP;
		c->udp  = UDP;
		c->type = TYPE;
		return true;
		}}}

	bool retVal = false;
	if (m_bin->getRemaining() > 0) {
		c = new cPeer(ID, IP, UDP, TYPE);
		retVal = m_bin->add(c);
		}
		else 
	if (canSplit()) {
		split();
		retVal = m_subZones[getBit(distance, m_level)]->add(ID, IP, UDP, TYPE);
		}
	else {
		merge();
		c = new cPeer(ID, IP, UDP, TYPE);
		retVal = m_bin->add(c);
		}
	if (retVal) return true;
	if (c != NULL) delete c;
	return false;
	}}}
void   cZone::split(void) {{{
	m_subZones[0] = genSubZone(0);
	m_subZones[1] = genSubZone(1);
	cPeerList entries;
	m_bin->getContacts(&entries);
	cPeerList::const_iterator it;
	for (it = entries.begin(); it != entries.end(); it++) {
		int sz = getBit(((*it)->get_Hash())->hash, m_level);
		m_subZones[sz]->m_bin->add(*it);
		}
	m_bin->dontDeleteContacts = true;
	delete m_bin;
	m_bin = NULL;
	}}}
void   cZone::merge(void) {{{
	if (isLeaf() && m_superZone != NULL) {
		m_superZone->merge();
		return;
		}
	if (isLeaf()) return;
	if ( getNumContacts() >= (OVERNET_BUCKET/2)) return;
	if (!m_subZones[0]->isLeaf()) return;
	if (!m_subZones[1]->isLeaf()) return;
	m_bin = new cBucket();
	if (getNumContacts() > 0) {
		cPeerList list0;
		cPeerList list1;
		m_subZones[0]->m_bin->getContacts(&list0);
		m_subZones[1]->m_bin->getContacts(&list1);
		cPeerList::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;
	if (m_superZone != NULL) m_superZone->merge();
	}}}
class  cZone *cZone::genSubZone(int side) {{{
	uint8_t newIndex[HASH_LEN];
	memcpy(newIndex, m_zoneIndex, HASH_LEN);
	shiftLeft(newIndex,1);
	if (side != 0) add_128(newIndex, eins);

	return new cZone(this, m_level+1, newIndex);
	}}}
void   cZone::setAlive(uint32_t ip, uint16_t port) {{{
	if (isLeaf()) {
		m_bin->setAlive(ip, port);
		return;
		}
	m_subZones[0]->setAlive(ip, port);
	m_subZones[1]->setAlive(ip, port);
	}}}
bool   cZone::contains(const uint8_t *id) const {{{
	if (isLeaf()) return m_bin->contains(id);
	else return m_subZones[getBit(id,m_level)]->contains(id);
	}}}
const  class cPeer* cZone::getContact(const uint8_t *id) const {{{
	if (isLeaf()) return m_bin->getContact(id);
	else return m_subZones[getBit(id,m_level)]->getContact(id);
	}}}
size_t cZone::getApproximateNodeCount(size_t ourLevel) const {{{
	if (isLeaf()) return (1 << ourLevel) * m_bin->getSize();
	return (m_subZones[0]->getApproximateNodeCount(ourLevel+1) + m_subZones[1]->getApproximateNodeCount(ourLevel+1)) / 2;
	}}}
void   cZone::onBigTimer(void) {{{
	if (!isLeaf()) return;
	randomLookup();
	}}}
void   cZone::randomLookup(void) {{{
	uint8_t prefix[HASH_LEN];
	memcpy(prefix, m_zoneIndex, HASH_LEN);
	shiftLeft(prefix, 128 - m_level);
	random(prefix, m_level);
	xor_128(prefix, this_hash);
	cSearchManager::findNode(prefix);
        }}}
void   cZone::consolidate(void) {{{
	if (m_superZone == NULL) return;
	if (isLeaf()) {
		m_superZone->consolidate();
		return;
		}
	if (canSplit()) return;
	if (!m_subZones[0]->isLeaf()) return;
	if (!m_subZones[1]->isLeaf()) return;
	if (!(m_subZones[0]->m_bin->getRemaining() < 1 || m_subZones[1]->m_bin->getRemaining() < 1) ) return;
	if (m_superZone != NULL) m_superZone->consolidate();
	}}}
void   cZone::onSmallTimer(void) {{{
	if (!isLeaf()) {
		if (m_subZones[0] != NULL) m_subZones[0]->onSmallTimer();
		if (m_subZones[1] != NULL) m_subZones[1]->onSmallTimer();
		return;
		}
	if (smallTimer > currentTime) return;	
	smallTimer = currentTime + 600 + (rand() % 1800);
	time_t now = time(NULL);
	cPeerList entries;
	cPeerList::iterator it;
	m_bin->getContacts(&entries);	// Remove dead entries
	cPeer *c = NULL;
	for (it = entries.begin(); it != entries.end(); it++) {
		c = *it;
		if ((c->expires > 0) && (c->expires <= now)) {
			m_bin->remove(c); 
			delete c;
			}
		c = NULL;
		if (m_bin->getRemaining() == 0) {
			c = m_bin->getOldest(); 	// If bin is full, ping oldest entry
			continue;
			}
		if (m_bin->getSize() > 0) {    		// If haven't heard from oldest this session, ping now
			c = m_bin->getOldest();		// If haven't heard from oldest this session, ping now
			if (c->madeContact) c = NULL;
			}
		}
	if (c != NULL) {{{				// Test if client is alive
		c->expires = now;
		size_t len, LEN = len = 25;
		unsigned char BUF[25], *buf = BUF;
		ADD_U1   (&buf, &len, OP_EDONKEYHEADER);
		ADD_U1   (&buf, &len, OVERNET_HELLO_REQUEST);
		ADD_HASH (&buf, &len, this_hash);
		ADD_U4	 (&buf, &len, cSocket::getLocalExternalIP().s_addr);
		ADD_U2	 (&buf, &len, pref.ports.kademlia);
		ADD_U1	 (&buf, &len, 0);
		ASSERT(len == 0);
		struct in_addr ip;
		ip.s_addr = c->ip;
		kademlia->send_Raw(ip, c->udp, BUF, LEN);
		}}}
	}}}
size_t cZone::getMaxDepth(void) const {{{
	if (isLeaf()) return 0;
	size_t a = m_subZones[0]->getMaxDepth();
	size_t b = m_subZones[1]->getMaxDepth();
	if (a < b) 	return b + 1;
			return a + 1;
	}}}
void   cZone::randomBin(cPeerList *result, bool emptyFirst) {{{
	if (!isLeaf()) {
		m_subZones[rand()&1]->randomBin(result, emptyFirst);
		return;
		}
	m_bin->getContacts(result, emptyFirst);
	}}}
void   cZone::topDepth(int depth, cPeerList *result, bool emptyFirst) {{{
	if (isLeaf()) {
		m_bin->getContacts(result, emptyFirst);
		return;
		}
	if (depth <= 0) {
		randomBin(result, emptyFirst);
		return;
		}
	m_subZones[0]->topDepth(depth-1, result, emptyFirst);
	m_subZones[1]->topDepth(depth-1, result, false);
	}}}
void   cZone::getAllEntries(cPeerList *result, bool emptyFirst) {{{
	if (isLeaf()) {
		m_bin->getContacts(result, emptyFirst);
		return;
		}
	m_subZones[0]->getAllEntries(result, emptyFirst);
	m_subZones[1]->getAllEntries(result, false);            
	}}}
size_t cZone::getClosestTo(const uint8_t *target, size_t maxRequired, cPeerMap *result, bool emptyFirst) const {{{
	// If leaf zone, do it here
	if (isLeaf()) return m_bin->getClosest(target, maxRequired, result, emptyFirst);
	// otherwise, recurse in the closer-to-the-target subzone first
	int closer = getBit(target, m_level);
	size_t found = m_subZones[closer]->getClosestTo(target, maxRequired, result, emptyFirst);
	// if still not enough tokens found, recurse in the other subzone too
	if (found < maxRequired) found += m_subZones[1-closer]->getClosestTo(target, maxRequired-found, result, false);
	return found;
	}}}
size_t cZone::getBootstrapContacts(cPeerList *results, size_t maxRequired) {{{
	if (m_superZone == NULL) return 0;
	results->clear();
	size_t retVal = 0;
	cPeerList top;
	topDepth(5, &top);
	if (top.size() > 0) {
		cPeerList::const_iterator it;
		for (it = top.begin(); it != top.end(); it++) {
			results->push_back(*it);
			retVal++;
			if (retVal == maxRequired) break;
			}
		}
	return retVal;
	}}}


#include "misc.h"
void cZone::dumpContents(const char *prefix) const {{{
	char ZoneIndex[33];
	sprintf(ZoneIndex, "%32s", hash_bin2hex(m_zoneIndex));
	if (prefix == NULL) printf("------------------------------------------------------\n");
	if (isLeaf()) {
		printf("Zone level: %i\tZone prefix: %s\tContacts: %i\tZoneIndex: %s\n", 
				m_level, (prefix == NULL) ? "ROOT" : prefix, getNumContacts(), ZoneIndex);
		m_bin->dumpContents();
		}
	else {
		printf("Zone level: %i\tZone prefix: %s\tContacts: %i\tZoneIndex: %s NODE\n", 
				m_level, (prefix == NULL) ? "ROOT" : prefix, getNumContacts(), ZoneIndex);
		char msg[512];
		sprintf(msg, "%s0", (prefix == NULL) ? "" : prefix);
		m_subZones[0]->dumpContents(msg);
		sprintf(msg, "%s1", (prefix == NULL) ? "" : prefix);
		m_subZones[1]->dumpContents(msg);
		}
	}}}