sorted_runs.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/stream/sorted_runs.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2002-2005 Roman Dementiev <[email protected]>
 * Copyright (C) 2009, 2010 Andreas Beckmann <[email protected]>
 * Copyright (C) 2013 Timo Bingmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_STREAM_SORTED_RUNS_HEADER
#define STXXL_STREAM_SORTED_RUNS_HEADER

#include <vector>
#include <stxxl/bits/mng/block_manager.h>
#include <stxxl/bits/mng/typed_block.h>
#include <stxxl/bits/algo/adaptor.h>
#include <stxxl/bits/common/counting_ptr.h>


STXXL_BEGIN_NAMESPACE

namespace stream {

//! \addtogroup streampack Stream Package
//! \{


////////////////////////////////////////////////////////////////////////
// SORTED RUNS //
////////////////////////////////////////////////////////////////////////

//! All sorted runs of a sort operation.
template <typename TriggerEntryType, typename CompareType>
struct sorted_runs : private noncopyable, public counted_object
{
 typedef TriggerEntryType trigger_entry_type;
 typedef typename trigger_entry_type::block_type block_type;
 typedef typename block_type::value_type value_type; // may differ from trigger_entry_type::value_type
 typedef std::vector<trigger_entry_type> run_type;
 typedef std::vector<value_type> small_run_type;
 typedef stxxl::external_size_type size_type;
 typedef typename std::vector<run_type>::size_type run_index_type;

 typedef CompareType cmp_type;

 //! total number of elements in all runs
 size_type elements;

 //! vector of runs (containing vectors of block ids)
 std::vector<run_type> runs;

 //! vector of the number of elements in each individual run
 std::vector<size_type> runs_sizes;

 //! Small sort optimization:
 // if the input is small such that its total size is at most B
 // (block_type::size) then input is sorted internally and kept in the
 // array "small_run"
 small_run_type small_run;

public:
 sorted_runs()
 : elements(0)
 { }

 ~sorted_runs()
 {
 deallocate_blocks();
 }

 //! Clear the internal state of the object: release all runs and reset.
 void clear()
 {
 deallocate_blocks();

 elements = 0;
 runs.clear();
 runs_sizes.clear();
 small_run.clear();
 }

 //! Add a new run with given number of elements
 void add_run(const run_type& run, size_type run_size)
 {
 runs.push_back(run);
 runs_sizes.push_back(run_size);
 elements += run_size;
 }

 //! Swap contents with another object. This is used by the recursive
 //! merger to swap in a sorted_runs object with fewer runs.
 void swap(sorted_runs& b)
 {
 std::swap(elements, b.elements);
 std::swap(runs, b.runs);
 std::swap(runs_sizes, b.runs_sizes);
 std::swap(small_run, b.small_run);
 }

private:
 //! Deallocates the blocks which the runs occupy.
 //!
 //! \remark There is no need in calling this method, the blocks are
 //! deallocated by the destructor. However, if you wish to reuse the
 //! object, then this function can be used to clear its state.
 void deallocate_blocks()
 {
 block_manager* bm = block_manager::get_instance();
 for (unsigned_type i = 0; i < runs.size(); ++i)
 {
 bm->delete_blocks(make_bid_iterator(runs[i].begin()),
 make_bid_iterator(runs[i].end()));
 }
 }
};


//! \}

} // namespace stream

STXXL_END_NAMESPACE

#endif // !STXXL_STREAM_SORTED_RUNS_HEADER
// vim: et:ts=4:sw=4