15 #ifndef STXXL_SORT_HEADER
16 #define STXXL_SORT_HEADER
21 #include <stxxl/bits/mng/mng.h>
22 #include <stxxl/bits/common/rand.h>
23 #include <stxxl/bits/mng/adaptor.h>
24 #include <stxxl/bits/common/simple_vector.h>
25 #include <stxxl/bits/common/switch.h>
27 #include <stxxl/bits/mng/block_alloc_interleaved.h>
28 #include <stxxl/bits/algo/intksort.h>
29 #include <stxxl/bits/algo/adaptor.h>
30 #include <stxxl/bits/algo/async_schedule.h>
31 #include <stxxl/bits/mng/block_prefetcher.h>
32 #include <stxxl/bits/mng/buf_writer.h>
33 #include <stxxl/bits/algo/run_cursor.h>
34 #include <stxxl/bits/algo/losertree.h>
35 #include <stxxl/bits/algo/inmemsort.h>
36 #include <stxxl/bits/parallel.h>
43 __STXXL_BEGIN_NAMESPACE
53 template <
typename BIDTp_,
typename ValTp_>
56 typedef BIDTp_ bid_type;
57 typedef ValTp_ value_type;
68 template <
typename BIDTp_,
typename ValTp_,
typename ValueCmp_>
69 struct trigger_entry_cmp :
public std::binary_function<trigger_entry<BIDTp_, ValTp_>, trigger_entry<BIDTp_, ValTp_>, bool>
71 typedef trigger_entry<BIDTp_, ValTp_> trigger_entry_type;
73 trigger_entry_cmp(ValueCmp_ c) : cmp(c) { }
74 trigger_entry_cmp(
const trigger_entry_cmp & a) : cmp(a.cmp) { }
75 bool operator () (
const trigger_entry_type & a,
const trigger_entry_type & b)
const
77 return cmp(a.value, b.value);
81 template <
typename block_type,
82 typename prefetcher_type,
84 struct run_cursor2_cmp
86 typedef run_cursor2<block_type, prefetcher_type> cursor_type;
89 run_cursor2_cmp(value_cmp c) : cmp(c) { }
90 run_cursor2_cmp(
const run_cursor2_cmp & a) : cmp(a.cmp) { }
91 inline bool operator () (
const cursor_type & a,
const cursor_type & b)
93 if (UNLIKELY(b.empty()))
96 if (UNLIKELY(a.empty()))
100 return (cmp(a.current(), b.current()));
104 template <
typename block_type,
typename b
id_type>
105 struct read_next_after_write_completed
112 * req = block->read(bid);
120 typename input_bid_iterator,
124 input_bid_iterator it,
130 typedef typename block_type::value_type type;
131 typedef typename block_type::bid_type bid_type;
132 STXXL_VERBOSE1(
"stxxl::create_runs nruns=" << nruns <<
" m=" << _m);
134 int_type m2 = _m / 2;
136 block_type * Blocks1 =
new block_type[m2];
137 block_type * Blocks2 =
new block_type[m2];
138 bid_type * bids1 =
new bid_type[m2];
139 bid_type * bids2 =
new bid_type[m2];
143 read_next_after_write_completed<block_type, bid_type> * next_run_reads =
144 new read_next_after_write_completed<block_type, bid_type>[m2];
146 disk_queues::get_instance()->set_priority_op(disk_queue::WRITE);
149 int_type run_size = 0, next_run_size = 0;
153 run_size = runs[0]->size();
154 assert(run_size == m2);
156 for (i = 0; i < run_size; ++i)
158 STXXL_VERBOSE1(
"stxxl::create_runs posting read " <<
long(Blocks1[i].elem));
160 read_reqs1[i] = Blocks1[i].read(bids1[i]);
163 run_size = runs[1]->size();
165 for (i = 0; i < run_size; ++i)
167 STXXL_VERBOSE1(
"stxxl::create_runs posting read " <<
long(Blocks2[i].elem));
169 read_reqs2[i] = Blocks2[i].read(bids2[i]);
172 for (int_type k = 0; k < nruns - 1; ++k)
174 run_type * run = runs[k];
175 run_size = run->size();
176 assert(run_size == m2);
177 next_run_size = runs[k + 1]->size();
178 assert((next_run_size == m2) || (next_run_size <= m2 && k == nruns - 2));
180 STXXL_VERBOSE1(
"stxxl::create_runs start waiting read_reqs1");
182 STXXL_VERBOSE1(
"stxxl::create_runs finish waiting read_reqs1");
183 for (i = 0; i < run_size; ++i)
186 if (block_type::has_filler)
188 ArrayOfSequencesIterator<
189 block_type,
typename block_type::value_type, block_type::size
191 ArrayOfSequencesIterator<
192 block_type,
typename block_type::value_type, block_type::size
193 >(Blocks1, run_size * block_type::size),
196 std::sort(Blocks1[0].elem, Blocks1[run_size].elem, cmp);
199 STXXL_VERBOSE1(
"stxxl::create_runs start waiting write_reqs");
202 STXXL_VERBOSE1(
"stxxl::create_runs finish waiting write_reqs");
204 int_type runplus2size = (k < nruns - 2) ? runs[k + 2]->size() : 0;
205 for (i = 0; i < m2; ++i)
207 STXXL_VERBOSE1(
"stxxl::create_runs posting write " <<
long(Blocks1[i].elem));
208 (*run)[i].value = Blocks1[i][0];
209 if (i >= runplus2size) {
210 write_reqs[i] = Blocks1[i].write((*run)[i].bid);
214 next_run_reads[i].block = Blocks1 + i;
215 next_run_reads[i].req = read_reqs1 + i;
216 bids1[i] = next_run_reads[i].bid = *(it++);
217 write_reqs[i] = Blocks1[i].write((*run)[i].bid, next_run_reads[i]);
220 std::swap(Blocks1, Blocks2);
221 std::swap(bids1, bids2);
222 std::swap(read_reqs1, read_reqs2);
225 run_type * run = runs[nruns - 1];
226 run_size = run->size();
227 STXXL_VERBOSE1(
"stxxl::create_runs start waiting read_reqs1");
229 STXXL_VERBOSE1(
"stxxl::create_runs finish waiting read_reqs1");
230 for (i = 0; i < run_size; ++i)
233 if (block_type::has_filler) {
235 ArrayOfSequencesIterator<
236 block_type,
typename block_type::value_type, block_type::size
238 ArrayOfSequencesIterator<
239 block_type,
typename block_type::value_type, block_type::size
240 >(Blocks1, run_size * block_type::size),
243 std::sort(Blocks1[0].elem, Blocks1[run_size].elem, cmp);
246 STXXL_VERBOSE1(
"stxxl::create_runs start waiting write_reqs");
248 STXXL_VERBOSE1(
"stxxl::create_runs finish waiting write_reqs");
250 for (i = 0; i < run_size; ++i)
252 STXXL_VERBOSE1(
"stxxl::create_runs posting write " <<
long(Blocks1[i].elem));
253 (*run)[i].value = Blocks1[i][0];
254 write_reqs[i] = Blocks1[i].write((*run)[i].bid);
257 STXXL_VERBOSE1(
"stxxl::create_runs start waiting write_reqs");
259 STXXL_VERBOSE1(
"stxxl::create_runs finish waiting write_reqs");
268 delete[] next_run_reads;
272 template <
typename block_type,
typename run_type,
typename value_cmp>
273 bool check_sorted_runs(run_type ** runs,
278 typedef typename block_type::value_type value_type;
281 STXXL_MSG(
"check_sorted_runs Runs: " << nruns);
282 unsigned_type irun = 0;
283 for (irun = 0; irun < nruns; ++irun)
285 const unsigned_type nblocks_per_run = runs[irun]->size();
286 unsigned_type blocks_left = nblocks_per_run;
287 block_type * blocks =
new block_type[m];
289 value_type last = cmp.min_value();
291 for (unsigned_type off = 0; off < nblocks_per_run; off += m)
293 const unsigned_type nblocks = STXXL_MIN(blocks_left, m);
294 const unsigned_type nelements = nblocks * block_type::size;
295 blocks_left -= nblocks;
297 for (unsigned_type j = 0; j < nblocks; ++j)
299 reqs[j] = blocks[j].read((*runs[irun])[j + off].bid);
303 if (off && cmp(blocks[0][0], last))
305 STXXL_MSG(
"check_sorted_runs wrong first value in the run " << irun);
306 STXXL_MSG(
" first value: " << blocks[0][0]);
307 STXXL_MSG(
" last value: " << last);
308 for (unsigned_type k = 0; k < block_type::size; ++k)
309 STXXL_MSG(
"Element " << k <<
" in the block is :" << blocks[0][k]);
314 for (unsigned_type j = 0; j < nblocks; ++j)
316 if (!(blocks[j][0] == (*runs[irun])[j + off].value))
318 STXXL_MSG(
"check_sorted_runs wrong trigger in the run " << irun <<
" block " << (j + off));
319 STXXL_MSG(
" trigger value: " << (*runs[irun])[j + off].value);
320 STXXL_MSG(
"Data in the block:");
321 for (unsigned_type k = 0; k < block_type::size; ++k)
322 STXXL_MSG(
"Element " << k <<
" in the block is :" << blocks[j][k]);
325 for (unsigned_type k = 0; k < nblocks; ++k)
328 STXXL_MSG(
"Bad one comes next.");
329 STXXL_MSG(
"BID " << (k + off) <<
" is: " << ((*runs[irun])[k + off].bid));
335 if (!stxxl::is_sorted(
336 ArrayOfSequencesIterator<
337 block_type,
typename block_type::value_type, block_type::size
339 ArrayOfSequencesIterator<
340 block_type,
typename block_type::value_type, block_type::size
341 >(blocks, nelements),
344 STXXL_MSG(
"check_sorted_runs wrong order in the run " << irun);
345 STXXL_MSG(
"Data in blocks:");
346 for (unsigned_type j = 0; j < nblocks; ++j)
348 for (unsigned_type k = 0; k < block_type::size; ++k)
349 STXXL_MSG(
" Element " << k <<
" in block " << (j + off) <<
" is :" << blocks[j][k]);
352 for (unsigned_type k = 0; k < nblocks; ++k)
354 STXXL_MSG(
"BID " << (k + off) <<
" is: " << ((*runs[irun])[k + off].bid));
360 last = blocks[nblocks - 1][block_type::size - 1];
363 assert(blocks_left == 0);
372 template <
typename block_type,
typename run_type,
typename value_cmp>
373 void merge_runs(run_type ** in_runs, int_type nruns, run_type * out_run, unsigned_type _m, value_cmp cmp
376 typedef typename block_type::bid_type bid_type;
377 typedef typename block_type::value_type value_type;
379 typedef run_cursor2<block_type, prefetcher_type> run_cursor_type;
380 typedef run_cursor2_cmp<block_type, prefetcher_type, value_cmp> run_cursor2_cmp_type;
383 run_type consume_seq(out_run->size());
385 int_type * prefetch_seq =
new int_type[out_run->size()];
387 typename run_type::iterator copy_start = consume_seq.begin();
388 for (i = 0; i < nruns; i++)
391 copy_start = std::copy(
397 std::stable_sort(consume_seq.begin(), consume_seq.end(),
398 trigger_entry_cmp<bid_type, value_type, value_cmp>(cmp));
400 int_type disks_number = config::get_instance()->disks_number();
402 #ifdef PLAY_WITH_OPT_PREF
403 const int_type n_write_buffers = 4 * disks_number;
405 const int_type n_prefetch_buffers = STXXL_MAX(2 * disks_number, (3 * (int_type(_m) - nruns) / 4));
406 const int_type n_write_buffers = STXXL_MAX(2 * disks_number, int_type(_m) - nruns - n_prefetch_buffers);
407 #ifdef SORT_OPTIMAL_PREFETCHING
409 const int_type n_opt_prefetch_buffers = 2 * disks_number + (3 * (n_prefetch_buffers - 2 * disks_number)) / 10;
413 #ifdef SORT_OPTIMAL_PREFETCHING
414 compute_prefetch_schedule(
417 n_opt_prefetch_buffers,
420 for (i = 0; i < out_run->size(); i++)
425 prefetcher_type prefetcher(consume_seq.begin(),
428 nruns + n_prefetch_buffers);
432 int_type out_run_size = out_run->size();
434 block_type * out_buffer = writer.get_free_block();
439 if (do_parallel_merge())
441 #if STXXL_PARALLEL_MULTIWAY_MERGE
445 typedef stxxl::int64 diff_type;
446 typedef std::pair<typename block_type::iterator, typename block_type::iterator> sequence;
447 typedef typename std::vector<sequence>::size_type seqs_size_type;
448 std::vector<sequence> seqs(nruns);
449 std::vector<block_type *> buffers(nruns);
451 for (int_type i = 0; i < nruns; i++)
453 buffers[i] = prefetcher.pull_block();
454 seqs[i] = std::make_pair(buffers[i]->begin(), buffers[i]->end());
458 #ifdef STXXL_CHECK_ORDER_IN_SORTS
459 value_type last_elem = cmp.min_value();
462 for (int_type j = 0; j < out_run_size; ++j)
464 diff_type rest = block_type::size;
466 STXXL_VERBOSE1(
"output block " << j);
468 value_type * min_last_element = NULL;
469 diff_type total_size = 0;
471 for (seqs_size_type i = 0; i < seqs.size(); i++)
473 if (seqs[i].first == seqs[i].second)
476 if (min_last_element == NULL)
477 min_last_element = &(*(seqs[i].second - 1));
479 min_last_element = cmp(*min_last_element, *(seqs[i].second - 1)) ? min_last_element : &(*(seqs[i].second - 1));
481 total_size += seqs[i].second - seqs[i].first;
482 STXXL_VERBOSE1(
"last " << *(seqs[i].second - 1) <<
" block size " << (seqs[i].second - seqs[i].first));
485 assert(min_last_element != NULL);
487 STXXL_VERBOSE1(
"min_last_element " << min_last_element <<
" total size " << total_size + (block_type::size - rest));
489 diff_type less_equal_than_min_last = 0;
491 for (seqs_size_type i = 0; i < seqs.size(); i++)
493 if (seqs[i].first == seqs[i].second)
496 typename block_type::iterator position = std::upper_bound(seqs[i].first, seqs[i].second, *min_last_element, cmp);
497 STXXL_VERBOSE1(
"greater equal than " << position - seqs[i].first);
498 less_equal_than_min_last += position - seqs[i].first;
501 STXXL_VERBOSE1(
"finished loop");
503 ptrdiff_t output_size = (std::min)(less_equal_than_min_last, rest);
505 STXXL_VERBOSE1(
"before merge" << output_size);
507 stxxl::parallel::multiway_merge(seqs.begin(), seqs.end(), out_buffer->end() - rest, cmp, output_size);
510 STXXL_VERBOSE1(
"after merge");
512 (*out_run)[j].value = (*out_buffer)[0];
516 STXXL_VERBOSE1(
"so long");
518 for (seqs_size_type i = 0; i < seqs.size(); i++)
520 if (seqs[i].first == seqs[i].second)
522 if (prefetcher.block_consumed(buffers[i]))
524 seqs[i].first = buffers[i]->begin();
525 seqs[i].second = buffers[i]->end();
526 STXXL_VERBOSE1(
"block ran empty " << i);
530 seqs.erase(seqs.begin() + i);
531 buffers.erase(buffers.begin() + i);
532 STXXL_VERBOSE1(
"seq removed " << i);
536 }
while (rest > 0 && seqs.size() > 0);
538 #ifdef STXXL_CHECK_ORDER_IN_SORTS
539 if (!stxxl::is_sorted(out_buffer->begin(), out_buffer->end(), cmp))
541 for (value_type * i = out_buffer->begin() + 1; i != out_buffer->end(); i++)
542 if (cmp(*i, *(i - 1)))
544 STXXL_VERBOSE1(
"Error at position " << (i - out_buffer->begin()));
550 assert(cmp((*out_buffer)[0], last_elem) ==
false);
552 last_elem = (*out_buffer)[block_type::size - 1];
556 out_buffer = writer.write(out_buffer, (*out_run)[j].bid);
569 loser_tree<run_cursor_type, run_cursor2_cmp_type, block_type::size>
570 losers(&prefetcher, nruns, run_cursor2_cmp_type(cmp));
572 #ifdef STXXL_CHECK_ORDER_IN_SORTS
573 value_type last_elem = cmp.min_value();
576 for (i = 0; i < out_run_size; ++i)
578 losers.multi_merge(out_buffer->elem);
579 (*out_run)[i].value = *(out_buffer->elem);
581 #ifdef STXXL_CHECK_ORDER_IN_SORTS
582 assert(stxxl::is_sorted(
588 assert(cmp(*(out_buffer->elem), last_elem) ==
false);
590 last_elem = (*out_buffer).elem[block_type::size - 1];
593 out_buffer = writer.write(out_buffer, (*out_run)[i].bid);
599 delete[] prefetch_seq;
602 for (i = 0; i < nruns; ++i)
604 unsigned_type sz = in_runs[i]->size();
605 for (unsigned_type j = 0; j < sz; ++j)
614 template <
typename block_type,
615 typename alloc_strategy,
616 typename input_bid_iterator,
618 simple_vector<trigger_entry<typename block_type::bid_type, typename block_type::value_type> > *
619 sort_blocks(input_bid_iterator input_bids,
625 typedef typename block_type::value_type type;
626 typedef typename block_type::bid_type bid_type;
627 typedef trigger_entry<bid_type, type> trigger_entry_type;
628 typedef simple_vector<trigger_entry_type> run_type;
629 typedef typename interleaved_alloc_traits<alloc_strategy>::strategy interleaved_alloc_strategy;
631 unsigned_type m2 = _m / 2;
632 unsigned_type full_runs = _n / m2;
633 unsigned_type partial_runs = ((_n % m2) ? 1 : 0);
634 unsigned_type nruns = full_runs + partial_runs;
637 config * cfg = config::get_instance();
643 double begin = timestamp(), after_runs_creation, end;
645 run_type ** runs =
new run_type *[nruns];
647 for (i = 0; i < full_runs; i++)
648 runs[i] =
new run_type(m2);
652 runs[i] =
new run_type(_n - full_runs * m2);
655 for (i = 0; i < nruns; ++i)
659 trigger_entry_iterator<typename run_type::iterator, block_type::raw_size>(runs[i]->begin()),
660 trigger_entry_iterator<typename run_type::iterator, block_type::raw_size>(runs[i]->end()));
663 sort_local::create_runs<block_type,
666 value_cmp>(input_bids, runs, nruns, _m, cmp);
668 after_runs_creation = timestamp();
670 double io_wait_after_rf = stats::get_instance()->get_io_wait_time();
672 disk_queues::get_instance()->set_priority_op(disk_queue::WRITE);
676 const int_type merge_factor =
static_cast<int_type
>(ceil(pow(nruns, 1. / ceil(log(
double(nruns)) /
678 run_type ** new_runs;
682 int_type new_nruns = div_and_round_up(nruns, merge_factor);
683 STXXL_VERBOSE(
"Starting new merge phase: nruns: " << nruns <<
684 " opt_merge_factor: " << merge_factor <<
" m:" << _m <<
" new_nruns: " << new_nruns);
686 new_runs =
new run_type *[new_nruns];
688 int_type runs_left = nruns;
689 int_type cur_out_run = 0;
690 int_type blocks_in_new_run = 0;
692 while (runs_left > 0)
694 int_type runs2merge = STXXL_MIN(runs_left, merge_factor);
695 blocks_in_new_run = 0;
696 for (unsigned_type i = nruns - runs_left; i < (nruns - runs_left + runs2merge); i++)
697 blocks_in_new_run += runs[i]->size();
700 new_runs[cur_out_run++] =
new run_type(blocks_in_new_run);
701 runs_left -= runs2merge;
704 if (cur_out_run == 1 && blocks_in_new_run == int_type(_n) && (input_bids->storage->get_id() == -1))
707 input_bid_iterator cur = input_bids;
708 for (int_type i = 0; cur != (input_bids + _n); ++cur)
710 (*new_runs[0])[i++].bid = *cur;
713 bid_type & firstBID = (*new_runs[0])[0].bid;
714 if (firstBID.storage->get_id() != -1)
720 bid_type & lastBID = (*new_runs[0])[_n - 1].bid;
721 if (lastBID.storage->get_id() != -1)
730 mng->
new_blocks(interleaved_alloc_strategy(new_nruns, 0, ndisks),
731 RunsToBIDArrayAdaptor2<block_type::raw_size, run_type>(new_runs, 0, new_nruns, blocks_in_new_run),
732 RunsToBIDArrayAdaptor2<block_type::raw_size, run_type>(new_runs, _n, new_nruns, blocks_in_new_run));
737 while (runs_left > 0)
739 int_type runs2merge = STXXL_MIN(runs_left, merge_factor);
740 #ifdef STXXL_CHECK_ORDER_IN_SORTS
741 assert((check_sorted_runs<block_type, run_type, value_cmp>(runs + nruns - runs_left, runs2merge, m2, cmp)));
743 STXXL_VERBOSE(
"Merging " << runs2merge <<
" runs");
744 merge_runs<block_type, run_type>(runs + nruns - runs_left,
745 runs2merge, *(new_runs + (cur_out_run++)), _m, cmp
747 runs_left -= runs2merge;
755 run_type * result = *runs;
760 STXXL_VERBOSE(
"Elapsed time : " << end - begin <<
" s. Run creation time: " <<
761 after_runs_creation - begin <<
" s");
762 STXXL_VERBOSE(
"Time in I/O wait(rf): " << io_wait_after_rf <<
" s");
763 STXXL_VERBOSE(*stats::get_instance());
764 UNUSED(begin + io_wait_after_rf);
778 template <
typename ExtIterator_,
typename StrictWeakOrdering_>
779 void sort(ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp, unsigned_type M)
781 typedef simple_vector<sort_local::trigger_entry<
typename ExtIterator_::bid_type,
782 typename ExtIterator_::vector_type::value_type> > run_type;
784 typedef typename ExtIterator_::vector_type::value_type value_type;
785 typedef typename ExtIterator_::block_type block_type;
788 assert(!cmp(cmp.min_value(), cmp.min_value()));
789 assert(cmp(cmp.min_value(), cmp.max_value()));
790 assert(!cmp(cmp.max_value(), cmp.max_value()));
798 if ((last - first) *
sizeof(value_type) * sort_memory_usage_factor() < M)
800 stl_in_memory_sort(first, last, cmp);
804 assert(2 * block_type::raw_size * sort_memory_usage_factor() <= M);
806 if (first.block_offset())
808 if (last.block_offset())
811 typename ExtIterator_::block_type * first_block =
new typename ExtIterator_::block_type;
812 typename ExtIterator_::block_type * last_block =
new typename ExtIterator_::block_type;
813 typename ExtIterator_::bid_type first_bid, last_bid;
816 req = first_block->read(*first.bid());
822 req = last_block->read(*last.bid());
825 for ( ; i < first.block_offset(); ++i)
827 first_block->elem[i] = cmp.min_value();
833 req = first_block->write(first_bid);
834 for (i = last.block_offset(); i < block_type::size; ++i)
836 last_block->elem[i] = cmp.max_value();
842 req = last_block->write(last_bid);
844 n = last.bid() - first.bid() + 1;
846 std::swap(first_bid, *first.bid());
847 std::swap(last_bid, *last.bid());
856 sort_local::sort_blocks<
857 typename ExtIterator_::block_type,
858 typename ExtIterator_::vector_type::alloc_strategy,
859 typename ExtIterator_::bids_container_iterator>
860 (first.bid(), n, M / sort_memory_usage_factor() / block_type::raw_size, cmp);
863 first_block =
new typename ExtIterator_::block_type;
864 last_block =
new typename ExtIterator_::block_type;
865 typename ExtIterator_::block_type * sorted_first_block =
new typename ExtIterator_::block_type;
866 typename ExtIterator_::block_type * sorted_last_block =
new typename ExtIterator_::block_type;
869 reqs[0] = first_block->read(first_bid);
870 reqs[1] = sorted_first_block->read((*(out->begin())).bid);
875 reqs[0] = last_block->read(last_bid);
876 reqs[1] = sorted_last_block->read(((*out)[out->size() - 1]).bid);
878 for (i = first.block_offset(); i < block_type::size; i++)
880 first_block->elem[i] = sorted_first_block->elem[i];
886 req = first_block->write(first_bid);
888 for (i = 0; i < last.block_offset(); ++i)
890 last_block->elem[i] = sorted_last_block->elem[i];
895 req = last_block->write(last_bid);
900 *first.bid() = first_bid;
901 *last.bid() = last_bid;
903 typename run_type::iterator it = out->begin();
905 typename ExtIterator_::bids_container_iterator cur_bid = first.bid();
908 for ( ; cur_bid != last.bid(); ++cur_bid, ++it)
910 *cur_bid = (*it).bid;
914 delete sorted_first_block;
915 delete sorted_last_block;
928 typename ExtIterator_::block_type * first_block =
new typename ExtIterator_::block_type;
929 typename ExtIterator_::bid_type first_bid;
932 req = first_block->read(*first.bid());
938 for ( ; i < first.block_offset(); ++i)
940 first_block->elem[i] = cmp.min_value();
943 req = first_block->write(first_bid);
945 n = last.bid() - first.bid();
947 std::swap(first_bid, *first.bid());
955 sort_local::sort_blocks<
956 typename ExtIterator_::block_type,
957 typename ExtIterator_::vector_type::alloc_strategy,
958 typename ExtIterator_::bids_container_iterator>
959 (first.bid(), n, M / sort_memory_usage_factor() / block_type::raw_size, cmp);
962 first_block =
new typename ExtIterator_::block_type;
964 typename ExtIterator_::block_type * sorted_first_block =
new typename ExtIterator_::block_type;
968 reqs[0] = first_block->read(first_bid);
969 reqs[1] = sorted_first_block->read((*(out->begin())).bid);
974 for (i = first.block_offset(); i < block_type::size; ++i)
976 first_block->elem[i] = sorted_first_block->elem[i];
979 req = first_block->write(first_bid);
983 *first.bid() = first_bid;
985 typename run_type::iterator it = out->begin();
987 typename ExtIterator_::bids_container_iterator cur_bid = first.bid();
990 for ( ; cur_bid != last.bid(); ++cur_bid, ++it)
992 *cur_bid = (*it).bid;
995 *cur_bid = (*it).bid;
997 delete sorted_first_block;
1008 if (last.block_offset())
1011 typename ExtIterator_::block_type * last_block =
new typename ExtIterator_::block_type;
1012 typename ExtIterator_::bid_type last_bid;
1016 req = last_block->read(*last.bid());
1021 for (i = last.block_offset(); i < block_type::size; ++i)
1023 last_block->elem[i] = cmp.max_value();
1026 req = last_block->write(last_bid);
1028 n = last.bid() - first.bid() + 1;
1030 std::swap(last_bid, *last.bid());
1038 sort_local::sort_blocks<
1039 typename ExtIterator_::block_type,
1040 typename ExtIterator_::vector_type::alloc_strategy,
1041 typename ExtIterator_::bids_container_iterator>
1042 (first.bid(), n, M / sort_memory_usage_factor() / block_type::raw_size, cmp);
1045 last_block =
new typename ExtIterator_::block_type;
1046 typename ExtIterator_::block_type * sorted_last_block =
new typename ExtIterator_::block_type;
1049 reqs[0] = last_block->read(last_bid);
1050 reqs[1] = sorted_last_block->read(((*out)[out->size() - 1]).bid);
1055 for (i = 0; i < last.block_offset(); ++i)
1057 last_block->elem[i] = sorted_last_block->elem[i];
1060 req = last_block->write(last_bid);
1064 *last.bid() = last_bid;
1066 typename run_type::iterator it = out->begin();
1067 typename ExtIterator_::bids_container_iterator cur_bid = first.bid();
1069 for ( ; cur_bid != last.bid(); ++cur_bid, ++it)
1071 *cur_bid = (*it).bid;
1074 delete sorted_last_block;
1085 n = last.bid() - first.bid();
1088 sort_local::sort_blocks<
typename ExtIterator_::block_type,
1089 typename ExtIterator_::vector_type::alloc_strategy,
1090 typename ExtIterator_::bids_container_iterator>
1091 (first.bid(), n, M / sort_memory_usage_factor() / block_type::raw_size, cmp);
1093 typename run_type::iterator it = out->begin();
1094 typename ExtIterator_::bids_container_iterator cur_bid = first.bid();
1096 for ( ; cur_bid != last.bid(); ++cur_bid, ++it)
1098 *cur_bid = (*it).bid;
1106 #ifdef STXXL_CHECK_ORDER_IN_SORTS
1107 assert(stxxl::is_sorted(first, last, cmp));
1113 __STXXL_END_NAMESPACE
1115 #endif // !STXXL_SORT_HEADER