14 #ifndef STXXL_SORT_HELPER_HEADER
15 #define STXXL_SORT_HELPER_HEADER
19 #include <stxxl/bits/algo/run_cursor.h>
20 #include <stxxl/bits/verbose.h>
23 __STXXL_BEGIN_NAMESPACE
28 template <
typename StrictWeakOrdering>
29 inline void verify_sentinel_strict_weak_ordering(StrictWeakOrdering cmp)
31 assert(!cmp(cmp.min_value(), cmp.min_value()));
32 assert(cmp(cmp.min_value(), cmp.max_value()));
33 assert(!cmp(cmp.max_value(), cmp.min_value()));
34 assert(!cmp(cmp.max_value(), cmp.max_value()));
38 template <
typename BlockTp_,
typename ValTp_ =
typename BlockTp_::value_type>
41 typedef BlockTp_ block_type;
42 typedef typename block_type::bid_type bid_type;
43 typedef ValTp_ value_type;
54 template <
typename TriggerEntryTp_,
typename ValueCmp_>
55 struct trigger_entry_cmp :
public std::binary_function<TriggerEntryTp_, TriggerEntryTp_, bool>
57 typedef TriggerEntryTp_ trigger_entry_type;
59 trigger_entry_cmp(ValueCmp_ c) : cmp(c) { }
60 trigger_entry_cmp(
const trigger_entry_cmp & a) : cmp(a.cmp) { }
61 bool operator () (
const trigger_entry_type & a,
const trigger_entry_type & b)
const
63 return cmp(a.value, b.value);
67 template <
typename block_type,
68 typename prefetcher_type,
70 struct run_cursor2_cmp :
public std::binary_function<run_cursor2<block_type, prefetcher_type>, run_cursor2<block_type, prefetcher_type>, bool>
72 typedef run_cursor2<block_type, prefetcher_type> cursor_type;
75 run_cursor2_cmp(value_cmp c) : cmp(c) { }
76 run_cursor2_cmp(
const run_cursor2_cmp & a) : cmp(a.cmp) { }
77 inline bool operator () (
const cursor_type & a,
const cursor_type & b)
const
79 if (UNLIKELY(b.empty()))
82 if (UNLIKELY(a.empty()))
86 return (cmp(a.current(), b.current()));
91 template <
typename SequenceVector,
typename ValueType,
typename Comparator>
93 unsigned_type count_elements_less_equal(
const SequenceVector & seqs,
const ValueType & bound, Comparator cmp)
95 typedef typename SequenceVector::size_type seqs_size_type;
96 typedef typename SequenceVector::value_type::first_type iterator;
97 unsigned_type count = 0;
99 for (seqs_size_type i = 0; i < seqs.size(); ++i)
101 iterator position = std::upper_bound(seqs[i].first, seqs[i].second, bound, cmp);
102 STXXL_VERBOSE1(
"less equal than " << position - seqs[i].first);
103 count += position - seqs[i].first;
105 STXXL_VERBOSE1(
"finished loop");
110 template <
typename SequenceVector,
typename BufferPtrVector,
typename Prefetcher>
112 void refill_or_remove_empty_sequences(SequenceVector & seqs,
113 BufferPtrVector & buffers,
114 Prefetcher & prefetcher)
116 typedef typename SequenceVector::size_type seqs_size_type;
118 for (seqs_size_type i = 0; i < seqs.size(); ++i)
120 if (seqs[i].first == seqs[i].second)
122 if (prefetcher.block_consumed(buffers[i]))
124 seqs[i].first = buffers[i]->begin();
125 seqs[i].second = buffers[i]->end();
126 STXXL_VERBOSE1(
"block ran empty " << i);
130 seqs.erase(seqs.begin() + i);
131 buffers.erase(buffers.begin() + i);
132 STXXL_VERBOSE1(
"seq removed " << i);
140 __STXXL_END_NAMESPACE
142 #endif // !STXXL_SORT_HELPER_HEADER