STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pq_mergers.h File Reference

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,
 
)
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,
 
)
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,
 
)
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; \
} \
}
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64

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