00001
00002
00003
00004
00005
00006
00007
00008 #include <vector>
00009 #include <cmath>
00010 #include <algorithm>
00011 #include <numeric>
00012
00013 #include "libtorrent/piece_picker.hpp"
00014 #include "libtorrent/aux_/session_impl.hpp"
00015
00016 #ifndef NDEBUG
00017 #include "libtorrent/peer_connection.hpp"
00018 #include "libtorrent/torrent.hpp"
00019 #endif
00020
00021 #define TORRENT_PIECE_PICKER_INVARIANT_CHECK
00022
00023 namespace libtorrent
00024 {
00025
00026 piece_picker::piece_picker(int blocks_per_piece, int total_num_blocks)
00027 : m_piece_info(2)
00028 , m_downloading_piece_info(2)
00029 , m_piece_map((total_num_blocks + blocks_per_piece-1) / blocks_per_piece)
00030 , m_num_filtered(0)
00031 , m_num_have_filtered(0)
00032 , m_sequenced_download_threshold(100)
00033 {
00034 assert(blocks_per_piece > 0);
00035 assert(total_num_blocks >= 0);
00036 #ifndef NDEBUG
00037 m_files_checked_called = false;
00038 #endif
00039
00040
00041
00042 if (m_piece_map.size() >= piece_pos::we_have_index)
00043 throw std::runtime_error("too many pieces in torrent");
00044
00045 m_blocks_per_piece = blocks_per_piece;
00046 m_blocks_in_last_piece = total_num_blocks % blocks_per_piece;
00047 if (m_blocks_in_last_piece == 0) m_blocks_in_last_piece = blocks_per_piece;
00048
00049 assert(m_blocks_per_piece <= max_blocks_per_piece);
00050 assert(m_blocks_in_last_piece <= m_blocks_per_piece);
00051 assert(m_blocks_in_last_piece <= max_blocks_per_piece);
00052
00053
00054
00055 std::fill(m_piece_map.begin(), m_piece_map.end()
00056 , piece_pos(0, piece_pos::we_have_index));
00057 }
00058
00059
00060 void piece_picker::files_checked(
00061 const std::vector<bool>& pieces
00062 , const std::vector<downloading_piece>& unfinished)
00063 {
00064 #ifndef NDEBUG
00065 m_files_checked_called = true;
00066 #endif
00067
00068 std::vector<int> piece_list;
00069 piece_list.reserve(std::count(pieces.begin(), pieces.end(), false));
00070
00071 for (std::vector<bool>::const_iterator i = pieces.begin();
00072 i != pieces.end(); ++i)
00073 {
00074 if (*i) continue;
00075 int index = static_cast<int>(i - pieces.begin());
00076 if (m_piece_map[index].filtered)
00077 {
00078 ++m_num_filtered;
00079 --m_num_have_filtered;
00080 m_piece_map[index].index = 0;
00081 }
00082 else
00083 {
00084 piece_list.push_back(index);
00085 }
00086 }
00087
00088
00089 for (std::vector<int>::reverse_iterator i = piece_list.rbegin();
00090 i != piece_list.rend(); ++i)
00091 {
00092 int index = *i;
00093 assert(index >= 0);
00094 assert(index < (int)m_piece_map.size());
00095 assert(m_piece_map[index].index == piece_pos::we_have_index);
00096 assert(m_piece_map[index].peer_count == 0);
00097 assert(m_piece_info.size() == 2);
00098
00099 add(index);
00100 assert(m_piece_map[index].index != piece_pos::we_have_index);
00101 }
00102
00103
00104
00105 if (!unfinished.empty())
00106 {
00107 for (std::vector<downloading_piece>::const_iterator i
00108 = unfinished.begin(); i != unfinished.end(); ++i)
00109 {
00110 tcp::endpoint peer;
00111 for (int j = 0; j < m_blocks_per_piece; ++j)
00112 {
00113 if (i->finished_blocks[j])
00114 mark_as_finished(piece_block(i->index, j), peer);
00115 }
00116 if (is_piece_finished(i->index))
00117 {
00118
00119
00120 assert(false);
00121 }
00122 }
00123 }
00124 }
00125
00126 void piece_picker::set_sequenced_download_threshold(
00127 int sequenced_download_threshold)
00128 {
00129 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00130
00131 if (sequenced_download_threshold == m_sequenced_download_threshold)
00132 return;
00133
00134 int old_limit = m_sequenced_download_threshold;
00135 m_sequenced_download_threshold = sequenced_download_threshold;
00136
00137 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
00138 , end(m_piece_map.end()); i != end; ++i)
00139 {
00140 if (i->priority(old_limit) != i->priority(m_sequenced_download_threshold))
00141 {
00142 piece_pos& p = *i;
00143 if (p.index == piece_pos::we_have_index) continue;
00144 int prev_priority = p.priority(old_limit);
00145 move(p.downloading, p.filtered, prev_priority, p.index);
00146 }
00147 }
00148
00149 typedef std::vector<int> info_t;
00150
00151 if (old_limit < sequenced_download_threshold)
00152 {
00153
00154
00155
00156
00157 if (int(m_piece_info.size()) > old_limit)
00158 {
00159 info_t& in = m_piece_info[old_limit];
00160 std::random_shuffle(in.begin(), in.end());
00161 int c = 0;
00162 for (info_t::iterator i = in.begin()
00163 , end(in.end()); i != end; ++i)
00164 {
00165 m_piece_map[*i].index = c++;
00166 assert(m_piece_map[*i].priority(old_limit) == old_limit);
00167 }
00168 }
00169 }
00170 else if (int(m_piece_info.size()) > sequenced_download_threshold)
00171 {
00172 info_t& in = m_piece_info[sequenced_download_threshold];
00173 std::sort(in.begin(), in.end());
00174 int c = 0;
00175 for (info_t::iterator i = in.begin()
00176 , end(in.end()); i != end; ++i)
00177 {
00178 m_piece_map[*i].index = c++;
00179 assert(m_piece_map[*i].priority(
00180 sequenced_download_threshold) == sequenced_download_threshold);
00181 }
00182 }
00183 }
00184
00185 #ifndef NDEBUG
00186
00187 void piece_picker::check_invariant(const torrent* t) const
00188 {
00189 assert(sizeof(piece_pos) == 4);
00190
00191 if (t != 0)
00192 assert((int)m_piece_map.size() == t->torrent_file().num_pieces());
00193
00194 int num_filtered = 0;
00195 int num_have_filtered = 0;
00196 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin();
00197 i != m_piece_map.end(); ++i)
00198 {
00199 int index = static_cast<int>(i - m_piece_map.begin());
00200 if (i->filtered)
00201 {
00202 if (i->index != piece_pos::we_have_index)
00203 ++num_filtered;
00204 else
00205 ++num_have_filtered;
00206 }
00207 if (t != 0)
00208 {
00209 int actual_peer_count = 0;
00210 for (torrent::const_peer_iterator peer = t->begin();
00211 peer != t->end(); ++peer)
00212 {
00213 if (peer->second->has_piece(index)) actual_peer_count++;
00214 }
00215
00216 assert((int)i->peer_count == actual_peer_count);
00217
00218 }
00219
00220 if (i->index == piece_pos::we_have_index)
00221 {
00222 assert(t == 0 || t->have_piece(index));
00223 assert(i->downloading == 0);
00224
00225
00226
00227
00228 for (std::vector<std::vector<int> >::const_iterator i = m_piece_info.begin();
00229 i != m_piece_info.end(); ++i)
00230 {
00231 for (std::vector<int>::const_iterator j= i->begin();
00232 j != i->end(); ++j)
00233 {
00234 assert(*j != index);
00235 }
00236 }
00237
00238 for (std::vector<std::vector<int> >::const_iterator i = m_downloading_piece_info.begin();
00239 i != m_downloading_piece_info.end(); ++i)
00240 {
00241 for (std::vector<int>::const_iterator j = i->begin();
00242 j != i->end(); ++j)
00243 {
00244 assert(*j != index);
00245 }
00246 }
00247
00248 }
00249 else if (!i->filtered)
00250 {
00251 if (t != 0)
00252 assert(!t->have_piece(index));
00253
00254 const std::vector<std::vector<int> >& c_vec = pick_piece_info_vector(i->downloading, i->filtered);
00255 assert(i->priority(m_sequenced_download_threshold) < (int)c_vec.size());
00256 const std::vector<int>& vec = c_vec[i->priority(m_sequenced_download_threshold)];
00257 if (i->index >= vec.size())
00258 {
00259 assert(false);
00260 }
00261 assert(vec[i->index] == index);
00262 }
00263
00264 std::vector<downloading_piece>::const_iterator down
00265 = std::find_if(m_downloads.begin(),
00266 m_downloads.end(),
00267 has_index(index));
00268 if (i->downloading == 1)
00269 {
00270 assert(down != m_downloads.end());
00271 }
00272 else
00273 {
00274 assert(down == m_downloads.end());
00275 }
00276 }
00277 assert(num_filtered == m_num_filtered);
00278 assert(num_have_filtered == m_num_have_filtered);
00279 }
00280 #endif
00281
00282 float piece_picker::distributed_copies() const
00283 {
00284 const float num_pieces = static_cast<float>(m_piece_map.size());
00285
00286 for (int i = 0; i < (int)m_piece_info.size(); ++i)
00287 {
00288 int p = (int)m_piece_info[i].size();
00289 assert(num_pieces == 0 || float(p) / num_pieces <= 1.f);
00290 if (p > 0)
00291 {
00292 float fraction_above_count =
00293 1.f - float(p) / num_pieces;
00294 return i + fraction_above_count;
00295 }
00296 }
00297 return 1.f;
00298 }
00299
00300 std::vector<std::vector<int> >& piece_picker::pick_piece_info_vector(
00301 bool downloading, bool filtered)
00302 {
00303 assert(!filtered);
00304 return downloading?m_downloading_piece_info:m_piece_info;
00305 }
00306
00307 std::vector<std::vector<int> > const& piece_picker::pick_piece_info_vector(
00308 bool downloading, bool filtered) const
00309 {
00310 assert(!filtered);
00311 return downloading?m_downloading_piece_info:m_piece_info;
00312 }
00313
00314 void piece_picker::add(int index)
00315 {
00316 assert(index >= 0);
00317 assert(index < (int)m_piece_map.size());
00318 piece_pos& p = m_piece_map[index];
00319 assert(!p.filtered);
00320
00321 std::vector<std::vector<int> >& dst_vec = pick_piece_info_vector(
00322 p.downloading, p.filtered);
00323
00324 int priority = p.priority(m_sequenced_download_threshold);
00325 if ((int)dst_vec.size() <= priority)
00326 dst_vec.resize(priority + 1);
00327
00328 assert((int)dst_vec.size() > priority);
00329
00330 if (p.ordered(m_sequenced_download_threshold))
00331 {
00332
00333 std::vector<int>& v = dst_vec[priority];
00334
00335 std::vector<int>::iterator i = std::lower_bound(v.begin(), v.end()
00336 , index);
00337 p.index = i - v.begin();
00338 v.insert(i, index);
00339 i = v.begin() + p.index + 1;
00340 for (;i != v.end(); ++i)
00341 {
00342 ++m_piece_map[*i].index;
00343 assert(v[m_piece_map[*i].index] == *i);
00344 }
00345
00346 }
00347 else if (dst_vec[priority].size() < 2)
00348 {
00349 p.index = dst_vec[priority].size();
00350 dst_vec[priority].push_back(index);
00351 }
00352 else
00353 {
00354
00355
00356 int dst_index = rand() % dst_vec[priority].size();
00357
00358
00359 m_piece_map[dst_vec[priority][dst_index]].index
00360 = dst_vec[priority].size();
00361 dst_vec[priority].push_back(dst_vec[priority][dst_index]);
00362
00363
00364
00365
00366 p.index = dst_index;
00367 dst_vec[priority][p.index] = index;
00368 }
00369 }
00370
00371
00372
00373
00374 void piece_picker::move(bool downloading, bool filtered, int priority
00375 , int elem_index)
00376 {
00377 assert(!filtered);
00378 assert(priority >= 0);
00379 assert(elem_index >= 0);
00380 assert(elem_index != piece_pos::we_have_index);
00381 std::vector<std::vector<int> >& src_vec(pick_piece_info_vector(
00382 downloading, filtered));
00383 assert(m_files_checked_called);
00384
00385 assert((int)src_vec.size() > priority);
00386 assert((int)src_vec[priority].size() > elem_index);
00387
00388 int index = src_vec[priority][elem_index];
00389
00390 piece_pos& p = m_piece_map[index];
00391 int new_priority = p.priority(m_sequenced_download_threshold);
00392
00393 if (p.downloading == downloading
00394 && p.filtered == filtered
00395 && new_priority == priority)
00396 {
00397 assert(p.ordered(m_sequenced_download_threshold));
00398 return;
00399 }
00400
00401 std::vector<std::vector<int> >& dst_vec(pick_piece_info_vector(
00402 p.downloading, p.filtered));
00403
00404 assert(&dst_vec != &src_vec || new_priority != priority);
00405
00406 if ((int)dst_vec.size() <= new_priority)
00407 {
00408 dst_vec.resize(new_priority + 1);
00409 assert((int)dst_vec.size() > new_priority);
00410 }
00411
00412 if (p.ordered(m_sequenced_download_threshold))
00413 {
00414
00415 std::vector<int>& v = dst_vec[new_priority];
00416
00417 std::vector<int>::iterator i = std::lower_bound(v.begin(), v.end()
00418 , index);
00419 p.index = i - v.begin();
00420 v.insert(i, index);
00421 i = v.begin() + p.index + 1;
00422 for (;i != v.end(); ++i)
00423 {
00424 ++m_piece_map[*i].index;
00425 assert(v[m_piece_map[*i].index] == *i);
00426 }
00427
00428 }
00429 else if (dst_vec[new_priority].size() < 2)
00430 {
00431 p.index = dst_vec[new_priority].size();
00432 dst_vec[new_priority].push_back(index);
00433 }
00434 else
00435 {
00436
00437
00438 int dst_index = rand() % dst_vec[new_priority].size();
00439
00440
00441 m_piece_map[dst_vec[new_priority][dst_index]].index
00442 = dst_vec[new_priority].size();
00443 dst_vec[new_priority].push_back(dst_vec[new_priority][dst_index]);
00444
00445
00446
00447
00448 p.index = dst_index;
00449 dst_vec[new_priority][p.index] = index;
00450 }
00451 assert(p.index < dst_vec[p.priority(m_sequenced_download_threshold)].size());
00452 assert(dst_vec[p.priority(m_sequenced_download_threshold)][p.index] == index);
00453
00454 if (priority >= m_sequenced_download_threshold)
00455 {
00456
00457 std::vector<int>& v = src_vec[priority];
00458 v.erase(v.begin() + elem_index);
00459 for (std::vector<int>::iterator i = v.begin() + elem_index;
00460 i != v.end(); ++i)
00461 {
00462 --m_piece_map[*i].index;
00463 assert(v[m_piece_map[*i].index] == *i);
00464 }
00465 }
00466 else
00467 {
00468
00469
00470 int replace_index = src_vec[priority][elem_index] = src_vec[priority].back();
00471 if (index != replace_index)
00472 {
00473
00474 m_piece_map[replace_index].index = elem_index;
00475
00476 assert((int)src_vec[priority].size() > elem_index);
00477
00478
00479
00480 assert((int)m_piece_map[replace_index].index == elem_index);
00481 assert(src_vec[priority][elem_index] == replace_index);
00482 }
00483 else
00484 {
00485 assert((int)src_vec[priority].size() == elem_index+1);
00486 }
00487
00488 src_vec[priority].pop_back();
00489 }
00490 }
00491
00492 void piece_picker::remove(bool downloading, bool filtered, int priority
00493 , int elem_index)
00494 {
00495 assert(!filtered);
00496 assert(priority >= 0);
00497 assert(elem_index >= 0);
00498 assert(m_files_checked_called);
00499
00500 std::vector<std::vector<int> >& src_vec(pick_piece_info_vector(downloading, filtered));
00501
00502 assert((int)src_vec.size() > priority);
00503 assert((int)src_vec[priority].size() > elem_index);
00504
00505 int index = src_vec[priority][elem_index];
00506
00507 if (downloading)
00508 {
00509 std::vector<downloading_piece>::iterator i
00510 = std::find_if(m_downloads.begin(),
00511 m_downloads.end(),
00512 has_index(index));
00513 assert(i != m_downloads.end());
00514 m_downloads.erase(i);
00515 }
00516 piece_pos& p = m_piece_map[index];
00517 p.downloading = 0;
00518 if (p.ordered(m_sequenced_download_threshold))
00519 {
00520 std::vector<int>& v = src_vec[priority];
00521
00522 std::vector<int>::iterator i = v.begin() + elem_index;
00523 v.erase(i);
00524 i = v.begin() + elem_index;
00525 for (; i != v.end(); ++i)
00526 {
00527 --m_piece_map[*i].index;
00528 assert(v[m_piece_map[*i].index] == *i);
00529 }
00530
00531 }
00532 else
00533 {
00534
00535
00536 index = src_vec[priority][elem_index] = src_vec[priority].back();
00537
00538 if ((int)src_vec[priority].size() > elem_index+1)
00539 m_piece_map[index].index = elem_index;
00540 src_vec[priority].pop_back();
00541 }
00542 }
00543
00544 void piece_picker::restore_piece(int index)
00545 {
00546 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00547
00548 assert(index >= 0);
00549 assert(index < (int)m_piece_map.size());
00550 assert(m_files_checked_called);
00551
00552 assert(m_piece_map[index].downloading == 1);
00553
00554 std::vector<downloading_piece>::iterator i
00555 = std::find_if(m_downloads.begin(),
00556 m_downloads.end(),
00557 has_index(index));
00558 assert(i != m_downloads.end());
00559 m_downloads.erase(i);
00560
00561 m_piece_map[index].downloading = 0;
00562 piece_pos& p = m_piece_map[index];
00563 if (p.filtered) return;
00564 move(true, p.filtered, p.priority(m_sequenced_download_threshold), p.index);
00565 }
00566
00567 void piece_picker::inc_refcount(int i)
00568 {
00569 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00570 assert(i >= 0);
00571 assert(i < (int)m_piece_map.size());
00572 assert(m_files_checked_called);
00573
00574 int index = m_piece_map[i].index;
00575 int prev_priority = m_piece_map[i].priority(m_sequenced_download_threshold);
00576
00577 assert(m_piece_map[i].peer_count < 2048);
00578 m_piece_map[i].peer_count++;
00579 assert(m_piece_map[i].peer_count != 0);
00580
00581 piece_pos& p = m_piece_map[i];
00582
00583
00584
00585 if (index == piece_pos::we_have_index || p.filtered
00586 || p.priority(m_sequenced_download_threshold) == prev_priority) return;
00587
00588 move(p.downloading, p.filtered, prev_priority, index);
00589
00590 #ifndef NDEBUG
00591
00592 #endif
00593 return;
00594 }
00595
00596 void piece_picker::dec_refcount(int i)
00597 {
00598 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00599
00600 assert(m_files_checked_called);
00601 assert(i >= 0);
00602 assert(i < (int)m_piece_map.size());
00603
00604 int prev_priority = m_piece_map[i].priority(m_sequenced_download_threshold);
00605 int index = m_piece_map[i].index;
00606 assert(m_piece_map[i].peer_count > 0);
00607
00608 if (m_piece_map[i].peer_count > 0)
00609 m_piece_map[i].peer_count--;
00610
00611 piece_pos& p = m_piece_map[i];
00612
00613 if (index == piece_pos::we_have_index || p.filtered
00614 || p.priority(m_sequenced_download_threshold) == prev_priority) return;
00615
00616 move(p.downloading, p.filtered, prev_priority, index);
00617 }
00618
00619
00620
00621
00622
00623 void piece_picker::we_have(int index)
00624 {
00625 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00626 assert(index >= 0);
00627 assert(index < (int)m_piece_map.size());
00628
00629 int info_index = m_piece_map[index].index;
00630 int priority = m_piece_map[index].priority(m_sequenced_download_threshold);
00631
00632 assert(m_piece_map[index].downloading == 1);
00633
00634 assert(info_index != piece_pos::we_have_index);
00635 piece_pos& p = m_piece_map[index];
00636 if (p.filtered)
00637 {
00638 --m_num_filtered;
00639 ++m_num_have_filtered;
00640 }
00641 if (info_index == piece_pos::we_have_index) return;
00642 remove(p.downloading, p.filtered, priority, info_index);
00643 p.index = piece_pos::we_have_index;
00644 }
00645
00646 void piece_picker::mark_as_filtered(int index)
00647 {
00648 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00649 assert(index >= 0);
00650 assert(index < (int)m_piece_map.size());
00651
00652 piece_pos& p = m_piece_map[index];
00653 if (p.filtered == 1) return;
00654 p.filtered = 1;
00655 if (p.index != piece_pos::we_have_index)
00656 {
00657 ++m_num_filtered;
00658 remove(p.downloading, false, p.priority(m_sequenced_download_threshold), p.index);
00659 assert(p.filtered == 1);
00660 }
00661 else
00662 {
00663 ++m_num_have_filtered;
00664 }
00665 }
00666
00667
00668
00669
00670
00671
00672 void piece_picker::mark_as_unfiltered(int index)
00673 {
00674 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00675 assert(index >= 0);
00676 assert(index < (int)m_piece_map.size());
00677
00678 piece_pos& p = m_piece_map[index];
00679 if (p.filtered == 0) return;
00680 p.filtered = 0;
00681 if (p.index != piece_pos::we_have_index)
00682 {
00683 --m_num_filtered;
00684 assert(m_num_filtered >= 0);
00685 add(index);
00686 }
00687 else
00688 {
00689 --m_num_have_filtered;
00690 assert(m_num_have_filtered >= 0);
00691 }
00692 }
00693
00694 bool piece_picker::is_filtered(int index) const
00695 {
00696 assert(index >= 0);
00697 assert(index < (int)m_piece_map.size());
00698
00699 return m_piece_map[index].filtered == 1;
00700 }
00701
00702 void piece_picker::filtered_pieces(std::vector<bool>& mask) const
00703 {
00704 mask.resize(m_piece_map.size());
00705 std::vector<bool>::iterator j = mask.begin();
00706 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin(),
00707 end(m_piece_map.end()); i != end; ++i, ++j)
00708 {
00709 *j = i->filtered == 1;
00710 }
00711 }
00712
00713 void piece_picker::pick_pieces(const std::vector<bool>& pieces
00714 , std::vector<piece_block>& interesting_blocks
00715 , int num_blocks, bool prefer_whole_pieces
00716 , tcp::endpoint peer) const
00717 {
00718 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00719 assert(num_blocks > 0);
00720 assert(pieces.size() == m_piece_map.size());
00721 assert(m_files_checked_called);
00722
00723
00724
00725
00726
00727
00728 assert(m_piece_info.begin() != m_piece_info.end());
00729
00730
00731 std::vector<std::vector<int> >::const_iterator free
00732 = m_piece_info.begin() + 1;
00733 assert(m_downloading_piece_info.begin()
00734 != m_downloading_piece_info.end());
00735
00736 std::vector<std::vector<int> >::const_iterator partial
00737 = m_downloading_piece_info.begin() + 1;
00738
00739 std::vector<piece_block> backup_blocks;
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759 while((free != m_piece_info.end())
00760 || (partial != m_downloading_piece_info.end()))
00761 {
00762 if (partial != m_downloading_piece_info.end())
00763 {
00764 for (int i = 0; i < 2; ++i)
00765 {
00766 num_blocks = add_interesting_blocks_partial(*partial, pieces
00767 , interesting_blocks, backup_blocks, num_blocks
00768 , prefer_whole_pieces, peer);
00769 assert(num_blocks >= 0);
00770 if (num_blocks == 0) return;
00771 ++partial;
00772 if (partial == m_downloading_piece_info.end()) break;
00773 }
00774 }
00775
00776 if (free != m_piece_info.end())
00777 {
00778 num_blocks = add_interesting_blocks_free(*free, pieces
00779 , interesting_blocks, num_blocks, prefer_whole_pieces);
00780 assert(num_blocks >= 0);
00781 if (num_blocks == 0) return;
00782 ++free;
00783 }
00784 }
00785
00786 if (!prefer_whole_pieces) return;
00787 assert(num_blocks > 0);
00788
00789 #ifdef TORRENT_VERBOSE_LOGGING
00790
00791 #endif
00792
00793 interesting_blocks.insert(interesting_blocks.end()
00794 , backup_blocks.begin(), backup_blocks.begin()
00795 + (std::min)(num_blocks, (int)backup_blocks.size()));
00796 }
00797
00798 namespace
00799 {
00800 bool exclusively_requested_from(piece_picker::downloading_piece const& p
00801 , int num_blocks_in_piece, tcp::endpoint peer)
00802 {
00803 for (int j = 0; j < num_blocks_in_piece; ++j)
00804 {
00805 if ((p.finished_blocks[j] == 1
00806 || p.requested_blocks[j] == 1)
00807 && p.info[j].peer != peer
00808 && p.info[j].peer != tcp::endpoint())
00809 {
00810 return false;
00811 }
00812 }
00813 return true;
00814 }
00815 }
00816
00817 int piece_picker::add_interesting_blocks_free(std::vector<int> const& piece_list
00818 , std::vector<bool> const& pieces
00819 , std::vector<piece_block>& interesting_blocks
00820 , int num_blocks, bool prefer_whole_pieces) const
00821 {
00822 for (std::vector<int>::const_iterator i = piece_list.begin();
00823 i != piece_list.end(); ++i)
00824 {
00825 assert(*i >= 0);
00826 assert(*i < (int)m_piece_map.size());
00827 assert(m_piece_map[*i].downloading == 0);
00828
00829
00830
00831 if (!pieces[*i]) continue;
00832
00833 int piece_blocks = blocks_in_piece(*i);
00834 if (!prefer_whole_pieces && piece_blocks > num_blocks)
00835 piece_blocks = num_blocks;
00836 for (int j = 0; j < piece_blocks; ++j)
00837 {
00838 interesting_blocks.push_back(piece_block(*i, j));
00839 }
00840 num_blocks -= (std::min)(piece_blocks, num_blocks);
00841 assert(num_blocks >= 0);
00842 if (num_blocks == 0) return num_blocks;
00843 }
00844 return num_blocks;
00845 }
00846
00847 int piece_picker::add_interesting_blocks_partial(std::vector<int> const& piece_list
00848 , const std::vector<bool>& pieces
00849 , std::vector<piece_block>& interesting_blocks
00850 , std::vector<piece_block>& backup_blocks
00851 , int num_blocks, bool prefer_whole_pieces
00852 , tcp::endpoint peer) const
00853 {
00854 assert(num_blocks > 0);
00855
00856 for (std::vector<int>::const_iterator i = piece_list.begin();
00857 i != piece_list.end(); ++i)
00858 {
00859 assert(*i >= 0);
00860 assert(*i < (int)m_piece_map.size());
00861
00862
00863 if (!pieces[*i]) continue;
00864
00865 assert(m_piece_map[*i].downloading == 1);
00866
00867
00868
00869
00870 int num_blocks_in_piece = blocks_in_piece(*i);
00871
00872 std::vector<downloading_piece>::const_iterator p
00873 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(*i));
00874 assert(p != m_downloads.end());
00875
00876
00877
00878
00879
00880
00881
00882
00883 if (prefer_whole_pieces
00884 && !exclusively_requested_from(*p, num_blocks_in_piece, peer))
00885 {
00886 if ((int)backup_blocks.size() >= num_blocks) continue;
00887 for (int j = 0; j < num_blocks_in_piece; ++j)
00888 {
00889 if (p->finished_blocks[j] == 1) continue;
00890 if (p->requested_blocks[j] == 1
00891 && p->info[j].peer == peer) continue;
00892 backup_blocks.push_back(piece_block(*i, j));
00893 }
00894 continue;
00895 }
00896
00897 for (int j = 0; j < num_blocks_in_piece; ++j)
00898 {
00899 if (p->finished_blocks[j] == 1) continue;
00900 if (p->requested_blocks[j] == 1
00901 && p->info[j].peer == peer) continue;
00902
00903
00904
00905
00906
00907
00908
00909
00910
00911 interesting_blocks.push_back(piece_block(*i, j));
00912 if (p->requested_blocks[j] == 0)
00913 {
00914
00915 num_blocks--;
00916 if (prefer_whole_pieces) continue;
00917 assert(num_blocks >= 0);
00918 if (num_blocks == 0) return num_blocks;
00919 }
00920 }
00921 assert(num_blocks >= 0 || prefer_whole_pieces);
00922 if (num_blocks < 0) num_blocks = 0;
00923 if (num_blocks == 0) return num_blocks;
00924 }
00925 return num_blocks;
00926 }
00927
00928 bool piece_picker::is_piece_finished(int index) const
00929 {
00930 assert(index < (int)m_piece_map.size());
00931 assert(index >= 0);
00932
00933 if (m_piece_map[index].downloading == 0)
00934 {
00935 assert(std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index))
00936 == m_downloads.end());
00937 return false;
00938 }
00939 std::vector<downloading_piece>::const_iterator i
00940 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index));
00941 assert(i != m_downloads.end());
00942 assert((int)i->finished_blocks.count() <= m_blocks_per_piece);
00943 int max_blocks = blocks_in_piece(index);
00944 if ((int)i->finished_blocks.count() < max_blocks) return false;
00945
00946 assert((int)i->requested_blocks.count() == max_blocks);
00947 return true;
00948 }
00949
00950 bool piece_picker::is_downloading(piece_block block) const
00951 {
00952 assert(block.piece_index >= 0);
00953 assert(block.block_index >= 0);
00954 assert(block.piece_index < (int)m_piece_map.size());
00955 assert(block.block_index < (int)max_blocks_per_piece);
00956
00957 if (m_piece_map[block.piece_index].downloading == 0) return false;
00958 std::vector<downloading_piece>::const_iterator i
00959 = std::find_if(
00960 m_downloads.begin()
00961 , m_downloads.end()
00962 , has_index(block.piece_index));
00963
00964 assert(i != m_downloads.end());
00965 return i->requested_blocks[block.block_index];
00966 }
00967
00968 bool piece_picker::is_finished(piece_block block) const
00969 {
00970 assert(block.piece_index >= 0);
00971 assert(block.block_index >= 0);
00972 assert(block.piece_index < (int)m_piece_map.size());
00973 assert(block.block_index < (int)max_blocks_per_piece);
00974
00975 if (m_piece_map[block.piece_index].index == piece_pos::we_have_index) return true;
00976 if (m_piece_map[block.piece_index].downloading == 0) return false;
00977 std::vector<downloading_piece>::const_iterator i
00978 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
00979 assert(i != m_downloads.end());
00980 return i->finished_blocks[block.block_index];
00981 }
00982
00983 void piece_picker::mark_as_downloading(piece_block block, const tcp::endpoint& peer)
00984 {
00985 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
00986
00987 assert(block.piece_index >= 0);
00988 assert(block.block_index >= 0);
00989 assert(block.piece_index < (int)m_piece_map.size());
00990 assert(block.block_index < blocks_in_piece(block.piece_index));
00991
00992 piece_pos& p = m_piece_map[block.piece_index];
00993 if (p.downloading == 0)
00994 {
00995 p.downloading = 1;
00996 move(false, p.filtered, p.priority(m_sequenced_download_threshold), p.index);
00997
00998 downloading_piece dp;
00999 dp.index = block.piece_index;
01000 dp.requested_blocks[block.block_index] = 1;
01001 dp.info[block.block_index].peer = peer;
01002 m_downloads.push_back(dp);
01003 }
01004 else
01005 {
01006 std::vector<downloading_piece>::iterator i
01007 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
01008 assert(i != m_downloads.end());
01009 assert(i->requested_blocks[block.block_index] == 0);
01010 i->info[block.block_index].peer = peer;
01011 i->requested_blocks[block.block_index] = 1;
01012 }
01013 }
01014
01015 void piece_picker::mark_as_finished(piece_block block, const tcp::endpoint& peer)
01016 {
01017 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
01018
01019 assert(block.piece_index >= 0);
01020 assert(block.block_index >= 0);
01021 assert(block.piece_index < (int)m_piece_map.size());
01022 assert(block.block_index < blocks_in_piece(block.piece_index));
01023
01024 piece_pos& p = m_piece_map[block.piece_index];
01025 if (p.index == piece_pos::we_have_index || p.filtered) return;
01026
01027 if (p.downloading == 0)
01028 {
01029 p.downloading = 1;
01030 move(false, p.filtered, p.priority(m_sequenced_download_threshold), p.index);
01031
01032 downloading_piece dp;
01033 dp.index = block.piece_index;
01034 dp.requested_blocks[block.block_index] = 1;
01035 dp.finished_blocks[block.block_index] = 1;
01036 dp.info[block.block_index].peer = peer;
01037 m_downloads.push_back(dp);
01038 }
01039 else
01040 {
01041 std::vector<downloading_piece>::iterator i
01042 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
01043 assert(i != m_downloads.end());
01044 i->info[block.block_index].peer = peer;
01045 i->requested_blocks[block.block_index] = 1;
01046 i->finished_blocks[block.block_index] = 1;
01047 }
01048 }
01049
01050 void piece_picker::get_downloaders(std::vector<tcp::endpoint>& d, int index) const
01051 {
01052 assert(index >= 0 && index <= (int)m_piece_map.size());
01053 std::vector<downloading_piece>::const_iterator i
01054 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index));
01055 assert(i != m_downloads.end());
01056
01057 d.clear();
01058 for (int j = 0; j < blocks_in_piece(index); ++j)
01059 {
01060 d.push_back(i->info[j].peer);
01061 }
01062 }
01063
01064 boost::optional<tcp::endpoint> piece_picker::get_downloader(piece_block block) const
01065 {
01066 std::vector<downloading_piece>::const_iterator i = std::find_if(
01067 m_downloads.begin()
01068 , m_downloads.end()
01069 , has_index(block.piece_index));
01070
01071 if (i == m_downloads.end())
01072 return boost::optional<tcp::endpoint>();
01073
01074 assert(block.block_index < max_blocks_per_piece);
01075 assert(block.block_index >= 0);
01076
01077 if (i->requested_blocks[block.block_index] == false
01078 || i->finished_blocks[block.block_index] == true)
01079 return boost::optional<tcp::endpoint>();
01080
01081 return boost::optional<tcp::endpoint>(i->info[block.block_index].peer);
01082 }
01083
01084 void piece_picker::abort_download(piece_block block)
01085 {
01086 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
01087
01088 assert(block.piece_index >= 0);
01089 assert(block.block_index >= 0);
01090 assert(block.piece_index < (int)m_piece_map.size());
01091 assert(block.block_index < blocks_in_piece(block.piece_index));
01092
01093 if (m_piece_map[block.piece_index].downloading == 0)
01094 {
01095 assert(std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index)) == m_downloads.end());
01096 return;
01097 }
01098
01099 std::vector<downloading_piece>::iterator i
01100 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
01101 assert(i != m_downloads.end());
01102
01103 if (i->finished_blocks[block.block_index]) return;
01104
01105 assert(block.block_index < blocks_in_piece(block.piece_index));
01106 #ifndef NDEBUG
01107 if (i->requested_blocks[block.block_index] == false)
01108 {
01109 assert(false);
01110 }
01111 #endif
01112
01113
01114 i->requested_blocks[block.block_index] = false;
01115
01116
01117 i->info[block.block_index].peer = tcp::endpoint();
01118
01119
01120
01121 if (i->requested_blocks.count() == 0)
01122 {
01123 m_downloads.erase(i);
01124 m_piece_map[block.piece_index].downloading = 0;
01125 piece_pos& p = m_piece_map[block.piece_index];
01126 move(true, p.filtered, p.priority(m_sequenced_download_threshold), p.index);
01127 }
01128 }
01129
01130 int piece_picker::unverified_blocks() const
01131 {
01132 int counter = 0;
01133 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin();
01134 i != m_downloads.end(); ++i)
01135 {
01136 counter += (int)i->finished_blocks.count();
01137 }
01138 return counter;
01139 }
01140
01141 }
01142
