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