My Project 3.2.0
C++ Distributed Hash Table
Loading...
Searching...
No Matches
routing_table.h
1/*
2 * Copyright (C) 2014-2023 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(std::mt19937_64& rd);
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
52class RoutingTable : public std::list<Bucket> {
53public:
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, std::mt19937_64& rd) 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
bool isEmpty() const
InfoHash randomId(const RoutingTable::const_iterator &bucket, std::mt19937_64 &rd) const
bool split(const RoutingTable::iterator &b)
An abstraction of communication protocol on the network.
Sp< Node > randomNode(std::mt19937_64 &rd)