include/libtorrent/kademlia/traversal_algorithm.hpp

   1 /*
   2
   3 Copyright (c) 2006, Arvid Norberg & Daniel Wallin
   4 All rights reserved.
   5
   6 Redistribution and use in source and binary forms, with or without
   7 modification, are permitted provided that the following conditions
   8 are met:
   9
  10     * Redistributions of source code must retain the above copyright
  11       notice, this list of conditions and the following disclaimer.
  12     * Redistributions in binary form must reproduce the above copyright
  13       notice, this list of conditions and the following disclaimer in
  14       the documentation and/or other materials provided with the distribution.
  15     * Neither the name of the author nor the names of its
  16       contributors may be used to endorse or promote products derived
  17       from this software without specific prior written permission.
  18
  19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29 POSSIBILITY OF SUCH DAMAGE.
  30
  31 */
  32
  33 #ifndef TRAVERSAL_ALGORITHM_050324_HPP
  34 #define TRAVERSAL_ALGORITHM_050324_HPP
  35
  36 #include <vector>
  37 #include <set>
  38
  39 #include <libtorrent/kademlia/node_id.hpp>
  40 #include <libtorrent/kademlia/routing_table.hpp>
  41 #include <libtorrent/kademlia/logging.hpp>
  42
  43 #include <boost/noncopyable.hpp>
  44 #include <boost/intrusive_ptr.hpp>
  45 #include <boost/bind.hpp>
  46 #include <boost/pool/pool.hpp>
  47
  48 namespace libtorrent { namespace dht
  49 {
  50 #ifdef TORRENT_DHT_VERBOSE_LOGGING
  51 TORRENT_DECLARE_LOG(traversal);
  52 #endif
  53
  54 class rpc_manager;
  55
  56 // this class may not be instantiated as a stack object
  57 class traversal_algorithm : boost::noncopyable
  58 {
  59 public:
  60         void traverse(node_id const& id, udp::endpoint addr);
  61         void finished(node_id const& id);
  62         void failed(node_id const& id, bool prevent_request = false);
  63         virtual ~traversal_algorithm() {}
  64         boost::pool<>& allocator() const;
  65
  66 protected:
  67         template<class InIt>
  68         traversal_algorithm(
  69                 node_id target
  70                 , int branch_factor
  71                 , int max_results
  72                 , routing_table& table
  73                 , rpc_manager& rpc
  74                 , InIt start
  75                 , InIt end
  76         );
  77
  78         void add_requests();
  79         void add_entry(node_id const& id, udp::endpoint addr, unsigned char flags);
  80
  81         virtual void done() = 0;
  82         virtual void invoke(node_id const& id, udp::endpoint addr) = 0;
  83
  84         struct result
  85         {
  86                 result(node_id const& id, udp::endpoint addr, unsigned char f = 0)
  87                         : id(id), addr(addr), flags(f) {}
  88
  89                 node_id id;
  90                 udp::endpoint addr;
  91                 enum { queried = 1, initial = 2, no_id = 4 };
  92                 unsigned char flags;
  93         };
  94
  95         std::vector<result>::iterator last_iterator();
  96
  97         friend void intrusive_ptr_add_ref(traversal_algorithm* p)
  98         {
  99                 p->m_ref_count++;
 100         }
 101
 102         friend void intrusive_ptr_release(traversal_algorithm* p)
 103         {
 104                 if (--p->m_ref_count == 0)
 105                         delete p;
 106         }
 107
 108         int m_ref_count;
 109
 110         node_id m_target;
 111         int m_branch_factor;
 112         int m_max_results;
 113         std::vector<result> m_results;
 114         std::set<udp::endpoint> m_failed;
 115         routing_table& m_table;
 116         rpc_manager& m_rpc;
 117         int m_invoke_count;
 118 };
 119
 120 template<class InIt>
 121 traversal_algorithm::traversal_algorithm(
 122         node_id target
 123         , int branch_factor
 124         , int max_results
 125         , routing_table& table
 126         , rpc_manager& rpc
 127         , InIt start    // <- nodes to initiate traversal with
 128         , InIt end
 129 )
 130         : m_ref_count(0)
 131         , m_target(target)
 132         , m_branch_factor(branch_factor)
 133         , m_max_results(max_results)
 134         , m_table(table)
 135         , m_rpc(rpc)
 136         , m_invoke_count(0)
 137 {
 138         using boost::bind;
 139
 140         for (InIt i = start; i != end; ++i)
 141         {
 142                 add_entry(i->id, i->addr, result::initial);
 143         }
 144
 145         // in case the routing table is empty, use the
 146         // router nodes in the table
 147         if (start == end)
 148         {
 149                 for (routing_table::router_iterator i = table.router_begin()
 150                         , end(table.router_end()); i != end; ++i)
 151                 {
 152                         add_entry(node_id(0), *i, result::initial);
 153                 }
 154         }
 155
 156 }
 157
 158 } } // namespace libtorrent::dht
 159
 160 #endif // TRAVERSAL_ALGORITHM_050324_HPP
 161