src/kademlia/routing/RoutingZone.h

   1 //                                                              -*- C++ -*-
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2004-2008 Angel Vidal ( kry@amule.org )
   5 // Copyright (c) 2004-2008 aMule Team ( admin@amule.org / http://www.amule.org )
   6 // Copyright (c) 2003-2008 Barry Dunne (http://www.emule-project.net)
   7 //
   8 // Any parts of this program derived from the xMule, lMule or eMule project,
   9 // or contributed by third-party developers are copyrighted by their
  10 // respective authors.
  11 //
  12 // This program is free software; you can redistribute it and/or modify
  13 // it under the terms of the GNU General Public License as published by
  14 // the Free Software Foundation; either version 2 of the License, or
  15 // (at your option) any later version.
  16 //
  17 // This program is distributed in the hope that it will be useful,
  18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 // GNU General Public License for more details.
  21 //
  22 // You should have received a copy of the GNU General Public License
  23 // along with this program; if not, write to the Free Software
  24 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  25 //
  26
  27 // Note To Mods //
  28 /*
  29 Please do not change anything here and release it..
  30 There is going to be a new forum created just for the Kademlia side of the client..
  31 If you feel there is an error or a way to improve something, please
  32 post it in the forum first and let us look at it.. If it is a real improvement,
  33 it will be added to the offical client.. Changing something without knowing
  34 what all it does can cause great harm to the network if released in mass form..
  35 Any mod that changes anything within the Kademlia side will not be allowed to advertise
  36 there client on the eMule forum..
  37 */
  38
  39 #ifndef __ROUTING_ZONE__
  40 #define __ROUTING_ZONE__
  41
  42 #include "Maps.h"
  43 #include "../utils/UInt128.h"
  44
  45 class CFileDataIO;
  46
  47 ////////////////////////////////////////
  48 namespace Kademlia {
  49 ////////////////////////////////////////
  50
  51 class CRoutingBin;
  52 class CContact;
  53 class CKadUDPKey;
  54
  55 /**
  56  * The *Zone* is just a node in a binary tree of *Zone*s.
  57  * Each zone is either an internal node or a leaf node.
  58  * Internal nodes have "bin == null" and "subZones[i] != null",
  59  * leaf nodes have "subZones[i] == null" and "bin != null".
  60  *
  61  * All key pseudoaddresses are relative to the center (self), which
  62  * is considered to be 000..000
  63  */
  64 class CRoutingZone
  65 {
  66 public:
  67
  68         CRoutingZone();
  69         ~CRoutingZone();
  70
  71         bool     OnBigTimer() const;
  72         void     OnSmallTimer();
  73         uint32_t Consolidate();
  74
  75         bool     Add(const CUInt128 &id, uint32_t ip, uint16_t port, uint16_t tport, uint8_t version, const CKadUDPKey& key, bool& ipVerified, bool update, bool fromHello);
  76         bool     AddUnfiltered(const CUInt128 &id, uint32_t ip, uint16_t port, uint16_t tport, uint8_t version, const CKadUDPKey& key, bool& ipVerified, bool update, bool fromHello);
  77         bool     Add(CContact *contact, bool& update, bool& outIpVerified);
  78
  79         void     ReadFile(const wxString& specialNodesdat = wxEmptyString);
  80
  81         bool     VerifyContact(const CUInt128& id, uint32_t ip);
  82         CContact *GetContact(const CUInt128& id) const throw();
  83         CContact *GetContact(uint32_t ip, uint16_t port, bool tcpPort) const throw();
  84         CContact *GetRandomContact(uint32_t maxType, uint32_t minKadVersion) const;
  85         uint32_t GetNumContacts() const throw();
  86         void     GetNumContacts(uint32_t& nInOutContacts, uint32_t& nInOutFilteredContacts, uint8_t minVersion) const throw();
  87
  88         // Check if we know a contact with the same IP or ID but not matching IP/ID and other limitations, similar checks like when adding a node to the table except allowing duplicates
  89         bool    IsAcceptableContact(const CContact *toCheck) const;
  90
  91         // Returns a list of all contacts in all leafs of this zone.
  92         void     GetAllEntries(ContactList *result, bool emptyFirst = true) const;
  93
  94         // Returns the *maxRequired* tokens that are closest to the target within this zone's subtree.
  95         void     GetClosestTo(uint32_t maxType, const CUInt128& target, const CUInt128& distance, uint32_t maxRequired, ContactMap *result, bool emptyFirst = true, bool setInUse = false) const;
  96
  97         // Ideally: Returns all contacts that are in buckets of common range between us and the asker.
  98         // In practice: returns the contacts from the top (2^{logBase+1}) buckets.
  99         uint32_t GetBootstrapContacts(ContactList *results, uint32_t maxRequired) const;
 100
 101         uint32_t EstimateCount() const;
 102         bool     HasOnlyLANNodes() const throw();
 103
 104         time_t   m_nextBigTimer;
 105         time_t   m_nextSmallTimer;
 106
 107 private:
 108
 109         CRoutingZone(CRoutingZone *super_zone, int level, const CUInt128& zone_index) { Init(super_zone, level, zone_index); }
 110         void Init(CRoutingZone *super_zone, int level, const CUInt128& zone_index);
 111         void ReadBootstrapNodesDat(CFileDataIO& file);
 112 #if 0
 113         void WriteBootstrapFile();
 114 #endif
 115
 116         void WriteFile();
 117
 118         bool IsLeaf() const throw() { return m_bin != NULL; }
 119         bool CanSplit() const throw();
 120
 121         // Returns all contacts from this zone tree that are no deeper than *depth* from the current zone.
 122         void TopDepth(int depth, ContactList *result, bool emptyFirst = true) const;
 123
 124         // Returns the maximum depth of the tree as the number of edges of the longest path to a leaf.
 125         uint32_t GetMaxDepth() const throw();
 126
 127         void RandomBin(ContactList *result, bool emptyFirst = true) const;
 128
 129         void Split();
 130
 131         void StartTimer();
 132         void StopTimer();
 133
 134         void RandomLookup() const;
 135
 136         void SetAllContactsVerified();
 137
 138         /**
 139          * Generates a new TokenBin for this zone. Used when the current zone is becoming a leaf zone.
 140          * Must be deleted by caller
 141          */
 142         CRoutingZone *GenSubZone(unsigned side);
 143
 144         /**
 145          * Zone pair is an array of two. Either both entries are null, which
 146          * means that *this* is a leaf zone, or both are non-null which means
 147          * that *this* has been split into equally sized finer zones.
 148          * The zone with index 0 is the one closer to our *self* token.
 149          */
 150         CRoutingZone *m_subZones[2];
 151         CRoutingZone *m_superZone;
 152
 153         static wxString m_filename;
 154         static CUInt128 me;
 155
 156         /**
 157          * The level indicates what size chunk of the address space
 158          * this zone is representing. Level 0 is the whole space,
 159          * level 1 is 1/2 of the space, level 2 is 1/4, etc.
 160          */
 161         uint32_t m_level;
 162
 163         /**
 164          * This is the distance in number of zones from the zone at this level
 165          * that contains the center of the system; distance is wrt the XOR metric.
 166          */
 167         CUInt128 m_zoneIndex;
 168
 169         /** List of contacts, if this zone is a leaf zone. */
 170         CRoutingBin *m_bin;
 171 };
 172
 173 } // End namespace
 174
 175 #endif // __ROUTING_ZONE__
 176 // File_checked_for_headers