14 #ifndef STXXL_QUEUE_HEADER
15 #define STXXL_QUEUE_HEADER
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>
31 __STXXL_BEGIN_NAMESPACE
33 #ifndef STXXL_VERBOSE_QUEUE
34 #define STXXL_VERBOSE_QUEUE STXXL_VERBOSE2
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
54 typedef ValTp value_type;
55 typedef AllocStr alloc_strategy_type;
56 typedef SzTp size_type;
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;
78 unsigned_type blocks2prefetch;
87 explicit queue(unsigned_type w_pool_size = 3, unsigned_type p_pool_size = 1,
int blocks2prefetch_ = -1) :
93 STXXL_VERBOSE_QUEUE(
"queue[" <<
this <<
"]::queue(sizes)");
94 pool =
new pool_type(p_pool_size, w_pool_size);
95 init(blocks2prefetch_);
113 STXXL_VERBOSE_QUEUE(
"queue[" <<
this <<
"]::queue(pools)");
115 init(blocks2prefetch_);
132 STXXL_VERBOSE_QUEUE(
"queue[" <<
this <<
"]::queue(pool)");
133 init(blocks2prefetch_);
137 void init(
int blocks2prefetch_)
140 STXXL_ERRMSG(
"queue: invalid configuration, not enough blocks (" << pool->
size_write() <<
141 ") in write pool, at least 2 are needed, resizing to 3");
146 STXXL_MSG(
"queue: inefficient configuration, no blocks for buffered writing available");
150 STXXL_MSG(
"queue: inefficient configuration, no blocks for prefetching available");
153 front_block = back_block = pool->
steal();
154 back_element = back_block->
begin() - 1;
155 front_element = back_block->
begin();
166 if (blocks2prefetch_ < 0)
169 blocks2prefetch = blocks2prefetch_;
175 return blocks2prefetch;
179 void push(
const value_type & val)
184 if (front_block == back_block)
187 STXXL_VERBOSE1(
"queue::push Case 1");
191 STXXL_VERBOSE1(
"queue::push Case 2");
196 bm->
new_block(alloc_strategy, newbid, alloc_count++);
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");
206 back_block = pool->
steal();
208 back_element = back_block->
begin();
226 if (back_block == front_block)
228 STXXL_VERBOSE1(
"queue::pop Case 3");
230 assert(back_element == front_element);
231 assert(bids.empty());
233 back_element = back_block->
begin() - 1;
234 front_element = back_block->
begin();
242 STXXL_VERBOSE1(
"queue::pop Case 4");
243 assert(bids.empty());
245 pool->add(front_block);
246 front_block = back_block;
247 front_element = back_block->
begin();
250 STXXL_VERBOSE1(
"queue::pop Case 5");
252 assert(!bids.empty());
254 STXXL_VERBOSE_QUEUE(
"queue[" <<
this <<
"]: pop block " << front_block <<
" @ " << FMT_BID(bids.front()));
257 for (unsigned_type i = 0; i < blocks2prefetch && i < bids.size() - 1; ++i)
259 STXXL_VERBOSE1(
"queue::pop Case Hints");
260 pool->
hint(bids[i + 1]);
263 front_element = front_block->
begin();
291 return *back_element;
295 const value_type &
back()
const
298 return *back_element;
305 return *front_element;
312 return *front_element;
317 pool->add(front_block);
318 if (front_block != back_block)
319 pool->add(back_block);
334 __STXXL_END_NAMESPACE
336 #endif // !STXXL_QUEUE_HEADER