13 #ifndef STXXL_QUEUE_HEADER
14 #define STXXL_QUEUE_HEADER
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>
27 __STXXL_BEGIN_NAMESPACE
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
47 typedef ValTp value_type;
48 typedef AllocStr alloc_strategy;
49 typedef SzTp size_type;
64 value_type * front_element;
65 value_type * back_element;
67 unsigned_type alloc_counter;
68 std::deque<bid_type> bids;
70 unsigned_type blocks2prefetch;
78 queue(unsigned_type w_pool_size, unsigned_type p_pool_size, unsigned_type blocks2prefetch_ = 1) :
82 blocks2prefetch(blocks2prefetch_)
91 front_block = back_block = w_pool->
steal();
92 back_element = back_block->
elem - 1;
93 front_element = back_block->
elem;
95 bm = block_manager::get_instance();
111 blocks2prefetch(blocks2prefetch_)
113 if (w_pool->
size() < 2)
116 if (p_pool->
size() < 2)
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();
128 blocks2prefetch = blocks2prefetch_;
134 return blocks2prefetch;
138 void push(
const value_type & val)
143 if (front_block == back_block)
146 STXXL_VERBOSE1(
"queue::push Case 1");
150 STXXL_VERBOSE1(
"queue::push Case 2");
158 bm->
new_blocks(alloc_str, &newbid, (&newbid) + 1);
160 bids.push_back(newbid);
161 w_pool->
write(back_block, newbid);
163 back_block = w_pool->
steal();
165 back_element = back_block->
elem;
183 if (back_block == front_block)
185 STXXL_VERBOSE1(
"queue::pop Case 3");
187 assert(back_element == front_element);
188 assert(bids.empty());
190 back_element = back_block->
elem - 1;
191 front_element = back_block->
elem;
199 STXXL_VERBOSE1(
"queue::pop Case 4");
200 assert(bids.empty());
202 w_pool->add(front_block);
203 front_block = back_block;
204 front_element = back_block->
elem;
207 STXXL_VERBOSE1(
"queue::pop Case 5");
209 assert(!bids.empty());
211 for (unsigned_type i = 0; i < blocks2prefetch && i < bids.size() - 1; ++i)
213 STXXL_VERBOSE1(
"queue::pop Case Hints");
214 p_pool->
hint(bids[i + 1], *w_pool);
217 front_element = front_block->
elem;
245 return *back_element;
249 const value_type &
back()
const
252 return *back_element;
259 return *front_element;
266 return *front_element;
271 w_pool->add(front_block);
272 if (front_block != back_block)
273 w_pool->add(back_block);
289 __STXXL_END_NAMESPACE
291 #endif // !STXXL_QUEUE_HEADER