LCOV - code coverage report
Current view: top level - foo/src/jamidht/swarm - routing_table.cpp (source / functions) Hit Total Coverage
Test: jami-coverage-filtered.info Lines: 276 365 75.6 %
Date: 2026-04-22 10:25:21 Functions: 44 71 62.0 %

          Line data    Source code
       1             : /*
       2             :  *  Copyright (C) 2004-2026 Savoir-faire Linux Inc.
       3             :  *
       4             :  *  This program is free software: you can redistribute it and/or modify
       5             :  *  it under the terms of the GNU General Public License as published by
       6             :  *  the Free Software Foundation, either version 3 of the License, or
       7             :  *  (at your option) any later version.
       8             :  *
       9             :  *  This program is distributed in the hope that it will be useful,
      10             :  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
      12             :  *  GNU General Public License for more details.
      13             :  *
      14             :  *  You should have received a copy of the GNU General Public License
      15             :  *  along with this program. If not, see <https://www.gnu.org/licenses/>.
      16             :  */
      17             : 
      18             : #include "routing_table.h"
      19             : 
      20             : #include <dhtnet/multiplexed_socket.h>
      21             : #include <opendht/infohash.h>
      22             : #include <opendht/thread_pool.h>
      23             : 
      24             : #include <math.h>
      25             : #include <iterator>
      26             : #include <stdlib.h>
      27             : 
      28             : using namespace std::placeholders;
      29             : 
      30             : namespace jami {
      31             : 
      32             : using namespace dht;
      33             : 
      34         916 : Bucket::Bucket(const NodeId& id)
      35         916 :     : lowerLimit_(id)
      36         916 : {}
      37             : 
      38             : bool
      39        1065 : Bucket::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
      40             : {
      41        1065 :     return addNode(NodeInfo(socket));
      42             : }
      43             : 
      44             : bool
      45        1352 : Bucket::addNode(NodeInfo&& info)
      46             : {
      47        1352 :     auto nodeId = info.socket->deviceId();
      48        1352 :     if (nodes.try_emplace(nodeId, std::move(info)).second) {
      49        1350 :         connecting_nodes.erase(nodeId);
      50        1351 :         known_nodes.erase(nodeId);
      51        1350 :         mobile_nodes.erase(nodeId);
      52        1350 :         return true;
      53             :     }
      54           1 :     return false;
      55             : }
      56             : 
      57             : bool
      58        1068 : Bucket::removeNode(const NodeId& nodeId)
      59             : {
      60        1068 :     auto node = nodes.find(nodeId);
      61        1068 :     auto isMobile = node->second.isMobile_;
      62        1068 :     if (node == nodes.end())
      63           3 :         return false;
      64        1065 :     nodes.erase(nodeId);
      65        1065 :     if (isMobile) {
      66          94 :         addMobileNode(nodeId);
      67             :     } else {
      68         971 :         addKnownNode(nodeId);
      69             :     }
      70             : 
      71        1064 :     return true;
      72             : }
      73             : 
      74             : std::set<NodeId>
      75        2833 : Bucket::getNodeIds() const
      76             : {
      77        2833 :     std::set<NodeId> nodesId;
      78        7965 :     for (auto const& key : nodes)
      79        5154 :         nodesId.insert(key.first);
      80        2829 :     return nodesId;
      81           0 : }
      82             : 
      83             : bool
      84        5609 : Bucket::hasNode(const NodeId& nodeId) const
      85             : {
      86        5609 :     return nodes.find(nodeId) != nodes.end();
      87             : }
      88             : 
      89             : bool
      90        2803 : Bucket::addKnownNode(const NodeId& nodeId)
      91             : {
      92        2803 :     if (!hasNode(nodeId)) {
      93        1989 :         if (known_nodes.emplace(nodeId).second) {
      94        1886 :             return true;
      95             :         }
      96             :     }
      97         915 :     return false;
      98             : }
      99             : 
     100             : NodeId
     101         108 : Bucket::getKnownNode(unsigned index) const
     102             : {
     103         108 :     if (index > known_nodes.size()) {
     104           1 :         throw std::out_of_range("End of table for get known Node Id " + std::to_string(index));
     105             :     }
     106         107 :     auto it = known_nodes.begin();
     107         107 :     std::advance(it, index);
     108             : 
     109         107 :     return *it;
     110             : }
     111             : 
     112             : bool
     113         108 : Bucket::addMobileNode(const NodeId& nodeId)
     114             : {
     115         108 :     if (!hasNode(nodeId)) {
     116         107 :         if (mobile_nodes.emplace(nodeId).second) {
     117         107 :             known_nodes.erase(nodeId);
     118         107 :             return true;
     119             :         }
     120             :     }
     121           1 :     return false;
     122             : }
     123             : 
     124             : bool
     125         950 : Bucket::addConnectingNode(const NodeId& nodeId)
     126             : {
     127         950 :     if (!hasNode(nodeId)) {
     128         949 :         if (connecting_nodes.emplace(nodeId).second) {
     129         910 :             known_nodes.erase(nodeId);
     130         910 :             mobile_nodes.erase(nodeId);
     131         911 :             return true;
     132             :         }
     133             :     }
     134          40 :     return false;
     135             : }
     136             : 
     137             : std::set<NodeId>
     138        1315 : Bucket::getKnownNodesRandom(unsigned numberNodes, std::mt19937_64& rd) const
     139             : {
     140        1315 :     std::set<NodeId> nodesToReturn;
     141             : 
     142        1315 :     if (getKnownNodesSize() <= numberNodes)
     143        1212 :         return getKnownNodes();
     144             : 
     145         104 :     std::uniform_int_distribution<unsigned> distrib(0, getKnownNodesSize() - 1);
     146             : 
     147         211 :     while (nodesToReturn.size() < numberNodes) {
     148         107 :         nodesToReturn.emplace(getKnownNode(distrib(rd)));
     149             :     }
     150             : 
     151         104 :     return nodesToReturn;
     152        1315 : }
     153             : 
     154             : asio::steady_timer&
     155           0 : Bucket::getNodeTimer(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
     156             : {
     157           0 :     auto node = nodes.find(socket->deviceId());
     158           0 :     if (node == nodes.end()) {
     159           0 :         throw std::range_error("Unable to find timer " + socket->deviceId().toString());
     160             :     }
     161           0 :     return node->second.refresh_timer;
     162             : }
     163             : 
     164             : bool
     165           5 : Bucket::shutdownNode(const NodeId& nodeId)
     166             : {
     167           5 :     auto node = nodes.find(nodeId);
     168           5 :     if (node != nodes.end()) {
     169           3 :         auto& socket = node->second.socket;
     170           3 :         auto node = socket->deviceId();
     171           6 :         dht::ThreadPool::io().run([socket] { socket->shutdown(); });
     172           3 :         removeNode(node);
     173           3 :         return true;
     174             :     }
     175           2 :     return false;
     176             : }
     177             : 
     178             : void
     179         942 : Bucket::shutdownAllNodes()
     180             : {
     181        1664 :     while (not nodes.empty()) {
     182         722 :         auto it = nodes.begin();
     183        1062 :         dht::ThreadPool::io().run([socket = it->second.socket] { socket->shutdown(); });
     184         722 :         auto nodeId = it->first;
     185         722 :         removeNode(nodeId);
     186             :     }
     187         942 : }
     188             : 
     189             : void
     190           0 : Bucket::printBucket(unsigned number) const
     191             : {
     192           0 :     JAMI_ERROR("BUCKET Number: {:d}", number);
     193             : 
     194           0 :     unsigned nodeNum = 1;
     195           0 :     for (auto it = nodes.begin(); it != nodes.end(); ++it) {
     196           0 :         JAMI_DEBUG("Node {:s}   Id: {:s}  isMobile: {:s}",
     197             :                    std::to_string(nodeNum),
     198             :                    it->first.toString(),
     199             :                    std::to_string(it->second.isMobile_));
     200           0 :         nodeNum++;
     201             :     }
     202           0 :     JAMI_ERROR("Mobile Nodes");
     203           0 :     nodeNum = 0;
     204           0 :     for (auto it = mobile_nodes.begin(); it != mobile_nodes.end(); ++it) {
     205           0 :         JAMI_DEBUG("Node {:s}   Id: {:s}", std::to_string(nodeNum), (*it).toString());
     206           0 :         nodeNum++;
     207             :     }
     208             : 
     209           0 :     JAMI_ERROR("Known Nodes");
     210           0 :     nodeNum = 0;
     211           0 :     for (auto it = known_nodes.begin(); it != known_nodes.end(); ++it) {
     212           0 :         JAMI_DEBUG("Node {:s}   Id: {:s}", std::to_string(nodeNum), (*it).toString());
     213           0 :         nodeNum++;
     214             :     }
     215           0 :     JAMI_ERROR("Connecting_nodes");
     216           0 :     nodeNum = 0;
     217           0 :     for (auto it = connecting_nodes.begin(); it != connecting_nodes.end(); ++it) {
     218           0 :         JAMI_DEBUG("Node {:s}   Id: {:s}", std::to_string(nodeNum), (*it).toString());
     219           0 :         nodeNum++;
     220             :     }
     221           0 : };
     222             : 
     223             : void
     224         186 : Bucket::changeMobility(const NodeId& nodeId, bool isMobile)
     225             : {
     226         186 :     auto itn = nodes.find(nodeId);
     227         186 :     if (itn != nodes.end()) {
     228         186 :         itn->second.isMobile_ = isMobile;
     229             :     }
     230         186 : }
     231             : 
     232             : // For tests
     233             : 
     234             : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>>
     235           1 : Bucket::getNodeSockets() const
     236             : {
     237           1 :     std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>> sockets;
     238           3 :     for (auto const& info : nodes)
     239           2 :         sockets.insert(info.second.socket);
     240           1 :     return sockets;
     241           0 : }
     242             : 
     243             : // ####################################################################################################
     244             : 
     245         595 : RoutingTable::RoutingTable()
     246             : {
     247         595 :     buckets.emplace_back(NodeId::zero());
     248         595 : }
     249             : 
     250             : bool
     251        2472 : RoutingTable::isEmpty() const
     252             : {
     253        3720 :     for (const auto& bucket : buckets) {
     254        2593 :         if (!bucket.isEmpty()) {
     255        1345 :             return false;
     256             :         }
     257             :     }
     258        1127 :     return true;
     259             : }
     260             : 
     261             : bool
     262          10 : RoutingTable::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
     263             : {
     264          10 :     auto bucket = findBucket(socket->deviceId());
     265          20 :     return addNode(socket, bucket);
     266             : }
     267             : 
     268             : bool
     269        1293 : RoutingTable::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel,
     270             :                       std::list<Bucket>::iterator& bucket)
     271             : {
     272        1293 :     NodeId nodeId = channel->deviceId();
     273             : 
     274        1293 :     if (bucket->hasNode(nodeId) || id_ == nodeId) {
     275         260 :         return false;
     276             :     }
     277             : 
     278        1352 :     while (bucket->isFull()) {
     279         437 :         if (contains(bucket, id_)) {
     280         319 :             split(bucket);
     281         319 :             bucket = findBucket(nodeId);
     282             : 
     283             :         } else {
     284         118 :             return bucket->addNode(std::move(channel));
     285             :         }
     286             :     }
     287         915 :     return bucket->addNode(std::move(channel));
     288             : }
     289             : 
     290             : bool
     291         340 : RoutingTable::removeNode(const NodeId& nodeId)
     292             : {
     293         340 :     return findBucket(nodeId)->removeNode(nodeId);
     294             : }
     295             : 
     296             : bool
     297         448 : RoutingTable::hasNode(const NodeId& nodeId)
     298             : {
     299         448 :     return findBucket(nodeId)->hasNode(nodeId);
     300             : }
     301             : 
     302             : bool
     303        2153 : RoutingTable::addKnownNode(const NodeId& nodeId)
     304             : {
     305        2153 :     if (id_ == nodeId)
     306         512 :         return false;
     307             : 
     308        1651 :     auto bucket = findBucket(nodeId);
     309        1648 :     if (bucket == buckets.end())
     310           0 :         return false;
     311             : 
     312        1649 :     return bucket->addKnownNode(nodeId);
     313             : }
     314             : 
     315             : bool
     316          15 : RoutingTable::addMobileNode(const NodeId& nodeId)
     317             : {
     318          15 :     if (id_ == nodeId)
     319           1 :         return false;
     320             : 
     321          14 :     auto bucket = findBucket(nodeId);
     322             : 
     323          14 :     if (bucket == buckets.end())
     324           0 :         return false;
     325             : 
     326          14 :     bucket->addMobileNode(nodeId);
     327          14 :     return true;
     328             : }
     329             : 
     330             : void
     331           2 : RoutingTable::removeMobileNode(const NodeId& nodeId)
     332             : {
     333           2 :     return findBucket(nodeId)->removeMobileNode(nodeId);
     334             : }
     335             : 
     336             : bool
     337           7 : RoutingTable::hasMobileNode(const NodeId& nodeId)
     338             : {
     339           7 :     return findBucket(nodeId)->hasMobileNode(nodeId);
     340             : };
     341             : 
     342             : bool
     343         825 : RoutingTable::addConnectingNode(const NodeId& nodeId)
     344             : {
     345         825 :     if (id_ == nodeId)
     346           1 :         return false;
     347             : 
     348         825 :     auto bucket = findBucket(nodeId);
     349             : 
     350         825 :     if (bucket == buckets.end())
     351           0 :         return 0;
     352             : 
     353         826 :     bucket->addConnectingNode(nodeId);
     354         826 :     return 1;
     355             : }
     356             : 
     357             : void
     358           0 : RoutingTable::removeConnectingNode(const NodeId& nodeId)
     359             : {
     360           0 :     findBucket(nodeId)->removeConnectingNode(nodeId);
     361           0 : }
     362             : 
     363             : std::list<Bucket>::iterator
     364        9310 : RoutingTable::findBucket(const NodeId& nodeId)
     365             : {
     366        9310 :     if (buckets.empty())
     367           0 :         throw std::runtime_error("No bucket");
     368             : 
     369        9303 :     auto b = buckets.begin();
     370             : 
     371             :     while (true) {
     372       15796 :         auto next = std::next(b);
     373       15790 :         if (next == buckets.end())
     374        9311 :             return b;
     375       10585 :         if (std::memcmp(nodeId.data(), next->getLowerLimit().data(), nodeId.size()) < 0)
     376        4103 :             return b;
     377        6492 :         b = next;
     378        6492 :     }
     379             : }
     380             : 
     381             : std::vector<NodeId>
     382         943 : RoutingTable::closestNodes(const NodeId& nodeId, unsigned count)
     383             : {
     384         943 :     std::vector<NodeId> closestNodes;
     385         942 :     auto bucket = findBucket(nodeId);
     386        2416 :     auto sortedBucketInsert = [&](const std::list<Bucket>::iterator& b) {
     387        2416 :         auto nodes = b->getNodeIds();
     388        6884 :         for (auto n : nodes) {
     389        4472 :             if (n != nodeId) {
     390        3532 :                 auto here = std::find_if(closestNodes.begin(), closestNodes.end(), [&nodeId, &n](NodeId& NodeId) {
     391        9940 :                     return nodeId.xorCmp(n, NodeId) < 0;
     392             :                 });
     393             : 
     394        3544 :                 closestNodes.insert(here, n);
     395             :             }
     396             :         }
     397        2408 :     };
     398             : 
     399         946 :     auto itn = bucket;
     400         946 :     auto itp = (bucket == buckets.begin()) ? buckets.end() : std::prev(bucket);
     401        2855 :     while (itn != buckets.end() || itp != buckets.end()) {
     402        1910 :         if (itn != buckets.end()) {
     403        1694 :             sortedBucketInsert(itn);
     404        1694 :             itn = std::next(itn);
     405             :         }
     406        1907 :         if (itp != buckets.end()) {
     407         724 :             sortedBucketInsert(itp);
     408         725 :             itp = (itp == buckets.begin()) ? buckets.end() : std::prev(itp);
     409             :         }
     410             :     }
     411             : 
     412         948 :     if (closestNodes.size() > count) {
     413         514 :         closestNodes.resize(count);
     414             :     }
     415             : 
     416        1894 :     return closestNodes;
     417           0 : }
     418             : 
     419             : void
     420           0 : RoutingTable::printRoutingTable() const
     421             : {
     422           0 :     int counter = 1;
     423           0 :     JAMI_DEBUG("SWARM: {:s} ", id_.toString());
     424           0 :     for (auto it = buckets.begin(); it != buckets.end(); ++it) {
     425           0 :         it->printBucket(counter);
     426           0 :         counter++;
     427             :     }
     428           0 :     JAMI_DEBUG("_____________________________________________________________________________");
     429           0 : }
     430             : 
     431             : void
     432           2 : RoutingTable::shutdownNode(const NodeId& nodeId)
     433             : {
     434           2 :     findBucket(nodeId)->shutdownNode(nodeId);
     435           2 : }
     436             : 
     437             : std::vector<NodeId>
     438         101 : RoutingTable::getNodes() const
     439             : {
     440         101 :     std::lock_guard lock(mutex_);
     441         101 :     std::vector<NodeId> ret;
     442         493 :     for (const auto& b : buckets) {
     443         392 :         const auto& nodes = b.getNodeIds();
     444         392 :         ret.insert(ret.end(), nodes.begin(), nodes.end());
     445         392 :     }
     446         202 :     return ret;
     447         101 : }
     448             : 
     449             : std::vector<NodeId>
     450           1 : RoutingTable::getKnownNodes() const
     451             : {
     452           1 :     std::vector<NodeId> ret;
     453           2 :     for (const auto& b : buckets) {
     454           1 :         const auto& nodes = b.getKnownNodes();
     455           1 :         ret.insert(ret.end(), nodes.begin(), nodes.end());
     456             :     }
     457           1 :     return ret;
     458           0 : }
     459             : 
     460             : std::vector<NodeId>
     461           2 : RoutingTable::getMobileNodes() const
     462             : {
     463           2 :     std::vector<NodeId> ret;
     464           4 :     for (const auto& b : buckets) {
     465           2 :         const auto& nodes = b.getMobileNodes();
     466           2 :         ret.insert(ret.end(), nodes.begin(), nodes.end());
     467             :     }
     468           2 :     return ret;
     469           0 : }
     470             : 
     471             : std::vector<NodeId>
     472           1 : RoutingTable::getConnectingNodes() const
     473             : {
     474           1 :     std::vector<NodeId> ret;
     475           2 :     for (const auto& b : buckets) {
     476           1 :         const auto& nodes = b.getConnectingNodes();
     477           1 :         ret.insert(ret.end(), nodes.begin(), nodes.end());
     478             :     }
     479           1 :     return ret;
     480           0 : }
     481             : 
     482             : std::vector<NodeId>
     483           0 : RoutingTable::getBucketMobileNodes() const
     484             : {
     485           0 :     std::vector<NodeId> ret;
     486           0 :     auto bucket = findBucket(id_);
     487           0 :     const auto& nodes = bucket->getMobileNodes();
     488           0 :     ret.insert(ret.end(), nodes.begin(), nodes.end());
     489             : 
     490           0 :     return ret;
     491           0 : }
     492             : 
     493             : bool
     494        3710 : RoutingTable::contains(const std::list<Bucket>::iterator& bucket, const NodeId& nodeId) const
     495             : {
     496        3710 :     return NodeId::cmp(bucket->getLowerLimit(), nodeId) <= 0
     497        3715 :            && (std::next(bucket) == buckets.end() || NodeId::cmp(nodeId, std::next(bucket)->getLowerLimit()) < 0);
     498             : }
     499             : 
     500             : std::vector<NodeId>
     501          18 : RoutingTable::getAllNodes() const
     502             : {
     503          18 :     std::vector<NodeId> ret;
     504          36 :     for (const auto& b : buckets) {
     505          18 :         const auto& nodes = b.getNodeIds();
     506          18 :         const auto& knownNodes = b.getKnownNodes();
     507          18 :         const auto& mobileNodes = b.getMobileNodes();
     508          18 :         const auto& connectingNodes = b.getConnectingNodes();
     509          18 :         ret.reserve(ret.size() + nodes.size() + knownNodes.size() + mobileNodes.size() + connectingNodes.size());
     510          18 :         ret.insert(ret.end(), nodes.begin(), nodes.end());
     511          18 :         ret.insert(ret.end(), knownNodes.begin(), knownNodes.end());
     512          18 :         ret.insert(ret.end(), mobileNodes.begin(), mobileNodes.end());
     513          18 :         ret.insert(ret.end(), connectingNodes.begin(), connectingNodes.end());
     514          18 :     }
     515          18 :     return ret;
     516           0 : }
     517             : 
     518             : std::vector<NodeId>
     519        1692 : RoutingTable::getConnectedNodes() const
     520             : {
     521        1692 :     std::vector<NodeId> ret;
     522        5960 :     for (const auto& b : buckets) {
     523        4268 :         const auto& nodes = b.getNodes();
     524        4267 :         const auto& mobiles = b.getMobileNodes();
     525        4267 :         ret.reserve(ret.size() + nodes.size() + mobiles.size());
     526       11546 :         for (const auto& n : nodes)
     527        7280 :             ret.emplace_back(n.first);
     528        4267 :         ret.insert(ret.end(), mobiles.begin(), mobiles.end());
     529             :     }
     530        1691 :     return ret;
     531           0 : }
     532             : 
     533             : void
     534           2 : RoutingTable::deleteNode(const NodeId& nodeId)
     535             : {
     536           2 :     auto bucket = findBucket(nodeId);
     537           2 :     bucket->shutdownNode(nodeId);
     538           2 :     bucket->removeConnectingNode(nodeId);
     539           2 :     bucket->removeKnownNode(nodeId);
     540           2 :     bucket->removeMobileNode(nodeId);
     541           2 : }
     542             : 
     543             : inline std::chrono::system_clock::time_point
     544           0 : systemTimeFromSteady(std::chrono::steady_clock::time_point t,
     545             :                      const std::chrono::steady_clock::time_point& now,
     546             :                      const std::chrono::system_clock::time_point& nowSystem)
     547             : {
     548           0 :     return nowSystem + std::chrono::duration_cast<std::chrono::system_clock::duration>(t - now);
     549             : }
     550             : 
     551             : std::vector<RoutingTable::NodeStats>
     552           0 : RoutingTable::getRoutingTableStats() const
     553             : {
     554           0 :     std::vector<NodeStats> stats;
     555           0 :     auto now = std::chrono::steady_clock::now();
     556           0 :     auto nowSystem = std::chrono::system_clock::now();
     557           0 :     std::lock_guard lock(mutex_);
     558           0 :     for (const auto& bucket : buckets) {
     559           0 :         for (const auto& [id, info] : bucket.getNodes()) {
     560           0 :             if (auto channel = std::dynamic_pointer_cast<dhtnet::ChannelSocket>(info.socket)) {
     561           0 :                 stats.push_back({id.toString(),
     562             :                                  "connected",
     563           0 :                                  channel->getRemoteAddress().toString(true),
     564           0 :                                  systemTimeFromSteady(channel->getStartTime(), now, nowSystem),
     565           0 :                                  info.isMobile_});
     566             :             } else {
     567           0 :                 stats.push_back(
     568           0 :                     {id.toString(), "connected", "", std::chrono::system_clock::time_point::min(), info.isMobile_});
     569           0 :             }
     570             :         }
     571           0 :         for (const auto& id : bucket.getKnownNodes()) {
     572           0 :             stats.push_back({id.toString(), "known", "", std::chrono::system_clock::time_point::min(), false});
     573             :         }
     574           0 :         for (const auto& id : bucket.getMobileNodes()) {
     575           0 :             stats.push_back({id.toString(), "mobile", "", std::chrono::system_clock::time_point::min(), true});
     576             :         }
     577           0 :         for (const auto& id : bucket.getConnectingNodes()) {
     578           0 :             stats.push_back({id.toString(), "connecting", "", std::chrono::system_clock::time_point::min(), false});
     579             :         }
     580             :     }
     581           0 :     return stats;
     582           0 : }
     583             : 
     584             : NodeId
     585         319 : RoutingTable::middle(std::list<Bucket>::iterator& it) const
     586             : {
     587         319 :     unsigned bit = depth(it);
     588         319 :     if (bit >= 8 * HASH_LEN)
     589           0 :         throw std::out_of_range("End of table");
     590             : 
     591         319 :     NodeId id = it->getLowerLimit();
     592         319 :     id.setBit(bit, true);
     593         319 :     return id;
     594             : }
     595             : 
     596             : unsigned
     597         319 : RoutingTable::depth(std::list<Bucket>::iterator& bucket) const
     598             : {
     599         319 :     int bit1 = bucket->getLowerLimit().lowbit();
     600         319 :     int bit2 = std::next(bucket) != buckets.end() ? std::next(bucket)->getLowerLimit().lowbit() : -1;
     601         319 :     return std::max(bit1, bit2) + 1;
     602             : }
     603             : 
     604             : bool
     605         319 : RoutingTable::split(std::list<Bucket>::iterator& bucket)
     606             : {
     607         319 :     NodeId id = middle(bucket);
     608         319 :     auto newBucketIt = buckets.emplace(std::next(bucket), id);
     609             :     // Re-assign nodes
     610         319 :     auto& nodeSwap = bucket->getNodes();
     611             : 
     612         955 :     for (auto it = nodeSwap.begin(); it != nodeSwap.end();) {
     613         637 :         auto& node = *it;
     614             : 
     615         637 :         auto nodeId = it->first;
     616             : 
     617         638 :         if (!contains(bucket, nodeId)) {
     618         286 :             newBucketIt->addNode(std::move(node.second));
     619         285 :             it = nodeSwap.erase(it);
     620             :         } else {
     621         352 :             ++it;
     622             :         }
     623             :     }
     624             : 
     625         318 :     auto connectingSwap = bucket->getConnectingNodes();
     626         591 :     for (auto it = connectingSwap.begin(); it != connectingSwap.end();) {
     627         272 :         auto nodeId = *it;
     628             : 
     629         272 :         if (!contains(bucket, nodeId)) {
     630         124 :             newBucketIt->addConnectingNode(nodeId);
     631         124 :             it = connectingSwap.erase(it);
     632         124 :             bucket->removeConnectingNode(nodeId);
     633             :         } else {
     634         148 :             ++it;
     635             :         }
     636             :     }
     637             : 
     638         319 :     auto knownSwap = bucket->getKnownNodes();
     639         514 :     for (auto it = knownSwap.begin(); it != knownSwap.end();) {
     640         195 :         auto nodeId = *it;
     641             : 
     642         195 :         if (!contains(bucket, nodeId)) {
     643          94 :             newBucketIt->addKnownNode(nodeId);
     644          94 :             it = knownSwap.erase(it);
     645          94 :             bucket->removeKnownNode(nodeId);
     646             :         } else {
     647         101 :             ++it;
     648             :         }
     649             :     }
     650             : 
     651         319 :     auto mobileSwap = bucket->getMobileNodes();
     652         319 :     for (auto it = mobileSwap.begin(); it != mobileSwap.end();) {
     653           0 :         auto nodeId = *it;
     654             : 
     655           0 :         if (!contains(bucket, nodeId)) {
     656           0 :             newBucketIt->addMobileNode(nodeId);
     657           0 :             it = mobileSwap.erase(it);
     658           0 :             bucket->removeMobileNode(nodeId);
     659             :         } else {
     660           0 :             ++it;
     661             :         }
     662             :     }
     663             : 
     664         319 :     return true;
     665         319 : }
     666             : 
     667             : } // namespace jami

Generated by: LCOV version 1.14