pq_mergers.h File Reference

#include <stxxl/bits/containers/pq_helpers.h>

Go to the source code of this file.

Classes
class	stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >
	Loser tree from Knuth, "Sorting and Searching", Section 5.4.1. More...
struct	stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::Entry
	type of nodes in the loser tree More...

Namespaces
	stxxl
	STXXL library namespace
	stxxl::priority_queue_local

Macros
#define	Merge3Case(a, b, c)
#define	Merge4Case(a, b, c, d)
#define	StartMerge4(a, b, c, d)
#define	TreeStep(L)

Functions
template<class InputIterator , class OutputIterator , class CompareType >
void	stxxl::priority_queue_local::merge2_iterator (InputIterator &source0, InputIterator &source1, OutputIterator target, OutputIterator end, CompareType &cmp)
template<class InputIterator , class OutputIterator , class CompareType >
void	stxxl::priority_queue_local::merge3_iterator (InputIterator &source0, InputIterator &source1, InputIterator &source2, OutputIterator target, OutputIterator end, CompareType &cmp)
template<class InputIterator , class OutputIterator , class CompareType >
void	stxxl::priority_queue_local::merge4_iterator (InputIterator &source0, InputIterator &source1, InputIterator &source2, InputIterator &source3, OutputIterator target, OutputIterator end, CompareType &cmp)

Macro Definition Documentation

#define Merge3Case	(		a,
			b,
			c
	)

Value:

s ## a ## b ## c:                    \
    if (target == end)                   \
        return;                          \
    *target = *source ## a;              \
    ++target;                            \
    ++source ## a;                       \
    if (cmp(*source ## b, *source ## a)) \
        goto s ## a ## b ## c;           \
    if (cmp(*source ## c, *source ## a)) \
        goto s ## b ## a ## c;           \
    goto s ## b ## c ## a;

Referenced by stxxl::priority_queue_local::merge3_iterator().

#define Merge4Case	(		a,
			b,
			c,
			d
	)

Value:

s ## a ## b ## c ## d:                   \
    if (target == end)                       \
        return;                              \
    *target = *source ## a;                  \
    ++target;                                \
    ++source ## a;                           \
    if (cmp(*source ## c, *source ## a))     \
    {                                        \
        if (cmp(*source ## b, *source ## a)) \
            goto s ## a ## b ## c ## d;      \
        else                                 \
            goto s ## b ## a ## c ## d;      \
    }                                        \
    else                                     \
    {                                        \
        if (cmp(*source ## d, *source ## a)) \
            goto s ## b ## c ## a ## d;      \
        else                                 \
            goto s ## b ## c ## d ## a;      \
    }

Referenced by stxxl::priority_queue_local::merge4_iterator().

#define StartMerge4	(		a,
			b,
			c,
			d
	)

Value:

if ((!cmp(*source ## a, *source ## b)) && \
        (!cmp(*source ## b, *source ## c)) && \
        (!cmp(*source ## c, *source ## d)))   \
        goto s ## a ## b ## c ## d;

Referenced by stxxl::priority_queue_local::merge4_iterator().

#define TreeStep

(

L

)

Value:

if (1 << LogK >= 1 << L) {                                             \
        int pos_shift = ((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0; \
        Entry* pos = entry + ((winner_index + (1 << LogK)) >> pos_shift);  \
        value_type key = pos->key;                                         \
        if (cmp(winner_key, key)) {                                        \
            unsigned_type index = pos->index;                              \
            pos->key = winner_key;                                         \
            pos->index = winner_index;                                     \
            winner_key = key;                                              \
            winner_index = index;                                          \
        }                                                                  \
    }

Referenced by stxxl::priority_queue_local::loser_tree< self_type, CompareType, MaxArity >::multi_merge_f().