src/kademlia/routing/RoutingZone.h

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2004-2008 Angel Vidal (Kry) ( kry@amule.org )
   5 // Copyright (c) 2004-2008 aMule Team ( admin@amule.org / http://www.amule.org )
   6 // Copyright (c) 2003 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 ////////////////////////////////////////
  46 namespace Kademlia {
  47 ////////////////////////////////////////
  48
  49 class CRoutingBin;
  50 //class CPing;
  51 class CContact;
  52
  53 /**
  54  * The *Zone* is just a node in a binary tree of *Zone*s.
  55  * Each zone is either an internal node or a leaf node.
  56  * Internal nodes have "bin == null" and "subZones[i] != null",
  57  * leaf nodes have "subZones[i] == null" and "bin != null".
  58  *
  59  * All key pseudoaddresses are relative to the center (self), which
  60  * is considered to be 000..000
  61  */
  62 class CRoutingZone
  63 {
  64         //friend CRoutingZone;
  65 public:
  66
  67         CRoutingZone();
  68         ~CRoutingZone();
  69
  70         time_t m_nextBigTimer;
  71         time_t m_nextSmallTimer;
  72         bool OnBigTimer(void);
  73         void OnSmallTimer(void);
  74
  75         bool Add(const CUInt128 &id, uint32 ip, uint16 port, uint16 tport, byte type);
  76         void Remove(const CUInt128 &id);
  77         void SetAlive(uint32 ip, uint16 port);
  78
  79         CContact *GetContact(const CUInt128 &id) const;
  80         uint32 GetNumContacts(void) const;
  81
  82         // Returns a list of all contacts in all leafs of this zone.
  83         void GetAllEntries(ContactList *result, bool emptyFirst = true);
  84
  85         // Returns the *maxRequired* tokens that are closest to the target within this zone's subtree.
  86         void GetClosestTo(uint32 maxType, const CUInt128 &target, const CUInt128 &distance, uint32 maxRequired, ContactMap *result, bool emptyFirst = true, bool setInUse = false) const;
  87
  88         // Ideally: Returns all contacts that are in buckets of common range between us and the asker.
  89         // In practice: returns the contacts from the top (2^{logBase+1}) buckets.
  90         uint32 GetBootstrapContacts(ContactList *results, uint32 maxRequired);
  91
  92         /** Debugging. */
  93 //      void dumpContents(LPCTSTR prefix = NULL) const;
  94 //      void selfTest(void);
  95
  96 //      uint64 getApproximateNodeCount(uint32 ourLevel) const;
  97
  98         bool IsDirty() const { return dirty; }
  99
 100         uint32 EstimateCount();
 101
 102         void Merge(void);
 103
 104 private:
 105
 106         CRoutingZone(CRoutingZone *super_zone, int level, const CUInt128 &zone_index);
 107         void Init(CRoutingZone *super_zone, int level, const CUInt128 &zone_index);
 108
 109         bool AddByDistance(const CUInt128 &distance, const CUInt128 &id, uint32 ip, uint16 port, uint16 tport, byte type);
 110
 111         /**
 112          * Zone pair is an array of two. Either both entries are null, which
 113          * means that *this* is a leaf zone, or both are non-null which means
 114          * that *this* has been split into equally sized finer zones.
 115          * The zone with index 0 is the one closer to our *self* token.
 116          */
 117         CRoutingZone *m_subZones[2];
 118         CRoutingZone *m_superZone;
 119
 120         static wxString m_filename;
 121         static CUInt128 me;
 122
 123         void ReadFile(void);
 124         void WriteFile(void);
 125
 126         bool IsLeaf(void) const;
 127         bool CanSplit(void) const;
 128
 129         // Returns all contacts from this zone tree that are no deeper than *depth* from the current zone.
 130         void TopDepth(int depth, ContactList *result, bool emptyFirst = true);
 131
 132         // Returns the maximum depth of the tree as the number of edges of the longest path to a leaf.
 133         uint32 GetMaxDepth(void) const;
 134
 135         void RandomBin(ContactList *result, bool emptyFirst = true);
 136
 137         /**
 138          * The level indicates what size chunk of the address space
 139          * this zone is representing. Level 0 is the whole space,
 140          * level 1 is 1/2 of the space, level 2 is 1/4, etc.
 141          */
 142         uint32 m_level;
 143
 144         /**
 145          * This is the distance in number of zones from the zone at this level
 146          * that contains the center of the system; distance is wrt the XOR metric.
 147          */
 148         CUInt128 m_zoneIndex;
 149
 150         /** List of contacts, if this zone is a leaf zone. */
 151         CRoutingBin *m_bin;
 152
 153         /**
 154          * Generates a new TokenBin for this zone. Used when the current zone is becoming a leaf zone.
 155          * Must be deleted by caller
 156          */
 157         CRoutingZone *GenSubZone(int side);
 158
 159         void Split(void);
 160
 161         void StartTimer(void);
 162         void StopTimer(void);
 163
 164         void RandomLookup(void);
 165
 166         bool dirty;
 167 };
 168
 169 } // End namespace
 170
 171 #endif // __ROUTING_ZONE__
 172 // File_checked_for_headers