← Back to branch summary

~ubuntu-branches/ubuntu/trusty/miro/trusty

« back to all changes in this revision

Viewing changes to portable/libtorrent/src/kademlia/traversal_algorithm.cpp

  • Committer: Daniel Hahler
  • Date: 2010-04-13 18:51:35 UTC
  • mfrom: (1.2.10 upstream)
  • Revision ID: ubuntu-launchpad@thequod.de-20100413185135-xi24v1diqg8w406x
Merging shared upstream rev into target branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
portable/libtorrent/src/kademlia/traversal_algorithm.cpp
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
 
#include "libtorrent/pch.hpp"
34
 
 
35
 
#include <libtorrent/kademlia/traversal_algorithm.hpp>
36
 
#include <libtorrent/kademlia/routing_table.hpp>
37
 
#include <libtorrent/kademlia/rpc_manager.hpp>
38
 
 
39
 
#include <boost/bind.hpp>
40
 
 
41
 
using boost::bind;
42
 
 
43
 
namespace libtorrent { namespace dht
44
 
{
45
 
#ifdef TORRENT_DHT_VERBOSE_LOGGING
46
 
TORRENT_DEFINE_LOG(traversal)
47
 
#endif
48
 
 
49
 
void traversal_algorithm::add_entry(node_id const& id, udp::endpoint addr, unsigned char flags)
50
 
{
51
 
        if (m_failed.find(addr) != m_failed.end()) return;
52
 
 
53
 
        result entry(id, addr, flags);
54
 
        if (entry.id.is_all_zeros())
55
 
        {
56
 
                entry.id = generate_id();
57
 
                entry.flags |= result::no_id;
58
 
        }
59
 
 
60
 
        std::vector<result>::iterator i = std::lower_bound(
61
 
                m_results.begin()
62
 
                , m_results.end()
63
 
                , entry
64
 
                , bind(
65
 
                        compare_ref
66
 
                        , bind(&result::id, _1)
67
 
                        , bind(&result::id, _2)
68
 
                        , m_target
69
 
                )
70
 
        );
71
 
 
72
 
        if (i == m_results.end() || i->id != id)
73
 
        {
74
 
                TORRENT_ASSERT(std::find_if(m_results.begin(), m_results.end()
75
 
                        , bind(&result::id, _1) == id) == m_results.end());
76
 
#ifdef TORRENT_DHT_VERBOSE_LOGGING
77
 
                TORRENT_LOG(traversal) << "adding result: " << id << " " << addr;
78
 
#endif
79
 
                m_results.insert(i, entry);
80
 
        }
81
 
}
82
 
 
83
 
boost::pool<>& traversal_algorithm::allocator() const
84
 
{
85
 
        return m_rpc.allocator();
86
 
}
87
 
 
88
 
void traversal_algorithm::traverse(node_id const& id, udp::endpoint addr)
89
 
{
90
 
#ifdef TORRENT_DHT_VERBOSE_LOGGING
91
 
        if (id.is_all_zeros())
92
 
        TORRENT_LOG(traversal) << time_now_string() << " WARNING: node returned a list which included a node with id 0";
93
 
#endif
94
 
        add_entry(id, addr, 0);
95
 
}
96
 
 
97
 
void traversal_algorithm::finished(node_id const& id)
98
 
{
99
 
        --m_invoke_count;
100
 
        add_requests();
101
 
        if (m_invoke_count == 0) done();
102
 
}
103
 
 
104
 
// prevent request means that the total number of requests has
105
 
// overflown. This query failed because it was the oldest one.
106
 
// So, if this is true, don't make another request
107
 
void traversal_algorithm::failed(node_id const& id, bool prevent_request)
108
 
{
109
 
        m_invoke_count--;
110
 
 
111
 
        TORRENT_ASSERT(!id.is_all_zeros());
112
 
        std::vector<result>::iterator i = std::find_if(
113
 
                m_results.begin()
114
 
                , m_results.end()
115
 
                , bind(
116
 
                        std::equal_to<node_id>()
117
 
                        , bind(&result::id, _1)
118
 
                        , id
119
 
                )
120
 
        );
121
 
 
122
 
        TORRENT_ASSERT(i != m_results.end());
123
 
 
124
 
        if (i != m_results.end())
125
 
        {
126
 
                TORRENT_ASSERT(i->flags & result::queried);
127
 
                m_failed.insert(i->addr);
128
 
#ifdef TORRENT_DHT_VERBOSE_LOGGING
129
 
                TORRENT_LOG(traversal) << "failed: " << i->id << " " << i->addr;
130
 
#endif
131
 
                // don't tell the routing table about
132
 
                // node ids that we just generated ourself
133
 
                if ((i->flags & result::no_id) == 0)
134
 
                        m_table.node_failed(id);
135
 
                m_results.erase(i);
136
 
        }
137
 
        if (prevent_request)
138
 
        {
139
 
                --m_branch_factor;
140
 
                if (m_branch_factor <= 0) m_branch_factor = 1;
141
 
        }
142
 
        add_requests();
143
 
        if (m_invoke_count == 0) done();
144
 
}
145
 
 
146
 
namespace
147
 
{
148
 
        bool bitwise_nand(unsigned char lhs, unsigned char rhs)
149
 
        {
150
 
                return (lhs & rhs) == 0;
151
 
        }
152
 
}
153
 
 
154
 
void traversal_algorithm::add_requests()
155
 
{
156
 
        while (m_invoke_count < m_branch_factor)
157
 
        {
158
 
                // Find the first node that hasn't already been queried.
159
 
                // TODO: Better heuristic
160
 
                std::vector<result>::iterator i = std::find_if(
161
 
                        m_results.begin()
162
 
                        , last_iterator()
163
 
                        , bind(
164
 
                                &bitwise_nand
165
 
                                , bind(&result::flags, _1)
166
 
                                , (unsigned char)result::queried
167
 
                        )
168
 
                );
169
 
#ifdef TORRENT_DHT_VERBOSE_LOGGING
170
 
                TORRENT_LOG(traversal) << "nodes left (" << this << "): " << (last_iterator() - i);
171
 
#endif
172
 
 
173
 
                if (i == last_iterator()) break;
174
 
 
175
 
                try
176
 
                {
177
 
                        invoke(i->id, i->addr);
178
 
                        ++m_invoke_count;
179
 
                        i->flags |= result::queried;
180
 
                }
181
 
                catch (std::exception& e) {}
182
 
        }
183
 
}
184
 
 
185
 
std::vector<traversal_algorithm::result>::iterator traversal_algorithm::last_iterator()
186
 
{
187
 
        return (int)m_results.size() >= m_max_results ?
188
 
                m_results.begin() + m_max_results
189
 
                : m_results.end();
190
 
}
191
 
 
192
 
} } // namespace libtorrent::dht
193