sort_helper.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/algo/sort_helper.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2002-2003 Roman Dementiev <[email protected]>
 * Copyright (C) 2009, 2010 Andreas Beckmann <[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_ALGO_SORT_HELPER_HEADER
#define STXXL_ALGO_SORT_HELPER_HEADER

#include <algorithm>
#include <functional>
#include <stxxl/bits/algo/run_cursor.h>
#include <stxxl/bits/verbose.h>


STXXL_BEGIN_NAMESPACE

//! \internal
namespace sort_helper {

template <typename StrictWeakOrdering>
inline void verify_sentinel_strict_weak_ordering(StrictWeakOrdering cmp)
{
 assert(!cmp(cmp.min_value(), cmp.min_value()));
 assert(cmp(cmp.min_value(), cmp.max_value()));
 assert(!cmp(cmp.max_value(), cmp.min_value()));
 assert(!cmp(cmp.max_value(), cmp.max_value()));
 STXXL_UNUSED(cmp);
}

template <typename BlockTp_, typename ValTp_ = typename BlockTp_::value_type>
struct trigger_entry
{
 typedef BlockTp_ block_type;
 typedef typename block_type::bid_type bid_type;
 typedef ValTp_ value_type;

 bid_type bid;
 value_type value;

 operator bid_type ()
 {
 return bid;
 }
};

template <typename TriggerEntryTp_, typename ValueCmp_>
struct trigger_entry_cmp : public std::binary_function<TriggerEntryTp_, TriggerEntryTp_, bool>
{
 typedef TriggerEntryTp_ trigger_entry_type;
 ValueCmp_ cmp;
 trigger_entry_cmp(ValueCmp_ c) : cmp(c) { }
 trigger_entry_cmp(const trigger_entry_cmp& a) : cmp(a.cmp) { }
 bool operator () (const trigger_entry_type& a, const trigger_entry_type& b) const
 {
 return cmp(a.value, b.value);
 }
};

template <typename block_type,
 typename prefetcher_type,
 typename value_cmp>
struct run_cursor2_cmp : public std::binary_function<run_cursor2<block_type, prefetcher_type>, run_cursor2<block_type, prefetcher_type>, bool>
{
 typedef run_cursor2<block_type, prefetcher_type> cursor_type;
 value_cmp cmp;

 run_cursor2_cmp(value_cmp c) : cmp(c) { }
 run_cursor2_cmp(const run_cursor2_cmp& a) : cmp(a.cmp) { }
 inline bool operator () (const cursor_type& a, const cursor_type& b) const
 {
 if (UNLIKELY(b.empty()))
 return true;
 // sentinel emulation
 if (UNLIKELY(a.empty()))
 return false;
 // sentinel emulation

 return (cmp(a.current(), b.current()));
 }
};

// this function is used by parallel mergers
template <typename SequenceVector, typename ValueType, typename Comparator>
inline
unsigned_type count_elements_less_equal(const SequenceVector& seqs, const ValueType& bound, Comparator cmp)
{
 typedef typename SequenceVector::size_type seqs_size_type;
 typedef typename SequenceVector::value_type::first_type iterator;
 unsigned_type count = 0;

 for (seqs_size_type i = 0; i < seqs.size(); ++i)
 {
 iterator position = std::upper_bound(seqs[i].first, seqs[i].second, bound, cmp);
 STXXL_VERBOSE1("less equal than " << position - seqs[i].first);
 count += position - seqs[i].first;
 }
 STXXL_VERBOSE1("finished loop");
 return count;
}

// this function is used by parallel mergers
template <typename SequenceVector, typename BufferPtrVector, typename Prefetcher>
inline
void refill_or_remove_empty_sequences(SequenceVector& seqs,
 BufferPtrVector& buffers,
 Prefetcher& prefetcher)
{
 typedef typename SequenceVector::size_type seqs_size_type;

 for (seqs_size_type i = 0; i < seqs.size(); ++i)
 {
 if (seqs[i].first == seqs[i].second) // run empty
 {
 if (prefetcher.block_consumed(buffers[i]))
 {
 seqs[i].first = buffers[i]->begin(); // reset iterator
 seqs[i].second = buffers[i]->end();
 STXXL_VERBOSE1("block ran empty " << i);
 }
 else
 {
 seqs.erase(seqs.begin() + i); // remove this sequence
 buffers.erase(buffers.begin() + i);
 STXXL_VERBOSE1("seq removed " << i);
 --i; // don't skip the next sequence
 }
 }
 }
}

} // namespace sort_helper

STXXL_END_NAMESPACE

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