Stxxl  1.2.1
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 <dementiev@ira.uka.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_QUEUE_HEADER
14 #define STXXL_QUEUE_HEADER
15 
16 #include <vector>
17 #include <queue>
18 #include <deque>
19 
20 #include <stxxl/bits/mng/mng.h>
21 #include <stxxl/bits/common/simple_vector.h>
22 #include <stxxl/bits/common/tmeta.h>
23 #include <stxxl/bits/mng/write_pool.h>
24 #include <stxxl/bits/mng/prefetch_pool.h>
25 
26 
27 __STXXL_BEGIN_NAMESPACE
28 
31 
32 
34 
40 template <class ValTp,
41  unsigned BlkSz = STXXL_DEFAULT_BLOCK_SIZE(ValTp),
42  class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
43  class SzTp = stxxl::uint64>
44 class queue : private noncopyable
45 {
46 public:
47  typedef ValTp value_type;
48  typedef AllocStr alloc_strategy;
49  typedef SzTp size_type;
50  enum {
51  block_size = BlkSz
52  };
53 
55  typedef BID<block_size> bid_type;
56 
57 private:
58  size_type size_;
59  bool delete_pools;
60  write_pool<block_type> * w_pool;
62  block_type * front_block;
63  block_type * back_block;
64  value_type * front_element;
65  value_type * back_element;
66  //alloc_strategy alloc_strategy_;
67  unsigned_type alloc_counter;
68  std::deque<bid_type> bids;
69  block_manager * bm;
70  unsigned_type blocks2prefetch;
71 
72 public:
74 
78  queue(unsigned_type w_pool_size, unsigned_type p_pool_size, unsigned_type blocks2prefetch_ = 1) :
79  size_(0),
80  delete_pools(true),
81  alloc_counter(0),
82  blocks2prefetch(blocks2prefetch_)
83  {
84  if (w_pool_size < 2)
85  w_pool_size = 2;
86 
87  if (p_pool_size < 1)
88  p_pool_size = 1;
89 
90  w_pool = new write_pool<block_type>(w_pool_size);
91  front_block = back_block = w_pool->steal();
92  back_element = back_block->elem - 1;
93  front_element = back_block->elem;
94  p_pool = new prefetch_pool<block_type>(p_pool_size);
95  bm = block_manager::get_instance();
96  }
97 
99 
105  queue(write_pool<block_type> & w_pool_, prefetch_pool<block_type> & p_pool_, unsigned blocks2prefetch_ = 1) :
106  size_(0),
107  delete_pools(false),
108  w_pool(&w_pool_),
109  p_pool(&p_pool_),
110  alloc_counter(0),
111  blocks2prefetch(blocks2prefetch_)
112  {
113  if (w_pool->size() < 2)
114  w_pool->resize(2);
115 
116  if (p_pool->size() < 2)
117  p_pool->resize(1);
118 
119  front_block = back_block = w_pool->steal();
120  back_element = back_block->elem - 1;
121  front_element = back_block->elem;
122  bm = block_manager::get_instance();
123  }
124 
126  void set_prefetch_aggr(unsigned_type blocks2prefetch_)
127  {
128  blocks2prefetch = blocks2prefetch_;
129  }
130 
132  unsigned_type get_prefetch_aggr() const
133  {
134  return blocks2prefetch;
135  }
136 
138  void push(const value_type & val)
139  {
140  if (back_element == back_block->elem + (block_type::size - 1))
141  {
142  // back block is filled
143  if (front_block == back_block)
144  { // can not write the back block because it
145  // is the same as the front block, must keep it memory
146  STXXL_VERBOSE1("queue::push Case 1");
147  }
148  else
149  {
150  STXXL_VERBOSE1("queue::push Case 2");
151  // write the back block
152  // need to allocate new block
153  bid_type newbid;
154 
155  offset_allocator<alloc_strategy> alloc_str(alloc_counter++);
156 
157  //bm->new_blocks<block_type>(1, alloc_str, &newbid);
158  bm->new_blocks(alloc_str, &newbid, (&newbid) + 1);
159 
160  bids.push_back(newbid);
161  w_pool->write(back_block, newbid);
162  }
163  back_block = w_pool->steal();
164 
165  back_element = back_block->elem;
166  *back_element = val;
167  ++size_;
168  return;
169  }
170  ++back_element;
171  *back_element = val;
172  ++size_;
173  }
174 
176  void pop()
177  {
178  assert(!empty());
179 
180  if (front_element == front_block->elem + (block_type::size - 1))
181  {
182  // if there is only one block, it implies ...
183  if (back_block == front_block)
184  {
185  STXXL_VERBOSE1("queue::pop Case 3");
186  assert(size() == 1);
187  assert(back_element == front_element);
188  assert(bids.empty());
189  // reset everything
190  back_element = back_block->elem - 1;
191  front_element = back_block->elem;
192  size_ = 0;
193  return;
194  }
195 
196  --size_;
197  if (size_ <= block_type::size)
198  {
199  STXXL_VERBOSE1("queue::pop Case 4");
200  assert(bids.empty());
201  // the back_block is the next block
202  w_pool->add(front_block);
203  front_block = back_block;
204  front_element = back_block->elem;
205  return;
206  }
207  STXXL_VERBOSE1("queue::pop Case 5");
208 
209  assert(!bids.empty());
210  request_ptr req = p_pool->read(front_block, bids.front());
211  for (unsigned_type i = 0; i < blocks2prefetch && i < bids.size() - 1; ++i)
212  { // give prefetching hints
213  STXXL_VERBOSE1("queue::pop Case Hints");
214  p_pool->hint(bids[i + 1], *w_pool);
215  }
216 
217  front_element = front_block->elem;
218  req->wait();
219 
220  bm->delete_block(bids.front());
221  bids.pop_front();
222  return;
223  }
224 
225  ++front_element;
226  --size_;
227  }
228 
230  size_type size() const
231  {
232  return size_;
233  }
234 
236  bool empty() const
237  {
238  return (size_ == 0);
239  }
240 
242  value_type & back()
243  {
244  assert(!empty());
245  return *back_element;
246  }
247 
249  const value_type & back() const
250  {
251  assert(!empty());
252  return *back_element;
253  }
254 
256  value_type & front()
257  {
258  assert(!empty());
259  return *front_element;
260  }
261 
263  const value_type & front() const
264  {
265  assert(!empty());
266  return *front_element;
267  }
268 
269  ~queue()
270  {
271  w_pool->add(front_block);
272  if (front_block != back_block)
273  w_pool->add(back_block);
274 
275 
276  if (delete_pools)
277  {
278  delete w_pool;
279  delete p_pool;
280  }
281 
282  if (!bids.empty())
283  bm->delete_blocks(bids.begin(), bids.end());
284  }
285 };
286 
288 
289 __STXXL_END_NAMESPACE
290 
291 #endif // !STXXL_QUEUE_HEADER