1 /* <!-- copyright */
2 /*
3  * aria2 - The high speed download utility
4  *
5  * Copyright (C) 2006 Tatsuhiro Tsujikawa
6  *
7  * This program is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  *
21  * In addition, as a special exception, the copyright holders give
22  * permission to link the code of portions of this program with the
23  * OpenSSL library under certain conditions as described in each
24  * individual source file, and distribute linked combinations
25  * including the two.
26  * You must obey the GNU General Public License in all respects
27  * for all of the code used other than OpenSSL.  If you modify
28  * file(s) with this exception, you may extend this exception to your
29  * version of the file(s), but you are not obligated to do so.  If you
30  * do not wish to do so, delete this exception statement from your
31  * version.  If you delete this exception statement from all source
32  * files in the program, then also delete it here.
33  */
34 /* copyright --> */
35 #ifndef D_DHT_BUCKET_H
36 #define D_DHT_BUCKET_H
37 
38 #include "common.h"
39 
40 #include <string>
41 #include <deque>
42 #include <vector>
43 #include <memory>
44 
45 #include "DHTConstants.h"
46 #include "TimerA2.h"
47 
48 namespace aria2 {
49 
50 class DHTNode;
51 
52 class DHTBucket {
53 private:
54   size_t prefixLength_;
55 
56   // this bucket contains nodes of distance between [min_, max_](inclusive).
57   unsigned char min_[DHT_ID_LENGTH];
58 
59   unsigned char max_[DHT_ID_LENGTH];
60 
61   std::shared_ptr<DHTNode> localNode_;
62 
63   // sorted in ascending order
64   std::deque<std::shared_ptr<DHTNode>> nodes_;
65 
66   // a replacement cache. The maximum size is specified by CACHE_SIZE.
67   // This is sorted by last time seen.
68   std::deque<std::shared_ptr<DHTNode>> cachedNodes_;
69 
70   Timer lastUpdated_;
71 
72   bool isInRange(const unsigned char* nodeID, const unsigned char* max,
73                  const unsigned char* min) const;
74 
75 public:
76   DHTBucket(const std::shared_ptr<DHTNode>& localNode);
77 
78   DHTBucket(size_t prefixLength, const unsigned char* max,
79             const unsigned char* min,
80             const std::shared_ptr<DHTNode>& localNode);
81 
82   ~DHTBucket();
83 
84   static const size_t K = 8;
85 
86   static const size_t CACHE_SIZE = 2;
87 
88   void getRandomNodeID(unsigned char* nodeID) const;
89 
90   std::unique_ptr<DHTBucket> split();
91 
92   bool isInRange(const std::shared_ptr<DHTNode>& node) const;
93 
94   bool isInRange(const unsigned char* nodeID) const;
95 
96   bool addNode(const std::shared_ptr<DHTNode>& node);
97 
98   void cacheNode(const std::shared_ptr<DHTNode>& node);
99 
100   bool splitAllowed() const;
101 
getPrefixLength()102   size_t getPrefixLength() const { return prefixLength_; }
103 
getMaxID()104   const unsigned char* getMaxID() const { return max_; }
105 
getMinID()106   const unsigned char* getMinID() const { return min_; }
107 
countNode()108   size_t countNode() const { return nodes_.size(); }
109 
getNodes()110   const std::deque<std::shared_ptr<DHTNode>>& getNodes() const
111   {
112     return nodes_;
113   }
114 
115   void getGoodNodes(std::vector<std::shared_ptr<DHTNode>>& nodes) const;
116 
117   void dropNode(const std::shared_ptr<DHTNode>& node);
118 
119   void moveToHead(const std::shared_ptr<DHTNode>& node);
120 
121   void moveToTail(const std::shared_ptr<DHTNode>& node);
122 
123   bool contains(const std::shared_ptr<DHTNode>& node) const;
124 
125   std::shared_ptr<DHTNode> getNode(const unsigned char* nodeID,
126                                    const std::string& ipaddr,
127                                    uint16_t port) const;
128 
129   bool operator==(const DHTBucket& bucket) const;
130 
131   bool needsRefresh() const;
132 
133   void notifyUpdate();
134 
135   bool containsQuestionableNode() const;
136 
137   std::shared_ptr<DHTNode> getLRUQuestionableNode() const;
138 
getCachedNodes()139   const std::deque<std::shared_ptr<DHTNode>>& getCachedNodes() const
140   {
141     return cachedNodes_;
142   }
143 };
144 
145 } // namespace aria2
146 
147 #endif // D_DHT_BUCKET_H
148