14 #ifndef STXXL_KSORT_HEADER
15 #define STXXL_KSORT_HEADER
19 #include <stxxl/bits/mng/mng.h>
20 #include <stxxl/bits/common/rand.h>
21 #include <stxxl/bits/mng/adaptor.h>
22 #include <stxxl/bits/common/simple_vector.h>
23 #include <stxxl/bits/common/switch.h>
24 #include <stxxl/bits/mng/block_alloc_interleaved.h>
25 #include <stxxl/bits/algo/intksort.h>
26 #include <stxxl/bits/algo/adaptor.h>
27 #include <stxxl/bits/algo/async_schedule.h>
28 #include <stxxl/bits/mng/block_prefetcher.h>
29 #include <stxxl/bits/mng/buf_writer.h>
30 #include <stxxl/bits/algo/run_cursor.h>
31 #include <stxxl/bits/algo/losertree.h>
32 #include <stxxl/bits/algo/inmemsort.h>
40 __STXXL_BEGIN_NAMESPACE
54 template <
typename _BIDTp,
typename _KeyTp>
57 typedef _BIDTp bid_type;
58 typedef _KeyTp key_type;
70 template <
typename _BIDTp,
typename _KeyTp>
71 inline bool operator < (const trigger_entry<_BIDTp, _KeyTp> & a,
72 const trigger_entry<_BIDTp, _KeyTp> & b)
74 return (a.key < b.key);
77 template <
typename _BIDTp,
typename _KeyTp>
78 inline bool operator > (
const trigger_entry<_BIDTp, _KeyTp> & a,
79 const trigger_entry<_BIDTp, _KeyTp> & b)
81 return (a.key > b.key);
84 template <
typename type,
typename key_type1>
87 typedef key_type1 key_type;
92 type_key(key_type k, type * p) : key(k), ptr(p)
96 template <
typename type,
typename key1>
97 bool operator < (const type_key<type, key1> & a,
const type_key<type, key1> & b)
102 template <
typename type,
typename key1>
103 bool operator > (
const type_key<type, key1> & a,
const type_key<type, key1> & b)
105 return a.key > b.key;
109 template <
typename block_type,
typename b
id_type>
110 struct write_completion_handler
117 * req = block->read(bid);
121 template <
typename type_key_,
124 typename input_bid_iterator,
125 typename key_extractor>
126 inline void write_out(
129 block_type * & cur_blk,
130 const block_type * end_blk,
131 int_type & out_block,
134 write_completion_handler<block_type, typename block_type::bid_type> * & next_read,
135 typename block_type::bid_type * & bids,
138 input_bid_iterator & it,
139 key_extractor keyobj)
141 typedef typename block_type::bid_type bid_type;
142 typedef typename block_type::type type;
144 type * elem = cur_blk->elem;
145 for (type_key_ * p = begin; p < end; p++)
147 elem[out_pos++] = *(p->ptr);
149 if (out_pos >= block_type::size)
151 run[out_block].key = keyobj(*(cur_blk->elem));
153 if (cur_blk < end_blk)
155 next_read->block = cur_blk;
156 next_read->req = read_reqs + out_block;
157 read_reqs[out_block] = NULL;
158 bids[out_block] = next_read->bid = *(it++);
160 write_reqs[out_block] = cur_blk->write(
168 write_reqs[out_block] = cur_blk->write(run[out_block].bid);
172 elem = cur_blk->elem;
182 typename input_bid_iterator,
183 typename key_extractor>
186 input_bid_iterator it,
188 const unsigned_type nruns,
189 const unsigned_type m2,
190 key_extractor keyobj)
192 typedef typename block_type::value_type type;
193 typedef typename block_type::bid_type bid_type;
194 typedef typename key_extractor::key_type key_type;
195 typedef type_key<type, key_type> type_key_;
198 block_type * Blocks1 =
new block_type[m2];
199 block_type * Blocks2 =
new block_type[m2];
200 bid_type * bids =
new bid_type[m2];
201 type_key_ * refs1 =
new type_key_[m2 * Blocks1->size];
202 type_key_ * refs2 =
new type_key_[m2 * Blocks1->size];
205 write_completion_handler<block_type, bid_type> * next_run_reads =
206 new write_completion_handler<block_type, bid_type>[m2];
210 int_type run_size = (*runs)->size();
213 static_cast<int>(ceil(log2((m2 * block_type::size *
sizeof(type_key_) / STXXL_L2_SIZE) ?
214 (
double(m2 * block_type::size *
sizeof(type_key_) / STXXL_L2_SIZE)) : 2.)));
215 const int log_k2 = int(log2(
double(m2 * Blocks1->size))) - log_k1 - 1;
216 STXXL_VERBOSE(
"log_k1: " << log_k1 <<
" log_k2:" << log_k2);
217 const int_type k1 = 1 << log_k1;
218 const int_type k2 = 1 << log_k2;
219 int_type * bucket1 =
new int_type[k1];
220 int_type * bucket2 =
new int_type[k2];
223 disk_queues::get_instance()->set_priority_op(disk_queue::WRITE);
225 for (i = 0; i < run_size; i++)
228 read_reqs[i] = Blocks1[i].read(bids[i]);
232 const int shift1 =
sizeof(key_type) * 8 - log_k1;
233 const int shift2 = shift1 - log_k2;
234 STXXL_VERBOSE(
"shift1: " << shift1 <<
" shift2:" << shift2);
236 for ( ; k < nruns; k++)
239 run_size = run->size();
241 std::fill(bucket1, bucket1 + k1, 0);
243 type_key_ * ref_ptr = refs1;
244 for (i = 0; i < run_size; i++)
247 write_reqs[i]->
wait();
249 read_reqs[i]->
wait();
252 classify_block(Blocks1[i].begin(), Blocks1[i].end(), ref_ptr, bucket1, offset, shift1, keyobj);
255 exclusive_prefix_sum(bucket1, k1);
256 classify(refs1, refs1 + run_size * Blocks1->size, refs2, bucket1,
259 int_type out_block = 0;
260 int_type out_pos = 0;
261 unsigned_type next_run_size = (k < nruns - 1) ? (runs[k + 1]->size()) : 0;
264 type_key_ * c = refs2;
265 type_key_ * d = refs1;
266 block_type * cur_blk = Blocks2;
267 block_type * end_blk = Blocks2 + next_run_size;
268 write_completion_handler<block_type, bid_type> * next_read = next_run_reads;
270 for (i = 0; i < k1; i++)
272 type_key_ * cEnd = refs2 + bucket1[i];
273 type_key_ * dEnd = refs1 + bucket1[i];
275 l1sort(c, cEnd, d, bucket2, k2,
276 offset + (key_type(1) << key_type(shift1)) * key_type(i), shift2);
279 d, dEnd, cur_blk, end_blk,
280 out_block, out_pos, *run, next_read, bids,
281 write_reqs, read_reqs, it, keyobj);
287 std::swap(Blocks1, Blocks2);
299 delete[] next_run_reads;
304 template <
typename block_type,
305 typename prefetcher_type,
306 typename key_extractor>
307 struct run_cursor2_cmp
309 typedef run_cursor2<block_type, prefetcher_type> cursor_type;
310 key_extractor keyobj;
311 run_cursor2_cmp(key_extractor keyobj_)
315 inline bool operator () (
const cursor_type & a,
const cursor_type & b)
317 if (UNLIKELY(b.empty()))
320 if (UNLIKELY(a.empty()))
324 return (keyobj(a.current()) < keyobj(b.current()));
328 run_cursor2_cmp() { }
332 template <
typename record_type,
typename key_extractor>
333 class key_comparison :
public std::binary_function<record_type, record_type, bool>
339 key_comparison(key_extractor ke_) : ke(ke_) { }
340 bool operator () (
const record_type & a,
const record_type & b)
const
342 return ke(a) < ke(b);
347 template <
typename block_type,
typename run_type,
typename key_ext_>
348 bool check_ksorted_runs(run_type ** runs,
353 typedef typename block_type::value_type value_type;
356 STXXL_MSG(
"check_sorted_runs Runs: " << nruns);
357 unsigned_type irun = 0;
358 for (irun = 0; irun < nruns; ++irun)
360 const unsigned_type nblocks_per_run = runs[irun]->size();
361 unsigned_type blocks_left = nblocks_per_run;
362 block_type * blocks =
new block_type[m];
364 value_type last = keyext.min_value();
366 for (unsigned_type off = 0; off < nblocks_per_run; off += m)
368 const unsigned_type nblocks = STXXL_MIN(blocks_left, m);
369 const unsigned_type nelements = nblocks * block_type::size;
370 blocks_left -= nblocks;
372 for (unsigned_type j = 0; j < nblocks; ++j)
374 reqs[j] = blocks[j].read((*runs[irun])[off + j].bid);
378 if (off && (keyext(blocks[0][0]) < keyext(last)))
380 STXXL_MSG(
"check_sorted_runs wrong first value in the run " << irun);
381 STXXL_MSG(
" first value: " << blocks[0][0] <<
" with key" << keyext(blocks[0][0]));
382 STXXL_MSG(
" last value: " << last <<
" with key" << keyext(last));
383 for (unsigned_type k = 0; k < block_type::size; ++k)
384 STXXL_MSG(
"Element " << k <<
" in the block is :" << blocks[0][k] <<
" key: " << keyext(blocks[0][k]));
388 for (unsigned_type j = 0; j < nblocks; ++j)
390 if (keyext(blocks[j][0]) != (*runs[irun])[off + j].key)
392 STXXL_MSG(
"check_sorted_runs wrong trigger in the run " << irun <<
" block " << (off + j));
393 STXXL_MSG(
" trigger value: " << (*runs[irun])[off + j].key);
394 STXXL_MSG(
"Data in the block:");
395 for (unsigned_type k = 0; k < block_type::size; ++k)
396 STXXL_MSG(
"Element " << k <<
" in the block is :" << blocks[j][k] <<
" with key: " << keyext(blocks[j][k]));
399 for (unsigned_type k = 0; k < nblocks; ++k)
402 STXXL_MSG(
"Bad one comes next.");
403 STXXL_MSG(
"BID " << (off + k) <<
" is: " << ((*runs[irun])[off + k].bid));
409 if (!stxxl::is_sorted(
411 ArrayOfSequencesIterator<
412 block_type,
typename block_type::value_type, block_type::size
414 ArrayOfSequencesIterator<
415 block_type,
typename block_type::value_type, block_type::size
416 >(blocks, nelements),
418 TwoToOneDimArrayRowAdaptor<
419 block_type, value_type, block_type::size
421 TwoToOneDimArrayRowAdaptor<
422 block_type, value_type, block_type::size
423 >(blocks, nelements),
425 key_comparison<value_type, key_ext_>()))
427 STXXL_MSG(
"check_sorted_runs wrong order in the run " << irun);
428 STXXL_MSG(
"Data in blocks:");
429 for (unsigned_type j = 0; j < nblocks; ++j)
431 for (unsigned_type k = 0; k < block_type::size; ++k)
432 STXXL_MSG(
" Element " << k <<
" in block " << (off + j) <<
" is :" << blocks[j][k] <<
" with key: " << keyext(blocks[j][k]));
435 for (unsigned_type k = 0; k < nblocks; ++k)
437 STXXL_MSG(
"BID " << (k + off) <<
" is: " << ((*runs[irun])[k + off].bid));
442 last = blocks[nblocks - 1][block_type::size - 1];
445 assert(blocks_left == 0);
454 template <
typename block_type,
typename run_type,
typename key_extractor>
455 void merge_runs(run_type ** in_runs, unsigned_type nruns, run_type * out_run, unsigned_type _m, key_extractor keyobj)
458 typedef run_cursor2<block_type, prefetcher_type> run_cursor_type;
461 run_type consume_seq(out_run->size());
463 int_type * prefetch_seq =
new int_type[out_run->size()];
465 typename run_type::iterator copy_start = consume_seq.begin();
466 for (i = 0; i < nruns; i++)
469 copy_start = std::copy(
474 std::stable_sort(consume_seq.begin(), consume_seq.end());
476 unsigned disks_number = config::get_instance()->disks_number();
478 #ifdef PLAY_WITH_OPT_PREF
479 const int_type n_write_buffers = 4 * disks_number;
481 const int_type n_prefetch_buffers = STXXL_MAX(int_type(2 * disks_number), (3 * (int_type(_m) - int_type(nruns)) / 4));
482 STXXL_VERBOSE(
"Prefetch buffers " << n_prefetch_buffers);
483 const int_type n_write_buffers = STXXL_MAX(int_type(2 * disks_number), int_type(_m) - int_type(nruns) - int_type(n_prefetch_buffers));
484 STXXL_VERBOSE(
"Write buffers " << n_write_buffers);
486 const int_type n_opt_prefetch_buffers = 2 * int_type(disks_number) + (3 * (int_type(n_prefetch_buffers) - int_type(2 * disks_number))) / 10;
487 STXXL_VERBOSE(
"Prefetch buffers " << n_opt_prefetch_buffers);
490 #ifdef SORT_OPTIMAL_PREFETCHING
491 compute_prefetch_schedule(
494 n_opt_prefetch_buffers,
497 for (i = 0; i < out_run->size(); i++)
503 prefetcher_type prefetcher(consume_seq.begin(),
506 nruns + n_prefetch_buffers);
510 unsigned_type out_run_size = out_run->size();
512 run_cursor2_cmp<block_type, prefetcher_type, key_extractor> cmp(keyobj);
515 run_cursor2_cmp<block_type, prefetcher_type, key_extractor>,
516 block_type::size> losers(&prefetcher, nruns, cmp);
519 block_type * out_buffer = writer.get_free_block();
521 for (i = 0; i < out_run_size; i++)
523 losers.multi_merge(out_buffer->elem);
524 (*out_run)[i].key = keyobj(out_buffer->elem[0]);
525 out_buffer = writer.write(out_buffer, (*out_run)[i].bid);
528 delete[] prefetch_seq;
531 for (i = 0; i < nruns; i++)
533 unsigned_type sz = in_runs[i]->size();
534 for (unsigned_type j = 0; j < sz; j++)
542 template <
typename block_type,
543 typename alloc_strategy,
544 typename input_bid_iterator,
545 typename key_extractor>
547 simple_vector<trigger_entry<typename block_type::bid_type, typename key_extractor::key_type> > *
548 ksort_blocks(input_bid_iterator input_bids, unsigned_type _n, unsigned_type _m, key_extractor keyobj)
550 typedef typename block_type::value_type type;
551 typedef typename key_extractor::key_type key_type;
552 typedef typename block_type::bid_type bid_type;
553 typedef trigger_entry<bid_type, typename key_extractor::key_type> trigger_entry_type;
554 typedef simple_vector<trigger_entry_type> run_type;
555 typedef typename interleaved_alloc_traits<alloc_strategy>::strategy interleaved_alloc_strategy;
557 unsigned_type m2 = div_and_round_up(_m, 2);
558 const unsigned_type m2_rf = m2 * block_type::raw_size /
559 (block_type::raw_size + block_type::size *
sizeof(type_key<type, key_type>));
560 STXXL_VERBOSE(
"Reducing number of blocks in a run from " << m2 <<
" to " <<
561 m2_rf <<
" due to key size: " <<
sizeof(
typename key_extractor::key_type) <<
" bytes");
563 unsigned_type full_runs = _n / m2;
564 unsigned_type partial_runs = ((_n % m2) ? 1 : 0);
565 unsigned_type nruns = full_runs + partial_runs;
568 config * cfg = config::get_instance();
572 STXXL_VERBOSE(
"n=" << _n <<
" nruns=" << nruns <<
"=" << full_runs <<
"+" << partial_runs);
574 double begin = timestamp(), after_runs_creation, end;
576 run_type ** runs =
new run_type *[nruns];
578 for (i = 0; i < full_runs; i++)
579 runs[i] =
new run_type(m2);
582 #ifdef INTERLEAVED_ALLOC
585 unsigned_type last_run_size = _n - full_runs * m2;
586 runs[i] =
new run_type(last_run_size);
588 mng->
new_blocks(interleaved_alloc_strategy(nruns, 0, ndisks),
589 RunsToBIDArrayAdaptor2<block_type::raw_size, run_type>
590 (runs, 0, nruns, last_run_size),
591 RunsToBIDArrayAdaptor2<block_type::raw_size, run_type>
592 (runs, _n, nruns, last_run_size));
595 mng->
new_blocks(interleaved_alloc_strategy(nruns, 0, ndisks),
596 RunsToBIDArrayAdaptor<block_type::raw_size, run_type>
598 RunsToBIDArrayAdaptor<block_type::raw_size, run_type>
603 runs[i] =
new run_type(_n - full_runs * m2);
606 for (i = 0; i < nruns; i++)
609 trigger_entry_iterator<typename run_type::iterator, block_type::raw_size>(runs[i]->begin()),
610 trigger_entry_iterator<typename run_type::iterator, block_type::raw_size>(runs[i]->end()));
614 create_runs<block_type,
617 key_extractor>(input_bids, runs, nruns, m2, keyobj);
619 after_runs_creation = timestamp();
621 double io_wait_after_rf = stats::get_instance()->get_io_wait_time();
623 disk_queues::get_instance()->set_priority_op(disk_queue::WRITE);
627 const int_type merge_factor =
static_cast<int_type
>(ceil(pow(nruns, 1. / ceil(log(
double(nruns)) / log(
double(_m))))));
628 run_type ** new_runs;
632 int_type new_nruns = div_and_round_up(nruns, merge_factor);
633 STXXL_VERBOSE(
"Starting new merge phase: nruns: " << nruns <<
634 " opt_merge_factor: " << merge_factor <<
" m:" << _m <<
" new_nruns: " << new_nruns);
636 new_runs =
new run_type *[new_nruns];
638 int_type runs_left = nruns;
639 int_type cur_out_run = 0;
640 int_type blocks_in_new_run = 0;
642 while (runs_left > 0)
644 int_type runs2merge = STXXL_MIN(runs_left, merge_factor);
645 blocks_in_new_run = 0;
646 for (unsigned_type i = nruns - runs_left; i < (nruns - runs_left + runs2merge); i++)
647 blocks_in_new_run += runs[i]->size();
650 new_runs[cur_out_run++] =
new run_type(blocks_in_new_run);
651 runs_left -= runs2merge;
654 if (cur_out_run == 1 && blocks_in_new_run == int_type(_n) && (input_bids->storage->get_id() == -1))
657 input_bid_iterator cur = input_bids;
658 for (int_type i = 0; cur != (input_bids + _n); ++cur)
660 (*new_runs[0])[i++].bid = *cur;
663 bid_type & firstBID = (*new_runs[0])[0].bid;
664 if (firstBID.storage->get_id() != -1)
670 bid_type & lastBID = (*new_runs[0])[_n - 1].bid;
671 if (lastBID.storage->get_id() != -1)
680 mng->
new_blocks(interleaved_alloc_strategy(new_nruns, 0, ndisks),
681 RunsToBIDArrayAdaptor2<block_type::raw_size, run_type>(new_runs, 0, new_nruns, blocks_in_new_run),
682 RunsToBIDArrayAdaptor2<block_type::raw_size, run_type>(new_runs, _n, new_nruns, blocks_in_new_run));
689 while (runs_left > 0)
691 int_type runs2merge = STXXL_MIN(runs_left, merge_factor);
692 #ifdef STXXL_CHECK_ORDER_IN_SORTS
693 assert((check_ksorted_runs<block_type, run_type, key_extractor>(runs + nruns - runs_left, runs2merge, m2, keyobj)));
695 STXXL_VERBOSE(
"Merging " << runs2merge <<
" runs");
696 merge_runs<block_type, run_type, key_extractor>(runs + nruns - runs_left,
697 runs2merge, *(new_runs + (cur_out_run++)), _m, keyobj);
698 runs_left -= runs2merge;
706 run_type * result = *runs;
711 STXXL_VERBOSE(
"Elapsed time : " << end - begin <<
" s. Run creation time: " <<
712 after_runs_creation - begin <<
" s");
713 STXXL_VERBOSE(
"Time in I/O wait(rf): " << io_wait_after_rf <<
" s");
714 STXXL_VERBOSE(*stats::get_instance());
715 UNUSED(begin + io_wait_after_rf);
764 template <
typename ExtIterator_,
typename KeyExtractor_>
765 void ksort(ExtIterator_ first_, ExtIterator_ last_, KeyExtractor_ keyobj, unsigned_type M__)
767 typedef simple_vector<ksort_local::trigger_entry<
typename ExtIterator_::bid_type,
768 typename KeyExtractor_::key_type> > run_type;
769 typedef typename ExtIterator_::vector_type::value_type value_type;
770 typedef typename ExtIterator_::block_type block_type;
778 if ((last_ - first_) *
sizeof(value_type) < M__)
780 stl_in_memory_sort(first_, last_, ksort_local::key_comparison<value_type, KeyExtractor_>(keyobj));
784 assert(2 * block_type::raw_size <= M__);
786 if (first_.block_offset())
788 if (last_.block_offset())
791 typename ExtIterator_::block_type * first_block =
new typename ExtIterator_::block_type;
792 typename ExtIterator_::block_type * last_block =
new typename ExtIterator_::block_type;
793 typename ExtIterator_::bid_type first_bid, last_bid;
796 req = first_block->read(*first_.bid());
802 req = last_block->read(*last_.bid());
805 for ( ; i < first_.block_offset(); i++)
807 first_block->elem[i] = keyobj.min_value();
812 req = first_block->write(first_bid);
813 for (i = last_.block_offset(); i < block_type::size; i++)
815 last_block->elem[i] = keyobj.max_value();
820 req = last_block->write(last_bid);
822 n = last_.bid() - first_.bid() + 1;
824 std::swap(first_bid, *first_.bid());
825 std::swap(last_bid, *last_.bid());
833 ksort_local::ksort_blocks<
834 typename ExtIterator_::block_type,
835 typename ExtIterator_::vector_type::alloc_strategy,
836 typename ExtIterator_::bids_container_iterator,
838 (first_.bid(), n, M__ / block_type::raw_size, keyobj);
841 first_block =
new typename ExtIterator_::block_type;
842 last_block =
new typename ExtIterator_::block_type;
843 typename ExtIterator_::block_type * sorted_first_block =
new typename ExtIterator_::block_type;
844 typename ExtIterator_::block_type * sorted_last_block =
new typename ExtIterator_::block_type;
847 reqs[0] = first_block->read(first_bid);
848 reqs[1] = sorted_first_block->read((*(out->begin())).bid);
851 reqs[0] = last_block->read(last_bid);
852 reqs[1] = sorted_last_block->read(((*out)[out->size() - 1]).bid);
854 for (i = first_.block_offset(); i < block_type::size; i++)
856 first_block->elem[i] = sorted_first_block->elem[i];
860 req = first_block->write(first_bid);
862 for (i = 0; i < last_.block_offset(); i++)
864 last_block->elem[i] = sorted_last_block->elem[i];
870 req = last_block->write(last_bid);
875 *first_.bid() = first_bid;
876 *last_.bid() = last_bid;
878 typename run_type::iterator it = out->begin();
880 typename ExtIterator_::bids_container_iterator cur_bid = first_.bid();
883 for ( ; cur_bid != last_.bid(); cur_bid++, it++)
885 *cur_bid = (*it).bid;
889 delete sorted_first_block;
890 delete sorted_last_block;
903 typename ExtIterator_::block_type * first_block =
new typename ExtIterator_::block_type;
904 typename ExtIterator_::bid_type first_bid;
907 req = first_block->read(*first_.bid());
913 for ( ; i < first_.block_offset(); i++)
915 first_block->elem[i] = keyobj.min_value();
918 req = first_block->write(first_bid);
920 n = last_.bid() - first_.bid();
922 std::swap(first_bid, *first_.bid());
929 ksort_local::ksort_blocks<
930 typename ExtIterator_::block_type,
931 typename ExtIterator_::vector_type::alloc_strategy,
932 typename ExtIterator_::bids_container_iterator,
934 (first_.bid(), n, M__ / block_type::raw_size, keyobj);
937 first_block =
new typename ExtIterator_::block_type;
939 typename ExtIterator_::block_type * sorted_first_block =
new typename ExtIterator_::block_type;
943 reqs[0] = first_block->read(first_bid);
944 reqs[1] = sorted_first_block->read((*(out->begin())).bid);
947 for (i = first_.block_offset(); i < block_type::size; i++)
949 first_block->elem[i] = sorted_first_block->elem[i];
952 req = first_block->write(first_bid);
956 *first_.bid() = first_bid;
958 typename run_type::iterator it = out->begin();
960 typename ExtIterator_::bids_container_iterator cur_bid = first_.bid();
963 for ( ; cur_bid != last_.bid(); cur_bid++, it++)
965 *cur_bid = (*it).bid;
968 *cur_bid = (*it).bid;
970 delete sorted_first_block;
981 if (last_.block_offset())
984 typename ExtIterator_::block_type * last_block =
new typename ExtIterator_::block_type;
985 typename ExtIterator_::bid_type last_bid;
989 req = last_block->read(*last_.bid());
993 for (i = last_.block_offset(); i < block_type::size; i++)
995 last_block->elem[i] = keyobj.max_value();
998 req = last_block->write(last_bid);
1000 n = last_.bid() - first_.bid() + 1;
1002 std::swap(last_bid, *last_.bid());
1009 ksort_local::ksort_blocks<
1010 typename ExtIterator_::block_type,
1011 typename ExtIterator_::vector_type::alloc_strategy,
1012 typename ExtIterator_::bids_container_iterator,
1014 (first_.bid(), n, M__ / block_type::raw_size, keyobj);
1017 last_block =
new typename ExtIterator_::block_type;
1018 typename ExtIterator_::block_type * sorted_last_block =
new typename ExtIterator_::block_type;
1021 reqs[0] = last_block->read(last_bid);
1022 reqs[1] = sorted_last_block->read(((*out)[out->size() - 1]).bid);
1025 for (i = 0; i < last_.block_offset(); i++)
1027 last_block->elem[i] = sorted_last_block->elem[i];
1030 req = last_block->write(last_bid);
1034 *last_.bid() = last_bid;
1036 typename run_type::iterator it = out->begin();
1037 typename ExtIterator_::bids_container_iterator cur_bid = first_.bid();
1039 for ( ; cur_bid != last_.bid(); cur_bid++, it++)
1041 *cur_bid = (*it).bid;
1044 delete sorted_last_block;
1055 n = last_.bid() - first_.bid();
1058 ksort_local::ksort_blocks<
1059 typename ExtIterator_::block_type,
1060 typename ExtIterator_::vector_type::alloc_strategy,
1061 typename ExtIterator_::bids_container_iterator,
1063 (first_.bid(), n, M__ / block_type::raw_size, keyobj);
1065 typename run_type::iterator it = out->begin();
1066 typename ExtIterator_::bids_container_iterator cur_bid = first_.bid();
1068 for ( ; cur_bid != last_.bid(); cur_bid++, it++)
1070 *cur_bid = (*it).bid;
1078 #ifdef STXXL_CHECK_ORDER_IN_SORTS
1079 assert(stxxl::is_sorted(first_, last_, ksort_local::key_comparison<value_type, KeyExtractor_>()));
1083 template <
typename record_type>
1084 struct ksort_defaultkey
1086 typedef typename record_type::key_type key_type;
1087 key_type operator () (
const record_type & obj)
const
1091 record_type max_value()
const
1093 return record_type::max_value();
1095 record_type min_value()
const
1097 return record_type::min_value();
1117 template <
typename ExtIterator_>
1118 void ksort(ExtIterator_ first_, ExtIterator_ last_, unsigned_type M__)
1120 ksort(first_, last_,
1121 ksort_defaultkey<typename ExtIterator_::vector_type::value_type>(), M__);
1127 __STXXL_END_NAMESPACE
1129 #endif // !STXXL_KSORT_HEADER