My Project 1.7.4
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
24namespace dht {
25
26static constexpr unsigned TARGET_NODES {8};
27namespace net {
28class NetworkEngine;
29}
30
31struct 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};
46
47class RoutingTable : public std::list<Bucket> {
48public:
49 using std::list<Bucket>::list;
50
51 time_point grow_time {time_point::min()};
52 bool is_client {false};
53
54 InfoHash middle(const RoutingTable::const_iterator&) const;
55
56 std::vector<Sp<Node>> findClosestNodes(const InfoHash id, time_point now, size_t count = TARGET_NODES) const;
57
58 RoutingTable::iterator findBucket(const InfoHash& id);
59 RoutingTable::const_iterator findBucket(const InfoHash& id) const;
60
64 inline bool contains(const RoutingTable::const_iterator& bucket, const InfoHash& id) const {
65 return InfoHash::cmp(bucket->first, id) <= 0
66 && (std::next(bucket) == end() || InfoHash::cmp(id, std::next(bucket)->first) < 0);
67 }
68
72 inline bool isEmpty() const {
73 return empty() || (size() == 1 && front().nodes.empty());
74 }
75
76 void connectivityChanged(const time_point& now) {
77 grow_time = now;
78 for (auto& b : *this)
79 b.time = time_point::min();
80 }
81
82 bool onNewNode(const Sp<Node>& node, int comfirm, const time_point& now, const InfoHash& myid, net::NetworkEngine& ne);
83
87 InfoHash randomId(const RoutingTable::const_iterator& bucket) const;
88
89 unsigned depth(const RoutingTable::const_iterator& bucket) const;
90
94 bool split(const RoutingTable::iterator& b);
95};
96
97}
static int cmp(const Hash &id1, const Hash &id2)
Definition: infohash.h:149
bool contains(const RoutingTable::const_iterator &bucket, const InfoHash &id) const
Definition: routing_table.h:64
bool isEmpty() const
Definition: routing_table.h:72
bool split(const RoutingTable::iterator &b)
InfoHash randomId(const RoutingTable::const_iterator &bucket) const
An abstraction of communication protocol on the network.
Definition: callbacks.h:34
Sp< Node > randomNode()