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