STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sorted_runs.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/stream/sorted_runs.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2005 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009, 2010 Andreas Beckmann <[email protected]>
8  * Copyright (C) 2013 Timo Bingmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_STREAM_SORTED_RUNS_HEADER
16 #define STXXL_STREAM_SORTED_RUNS_HEADER
17 
18 #include <vector>
23 
25 
26 namespace stream {
27 
28 //! \addtogroup streampack Stream Package
29 //! \{
30 
31 ////////////////////////////////////////////////////////////////////////
32 // SORTED RUNS //
33 ////////////////////////////////////////////////////////////////////////
34 
35 //! All sorted runs of a sort operation.
36 template <typename TriggerEntryType, typename CompareType>
37 struct sorted_runs : private noncopyable, public counted_object
38 {
39  typedef TriggerEntryType trigger_entry_type;
40  typedef typename trigger_entry_type::block_type block_type;
41  //! may differ from trigger_entry_type::value_type
42  typedef typename block_type::value_type value_type;
43  typedef std::vector<trigger_entry_type> run_type;
44  typedef std::vector<value_type> small_run_type;
46  typedef typename std::vector<run_type>::size_type run_index_type;
47 
48  typedef CompareType cmp_type;
49 
50  //! total number of elements in all runs
52 
53  //! vector of runs (containing vectors of block ids)
54  std::vector<run_type> runs;
55 
56  //! vector of the number of elements in each individual run
57  std::vector<size_type> runs_sizes;
58 
59  //! Small sort optimization:
60  // if the input is small such that its total size is at most B
61  // (block_type::size) then input is sorted internally and kept in the
62  // array "small_run"
64 
65 public:
67  : elements(0)
68  { }
69 
71  {
72  deallocate_blocks();
73  }
74 
75  //! Clear the internal state of the object: release all runs and reset.
76  void clear()
77  {
78  deallocate_blocks();
79 
80  elements = 0;
81  runs.clear();
82  runs_sizes.clear();
83  small_run.clear();
84  }
85 
86  //! Add a new run with given number of elements
87  void add_run(const run_type& run, size_type run_size)
88  {
89  runs.push_back(run);
90  runs_sizes.push_back(run_size);
91  elements += run_size;
92  }
93 
94  //! Swap contents with another object. This is used by the recursive
95  //! merger to swap in a sorted_runs object with fewer runs.
96  void swap(sorted_runs& b)
97  {
98  std::swap(elements, b.elements);
99  std::swap(runs, b.runs);
100  std::swap(runs_sizes, b.runs_sizes);
101  std::swap(small_run, b.small_run);
102  }
103 
104 private:
105  //! Deallocates the blocks which the runs occupy.
106  //!
107  //! \remark There is no need in calling this method, the blocks are
108  //! deallocated by the destructor. However, if you wish to reuse the
109  //! object, then this function can be used to clear its state.
111  {
112  block_manager* bm = block_manager::get_instance();
113  for (unsigned_type i = 0; i < runs.size(); ++i)
114  {
115  bm->delete_blocks(make_bid_iterator(runs[i].begin()),
116  make_bid_iterator(runs[i].end()));
117  }
118  }
119 };
120 
121 //! \}
122 
123 } // namespace stream
124 
126 
127 #endif // !STXXL_STREAM_SORTED_RUNS_HEADER
128 // vim: et:ts=4:sw=4
void swap(sorted_runs &b)
Swap contents with another object. This is used by the recursive merger to swap in a sorted_runs obje...
Definition: sorted_runs.h:96
Block manager class.
Definition: block_manager.h:61
trigger_entry_iterator< Iterator > make_bid_iterator(Iterator iter)
Definition: adaptor.h:239
All sorted runs of a sort operation.
Definition: sorted_runs.h:37
std::vector< run_type > runs
vector of runs (containing vectors of block ids)
Definition: sorted_runs.h:54
void deallocate_blocks()
Deallocates the blocks which the runs occupy.
Definition: sorted_runs.h:110
small_run_type small_run
Small sort optimization:
Definition: sorted_runs.h:63
stxxl::external_size_type size_type
Definition: sorted_runs.h:45
void delete_blocks(const BIDIteratorClass &bidbegin, const BIDIteratorClass &bidend)
Deallocates blocks.
void clear()
Clear the internal state of the object: release all runs and reset.
Definition: sorted_runs.h:76
Provides reference counting abilities for use with counting_ptr.
Definition: counting_ptr.h:329
trigger_entry_type::block_type block_type
Definition: sorted_runs.h:40
std::vector< size_type > runs_sizes
vector of the number of elements in each individual run
Definition: sorted_runs.h:57
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
std::vector< run_type >::size_type run_index_type
Definition: sorted_runs.h:46
void add_run(const run_type &run, size_type run_size)
Add a new run with given number of elements.
Definition: sorted_runs.h:87
block_type::value_type value_type
may differ from trigger_entry_type::value_type
Definition: sorted_runs.h:42
std::vector< value_type > small_run_type
Definition: sorted_runs.h:44
uint64 external_size_type
Definition: types.h:67
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
TriggerEntryType trigger_entry_type
Definition: sorted_runs.h:39
std::vector< trigger_entry_type > run_type
Definition: sorted_runs.h:43
size_type elements
total number of elements in all runs
Definition: sorted_runs.h:51
#define STXXL_END_NAMESPACE
Definition: namespace.h:17