STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
queue.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/queue.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2005 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_QUEUE_HEADER
15 #define STXXL_CONTAINERS_QUEUE_HEADER
16 
17 #include <vector>
18 #include <queue>
19 #include <deque>
20 
21 #include <stxxl/bits/deprecated.h>
29 
31 
32 #ifndef STXXL_VERBOSE_QUEUE
33 #define STXXL_VERBOSE_QUEUE STXXL_VERBOSE2
34 #endif
35 
36 //! \addtogroup stlcont
37 //! \{
38 
39 //! External FIFO queue container. \n
40 //! <b> Introduction </b> to queue container: see \ref tutorial_queue tutorial\n
41 //! <b> Design and Internals </b> of queue container: see \ref design_queue.
42 //!
43 //! \tparam ValueType type of the contained objects (POD with no references to internal memory)
44 //! \tparam BlockSize size of the external memory block in bytes, default is \c STXXL_DEFAULT_BLOCK_SIZE(ValueType)
45 //! \tparam AllocStr parallel disk allocation strategy, default is \c STXXL_DEFAULT_ALLOC_STRATEGY
46 //! \tparam SizeType size data type, default is \c stxxl::uint64
47 template <class ValueType,
48  unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
49  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
50  class SizeType = stxxl::uint64>
51 class queue : private noncopyable
52 {
53 public:
54  typedef ValueType value_type;
55  typedef AllocStr alloc_strategy_type;
56  typedef SizeType size_type;
57  enum {
58  block_size = BlockSize
59  };
60 
63 
64 private:
66 
76  std::deque<bid_type> bids;
79 
80 public:
81  //! \name Constructors/Destructors
82  //! \{
83 
84  //! Constructs empty queue with own write and prefetch block pool.
85  //!
86  //! \param D number of parallel disks, defaulting to the configured number of scratch disks,
87  //! memory consumption will be 2 * D + 2 blocks
88  //! (first and last block, D blocks as write cache, D block for prefetching)
89  explicit queue(int_type D = -1)
90  : m_size(0),
91  delete_pool(true),
92  alloc_count(0),
93  bm(block_manager::get_instance())
94  {
95  if (D < 1)
96  D = config::get_instance()->disks_number();
97  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(D)");
98  pool = new pool_type(D, D + 2);
99  init();
100  }
101 
102  //! Constructs empty queue with own write and prefetch block pool.
103  //!
104  //! \param w_pool_size number of blocks in the write pool, must be at least 2, recommended at least 3
105  //! \param p_pool_size number of blocks in the prefetch pool, recommended at least 1
106  //! \param blocks2prefetch_ defines the number of blocks to prefetch (\c front side),
107  //! default is number of block in the prefetch pool
108  explicit queue(unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch_ = -1)
109  : m_size(0),
110  delete_pool(true),
111  alloc_count(0),
112  bm(block_manager::get_instance())
113  {
114  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(sizes)");
115  pool = new pool_type(p_pool_size, w_pool_size);
116  init(blocks2prefetch_);
117  }
118 
119  //! Constructs empty queue.
120  //!
121  //! \param w_pool write pool
122  //! \param p_pool prefetch pool
123  //! \param blocks2prefetch_ defines the number of blocks to prefetch (\c front side),
124  //! default is number of blocks in the prefetch pool
125  //! \warning Number of blocks in the write pool must be at least 2, recommended at least 3
126  //! \warning Number of blocks in the prefetch pool recommended at least 1
128  queue(write_pool<block_type>& w_pool, prefetch_pool<block_type>& p_pool, int blocks2prefetch_ = -1))
129  : m_size(0),
130  delete_pool(true),
131  alloc_count(0),
132  bm(block_manager::get_instance())
133  {
134  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(pools)");
135  pool = new pool_type(p_pool, w_pool);
136  init(blocks2prefetch_);
137  }
138 
139  //! Constructs empty queue.
140  //!
141  //! \param pool_ block write/prefetch pool
142  //! \param blocks2prefetch_ defines the number of blocks to prefetch (\c front side),
143  //! default is number of blocks in the prefetch pool
144  //! \warning Number of blocks in the write pool must be at least 2, recommended at least 3
145  //! \warning Number of blocks in the prefetch pool recommended at least 1
146  queue(pool_type& pool_, int blocks2prefetch_ = -1)
147  : m_size(0),
148  delete_pool(false),
149  pool(&pool_),
150  alloc_count(0),
151  bm(block_manager::get_instance())
152  {
153  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(pool)");
154  init(blocks2prefetch_);
155  }
156 
157  //! \}
158 
159  //! \name Modifiers
160  //! \{
161 
162  void swap(queue& obj)
163  {
164  std::swap(m_size, obj.m_size);
165  std::swap(delete_pool, obj.delete_pool);
166  std::swap(pool, obj.pool);
167  std::swap(front_block, obj.front_block);
168  std::swap(back_block, obj.back_block);
169  std::swap(front_element, obj.front_element);
170  std::swap(back_element, obj.back_element);
171  std::swap(alloc_strategy, obj.alloc_strategy);
172  std::swap(alloc_count, obj.alloc_count);
173  std::swap(bids, obj.bids);
174  std::swap(bm, obj.bm);
175  std::swap(blocks2prefetch, obj.blocks2prefetch);
176  }
177 
178  //! \}
179 
180 private:
181  void init(int blocks2prefetch_ = -1)
182  {
183  if (pool->size_write() < 2) {
184  STXXL_ERRMSG("queue: invalid configuration, not enough blocks (" << pool->size_write() <<
185  ") in write pool, at least 2 are needed, resizing to 3");
186  pool->resize_write(3);
187  }
188 
189  if (pool->size_write() < 3) {
190  STXXL_MSG("queue: inefficient configuration, no blocks for buffered writing available");
191  }
192 
193  if (pool->size_prefetch() < 1) {
194  STXXL_MSG("queue: inefficient configuration, no blocks for prefetching available");
195  }
196 
197  front_block = back_block = pool->steal();
198  back_element = back_block->begin() - 1;
199  front_element = back_block->begin();
200  set_prefetch_aggr(blocks2prefetch_);
201  }
202 
203 public:
204  //! \name Miscellaneous
205  //! \{
206 
207  //! Defines the number of blocks to prefetch (\c front side).
208  //! This method should be called whenever the prefetch pool is resized
209  //! \param blocks2prefetch_ defines the number of blocks to prefetch (\c front side),
210  //! a negative value means to use the number of blocks in the prefetch pool
211  void set_prefetch_aggr(int_type blocks2prefetch_)
212  {
213  if (blocks2prefetch_ < 0)
214  blocks2prefetch = pool->size_prefetch();
215  else
216  blocks2prefetch = blocks2prefetch_;
217  }
218 
219  //! Returns the number of blocks prefetched from the \c front side.
221  {
222  return blocks2prefetch;
223  }
224  //! \}
225 
226  //! \name Modifiers
227  //! \{
228 
229  //! Adds an element in the queue.
230  void push(const value_type& val)
231  {
232  if (UNLIKELY(back_element == back_block->begin() + (block_type::size - 1)))
233  {
234  // back block is filled
235  if (front_block == back_block)
236  { // can not write the back block because it
237  // is the same as the front block, must keep it memory
238  STXXL_VERBOSE1("queue::push Case 1");
239  }
240  else if (size() < 2 * block_type::size)
241  {
242  STXXL_VERBOSE1("queue::push Case 1.5");
243  // only two blocks with a gap in the beginning, move elements within memory
244  assert(bids.empty());
245  size_t gap = front_element - front_block->begin();
246  assert(gap > 0);
247  std::copy(front_element, front_block->end(), front_block->begin());
248  std::copy(back_block->begin(), back_block->begin() + gap, front_block->begin() + (block_type::size - gap));
249  std::copy(back_block->begin() + gap, back_block->end(), back_block->begin());
250  front_element -= gap;
251  back_element -= gap;
252 
253  ++back_element;
254  *back_element = val;
255  ++m_size;
256  return;
257  }
258  else
259  {
260  STXXL_VERBOSE1("queue::push Case 2");
261  // write the back block
262  // need to allocate new block
263  bid_type newbid;
264 
265  bm->new_block(alloc_strategy, newbid, alloc_count++);
266 
267  STXXL_VERBOSE_QUEUE("queue[" << this << "]: push block " << back_block << " @ " << FMT_BID(newbid));
268  bids.push_back(newbid);
269  pool->write(back_block, newbid);
270  if (bids.size() <= blocks2prefetch) {
271  STXXL_VERBOSE1("queue::push Case Hints");
272  pool->hint(newbid);
273  }
274  }
275  back_block = pool->steal();
276 
277  back_element = back_block->begin();
278  *back_element = val;
279  ++m_size;
280  return;
281  }
282  ++back_element;
283  *back_element = val;
284  ++m_size;
285  }
286 
287  //! Removes element from the queue.
288  void pop()
289  {
290  assert(!empty());
291 
292  if (UNLIKELY(front_element == front_block->begin() + (block_type::size - 1)))
293  {
294  // if there is only one block, it implies ...
295  if (back_block == front_block)
296  {
297  STXXL_VERBOSE1("queue::pop Case 3");
298  assert(size() == 1);
299  assert(back_element == front_element);
300  assert(bids.empty());
301  // reset everything
302  back_element = back_block->begin() - 1;
303  front_element = back_block->begin();
304  m_size = 0;
305  return;
306  }
307 
308  --m_size;
309  if (m_size <= block_type::size)
310  {
311  STXXL_VERBOSE1("queue::pop Case 4");
312  assert(bids.empty());
313  // the back_block is the next block
314  pool->add(front_block);
315  front_block = back_block;
316  front_element = back_block->begin();
317  return;
318  }
319  STXXL_VERBOSE1("queue::pop Case 5");
320 
321  assert(!bids.empty());
322  request_ptr req = pool->read(front_block, bids.front());
323  STXXL_VERBOSE_QUEUE("queue[" << this << "]: pop block " << front_block << " @ " << FMT_BID(bids.front()));
324 
325  // give prefetching hints
326  for (unsigned_type i = 0; i < blocks2prefetch && i < bids.size() - 1; ++i)
327  {
328  STXXL_VERBOSE1("queue::pop Case Hints");
329  pool->hint(bids[i + 1]);
330  }
331 
332  front_element = front_block->begin();
333  req->wait();
334 
335  bm->delete_block(bids.front());
336  bids.pop_front();
337  return;
338  }
339 
340  ++front_element;
341  --m_size;
342  }
343  //! \}
344 
345  //! \name Operators
346  //! \{
347 
348  //! Returns a mutable reference at the back of the queue.
350  {
351  assert(!empty());
352  return *back_element;
353  }
354 
355  //! Returns a const reference at the back of the queue.
356  const value_type & back() const
357  {
358  assert(!empty());
359  return *back_element;
360  }
361 
362  //! Returns a mutable reference at the front of the queue.
364  {
365  assert(!empty());
366  return *front_element;
367  }
368 
369  //! Returns a const reference at the front of the queue.
370  const value_type & front() const
371  {
372  assert(!empty());
373  return *front_element;
374  }
375 
376  //! \}
377 
378  //! \name Constructors/Destructors
379  //! \{
380 
382  {
383  if (front_block != back_block)
384  pool->add(back_block);
385  pool->add(front_block);
386 
387  if (delete_pool)
388  {
389  delete pool;
390  }
391 
392  if (!bids.empty())
393  bm->delete_blocks(bids.begin(), bids.end());
394  }
395 
396  //! \}
397 
398  //! \name Capacity
399  //! \{
400 
401  //! Returns the size of the queue.
402  size_type size() const
403  {
404  return m_size;
405  }
406 
407  //! Returns \c true if queue is empty.
408  bool empty() const
409  {
410  return (m_size == 0);
411  }
412 
413  //! \}
414 };
415 
416 //! \}
417 
419 
420 #endif // !STXXL_CONTAINERS_QUEUE_HEADER
421 // vim: et:ts=4:sw=4
const value_type & back() const
Returns a const reference at the back of the queue.
Definition: queue.h:356
queue(pool_type &pool_, int blocks2prefetch_=-1)
Constructs empty queue.
Definition: queue.h:146
#define STXXL_DEFAULT_BLOCK_SIZE(type)
value_type * back_element
Definition: queue.h:73
Block manager class.
Definition: block_manager.h:61
#define STXXL_VERBOSE_QUEUE
Definition: queue.h:33
void swap(queue &obj)
Definition: queue.h:162
unsigned_type alloc_count
Definition: queue.h:75
unsigned long long int uint64
Definition: types.h:39
alloc_strategy_type alloc_strategy
Definition: queue.h:74
bool empty() const
Returns true if queue is empty.
Definition: queue.h:408
External FIFO queue container. Introduction to queue container: see STXXL Queue tutorial Design a...
Definition: queue.h:51
typed_block< block_size, value_type > block_type
Definition: queue.h:61
#define STXXL_DEFAULT_ALLOC_STRATEGY
Definition: block_alloc.h:258
read_write_pool< block_type > pool_type
Definition: queue.h:65
queue(write_pool< block_type > &w_pool, prefetch_pool< block_type > &p_pool, int blocks2prefetch_=-1)
Constructs empty queue.
Definition: queue.h:128
block_type * front_block
Definition: queue.h:70
void push(const value_type &val)
Adds an element in the queue.
Definition: queue.h:230
SizeType size_type
Definition: queue.h:56
#define STXXL_DEPRECATED(x)
Definition: deprecated.h:30
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:32
value_type & front()
Returns a mutable reference at the front of the queue.
Definition: queue.h:363
size_type m_size
Definition: queue.h:67
Implements dynamically resizable prefetching pool.
Definition: prefetch_pool.h:29
Block containing elements of fixed length.
Definition: typed_block.h:237
AllocStr alloc_strategy_type
Definition: queue.h:55
const value_type & front() const
Returns a const reference at the front of the queue.
Definition: queue.h:370
BID< block_size > bid_type
Definition: queue.h:62
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
pool_type * pool
Definition: queue.h:69
value_type & back()
Returns a mutable reference at the back of the queue.
Definition: queue.h:349
#define UNLIKELY(c)
Definition: utils.h:225
value_type * front_element
Definition: queue.h:72
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
void init(int blocks2prefetch_=-1)
Definition: queue.h:181
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
size_type size() const
Returns the size of the queue.
Definition: queue.h:402
block_type * back_block
Definition: queue.h:71
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: queue.h:211
queue(unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch_=-1)
Constructs empty queue with own write and prefetch block pool.
Definition: queue.h:108
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
void pop()
Removes element from the queue.
Definition: queue.h:288
block_manager * bm
Definition: queue.h:77
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
unsigned_type blocks2prefetch
Definition: queue.h:78
#define STXXL_MSG(x)
Definition: verbose.h:73
std::deque< bid_type > bids
Definition: queue.h:76
queue(int_type D=-1)
Constructs empty queue with own write and prefetch block pool.
Definition: queue.h:89
ValueType value_type
Definition: queue.h:54
unsigned_type get_prefetch_aggr() const
Returns the number of blocks prefetched from the front side.
Definition: queue.h:220
#define FMT_BID(_bid_)
Definition: bid.h:30
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
bool delete_pool
Definition: queue.h:68