00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #ifndef STXXL_IN_MEMORY_SORT_HEADER
00015 #define STXXL_IN_MEMORY_SORT_HEADER
00016
00017 #include <stxxl/bits/namespace.h>
00018 #include <stxxl/bits/common/simple_vector.h>
00019 #include <stxxl/bits/io/request_operations.h>
00020 #include <stxxl/bits/algo/adaptor.h>
00021 #include <stxxl/bits/mng/adaptor.h>
00022 #include <stxxl/bits/parallel.h>
00023
00024 #include <algorithm>
00025
00026
00027 __STXXL_BEGIN_NAMESPACE
00028
00029 template <typename ExtIterator_, typename StrictWeakOrdering_>
00030 void stl_in_memory_sort(ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp)
00031 {
00032 typedef typename ExtIterator_::vector_type::value_type value_type;
00033 typedef typename ExtIterator_::block_type block_type;
00034
00035 STXXL_VERBOSE("stl_in_memory_sort, range: " << (last - first));
00036 first.flush();
00037 unsigned_type nblocks = last.bid() - first.bid() + (last.block_offset() ? 1 : 0);
00038 simple_vector<block_type> blocks(nblocks);
00039 simple_vector<request_ptr> reqs(nblocks);
00040 unsigned_type i;
00041
00042 for (i = 0; i < nblocks; ++i)
00043 reqs[i] = blocks[i].read(*(first.bid() + i));
00044
00045
00046 wait_all(reqs.begin(), nblocks);
00047
00048 unsigned_type last_block_correction = last.block_offset() ? (block_type::size - last.block_offset()) : 0;
00049 potentially_parallel::
00050 sort(make_element_iterator(blocks.begin(), first.block_offset()),
00051 make_element_iterator(blocks.begin(), nblocks * block_type::size - last_block_correction),
00052 cmp);
00053
00054 for (i = 0; i < nblocks; ++i)
00055 reqs[i] = blocks[i].write(*(first.bid() + i));
00056
00057 wait_all(reqs.begin(), nblocks);
00058 }
00059
00060
00061 __STXXL_END_NAMESPACE
00062
00063 #endif // !STXXL_IN_MEMORY_SORT_HEADER