STXXL
1.4.1
|
Loser tree from Knuth, "Sorting and Searching", Section 5.4.1.
MaxArity | maximum arity of loser tree, has to be a power of two |
Definition at line 38 of file pq_losertree.h.
Public Types | |
enum | { max_arity = MaxArity } |
typedef CompareType | comparator_type |
typedef value_type | Element |
typedef ValueType | value_type |
Public Member Functions | |
loser_tree () | |
~loser_tree () | |
void | init () |
void | insert_segment (Element *target, unsigned_type length) |
insert segment beginning at target More... | |
bool | is_sentinel (const Element &a) |
bool | is_space_available () const |
unsigned_type | mem_cons () const |
void | multi_merge (Element *begin, Element *end) |
void | multi_merge (Element *, unsigned_type length) |
bool | not_sentinel (const Element &a) |
unsigned_type | size () const |
void | swap (loser_tree &obj) |
Private Member Functions | |
void | compactTree () |
void | deallocate_segment (unsigned_type slot) |
void | doubleK () |
unsigned_type | initWinner (unsigned_type root) |
bool | is_segment_empty (unsigned_type slot) |
void | multi_merge_k (Element *target, unsigned_type length) |
void | rebuildLoserTree () |
void | update_on_insert (unsigned_type node, const Element &newKey, unsigned_type newIndex, Element *winnerKey, unsigned_type *winnerIndex, unsigned_type *mask) |
Private Member Functions inherited from stxxl::noncopyable | |
noncopyable () | |
Private Attributes | |
comparator_type | cmp |
Element * | current [MaxArity] |
Element * | current_end [MaxArity] |
internal_bounded_stack < unsigned_type, MaxArity > | free_slots |
unsigned_type | k |
unsigned_type | logK |
unsigned_type | mem_cons_ |
Element * | segment [MaxArity] |
unsigned_type | segment_size [MaxArity] |
Element | sentinel |
unsigned_type | size_ |
typedef CompareType stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::comparator_type |
Definition at line 42 of file pq_losertree.h.
typedef value_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::Element |
Definition at line 43 of file pq_losertree.h.
typedef ValueType stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::value_type |
Definition at line 41 of file pq_losertree.h.
anonymous enum |
Enumerator | |
---|---|
max_arity |
Definition at line 44 of file pq_losertree.h.
stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree | ( | ) |
Definition at line 211 of file pq_losertree.h.
References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::current, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::current_end, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::free_slots, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::init(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::push(), stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::segment, and stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::sentinel.
stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::~loser_tree | ( | ) |
Definition at line 461 of file pq_losertree.h.
References STXXL_VERBOSE1, and STXXL_VERBOSE2.
|
private |
Definition at line 359 of file pq_losertree.h.
References STXXL_VERBOSE3.
|
private |
Definition at line 480 of file pq_losertree.h.
References STXXL_VERBOSE2.
|
private |
Definition at line 329 of file pq_losertree.h.
References STXXL_VERBOSE3.
void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::init | ( | ) |
Definition at line 224 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree().
|
private |
void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::insert_segment | ( | Element * | target, |
unsigned_type | length | ||
) |
insert segment beginning at target
Definition at line 416 of file pq_losertree.h.
References STXXL_VERBOSE2.
|
inlineprivate |
Definition at line 681 of file pq_losertree.h.
|
inline |
Definition at line 158 of file pq_losertree.h.
|
inline |
Definition at line 198 of file pq_losertree.h.
|
inline |
Definition at line 196 of file pq_losertree.h.
|
inline |
Definition at line 190 of file pq_losertree.h.
void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::multi_merge | ( | Element * | target, |
unsigned_type | length | ||
) |
Definition at line 505 of file pq_losertree.h.
References stxxl::priority_queue_local::merge3_iterator(), stxxl::priority_queue_local::merge4_iterator(), stxxl::priority_queue_local::merge_iterator(), and STXXL_VERBOSE3.
|
private |
|
inline |
Definition at line 162 of file pq_losertree.h.
|
private |
Definition at line 236 of file pq_losertree.h.
|
inline |
Definition at line 206 of file pq_losertree.h.
|
inline |
Definition at line 172 of file pq_losertree.h.
|
private |
|
private |
Definition at line 55 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 74 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 75 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 57 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 61 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 60 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 79 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 76 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 77 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 63 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().
|
private |
Definition at line 59 of file pq_losertree.h.
Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().