3
Copyright (c) 2006, Arvid Norberg
6
Redistribution and use in source and binary forms, with or without
7
modification, are permitted provided that the following conditions
10
* Redistributions of source code must retain the above copyright
11
notice, this list of conditions and the following disclaimer.
12
* Redistributions in binary form must reproduce the above copyright
13
notice, this list of conditions and the following disclaimer in
14
the documentation and/or other materials provided with the distribution.
15
* Neither the name of the author nor the names of its
16
contributors may be used to endorse or promote products derived
17
from this software without specific prior written permission.
19
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29
POSSIBILITY OF SUCH DAMAGE.
33
#ifndef ROUTING_TABLE_HPP
34
#define ROUTING_TABLE_HPP
38
#include <boost/cstdint.hpp>
40
#include <boost/iterator/iterator_facade.hpp>
41
#include <boost/iterator/iterator_categories.hpp>
42
#include <boost/utility.hpp>
43
#include <boost/tuple/tuple.hpp>
44
#include <boost/array.hpp>
47
#include <libtorrent/kademlia/logging.hpp>
49
#include <libtorrent/kademlia/node_id.hpp>
50
#include <libtorrent/kademlia/node_entry.hpp>
51
#include <libtorrent/session_settings.hpp>
52
#include <libtorrent/size_type.hpp>
53
#include <libtorrent/assert.hpp>
55
namespace libtorrent { namespace dht
60
//TORRENT_DECLARE_LOG(table);
62
typedef std::vector<node_entry> bucket_t;
64
// differences in the implementation from the description in
67
// * The routing table tree is not allocated dynamically, there
68
// are always 160 buckets.
69
// * Nodes are not marked as being stale, they keep a counter
70
// that tells how many times in a row they have failed. When
71
// a new node is to be inserted, the node that has failed
72
// the most times is replaced. If none of the nodes in the
73
// bucket has failed, then it is put in the replacement
74
// cache (just like in the paper).
81
// Iterates over a flattened routing_table structure.
82
class routing_table_iterator
83
: public boost::iterator_facade<
84
routing_table_iterator
86
, boost::forward_traversal_tag
90
routing_table_iterator()
95
friend class libtorrent::dht::routing_table;
96
friend class boost::iterator_core_access;
98
typedef boost::array<std::pair<bucket_t, bucket_t>, 160>::const_iterator
101
routing_table_iterator(
102
bucket_iterator_t begin
103
, bucket_iterator_t end)
104
: m_bucket_iterator(begin)
106
, m_iterator(begin != end ? begin->first.begin() : bucket_t::const_iterator())
108
if (m_bucket_iterator == m_bucket_end) return;
109
while (m_iterator == m_bucket_iterator->first.end())
111
if (++m_bucket_iterator == m_bucket_end)
113
m_iterator = m_bucket_iterator->first.begin();
117
bool equal(routing_table_iterator const& other) const
119
return m_bucket_iterator == other.m_bucket_iterator
120
&& (m_bucket_iterator == m_bucket_end
121
|| m_iterator == other.m_iterator);
126
TORRENT_ASSERT(m_bucket_iterator != m_bucket_end);
128
while (m_iterator == m_bucket_iterator->first.end())
130
if (++m_bucket_iterator == m_bucket_end)
132
m_iterator = m_bucket_iterator->first.begin();
136
node_entry const& dereference() const
138
TORRENT_ASSERT(m_bucket_iterator != m_bucket_end);
142
bucket_iterator_t m_bucket_iterator;
143
bucket_iterator_t m_bucket_end;
144
bucket_t::const_iterator m_iterator;
152
typedef aux::routing_table_iterator iterator;
153
typedef iterator const_iterator;
155
routing_table(node_id const& id, int bucket_size
156
, dht_settings const& settings);
158
void node_failed(node_id const& id);
160
// adds an endpoint that will never be added to
162
void add_router_node(udp::endpoint router);
164
// iterates over the router nodes added
165
typedef std::set<udp::endpoint>::const_iterator router_iterator;
166
router_iterator router_begin() const { return m_router_nodes.begin(); }
167
router_iterator router_end() const { return m_router_nodes.end(); }
169
// this function is called every time the node sees
170
// a sign of a node being alive. This node will either
171
// be inserted in the k-buckets or be moved to the top
173
bool node_seen(node_id const& id, udp::endpoint addr);
175
// returns time when the given bucket needs another refresh.
176
// if the given bucket is empty but there are nodes
177
// in a bucket closer to us, or if the bucket is non-empty and
178
// the time from the last activity is more than 15 minutes
179
ptime next_refresh(int bucket);
181
// fills the vector with the count nodes from our buckets that
182
// are nearest to the given id.
183
void find_node(node_id const& id, std::vector<node_entry>& l
184
, bool include_self, int count = 0);
186
// returns true if the given node would be placed in a bucket
187
// that is not full. If the node already exists in the table
188
// this function returns false
189
bool need_node(node_id const& id);
191
// this will set the given bucket's latest activity
192
// to the current time
193
void touch_bucket(int bucket);
195
int bucket_size(int bucket)
197
TORRENT_ASSERT(bucket >= 0 && bucket < 160);
198
return (int)m_buckets[bucket].first.size();
200
int bucket_size() const { return m_bucket_size; }
202
iterator begin() const;
203
iterator end() const;
205
boost::tuple<int, int> size() const;
206
size_type num_global_nodes() const;
208
// returns true if there are no working nodes
209
// in the routing table
210
bool need_bootstrap() const;
211
int num_active_buckets() const
212
{ return 160 - m_lowest_active_bucket + 1; }
214
void replacement_cache(bucket_t& nodes) const;
215
#ifdef TORRENT_DHT_VERBOSE_LOGGING
216
// used for debug and monitoring purposes. This will print out
217
// the state of the routing table to the given stream
218
void print_state(std::ostream& os) const;
223
// constant called k in paper
226
dht_settings const& m_settings;
228
// 160 (k-bucket, replacement cache) pairs
229
typedef boost::array<std::pair<bucket_t, bucket_t>, 160> table_t;
231
// timestamps of the last activity in each bucket
232
typedef boost::array<ptime, 160> table_activity_t;
233
table_activity_t m_bucket_activity;
234
node_id m_id; // our own node id
236
// this is a set of all the endpoints that have
237
// been identified as router nodes. They will
238
// be used in searches, but they will never
239
// be added to the routing table.
240
std::set<udp::endpoint> m_router_nodes;
242
// this is the lowest bucket index with nodes in it
243
int m_lowest_active_bucket;
246
} } // namespace libtorrent::dht
248
#endif // ROUTING_TABLE_HPP
added
removed
include/libtorrent/kademlia/routing_table.hpp
