STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sort_helper.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/algo/sort_helper.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2003 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009, 2010 Andreas Beckmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_ALGO_SORT_HELPER_HEADER
15 #define STXXL_ALGO_SORT_HELPER_HEADER
16 
17 #include <algorithm>
18 #include <functional>
20 #include <stxxl/bits/verbose.h>
21 
23 
24 //! \internal
25 namespace sort_helper {
26 
27 template <typename StrictWeakOrdering>
28 inline void verify_sentinel_strict_weak_ordering(StrictWeakOrdering cmp)
29 {
30  STXXL_ASSERT(!cmp(cmp.min_value(), cmp.min_value()));
31  STXXL_ASSERT(cmp(cmp.min_value(), cmp.max_value()));
32  STXXL_ASSERT(!cmp(cmp.max_value(), cmp.min_value()));
33  STXXL_ASSERT(!cmp(cmp.max_value(), cmp.max_value()));
34 }
35 
36 template <typename BlockType, typename ValueType = typename BlockType::value_type>
38 {
39  typedef BlockType block_type;
40  typedef typename block_type::bid_type bid_type;
41  typedef ValueType value_type;
42 
45 
46  operator bid_type ()
47  {
48  return bid;
49  }
50 };
51 
52 template <typename TriggerEntryType, typename ValueCmp>
54  : public std::binary_function<TriggerEntryType, TriggerEntryType, bool>
55 {
56  typedef TriggerEntryType trigger_entry_type;
57  ValueCmp cmp;
58  trigger_entry_cmp(ValueCmp c) : cmp(c) { }
59  trigger_entry_cmp(const trigger_entry_cmp& a) : cmp(a.cmp) { }
60  bool operator () (const trigger_entry_type& a, const trigger_entry_type& b) const
61  {
62  return cmp(a.value, b.value);
63  }
64 };
65 
66 template <typename BlockType,
67  typename PrefetcherType,
68  typename ValueCmp>
70  : public std::binary_function<
71  run_cursor2<BlockType, PrefetcherType>,
72  run_cursor2<BlockType, PrefetcherType>,
73  bool
74  >
75 {
76  typedef BlockType block_type;
77  typedef PrefetcherType prefetcher_type;
78  typedef ValueCmp value_cmp;
79 
82 
83  run_cursor2_cmp(value_cmp c) : cmp(c) { }
84  run_cursor2_cmp(const run_cursor2_cmp& a) : cmp(a.cmp) { }
85  inline bool operator () (const cursor_type& a, const cursor_type& b) const
86  {
87  if (UNLIKELY(b.empty()))
88  return true;
89  // sentinel emulation
90  if (UNLIKELY(a.empty()))
91  return false;
92  // sentinel emulation
93 
94  return (cmp(a.current(), b.current()));
95  }
96 };
97 
98 // this function is used by parallel mergers
99 template <typename SequenceVector, typename ValueType, typename Comparator>
100 inline unsigned_type
101 count_elements_less_equal(const SequenceVector& seqs,
102  const ValueType& bound, Comparator cmp)
103 {
104  typedef typename SequenceVector::size_type seqs_size_type;
105  typedef typename SequenceVector::value_type::first_type iterator;
106  unsigned_type count = 0;
107 
108  for (seqs_size_type i = 0; i < seqs.size(); ++i)
109  {
110  iterator position = std::upper_bound(seqs[i].first, seqs[i].second, bound, cmp);
111  STXXL_VERBOSE1("less equal than " << position - seqs[i].first);
112  count += position - seqs[i].first;
113  }
114  STXXL_VERBOSE1("finished loop");
115  return count;
116 }
117 
118 // this function is used by parallel mergers
119 template <typename SequenceVector, typename BufferPtrVector, typename Prefetcher>
120 inline void
121 refill_or_remove_empty_sequences(SequenceVector& seqs,
122  BufferPtrVector& buffers,
123  Prefetcher& prefetcher)
124 {
125  typedef typename SequenceVector::size_type seqs_size_type;
126 
127  for (seqs_size_type i = 0; i < seqs.size(); ++i)
128  {
129  if (seqs[i].first == seqs[i].second) // run empty
130  {
131  if (prefetcher.block_consumed(buffers[i]))
132  {
133  seqs[i].first = buffers[i]->begin(); // reset iterator
134  seqs[i].second = buffers[i]->end();
135  STXXL_VERBOSE1("block ran empty " << i);
136  }
137  else
138  {
139  seqs.erase(seqs.begin() + i); // remove this sequence
140  buffers.erase(buffers.begin() + i);
141  STXXL_VERBOSE1("seq removed " << i);
142  --i; // don't skip the next sequence
143  }
144  }
145  }
146 }
147 
148 } // namespace sort_helper
149 
151 
152 #endif // !STXXL_ALGO_SORT_HELPER_HEADER
153 // vim: et:ts=4:sw=4
TriggerEntryType trigger_entry_type
Definition: sort_helper.h:56
#define STXXL_ASSERT(condition)
Definition: verbose.h:220
BlockType block_type
Definition: sort_helper.h:39
value_type value
Definition: sort_helper.h:44
block_type::bid_type bid_type
Definition: sort_helper.h:40
bid_type bid
Definition: sort_helper.h:43
ValueCmp cmp
Definition: sort_helper.h:57
ValueType value_type
Definition: sort_helper.h:41
unsigned_type count_elements_less_equal(const SequenceVector &seqs, const ValueType &bound, Comparator cmp)
Definition: sort_helper.h:101
void verify_sentinel_strict_weak_ordering(StrictWeakOrdering cmp)
Definition: sort_helper.h:28
bool empty() const
Definition: run_cursor.h:85
void refill_or_remove_empty_sequences(SequenceVector &seqs, BufferPtrVector &buffers, Prefetcher &prefetcher)
Definition: sort_helper.h:121
Definition: sort_helper.h:53
run_cursor2_cmp(const run_cursor2_cmp &a)
Definition: sort_helper.h:84
#define UNLIKELY(c)
Definition: utils.h:225
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
static void count(TypeKey *a, TypeKey *aEnd, int_type *bucket, int_type K, typename TypeKey::key_type offset, unsigned shift)
Definition: intksort.h:26
BlockType::const_reference current() const
Definition: run_cursor.h:30
trigger_entry_cmp(ValueCmp c)
Definition: sort_helper.h:58
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
trigger_entry_cmp(const trigger_entry_cmp &a)
Definition: sort_helper.h:59
Definition: sort_helper.h:37
run_cursor2< block_type, prefetcher_type > cursor_type
Definition: sort_helper.h:80
#define STXXL_END_NAMESPACE
Definition: namespace.h:17