STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stack.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/stack.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2003-2004 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009, 2010 Andreas Beckmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_CONTAINERS_STACK_HEADER
15 #define STXXL_CONTAINERS_STACK_HEADER
16 
17 #include <stack>
18 #include <vector>
19 
20 #include <stxxl/bits/deprecated.h>
30 
32 
33 //! \defgroup stlcont_stack stack
34 //! \ingroup stlcont
35 //! External stack implementations
36 //! \{
37 
38 template <class ValueType,
39  unsigned BlocksPerPage = 4,
40  unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
41  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
42  class SizeType = stxxl::uint64>
44 {
45  typedef ValueType value_type;
46  enum { blocks_per_page = BlocksPerPage };
47  typedef AllocStr alloc_strategy;
48  enum { block_size = BlockSize };
49  typedef SizeType size_type;
50 };
51 
52 //! External stack container.
53 //! <b> Introduction </b> to stack container: see \ref tutorial_stack tutorial. \n
54 //! <b> Design and Internals </b> of stack container: see \ref design_stack
55 //! Conservative implementation. Fits best if your access pattern consists of irregularly mixed
56 //! push'es and pop's.
57 //! For semantics of the methods see documentation of the STL \c std::stack. <BR>
58 //! To gain full bandwidth of disks \c StackConfig::BlocksPerPage must >= number of disks <BR>
59 //! \internal
60 template <class StackConfig>
61 class normal_stack : private noncopyable
62 {
63 public:
64  typedef StackConfig cfg;
65  //! type of the elements stored in the stack
66  typedef typename cfg::value_type value_type;
67  typedef typename cfg::alloc_strategy alloc_strategy_type;
68  //! type for sizes (64-bit)
69  typedef typename cfg::size_type size_type;
70  enum {
71  blocks_per_page = cfg::blocks_per_page,
72  block_size = cfg::block_size
73  };
74 
75  //! type of block used in disk-memory transfers
78 
79 private:
86  std::vector<bid_type> bids;
88 
89 public:
90  //! \name Constructors/Destructors
91  //! \{
92 
93  //! Default constructor: creates empty stack.
95  : m_size(0),
96  cache_offset(0),
97  current_element(NULL),
98  cache(blocks_per_page * 2),
99  front_page(cache.begin() + blocks_per_page),
100  back_page(cache.begin()),
101  bids(0)
102  {
103  bids.reserve(blocks_per_page);
104  }
105 
106  //! \name Accessor Functions
107  //! \{
108 
109  void swap(normal_stack& obj)
110  {
111  std::swap(m_size, obj.m_size);
112  std::swap(cache_offset, obj.cache_offset);
113  std::swap(current_element, obj.current_element);
114  std::swap(cache, obj.cache);
115  std::swap(front_page, obj.front_page);
116  std::swap(back_page, obj.back_page);
117  std::swap(bids, obj.bids);
118  std::swap(alloc_strategy, obj.alloc_strategy);
119  }
120 
121  //! \}
122 
123  //! \name Constructors/Destructors
124  //! \{
125 
126  //! Copy-construction from a another stack of any type.
127  //! \param stack_ stack object (could be external or internal, important is that it must
128  //! have a copy constructor, \c top() and \c pop() methods )
129  template <class StackType>
130  normal_stack(const StackType& stack_)
131  : m_size(0),
132  cache_offset(0),
133  current_element(NULL),
134  cache(blocks_per_page * 2),
135  front_page(cache.begin() + blocks_per_page),
136  back_page(cache.begin()),
137  bids(0)
138  {
139  bids.reserve(blocks_per_page);
140 
141  StackType stack_copy = stack_;
142  size_t sz = stack_copy.size();
143 
144  std::vector<value_type> tmp(sz);
145 
146  for (size_t i = 0; i < sz; ++i) {
147  tmp[sz - i - 1] = stack_copy.top();
148  stack_copy.pop();
149  }
150 
151  for (size_t i = 0; i < sz; ++i)
152  push(tmp[i]);
153  }
154 
155  virtual ~normal_stack()
156  {
158  block_manager::get_instance()->delete_blocks(bids.begin(), bids.end());
159  }
160 
161  //! \}
162 
163  //! \name Capacity
164  //! \{
165 
166  //! Returns the number of elements contained in the stack
167  size_type size() const
168  {
169  return m_size;
170  }
171 
172  //! Returns true if the stack is empty.
173  bool empty() const
174  {
175  return (!m_size);
176  }
177 
178  //! \}
179 
180  //! \name Accessor Functions
181  //! \{
182 
183  //! Return mutable reference to the element at the top of the
184  //! stack. Precondition: stack is not empty().
186  {
187  assert(m_size > 0);
188  return (*current_element);
189  }
190 
191  //! Return constant reference to the element at the top of the
192  //! stack. Precondition: stack is not empty().
193  const value_type & top() const
194  {
195  assert(m_size > 0);
196  return (*current_element);
197  }
198 
199  //! Inserts an element at the top of the stack. Postconditions: size() is
200  //! incremented by 1, and top() is the inserted element.
201  void push(const value_type& val)
202  {
203  assert(cache_offset <= 2 * blocks_per_page * block_type::size);
204  //assert(cache_offset >= 0);
205 
206  if (UNLIKELY(cache_offset == 2 * blocks_per_page * block_type::size)) // cache overflow
207  {
208  STXXL_VERBOSE2("growing, size: " << m_size);
209 
210  bids.resize(bids.size() + blocks_per_page);
211  typename std::vector<bid_type>::iterator cur_bid = bids.end() - blocks_per_page;
212  block_manager::get_instance()->new_blocks(alloc_strategy, cur_bid, bids.end(), cur_bid - bids.begin());
213 
214  simple_vector<request_ptr> requests(blocks_per_page);
215 
216  for (int i = 0; i < blocks_per_page; ++i, ++cur_bid)
217  {
218  requests[i] = (back_page + i)->write(*cur_bid);
219  }
220 
221  std::swap(back_page, front_page);
222 
223  bids.reserve(bids.size() + blocks_per_page);
224 
225  cache_offset = blocks_per_page * block_type::size + 1;
226  current_element = &((*front_page)[0]);
227  ++m_size;
228 
229  wait_all(requests.begin(), blocks_per_page);
230 
231  *current_element = val;
232 
233  return;
234  }
235 
236  current_element = element(cache_offset);
237  *current_element = val;
238  ++m_size;
239  ++cache_offset;
240  }
241 
242  //! Removes the element at the top of the stack. Precondition: stack is not
243  //! empty(). Postcondition: size() is decremented.
244  void pop()
245  {
246  assert(cache_offset <= 2 * blocks_per_page * block_type::size);
247  assert(cache_offset > 0);
248  assert(m_size > 0);
249 
250  if (UNLIKELY(cache_offset == 1 && bids.size() >= blocks_per_page))
251  {
252  STXXL_VERBOSE2("shrinking, size: " << m_size);
253 
254  simple_vector<request_ptr> requests(blocks_per_page);
255 
256  {
257  typename std::vector<bid_type>::const_iterator cur_bid = bids.end();
258  for (int i = blocks_per_page - 1; i >= 0; --i)
259  {
260  requests[i] = (front_page + i)->read(*(--cur_bid));
261  }
262  }
263 
264  std::swap(front_page, back_page);
265 
266  cache_offset = blocks_per_page * block_type::size;
267  --m_size;
268  current_element = &((*(back_page + (blocks_per_page - 1)))[block_type::size - 1]);
269 
270  wait_all(requests.begin(), blocks_per_page);
271 
272  block_manager::get_instance()->delete_blocks(bids.end() - blocks_per_page, bids.end());
273  bids.resize(bids.size() - blocks_per_page);
274 
275  return;
276  }
277 
278  --m_size;
279 
280  current_element = element((--cache_offset) - 1);
281  }
282 
283  //! \}
284 
285 private:
287  {
288  if (offset < blocks_per_page * block_type::size)
289  return &((*(back_page + offset / block_type::size))[offset % block_type::size]);
290 
291  unsigned_type unbiased_offset = offset - blocks_per_page * block_type::size;
292  return &((*(front_page + unbiased_offset / block_type::size))[unbiased_offset % block_type::size]);
293  }
294 };
295 
296 //! Efficient implementation that uses prefetching and overlapping using internal buffers.
297 //!
298 //! Use it if your access pattern consists of many repeated push'es and pop's
299 //! For semantics of the methods see documentation of the STL \c std::stack.
300 //! \warning The amortized complexity of operation is not O(1/DB), rather O(DB)
301 template <class StackConfig>
303 {
304 public:
305  typedef StackConfig cfg;
306  //! type of the elements stored in the stack
307  typedef typename cfg::value_type value_type;
308  typedef typename cfg::alloc_strategy alloc_strategy_type;
309  //! type for sizes (64-bit)
310  typedef typename cfg::size_type size_type;
311  enum {
312  blocks_per_page = cfg::blocks_per_page,
313  block_size = cfg::block_size
314  };
315 
316  //! type of block used in disk-memory transfers
319 
320 private:
328  std::vector<bid_type> bids;
330 
331 public:
332  //! \name Constructors/Destructor
333  //! \{
334 
335  //! Default constructor: creates empty stack.
337  : m_size(0),
338  cache_offset(0),
339  current_element(NULL),
340  cache(blocks_per_page * 2),
341  cache_buffers(cache.begin()),
342  overlap_buffers(cache.begin() + blocks_per_page),
343  requests(blocks_per_page),
344  bids(0)
345  {
346  bids.reserve(blocks_per_page);
347  }
348 
349  //! \}
350 
351  //! \name Accessor Functions
352  //! \{
353 
355  {
356  std::swap(m_size, obj.m_size);
357  std::swap(cache_offset, obj.cache_offset);
358  std::swap(current_element, obj.current_element);
359  std::swap(cache, obj.cache);
360  std::swap(cache_buffers, obj.cache_buffers);
361  std::swap(overlap_buffers, obj.overlap_buffers);
362  std::swap(requests, obj.requests);
363  std::swap(bids, obj.bids);
364  std::swap(alloc_strategy, obj.alloc_strategy);
365  }
366 
367  //! \}
368 
369  //! \name Constructors/Destructors
370  //! \{
371 
372  //! Copy-construction from a another stack of any type.
373  //! \param stack_ stack object (could be external or internal, important is that it must
374  //! have a copy constructor, \c top() and \c pop() methods )
375  template <class StackType>
376  grow_shrink_stack(const StackType& stack_)
377  : m_size(0),
378  cache_offset(0),
379  current_element(NULL),
380  cache(blocks_per_page * 2),
381  cache_buffers(cache.begin()),
382  overlap_buffers(cache.begin() + blocks_per_page),
383  requests(blocks_per_page),
384  bids(0)
385  {
386  bids.reserve(blocks_per_page);
387 
388  StackType stack_copy = stack_;
389  size_t sz = stack_copy.size();
390 
391  std::vector<value_type> tmp(sz);
392 
393  for (size_t i = 0; i < sz; ++i)
394  {
395  tmp[sz - i - 1] = stack_copy.top();
396  stack_copy.pop();
397  }
398 
399  for (size_t i = 0; i < sz; ++i)
400  push(tmp[i]);
401  }
403  {
405  try
406  {
407  if (requests[0].get())
408  wait_all(requests.begin(), blocks_per_page);
409  }
410  catch (const io_error&)
411  { }
412  block_manager::get_instance()->delete_blocks(bids.begin(), bids.end());
413  }
414 
415  //! \}
416 
417  //! \name Capacity
418  //! \{
419 
420  //! Returns the number of elements contained in the stack
421  size_type size() const
422  {
423  return m_size;
424  }
425  //! Returns true if the stack is empty.
426  bool empty() const
427  {
428  return (!m_size);
429  }
430 
431  //! \}
432 
433  //! \name Accessor Functions
434  //! \{
435 
436  //! Return mutable reference to the element at the top of the
437  //! stack. Precondition: stack is not empty().
439  {
440  assert(m_size > 0);
441  return (*current_element);
442  }
443 
444  //! Return constant reference to the element at the top of the
445  //! stack. Precondition: stack is not empty().
446  const value_type & top() const
447  {
448  assert(m_size > 0);
449  return (*current_element);
450  }
451 
452  //! Inserts an element at the top of the stack. Postconditions: size() is
453  //! incremented by 1, and top() is the inserted element.
454  void push(const value_type& val)
455  {
456  assert(cache_offset <= blocks_per_page * block_type::size);
457  //assert(cache_offset >= 0);
458 
459  if (UNLIKELY(cache_offset == blocks_per_page * block_type::size)) // cache overflow
460  {
461  STXXL_VERBOSE2("growing, size: " << m_size);
462 
463  bids.resize(bids.size() + blocks_per_page);
464  typename std::vector<bid_type>::iterator cur_bid = bids.end() - blocks_per_page;
465  block_manager::get_instance()->new_blocks(alloc_strategy, cur_bid, bids.end(), cur_bid - bids.begin());
466 
467  for (int i = 0; i < blocks_per_page; ++i, ++cur_bid)
468  {
469  if (requests[i].get())
470  requests[i]->wait();
471 
472  requests[i] = (cache_buffers + i)->write(*cur_bid);
473  }
474 
475  std::swap(cache_buffers, overlap_buffers);
476 
477  bids.reserve(bids.size() + blocks_per_page);
478 
479  cache_offset = 1;
480  current_element = &((*cache_buffers)[0]);
481  ++m_size;
482 
483  *current_element = val;
484 
485  return;
486  }
487 
488  current_element = &((*(cache_buffers + cache_offset / block_type::size))[cache_offset % block_type::size]);
489  *current_element = val;
490  ++m_size;
491  ++cache_offset;
492  }
493 
494  //! Removes the element at the top of the stack. Precondition: stack is not
495  //! empty(). Postcondition: size() is decremented.
496  void pop()
497  {
498  assert(cache_offset <= blocks_per_page * block_type::size);
499  assert(cache_offset > 0);
500  assert(m_size > 0);
501 
502  if (UNLIKELY(cache_offset == 1 && bids.size() >= blocks_per_page))
503  {
504  STXXL_VERBOSE2("shrinking, size: " << m_size);
505 
506  if (requests[0].get())
507  wait_all(requests.begin(), blocks_per_page);
508 
509  std::swap(cache_buffers, overlap_buffers);
510 
511  if (bids.size() > blocks_per_page)
512  {
513  STXXL_VERBOSE2("prefetching, size: " << m_size);
514  typename std::vector<bid_type>::const_iterator cur_bid = bids.end() - blocks_per_page;
515  for (int i = blocks_per_page - 1; i >= 0; --i)
516  requests[i] = (overlap_buffers + i)->read(*(--cur_bid));
517  }
518 
519  block_manager::get_instance()->delete_blocks(bids.end() - blocks_per_page, bids.end());
520  bids.resize(bids.size() - blocks_per_page);
521 
522  cache_offset = blocks_per_page * block_type::size;
523  --m_size;
524  current_element = &((*(cache_buffers + (blocks_per_page - 1)))[block_type::size - 1]);
525 
526  return;
527  }
528 
529  --m_size;
530  unsigned_type cur_offset = (--cache_offset) - 1;
531  current_element = &((*(cache_buffers + cur_offset / block_type::size))[cur_offset % block_type::size]);
532  }
533 
534  //! \}
535 };
536 
537 //! Efficient implementation that uses prefetching and overlapping using (shared) buffers pools.
538 //! \warning This is a single buffer stack! Each direction change (push() followed by pop() or vice versa) may cause one I/O.
539 template <class StackConfig>
541 {
542 public:
543  typedef StackConfig cfg;
544  //! type of the elements stored in the stack
545  typedef typename cfg::value_type value_type;
546  typedef typename cfg::alloc_strategy alloc_strategy_type;
547  //! type for sizes (64-bit)
548  typedef typename cfg::size_type size_type;
549  enum {
550  blocks_per_page = cfg::blocks_per_page, // stack of this type has only one page
551  block_size = cfg::block_size
552  };
553 
554  //! type of block used in disk-memory transfers
557 
558 private:
560 
564  std::vector<bid_type> bids;
569 
570 public:
571  //! \name Constructors/Destructors
572  //! \{
573 
574  //! Default constructor: creates empty stack. The stack will use the
575  //! read_write_pool for prefetching and buffered writing.
576  //! \param pool_ block write/prefetch pool
577  //! \param prefetch_aggressiveness number of blocks that will be used from prefetch pool
579  unsigned_type prefetch_aggressiveness = 0)
580  : m_size(0),
581  cache_offset(0),
582  cache(new block_type),
583  pref_aggr(prefetch_aggressiveness),
584  owned_pool(NULL),
585  pool(&pool_)
586  {
587  STXXL_VERBOSE2("grow_shrink_stack2::grow_shrink_stack2(...)");
588  }
589 
590  //! Default constructor: creates empty stack. The stack will use the pair
591  //! of prefetch_pool and write_pool for prefetching and buffered writing.
592  //! This constructor is deprecated in favor of the read_write_pool
593  //! constructor.
594  //!
595  //! \param p_pool_ prefetch pool, that will be used for block prefetching
596  //! \param w_pool_ write pool, that will be used for block writing
597  //! \param prefetch_aggressiveness number of blocks that will be used from prefetch pool
600  write_pool<block_type>& w_pool_,
601  unsigned_type prefetch_aggressiveness = 0)
602  )
603  : m_size(0),
604  cache_offset(0),
605  cache(new block_type),
606  pref_aggr(prefetch_aggressiveness),
607  owned_pool(new pool_type(p_pool_, w_pool_)),
608  pool(owned_pool)
609  {
610  STXXL_VERBOSE2("grow_shrink_stack2::grow_shrink_stack2(...)");
611  }
612 
613  //! \}
614 
615  //! \name Accessor Functions
616  //! \{
617 
619  {
620  std::swap(m_size, obj.m_size);
621  std::swap(cache_offset, obj.cache_offset);
622  std::swap(cache, obj.cache);
623  std::swap(bids, obj.bids);
624  std::swap(alloc_strategy, obj.alloc_strategy);
625  std::swap(pref_aggr, obj.pref_aggr);
626  std::swap(owned_pool, obj.owned_pool);
627  std::swap(pool, obj.pool);
628  }
629 
630  //! \}
631 
632  //! \name Constructors/Destructors
633  //! \{
634 
636  {
637  try
638  {
639  STXXL_VERBOSE2("grow_shrink_stack2::~grow_shrink_stack2()");
640  const int_type bids_size = bids.size();
641  const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr), (int_type)0);
642  int_type i;
643  for (i = bids_size - 1; i >= last_pref; --i)
644  {
645  // clean the prefetch buffer
646  pool->invalidate(bids[i]);
647  }
648  typename std::vector<bid_type>::iterator cur = bids.begin();
649  typename std::vector<bid_type>::const_iterator end = bids.end();
650  for ( ; cur != end; ++cur)
651  {
652  // FIXME: read_write_pool needs something like cancel_write(bid)
653  block_type* b = NULL; // w_pool.steal(*cur);
654  if (b)
655  {
656  pool->add(cache); // return buffer
657  cache = b;
658  }
659  }
660  delete cache;
661  }
662  catch (const io_error&)
663  { }
664  block_manager::get_instance()->delete_blocks(bids.begin(), bids.end());
665  delete owned_pool;
666  }
667 
668  //! \}
669 
670  //! \name Capacity
671  //! \{
672 
673  //! Returns the number of elements contained in the stack
674  size_type size() const
675  {
676  return m_size;
677  }
678  //! Returns true if the stack is empty.
679  bool empty() const
680  {
681  return (!m_size);
682  }
683 
684  //! \}
685 
686  //! \name Accessor Functions
687  //! \{
688 
689  //! Inserts an element at the top of the stack. Postconditions: size() is
690  //! incremented by 1, and top() is the inserted element.
691  void push(const value_type& val)
692  {
693  STXXL_VERBOSE3("grow_shrink_stack2::push(" << val << ")");
694  assert(cache_offset <= block_type::size);
695 
696  if (UNLIKELY(cache_offset == block_type::size))
697  {
698  STXXL_VERBOSE2("grow_shrink_stack2::push(" << val << ") growing, size: " << m_size);
699 
700  bids.resize(bids.size() + 1);
701  typename std::vector<bid_type>::iterator cur_bid = bids.end() - 1;
702  block_manager::get_instance()->new_blocks(alloc_strategy, cur_bid, bids.end(), cur_bid - bids.begin());
703  pool->write(cache, bids.back());
704  cache = pool->steal();
705  const int_type bids_size = bids.size();
706  const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr) - 1, (int_type)0);
707  for (int_type i = bids_size - 2; i >= last_pref; --i)
708  {
709  // clean prefetch buffers
710  pool->invalidate(bids[i]);
711  }
712  cache_offset = 0;
713  }
714  (*cache)[cache_offset] = val;
715  ++m_size;
716  ++cache_offset;
717 
718  assert(cache_offset > 0);
719  assert(cache_offset <= block_type::size);
720  }
721 
722  //! Return mutable reference to the element at the top of the
723  //! stack. Precondition: stack is not empty().
725  {
726  assert(m_size > 0);
727  assert(cache_offset > 0);
728  assert(cache_offset <= block_type::size);
729  return (*cache)[cache_offset - 1];
730  }
731 
732  //! Return constant reference to the element at the top of the
733  //! stack. Precondition: stack is not empty().
734  const value_type & top() const
735  {
736  assert(m_size > 0);
737  assert(cache_offset > 0);
738  assert(cache_offset <= block_type::size);
739  return (*cache)[cache_offset - 1];
740  }
741 
742  //! Removes the element at the top of the stack. Precondition: stack is not
743  //! empty(). Postcondition: size() is decremented.
744  void pop()
745  {
746  STXXL_VERBOSE3("grow_shrink_stack2::pop()");
747  assert(m_size > 0);
748  assert(cache_offset > 0);
749  assert(cache_offset <= block_type::size);
750  if (UNLIKELY(cache_offset == 1 && (!bids.empty())))
751  {
752  STXXL_VERBOSE2("grow_shrink_stack2::pop() shrinking, size = " << m_size);
753 
754  bid_type last_block = bids.back();
755  bids.pop_back();
756  pool->read(cache, last_block)->wait();
757  block_manager::get_instance()->delete_block(last_block);
758  rehint();
759  cache_offset = block_type::size + 1;
760  }
761 
762  --cache_offset;
763  --m_size;
764  }
765 
766  //! \}
767 
768  //! \name Miscellaneous
769  //! \{
770 
771  //! Sets level of prefetch aggressiveness (number of blocks from the
772  //! prefetch pool used for prefetching).
773  //! \param new_p new value for the prefetch aggressiveness
775  {
776  if (pref_aggr > new_p)
777  {
778  const int_type bids_size = bids.size();
779  const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr), (int_type)0);
780  for (int_type i = bids_size - new_p - 1; i >= last_pref; --i)
781  {
782  // clean prefetch buffers
783  pool->invalidate(bids[i]);
784  }
785  }
786  pref_aggr = new_p;
787  rehint();
788  }
789 
790  //! Returns number of blocks used for prefetching.
792  {
793  return pref_aggr;
794  }
795 
796  //! \}
797 
798 private:
799  //! hint the last pref_aggr external blocks.
800  void rehint()
801  {
802  const int_type bids_size = bids.size();
803  const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr), (int_type)0);
804  for (int_type i = bids_size - 1; i >= last_pref; --i)
805  {
806  pool->hint(bids[i]); // prefetch
807  }
808  }
809 };
810 
811 //! A stack that migrates from internal memory to external when its size exceeds a certain threshold.
812 //!
813 //! For semantics of the methods see documentation of the STL \c std::stack.
814 template <unsigned_type CritSize, class ExternalStack, class InternalStack>
816 {
817 public:
818  typedef typename ExternalStack::cfg cfg;
819  //! type of the elements stored in the stack
820  typedef typename cfg::value_type value_type;
821  //! type for sizes (64-bit)
822  typedef typename cfg::size_type size_type;
823  enum {
824  blocks_per_page = cfg::blocks_per_page,
825  block_size = cfg::block_size
826  };
827 
828  typedef InternalStack int_stack_type;
829  typedef ExternalStack ext_stack_type;
830 
831 private:
832  enum { critical_size = CritSize };
833 
836 
837  //! Copy-construction from a another stack of any type.
838  //! \warning not implemented yet!
839  template <class StackType>
840  migrating_stack(const StackType& stack_);
841 
842 public:
843  //! \name Constructors/Destructors
844  //! \{
845 
846  //! Default constructor: creates empty stack.
848  : int_impl(new int_stack_type()), ext_impl(NULL)
849  { }
850 
852  {
853  delete int_impl;
854  delete ext_impl;
855  }
856 
857  //! \}
858 
859  //! \name Accessor Functions
860  //! \{
861 
863  {
864  std::swap(int_impl, obj.int_impl);
865  std::swap(ext_impl, obj.ext_impl);
866  }
867 
868  //! \}
869 
870  //! \name Miscellaneous
871  //! \{
872 
873  //! Returns true if current implementation is internal, otherwise false.
874  bool internal() const
875  {
876  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
877  return (int_impl != NULL);
878  }
879  //! Returns true if current implementation is external, otherwise false.
880  bool external() const
881  {
882  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
883  return (ext_impl != NULL);
884  }
885 
886  //! \}
887 
888  //! \name Capacity
889  //! \{
890 
891  //! Returns true if the stack is empty.
892  bool empty() const
893  {
894  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
895  return (int_impl) ? int_impl->empty() : ext_impl->empty();
896  }
897  //! Returns the number of elements contained in the stack
898  size_type size() const
899  {
900  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
901  return (int_impl) ? size_type(int_impl->size()) : ext_impl->size();
902  }
903 
904  //! \}
905 
906  //! \name Accessor Functions
907  //! \{
908 
909  //! Return mutable reference to the element at the top of the
910  //! stack. Precondition: stack is not empty().
912  {
913  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
914  return (int_impl) ? int_impl->top() : ext_impl->top();
915  }
916 
917  //! Return constant reference to the element at the top of the
918  //! stack. Precondition: stack is not empty().
919  const value_type & top() const
920  {
921  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
922  return (int_impl) ? int_impl->top() : ext_impl->top();
923  }
924 
925  //! Inserts an element at the top of the stack. Postconditions: size() is
926  //! incremented by 1, and top() is the inserted element.
927  void push(const value_type& val)
928  {
929  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
930 
931  if (int_impl)
932  {
933  int_impl->push(val);
934  if (UNLIKELY(int_impl->size() == critical_size))
935  {
936  // migrate to external stack
937  ext_impl = new ext_stack_type(*int_impl);
938  delete int_impl;
939  int_impl = NULL;
940  }
941  }
942  else
943  ext_impl->push(val);
944  }
945 
946  //! Removes the element at the top of the stack. Precondition: stack is not
947  //! empty(). Postcondition: size() is decremented.
948  void pop()
949  {
950  assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
951 
952  if (int_impl)
953  int_impl->pop();
954  else
955  ext_impl->pop();
956  }
957 
958  //! \}
959 };
960 
963 
964 //! Stack type generator \n
965 //! <b> Introduction </b> to stack container: see \ref tutorial_stack tutorial. \n
966 //! <b> Design and Internals </b> of stack container: see \ref design_stack.
967 //!
968 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
969 //!
970 //! \tparam Externality selects stack implementation, default: \b external. One of
971 //! - \c external, external container, implementation is chosen according to \c Behaviour parameter.
972 //! - \c migrating, migrates from internal implementation given by \c IntStackType parameter
973 //! to external implementation given by \c Behaviour parameter when size exceeds \c MigrCritSize
974 //! - \c internal, choses \c IntStackType implementation
975 //!
976 //! \tparam Behaviour chooses \b external implementation, default: \b stxxl::normal_stack. One of:
977 //! - \c normal, conservative version, implemented in \c stxxl::normal_stack
978 //! - \c grow_shrink, efficient version, implemented in \c stxxl::grow_shrink_stack
979 //! - \c grow_shrink2, efficient version, implemented in \c stxxl::grow_shrink_stack2
980 //!
981 //! \tparam BlocksPerPage defines how many blocks has one page of internal cache of an
982 //! \b external implementation, default is \b 4. All \b external implementations have
983 //! \b two pages.
984 //!
985 //! \tparam BlockSize external block size in bytes, default is <b>2 MiB</b>.
986 //!
987 //! \tparam IntStackType type of internal stack used for some implementations, default: \b std::stack.
988 //!
989 //! \tparam MigrCritSize threshold value for number of elements when
990 //! stxxl::migrating_stack migrates to the external memory, default: <b>2 x BlocksPerPage x BlockSize</b>.
991 //!
992 //! \tparam AllocStr one of allocation strategies: striping, RC, SR, or FR. Default is \b RC.
993 //!
994 //! \tparam SizeType size type, default is \b stxxl::uint64.
995 //!
996 //! The configured stack type is available as STACK_GENERATOR<>::result.
997 //!
998 template <
999  class ValueType,
1000  stack_externality Externality = external,
1001  stack_behaviour Behaviour = normal,
1002  unsigned BlocksPerPage = 4,
1003  unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
1004 
1005  class IntStackType = std::stack<ValueType>,
1006  unsigned_type MigrCritSize = (2* BlocksPerPage* BlockSize),
1007 
1008  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
1009  class SizeType = stxxl::uint64
1010  >
1012 {
1014 
1015  typedef typename IF<Behaviour == grow_shrink,
1019  typedef typename IF<Externality == migrating,
1021 
1022 public:
1024 };
1025 
1026 //! \}
1027 
1029 
1030 namespace std {
1031 
1032 template <class StackConfig>
1035 {
1036  a.swap(b);
1037 }
1038 
1039 template <class StackConfig>
1042 {
1043  a.swap(b);
1044 }
1045 
1046 template <class StackConfig>
1049 {
1050  a.swap(b);
1051 }
1052 
1053 template <stxxl::unsigned_type CritSize, class ExternalStack, class InternalStack>
1056 {
1057  a.swap(b);
1058 }
1059 
1060 } // namespace std
1061 
1062 #endif // !STXXL_CONTAINERS_STACK_HEADER
1063 // vim: et:ts=4:sw=4
cfg::size_type size_type
type for sizes (64-bit)
Definition: stack.h:548
#define STXXL_VERBOSE(x)
Definition: verbose.h:116
simple_vector< block_type >::iterator front_page
Definition: stack.h:84
void swap(normal_stack &obj)
Definition: stack.h:109
External stack container. Introduction to stack container: see STXXL Stack tutorial. Design and Internals of stack container: see Stack Conservative implementation. Fits best if your access pattern consists of irregularly mixed push&#39;es and pop&#39;s. For semantics of the methods see documentation of the STL std::stack. To gain full bandwidth of disks StackConfig::BlocksPerPage must &gt;= number of disks
Definition: stack.h:61
#define STXXL_DEFAULT_BLOCK_SIZE(type)
value_type * current_element
Definition: stack.h:323
std::vector< bid_type > bids
Definition: stack.h:564
simple_vector< block_type > cache
Definition: stack.h:83
A stack that migrates from internal memory to external when its size exceeds a certain threshold...
Definition: stack.h:815
virtual ~migrating_stack()
Definition: stack.h:851
cfg::size_type size_type
type for sizes (64-bit)
Definition: stack.h:822
simple_vector< block_type >::iterator cache_buffers
Definition: stack.h:325
StackConfig cfg
Definition: stack.h:305
void push(const value_type &val)
Inserts an element at the top of the stack. Postconditions: size() is incremented by 1...
Definition: stack.h:454
value_type & top()
Return mutable reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:185
IF< Externality==migrating, migrating_stack< MigrCritSize, ExtStackType, IntStackType >, ExtStackType >::result MigrOrNotStackType
Definition: stack.h:1020
stack_config_generator< ValueType, BlocksPerPage, BlockSize, AllocStr, SizeType > cfg
Definition: stack.h:1013
cfg::alloc_strategy alloc_strategy_type
Definition: stack.h:67
unsigned long long int uint64
Definition: types.h:39
virtual ~normal_stack()
Definition: stack.h:155
IF< Behaviour==grow_shrink, grow_shrink_stack< cfg >, grow_shrink_stack2< cfg > >::result GrShrTp
Definition: stack.h:1017
grow_shrink_stack(const StackType &stack_)
Copy-construction from a another stack of any type.
Definition: stack.h:376
BID< block_size > bid_type
Definition: stack.h:556
bool external() const
Returns true if current implementation is external, otherwise false.
Definition: stack.h:880
size_type size() const
Returns the number of elements contained in the stack.
Definition: stack.h:898
alloc_strategy_type alloc_strategy
Definition: stack.h:329
stack_behaviour
Definition: stack.h:962
value_type * element(unsigned_type offset)
Definition: stack.h:286
BID< block_size > bid_type
Definition: stack.h:318
virtual ~grow_shrink_stack2()
Definition: stack.h:635
void push(const value_type &val)
Inserts an element at the top of the stack. Postconditions: size() is incremented by 1...
Definition: stack.h:201
value_type & top()
Return mutable reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:724
cfg::alloc_strategy alloc_strategy_type
Definition: stack.h:546
#define STXXL_DEFAULT_ALLOC_STRATEGY
Definition: block_alloc.h:258
size_type size() const
Returns the number of elements contained in the stack.
Definition: stack.h:167
size_type size() const
Returns the number of elements contained in the stack.
Definition: stack.h:421
migrating_stack()
Default constructor: creates empty stack.
Definition: stack.h:847
#define STXXL_VERBOSE2(x)
Definition: verbose.h:121
cfg::value_type value_type
type of the elements stored in the stack
Definition: stack.h:307
cfg::alloc_strategy alloc_strategy_type
Definition: stack.h:308
#define STXXL_DEPRECATED(x)
Definition: deprecated.h:30
typed_block< block_size, value_type > block_type
type of block used in disk-memory transfers
Definition: stack.h:76
alloc_strategy_type alloc_strategy
Definition: stack.h:87
void set_prefetch_aggr(unsigned_type new_p)
Sets level of prefetch aggressiveness (number of blocks from the prefetch pool used for prefetching)...
Definition: stack.h:774
unsigned_type pref_aggr
Definition: stack.h:566
ext_stack_type * ext_impl
Definition: stack.h:835
const value_type & top() const
Return constant reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:193
void pop()
Removes the element at the top of the stack. Precondition: stack is not empty(). Postcondition: size(...
Definition: stack.h:948
IF< Externality==internal, IntStackType, MigrOrNotStackType >::result result
Definition: stack.h:1023
typed_block< block_size, value_type > block_type
type of block used in disk-memory transfers
Definition: stack.h:555
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:32
stack_externality
Definition: stack.h:961
simple_vector< block_type > cache
Definition: stack.h:324
simple_vector< block_type >::iterator back_page
Definition: stack.h:85
const value_type & top() const
Return constant reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:446
Implements dynamically resizable prefetching pool.
Definition: prefetch_pool.h:29
Block containing elements of fixed length.
Definition: typed_block.h:237
int_stack_type * int_impl
Definition: stack.h:834
value_type * current_element
Definition: stack.h:82
std::vector< bid_type > bids
Definition: stack.h:328
#define STXXL_VERBOSE3(x)
Definition: verbose.h:127
bool empty() const
Returns true if the stack is empty.
Definition: stack.h:173
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
void swap(grow_shrink_stack2 &obj)
Definition: stack.h:618
iterator begin()
return mutable iterator to first element
Definition: simple_vector.h:94
void swap(grow_shrink_stack &obj)
Definition: stack.h:354
grow_shrink_stack2(pool_type &pool_, unsigned_type prefetch_aggressiveness=0)
Default constructor: creates empty stack. The stack will use the read_write_pool for prefetching and ...
Definition: stack.h:578
#define UNLIKELY(c)
Definition: utils.h:225
const Type & STXXL_MAX(const Type &a, const Type &b)
Definition: utils.h:153
std::vector< bid_type > bids
Definition: stack.h:86
virtual ~grow_shrink_stack()
Definition: stack.h:402
bool empty() const
Returns true if the stack is empty.
Definition: stack.h:679
ExternalStack::cfg cfg
Definition: stack.h:818
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
void push(const value_type &val)
Inserts an element at the top of the stack. Postconditions: size() is incremented by 1...
Definition: stack.h:927
pool_type * pool
Definition: stack.h:568
read_write_pool< block_type > pool_type
Definition: stack.h:559
void rehint()
hint the last pref_aggr external blocks.
Definition: stack.h:800
unsigned_type get_prefetch_aggr() const
Returns number of blocks used for prefetching.
Definition: stack.h:791
cfg::value_type value_type
type of the elements stored in the stack
Definition: stack.h:66
void pop()
Removes the element at the top of the stack. Precondition: stack is not empty(). Postcondition: size(...
Definition: stack.h:496
const value_type & top() const
Return constant reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:919
bool empty() const
Returns true if the stack is empty.
Definition: stack.h:892
pool_type * owned_pool
Definition: stack.h:567
cfg::size_type size_type
type for sizes (64-bit)
Definition: stack.h:310
const value_type & top() const
Return constant reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:734
normal_stack()
Default constructor: creates empty stack.
Definition: stack.h:94
bool empty() const
Returns true if the stack is empty.
Definition: stack.h:426
Efficient implementation that uses prefetching and overlapping using (shared) buffers pools...
Definition: stack.h:540
size_type size() const
Returns the number of elements contained in the stack.
Definition: stack.h:674
Simpler non-growing vector without initialization.
Definition: simple_vector.h:39
unsigned_type cache_offset
Definition: stack.h:81
BID< block_size > bid_type
Definition: stack.h:77
size_type m_size
Definition: stack.h:80
void wait_all(RequestIterator reqs_begin, RequestIterator reqs_end)
Collection of functions to track statuses of a number of requests.
alloc_strategy_type alloc_strategy
Definition: stack.h:565
simple_vector< request_ptr > requests
Definition: stack.h:327
normal_stack(const StackType &stack_)
Copy-construction from a another stack of any type.
Definition: stack.h:130
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
value_type & top()
Return mutable reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:438
value_type & top()
Return mutable reference to the element at the top of the stack. Precondition: stack is not empty()...
Definition: stack.h:911
Type1 result
Definition: tmeta.h:32
unsigned_type cache_offset
Definition: stack.h:562
InternalStack int_stack_type
Definition: stack.h:828
Stack type generator Introduction to stack container: see STXXL Stack tutorial. Design and Internals of stack container: see Stack.
Definition: stack.h:1011
void swap(migrating_stack &obj)
Definition: stack.h:862
IF template metaprogramming statement.
Definition: tmeta.h:30
void pop()
Removes the element at the top of the stack. Precondition: stack is not empty(). Postcondition: size(...
Definition: stack.h:244
Efficient implementation that uses prefetching and overlapping using internal buffers.
Definition: stack.h:302
cfg::size_type size_type
type for sizes (64-bit)
Definition: stack.h:69
ExternalStack ext_stack_type
Definition: stack.h:829
cfg::value_type value_type
type of the elements stored in the stack
Definition: stack.h:820
cfg::value_type value_type
type of the elements stored in the stack
Definition: stack.h:545
block_type * cache
Definition: stack.h:563
value_type * iterator
Definition: simple_vector.h:55
simple_vector< block_type >::iterator overlap_buffers
Definition: stack.h:326
void push(const value_type &val)
Inserts an element at the top of the stack. Postconditions: size() is incremented by 1...
Definition: stack.h:691
typed_block< block_size, value_type > block_type
type of block used in disk-memory transfers
Definition: stack.h:317
grow_shrink_stack()
Default constructor: creates empty stack.
Definition: stack.h:336
#define STXXL_PRETTY_FUNCTION_NAME
StackConfig cfg
Definition: stack.h:64
void pop()
Removes the element at the top of the stack. Precondition: stack is not empty(). Postcondition: size(...
Definition: stack.h:744
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
unsigned_type cache_offset
Definition: stack.h:322
IF< Behaviour==normal, normal_stack< cfg >, GrShrTp >::result ExtStackType
Definition: stack.h:1018