C++ Distributed Hash Table
routing_table.h
1 /*
2  * Copyright (C) 2014-2017 Savoir-faire Linux Inc.
3  * Author(s) : Adrien BĂ©raud <adrien.beraud@savoirfairelinux.com>
4  * Simon DĂ©saulniers <simon.desaulniers@savoirfairelinux.com>
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program. If not, see <https://www.gnu.org/licenses/>.
18  */
19 
20 #pragma once
21 
22 #include "node.h"
23 
24 namespace dht {
25 
26 static constexpr unsigned TARGET_NODES {8};
27 namespace net {
28 class NetworkEngine;
29 }
30 
31 struct Bucket {
32  Bucket() : cached() {}
33  Bucket(sa_family_t af, const InfoHash& f = {}, time_point t = time_point::min())
34  : af(af), first(f), time(t), cached() {}
35  sa_family_t af {0};
36  InfoHash first {};
37  time_point time {time_point::min()}; /* time of last reply in this bucket */
38  std::list<Sp<Node>> nodes {};
39  Sp<Node> cached; /* the address of a likely candidate */
40 
42  Sp<Node> randomNode();
43 
44  void sendCachedPing(net::NetworkEngine& ne);
45  void connectivityChanged() {
46  time = time_point::min();
47  for (auto& node : nodes)
48  node->setTime(time_point::min());
49  }
50 };
51 
52 class RoutingTable : public std::list<Bucket> {
53 public:
54  using std::list<Bucket>::list;
55 
56  time_point grow_time {time_point::min()};
57  bool is_client {false};
58 
59  InfoHash middle(const RoutingTable::const_iterator&) const;
60 
61  std::vector<Sp<Node>> findClosestNodes(const InfoHash id, time_point now, size_t count = TARGET_NODES) const;
62 
63  RoutingTable::iterator findBucket(const InfoHash& id);
64  RoutingTable::const_iterator findBucket(const InfoHash& id) const;
65 
69  inline bool contains(const RoutingTable::const_iterator& bucket, const InfoHash& id) const {
70  return InfoHash::cmp(bucket->first, id) <= 0
71  && (std::next(bucket) == end() || InfoHash::cmp(id, std::next(bucket)->first) < 0);
72  }
73 
77  inline bool isEmpty() const {
78  return empty() || (size() == 1 && front().nodes.empty());
79  }
80 
81  void connectivityChanged(const time_point& now) {
82  grow_time = now;
83  for (auto& b : *this)
84  b.connectivityChanged();
85  }
86 
87  bool onNewNode(const Sp<Node>& node, int comfirm, const time_point& now, const InfoHash& myid, net::NetworkEngine& ne);
88 
92  InfoHash randomId(const RoutingTable::const_iterator& bucket) const;
93 
94  unsigned depth(const RoutingTable::const_iterator& bucket) const;
95 
99  bool split(const RoutingTable::iterator& b);
100 };
101 
102 }
bool contains(const RoutingTable::const_iterator &bucket, const InfoHash &id) const
Definition: routing_table.h:69
An abstraction of communication protocol on the network.
static int cmp(const Hash &id1, const Hash &id2)
Definition: infohash.h:149
Sp< Node > randomNode()
bool split(const RoutingTable::iterator &b)
InfoHash randomId(const RoutingTable::const_iterator &bucket) const
bool isEmpty() const
Definition: routing_table.h:77
Definition: callbacks.h:34