STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sequence.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/sequence.h
3  *
4  * based on include/stxxl/bits/containers/queue.h
5  *
6  * Part of the STXXL. See http://stxxl.sourceforge.net
7  *
8  * Copyright (C) 2012-2013 Timo Bingmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_CONTAINERS_SEQUENCE_HEADER
16 #define STXXL_CONTAINERS_SEQUENCE_HEADER
17 
18 #include <deque>
19 
20 #include <stxxl/bits/deprecated.h>
27 
29 
30 #ifndef STXXL_VERBOSE_SEQUENCE
31 #define STXXL_VERBOSE_SEQUENCE STXXL_VERBOSE2
32 #endif
33 
34 //! \addtogroup stlcont
35 //! \{
36 
37 //! External sequence or deque container without random access. \n
38 //! <b> Introduction </b> to sequence container: see \ref tutorial_sequence tutorial. \n
39 //! <b> Design and Internals </b> of sequence container: see \ref design_queue
40 
41 /**
42  * Sequence is a primitive container consisting of only a sequence of blocks in
43  * external memory. The sequence provides appending methods similar to a deque:
44  * push_back and push_front; and also the corresponding pop functions. However,
45  * different from stxxl::deque (which is a vector in disguise), the sequence
46  * does not allow random access. Instead, the sequence can only be iterated
47  * using streams: either from front to back or in reverse.
48  *
49  * As with queue and stack, sequences of pushes and pops are made efficient
50  * using overlapping or read-ahead via block pools. The stream access likewise
51  * uses overlapped I/O, just like stream::vector_iterator2stream.
52  *
53  * \tparam ValueType type of the contained objects (POD with no references to internal memory)
54  * \tparam BlockSize size of the external memory block in bytes, default is \c STXXL_DEFAULT_BLOCK_SIZE(ValTp)
55  * \tparam AllocStr parallel disk allocation strategy, default is \c STXXL_DEFAULT_ALLOC_STRATEGY
56  * \tparam SizeType size data type, default is \c stxxl::uint64
57  */
58 template <class ValueType,
59  unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
60  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
61  class SizeType = stxxl::uint64>
62 class sequence : private noncopyable
63 {
64 public:
65  typedef ValueType value_type;
66  typedef AllocStr alloc_strategy_type;
67  typedef SizeType size_type;
68  enum {
69  block_size = BlockSize
70  };
71 
74 
75  typedef std::deque<bid_type> bid_deque_type;
76 
77 private:
79 
80  /// current number of items in the sequence
82 
83  /// whether the m_pool object is own and should be deleted.
85 
86  /// read_write_pool of blocks
88 
89  /// current front block of sequence
91 
92  /// current back block of sequence
94 
95  /// pointer to current front element in m_front_block
97 
98  /// pointer to current back element in m_back_block
100 
101  /// block allocation strategy
103 
104  /// block allocation counter
106 
107  /// allocated block identifiers
109 
110  /// block manager used
112 
113  /// number of blocks to prefetch
115 
116 public:
117  //! \name Constructors/Destructors
118  //! \{
119 
120  //! Constructs empty sequence with own write and prefetch block pool
121  //!
122  //! \param D number of parallel disks, defaulting to the configured number of scratch disks,
123  //! memory consumption will be 2 * D + 2 blocks
124  //! (first and last block, D blocks as write cache, D block for prefetching)
125  explicit sequence(int_type D = -1)
126  : m_size(0),
127  m_owns_pool(true),
128  m_alloc_count(0),
129  m_bm(block_manager::get_instance())
130  {
131  if (D < 1) D = config::get_instance()->disks_number();
132  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]::sequence(D)");
133  m_pool = new pool_type(D, D + 2);
134  init();
135  }
136 
137  //! Constructs empty sequence with own write and prefetch block pool
138  //!
139  //! \param w_pool_size number of blocks in the write pool, must be at least 2, recommended at least 3
140  //! \param p_pool_size number of blocks in the prefetch pool, recommended at least 1
141  //! \param blocks2prefetch defines the number of blocks to prefetch (\c front side),
142  //! default is number of block in the prefetch pool
143  explicit sequence(unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch = -1)
144  : m_size(0),
145  m_owns_pool(true),
146  m_alloc_count(0),
147  m_bm(block_manager::get_instance())
148  {
149  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]::sequence(sizes)");
150  m_pool = new pool_type(p_pool_size, w_pool_size);
151  init(blocks2prefetch);
152  }
153 
154  //! Constructs empty sequence
155  //!
156  //! \param pool block write/prefetch pool
157  //! \param blocks2prefetch defines the number of blocks to prefetch (\c front side), default is number of blocks in the prefetch pool
158  //! \warning Number of blocks in the write pool must be at least 2, recommended at least 3
159  //! \warning Number of blocks in the prefetch pool recommended at least 1
160  sequence(pool_type& pool, int blocks2prefetch = -1)
161  : m_size(0),
162  m_owns_pool(false),
163  m_pool(&pool),
164  m_alloc_count(0),
165  m_bm(block_manager::get_instance())
166  {
167  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]::sequence(pool)");
168  init(blocks2prefetch);
169  }
170 
171  //! \}
172 
173  //! \name Modifiers
174  //! \{
175 
176  void swap(sequence& obj)
177  {
178  std::swap(m_size, obj.m_size);
179  std::swap(m_owns_pool, obj.m_owns_pool);
180  std::swap(m_pool, obj.m_pool);
181  std::swap(m_front_block, obj.m_front_block);
182  std::swap(m_back_block, obj.m_back_block);
183  std::swap(m_front_element, obj.m_front_element);
184  std::swap(m_back_element, obj.m_back_element);
185  std::swap(m_alloc_strategy, obj.m_alloc_strategy);
186  std::swap(m_alloc_count, obj.m_alloc_count);
187  std::swap(m_bids, obj.m_bids);
188  std::swap(m_bm, obj.m_bm);
189  std::swap(m_blocks2prefetch, obj.m_blocks2prefetch);
190  }
191 
192  //! \}
193 
194 private:
195  void init(int blocks2prefetch = -1)
196  {
197  if (m_pool->size_write() < 2) {
198  STXXL_ERRMSG("sequence: invalid configuration, not enough blocks (" << m_pool->size_write() <<
199  ") in write pool, at least 2 are needed, resizing to 3");
200  m_pool->resize_write(3);
201  }
202 
203  if (m_pool->size_write() < 3) {
204  STXXL_MSG("sequence: inefficient configuration, no blocks for buffered writing available");
205  }
206 
207  if (m_pool->size_prefetch() < 1) {
208  STXXL_MSG("sequence: inefficient configuration, no blocks for prefetching available");
209  }
210 
211  /// initialize empty sequence
212  m_front_block = m_back_block = m_pool->steal();
213  m_back_element = m_back_block->begin() - 1;
214  m_front_element = m_back_block->begin();
215  set_prefetch_aggr(blocks2prefetch);
216  }
217 
218 public:
219  //! \name Miscellaneous
220  //! \{
221 
222  //! Defines the number of blocks to prefetch (\c front side).
223  //! This method should be called whenever the prefetch pool is resized
224  //! \param blocks2prefetch defines the number of blocks to prefetch (\c front side),
225  //! a negative value means to use the number of blocks in the prefetch pool
226  void set_prefetch_aggr(int_type blocks2prefetch)
227  {
228  if (blocks2prefetch < 0)
229  m_blocks2prefetch = m_pool->size_prefetch();
230  else
231  m_blocks2prefetch = blocks2prefetch;
232  }
233 
234  //! Returns the number of blocks prefetched from the \c front side
236  {
237  return m_blocks2prefetch;
238  }
239 
240  //! \}
241 
242  //! \name Modifiers
243  //! \{
244 
245  //! Adds an element to the front of the sequence
246  void push_front(const value_type& val)
247  {
248  if (UNLIKELY(m_front_element == m_front_block->begin()))
249  {
250  if (m_size == 0)
251  {
252  STXXL_VERBOSE1("sequence::push_front Case 0");
253  assert(m_front_block == m_back_block);
254  m_front_element = m_back_element = m_front_block->end() - 1;
255  *m_front_element = val;
256  ++m_size;
257  return;
258  }
259  // front block is completely filled
260  else if (m_front_block == m_back_block)
261  {
262  // can not write the front block because it
263  // is the same as the back block, must keep it memory
264  STXXL_VERBOSE1("sequence::push_front Case 1");
265  }
266  else if (size() < 2 * block_type::size)
267  {
268  STXXL_VERBOSE1("sequence::push_front Case 1.5");
269  // only two blocks with a gap at the end, move elements within memory
270  assert(m_bids.empty());
271  size_t gap = m_back_block->end() - (m_back_element + 1);
272  assert(gap > 0);
273  std::copy_backward(m_back_block->begin(), m_back_element + 1, m_back_block->end());
274  std::copy_backward(m_front_block->end() - gap, m_front_block->end(), m_back_block->begin() + gap);
275  std::copy_backward(m_front_block->begin(), m_front_block->end() - gap, m_front_block->end());
276  m_front_element += gap;
277  m_back_element += gap;
278 
279  --m_front_element;
280  *m_front_element = val;
281  ++m_size;
282  return;
283  }
284  else
285  {
286  STXXL_VERBOSE1("sequence::push_front Case 2");
287  // write the front block
288  // need to allocate new block
289  bid_type newbid;
290 
291  m_bm->new_block(m_alloc_strategy, newbid, m_alloc_count++);
292 
293  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]: push_front block " << m_front_block << " @ " << FMT_BID(newbid));
294  m_bids.push_front(newbid);
295  m_pool->write(m_front_block, newbid);
296  if (m_bids.size() <= m_blocks2prefetch) {
297  STXXL_VERBOSE1("sequence::push Case Hints");
298  m_pool->hint(newbid);
299  }
300  }
301 
302  m_front_block = m_pool->steal();
303  m_front_element = m_front_block->end() - 1;
304  *m_front_element = val;
305  ++m_size;
306  }
307  else // not at beginning of a block
308  {
309  --m_front_element;
310  *m_front_element = val;
311  ++m_size;
312  }
313  }
314 
315  //! Adds an element to the end of the sequence
316  void push_back(const value_type& val)
317  {
318  if (UNLIKELY(m_back_element == m_back_block->begin() + (block_type::size - 1)))
319  {
320  // back block is completely filled
321  if (m_front_block == m_back_block)
322  {
323  // can not write the back block because it
324  // is the same as the front block, must keep it memory
325  STXXL_VERBOSE1("sequence::push_back Case 1");
326  }
327  else if (size() < 2 * block_type::size)
328  {
329  STXXL_VERBOSE1("sequence::push_back Case 1.5");
330  // only two blocks with a gap in the beginning, move elements within memory
331  assert(m_bids.empty());
332  size_t gap = m_front_element - m_front_block->begin();
333  assert(gap > 0);
334  std::copy(m_front_element, m_front_block->end(), m_front_block->begin());
335  std::copy(m_back_block->begin(), m_back_block->begin() + gap, m_front_block->begin() + (block_type::size - gap));
336  std::copy(m_back_block->begin() + gap, m_back_block->end(), m_back_block->begin());
337  m_front_element -= gap;
338  m_back_element -= gap;
339 
340  ++m_back_element;
341  *m_back_element = val;
342  ++m_size;
343  return;
344  }
345  else
346  {
347  STXXL_VERBOSE1("sequence::push_back Case 2");
348  // write the back block
349  // need to allocate new block
350  bid_type newbid;
351 
352  m_bm->new_block(m_alloc_strategy, newbid, m_alloc_count++);
353 
354  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]: push_back block " << m_back_block << " @ " << FMT_BID(newbid));
355  m_bids.push_back(newbid);
356  m_pool->write(m_back_block, newbid);
357  if (m_bids.size() <= m_blocks2prefetch) {
358  STXXL_VERBOSE1("sequence::push_back Case Hints");
359  m_pool->hint(newbid);
360  }
361  }
362  m_back_block = m_pool->steal();
363 
364  m_back_element = m_back_block->begin();
365  *m_back_element = val;
366  ++m_size;
367  }
368  else // not at end of a block
369  {
370  ++m_back_element;
371  *m_back_element = val;
372  ++m_size;
373  }
374  }
375 
376  //! Removes element from the front of the sequence
377  void pop_front()
378  {
379  assert(!empty());
380 
381  if (UNLIKELY(m_front_element == m_front_block->begin() + (block_type::size - 1)))
382  {
383  // if there is only one block, it implies ...
384  if (m_back_block == m_front_block)
385  {
386  STXXL_VERBOSE1("sequence::pop_front Case 1");
387  assert(size() == 1);
388  assert(m_back_element == m_front_element);
389  assert(m_bids.empty());
390  // reset everything
391  m_back_element = m_back_block->begin() - 1;
392  m_front_element = m_back_block->begin();
393  m_size = 0;
394  return;
395  }
396 
397  --m_size;
398  if (m_size <= block_type::size)
399  {
400  STXXL_VERBOSE1("sequence::pop_front Case 2");
401  assert(m_bids.empty());
402  // the m_back_block is the next block
403  m_pool->add(m_front_block);
404  m_front_block = m_back_block;
405  m_front_element = m_back_block->begin();
406  return;
407  }
408  STXXL_VERBOSE1("sequence::pop_front Case 3");
409 
410  assert(!m_bids.empty());
411  request_ptr req = m_pool->read(m_front_block, m_bids.front());
412  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]: pop_front block " << m_front_block << " @ " << FMT_BID(m_bids.front()));
413 
414  // give prefetching hints
415  for (unsigned_type i = 0; i < m_blocks2prefetch && i < m_bids.size() - 1; ++i)
416  {
417  STXXL_VERBOSE1("sequence::pop_front Case Hints");
418  m_pool->hint(m_bids[i + 1]);
419  }
420 
421  m_front_element = m_front_block->begin();
422  req->wait();
423 
424  m_bm->delete_block(m_bids.front());
425  m_bids.pop_front();
426  }
427  else
428  {
429  ++m_front_element;
430  --m_size;
431  }
432  }
433 
434  //! Removes element from the back of the sequence
435  void pop_back()
436  {
437  assert(!empty());
438 
439  if (UNLIKELY(m_back_element == m_back_block->begin()))
440  {
441  // if there is only one block, it implies ...
442  if (m_back_block == m_front_block)
443  {
444  STXXL_VERBOSE1("sequence::pop_back Case 1");
445  assert(size() == 1);
446  assert(m_back_element == m_front_element);
447  assert(m_bids.empty());
448  // reset everything
449  m_back_element = m_back_block->begin() - 1;
450  m_front_element = m_back_block->begin();
451  m_size = 0;
452  return;
453  }
454 
455  --m_size;
456  if (m_size <= block_type::size)
457  {
458  STXXL_VERBOSE1("sequence::pop_back Case 2");
459  assert(m_bids.empty());
460  // the m_front_block is the next block
461  m_pool->add(m_back_block);
462  m_back_block = m_front_block;
463  m_back_element = m_back_block->end() - 1;
464  return;
465  }
466 
467  STXXL_VERBOSE1("sequence::pop_back Case 3");
468 
469  assert(!m_bids.empty());
470  request_ptr req = m_pool->read(m_back_block, m_bids.back());
471  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]: pop_back block " << m_back_block << " @ " << FMT_BID(m_bids.back()));
472 
473  // give prefetching hints
474  for (unsigned_type i = 1; i < m_blocks2prefetch && i < m_bids.size() - 1; ++i)
475  {
476  STXXL_VERBOSE1("sequence::pop_front Case Hints");
477  m_pool->hint(m_bids[m_bids.size() - 1 - i]);
478  }
479 
480  m_back_element = m_back_block->end() - 1;
481  req->wait();
482 
483  m_bm->delete_block(m_bids.back());
484  m_bids.pop_back();
485  }
486  else
487  {
488  --m_back_element;
489  --m_size;
490  }
491  }
492 
493  //! \}
494 
495  //! \name Capacity
496  //! \{
497 
498  //! Returns the size of the sequence
499  size_type size() const
500  {
501  return m_size;
502  }
503 
504  //! Returns \c true if sequence is empty
505  bool empty() const
506  {
507  return (m_size == 0);
508  }
509 
510  //! \}
511 
512  //! \name Operators
513  //! \{
514 
515  //! Returns a mutable reference at the back of the sequence
517  {
518  assert(!empty());
519  return *m_back_element;
520  }
521 
522  //! Returns a const reference at the back of the sequence
523  const value_type & back() const
524  {
525  assert(!empty());
526  return *m_back_element;
527  }
528 
529  //! Returns a mutable reference at the front of the sequence
531  {
532  assert(!empty());
533  return *m_front_element;
534  }
535 
536  //! Returns a const reference at the front of the sequence
537  const value_type & front() const
538  {
539  assert(!empty());
540  return *m_front_element;
541  }
542 
543  //! \}
544 
545  //! \name Constructors/Destructors
546  //! \{
547 
549  {
550  if (m_front_block != m_back_block)
551  m_pool->add(m_back_block);
552 
553  m_pool->add(m_front_block);
554 
555  if (m_owns_pool)
556  delete m_pool;
557 
558  if (!m_bids.empty())
559  m_bm->delete_blocks(m_bids.begin(), m_bids.end());
560  }
561 
562  //! \}
563 
564  /**************************************************************************/
565 
566  class stream
567  {
568  public:
570 
571  typedef typename bid_deque_type::const_iterator bid_iter_type;
572 
573  protected:
575 
577 
579 
581 
583 
584  public:
586  : m_sequence(sequence),
587  m_size(sequence.size())
588  {
589  m_current_block = sequence.m_front_block;
590  m_current_element = sequence.m_front_element;
591  m_next_bid = sequence.m_bids.begin();
592  }
593 
595  {
596  if (m_current_block != m_sequence.m_front_block &&
597  m_current_block != m_sequence.m_back_block) // give m_current_block back to pool
598  m_sequence.m_pool->add(m_current_block);
599  }
600 
601  //! return number of element left till end-of-stream.
602  size_type size() const
603  {
604  return m_size;
605  }
606 
607  //! standard stream method
608  bool empty() const
609  {
610  return (m_size == 0);
611  }
612 
613  //! standard stream method
614  const value_type& operator * () const
615  {
616  assert(!empty());
617  return *m_current_element;
618  }
619 
620  //! standard stream method
622  {
623  assert(!empty());
624 
625  if (UNLIKELY(m_current_element == m_current_block->begin() + (block_type::size - 1)))
626  {
627  // next item position is beyond end of current block, find next block
628  --m_size;
629 
630  if (m_size == 0)
631  {
632  STXXL_VERBOSE1("sequence::stream::operator++ last block finished clean at block end");
633  assert(m_next_bid == m_sequence.m_bids.end());
634  assert(m_current_block == m_sequence.m_back_block);
635  // nothing to give back to sequence pool
636  m_current_element = NULL;
637  return *this;
638  }
639  else if (m_size <= block_type::size) // still items left in last partial block
640  {
641  STXXL_VERBOSE1("sequence::stream::operator++ reached last block");
642  assert(m_next_bid == m_sequence.m_bids.end());
643  // the m_back_block is the next block
644  if (m_current_block != m_sequence.m_front_block) // give current_block back to pool
645  m_sequence.m_pool->add(m_current_block);
646  m_current_block = m_sequence.m_back_block;
647  m_current_element = m_current_block->begin();
648  return *this;
649  }
650  else if (m_current_block == m_sequence.m_front_block)
651  {
652  STXXL_VERBOSE1("sequence::stream::operator++ first own-block case: steal block from sequence's pool");
653  m_current_block = m_sequence.m_pool->steal();
654  }
655 
656  STXXL_VERBOSE1("sequence::stream::operator++ default case: fetch next block");
657 
658  assert(m_next_bid != m_sequence.m_bids.end());
659  request_ptr req = m_sequence.m_pool->read(m_current_block, *m_next_bid);
660  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]::stream::operator++ read block " << m_current_block << " @ " << FMT_BID(*m_next_bid));
661 
662  // give prefetching hints
663  bid_iter_type bid = m_next_bid + 1;
664  for (unsigned_type i = 0; i < m_sequence.m_blocks2prefetch && bid != m_sequence.m_bids.end(); ++i, ++bid)
665  {
666  STXXL_VERBOSE1("sequence::stream::operator++ giving prefetch hints");
667  m_sequence.m_pool->hint(*bid);
668  }
669 
670  m_current_element = m_current_block->begin();
671  req->wait();
672 
673  ++m_next_bid;
674  }
675  else
676  {
677  --m_size;
678  ++m_current_element;
679  }
680  return *this;
681  }
682  };
683 
684  //! \name Miscellaneous
685  //! \{
686 
687  //! construct a forward stream from this sequence
689  {
690  return stream(*this);
691  }
692 
693  //! \}
694 
695  /**************************************************************************/
696 
698  {
699  public:
701 
702  typedef typename bid_deque_type::const_reverse_iterator bid_iter_type;
703 
704  protected:
706 
708 
710 
712 
714 
715  public:
717  : m_sequence(sequence),
718  m_size(sequence.size())
719  {
720  m_current_block = sequence.m_back_block;
721  m_current_element = sequence.m_back_element;
722  m_next_bid = sequence.m_bids.rbegin();
723  }
724 
726  {
727  if (m_current_block != m_sequence.m_front_block &&
728  m_current_block != m_sequence.m_back_block) // give m_current_block back to pool
729  m_sequence.m_pool->add(m_current_block);
730  }
731 
732  //! return number of element left till end-of-stream.
733  size_type size() const
734  {
735  return m_size;
736  }
737 
738  //! standard stream method
739  bool empty() const
740  {
741  return (m_size == 0);
742  }
743 
744  //! standard stream method
745  const value_type& operator * () const
746  {
747  assert(!empty());
748  return *m_current_element;
749  }
750 
751  //! standard stream method
753  {
754  assert(!empty());
755 
756  if (UNLIKELY(m_current_element == m_current_block->begin()))
757  {
758  // next item position is beyond begin of current block, find next block
759  --m_size;
760 
761  if (m_size == 0)
762  {
763  STXXL_VERBOSE1("sequence::reverse_stream::operator++ last block finished clean at block begin");
764  assert(m_next_bid == m_sequence.m_bids.rend());
765  assert(m_current_block == m_sequence.m_front_block);
766  // nothing to give back to sequence pool
767  m_current_element = NULL;
768  return *this;
769  }
770  else if (m_size <= block_type::size)
771  {
772  STXXL_VERBOSE1("sequence::reverse_stream::operator++ reached first block");
773  assert(m_next_bid == m_sequence.m_bids.rend());
774  // the m_back_block is the next block
775  if (m_current_block != m_sequence.m_back_block) // give current_block back to pool
776  m_sequence.m_pool->add(m_current_block);
777  m_current_block = m_sequence.m_front_block;
778  m_current_element = m_current_block->begin() + (block_type::size - 1);
779  return *this;
780  }
781  else if (m_current_block == m_sequence.m_back_block)
782  {
783  STXXL_VERBOSE1("sequence::reverse_stream::operator++ first own-block case: steal block from sequence's pool");
784  m_current_block = m_sequence.m_pool->steal();
785  }
786 
787  STXXL_VERBOSE1("sequence::reverse_stream::operator++ default case: fetch previous block");
788 
789  assert(m_next_bid != m_sequence.m_bids.rend());
790  request_ptr req = m_sequence.m_pool->read(m_current_block, *m_next_bid);
791  STXXL_VERBOSE_SEQUENCE("sequence[" << this << "]::reverse_stream::operator++ read block " << m_current_block << " @ " << FMT_BID(*m_next_bid));
792 
793  // give prefetching hints
794  bid_iter_type bid = m_next_bid + 1;
795  for (unsigned_type i = 0; i < m_sequence.m_blocks2prefetch && bid != m_sequence.m_bids.rend(); ++i, ++bid)
796  {
797  STXXL_VERBOSE1("sequence::reverse_stream::operator++ giving prefetch hints");
798  m_sequence.m_pool->hint(*bid);
799  }
800 
801  m_current_element = m_current_block->begin() + (block_type::size - 1);
802  req->wait();
803 
804  ++m_next_bid;
805  }
806  else
807  {
808  --m_size;
809  --m_current_element;
810  }
811  return *this;
812  }
813  };
814 
815  //! \name Miscellaneous
816  //! \{
817 
818  //! construct a reverse stream from this sequence
820  {
821  return reverse_stream(*this);
822  }
823 
824  //! \}
825 };
826 
827 //! \}
828 
830 
831 #endif // !STXXL_CONTAINERS_SEQUENCE_HEADER
832 // vim: et:ts=4:sw=4
void pop_front()
Removes element from the front of the sequence.
Definition: sequence.h:377
#define STXXL_DEFAULT_BLOCK_SIZE(type)
BID< block_size > bid_type
Definition: sequence.h:73
pool_type * m_pool
read_write_pool of blocks
Definition: sequence.h:87
bid_deque_type::const_iterator bid_iter_type
Definition: sequence.h:571
void push_back(const value_type &val)
Adds an element to the end of the sequence.
Definition: sequence.h:316
Block manager class.
Definition: block_manager.h:61
block_type * m_front_block
current front block of sequence
Definition: sequence.h:90
bool empty() const
standard stream method
Definition: sequence.h:608
unsigned long long int uint64
Definition: types.h:39
value_type * m_back_element
pointer to current back element in m_back_block
Definition: sequence.h:99
bid_iter_type m_next_bid
Definition: sequence.h:582
size_type size() const
return number of element left till end-of-stream.
Definition: sequence.h:733
sequence(int_type D=-1)
Constructs empty sequence with own write and prefetch block pool.
Definition: sequence.h:125
stream get_stream()
construct a forward stream from this sequence
Definition: sequence.h:688
void swap(sequence &obj)
Definition: sequence.h:176
void push_front(const value_type &val)
Adds an element to the front of the sequence.
Definition: sequence.h:246
void init(int blocks2prefetch=-1)
Definition: sequence.h:195
#define STXXL_DEFAULT_ALLOC_STRATEGY
Definition: block_alloc.h:258
size_type m_size
current number of items in the sequence
Definition: sequence.h:81
value_type * m_current_element
Definition: sequence.h:578
AllocStr alloc_strategy_type
Definition: sequence.h:66
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
value_type & front()
Returns a mutable reference at the front of the sequence.
Definition: sequence.h:530
const value_type & front() const
Returns a const reference at the front of the sequence.
Definition: sequence.h:537
unsigned_type m_alloc_count
block allocation counter
Definition: sequence.h:105
void pop_back()
Removes element from the back of the sequence.
Definition: sequence.h:435
Block containing elements of fixed length.
Definition: typed_block.h:237
External sequence or deque container without random access. Introduction to sequence container: se...
Definition: sequence.h:62
size_type size() const
return number of element left till end-of-stream.
Definition: sequence.h:602
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
#define UNLIKELY(c)
Definition: utils.h:225
ValueType value_type
Definition: sequence.h:65
#define STXXL_VERBOSE_SEQUENCE
Definition: sequence.h:31
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
sequence(unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch=-1)
Constructs empty sequence with own write and prefetch block pool.
Definition: sequence.h:143
bool m_owns_pool
whether the m_pool object is own and should be deleted.
Definition: sequence.h:84
void set_prefetch_aggr(int_type blocks2prefetch)
Defines the number of blocks to prefetch (front side). This method should be called whenever the pref...
Definition: sequence.h:226
stream(const sequence &sequence)
Definition: sequence.h:585
block_type * m_current_block
Definition: sequence.h:580
reverse_stream get_reverse_stream()
construct a reverse stream from this sequence
Definition: sequence.h:819
sequence(pool_type &pool, int blocks2prefetch=-1)
Constructs empty sequence.
Definition: sequence.h:160
const sequence & m_sequence
Definition: sequence.h:574
read_write_pool< block_type > pool_type
Definition: sequence.h:78
SizeType size_type
Definition: sequence.h:67
bid_deque_type m_bids
allocated block identifiers
Definition: sequence.h:108
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
alloc_strategy_type m_alloc_strategy
block allocation strategy
Definition: sequence.h:102
unsigned_type m_blocks2prefetch
number of blocks to prefetch
Definition: sequence.h:114
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
size_type size() const
Returns the size of the sequence.
Definition: sequence.h:499
block_type * m_back_block
current back block of sequence
Definition: sequence.h:93
#define STXXL_MSG(x)
Definition: verbose.h:73
std::deque< bid_type > bid_deque_type
Definition: sequence.h:75
value_type * m_front_element
pointer to current front element in m_front_block
Definition: sequence.h:96
sequence::value_type value_type
Definition: sequence.h:569
const value_type & back() const
Returns a const reference at the back of the sequence.
Definition: sequence.h:523
value_type & back()
Returns a mutable reference at the back of the sequence.
Definition: sequence.h:516
const sequence & m_sequence
Definition: sequence.h:705
bool empty() const
Returns true if sequence is empty.
Definition: sequence.h:505
reverse_stream(const sequence &sequence)
Definition: sequence.h:716
sequence::value_type value_type
Definition: sequence.h:700
bool empty() const
standard stream method
Definition: sequence.h:739
block_manager * m_bm
block manager used
Definition: sequence.h:111
typed_block< block_size, value_type > block_type
Definition: sequence.h:72
#define FMT_BID(_bid_)
Definition: bid.h:30
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
bid_deque_type::const_reverse_iterator bid_iter_type
Definition: sequence.h:702
unsigned_type get_prefetch_aggr() const
Returns the number of blocks prefetched from the front side.
Definition: sequence.h:235