http://stxxl.sourceforge.net
<bingmann@kit.edu>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_DEQUE2_HEADER
#define STXXL_DEQUE2_HEADER
#include <deque>
#include <stxxl/bits/deprecated.h>
#include <stxxl/bits/mng/mng.h>
#include <stxxl/bits/mng/typed_block.h>
#include <stxxl/bits/common/tmeta.h>
#include <stxxl/bits/mng/read_write_pool.h>
#include <stxxl/bits/mng/write_pool.h>
#include <stxxl/bits/mng/prefetch_pool.h>
__STXXL_BEGIN_NAMESPACE
#ifndef STXXL_VERBOSE_DEQUE2
#define STXXL_VERBOSE_DEQUE2 STXXL_VERBOSE2
#endif
template <class ValueType,
unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY,
class SizeType = stxxl::uint64>
class deque2 : private noncopyable
{
public:
typedef ValueType value_type;
typedef AllocStrategy alloc_strategy_type;
typedef SizeType size_type;
enum {
block_size = BlockSize
};
typedef typed_block<block_size, value_type> block_type;
typedef BID<block_size> bid_type;
typedef std::deque<bid_type> bid_deque_type;
private:
typedef read_write_pool<block_type> pool_type;
size_type m_size;
bool m_owns_pool;
pool_type* m_pool;
block_type* m_front_block;
block_type* m_back_block;
value_type * m_front_element;
value_type * m_back_element;
alloc_strategy_type m_alloc_strategy;
unsigned_type m_alloc_count;
bid_deque_type m_bids;
block_manager* m_bm;
unsigned_type m_blocks2prefetch;
public:
explicit deque2(int D = -1) :
m_size(0),
m_owns_pool(true),
m_alloc_count(0),
m_bm(block_manager::get_instance())
{
if (D < 1) D = config::get_instance()->disks_number();
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]::deque2(D)");
m_pool = new pool_type(D, D + 2);
init();
}
explicit deque2(unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch = -1) :
m_size(0),
m_owns_pool(true),
m_alloc_count(0),
m_bm(block_manager::get_instance())
{
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]::deque2(sizes)");
m_pool = new pool_type(p_pool_size, w_pool_size);
init(blocks2prefetch);
}
deque2(pool_type & pool, int blocks2prefetch = -1) :
m_size(0),
m_owns_pool(false),
m_pool(&pool),
m_alloc_count(0),
m_bm(block_manager::get_instance())
{
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]::deque2(pool)");
init(blocks2prefetch);
}
void swap(deque2& obj)
{
std::swap(m_size, obj.m_size);
std::swap(m_owns_pool, obj.m_owns_pool);
std::swap(m_pool, obj.m_pool);
std::swap(m_front_block, obj.m_front_block);
std::swap(m_back_block, obj.m_back_block);
std::swap(m_front_element, obj.m_front_element);
std::swap(m_back_element, obj.m_back_element);
std::swap(m_alloc_strategy, obj.m_alloc_strategy);
std::swap(m_alloc_count, obj.m_alloc_count);
std::swap(m_bids, obj.m_bids);
std::swap(m_bm, obj.m_bm);
std::swap(m_blocks2prefetch, obj.m_blocks2prefetch);
}
private:
void init(int blocks2prefetch = -1)
{
if (m_pool->size_write() < 2) {
STXXL_ERRMSG("deque2: invalid configuration, not enough blocks (" << m_pool->size_write() <<
") in write pool, at least 2 are needed, resizing to 3");
m_pool->resize_write(3);
}
if (m_pool->size_write() < 3) {
STXXL_MSG("deque2: inefficient configuration, no blocks for buffered writing available");
}
if (m_pool->size_prefetch() < 1) {
STXXL_MSG("deque2: inefficient configuration, no blocks for prefetching available");
}
m_front_block = m_back_block = m_pool->steal();
m_back_element = m_back_block->begin() - 1;
m_front_element = m_back_block->begin();
set_prefetch_aggr(blocks2prefetch);
}
public:
void set_prefetch_aggr(int_type blocks2prefetch)
{
if (blocks2prefetch < 0)
m_blocks2prefetch = m_pool->size_prefetch();
else
m_blocks2prefetch = blocks2prefetch;
}
unsigned_type get_prefetch_aggr() const
{
return m_blocks2prefetch;
}
void push_front(const value_type & val)
{
if (UNLIKELY(m_front_element == m_front_block->begin()))
{
if (m_size == 0)
{
STXXL_VERBOSE1("deque2::push_front Case 0");
assert(m_front_block == m_back_block);
m_front_element = m_back_element = m_front_block->end()-1;
*m_front_element = val;
++m_size;
return;
}
else if (m_front_block == m_back_block)
{
STXXL_VERBOSE1("deque2::push_front Case 1");
}
else if (size() < 2 * block_type::size)
{
STXXL_VERBOSE1("deque2::push_front Case 1.5");
assert(m_bids.empty());
size_t gap = m_back_block->end() - (m_back_element+1);
assert(gap > 0);
std::copy_backward(m_back_block->begin(), m_back_element+1, m_back_block->end());
std::copy_backward(m_front_block->end() - gap, m_front_block->end(), m_back_block->begin() + gap);
std::copy_backward(m_front_block->begin(), m_front_block->end() - gap, m_front_block->end());
m_front_element += gap;
m_back_element += gap;
--m_front_element;
*m_front_element = val;
++m_size;
return;
}
else
{
STXXL_VERBOSE1("deque2::push_front Case 2");
bid_type newbid;
m_bm->new_block(m_alloc_strategy, newbid, m_alloc_count++);
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]: push_front block " << m_front_block << " @ " << FMT_BID(newbid));
m_bids.push_front(newbid);
m_pool->write(m_front_block, newbid);
if (m_bids.size() <= m_blocks2prefetch) {
STXXL_VERBOSE1("deque2::push Case Hints");
m_pool->hint(newbid);
}
}
m_front_block = m_pool->steal();
m_front_element = m_front_block->end()-1;
*m_front_element = val;
++m_size;
}
else
{
--m_front_element;
*m_front_element = val;
++m_size;
}
}
void push_back(const value_type & val)
{
if (UNLIKELY(m_back_element == m_back_block->begin() + (block_type::size - 1)))
{
if (m_front_block == m_back_block)
{
STXXL_VERBOSE1("deque2::push_back Case 1");
}
else if (size() < 2 * block_type::size)
{
STXXL_VERBOSE1("deque2::push_back Case 1.5");
assert(m_bids.empty());
size_t gap = m_front_element - m_front_block->begin();
assert(gap > 0);
std::copy(m_front_element, m_front_block->end(), m_front_block->begin());
std::copy(m_back_block->begin(), m_back_block->begin() + gap, m_front_block->begin() + (block_type::size - gap));
std::copy(m_back_block->begin() + gap, m_back_block->end(), m_back_block->begin());
m_front_element -= gap;
m_back_element -= gap;
++m_back_element;
*m_back_element = val;
++m_size;
return;
}
else
{
STXXL_VERBOSE1("deque2::push_back Case 2");
bid_type newbid;
m_bm->new_block(m_alloc_strategy, newbid, m_alloc_count++);
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]: push_back block " << m_back_block << " @ " << FMT_BID(newbid));
m_bids.push_back(newbid);
m_pool->write(m_back_block, newbid);
if (m_bids.size() <= m_blocks2prefetch) {
STXXL_VERBOSE1("deque2::push_back Case Hints");
m_pool->hint(newbid);
}
}
m_back_block = m_pool->steal();
m_back_element = m_back_block->begin();
*m_back_element = val;
++m_size;
}
else
{
++m_back_element;
*m_back_element = val;
++m_size;
}
}
void pop_front()
{
assert(!empty());
if (UNLIKELY(m_front_element == m_front_block->begin() + (block_type::size - 1)))
{
if (m_back_block == m_front_block)
{
STXXL_VERBOSE1("deque2::pop_front Case 1");
assert(size() == 1);
assert(m_back_element == m_front_element);
assert(m_bids.empty());
m_back_element = m_back_block->begin() - 1;
m_front_element = m_back_block->begin();
m_size = 0;
return;
}
--m_size;
if (m_size <= block_type::size)
{
STXXL_VERBOSE1("deque2::pop_front Case 2");
assert(m_bids.empty());
m_pool->add(m_front_block);
m_front_block = m_back_block;
m_front_element = m_back_block->begin();
return;
}
STXXL_VERBOSE1("deque2::pop_front Case 3");
assert(!m_bids.empty());
request_ptr req = m_pool->read(m_front_block, m_bids.front());
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]: pop_front block " << m_front_block << " @ " << FMT_BID(m_bids.front()));
for (unsigned_type i = 0; i < m_blocks2prefetch && i < m_bids.size() - 1; ++i)
{
STXXL_VERBOSE1("deque2::pop_front Case Hints");
m_pool->hint(m_bids[i + 1]);
}
m_front_element = m_front_block->begin();
req->wait();
m_bm->delete_block(m_bids.front());
m_bids.pop_front();
}
else
{
++m_front_element;
--m_size;
}
}
void pop_back()
{
assert(!empty());
if (UNLIKELY(m_back_element == m_back_block->begin()))
{
if (m_back_block == m_front_block)
{
STXXL_VERBOSE1("deque2::pop_back Case 1");
assert(size() == 1);
assert(m_back_element == m_front_element);
assert(m_bids.empty());
m_back_element = m_back_block->begin() - 1;
m_front_element = m_back_block->begin();
m_size = 0;
return;
}
--m_size;
if (m_size <= block_type::size)
{
STXXL_VERBOSE1("deque2::pop_back Case 2");
assert(m_bids.empty());
m_pool->add(m_back_block);
m_back_block = m_front_block;
m_back_element = m_back_block->end() - 1;
return;
}
STXXL_VERBOSE1("deque2::pop_back Case 3");
assert(!m_bids.empty());
request_ptr req = m_pool->read(m_back_block, m_bids.back());
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]: pop_back block " << m_back_block << " @ " << FMT_BID(m_bids.back()));
for (unsigned_type i = 1; i < m_blocks2prefetch && i < m_bids.size() - 1; ++i)
{
STXXL_VERBOSE1("deque2::pop_front Case Hints");
m_pool->hint(m_bids[m_bids.size()-1 - i]);
}
m_back_element = m_back_block->end() - 1;
req->wait();
m_bm->delete_block(m_bids.back());
m_bids.pop_back();
}
else
{
--m_back_element;
--m_size;
}
}
size_type size() const
{
return m_size;
}
bool empty() const
{
return (m_size == 0);
}
value_type & back()
{
assert(!empty());
return *m_back_element;
}
const value_type & back() const
{
assert(!empty());
return *m_back_element;
}
value_type & front()
{
assert(!empty());
return *m_front_element;
}
const value_type & front() const
{
assert(!empty());
return *m_front_element;
}
~deque2()
{
if (m_front_block != m_back_block)
m_pool->add(m_back_block);
m_pool->add(m_front_block);
if (m_owns_pool)
delete m_pool;
if (!m_bids.empty())
m_bm->delete_blocks(m_bids.begin(), m_bids.end());
}
class stream
{
public:
typedef typename deque2::value_type value_type;
typedef typename bid_deque_type::const_iterator bid_iter_type;
protected:
const deque2& m_deque;
size_type m_size;
value_type* m_current_element;
block_type* m_current_block;
bid_iter_type m_next_bid;
public:
stream(const deque2& deque2)
: m_deque(deque2),
m_size(deque2.size())
{
m_current_block = deque2.m_front_block;
m_current_element = deque2.m_front_element;
m_next_bid = deque2.m_bids.begin();
}
~stream()
{
if ( m_current_block != m_deque.m_front_block &&
m_current_block != m_deque.m_back_block )
m_deque.m_pool->add(m_current_block);
}
size_type size() const
{
return m_size;
}
bool empty() const
{
return (m_size == 0);
}
const value_type& operator*() const
{
assert(!empty());
return *m_current_element;
}
stream& operator++()
{
assert(!empty());
if (UNLIKELY(m_current_element == m_current_block->begin() + (block_type::size - 1)))
{
--m_size;
if (m_size == 0)
{
STXXL_VERBOSE1("deque2::stream::operator++ last block finished clean at block end");
assert( m_next_bid == m_deque.m_bids.end() );
assert( m_current_block == m_deque.m_back_block );
m_current_element = NULL;
return *this;
}
else if (m_size <= block_type::size)
{
STXXL_VERBOSE1("deque2::stream::operator++ reached last block");
assert( m_next_bid == m_deque.m_bids.end() );
if (m_current_block != m_deque.m_front_block)
m_deque.m_pool->add(m_current_block);
m_current_block = m_deque.m_back_block;
m_current_element = m_current_block->begin();
return *this;
}
else if (m_current_block == m_deque.m_front_block)
{
STXXL_VERBOSE1("deque2::stream::operator++ first own-block case: steal block from deque's pool");
m_current_block = m_deque.m_pool->steal();
}
STXXL_VERBOSE1("deque2::stream::operator++ default case: fetch next block");
assert( m_next_bid != m_deque.m_bids.end() );
request_ptr req = m_deque.m_pool->read(m_current_block, *m_next_bid);
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]::stream::operator++ read block " << m_current_block << " @ " << FMT_BID(*m_next_bid));
bid_iter_type bid = m_next_bid+1;
for (unsigned_type i = 0; i < m_deque.m_blocks2prefetch && bid != m_deque.m_bids.end(); ++i, ++bid)
{
STXXL_VERBOSE1("deque2::stream::operator++ giving prefetch hints");
m_deque.m_pool->hint(*bid);
}
m_current_element = m_current_block->begin();
req->wait();
++m_next_bid;
}
else
{
--m_size;
++m_current_element;
}
return *this;
}
};
stream get_stream()
{
return stream(*this);
}
class reverse_stream
{
public:
typedef typename deque2::value_type value_type;
typedef typename bid_deque_type::const_reverse_iterator bid_iter_type;
protected:
const deque2& m_deque;
size_type m_size;
value_type* m_current_element;
block_type* m_current_block;
bid_iter_type m_next_bid;
public:
reverse_stream(const deque2& deque2)
: m_deque(deque2),
m_size(deque2.size())
{
m_current_block = deque2.m_back_block;
m_current_element = deque2.m_back_element;
m_next_bid = deque2.m_bids.rbegin();
}
~reverse_stream()
{
if ( m_current_block != m_deque.m_front_block &&
m_current_block != m_deque.m_back_block )
m_deque.m_pool->add(m_current_block);
}
size_type size() const
{
return m_size;
}
bool empty() const
{
return (m_size == 0);
}
const value_type& operator*() const
{
assert(!empty());
return *m_current_element;
}
reverse_stream& operator++()
{
assert(!empty());
if (UNLIKELY(m_current_element == m_current_block->begin()))
{
--m_size;
if (m_size == 0)
{
STXXL_VERBOSE1("deque2::reverse_stream::operator++ last block finished clean at block begin");
assert( m_next_bid == m_deque.m_bids.rend() );
assert( m_current_block == m_deque.m_front_block );
m_current_element = NULL;
return *this;
}
else if (m_size <= block_type::size)
{
STXXL_VERBOSE1("deque2::reverse_stream::operator++ reached first block");
assert( m_next_bid == m_deque.m_bids.rend() );
if (m_current_block != m_deque.m_back_block)
m_deque.m_pool->add(m_current_block);
m_current_block = m_deque.m_front_block;
m_current_element = m_current_block->begin() + (block_type::size - 1);
return *this;
}
else if (m_current_block == m_deque.m_back_block)
{
STXXL_VERBOSE1("deque2::reverse_stream::operator++ first own-block case: steal block from deque's pool");
m_current_block = m_deque.m_pool->steal();
}
STXXL_VERBOSE1("deque2::reverse_stream::operator++ default case: fetch previous block");
assert( m_next_bid != m_deque.m_bids.rend() );
request_ptr req = m_deque.m_pool->read(m_current_block, *m_next_bid);
STXXL_VERBOSE_DEQUE2("deque2[" << this << "]::reverse_stream::operator++ read block " << m_current_block << " @ " << FMT_BID(*m_next_bid));
bid_iter_type bid = m_next_bid+1;
for (unsigned_type i = 0; i < m_deque.m_blocks2prefetch && bid != m_deque.m_bids.rend(); ++i, ++bid)
{
STXXL_VERBOSE1("deque2::reverse_stream::operator++ giving prefetch hints");
m_deque.m_pool->hint(*bid);
}
m_current_element = m_current_block->begin() + (block_type::size - 1);
req->wait();
++m_next_bid;
}
else
{
--m_size;
--m_current_element;
}
return *this;
}
};
reverse_stream get_reverse_stream()
{
return reverse_stream(*this);
}
};
__STXXL_END_NAMESPACE
#endif