?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
LT SYNC
[tore.git] / libtorrent / src / piece_picker.cpp
blobbb0b460a30886d3d9a8f12f9e2fe8de61c07537b
1 /*
2
3 Copyright (c) 2003, Arvid Norberg
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 <vector>
36 #include <cmath>
37 #include <algorithm>
38 #include <numeric>
39
40 #include "libtorrent/piece_picker.hpp"
41 #include "libtorrent/aux_/session_impl.hpp"
42 #include "libtorrent/bitfield.hpp"
43
44 #ifndef NDEBUG
45 #include "libtorrent/peer_connection.hpp"
46 #include "libtorrent/torrent.hpp"
47 #endif
48
49 //#define TORRENT_PIECE_PICKER_INVARIANT_CHECK INVARIANT_CHECK
50 //#define TORRENT_NO_EXPENSIVE_INVARIANT_CHECK
51 #define TORRENT_PIECE_PICKER_INVARIANT_CHECK
52
53 //#define TORRENT_PICKER_LOG
54
55 namespace libtorrent
56 {
57
58 piece_picker::piece_picker()
59 : m_seeds(0)
60 , m_priority_boundries(1, int(m_pieces.size()))
61 , m_num_filtered(0)
62 , m_num_have_filtered(0)
63 , m_num_have(0)
64 , m_sequential_download(-1)
65 , m_dirty(false)
66 {
67 #ifdef TORRENT_PICKER_LOG
68 std::cerr << "new piece_picker" << std::endl;
69 #endif
70 #ifndef NDEBUG
71 check_invariant();
72 #endif
73 }
74
75 void piece_picker::init(int blocks_per_piece, int total_num_blocks)
76 {
77 TORRENT_ASSERT(blocks_per_piece > 0);
78 TORRENT_ASSERT(total_num_blocks >= 0);
79
80 // allocate the piece_map to cover all pieces
81 // and make them invalid (as if we don't have a single piece)
82 m_piece_map.resize((total_num_blocks + blocks_per_piece-1) / blocks_per_piece
83 , piece_pos(0, 0));
84
85 m_num_filtered += m_num_have_filtered;
86 m_num_have_filtered = 0;
87 m_num_have = 0;
88 m_dirty = true;
89 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
90 , end(m_piece_map.end()); i != end; ++i)
91 {
92 i->peer_count = 0;
93 i->downloading = 0;
94 i->index = 0;
95 }
96
97 // the piece index is stored in 20 bits, which limits the allowed
98 // number of pieces somewhat
99 if (m_piece_map.size() >= piece_pos::we_have_index)
100 throw std::runtime_error("too many pieces in torrent");
101
102 m_blocks_per_piece = blocks_per_piece;
103 m_blocks_in_last_piece = total_num_blocks % blocks_per_piece;
104 if (m_blocks_in_last_piece == 0) m_blocks_in_last_piece = blocks_per_piece;
105
106 TORRENT_ASSERT(m_blocks_in_last_piece <= m_blocks_per_piece);
107 }
108
109 void piece_picker::sequential_download(bool sd)
110 {
111 if (sd == sequential_download()) return;
112
113 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
114
115 if (sd)
116 {
117 std::vector<int>().swap(m_pieces);
118 std::vector<int>().swap(m_priority_boundries);
119
120 // initialize m_sdquential_download
121 m_sequential_download = 0;
122 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
123 , end(m_piece_map.end()); i != end && (i->have() || i->filtered());
124 ++i, ++m_sequential_download);
125 }
126 else
127 {
128 m_sequential_download = -1;
129 m_dirty = true;
130 }
131 }
132
133 void piece_picker::piece_info(int index, piece_picker::downloading_piece& st) const
134 {
135 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
136
137 TORRENT_ASSERT(index >= 0);
138 TORRENT_ASSERT(index < int(m_piece_map.size()));
139
140 if (m_piece_map[index].downloading)
141 {
142 std::vector<downloading_piece>::const_iterator piece = std::find_if(
143 m_downloads.begin(), m_downloads.end()
144 , bind(&downloading_piece::index, _1) == index);
145 TORRENT_ASSERT(piece != m_downloads.end());
146 st = *piece;
147 st.info = 0;
148 return;
149 }
150 st.info = 0;
151 st.index = index;
152 st.writing = 0;
153 st.requested = 0;
154 if (m_piece_map[index].have())
155 {
156 st.finished = blocks_in_piece(index);
157 return;
158 }
159 st.finished = 0;
160 }
161
162 piece_picker::downloading_piece& piece_picker::add_download_piece()
163 {
164 int num_downloads = m_downloads.size();
165 int block_index = num_downloads * m_blocks_per_piece;
166 if (int(m_block_info.size()) < block_index + m_blocks_per_piece)
167 {
168 block_info* base = 0;
169 if (!m_block_info.empty()) base = &m_block_info[0];
170 m_block_info.resize(block_index + m_blocks_per_piece);
171 if (!m_downloads.empty() && &m_block_info[0] != base)
172 {
173 // this means the memory was reallocated, update the pointers
174 for (int i = 0; i < int(m_downloads.size()); ++i)
175 m_downloads[i].info = &m_block_info[m_downloads[i].info - base];
176 }
177 }
178 m_downloads.push_back(downloading_piece());
179 downloading_piece& ret = m_downloads.back();
180 ret.info = &m_block_info[block_index];
181 for (int i = 0; i < m_blocks_per_piece; ++i)
182 {
183 ret.info[i].num_peers = 0;
184 ret.info[i].state = block_info::state_none;
185 ret.info[i].peer = 0;
186 }
187 return ret;
188 }
189
190 void piece_picker::erase_download_piece(std::vector<downloading_piece>::iterator i)
191 {
192 std::vector<downloading_piece>::iterator other = std::find_if(
193 m_downloads.begin(), m_downloads.end()
194 , bind(&downloading_piece::info, _1)
195 == &m_block_info[(m_downloads.size() - 1) * m_blocks_per_piece]);
196 TORRENT_ASSERT(other != m_downloads.end());
197
198 if (i != other)
199 {
200 std::copy(other->info, other->info + m_blocks_per_piece, i->info);
201 other->info = i->info;
202 }
203 m_downloads.erase(i);
204 }
205
206 #ifndef NDEBUG
207
208 void piece_picker::verify_pick(std::vector<piece_block> const& picked
209 , bitfield const& bits) const
210 {
211 TORRENT_ASSERT(bits.size() == m_piece_map.size());
212 for (std::vector<piece_block>::const_iterator i = picked.begin()
213 , end(picked.end()); i != end; ++i)
214 {
215 TORRENT_ASSERT(i->piece_index >= 0);
216 TORRENT_ASSERT(i->piece_index < int(bits.size()));
217 TORRENT_ASSERT(bits[i->piece_index]);
218 TORRENT_ASSERT(!m_piece_map[i->piece_index].have());
219 }
220 }
221
222 void piece_picker::verify_priority(int range_start, int range_end, int prio) const
223 {
224 TORRENT_ASSERT(range_start <= range_end);
225 TORRENT_ASSERT(range_end <= int(m_pieces.size()));
226 for (std::vector<int>::const_iterator i = m_pieces.begin() + range_start
227 , end(m_pieces.begin() + range_end); i != end; ++i)
228 {
229 int index = *i;
230 TORRENT_ASSERT(index >= 0);
231 TORRENT_ASSERT(index < int(m_piece_map.size()));
232 int p = m_piece_map[index].priority(this);
233 TORRENT_ASSERT(p == prio);
234 }
235 }
236
237 #ifdef TORRENT_PICKER_LOG
238 void piece_picker::print_pieces() const
239 {
240 for (std::vector<int>::const_iterator i = m_priority_boundries.begin()
241 , end(m_priority_boundries.end()); i != end; ++i)
242 {
243 std::cerr << *i << " ";
244 }
245 std::cout << std::endl;
246 int index = 0;
247 std::vector<int>::const_iterator j = m_priority_boundries.begin();
248 for (std::vector<int>::const_iterator i = m_pieces.begin()
249 , end(m_pieces.end()); i != end; ++i, ++index)
250 {
251 if (*i == -1) break;
252 while (j != m_priority_boundries.end() && *j <= index)
253 {
254 std::cerr << "| ";
255 ++j;
256 }
257 std::cerr << *i << "(" << m_piece_map[*i].index << ") ";
258 }
259 std::cerr << std::endl;
260 }
261 #endif
262
263 void piece_picker::check_invariant(const torrent* t) const
264 {
265 TORRENT_ASSERT(sizeof(piece_pos) == 4);
266 TORRENT_ASSERT(m_num_have >= 0);
267 TORRENT_ASSERT(m_num_have_filtered >= 0);
268 TORRENT_ASSERT(m_num_filtered >= 0);
269 TORRENT_ASSERT(m_seeds >= 0);
270
271 if (!m_downloads.empty())
272 {
273 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin();
274 i != m_downloads.end() - 1; ++i)
275 {
276 downloading_piece const& dp = *i;
277 downloading_piece const& next = *(i + 1);
278 TORRENT_ASSERT(dp.finished + dp.writing >= next.finished + next.writing);
279 }
280 }
281
282 if (t != 0)
283 TORRENT_ASSERT((int)m_piece_map.size() == t->torrent_file().num_pieces());
284
285 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
286 , end(m_downloads.end()); i != end; ++i)
287 {
288 bool blocks_requested = false;
289 int num_blocks = blocks_in_piece(i->index);
290 int num_requested = 0;
291 int num_finished = 0;
292 int num_writing = 0;
293 for (int k = 0; k < num_blocks; ++k)
294 {
295 if (i->info[k].state == block_info::state_finished)
296 {
297 ++num_finished;
298 TORRENT_ASSERT(i->info[k].num_peers == 0);
299 }
300 else if (i->info[k].state == block_info::state_requested)
301 {
302 ++num_requested;
303 blocks_requested = true;
304 TORRENT_ASSERT(i->info[k].num_peers > 0);
305 }
306 else if (i->info[k].state == block_info::state_writing)
307 {
308 ++num_writing;
309 TORRENT_ASSERT(i->info[k].num_peers == 0);
310 }
311 }
312 TORRENT_ASSERT(blocks_requested == (i->state != none));
313 TORRENT_ASSERT(num_requested == i->requested);
314 TORRENT_ASSERT(num_writing == i->writing);
315 TORRENT_ASSERT(num_finished == i->finished);
316 }
317 #ifdef TORRENT_NO_EXPENSIVE_INVARIANT_CHECK
318 return;
319 #endif
320
321 if (m_sequential_download == -1 && !m_dirty)
322 {
323 TORRENT_ASSERT(!m_priority_boundries.empty());
324 int prio = 0;
325 int start = 0;
326 for (std::vector<int>::const_iterator i = m_priority_boundries.begin()
327 , end(m_priority_boundries.end()); i != end; ++i)
328 {
329 verify_priority(start, *i, prio);
330 ++prio;
331 start = *i;
332 }
333 TORRENT_ASSERT(m_priority_boundries.back() == int(m_pieces.size()));
334 }
335 else if (m_sequential_download >= 0)
336 {
337 int index = 0;
338 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
339 , end(m_piece_map.end()); i != end && (i->have() || i->filtered());
340 ++i, ++index);
341 TORRENT_ASSERT(m_sequential_download == index);
342 }
343
344 int num_filtered = 0;
345 int num_have_filtered = 0;
346 int num_have = 0;
347 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin();
348 i != m_piece_map.end(); ++i)
349 {
350 int index = static_cast<int>(i - m_piece_map.begin());
351 piece_pos const& p = *i;
352
353 if (p.filtered())
354 {
355 if (p.index != piece_pos::we_have_index)
356 ++num_filtered;
357 else
358 ++num_have_filtered;
359 }
360 if (p.index == piece_pos::we_have_index)
361 ++num_have;
362
363 #if 0
364 if (t != 0)
365 {
366 int actual_peer_count = 0;
367 for (torrent::const_peer_iterator peer = t->begin();
368 peer != t->end(); ++peer)
369 {
370 if (peer->second->has_piece(index)) actual_peer_count++;
371 }
372
373 TORRENT_ASSERT((int)i->peer_count == actual_peer_count);
374 /*
375 int num_downloaders = 0;
376 for (std::vector<peer_connection*>::const_iterator peer = t->begin();
377 peer != t->end();
378 ++peer)
379 {
380 const std::vector<piece_block>& queue = (*peer)->download_queue();
381 if (std::find_if(queue.begin(), queue.end(), has_index(index)) == queue.end()) continue;
382
383 ++num_downloaders;
384 }
385
386 if (i->downloading)
387 {
388 TORRENT_ASSERT(num_downloaders == 1);
389 }
390 else
391 {
392 TORRENT_ASSERT(num_downloaders == 0);
393 }
394 */
395 }
396 #endif
397
398 if (p.index == piece_pos::we_have_index)
399 {
400 TORRENT_ASSERT(t == 0 || t->have_piece(index));
401 TORRENT_ASSERT(p.downloading == 0);
402 }
403
404 if (t != 0)
405 TORRENT_ASSERT(!t->have_piece(index));
406
407 if (m_sequential_download == -1 && !m_dirty)
408 {
409 int prio = p.priority(this);
410 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
411 || m_dirty);
412 if (prio >= 0)
413 {
414 TORRENT_ASSERT(p.index < m_pieces.size());
415 TORRENT_ASSERT(m_pieces[p.index] == index);
416 }
417 else
418 {
419 TORRENT_ASSERT(prio == -1);
420 // make sure there's no entry
421 // with this index. (there shouldn't
422 // be since the priority is -1)
423 TORRENT_ASSERT(std::find(m_pieces.begin(), m_pieces.end(), index)
424 == m_pieces.end());
425 }
426 }
427 else if (m_sequential_download >= 0)
428 {
429 TORRENT_ASSERT(m_pieces.empty());
430 TORRENT_ASSERT(m_priority_boundries.empty());
431 }
432
433 int count = std::count_if(m_downloads.begin(), m_downloads.end()
434 , has_index(index));
435 if (i->downloading == 1)
436 {
437 TORRENT_ASSERT(count == 1);
438 }
439 else
440 {
441 TORRENT_ASSERT(count == 0);
442 }
443 }
444 TORRENT_ASSERT(num_have == m_num_have);
445 TORRENT_ASSERT(num_filtered == m_num_filtered);
446 TORRENT_ASSERT(num_have_filtered == m_num_have_filtered);
447
448 if (!m_dirty)
449 {
450 for (std::vector<int>::const_iterator i = m_pieces.begin()
451 , end(m_pieces.end()); i != end; ++i)
452 {
453 TORRENT_ASSERT(m_piece_map[*i].priority(this) >= 0);
454 }
455 }
456 }
457 #endif
458
459 float piece_picker::distributed_copies() const
460 {
461 TORRENT_ASSERT(m_seeds >= 0);
462 const float num_pieces = static_cast<float>(m_piece_map.size());
463
464 int min_availability = piece_pos::max_peer_count;
465 // find the lowest availability count
466 // count the number of pieces that have that availability
467 // and also the number of pieces that have more than that.
468 int integer_part = 0;
469 int fraction_part = 0;
470 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
471 , end(m_piece_map.end()); i != end; ++i)
472 {
473 int peer_count = int(i->peer_count);
474 // take ourself into account
475 if (i->have()) ++peer_count;
476 if (min_availability > peer_count)
477 {
478 min_availability = peer_count;
479 fraction_part += integer_part;
480 integer_part = 1;
481 }
482 else if (peer_count == min_availability)
483 {
484 ++integer_part;
485 }
486 else
487 {
488 TORRENT_ASSERT(peer_count > min_availability);
489 ++fraction_part;
490 }
491 }
492 TORRENT_ASSERT(integer_part + fraction_part == num_pieces);
493 return float(min_availability + m_seeds) + (fraction_part / num_pieces);
494 }
495
496 void piece_picker::priority_range(int prio, int* start, int* end)
497 {
498 TORRENT_ASSERT(prio >= 0);
499 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
500 || m_dirty);
501 if (prio == 0) *start = 0;
502 else *start = m_priority_boundries[prio - 1];
503 *end = m_priority_boundries[prio];
504 TORRENT_ASSERT(*start <= *end);
505 }
506
507 void piece_picker::add(int index)
508 {
509 TORRENT_ASSERT(!m_dirty);
510 TORRENT_ASSERT(index >= 0);
511 TORRENT_ASSERT(index < int(m_piece_map.size()));
512 piece_pos& p = m_piece_map[index];
513 TORRENT_ASSERT(!p.filtered());
514 TORRENT_ASSERT(!p.have());
515 TORRENT_ASSERT(m_sequential_download == -1);
516
517 int priority = p.priority(this);
518 TORRENT_ASSERT(priority >= 0);
519 if (int(m_priority_boundries.size()) <= priority)
520 m_priority_boundries.resize(priority + 1, m_pieces.size());
521
522 TORRENT_ASSERT(int(m_priority_boundries.size()) >= priority);
523
524 int range_start, range_end;
525 priority_range(priority, &range_start, &range_end);
526 int new_index;
527 if (range_end == range_start) new_index = range_start;
528 else new_index = rand() % (range_end - range_start + 1) + range_start;
529
530 #ifdef TORRENT_PICKER_LOG
531 std::cerr << "add " << index << " (" << priority << ")" << std::endl;
532 print_pieces();
533 #endif
534 m_pieces.push_back(-1);
535
536 for (;;)
537 {
538 TORRENT_ASSERT(new_index < int(m_pieces.size()));
539 int temp = m_pieces[new_index];
540 m_pieces[new_index] = index;
541 m_piece_map[index].index = new_index;
542 index = temp;
543 do
544 {
545 temp = m_priority_boundries[priority]++;
546 ++priority;
547 } while (temp == new_index && priority < int(m_priority_boundries.size()));
548 new_index = temp;
549 #ifdef TORRENT_PICKER_LOG
550 print_pieces();
551 std::cerr << " index: " << index
552 << " prio: " << priority
553 << " new_index: " << new_index
554 << std::endl;
555 #endif
556 if (priority >= int(m_priority_boundries.size())) break;
557 TORRENT_ASSERT(temp >= 0);
558 }
559 if (index != -1)
560 {
561 TORRENT_ASSERT(new_index == int(m_pieces.size() - 1));
562 m_pieces[new_index] = index;
563 m_piece_map[index].index = new_index;
564
565 #ifdef TORRENT_PICKER_LOG
566 print_pieces();
567 #endif
568 }
569 }
570
571 void piece_picker::remove(int priority, int elem_index)
572 {
573 TORRENT_ASSERT(!m_dirty);
574 TORRENT_ASSERT(priority >= 0);
575 TORRENT_ASSERT(m_sequential_download == -1);
576
577 #ifdef TORRENT_PICKER_LOG
578 std::cerr << "remove " << m_pieces[elem_index] << " (" << priority << ")" << std::endl;
579 #endif
580 int next_index = elem_index;
581 TORRENT_ASSERT(m_piece_map[m_pieces[elem_index]].priority(this) == -1);
582 for (;;)
583 {
584 #ifdef TORRENT_PICKER_LOG
585 print_pieces();
586 #endif
587 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
588 int temp;
589 do
590 {
591 temp = --m_priority_boundries[priority];
592 ++priority;
593 } while (next_index == temp && priority < int(m_priority_boundries.size()));
594 if (next_index == temp) break;
595 next_index = temp;
596
597 int piece = m_pieces[next_index];
598 m_pieces[elem_index] = piece;
599 m_piece_map[piece].index = elem_index;
600 TORRENT_ASSERT(m_piece_map[piece].priority(this) == priority - 1);
601 TORRENT_ASSERT(elem_index < int(m_pieces.size() - 1));
602 elem_index = next_index;
603
604 if (priority == int(m_priority_boundries.size()))
605 break;
606 }
607 m_pieces.pop_back();
608 TORRENT_ASSERT(next_index == int(m_pieces.size()));
609 #ifdef TORRENT_PICKER_LOG
610 print_pieces();
611 #endif
612 }
613
614 // will update the piece with the given properties (priority, elem_index)
615 // to place it at the correct position
616 void piece_picker::update(int priority, int elem_index)
617 {
618 TORRENT_ASSERT(!m_dirty);
619 TORRENT_ASSERT(priority >= 0);
620 TORRENT_ASSERT(elem_index >= 0);
621 TORRENT_ASSERT(m_sequential_download == -1);
622
623 TORRENT_ASSERT(int(m_priority_boundries.size()) > priority);
624
625 int index = m_pieces[elem_index];
626 // update the piece_map
627 piece_pos& p = m_piece_map[index];
628 TORRENT_ASSERT(int(p.index) == elem_index || p.have());
629
630 int new_priority = p.priority(this);
631
632 if (new_priority == priority) return;
633
634 if (new_priority == -1)
635 {
636 remove(priority, elem_index);
637 return;
638 }
639
640 if (int(m_priority_boundries.size()) <= new_priority)
641 m_priority_boundries.resize(new_priority + 1, m_pieces.size());
642
643 #ifdef TORRENT_PICKER_LOG
644 std::cerr << "update " << index << " (" << priority << "->" << new_priority << ")" << std::endl;
645 #endif
646 if (priority > new_priority)
647 {
648 int new_index;
649 int temp = index;
650 for (;;)
651 {
652 #ifdef TORRENT_PICKER_LOG
653 print_pieces();
654 #endif
655 --priority;
656 new_index = m_priority_boundries[priority]++;
657 TORRENT_ASSERT(new_index < int(m_pieces.size()));
658 if (temp != m_pieces[new_index])
659 {
660 temp = m_pieces[new_index];
661 m_pieces[elem_index] = temp;
662 m_piece_map[temp].index = elem_index;
663 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
664 }
665 elem_index = new_index;
666 if (priority == new_priority) break;
667 }
668 #ifdef TORRENT_PICKER_LOG
669 print_pieces();
670 #endif
671 m_pieces[elem_index] = index;
672 m_piece_map[index].index = elem_index;
673 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
674 #ifdef TORRENT_PICKER_LOG
675 print_pieces();
676 #endif
677 shuffle(priority, elem_index);
678 #ifdef TORRENT_PICKER_LOG
679 print_pieces();
680 #endif
681 TORRENT_ASSERT(m_piece_map[index].priority(this) == priority);
682 }
683 else
684 {
685 int new_index;
686 int temp = index;
687 for (;;)
688 {
689 #ifdef TORRENT_PICKER_LOG
690 print_pieces();
691 #endif
692 new_index = --m_priority_boundries[priority];
693 TORRENT_ASSERT(new_index < int(m_pieces.size()));
694 if (temp != m_pieces[new_index])
695 {
696 temp = m_pieces[new_index];
697 m_pieces[elem_index] = temp;
698 m_piece_map[temp].index = elem_index;
699 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
700 }
701 elem_index = new_index;
702 ++priority;
703 if (priority == new_priority) break;
704 }
705 #ifdef TORRENT_PICKER_LOG
706 print_pieces();
707 #endif
708 m_pieces[elem_index] = index;
709 m_piece_map[index].index = elem_index;
710 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
711 #ifdef TORRENT_PICKER_LOG
712 print_pieces();
713 #endif
714 shuffle(priority, elem_index);
715 #ifdef TORRENT_PICKER_LOG
716 print_pieces();
717 #endif
718 TORRENT_ASSERT(m_piece_map[index].priority(this) == priority);
719 }
720 }
721
722 void piece_picker::shuffle(int priority, int elem_index)
723 {
724 TORRENT_ASSERT(!m_dirty);
725 TORRENT_ASSERT(priority >= 0);
726 TORRENT_ASSERT(elem_index >= 0);
727 TORRENT_ASSERT(m_sequential_download == -1);
728
729 int range_start, range_end;
730 priority_range(priority, &range_start, &range_end);
731 TORRENT_ASSERT(range_start < range_end);
732 int other_index = rand() % (range_end - range_start) + range_start;
733
734 if (other_index == elem_index) return;
735
736 // swap other_index with elem_index
737 piece_pos& p1 = m_piece_map[m_pieces[other_index]];
738 piece_pos& p2 = m_piece_map[m_pieces[elem_index]];
739
740 int temp = p1.index;
741 p1.index = p2.index;
742 p2.index = temp;
743 std::swap(m_pieces[other_index], m_pieces[elem_index]);
744 }
745
746 void piece_picker::sort_piece(std::vector<downloading_piece>::iterator dp)
747 {
748 TORRENT_ASSERT(m_piece_map[dp->index].downloading);
749 if (dp == m_downloads.begin()) return;
750 int complete = dp->writing + dp->finished;
751 for (std::vector<downloading_piece>::iterator i = dp, j(dp-1);
752 i != m_downloads.begin(); --i, --j)
753 {
754 TORRENT_ASSERT(j >= m_downloads.begin());
755 if (j->finished + j->writing >= complete) return;
756 using std::swap;
757 swap(*j, *i);
758 if (j == m_downloads.begin()) break;
759 }
760 }
761
762 void piece_picker::restore_piece(int index)
763 {
764 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
765
766 TORRENT_ASSERT(index >= 0);
767 TORRENT_ASSERT(index < (int)m_piece_map.size());
768
769 TORRENT_ASSERT(m_piece_map[index].downloading == 1);
770
771 std::vector<downloading_piece>::iterator i
772 = std::find_if(m_downloads.begin(), m_downloads.end()
773 , has_index(index));
774
775 TORRENT_ASSERT(i != m_downloads.end());
776 erase_download_piece(i);
777
778 piece_pos& p = m_piece_map[index];
779 int prev_priority = p.priority(this);
780 p.downloading = 0;
781 int new_priority = p.priority(this);
782
783 if (new_priority == prev_priority) return;
784 if (m_dirty) return;
785 if (m_sequential_download >= 0)
786 {
787 m_dirty = true;
788 return;
789 }
790 if (prev_priority == -1)
791 {
792 add(index);
793 }
794 else
795 {
796 update(prev_priority, p.index);
797 }
798 }
799
800 void piece_picker::inc_refcount_all()
801 {
802 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
803 ++m_seeds;
804 if (m_seeds == 1)
805 {
806 // when m_seeds is increased from 0 to 1
807 // we may have to add pieces that previously
808 // didn't have any peers
809 m_dirty = true;
810 }
811 }
812
813 void piece_picker::dec_refcount_all()
814 {
815 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
816
817 if (m_seeds > 0)
818 {
819 --m_seeds;
820 if (m_seeds == 0)
821 {
822 // when m_seeds is decreased from 1 to 0
823 // we may have to remove pieces that previously
824 // didn't have any peers
825 m_dirty = true;
826 }
827 return;
828 }
829 TORRENT_ASSERT(m_seeds == 0);
830
831 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
832 , end(m_piece_map.end()); i != end; ++i)
833 {
834 TORRENT_ASSERT(i->peer_count > 0);
835 --i->peer_count;
836 }
837
838 m_dirty = true;
839 }
840
841 void piece_picker::inc_refcount(int index)
842 {
843 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
844
845 piece_pos& p = m_piece_map[index];
846 if (m_sequential_download >= 0)
847 {
848 ++p.peer_count;
849 m_dirty = true;
850 return;
851 }
852
853 int prev_priority = p.priority(this);
854 ++p.peer_count;
855 if (m_dirty) return;
856 int new_priority = p.priority(this);
857 if (prev_priority == new_priority) return;
858 if (prev_priority == -1)
859 add(index);
860 else
861 update(prev_priority, p.index);
862 }
863
864 void piece_picker::dec_refcount(int index)
865 {
866 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
867
868 piece_pos& p = m_piece_map[index];
869 if (m_sequential_download >= 0)
870 {
871 TORRENT_ASSERT(p.peer_count > 0);
872 --p.peer_count;
873 m_dirty = true;
874 return;
875 }
876 int prev_priority = p.priority(this);
877 TORRENT_ASSERT(p.peer_count > 0);
878 --p.peer_count;
879 if (m_dirty) return;
880 if (prev_priority >= 0) update(prev_priority, p.index);
881 }
882
883 void piece_picker::inc_refcount(bitfield const& bitmask)
884 {
885 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
886 TORRENT_ASSERT(bitmask.size() == m_piece_map.size());
887
888 int index = 0;
889 bool updated = false;
890 for (bitfield::const_iterator i = bitmask.begin()
891 , end(bitmask.end()); i != end; ++i, ++index)
892 {
893 if (*i)
894 {
895 ++m_piece_map[index].peer_count;
896 updated = true;
897 }
898 }
899
900 if (updated && m_sequential_download == -1) m_dirty = true;
901 }
902
903 void piece_picker::dec_refcount(bitfield const& bitmask)
904 {
905 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
906 TORRENT_ASSERT(bitmask.size() == m_piece_map.size());
907
908 int index = 0;
909 bool updated = false;
910 for (bitfield::const_iterator i = bitmask.begin()
911 , end(bitmask.end()); i != end; ++i, ++index)
912 {
913 if (*i)
914 {
915 --m_piece_map[index].peer_count;
916 updated = true;
917 }
918 }
919
920 if (updated && m_sequential_download == -1) m_dirty = true;
921 }
922
923 void piece_picker::update_pieces() const
924 {
925 TORRENT_ASSERT(m_dirty);
926 TORRENT_ASSERT(m_sequential_download == -1);
927 if (m_priority_boundries.empty()) m_priority_boundries.resize(1, 0);
928 #ifdef TORRENT_PICKER_LOG
929 std::cerr << "update_pieces" << std::endl;
930 #endif
931 std::fill(m_priority_boundries.begin(), m_priority_boundries.end(), 0);
932 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
933 , end(m_piece_map.end()); i != end; ++i)
934 {
935 int prio = i->priority(this);
936 if (prio == -1) continue;
937 if (prio >= int(m_priority_boundries.size()))
938 m_priority_boundries.resize(prio + 1, 0);
939 i->index = m_priority_boundries[prio];
940 ++m_priority_boundries[prio];
941 }
942
943 #ifdef TORRENT_PICKER_LOG
944 print_pieces();
945 #endif
946
947 int index = 0;
948 for (std::vector<int>::iterator i = m_priority_boundries.begin()
949 , end(m_priority_boundries.end()); i != end; ++i)
950 {
951 *i += index;
952 index = *i;
953 }
954 m_pieces.resize(index, 0);
955
956 #ifdef TORRENT_PICKER_LOG
957 print_pieces();
958 #endif
959
960 index = 0;
961 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
962 , end(m_piece_map.end()); i != end; ++i, ++index)
963 {
964 piece_pos& p = *i;
965 int prio = p.priority(this);
966 if (prio == -1) continue;
967 int new_index = (prio == 0 ? 0 : m_priority_boundries[prio - 1]) + p.index;
968 m_pieces[new_index] = index;
969 }
970
971 int start = 0;
972 for (std::vector<int>::iterator i = m_priority_boundries.begin()
973 , end(m_priority_boundries.end()); i != end; ++i)
974 {
975 if (start == *i) continue;
976 std::random_shuffle(&m_pieces[0] + start, &m_pieces[0] + *i);
977 start = *i;
978 }
979
980 index = 0;
981 for (std::vector<int>::const_iterator i = m_pieces.begin()
982 , end(m_pieces.end()); i != end; ++i, ++index)
983 {
984 TORRENT_ASSERT(*i >= 0 && *i < int(m_piece_map.size()));
985 m_piece_map[*i].index = index;
986 }
987
988 m_dirty = false;
989 #ifdef TORRENT_PICKER_LOG
990 print_pieces();
991 #endif
992
993 #ifndef NDEBUG
994 check_invariant();
995 #endif
996 }
997
998 void piece_picker::we_dont_have(int index)
999 {
1000 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1001 TORRENT_ASSERT(index >= 0);
1002 TORRENT_ASSERT(index < (int)m_piece_map.size());
1003
1004 piece_pos& p = m_piece_map[index];
1005 TORRENT_ASSERT(p.downloading == 0);
1006
1007 if (!p.have()) return;
1008
1009 if (m_sequential_download > index)
1010 m_sequential_download = index;
1011
1012 if (p.filtered())
1013 {
1014 ++m_num_filtered;
1015 --m_num_have_filtered;
1016 }
1017
1018 --m_num_have;
1019 p.set_not_have();
1020
1021 if (m_dirty) return;
1022 if (p.priority(this) >= 0) add(index);
1023 }
1024
1025 // this is used to indicate that we succesfully have
1026 // downloaded a piece, and that no further attempts
1027 // to pick that piece should be made. The piece will
1028 // be removed from the available piece list.
1029 void piece_picker::we_have(int index)
1030 {
1031 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1032 TORRENT_ASSERT(index >= 0);
1033 TORRENT_ASSERT(index < (int)m_piece_map.size());
1034
1035 piece_pos& p = m_piece_map[index];
1036 int info_index = p.index;
1037 int priority = p.priority(this);
1038 TORRENT_ASSERT(priority < int(m_priority_boundries.size()));
1039
1040 if (p.downloading)
1041 {
1042 std::vector<downloading_piece>::iterator i
1043 = std::find_if(m_downloads.begin()
1044 , m_downloads.end()
1045 , has_index(index));
1046 TORRENT_ASSERT(i != m_downloads.end());
1047 erase_download_piece(i);
1048 p.downloading = 0;
1049 }
1050
1051 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1052 , has_index(index)) == m_downloads.end());
1053
1054 if (m_sequential_download == index)
1055 {
1056 ++m_sequential_download;
1057 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin() + m_sequential_download
1058 , end(m_piece_map.end()); i != end && (i->have() || i->filtered());
1059 ++i, ++m_sequential_download);
1060 }
1061 if (p.have()) return;
1062 if (p.filtered())
1063 {
1064 --m_num_filtered;
1065 ++m_num_have_filtered;
1066 }
1067 ++m_num_have;
1068 p.set_have();
1069 if (priority == -1) return;
1070 if (m_dirty) return;
1071 remove(priority, info_index);
1072 TORRENT_ASSERT(p.priority(this) == -1);
1073 }
1074
1075 bool piece_picker::set_piece_priority(int index, int new_piece_priority)
1076 {
1077 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1078 TORRENT_ASSERT(new_piece_priority >= 0);
1079 TORRENT_ASSERT(new_piece_priority <= 7);
1080 TORRENT_ASSERT(index >= 0);
1081 TORRENT_ASSERT(index < (int)m_piece_map.size());
1082
1083 piece_pos& p = m_piece_map[index];
1084
1085 // if the priority isn't changed, don't do anything
1086 if (new_piece_priority == int(p.piece_priority)) return false;
1087
1088 int prev_priority = p.priority(this);
1089 TORRENT_ASSERT(m_dirty | prev_priority < int(m_priority_boundries.size()));
1090
1091 bool ret = false;
1092 if (new_piece_priority == piece_pos::filter_priority
1093 && p.piece_priority != piece_pos::filter_priority)
1094 {
1095 // the piece just got filtered
1096 if (p.have()) ++m_num_have_filtered;
1097 else ++m_num_filtered;
1098 ret = true;
1099 }
1100 else if (new_piece_priority != piece_pos::filter_priority
1101 && p.piece_priority == piece_pos::filter_priority)
1102 {
1103 // the piece just got unfiltered
1104 if (p.have()) --m_num_have_filtered;
1105 else --m_num_filtered;
1106 ret = true;
1107 }
1108 TORRENT_ASSERT(m_num_filtered >= 0);
1109 TORRENT_ASSERT(m_num_have_filtered >= 0);
1110
1111 p.piece_priority = new_piece_priority;
1112 int new_priority = p.priority(this);
1113
1114 if (prev_priority == new_priority) return ret;
1115
1116 if (m_dirty) return ret;
1117 if (prev_priority == -1)
1118 {
1119 add(index);
1120 }
1121 else
1122 {
1123 update(prev_priority, p.index);
1124 }
1125 return ret;
1126 }
1127
1128 int piece_picker::piece_priority(int index) const
1129 {
1130 TORRENT_ASSERT(index >= 0);
1131 TORRENT_ASSERT(index < (int)m_piece_map.size());
1132
1133 return m_piece_map[index].piece_priority;
1134 }
1135
1136 void piece_picker::piece_priorities(std::vector<int>& pieces) const
1137 {
1138 pieces.resize(m_piece_map.size());
1139 std::vector<int>::iterator j = pieces.begin();
1140 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin(),
1141 end(m_piece_map.end()); i != end; ++i, ++j)
1142 {
1143 *j = i->piece_priority;
1144 }
1145 }
1146
1147 // ============ start deprecation ==============
1148
1149 void piece_picker::filtered_pieces(std::vector<bool>& mask) const
1150 {
1151 mask.resize(m_piece_map.size());
1152 std::vector<bool>::iterator j = mask.begin();
1153 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin(),
1154 end(m_piece_map.end()); i != end; ++i, ++j)
1155 {
1156 *j = i->filtered();
1157 }
1158 }
1159
1160 // ============ end deprecation ==============
1161
1162 // pieces describes which pieces the peer we're requesting from
1163 // has.
1164 // interesting_blocks is an out parameter, and will be filled
1165 // with (up to) num_blocks of interesting blocks that the peer has.
1166 // prefer_whole_pieces can be set if this peer should download
1167 // whole pieces rather than trying to download blocks from the
1168 // same piece as other peers.
1169 // the void* is the pointer to the policy::peer of the peer we're
1170 // picking pieces from. This is used when downloading whole pieces,
1171 // to only pick from the same piece the same peer is downloading
1172 // from. state is supposed to be set to fast if the peer is downloading
1173 // relatively fast, by some notion. Slow peers will prefer not
1174 // to pick blocks from the same pieces as fast peers, and vice
1175 // versa. Downloading pieces are marked as being fast, medium
1176 // or slow once they're started.
1177 void piece_picker::pick_pieces(bitfield const& pieces
1178 , std::vector<piece_block>& interesting_blocks
1179 , int num_blocks, int prefer_whole_pieces
1180 , void* peer, piece_state_t speed, bool rarest_first
1181 , bool on_parole, std::vector<int> const& suggested_pieces) const
1182 {
1183 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1184 TORRENT_ASSERT(num_blocks > 0);
1185 TORRENT_ASSERT(pieces.size() == m_piece_map.size());
1186
1187 TORRENT_ASSERT(!m_priority_boundries.empty()
1188 || m_sequential_download >= 0
1189 || m_dirty);
1190
1191 // this will be filled with blocks that we should not request
1192 // unless we can't find num_blocks among the other ones.
1193 // blocks that belong to pieces with a mismatching speed
1194 // category for instance, or if we prefer whole pieces,
1195 // blocks belonging to a piece that others have
1196 // downloaded to
1197 std::vector<piece_block> backup_blocks;
1198 const std::vector<int> empty_vector;
1199
1200 // When prefer_whole_pieces is set (usually set when downloading from
1201 // fast peers) the partial pieces will not be prioritized, but actually
1202 // ignored as long as possible. All blocks found in downloading
1203 // pieces are regarded as backup blocks
1204
1205 num_blocks = add_blocks_downloading(pieces
1206 , interesting_blocks, backup_blocks, num_blocks
1207 , prefer_whole_pieces, peer, speed, on_parole);
1208
1209 if (num_blocks <= 0) return;
1210
1211 if (!suggested_pieces.empty())
1212 {
1213 num_blocks = add_blocks(suggested_pieces, pieces
1214 , interesting_blocks, num_blocks
1215 , prefer_whole_pieces, peer, empty_vector);
1216 if (num_blocks == 0) return;
1217 }
1218
1219 if (m_sequential_download >= 0)
1220 {
1221 for (int i = m_sequential_download;
1222 i < int(m_piece_map.size()) && num_blocks > 0; ++i)
1223 {
1224 if (!can_pick(i, pieces)) continue;
1225 int num_blocks_in_piece = blocks_in_piece(i);
1226 if (prefer_whole_pieces == 0 && num_blocks_in_piece > num_blocks)
1227 num_blocks_in_piece = num_blocks;
1228 for (int j = 0; j < num_blocks_in_piece; ++j)
1229 {
1230 interesting_blocks.push_back(piece_block(i, j));
1231 --num_blocks;
1232 }
1233 }
1234 }
1235 else if (rarest_first)
1236 {
1237 if (m_dirty) update_pieces();
1238 num_blocks = add_blocks(m_pieces, pieces
1239 , interesting_blocks, num_blocks
1240 , prefer_whole_pieces, peer, suggested_pieces);
1241 TORRENT_ASSERT(num_blocks >= 0);
1242 }
1243 else
1244 {
1245 // we're not using rarest first (only for the first
1246 // bucket, since that's where the currently downloading
1247 // pieces are)
1248 int start_piece = rand() % m_piece_map.size();
1249
1250 // if we have suggested pieces, try to find one of those instead
1251 for (std::vector<int>::const_iterator i = suggested_pieces.begin()
1252 , end(suggested_pieces.end()); i != end; ++i)
1253 {
1254 if (!can_pick(*i, pieces)) continue;
1255 start_piece = *i;
1256 break;
1257 }
1258 int piece = start_piece;
1259 while (num_blocks > 0)
1260 {
1261 while (!can_pick(piece, pieces))
1262 {
1263 ++piece;
1264 if (piece == int(m_piece_map.size())) piece = 0;
1265 // could not find any more pieces
1266 if (piece == start_piece) return;
1267 }
1268
1269 int start, end;
1270 boost::tie(start, end) = expand_piece(piece, prefer_whole_pieces, pieces);
1271 for (int k = start; k < end; ++k)
1272 {
1273 TORRENT_ASSERT(m_piece_map[piece].downloading == false);
1274 TORRENT_ASSERT(m_piece_map[k].priority(this) >= 0);
1275 int num_blocks_in_piece = blocks_in_piece(k);
1276 if (prefer_whole_pieces == 0 && num_blocks_in_piece > num_blocks)
1277 num_blocks_in_piece = num_blocks;
1278 for (int j = 0; j < num_blocks_in_piece; ++j)
1279 {
1280 interesting_blocks.push_back(piece_block(k, j));
1281 --num_blocks;
1282 }
1283 }
1284 piece = end;
1285 if (piece == int(m_piece_map.size())) piece = 0;
1286 // could not find any more pieces
1287 if (piece == start_piece) return;
1288 }
1289
1290 }
1291
1292 if (num_blocks <= 0) return;
1293
1294 if (!backup_blocks.empty())
1295 interesting_blocks.insert(interesting_blocks.end()
1296 , backup_blocks.begin(), backup_blocks.end());
1297 }
1298
1299 bool piece_picker::can_pick(int piece, bitfield const& bitmask) const
1300 {
1301 TORRENT_ASSERT(piece >= 0 && piece < int(m_piece_map.size()));
1302 return bitmask[piece]
1303 && !m_piece_map[piece].have()
1304 && !m_piece_map[piece].downloading
1305 && !m_piece_map[piece].filtered();
1306 }
1307
1308 void piece_picker::clear_peer(void* peer)
1309 {
1310 for (std::vector<block_info>::iterator i = m_block_info.begin()
1311 , end(m_block_info.end()); i != end; ++i)
1312 if (i->peer == peer) i->peer = 0;
1313 }
1314
1315 namespace
1316 {
1317 // the first bool is true if this is the only peer that has requested and downloaded
1318 // blocks from this piece.
1319 // the second bool is true if this is the only active peer that is requesting
1320 // and downloading blocks from this piece. Active means having a connection.
1321 boost::tuple<bool, bool> requested_from(piece_picker::downloading_piece const& p
1322 , int num_blocks_in_piece, void* peer)
1323 {
1324 bool exclusive = true;
1325 bool exclusive_active = true;
1326 for (int j = 0; j < num_blocks_in_piece; ++j)
1327 {
1328 piece_picker::block_info const& info = p.info[j];
1329 if (info.state != piece_picker::block_info::state_none
1330 && info.peer != peer)
1331 {
1332 exclusive = false;
1333 if (info.state == piece_picker::block_info::state_requested
1334 && info.peer != 0)
1335 {
1336 exclusive_active = false;
1337 return boost::make_tuple(exclusive, exclusive_active);
1338 }
1339 }
1340 }
1341 return boost::make_tuple(exclusive, exclusive_active);
1342 }
1343 }
1344
1345 int piece_picker::add_blocks(std::vector<int> const& piece_list
1346 , bitfield const& pieces
1347 , std::vector<piece_block>& interesting_blocks
1348 , int num_blocks, int prefer_whole_pieces
1349 , void* peer, std::vector<int> const& ignore) const
1350 {
1351 for (std::vector<int>::const_iterator i = piece_list.begin();
1352 i != piece_list.end(); ++i)
1353 {
1354 TORRENT_ASSERT(*i >= 0);
1355 TORRENT_ASSERT(*i < (int)m_piece_map.size());
1356
1357 // if the peer doesn't have the piece
1358 // or if it's set to 0 priority
1359 // skip it
1360 if (!can_pick(*i, pieces)) continue;
1361
1362 // ignore pieces found in the ignore list
1363 if (std::find(ignore.begin(), ignore.end(), *i) != ignore.end()) continue;
1364
1365 TORRENT_ASSERT(m_piece_map[*i].priority(this) >= 0);
1366 TORRENT_ASSERT(m_piece_map[*i].downloading == 0);
1367
1368 int num_blocks_in_piece = blocks_in_piece(*i);
1369
1370 // pick a new piece
1371 if (prefer_whole_pieces == 0)
1372 {
1373 if (num_blocks_in_piece > num_blocks)
1374 num_blocks_in_piece = num_blocks;
1375 for (int j = 0; j < num_blocks_in_piece; ++j)
1376 interesting_blocks.push_back(piece_block(*i, j));
1377 num_blocks -= num_blocks_in_piece;
1378 }
1379 else
1380 {
1381 int start, end;
1382 boost::tie(start, end) = expand_piece(*i, prefer_whole_pieces, pieces);
1383 for (int k = start; k < end; ++k)
1384 {
1385 TORRENT_ASSERT(m_piece_map[k].priority(this) > 0);
1386 num_blocks_in_piece = blocks_in_piece(k);
1387 for (int j = 0; j < num_blocks_in_piece; ++j)
1388 {
1389 interesting_blocks.push_back(piece_block(k, j));
1390 --num_blocks;
1391 }
1392 }
1393 }
1394 if (num_blocks <= 0)
1395 {
1396 #ifndef NDEBUG
1397 verify_pick(interesting_blocks, pieces);
1398 #endif
1399 return 0;
1400 }
1401 }
1402 #ifndef NDEBUG
1403 verify_pick(interesting_blocks, pieces);
1404 #endif
1405 return num_blocks;
1406 }
1407
1408 int piece_picker::add_blocks_downloading(bitfield const& pieces
1409 , std::vector<piece_block>& interesting_blocks
1410 , std::vector<piece_block>& backup_blocks
1411 , int num_blocks, int prefer_whole_pieces
1412 , void* peer, piece_state_t speed, bool on_parole) const
1413 {
1414 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1415 , end(m_downloads.end()); i != end; ++i)
1416 {
1417 if (!pieces[i->index]) continue;
1418
1419 int num_blocks_in_piece = blocks_in_piece(i->index);
1420
1421 // is true if all the other pieces that are currently
1422 // requested from this piece are from the same
1423 // peer as 'peer'.
1424 bool exclusive;
1425 bool exclusive_active;
1426 boost::tie(exclusive, exclusive_active)
1427 = requested_from(*i, num_blocks_in_piece, peer);
1428
1429 // peers on parole are only allowed to pick blocks from
1430 // pieces that only they have downloaded/requested from
1431 if (on_parole && !exclusive) continue;
1432
1433 if (prefer_whole_pieces > 0 && !exclusive_active) continue;
1434
1435 // don't pick too many back-up blocks
1436 if (i->state != none
1437 && i->state != speed
1438 && !exclusive_active
1439 && int(backup_blocks.size()) >= num_blocks)
1440 continue;
1441
1442 for (int j = 0; j < num_blocks_in_piece; ++j)
1443 {
1444 // ignore completed blocks and already requested blocks
1445 block_info const& info = i->info[j];
1446 if (info.state != block_info::state_none)
1447 continue;
1448
1449 TORRENT_ASSERT(i->info[j].state == block_info::state_none);
1450
1451 // if the piece is fast and the peer is slow, or vice versa,
1452 // add the block as a backup.
1453 // override this behavior if all the other blocks
1454 // have been requested from the same peer or
1455 // if the state of the piece is none (the
1456 // piece will in that case change state).
1457 if (i->state != none && i->state != speed
1458 && !exclusive_active)
1459 {
1460 backup_blocks.push_back(piece_block(i->index, j));
1461 continue;
1462 }
1463
1464 // this block is interesting (we don't have it
1465 // yet).
1466 interesting_blocks.push_back(piece_block(i->index, j));
1467 // we have found a block that's free to download
1468 num_blocks--;
1469 // if we prefer whole pieces, continue picking from this
1470 // piece even though we have num_blocks
1471 if (prefer_whole_pieces > 0) continue;
1472 TORRENT_ASSERT(num_blocks >= 0);
1473 if (num_blocks <= 0) break;
1474 }
1475 if (num_blocks <= 0) break;
1476 }
1477
1478 TORRENT_ASSERT(num_blocks >= 0 || prefer_whole_pieces > 0);
1479
1480 #ifndef NDEBUG
1481 verify_pick(interesting_blocks, pieces);
1482 verify_pick(backup_blocks, pieces);
1483 #endif
1484
1485 if (num_blocks <= 0) return 0;
1486 if (on_parole) return num_blocks;
1487
1488 int to_copy;
1489 if (prefer_whole_pieces == 0)
1490 to_copy = (std::min)(int(backup_blocks.size()), num_blocks);
1491 else
1492 to_copy = int(backup_blocks.size());
1493
1494 interesting_blocks.insert(interesting_blocks.end()
1495 , backup_blocks.begin(), backup_blocks.begin() + to_copy);
1496 num_blocks -= to_copy;
1497 backup_blocks.clear();
1498
1499 if (num_blocks <= 0) return 0;
1500
1501 if (prefer_whole_pieces > 0)
1502 {
1503 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1504 , end(m_downloads.end()); i != end; ++i)
1505 {
1506 if (!pieces[i->index]) continue;
1507 int num_blocks_in_piece = blocks_in_piece(i->index);
1508 bool exclusive;
1509 bool exclusive_active;
1510 boost::tie(exclusive, exclusive_active)
1511 = requested_from(*i, num_blocks_in_piece, peer);
1512
1513 if (exclusive_active) continue;
1514
1515 for (int j = 0; j < num_blocks_in_piece; ++j)
1516 {
1517 block_info const& info = i->info[j];
1518 if (info.state != block_info::state_none) continue;
1519 backup_blocks.push_back(piece_block(i->index, j));
1520 }
1521 }
1522 }
1523
1524 if (int(backup_blocks.size()) >= num_blocks) return num_blocks;
1525
1526
1527 #ifndef NDEBUG
1528 // make sure that we at this point has added requests to all unrequested blocks
1529 // in all downloading pieces
1530
1531 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1532 , end(m_downloads.end()); i != end; ++i)
1533 {
1534 if (!pieces[i->index]) continue;
1535
1536 int num_blocks_in_piece = blocks_in_piece(i->index);
1537 for (int j = 0; j < num_blocks_in_piece; ++j)
1538 {
1539 block_info const& info = i->info[j];
1540 if (info.state != block_info::state_none) continue;
1541 std::vector<piece_block>::iterator k = std::find(
1542 interesting_blocks.begin(), interesting_blocks.end()
1543 , piece_block(i->index, j));
1544 if (k != interesting_blocks.end()) continue;
1545
1546 k = std::find(backup_blocks.begin()
1547 , backup_blocks.end(), piece_block(i->index, j));
1548 if (k != backup_blocks.end()) continue;
1549
1550 std::cerr << "interesting blocks:" << std::endl;
1551 for (k = interesting_blocks.begin(); k != interesting_blocks.end(); ++k)
1552 std::cerr << "(" << k->piece_index << ", " << k->block_index << ") ";
1553 std::cerr << std::endl;
1554 std::cerr << "backup blocks:" << std::endl;
1555 for (k = backup_blocks.begin(); k != backup_blocks.end(); ++k)
1556 std::cerr << "(" << k->piece_index << ", " << k->block_index << ") ";
1557 std::cerr << std::endl;
1558 std::cerr << "num_blocks: " << num_blocks << std::endl;
1559
1560 for (std::vector<downloading_piece>::const_iterator l = m_downloads.begin()
1561 , end(m_downloads.end()); l != end; ++l)
1562 {
1563 std::cerr << l->index << " : ";
1564 int num_blocks_in_piece = blocks_in_piece(l->index);
1565 for (int m = 0; m < num_blocks_in_piece; ++m)
1566 std::cerr << l->info[m].state;
1567 std::cerr << std::endl;
1568 }
1569
1570 TORRENT_ASSERT(false);
1571 }
1572 }
1573 #endif
1574
1575 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1576 , end(m_downloads.end()); i != end; ++i)
1577 {
1578 if (!pieces[i->index]) continue;
1579
1580 int num_blocks_in_piece = blocks_in_piece(i->index);
1581
1582 // fill in with blocks requested from other peers
1583 // as backups
1584 for (int j = 0; j < num_blocks_in_piece; ++j)
1585 {
1586 block_info const& info = i->info[j];
1587 if (info.state != block_info::state_requested
1588 || info.peer == peer)
1589 continue;
1590 backup_blocks.push_back(piece_block(i->index, j));
1591 }
1592 }
1593 #ifndef NDEBUG
1594 verify_pick(backup_blocks, pieces);
1595 #endif
1596 return num_blocks;
1597 }
1598
1599 std::pair<int, int> piece_picker::expand_piece(int piece, int whole_pieces
1600 , bitfield const& have) const
1601 {
1602 if (whole_pieces == 0) return std::make_pair(piece, piece + 1);
1603
1604 int start = piece - 1;
1605 int lower_limit = piece - whole_pieces;
1606 if (lower_limit < -1) lower_limit = -1;
1607 while (start > lower_limit
1608 && can_pick(start, have))
1609 --start;
1610 ++start;
1611 TORRENT_ASSERT(start >= 0);
1612 int end = piece + 1;
1613 int upper_limit = start + whole_pieces;
1614 if (upper_limit > int(m_piece_map.size())) upper_limit = int(m_piece_map.size());
1615 while (end < upper_limit
1616 && can_pick(end, have))
1617 ++end;
1618 return std::make_pair(start, end);
1619 }
1620
1621 bool piece_picker::is_piece_finished(int index) const
1622 {
1623 TORRENT_ASSERT(index < (int)m_piece_map.size());
1624 TORRENT_ASSERT(index >= 0);
1625
1626 if (m_piece_map[index].downloading == 0)
1627 {
1628 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1629 , has_index(index)) == m_downloads.end());
1630 return false;
1631 }
1632 std::vector<downloading_piece>::const_iterator i
1633 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index));
1634 TORRENT_ASSERT(i != m_downloads.end());
1635 TORRENT_ASSERT((int)i->finished <= m_blocks_per_piece);
1636 int max_blocks = blocks_in_piece(index);
1637 if ((int)i->finished < max_blocks) return false;
1638
1639 #ifndef NDEBUG
1640 for (int k = 0; k < max_blocks; ++k)
1641 {
1642 TORRENT_ASSERT(i->info[k].state == block_info::state_finished);
1643 }
1644 #endif
1645
1646 TORRENT_ASSERT((int)i->finished == max_blocks);
1647 return true;
1648 }
1649
1650 bool piece_picker::is_requested(piece_block block) const
1651 {
1652 TORRENT_ASSERT(block.piece_index >= 0);
1653 TORRENT_ASSERT(block.block_index >= 0);
1654 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1655
1656 if (m_piece_map[block.piece_index].downloading == 0) return false;
1657 std::vector<downloading_piece>::const_iterator i
1658 = std::find_if(
1659 m_downloads.begin()
1660 , m_downloads.end()
1661 , has_index(block.piece_index));
1662
1663 TORRENT_ASSERT(i != m_downloads.end());
1664 return i->info[block.block_index].state == block_info::state_requested;
1665 }
1666
1667 bool piece_picker::is_downloaded(piece_block block) const
1668 {
1669 TORRENT_ASSERT(block.piece_index >= 0);
1670 TORRENT_ASSERT(block.block_index >= 0);
1671 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1672
1673 if (m_piece_map[block.piece_index].index == piece_pos::we_have_index) return true;
1674 if (m_piece_map[block.piece_index].downloading == 0) return false;
1675 std::vector<downloading_piece>::const_iterator i
1676 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1677 TORRENT_ASSERT(i != m_downloads.end());
1678 return i->info[block.block_index].state == block_info::state_finished
1679 || i->info[block.block_index].state == block_info::state_writing;
1680 }
1681
1682 bool piece_picker::is_finished(piece_block block) const
1683 {
1684 TORRENT_ASSERT(block.piece_index >= 0);
1685 TORRENT_ASSERT(block.block_index >= 0);
1686 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1687
1688 if (m_piece_map[block.piece_index].index == piece_pos::we_have_index) return true;
1689 if (m_piece_map[block.piece_index].downloading == 0) return false;
1690 std::vector<downloading_piece>::const_iterator i
1691 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1692 TORRENT_ASSERT(i != m_downloads.end());
1693 return i->info[block.block_index].state == block_info::state_finished;
1694 }
1695
1696 bool piece_picker::mark_as_downloading(piece_block block
1697 , void* peer, piece_state_t state)
1698 {
1699 TORRENT_ASSERT(block.piece_index >= 0);
1700 TORRENT_ASSERT(block.block_index >= 0);
1701 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1702 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1703 TORRENT_ASSERT(!m_piece_map[block.piece_index].have());
1704
1705 piece_pos& p = m_piece_map[block.piece_index];
1706 if (p.downloading == 0)
1707 {
1708 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1709 int prio = p.priority(this);
1710 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
1711 || m_sequential_download >= 0
1712 || m_dirty);
1713 TORRENT_ASSERT(prio > 0);
1714 p.downloading = 1;
1715 if (prio >= 0 && m_sequential_download == -1 && !m_dirty) update(prio, p.index);
1716
1717 downloading_piece& dp = add_download_piece();
1718 dp.state = state;
1719 dp.index = block.piece_index;
1720 block_info& info = dp.info[block.block_index];
1721 info.state = block_info::state_requested;
1722 info.peer = peer;
1723 info.num_peers = 1;
1724 ++dp.requested;
1725 }
1726 else
1727 {
1728 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1729 std::vector<downloading_piece>::iterator i
1730 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1731 TORRENT_ASSERT(i != m_downloads.end());
1732 block_info& info = i->info[block.block_index];
1733 if (info.state == block_info::state_writing
1734 || info.state == block_info::state_finished)
1735 return false;
1736 TORRENT_ASSERT(info.state == block_info::state_none
1737 || (info.state == block_info::state_requested
1738 && (info.num_peers > 0)));
1739 info.peer = peer;
1740 if (info.state != block_info::state_requested)
1741 {
1742 info.state = block_info::state_requested;
1743 ++i->requested;
1744 }
1745 ++info.num_peers;
1746 if (i->state == none) i->state = state;
1747 }
1748 return true;
1749 }
1750
1751 int piece_picker::num_peers(piece_block block) const
1752 {
1753 TORRENT_ASSERT(block.piece_index >= 0);
1754 TORRENT_ASSERT(block.block_index >= 0);
1755 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1756 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1757
1758 piece_pos const& p = m_piece_map[block.piece_index];
1759 if (!p.downloading) return 0;
1760
1761 std::vector<downloading_piece>::const_iterator i
1762 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1763 TORRENT_ASSERT(i != m_downloads.end());
1764
1765 block_info const& info = i->info[block.block_index];
1766 return info.num_peers;
1767 }
1768
1769 void piece_picker::get_availability(std::vector<int>& avail) const
1770 {
1771 TORRENT_ASSERT(m_seeds >= 0);
1772 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1773
1774 avail.resize(m_piece_map.size());
1775 std::vector<int>::iterator j = avail.begin();
1776 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
1777 , end(m_piece_map.end()); i != end; ++i, ++j)
1778 *j = i->peer_count + m_seeds;
1779 }
1780
1781 void piece_picker::mark_as_writing(piece_block block, void* peer)
1782 {
1783 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1784
1785 TORRENT_ASSERT(block.piece_index >= 0);
1786 TORRENT_ASSERT(block.block_index >= 0);
1787 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1788 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1789
1790 TORRENT_ASSERT(m_piece_map[block.piece_index].downloading);
1791
1792 std::vector<downloading_piece>::iterator i
1793 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1794 TORRENT_ASSERT(i != m_downloads.end());
1795 block_info& info = i->info[block.block_index];
1796
1797 info.peer = peer;
1798 TORRENT_ASSERT(info.state == block_info::state_requested);
1799 if (info.state == block_info::state_requested) --i->requested;
1800 TORRENT_ASSERT(i->requested >= 0);
1801 TORRENT_ASSERT(info.state != block_info::state_writing);
1802 ++i->writing;
1803 info.state = block_info::state_writing;
1804 TORRENT_ASSERT(info.num_peers > 0);
1805 info.num_peers = 0;
1806
1807 if (i->requested == 0)
1808 {
1809 // there are no blocks requested in this piece.
1810 // remove the fast/slow state from it
1811 i->state = none;
1812 }
1813 sort_piece(i);
1814 }
1815
1816 void piece_picker::write_failed(piece_block block)
1817 {
1818 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1819
1820 std::vector<downloading_piece>::iterator i
1821 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1822 TORRENT_ASSERT(i != m_downloads.end());
1823 block_info& info = i->info[block.block_index];
1824 TORRENT_ASSERT(info.state == block_info::state_writing);
1825
1826 --i->writing;
1827 if (info.num_peers > 0)
1828 {
1829 // there are other peers on this block
1830 // turn it back into requested
1831 ++i->requested;
1832 info.state = block_info::state_requested;
1833 }
1834 else
1835 {
1836 info.state = block_info::state_none;
1837 }
1838 info.peer = 0;
1839 }
1840
1841 void piece_picker::mark_as_finished(piece_block block, void* peer)
1842 {
1843 TORRENT_ASSERT(block.piece_index >= 0);
1844 TORRENT_ASSERT(block.block_index >= 0);
1845 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1846 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1847
1848 piece_pos& p = m_piece_map[block.piece_index];
1849
1850 if (p.downloading == 0)
1851 {
1852 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1853
1854 TORRENT_ASSERT(peer == 0);
1855 int prio = p.priority(this);
1856 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
1857 || m_dirty);
1858 p.downloading = 1;
1859 if (prio >= 0 && !m_dirty) update(prio, p.index);
1860
1861 downloading_piece& dp = add_download_piece();
1862 dp.state = none;
1863 dp.index = block.piece_index;
1864 block_info& info = dp.info[block.block_index];
1865 info.peer = peer;
1866 TORRENT_ASSERT(info.state == block_info::state_none);
1867 TORRENT_ASSERT(info.num_peers == 0);
1868 if (info.state != block_info::state_finished)
1869 {
1870 ++dp.finished;
1871 sort_piece(m_downloads.end() - 1);
1872 }
1873 info.state = block_info::state_finished;
1874 }
1875 else
1876 {
1877 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1878
1879 std::vector<downloading_piece>::iterator i
1880 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1881 TORRENT_ASSERT(i != m_downloads.end());
1882 block_info& info = i->info[block.block_index];
1883 TORRENT_ASSERT(info.num_peers == 0);
1884 info.peer = peer;
1885 TORRENT_ASSERT(info.state == block_info::state_writing
1886 || peer == 0);
1887 TORRENT_ASSERT(i->writing >= 0);
1888 ++i->finished;
1889 if (info.state == block_info::state_writing)
1890 {
1891 --i->writing;
1892 info.state = block_info::state_finished;
1893 }
1894 else
1895 {
1896 info.state = block_info::state_finished;
1897 sort_piece(i);
1898 }
1899 }
1900 }
1901
1902 void piece_picker::get_downloaders(std::vector<void*>& d, int index) const
1903 {
1904 TORRENT_ASSERT(index >= 0 && index <= (int)m_piece_map.size());
1905 std::vector<downloading_piece>::const_iterator i
1906 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index));
1907 TORRENT_ASSERT(i != m_downloads.end());
1908
1909 d.clear();
1910 for (int j = 0; j < blocks_in_piece(index); ++j)
1911 {
1912 d.push_back(i->info[j].peer);
1913 }
1914 }
1915
1916 void* piece_picker::get_downloader(piece_block block) const
1917 {
1918 std::vector<downloading_piece>::const_iterator i = std::find_if(
1919 m_downloads.begin()
1920 , m_downloads.end()
1921 , has_index(block.piece_index));
1922
1923 if (i == m_downloads.end()) return 0;
1924
1925 TORRENT_ASSERT(block.block_index >= 0);
1926
1927 if (i->info[block.block_index].state == block_info::state_none)
1928 return 0;
1929
1930 return i->info[block.block_index].peer;
1931 }
1932
1933 // this is called when a request is rejected or when
1934 // a peer disconnects. The piece might be in any state
1935 void piece_picker::abort_download(piece_block block)
1936 {
1937 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1938
1939 TORRENT_ASSERT(block.piece_index >= 0);
1940 TORRENT_ASSERT(block.block_index >= 0);
1941 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1942 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1943
1944 if (m_piece_map[block.piece_index].downloading == 0)
1945 {
1946 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1947 , has_index(block.piece_index)) == m_downloads.end());
1948 return;
1949 }
1950
1951 std::vector<downloading_piece>::iterator i = std::find_if(m_downloads.begin()
1952 , m_downloads.end(), has_index(block.piece_index));
1953 TORRENT_ASSERT(i != m_downloads.end());
1954
1955 block_info& info = i->info[block.block_index];
1956
1957 if (i->info[block.block_index].state != block_info::state_requested)
1958 return;
1959
1960 if (info.num_peers > 0) --info.num_peers;
1961
1962 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1963
1964 // if there are other peers, leave the block requested
1965 if (info.num_peers > 0) return;
1966
1967 // clear the downloader of this block
1968 info.peer = 0;
1969
1970 // clear this block as being downloaded
1971 info.state = block_info::state_none;
1972 --i->requested;
1973
1974 // if there are no other blocks in this piece
1975 // that's being downloaded, remove it from the list
1976 if (i->requested + i->finished + i->writing == 0)
1977 {
1978 erase_download_piece(i);
1979 piece_pos& p = m_piece_map[block.piece_index];
1980 int prev_prio = p.priority(this);
1981 TORRENT_ASSERT(prev_prio < int(m_priority_boundries.size())
1982 || m_dirty);
1983 p.downloading = 0;
1984 if (m_sequential_download == -1 && !m_dirty)
1985 {
1986 int prio = p.priority(this);
1987 if (prev_prio == -1 && prio >= 0) add(block.piece_index);
1988 else if (prev_prio >= 0) update(prev_prio, p.index);
1989 }
1990
1991 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1992 , has_index(block.piece_index)) == m_downloads.end());
1993 }
1994 else if (i->requested == 0)
1995 {
1996 // there are no blocks requested in this piece.
1997 // remove the fast/slow state from it
1998 i->state = none;
1999 }
2000 }
2001
2002 int piece_picker::unverified_blocks() const
2003 {
2004 int counter = 0;
2005 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin();
2006 i != m_downloads.end(); ++i)
2007 {
2008 counter += (int)i->finished;
2009 }
2010 return counter;
2011 }
2012
2013 }
2014
A bittorrent daemon and client