1 /*
2  *  Copyright (C) 2014-2019 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 {
BucketBucket32     Bucket() : cached() {}
33     Bucket(sa_family_t af, const InfoHash& f = {}, time_point t = time_point::min())
afBucket34         : 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 
41     /** Return a random node in a bucket. */
42     Sp<Node> randomNode();
43 
44     void sendCachedPing(net::NetworkEngine& ne);
connectivityChangedBucket45     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 
66     /**
67      * Return true if the id is in the bucket's range.
68      */
contains(const RoutingTable::const_iterator & bucket,const InfoHash & id)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 
74     /**
75      * Return true if the table has no bucket ore one empty buket.
76      */
isEmpty()77     inline bool isEmpty() const {
78         return empty() || (size() == 1 && front().nodes.empty());
79     }
80 
connectivityChanged(const time_point & now)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 
89     /**
90      * Return a random id in the bucket's range.
91      */
92     InfoHash randomId(const RoutingTable::const_iterator& bucket) const;
93 
94     unsigned depth(const RoutingTable::const_iterator& bucket) const;
95 
96     /**
97      * Split a bucket in two equal parts.
98      */
99     bool split(const RoutingTable::iterator& b);
100 };
101 
102 }
103