00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #ifndef STXXL_SORT_HELPER_HEADER
00015 #define STXXL_SORT_HELPER_HEADER
00016
00017 #include <algorithm>
00018 #include <functional>
00019 #include <stxxl/bits/algo/run_cursor.h>
00020 #include <stxxl/bits/verbose.h>
00021
00022
00023 __STXXL_BEGIN_NAMESPACE
00024
00026 namespace sort_helper
00027 {
00028 template <typename StrictWeakOrdering>
00029 inline void verify_sentinel_strict_weak_ordering(StrictWeakOrdering cmp)
00030 {
00031 assert(!cmp(cmp.min_value(), cmp.min_value()));
00032 assert(cmp(cmp.min_value(), cmp.max_value()));
00033 assert(!cmp(cmp.max_value(), cmp.min_value()));
00034 assert(!cmp(cmp.max_value(), cmp.max_value()));
00035 STXXL_UNUSED(cmp);
00036 }
00037
00038 template <typename BlockTp_, typename ValTp_ = typename BlockTp_::value_type>
00039 struct trigger_entry
00040 {
00041 typedef BlockTp_ block_type;
00042 typedef typename block_type::bid_type bid_type;
00043 typedef ValTp_ value_type;
00044
00045 bid_type bid;
00046 value_type value;
00047
00048 operator bid_type ()
00049 {
00050 return bid;
00051 }
00052 };
00053
00054 template <typename TriggerEntryTp_, typename ValueCmp_>
00055 struct trigger_entry_cmp : public std::binary_function<TriggerEntryTp_, TriggerEntryTp_, bool>
00056 {
00057 typedef TriggerEntryTp_ trigger_entry_type;
00058 ValueCmp_ cmp;
00059 trigger_entry_cmp(ValueCmp_ c) : cmp(c) { }
00060 trigger_entry_cmp(const trigger_entry_cmp & a) : cmp(a.cmp) { }
00061 bool operator () (const trigger_entry_type & a, const trigger_entry_type & b) const
00062 {
00063 return cmp(a.value, b.value);
00064 }
00065 };
00066
00067 template <typename block_type,
00068 typename prefetcher_type,
00069 typename value_cmp>
00070 struct run_cursor2_cmp : public std::binary_function<run_cursor2<block_type, prefetcher_type>, run_cursor2<block_type, prefetcher_type>, bool>
00071 {
00072 typedef run_cursor2<block_type, prefetcher_type> cursor_type;
00073 value_cmp cmp;
00074
00075 run_cursor2_cmp(value_cmp c) : cmp(c) { }
00076 run_cursor2_cmp(const run_cursor2_cmp & a) : cmp(a.cmp) { }
00077 inline bool operator () (const cursor_type & a, const cursor_type & b) const
00078 {
00079 if (UNLIKELY(b.empty()))
00080 return true;
00081
00082 if (UNLIKELY(a.empty()))
00083 return false;
00084
00085
00086 return (cmp(a.current(), b.current()));
00087 }
00088 };
00089
00090
00091 template <typename SequenceVector, typename ValueType, typename Comparator>
00092 inline
00093 unsigned_type count_elements_less_equal(const SequenceVector & seqs, const ValueType & bound, Comparator cmp)
00094 {
00095 typedef typename SequenceVector::size_type seqs_size_type;
00096 typedef typename SequenceVector::value_type::first_type iterator;
00097 unsigned_type count = 0;
00098
00099 for (seqs_size_type i = 0; i < seqs.size(); ++i)
00100 {
00101 iterator position = std::upper_bound(seqs[i].first, seqs[i].second, bound, cmp);
00102 STXXL_VERBOSE1("less equal than " << position - seqs[i].first);
00103 count += position - seqs[i].first;
00104 }
00105 STXXL_VERBOSE1("finished loop");
00106 return count;
00107 }
00108
00109
00110 template <typename SequenceVector, typename BufferPtrVector, typename Prefetcher>
00111 inline
00112 void refill_or_remove_empty_sequences(SequenceVector & seqs,
00113 BufferPtrVector & buffers,
00114 Prefetcher & prefetcher)
00115 {
00116 typedef typename SequenceVector::size_type seqs_size_type;
00117
00118 for (seqs_size_type i = 0; i < seqs.size(); ++i)
00119 {
00120 if (seqs[i].first == seqs[i].second)
00121 {
00122 if (prefetcher.block_consumed(buffers[i]))
00123 {
00124 seqs[i].first = buffers[i]->begin();
00125 seqs[i].second = buffers[i]->end();
00126 STXXL_VERBOSE1("block ran empty " << i);
00127 }
00128 else
00129 {
00130 seqs.erase(seqs.begin() + i);
00131 buffers.erase(buffers.begin() + i);
00132 STXXL_VERBOSE1("seq removed " << i);
00133 --i;
00134 }
00135 }
00136 }
00137 }
00138 }
00139
00140 __STXXL_END_NAMESPACE
00141
00142 #endif // !STXXL_SORT_HELPER_HEADER
00143