Stxxl  1.3.2
queue.h
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_QUEUE_HEADER
15 #define STXXL_QUEUE_HEADER
16 
17 #include <vector>
18 #include <queue>
19 #include <deque>
20 
21 #include <stxxl/bits/deprecated.h>
22 #include <stxxl/bits/mng/mng.h>
23 #include <stxxl/bits/mng/typed_block.h>
24 #include <stxxl/bits/common/simple_vector.h>
25 #include <stxxl/bits/common/tmeta.h>
26 #include <stxxl/bits/mng/read_write_pool.h>
27 #include <stxxl/bits/mng/write_pool.h>
28 #include <stxxl/bits/mng/prefetch_pool.h>
29 
30 
31 __STXXL_BEGIN_NAMESPACE
32 
33 #ifndef STXXL_VERBOSE_QUEUE
34 #define STXXL_VERBOSE_QUEUE STXXL_VERBOSE2
35 #endif
36 
39 
40 
42 
47 template <class ValTp,
48  unsigned BlkSz = STXXL_DEFAULT_BLOCK_SIZE(ValTp),
49  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
50  class SzTp = stxxl::uint64>
51 class queue : private noncopyable
52 {
53 public:
54  typedef ValTp value_type;
55  typedef AllocStr alloc_strategy_type;
56  typedef SzTp size_type;
57  enum {
58  block_size = BlkSz
59  };
60 
62  typedef BID<block_size> bid_type;
63 
64 private:
66 
67  size_type size_;
68  bool delete_pool;
69  pool_type * pool;
70  block_type * front_block;
71  block_type * back_block;
72  value_type * front_element;
73  value_type * back_element;
74  alloc_strategy_type alloc_strategy;
75  unsigned_type alloc_count;
76  std::deque<bid_type> bids;
77  block_manager * bm;
78  unsigned_type blocks2prefetch;
79 
80 public:
82 
87  explicit queue(unsigned_type w_pool_size = 3, unsigned_type p_pool_size = 1, int blocks2prefetch_ = -1) :
88  size_(0),
89  delete_pool(true),
90  alloc_count(0),
91  bm(block_manager::get_instance())
92  {
93  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(sizes)");
94  pool = new pool_type(p_pool_size, w_pool_size);
95  init(blocks2prefetch_);
96  }
97 
99 
107  queue(write_pool<block_type> & w_pool, prefetch_pool<block_type> & p_pool, int blocks2prefetch_ = -1)) :
108  size_(0),
109  delete_pool(true),
110  alloc_count(0),
111  bm(block_manager::get_instance())
112  {
113  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(pools)");
114  pool = new pool_type(w_pool, p_pool);
115  init(blocks2prefetch_);
116  }
117 
119 
125  queue(pool_type & pool_, int blocks2prefetch_ = -1) :
126  size_(0),
127  delete_pool(false),
128  pool(&pool_),
129  alloc_count(0),
130  bm(block_manager::get_instance())
131  {
132  STXXL_VERBOSE_QUEUE("queue[" << this << "]::queue(pool)");
133  init(blocks2prefetch_);
134  }
135 
136 private:
137  void init(int blocks2prefetch_)
138  {
139  if (pool->size_write() < 2) {
140  STXXL_ERRMSG("queue: invalid configuration, not enough blocks (" << pool->size_write() <<
141  ") in write pool, at least 2 are needed, resizing to 3");
142  pool->resize_write(3);
143  }
144 
145  if (pool->size_write() < 3) {
146  STXXL_MSG("queue: inefficient configuration, no blocks for buffered writing available");
147  }
148 
149  if (pool->size_prefetch() < 1) {
150  STXXL_MSG("queue: inefficient configuration, no blocks for prefetching available");
151  }
152 
153  front_block = back_block = pool->steal();
154  back_element = back_block->begin() - 1;
155  front_element = back_block->begin();
156  set_prefetch_aggr(blocks2prefetch_);
157  }
158 
159 public:
164  void set_prefetch_aggr(int_type blocks2prefetch_)
165  {
166  if (blocks2prefetch_ < 0)
167  blocks2prefetch = pool->size_prefetch();
168  else
169  blocks2prefetch = blocks2prefetch_;
170  }
171 
173  unsigned_type get_prefetch_aggr() const
174  {
175  return blocks2prefetch;
176  }
177 
179  void push(const value_type & val)
180  {
181  if (back_element == back_block->begin() + (block_type::size - 1))
182  {
183  // back block is filled
184  if (front_block == back_block)
185  { // can not write the back block because it
186  // is the same as the front block, must keep it memory
187  STXXL_VERBOSE1("queue::push Case 1");
188  }
189  else
190  {
191  STXXL_VERBOSE1("queue::push Case 2");
192  // write the back block
193  // need to allocate new block
194  bid_type newbid;
195 
196  bm->new_block(alloc_strategy, newbid, alloc_count++);
197 
198  STXXL_VERBOSE_QUEUE("queue[" << this << "]: push block " << back_block << " @ " << FMT_BID(newbid));
199  bids.push_back(newbid);
200  pool->write(back_block, newbid);
201  if (bids.size() <= blocks2prefetch) {
202  STXXL_VERBOSE1("queue::push Case Hints");
203  pool->hint(newbid);
204  }
205  }
206  back_block = pool->steal();
207 
208  back_element = back_block->begin();
209  *back_element = val;
210  ++size_;
211  return;
212  }
213  ++back_element;
214  *back_element = val;
215  ++size_;
216  }
217 
219  void pop()
220  {
221  assert(!empty());
222 
223  if (front_element == front_block->begin() + (block_type::size - 1))
224  {
225  // if there is only one block, it implies ...
226  if (back_block == front_block)
227  {
228  STXXL_VERBOSE1("queue::pop Case 3");
229  assert(size() == 1);
230  assert(back_element == front_element);
231  assert(bids.empty());
232  // reset everything
233  back_element = back_block->begin() - 1;
234  front_element = back_block->begin();
235  size_ = 0;
236  return;
237  }
238 
239  --size_;
240  if (size_ <= block_type::size)
241  {
242  STXXL_VERBOSE1("queue::pop Case 4");
243  assert(bids.empty());
244  // the back_block is the next block
245  pool->add(front_block);
246  front_block = back_block;
247  front_element = back_block->begin();
248  return;
249  }
250  STXXL_VERBOSE1("queue::pop Case 5");
251 
252  assert(!bids.empty());
253  request_ptr req = pool->read(front_block, bids.front());
254  STXXL_VERBOSE_QUEUE("queue[" << this << "]: pop block " << front_block << " @ " << FMT_BID(bids.front()));
255 
256  // give prefetching hints
257  for (unsigned_type i = 0; i < blocks2prefetch && i < bids.size() - 1; ++i)
258  {
259  STXXL_VERBOSE1("queue::pop Case Hints");
260  pool->hint(bids[i + 1]);
261  }
262 
263  front_element = front_block->begin();
264  req->wait();
265 
266  bm->delete_block(bids.front());
267  bids.pop_front();
268  return;
269  }
270 
271  ++front_element;
272  --size_;
273  }
274 
276  size_type size() const
277  {
278  return size_;
279  }
280 
282  bool empty() const
283  {
284  return (size_ == 0);
285  }
286 
288  value_type & back()
289  {
290  assert(!empty());
291  return *back_element;
292  }
293 
295  const value_type & back() const
296  {
297  assert(!empty());
298  return *back_element;
299  }
300 
302  value_type & front()
303  {
304  assert(!empty());
305  return *front_element;
306  }
307 
309  const value_type & front() const
310  {
311  assert(!empty());
312  return *front_element;
313  }
314 
315  ~queue()
316  {
317  pool->add(front_block);
318  if (front_block != back_block)
319  pool->add(back_block);
320 
321 
322  if (delete_pool)
323  {
324  delete pool;
325  }
326 
327  if (!bids.empty())
328  bm->delete_blocks(bids.begin(), bids.end());
329  }
330 };
331 
333 
334 __STXXL_END_NAMESPACE
335 
336 #endif // !STXXL_QUEUE_HEADER
337 // vim: et:ts=4:sw=4
queue(pool_type &pool_, int blocks2prefetch_=-1)
Constructs empty queue.
Definition: queue.h:125
Block containing elements of fixed length.
Definition: typed_block.h:223
number of elements in block
Definition: typed_block.h:240
value_type & back()
Returns a mutable reference at the back of the queue.
Definition: queue.h:288
value_type & front()
Returns a mutable reference at the front of the queue.
Definition: queue.h:302
bool empty() const
Returns true if queue is empty.
Definition: queue.h:282
Implements dynamically resizable prefetching pool.
Definition: prefetch_pool.h:34
iterator begin()
Returns iterator pointing to the first element.
Definition: typed_block.h:81
External FIFO queue container.
Definition: queue.h:51
const value_type & front() const
Returns a const reference at the front of the queue.
Definition: queue.h:309
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:36
Implements dynamically resizable buffered writing and prefetched reading pool.
Definition: read_write_pool.h:28
void resize_write(size_type new_size)
Resizes size of the pool.
Definition: read_write_pool.h:82
void delete_blocks(const BIDIteratorClass &bidbegin, const BIDIteratorClass &bidend)
Deallocates blocks.
Definition: mng.h:218
bool hint(bid_type bid)
Gives a hint for prefetching a block.
Definition: read_write_pool.h:135
size_type size() const
Returns the size of the queue.
Definition: queue.h:276
void push(const value_type &val)
Adds an element in the queue.
Definition: queue.h:179
unsigned_type get_prefetch_aggr() const
Returns the number of blocks prefetched from the front side.
Definition: queue.h:173
Implemented as reference counting smart pointer.
Definition: request_ptr.h:34
void new_block(const DiskAssignFunctor &functor, BID< BLK_SIZE > &bid, unsigned_type offset=0)
Definition: mng.h:131
request_ptr write(block_type *&block, bid_type bid)
Passes a block to the pool for writing.
Definition: read_write_pool.h:102
void delete_block(const BID< BLK_SIZE > &bid)
Deallocates a block.
Definition: mng.h:204
const value_type & back() const
Returns a const reference at the back of the queue.
Definition: queue.h:295
void set_prefetch_aggr(int_type blocks2prefetch_)
Defines the number of blocks to prefetch (front side) This method should be called whenever the prefe...
Definition: queue.h:164
request_ptr read(block_type *&block, bid_type bid)
Reads block. If this block is cached block is not read but passed from the cache. ...
Definition: read_write_pool.h:151
Block manager class.
Definition: mng.h:59
size_type size_prefetch() const
Returns number of blocks owned by the prefetch_pool.
Definition: read_write_pool.h:78
queue(unsigned_type w_pool_size=3, unsigned_type p_pool_size=1, int blocks2prefetch_=-1)
Constructs empty queue with own write and prefetch block pool.
Definition: queue.h:87
block_type * steal()
Take out a block from the pool.
Definition: read_write_pool.h:116
_STXXL_DEPRECATED(queue(write_pool< block_type > &w_pool, prefetch_pool< block_type > &p_pool, int blocks2prefetch_=-1))
Constructs empty queue.
Definition: queue.h:106
size_type size_write() const
Returns number of blocks owned by the write_pool.
Definition: read_write_pool.h:75
void pop()
Removes element from the queue.
Definition: queue.h:219
Block identifier class.
Definition: bid.h:40