16 #ifndef STXXL_CONTAINERS_PQ_INT_MERGER_HEADER
17 #define STXXL_CONTAINERS_PQ_INT_MERGER_HEADER
29 namespace priority_queue_local {
31 template <
class ValueType,
class CompareType,
unsigned MaxArity>
40 enum { max_arity = MaxArity };
45 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
47 typedef parallel_merger_adapter<self_type, CompareType, MaxArity>
tree_type;
90 return tree.is_sentinel(*(current[slot]));
103 return current[slot];
109 std::swap(current[a], current[b]);
110 std::swap(current_end[a], current_end[b]);
111 std::swap(segment[a], segment[b]);
112 std::swap(segment_size[a], segment_size[b]);
120 segment[slot] = NULL;
129 slot <<
" address: " << segment[slot] <<
" size: " << (segment_size[slot] /
sizeof(
value_type)) - 1);
134 delete[] segment[slot];
135 segment[slot] = NULL;
136 mem_cons_ -= segment_size[slot];
139 tree.free_player(slot);
150 int_merger(
const compare_type& c = compare_type())
172 STXXL_VERBOSE2(
"int_merger::~int_merger() deleting segment " << i);
174 mem_cons_ -= segment_size[i];
178 assert(mem_cons_ == 0);
196 return tree.is_space_available();
202 return tree.is_sentinel(a);
209 STXXL_VERBOSE2(
"int_merger::insert_segment(" << target <<
"," << length <<
")");
220 assert(!tree.is_sentinel(target[0]));
221 assert(!tree.is_sentinel(target[length - 1]));
222 assert(tree.is_sentinel(target[length]));
227 assert(current[index] == &
sentinel);
230 current[index] = segment[index] = target;
231 current_end[index] = target + length;
232 segment_size[index] = (length + 1) *
sizeof(
value_type);
233 mem_cons_ += (length + 1) *
sizeof(
value_type);
237 tree.update_on_insert((index + tree.k) >> 1, *target, index);
251 assert(begin + m_size >= end);
253 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
254 multi_merge_parallel(begin, end - begin);
256 tree.multi_merge(begin, end);
259 m_size -= end - begin;
262 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
267 void multi_merge_parallel(value_type* target,
unsigned_type length)
271 compare_type& cmp = tree.cmp;
273 STXXL_VERBOSE3(
"int_merger::multi_merge_parallel(target=" << target <<
", len=" << length <<
") k=" << k);
287 memcpy(target, current[0], length *
sizeof(value_type));
288 current[0] += length;
290 if (is_array_empty(0) && is_array_allocated(0))
298 std::pair<value_type*, value_type*> seqs[2] =
300 std::make_pair(current[0], current_end[0]),
301 std::make_pair(current[1], current_end[1])
305 seqs, seqs + 2, target, length, inv_cmp);
307 current[0] = seqs[0].first;
308 current[1] = seqs[1].first;
310 if (is_array_empty(0) && is_array_allocated(0))
313 if (is_array_empty(1) && is_array_allocated(1))
321 std::pair<value_type*, value_type*> seqs[4] =
323 std::make_pair(current[0], current_end[0]),
324 std::make_pair(current[1], current_end[1]),
325 std::make_pair(current[2], current_end[2]),
326 std::make_pair(current[3], current_end[3])
330 seqs, seqs + 4, target, length, inv_cmp);
332 current[0] = seqs[0].first;
333 current[1] = seqs[1].first;
334 current[2] = seqs[2].first;
335 current[3] = seqs[3].first;
337 if (is_array_empty(0) && is_array_allocated(0))
340 if (is_array_empty(1) && is_array_allocated(1))
343 if (is_array_empty(2) && is_array_allocated(2))
346 if (is_array_empty(3) && is_array_allocated(3))
352 std::vector<std::pair<value_type*, value_type*> > seqs;
353 std::vector<int_type> orig_seq_index;
354 for (
unsigned int i = 0; i < k; ++i)
356 if (current[i] != current_end[i] && !is_sentinel(*current[i]))
358 seqs.push_back(std::make_pair(current[i], current_end[i]));
359 orig_seq_index.push_back(i);
364 seqs.begin(), seqs.end(), target, length, inv_cmp);
366 for (
unsigned int i = 0; i < seqs.size(); ++i)
369 current[seg] = seqs[i].first;
372 for (
unsigned int i = 0; i < k; ++i)
374 if (is_array_empty(i) && is_array_allocated(i))
384 tree.maybe_compact();
386 #endif // STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
395 #endif // !STXXL_CONTAINERS_PQ_INT_MERGER_HEADER
unsigned_type mem_cons() const
bool is_array_allocated(unsigned_type slot) const
is this array's backing memory still allocated or does the current point to sentinel?
size_type m_size
total number of elements stored
void prefetch_arrays()
Hint (prefetch) first non-internal (actually second) block of each sequence. No-operation for interna...
void append_array(value_type *target, unsigned_type length)
append array to merger, takes ownership of the array. requires: is_space_available() == 1 ...
Inverts the order of a comparison functor by swapping its arguments.
loser_tree< self_type, CompareType, MaxArity > tree_type
type of embedded loser tree
bool is_sentinel(const value_type &a) const
True if a is the sentinel value.
bool is_array_empty(unsigned_type slot) const
is this array invalid? here: empty and prefixed with sentinel?
void swap_1D_arrays(Type *a, Type *b, unsigned_type size)
tree_type tree
loser tree instance
#define STXXL_VERBOSE2(x)
void multi_merge(value_type *begin, value_type *end)
extract the (length = end - begin) smallest elements and write them to [begin..end) empty segments ar...
void swap_arrays(unsigned_type a, unsigned_type b)
Swap contents of arrays a and b.
size_type size() const
Return the number of items in the arrays.
value_type * segment[MaxArity]
start of Segments
unsigned_type segment_size[MaxArity]
just to count the internal memory consumption, in bytes
value_type * sequence_type
type of sequences in which the values are stored: memory arrays
void make_array_sentinel(unsigned_type slot)
Set a usually empty array to the sentinel.
value_type * current_end[MaxArity]
pointer to end of block for current element
RandomAccessIterator3 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
Multi-way merging front-end.
#define STXXL_VERBOSE3(x)
choose_int_types< my_pointer_size >::int_type int_type
unsigned_type internal_size_type
#define STXXL_BEGIN_NAMESPACE
#define STXXL_VERBOSE1(x)
value_type * current[MaxArity]
pointer to current element
void swap(int_merger &obj)
bool is_space_available() const
Whether there is still space for new array.
void free_array(unsigned_type slot)
free an empty segment .
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
CompareType compare_type
comparator object type
static const size_t sentinel
value_type sentinel
target of free segment pointers
ValueType value_type
type of values in merger
int_merger< ValueType, CompareType, MaxArity > self_type
our type
sequence_type & get_array(unsigned_type slot)
Return the item sequence of the given slot.
#define STXXL_END_NAMESPACE
internal_size_type size_type
size type of total number of item in merger