STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pq_ext_merger.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/pq_ext_merger.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 1999 Peter Sanders <[email protected]>
7  * Copyright (C) 2003, 2004, 2007 Roman Dementiev <[email protected]>
8  * Copyright (C) 2007-2009 Johannes Singler <[email protected]>
9  * Copyright (C) 2007-2010 Andreas Beckmann <[email protected]>
10  *
11  * Distributed under the Boost Software License, Version 1.0.
12  * (See accompanying file LICENSE_1_0.txt or copy at
13  * http://www.boost.org/LICENSE_1_0.txt)
14  **************************************************************************/
15 
16 #ifndef STXXL_CONTAINERS_PQ_EXT_MERGER_HEADER
17 #define STXXL_CONTAINERS_PQ_EXT_MERGER_HEADER
18 
20 #include <deque>
21 
23 
24 //! \addtogroup stlcontinternals
25 //!
26 //! \{
27 
28 /*! \internal
29  */
30 namespace priority_queue_local {
31 
32 /*!
33  * External merger, based on the loser tree data structure.
34  * \param Arity maximum arity of merger, does not need to be a power of 2
35  */
36 template <class BlockType, class CompareType, unsigned Arity,
37  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
38 class ext_merger : private noncopyable
39 {
40 public:
41  //! class is parameterized by the block of the external arrays
42  typedef BlockType block_type;
43  typedef CompareType compare_type;
44 
45  // max_arity / 2 < arity <= max_arity
46  enum { arity = Arity, max_arity = 1UL << (LOG2<Arity>::ceil) };
47 
48  typedef AllocStr alloc_strategy;
49 
50  typedef typename block_type::bid_type bid_type;
51  typedef typename block_type::value_type value_type;
52 
53  typedef typename std::deque<bid_type> bid_container_type;
54 
56 
57  //! our type
59 
60 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
61  //! type of embedded adapter to parallel multiway_merge
62  typedef parallel_merger_adapter<self_type, CompareType, Arity> tree_type;
63 #else
64  //! type of embedded loser tree
66 #endif
67 
68  //! size type of total number of item in merger
70 
71 public:
72  struct sequence_state : private noncopyable
73  {
74  block_type* block; //!< current block
75  unsigned_type current; //!< current index in current block
76  bid_container_type bids; //!< list of blocks forming this sequence
79  bool allocated;
80 
81  //! \returns current element
82  const value_type& operator * () const
83  {
84  return (*block)[current];
85  }
86 
88  : block(NULL), current(0),
89  merger(NULL),
90  allocated(false)
91  { }
92 
94  {
95  STXXL_VERBOSE2("ext_merger sequence_state::~sequence_state()");
96 
97  block_manager* bm = block_manager::get_instance();
98  bm->delete_blocks(bids.begin(), bids.end());
99  }
100 
101  void make_inf()
102  {
103  current = 0;
104  (*block)[0] = cmp.min_value();
105  }
106 
107  bool is_sentinel(const value_type& a) const
108  {
109  return !(cmp(cmp.min_value(), a));
110  }
111 
112  bool not_sentinel(const value_type& a) const
113  {
114  return cmp(cmp.min_value(), a);
115  }
116 
117  void swap(sequence_state& obj)
118  {
119  if (&obj != this)
120  {
121  std::swap(current, obj.current);
122  std::swap(block, obj.block);
123  std::swap(bids, obj.bids);
124  assert(merger == obj.merger);
125  std::swap(allocated, obj.allocated);
126  }
127  }
128 
130  {
131  assert(not_sentinel((*block)[current]));
132  assert(current < block->size);
133 
134  ++current;
135 
136  if (current == block->size)
137  {
138  STXXL_VERBOSE2("ext_merger sequence_state operator++ crossing block border ");
139  // go to the next block
140  if (bids.empty()) // if there is no next block
141  {
142  STXXL_VERBOSE2("ext_merger sequence_state operator++ it was the last block in the sequence ");
143  // swap memory area and delete other object.
144  bid_container_type to_delete;
145  std::swap(to_delete, bids);
146  make_inf();
147  }
148  else
149  {
150  STXXL_VERBOSE2("ext_merger sequence_state operator++ there is another block ");
151  bid_type bid = bids.front();
152  bids.pop_front();
153  merger->pool->hint(bid);
154  if (!(bids.empty()))
155  {
156  STXXL_VERBOSE2("ext_merger sequence_state operator++ more blocks exist in a sequence, hinting the next");
157  merger->pool->hint(bids.front());
158  }
159  merger->pool->read(block, bid)->wait();
160  STXXL_VERBOSE2("first element of read block " << bid << " " << *(block->begin()) << " cached in " << block);
161  if (!(bids.empty()))
162  merger->pool->hint(bids.front()); // re-hint, reading might have made a block free
163  block_manager::get_instance()->delete_block(bid);
164  current = 0;
165  }
166  }
167  return *this;
168  }
169  };
170 
171  //! type of sequences in which the values are stored: external arrays
173 
174 protected:
175  //! loser tree instance
176  tree_type tree;
177 
178  //! sequence including current position, dereference gives current element
179  sequence_state states[max_arity];
180 
181  //! read and writer block pool
182  pool_type* pool;
183 
184  //! a memory block filled with sentinel values
186 
187  //! total number of elements stored
188  size_type m_size;
189 
190 public:
191  ext_merger(const compare_type& c = compare_type()) // TODO: pass pool as parameter
192  : tree(c, *this),
193  pool(NULL),
194  m_size(0)
195  {
196  init();
197 
198  tree.initialize();
199  }
200 
201  virtual ~ext_merger()
202  {
203  STXXL_VERBOSE1("ext_merger::~ext_merger()");
204  for (unsigned_type i = 0; i < arity; ++i)
205  {
206  delete states[i].block;
207  }
208  delete sentinel_block;
209  }
210 
211  void set_pool(pool_type* pool_)
212  {
213  pool = pool_;
214  }
215 
216 public:
217  //! \name Interface for loser_tree
218  //! \{
219 
220  //! is this segment empty ?
221  bool is_array_empty(unsigned_type slot) const
222  {
223  return is_sentinel(*(states[slot]));
224  }
225 
226  //! Is this segment allocated? Otherwise it's empty, already on the stack
227  //! of free segment indices and can be reused.
229  {
230  return states[slot].allocated;
231  }
232 
233  //! Return the item sequence of the given slot
234  sequence_type & get_array(unsigned_type slot)
235  {
236  return states[slot];
237  }
238 
239  //! Swap contents of arrays a and b
241  {
242  states[a].swap(states[b]);
243  }
244 
245  //! Set a usually empty array to the sentinel
247  {
248  states[a].make_inf();
249  }
250 
251  //! free an empty segment.
253  {
254  STXXL_VERBOSE1("ext_merger::free_array() deleting array " << slot << " allocated=" << int(is_array_allocated(slot)));
255  assert(is_array_allocated(slot));
256  states[slot].allocated = false;
257  states[slot].make_inf();
258 
259  // free player in loser tree
260  tree.free_player(slot);
261  }
262 
263  //! Hint (prefetch) first non-internal (actually second) block of each
264  //! sequence.
266  {
267  for (unsigned_type i = 0; i < tree.k; ++i)
268  {
269  if (!states[i].bids.empty())
270  pool->hint(states[i].bids.front());
271  }
272  }
273 
274  //! \}
275 
276 protected:
277  void init()
278  {
279  STXXL_VERBOSE2("ext_merger::init()");
280 
281  sentinel_block = NULL;
282  if (arity < max_arity)
283  {
284  sentinel_block = new block_type;
285  for (unsigned_type i = 0; i < block_type::size; ++i)
286  (*sentinel_block)[i] = tree.cmp.min_value();
287  if (arity + 1 == max_arity) {
288  // same memory consumption, but smaller merge width, better use arity = max_arity
289  STXXL_ERRMSG("inefficient PQ parameters for ext_merger: arity + 1 == max_arity");
290  }
291  }
292 
293  for (unsigned_type i = 0; i < max_arity; ++i)
294  {
295  states[i].merger = this;
296  if (i < arity)
297  states[i].block = new block_type;
298  else
299  states[i].block = sentinel_block;
300 
301  states[i].make_inf();
302  }
303  }
304 
305 #if 0
306  void swap(ext_merger& obj)
307  {
308  std::swap(cmp, obj.cmp);
309  std::swap(k, obj.k);
310  std::swap(logK, obj.logK);
311  std::swap(m_size, obj.m_size);
312  swap_1D_arrays(states, obj.states, max_arity);
313 
314  // std::swap(pool,obj.pool);
315  }
316 #endif
317 
318 public:
319  unsigned_type mem_cons() const // only rough estimation
320  {
321  return (STXXL_MIN<unsigned_type>(arity + 1, max_arity) * block_type::raw_size);
322  }
323 
324  //! Whether there is still space for new array
325  bool is_space_available() const
326  {
327  return tree.is_space_available();
328  }
329 
330  //! True if a is the sentinel value
331  bool is_sentinel(const value_type& a) const
332  {
333  return tree.is_sentinel(a);
334  }
335 
336  //! Return the number of items in the arrays
337  size_type size() const
338  {
339  return m_size;
340  }
341 
342  /*!
343  \param bidlist list of blocks to insert
344  \param first_block the first block of the sequence, before bidlist
345  \param first_size number of elements in the first block
346  \param slot slot to insert into
347  */
348  void insert_segment(bid_container_type& bidlist, block_type* first_block,
349  unsigned_type first_size, unsigned_type slot)
350  {
351  STXXL_VERBOSE1("ext_merger::insert_segment(bidlist,...) " << this << " " << bidlist.size() << " " << slot);
352  assert(!is_array_allocated(slot));
353  assert(first_size > 0);
354 
355  sequence_state& new_sequence = states[slot];
356  new_sequence.current = block_type::size - first_size;
357  std::swap(new_sequence.block, first_block);
358  delete first_block;
359  std::swap(new_sequence.bids, bidlist);
360  new_sequence.allocated = true;
361  assert(is_array_allocated(slot));
362  }
363 
364  //! Merge all items from another merger and insert the resulting external
365  //! array into the merger. Requires: is_space_available() == 1
366  template <class Merger>
367  void append_merger(Merger& another_merger, size_type segment_size)
368  {
369  STXXL_VERBOSE1("ext_merger::append_merger(merger,...)" << this);
370 
371  if (segment_size == 0)
372  {
373  // deallocate memory ?
374  STXXL_VERBOSE1("Merged segment with zero size.");
375  return;
376  }
377 
378  // allocate a new player slot
379  unsigned_type index = tree.new_player();
380 
381  // construct new sorted array from merger
382  assert(segment_size);
383  unsigned_type nblocks = (unsigned_type)(segment_size / block_type::size);
384  //assert(nblocks); // at least one block
385  STXXL_VERBOSE1("ext_merger::insert_segment nblocks=" << nblocks);
386  if (nblocks == 0)
387  {
388  STXXL_VERBOSE1("ext_merger::insert_segment(merger,...) WARNING: inserting a segment with " <<
389  nblocks << " blocks");
390  STXXL_VERBOSE1("THIS IS INEFFICIENT: TRY TO CHANGE PRIORITY QUEUE PARAMETERS");
391  }
392  unsigned_type first_size = (unsigned_type)(segment_size % block_type::size);
393  if (first_size == 0)
394  {
395  first_size = block_type::size;
396  --nblocks;
397  }
398 
399  // allocate blocks
400  block_manager* bm = block_manager::get_instance();
401  bid_container_type bids(nblocks);
402  bm->new_blocks(alloc_strategy(), bids.begin(), bids.end());
403  block_type* first_block = new block_type;
404 
405  another_merger.multi_merge(
406  first_block->begin() + (block_type::size - first_size),
407  first_block->end());
408 
409  STXXL_VERBOSE1("last element of first block " << *(first_block->end() - 1));
410  assert(!tree.cmp(*(first_block->begin() + (block_type::size - first_size)), *(first_block->end() - 1)));
411 
412  assert(pool->size_write() > 0);
413 
414  for (typename bid_container_type::iterator curbid = bids.begin(); curbid != bids.end(); ++curbid)
415  {
416  block_type* b = pool->steal();
417  another_merger.multi_merge(b->begin(), b->end());
418  STXXL_VERBOSE1("first element of following block " << *curbid << " " << *(b->begin()));
419  STXXL_VERBOSE1("last element of following block " << *curbid << " " << *(b->end() - 1));
420  assert(!tree.cmp(*(b->begin()), *(b->end() - 1)));
421  pool->write(b, *curbid);
422  STXXL_VERBOSE1("written to block " << *curbid << " cached in " << b);
423  }
424 
425  insert_segment(bids, first_block, first_size, index);
426 
427  m_size += segment_size;
428 
429  // propagate new information up the tree
430  tree.update_on_insert((index + tree.k) >> 1, *(states[index]), index);
431  }
432 
433  // delete the (length = end-begin) smallest elements and write them to [begin..end)
434  // empty segments are deallocated
435  // requires:
436  // - there are at least length elements
437  // - segments are ended by sentinels
438  template <class OutputIterator>
439  void multi_merge(OutputIterator begin, OutputIterator end)
440  {
441  assert((size_type)(end - begin) <= m_size);
442 
443 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
444  multi_merge_parallel(begin, end);
445 #else // STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
446  tree.multi_merge(begin, end);
447  m_size -= end - begin;
448 #endif
449  }
450 
451 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
452 
453 protected:
454  //! extract the (length = end - begin) smallest elements using parallel
455  //! multiway_merge.
456 
457  template <class OutputIterator>
458  void multi_merge_parallel(OutputIterator begin, OutputIterator end)
459  {
460  const unsigned_type& k = tree.k;
461 
462  if (begin == end)
463  return;
464 
465  typedef stxxl::int64 diff_type;
466 
467  typedef std::pair<typename block_type::iterator, typename block_type::iterator> sequence;
468 
469  std::vector<sequence> seqs;
470  std::vector<unsigned_type> orig_seq_index;
471 
473 
474  for (unsigned_type i = 0; i < k; ++i) //initialize sequences
475  {
476  if (states[i].current == states[i].block->size || is_sentinel(*states[i]))
477  continue;
478 
479  seqs.push_back(std::make_pair(states[i].block->begin() + states[i].current, states[i].block->end()));
480  orig_seq_index.push_back(i);
481 
482 #if STXXL_CHECK_ORDER_IN_SORTS
483  if (!is_sentinel(*seqs.back().first) && !stxxl::is_sorted(seqs.back().first, seqs.back().second, inv_cmp))
484  {
485  STXXL_VERBOSE1("length " << i << " " << (seqs.back().second - seqs.back().first));
486  for (value_type* v = seqs.back().first + 1; v < seqs.back().second; ++v)
487  {
488  if (inv_cmp(*v, *(v - 1)))
489  {
490  STXXL_VERBOSE1("Error at position " << i << "/" << (v - seqs.back().first - 1) << "/" << (v - seqs.back().first) << " " << *(v - 1) << " " << *v);
491  }
492  if (is_sentinel(*v))
493  {
494  STXXL_VERBOSE1("Wrong sentinel at position " << (v - seqs.back().first));
495  }
496  }
497  assert(false);
498  }
499 #endif
500 
501  // Hint first non-internal (actually second) block of this sequence.
502  if (!states[i].bids.empty())
503  pool->hint(states[i].bids.front());
504  }
505 
506  assert(seqs.size() > 0);
507 
508 #if STXXL_CHECK_ORDER_IN_SORTS
509  value_type last_elem;
510 #endif
511 
512  // elements still to merge for this output block
513  diff_type rest = end - begin;
514 
515  while (rest > 0)
516  {
517  // minimum of the sequences' last elements
518  value_type min_last = tree.cmp.min_value();
519 
520  diff_type total_size = 0;
521 
522  for (unsigned_type i = 0; i < seqs.size(); ++i)
523  {
524  diff_type seq_i_size = seqs[i].second - seqs[i].first;
525  if (seq_i_size > 0)
526  {
527  total_size += seq_i_size;
528  if (inv_cmp(*(seqs[i].second - 1), min_last))
529  min_last = *(seqs[i].second - 1);
530 
531  STXXL_VERBOSE1("front block of seq " << i << ": front=" << *(seqs[i].first) << " back=" << *(seqs[i].second - 1) << " len=" << seq_i_size);
532  }
533  else {
534  STXXL_VERBOSE1("front block of seq " << i << ": empty");
535  }
536  }
537 
538  assert(total_size > 0);
539  assert(!is_sentinel(min_last));
540 
541  STXXL_VERBOSE1("min_last " << min_last << " total size " << total_size << " num_seq " << seqs.size());
542 
543  diff_type less_equal_than_min_last = 0;
544  //locate this element in all sequences
545  for (unsigned_type i = 0; i < seqs.size(); ++i)
546  {
547  //assert(seqs[i].first < seqs[i].second);
548 
549  typename block_type::iterator position =
550  std::upper_bound(seqs[i].first, seqs[i].second, min_last, inv_cmp);
551 
552  //no element larger than min_last is merged
553 
554  STXXL_VERBOSE1("seq " << i << ": " << (position - seqs[i].first) << " greater equal than " << min_last);
555 
556  less_equal_than_min_last += (position - seqs[i].first);
557  }
558 
559  // at most rest elements
560  diff_type output_size = STXXL_MIN(less_equal_than_min_last, rest);
561 
562  STXXL_VERBOSE1("output_size=" << output_size << " = min(leq_t_ml=" << less_equal_than_min_last << ", rest=" << rest << ")");
563 
564  assert(output_size > 0);
565 
566  //main call
567 
568  // sequence iterators are progressed appropriately:
569  begin = parallel::multiway_merge(
570  seqs.begin(), seqs.end(), begin, output_size, inv_cmp);
571 
572  rest -= output_size;
573  m_size -= output_size;
574 
575  for (unsigned_type i = 0; i < seqs.size(); ++i)
576  {
577  sequence_state& state = states[orig_seq_index[i]];
578 
579  state.current = seqs[i].first - state.block->begin();
580 
581  assert(seqs[i].first <= seqs[i].second);
582 
583  if (seqs[i].first == seqs[i].second)
584  {
585  // has run empty?
586 
587  assert(state.current == state.block->size);
588  if (state.bids.empty())
589  {
590  // if there is no next block
591  STXXL_VERBOSE1("seq " << i << ": ext_merger::multi_merge(...) it was the last block in the sequence ");
592  state.make_inf();
593  }
594  else
595  {
596 #if STXXL_CHECK_ORDER_IN_SORTS
597  last_elem = *(seqs[i].second - 1);
598 #endif
599  STXXL_VERBOSE1("seq " << i << ": ext_merger::multi_merge(...) there is another block ");
600  bid_type bid = state.bids.front();
601  state.bids.pop_front();
602  pool->hint(bid);
603  if (!(state.bids.empty()))
604  {
605  STXXL_VERBOSE2("seq " << i << ": ext_merger::multi_merge(...) more blocks exist, hinting the next");
606  pool->hint(state.bids.front());
607  }
608  pool->read(state.block, bid)->wait();
609  STXXL_VERBOSE1("seq " << i << ": first element of read block " << bid << " " << *(state.block->begin()) << " cached in " << state.block);
610  if (!(state.bids.empty()))
611  pool->hint(state.bids.front()); // re-hint, reading might have made a block free
612  state.current = 0;
613  seqs[i] = std::make_pair(state.block->begin() + state.current, state.block->end());
614  block_manager::get_instance()->delete_block(bid);
615 
616 #if STXXL_CHECK_ORDER_IN_SORTS
617  STXXL_VERBOSE1("before " << last_elem << " after " << *seqs[i].first << " newly loaded block " << bid);
618  if (!stxxl::is_sorted(seqs[i].first, seqs[i].second, inv_cmp))
619  {
620  STXXL_VERBOSE1("length " << i << " " << (seqs[i].second - seqs[i].first));
621  for (value_type* v = seqs[i].first + 1; v < seqs[i].second; ++v)
622  {
623  if (inv_cmp(*v, *(v - 1)))
624  {
625  STXXL_VERBOSE1("Error at position " << i << "/" << (v - seqs[i].first - 1) << "/" << (v - seqs[i].first) << " " << *(v - 1) << " " << *v);
626  }
627  if (is_sentinel(*v))
628  {
629  STXXL_VERBOSE1("Wrong sentinel at position " << (v - seqs[i].first));
630  }
631  }
632  assert(false);
633  }
634 #endif
635  }
636  }
637  }
638  } //while (rest > 1)
639 
640  for (unsigned_type i = 0; i < seqs.size(); ++i)
641  {
642  unsigned_type seg = orig_seq_index[i];
643  if (is_array_empty(seg))
644  {
645  STXXL_VERBOSE1("deallocated " << seg);
646  free_array(seg);
647  }
648  }
649 
650  tree.maybe_compact();
651  }
652 #endif // STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
653 }; // class ext_merger
654 
655 } // namespace priority_queue_local
656 
657 //! \}
658 
660 
661 #endif // !STXXL_CONTAINERS_PQ_EXT_MERGER_HEADER
662 // vim: et:ts=4:sw=4
bid_container_type bids
list of blocks forming this sequence
Definition: pq_ext_merger.h:76
read_write_pool< block_type > pool_type
Definition: pq_ext_merger.h:55
const Type & STXXL_MIN(const Type &a, const Type &b)
Definition: utils.h:146
BlockType block_type
class is parameterized by the block of the external arrays
Definition: pq_ext_merger.h:42
Block manager class.
Definition: block_manager.h:61
External merger, based on the loser tree data structure.
Definition: pq_ext_merger.h:38
long long int int64
Definition: types.h:38
void maybe_compact()
compact tree if it got considerably smaller
Definition: pq_mergers.h:546
block_type * sentinel_block
a memory block filled with sentinel values
loser_tree< self_type, CompareType, Arity > tree_type
type of embedded loser tree
Definition: pq_ext_merger.h:65
bool hint(bid_type bid)
Gives a hint for prefetching a block.
Inverts the order of a comparison functor by swapping its arguments.
Definition: pq_helpers.h:187
std::deque< bid_type > bid_container_type
Definition: pq_ext_merger.h:53
RandomAccessIterator3 multiway_merge(RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
Multi-way merging dispatcher.
Definition: parallel.h:144
#define STXXL_DEFAULT_ALLOC_STRATEGY
Definition: block_alloc.h:258
ext_merger(const compare_type &c=compare_type())
request_ptr read(block_type *&block, bid_type bid)
Reads block.
void swap_1D_arrays(Type *a, Type *b, unsigned_type size)
Definition: utils.h:246
bool is_sentinel(const value_type &a) const
True if a is the sentinel value.
#define STXXL_VERBOSE2(x)
Definition: verbose.h:121
void insert_segment(bid_container_type &bidlist, block_type *first_block, unsigned_type first_size, unsigned_type slot)
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
bool is_array_allocated(unsigned_type slot) const
Is this segment allocated? Otherwise it&#39;s empty, already on the stack of free segment indices and can...
size_type size() const
Return the number of items in the arrays.
ext_merger< BlockType, CompareType, Arity, AllocStr > self_type
our type
Definition: pq_ext_merger.h:58
void free_player(unsigned_type slot)
Free a finished player&#39;s slot.
Definition: pq_mergers.h:338
void delete_blocks(const BIDIteratorClass &bidbegin, const BIDIteratorClass &bidend)
Deallocates blocks.
virtual void wait(bool measure_time=true)=0
Suspends calling thread until completion of the request.
unsigned_type k
current tree size, invariant (k == 1 &lt;&lt; logK), always a power of two
Definition: pq_losertree.h:61
External sequence or deque container without random access. Introduction to sequence container: se...
Definition: sequence.h:62
sequence_type & get_array(unsigned_type slot)
Return the item sequence of the given slot.
bool is_array_empty(unsigned_type slot) const
is this segment empty ?
void multi_merge(Element *begin, Element *end)
Definition: pq_losertree.h:190
void swap_arrays(unsigned_type a, unsigned_type b)
Swap contents of arrays a and b.
request_ptr write(block_type *&block, bid_type bid)
Passes a block to the pool for writing.
sequence_state sequence_type
type of sequences in which the values are stored: external arrays
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
size_type m_size
total number of elements stored
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
void prefetch_arrays()
Hint (prefetch) first non-internal (actually second) block of each sequence.
pool_type * pool
read and writer block pool
void update_on_insert(unsigned_type node, const Element &newKey, unsigned_type newIndex, Element *winnerKey, unsigned_type *winnerIndex, unsigned_type *mask)
tree_type tree
loser tree instance
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)
Definition: is_sorted.h:24
block_type * steal()
Take out a block from the pool.
void multi_merge(OutputIterator begin, OutputIterator end)
unsigned_type new_player()
Allocate a free slot for a new player.
Definition: pq_mergers.h:322
void append_merger(Merger &another_merger, size_type segment_size)
Merge all items from another merger and insert the resulting external array into the merger...
bool is_space_available() const
Whether there is still space for new array.
void new_blocks(const DiskAssignFunctor &functor, BIDIteratorClass bidbegin, BIDIteratorClass bidend, unsigned_type offset=0)
Allocates new blocks.
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
sequence_state states[max_arity]
sequence including current position, dereference gives current element
uint64 external_size_type
Definition: types.h:67
void make_array_sentinel(unsigned_type a)
Set a usually empty array to the sentinel.
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
size_type size_write() const
Returns number of blocks owned by the write_pool.
void free_array(unsigned_type slot)
free an empty segment.
unsigned_type current
current index in current block
Definition: pq_ext_merger.h:75
external_size_type size_type
size type of total number of item in merger
Definition: pq_ext_merger.h:69
#define STXXL_END_NAMESPACE
Definition: namespace.h:17