/usr/include/stxxl/bits/containers
Edit: /usr/include/stxxl/bits/containers/stack.h (33535B)
/***************************************************************************
* include/stxxl/bits/containers/stack.h
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2003-2004 Roman Dementiev
* Copyright (C) 2009, 2010 Andreas Beckmann
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#ifndef STXXL_CONTAINERS_STACK_HEADER
#define STXXL_CONTAINERS_STACK_HEADER
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
STXXL_BEGIN_NAMESPACE
//! \defgroup stlcont_stack stack
//! \ingroup stlcont
//! External stack implementations
//! \{
template
struct stack_config_generator
{
typedef ValueType value_type;
enum { blocks_per_page = BlocksPerPage };
typedef AllocStr alloc_strategy;
enum { block_size = BlockSize };
typedef SizeType size_type;
};
//! External stack container.
//! Introduction to stack container: see \ref tutorial_stack tutorial. \n
//! Design and Internals of stack container: see \ref design_stack
//! Conservative implementation. Fits best if your access pattern consists of irregularly mixed
//! push'es and pop's.
//! For semantics of the methods see documentation of the STL \c std::stack.
//! To gain full bandwidth of disks \c StackConfig::BlocksPerPage must >= number of disks
//! \internal
template
class normal_stack : private noncopyable
{
public:
typedef StackConfig cfg;
//! type of the elements stored in the stack
typedef typename cfg::value_type value_type;
typedef typename cfg::alloc_strategy alloc_strategy_type;
//! type for sizes (64-bit)
typedef typename cfg::size_type size_type;
enum {
blocks_per_page = cfg::blocks_per_page,
block_size = cfg::block_size
};
//! type of block used in disk-memory transfers
typedef typed_block block_type;
typedef BID bid_type;
private:
size_type m_size;
unsigned_type cache_offset;
value_type* current_element;
simple_vector cache;
typename simple_vector::iterator front_page;
typename simple_vector::iterator back_page;
std::vector bids;
alloc_strategy_type alloc_strategy;
public:
//! \name Constructors/Destructors
//! \{
//! Default constructor: creates empty stack.
normal_stack()
: m_size(0),
cache_offset(0),
current_element(NULL),
cache(blocks_per_page * 2),
front_page(cache.begin() + blocks_per_page),
back_page(cache.begin()),
bids(0)
{
bids.reserve(blocks_per_page);
}
//! \name Accessor Functions
//! \{
void swap(normal_stack& obj)
{
std::swap(m_size, obj.m_size);
std::swap(cache_offset, obj.cache_offset);
std::swap(current_element, obj.current_element);
std::swap(cache, obj.cache);
std::swap(front_page, obj.front_page);
std::swap(back_page, obj.back_page);
std::swap(bids, obj.bids);
std::swap(alloc_strategy, obj.alloc_strategy);
}
//! \}
//! \name Constructors/Destructors
//! \{
//! Copy-construction from a another stack of any type.
//! \param stack_ stack object (could be external or internal, important is that it must
//! have a copy constructor, \c top() and \c pop() methods )
template
normal_stack(const StackType& stack_)
: m_size(0),
cache_offset(0),
current_element(NULL),
cache(blocks_per_page * 2),
front_page(cache.begin() + blocks_per_page),
back_page(cache.begin()),
bids(0)
{
bids.reserve(blocks_per_page);
StackType stack_copy = stack_;
size_t sz = stack_copy.size();
std::vector tmp(sz);
for (size_t i = 0; i < sz; ++i) {
tmp[sz - i - 1] = stack_copy.top();
stack_copy.pop();
}
for (size_t i = 0; i < sz; ++i)
push(tmp[i]);
}
virtual ~normal_stack()
{
STXXL_VERBOSE(STXXL_PRETTY_FUNCTION_NAME);
block_manager::get_instance()->delete_blocks(bids.begin(), bids.end());
}
//! \}
//! \name Capacity
//! \{
//! Returns the number of elements contained in the stack
size_type size() const
{
return m_size;
}
//! Returns true if the stack is empty.
bool empty() const
{
return (!m_size);
}
//! \}
//! \name Accessor Functions
//! \{
//! Return mutable reference to the element at the top of the
//! stack. Precondition: stack is not empty().
value_type & top()
{
assert(m_size > 0);
return (*current_element);
}
//! Return constant reference to the element at the top of the
//! stack. Precondition: stack is not empty().
const value_type & top() const
{
assert(m_size > 0);
return (*current_element);
}
//! Inserts an element at the top of the stack. Postconditions: size() is
//! incremented by 1, and top() is the inserted element.
void push(const value_type& val)
{
assert(cache_offset <= 2 * blocks_per_page * block_type::size);
//assert(cache_offset >= 0);
if (UNLIKELY(cache_offset == 2 * blocks_per_page * block_type::size)) // cache overflow
{
STXXL_VERBOSE2("growing, size: " << m_size);
bids.resize(bids.size() + blocks_per_page);
typename std::vector::iterator cur_bid = bids.end() - blocks_per_page;
block_manager::get_instance()->new_blocks(alloc_strategy, cur_bid, bids.end(), cur_bid - bids.begin());
simple_vector requests(blocks_per_page);
for (int i = 0; i < blocks_per_page; ++i, ++cur_bid)
{
requests[i] = (back_page + i)->write(*cur_bid);
}
std::swap(back_page, front_page);
bids.reserve(bids.size() + blocks_per_page);
cache_offset = blocks_per_page * block_type::size + 1;
current_element = &((*front_page)[0]);
++m_size;
wait_all(requests.begin(), blocks_per_page);
*current_element = val;
return;
}
current_element = element(cache_offset);
*current_element = val;
++m_size;
++cache_offset;
}
//! Removes the element at the top of the stack. Precondition: stack is not
//! empty(). Postcondition: size() is decremented.
void pop()
{
assert(cache_offset <= 2 * blocks_per_page * block_type::size);
assert(cache_offset > 0);
assert(m_size > 0);
if (UNLIKELY(cache_offset == 1 && bids.size() >= blocks_per_page))
{
STXXL_VERBOSE2("shrinking, size: " << m_size);
simple_vector requests(blocks_per_page);
{
typename std::vector::const_iterator cur_bid = bids.end();
for (int i = blocks_per_page - 1; i >= 0; --i)
{
requests[i] = (front_page + i)->read(*(--cur_bid));
}
}
std::swap(front_page, back_page);
cache_offset = blocks_per_page * block_type::size;
--m_size;
current_element = &((*(back_page + (blocks_per_page - 1)))[block_type::size - 1]);
wait_all(requests.begin(), blocks_per_page);
block_manager::get_instance()->delete_blocks(bids.end() - blocks_per_page, bids.end());
bids.resize(bids.size() - blocks_per_page);
return;
}
--m_size;
current_element = element((--cache_offset) - 1);
}
//! \}
private:
value_type * element(unsigned_type offset)
{
if (offset < blocks_per_page * block_type::size)
return &((*(back_page + offset / block_type::size))[offset % block_type::size]);
unsigned_type unbiased_offset = offset - blocks_per_page * block_type::size;
return &((*(front_page + unbiased_offset / block_type::size))[unbiased_offset % block_type::size]);
}
};
//! Efficient implementation that uses prefetching and overlapping using internal buffers.
//!
//! Use it if your access pattern consists of many repeated push'es and pop's
//! For semantics of the methods see documentation of the STL \c std::stack.
//! \warning The amortized complexity of operation is not O(1/DB), rather O(DB)
template
class grow_shrink_stack : private noncopyable
{
public:
typedef StackConfig cfg;
//! type of the elements stored in the stack
typedef typename cfg::value_type value_type;
typedef typename cfg::alloc_strategy alloc_strategy_type;
//! type for sizes (64-bit)
typedef typename cfg::size_type size_type;
enum {
blocks_per_page = cfg::blocks_per_page,
block_size = cfg::block_size
};
//! type of block used in disk-memory transfers
typedef typed_block block_type;
typedef BID bid_type;
private:
size_type m_size;
unsigned_type cache_offset;
value_type* current_element;
simple_vector cache;
typename simple_vector::iterator cache_buffers;
typename simple_vector::iterator overlap_buffers;
simple_vector requests;
std::vector bids;
alloc_strategy_type alloc_strategy;
public:
//! \name Constructors/Destructor
//! \{
//! Default constructor: creates empty stack.
grow_shrink_stack()
: m_size(0),
cache_offset(0),
current_element(NULL),
cache(blocks_per_page * 2),
cache_buffers(cache.begin()),
overlap_buffers(cache.begin() + blocks_per_page),
requests(blocks_per_page),
bids(0)
{
bids.reserve(blocks_per_page);
}
//! \}
//! \name Accessor Functions
//! \{
void swap(grow_shrink_stack& obj)
{
std::swap(m_size, obj.m_size);
std::swap(cache_offset, obj.cache_offset);
std::swap(current_element, obj.current_element);
std::swap(cache, obj.cache);
std::swap(cache_buffers, obj.cache_buffers);
std::swap(overlap_buffers, obj.overlap_buffers);
std::swap(requests, obj.requests);
std::swap(bids, obj.bids);
std::swap(alloc_strategy, obj.alloc_strategy);
}
//! \}
//! \name Constructors/Destructors
//! \{
//! Copy-construction from a another stack of any type.
//! \param stack_ stack object (could be external or internal, important is that it must
//! have a copy constructor, \c top() and \c pop() methods )
template
grow_shrink_stack(const StackType& stack_)
: m_size(0),
cache_offset(0),
current_element(NULL),
cache(blocks_per_page * 2),
cache_buffers(cache.begin()),
overlap_buffers(cache.begin() + blocks_per_page),
requests(blocks_per_page),
bids(0)
{
bids.reserve(blocks_per_page);
StackType stack_copy = stack_;
size_t sz = stack_copy.size();
std::vector tmp(sz);
for (size_t i = 0; i < sz; ++i)
{
tmp[sz - i - 1] = stack_copy.top();
stack_copy.pop();
}
for (size_t i = 0; i < sz; ++i)
push(tmp[i]);
}
virtual ~grow_shrink_stack()
{
STXXL_VERBOSE(STXXL_PRETTY_FUNCTION_NAME);
try
{
if (requests[0].get())
wait_all(requests.begin(), blocks_per_page);
}
catch (const io_error&)
{ }
block_manager::get_instance()->delete_blocks(bids.begin(), bids.end());
}
//! \}
//! \name Capacity
//! \{
//! Returns the number of elements contained in the stack
size_type size() const
{
return m_size;
}
//! Returns true if the stack is empty.
bool empty() const
{
return (!m_size);
}
//! \}
//! \name Accessor Functions
//! \{
//! Return mutable reference to the element at the top of the
//! stack. Precondition: stack is not empty().
value_type & top()
{
assert(m_size > 0);
return (*current_element);
}
//! Return constant reference to the element at the top of the
//! stack. Precondition: stack is not empty().
const value_type & top() const
{
assert(m_size > 0);
return (*current_element);
}
//! Inserts an element at the top of the stack. Postconditions: size() is
//! incremented by 1, and top() is the inserted element.
void push(const value_type& val)
{
assert(cache_offset <= blocks_per_page * block_type::size);
//assert(cache_offset >= 0);
if (UNLIKELY(cache_offset == blocks_per_page * block_type::size)) // cache overflow
{
STXXL_VERBOSE2("growing, size: " << m_size);
bids.resize(bids.size() + blocks_per_page);
typename std::vector::iterator cur_bid = bids.end() - blocks_per_page;
block_manager::get_instance()->new_blocks(alloc_strategy, cur_bid, bids.end(), cur_bid - bids.begin());
for (int i = 0; i < blocks_per_page; ++i, ++cur_bid)
{
if (requests[i].get())
requests[i]->wait();
requests[i] = (cache_buffers + i)->write(*cur_bid);
}
std::swap(cache_buffers, overlap_buffers);
bids.reserve(bids.size() + blocks_per_page);
cache_offset = 1;
current_element = &((*cache_buffers)[0]);
++m_size;
*current_element = val;
return;
}
current_element = &((*(cache_buffers + cache_offset / block_type::size))[cache_offset % block_type::size]);
*current_element = val;
++m_size;
++cache_offset;
}
//! Removes the element at the top of the stack. Precondition: stack is not
//! empty(). Postcondition: size() is decremented.
void pop()
{
assert(cache_offset <= blocks_per_page * block_type::size);
assert(cache_offset > 0);
assert(m_size > 0);
if (UNLIKELY(cache_offset == 1 && bids.size() >= blocks_per_page))
{
STXXL_VERBOSE2("shrinking, size: " << m_size);
if (requests[0].get())
wait_all(requests.begin(), blocks_per_page);
std::swap(cache_buffers, overlap_buffers);
if (bids.size() > blocks_per_page)
{
STXXL_VERBOSE2("prefetching, size: " << m_size);
typename std::vector::const_iterator cur_bid = bids.end() - blocks_per_page;
for (int i = blocks_per_page - 1; i >= 0; --i)
requests[i] = (overlap_buffers + i)->read(*(--cur_bid));
}
block_manager::get_instance()->delete_blocks(bids.end() - blocks_per_page, bids.end());
bids.resize(bids.size() - blocks_per_page);
cache_offset = blocks_per_page * block_type::size;
--m_size;
current_element = &((*(cache_buffers + (blocks_per_page - 1)))[block_type::size - 1]);
return;
}
--m_size;
unsigned_type cur_offset = (--cache_offset) - 1;
current_element = &((*(cache_buffers + cur_offset / block_type::size))[cur_offset % block_type::size]);
}
//! \}
};
//! Efficient implementation that uses prefetching and overlapping using (shared) buffers pools.
//! \warning This is a single buffer stack! Each direction change (push() followed by pop() or vice versa) may cause one I/O.
template
class grow_shrink_stack2 : private noncopyable
{
public:
typedef StackConfig cfg;
//! type of the elements stored in the stack
typedef typename cfg::value_type value_type;
typedef typename cfg::alloc_strategy alloc_strategy_type;
//! type for sizes (64-bit)
typedef typename cfg::size_type size_type;
enum {
blocks_per_page = cfg::blocks_per_page, // stack of this type has only one page
block_size = cfg::block_size
};
//! type of block used in disk-memory transfers
typedef typed_block block_type;
typedef BID bid_type;
private:
typedef read_write_pool pool_type;
size_type m_size;
unsigned_type cache_offset;
block_type* cache;
std::vector bids;
alloc_strategy_type alloc_strategy;
unsigned_type pref_aggr;
pool_type* owned_pool;
pool_type* pool;
public:
//! \name Constructors/Destructors
//! \{
//! Default constructor: creates empty stack. The stack will use the
//! read_write_pool for prefetching and buffered writing.
//! \param pool_ block write/prefetch pool
//! \param prefetch_aggressiveness number of blocks that will be used from prefetch pool
grow_shrink_stack2(pool_type& pool_,
unsigned_type prefetch_aggressiveness = 0)
: m_size(0),
cache_offset(0),
cache(new block_type),
pref_aggr(prefetch_aggressiveness),
owned_pool(NULL),
pool(&pool_)
{
STXXL_VERBOSE2("grow_shrink_stack2::grow_shrink_stack2(...)");
}
//! Default constructor: creates empty stack. The stack will use the pair
//! of prefetch_pool and write_pool for prefetching and buffered writing.
//! This constructor is deprecated in favor of the read_write_pool
//! constructor.
//!
//! \param p_pool_ prefetch pool, that will be used for block prefetching
//! \param w_pool_ write pool, that will be used for block writing
//! \param prefetch_aggressiveness number of blocks that will be used from prefetch pool
STXXL_DEPRECATED(
grow_shrink_stack2(prefetch_pool& p_pool_,
write_pool& w_pool_,
unsigned_type prefetch_aggressiveness = 0)
)
: m_size(0),
cache_offset(0),
cache(new block_type),
pref_aggr(prefetch_aggressiveness),
owned_pool(new pool_type(p_pool_, w_pool_)),
pool(owned_pool)
{
STXXL_VERBOSE2("grow_shrink_stack2::grow_shrink_stack2(...)");
}
//! \}
//! \name Accessor Functions
//! \{
void swap(grow_shrink_stack2& obj)
{
std::swap(m_size, obj.m_size);
std::swap(cache_offset, obj.cache_offset);
std::swap(cache, obj.cache);
std::swap(bids, obj.bids);
std::swap(alloc_strategy, obj.alloc_strategy);
std::swap(pref_aggr, obj.pref_aggr);
std::swap(owned_pool, obj.owned_pool);
std::swap(pool, obj.pool);
}
//! \}
//! \name Constructors/Destructors
//! \{
virtual ~grow_shrink_stack2()
{
try
{
STXXL_VERBOSE2("grow_shrink_stack2::~grow_shrink_stack2()");
const int_type bids_size = bids.size();
const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr), (int_type)0);
int_type i;
for (i = bids_size - 1; i >= last_pref; --i)
{
// clean the prefetch buffer
pool->invalidate(bids[i]);
}
typename std::vector::iterator cur = bids.begin();
typename std::vector::const_iterator end = bids.end();
for ( ; cur != end; ++cur)
{
// FIXME: read_write_pool needs something like cancel_write(bid)
block_type* b = NULL; // w_pool.steal(*cur);
if (b)
{
pool->add(cache); // return buffer
cache = b;
}
}
delete cache;
}
catch (const io_error&)
{ }
block_manager::get_instance()->delete_blocks(bids.begin(), bids.end());
delete owned_pool;
}
//! \}
//! \name Capacity
//! \{
//! Returns the number of elements contained in the stack
size_type size() const
{
return m_size;
}
//! Returns true if the stack is empty.
bool empty() const
{
return (!m_size);
}
//! \}
//! \name Accessor Functions
//! \{
//! Inserts an element at the top of the stack. Postconditions: size() is
//! incremented by 1, and top() is the inserted element.
void push(const value_type& val)
{
STXXL_VERBOSE3("grow_shrink_stack2::push(" << val << ")");
assert(cache_offset <= block_type::size);
if (UNLIKELY(cache_offset == block_type::size))
{
STXXL_VERBOSE2("grow_shrink_stack2::push(" << val << ") growing, size: " << m_size);
bids.resize(bids.size() + 1);
typename std::vector::iterator cur_bid = bids.end() - 1;
block_manager::get_instance()->new_blocks(alloc_strategy, cur_bid, bids.end(), cur_bid - bids.begin());
pool->write(cache, bids.back());
cache = pool->steal();
const int_type bids_size = bids.size();
const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr) - 1, (int_type)0);
for (int_type i = bids_size - 2; i >= last_pref; --i)
{
// clean prefetch buffers
pool->invalidate(bids[i]);
}
cache_offset = 0;
}
(*cache)[cache_offset] = val;
++m_size;
++cache_offset;
assert(cache_offset > 0);
assert(cache_offset <= block_type::size);
}
//! Return mutable reference to the element at the top of the
//! stack. Precondition: stack is not empty().
value_type & top()
{
assert(m_size > 0);
assert(cache_offset > 0);
assert(cache_offset <= block_type::size);
return (*cache)[cache_offset - 1];
}
//! Return constant reference to the element at the top of the
//! stack. Precondition: stack is not empty().
const value_type & top() const
{
assert(m_size > 0);
assert(cache_offset > 0);
assert(cache_offset <= block_type::size);
return (*cache)[cache_offset - 1];
}
//! Removes the element at the top of the stack. Precondition: stack is not
//! empty(). Postcondition: size() is decremented.
void pop()
{
STXXL_VERBOSE3("grow_shrink_stack2::pop()");
assert(m_size > 0);
assert(cache_offset > 0);
assert(cache_offset <= block_type::size);
if (UNLIKELY(cache_offset == 1 && (!bids.empty())))
{
STXXL_VERBOSE2("grow_shrink_stack2::pop() shrinking, size = " << m_size);
bid_type last_block = bids.back();
bids.pop_back();
pool->read(cache, last_block)->wait();
block_manager::get_instance()->delete_block(last_block);
rehint();
cache_offset = block_type::size + 1;
}
--cache_offset;
--m_size;
}
//! \}
//! \name Miscellaneous
//! \{
//! Sets level of prefetch aggressiveness (number of blocks from the
//! prefetch pool used for prefetching).
//! \param new_p new value for the prefetch aggressiveness
void set_prefetch_aggr(unsigned_type new_p)
{
if (pref_aggr > new_p)
{
const int_type bids_size = bids.size();
const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr), (int_type)0);
for (int_type i = bids_size - new_p - 1; i >= last_pref; --i)
{
// clean prefetch buffers
pool->invalidate(bids[i]);
}
}
pref_aggr = new_p;
rehint();
}
//! Returns number of blocks used for prefetching.
unsigned_type get_prefetch_aggr() const
{
return pref_aggr;
}
//! \}
private:
//! hint the last pref_aggr external blocks.
void rehint()
{
const int_type bids_size = bids.size();
const int_type last_pref = STXXL_MAX(int_type(bids_size) - int_type(pref_aggr), (int_type)0);
for (int_type i = bids_size - 1; i >= last_pref; --i)
{
pool->hint(bids[i]); // prefetch
}
}
};
//! A stack that migrates from internal memory to external when its size exceeds a certain threshold.
//!
//! For semantics of the methods see documentation of the STL \c std::stack.
template
class migrating_stack : private noncopyable
{
public:
typedef typename ExternalStack::cfg cfg;
//! type of the elements stored in the stack
typedef typename cfg::value_type value_type;
//! type for sizes (64-bit)
typedef typename cfg::size_type size_type;
enum {
blocks_per_page = cfg::blocks_per_page,
block_size = cfg::block_size
};
typedef InternalStack int_stack_type;
typedef ExternalStack ext_stack_type;
private:
enum { critical_size = CritSize };
int_stack_type* int_impl;
ext_stack_type* ext_impl;
//! Copy-construction from a another stack of any type.
//! \warning not implemented yet!
template
migrating_stack(const StackType& stack_);
public:
//! \name Constructors/Destructors
//! \{
//! Default constructor: creates empty stack.
migrating_stack()
: int_impl(new int_stack_type()), ext_impl(NULL)
{ }
virtual ~migrating_stack()
{
delete int_impl;
delete ext_impl;
}
//! \}
//! \name Accessor Functions
//! \{
void swap(migrating_stack& obj)
{
std::swap(int_impl, obj.int_impl);
std::swap(ext_impl, obj.ext_impl);
}
//! \}
//! \name Miscellaneous
//! \{
//! Returns true if current implementation is internal, otherwise false.
bool internal() const
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
return (int_impl != NULL);
}
//! Returns true if current implementation is external, otherwise false.
bool external() const
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
return (ext_impl != NULL);
}
//! \}
//! \name Capacity
//! \{
//! Returns true if the stack is empty.
bool empty() const
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
return (int_impl) ? int_impl->empty() : ext_impl->empty();
}
//! Returns the number of elements contained in the stack
size_type size() const
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
return (int_impl) ? size_type(int_impl->size()) : ext_impl->size();
}
//! \}
//! \name Accessor Functions
//! \{
//! Return mutable reference to the element at the top of the
//! stack. Precondition: stack is not empty().
value_type & top()
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
return (int_impl) ? int_impl->top() : ext_impl->top();
}
//! Return constant reference to the element at the top of the
//! stack. Precondition: stack is not empty().
const value_type & top() const
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
return (int_impl) ? int_impl->top() : ext_impl->top();
}
//! Inserts an element at the top of the stack. Postconditions: size() is
//! incremented by 1, and top() is the inserted element.
void push(const value_type& val)
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
if (int_impl)
{
int_impl->push(val);
if (UNLIKELY(int_impl->size() == critical_size))
{
// migrate to external stack
ext_impl = new ext_stack_type(*int_impl);
delete int_impl;
int_impl = NULL;
}
}
else
ext_impl->push(val);
}
//! Removes the element at the top of the stack. Precondition: stack is not
//! empty(). Postcondition: size() is decremented.
void pop()
{
assert((int_impl && !ext_impl) || (!int_impl && ext_impl));
if (int_impl)
int_impl->pop();
else
ext_impl->pop();
}
//! \}
};
enum stack_externality { external, migrating, internal };
enum stack_behaviour { normal, grow_shrink, grow_shrink2 };
//! Stack type generator \n
//! Introduction to stack container: see \ref tutorial_stack tutorial. \n
//! Design and Internals of stack container: see \ref design_stack.
//!
//! \tparam ValueType type of contained objects (POD with no references to internal memory)
//!
//! \tparam Externality selects stack implementation, default: \b external. One of
//! - \c external, external container, implementation is chosen according to \c Behaviour parameter.
//! - \c migrating, migrates from internal implementation given by \c IntStackType parameter
//! to external implementation given by \c Behaviour parameter when size exceeds \c MigrCritSize
//! - \c internal, choses \c IntStackType implementation
//!
//! \tparam Behaviour chooses \b external implementation, default: \b stxxl::normal_stack. One of:
//! - \c normal, conservative version, implemented in \c stxxl::normal_stack
//! - \c grow_shrink, efficient version, implemented in \c stxxl::grow_shrink_stack
//! - \c grow_shrink2, efficient version, implemented in \c stxxl::grow_shrink_stack2
//!
//! \tparam BlocksPerPage defines how many blocks has one page of internal cache of an
//! \b external implementation, default is \b 4. All \b external implementations have
//! \b two pages.
//!
//! \tparam BlockSize external block size in bytes, default is 2 MiB.
//!
//! \tparam IntStackType type of internal stack used for some implementations, default: \b std::stack.
//!
//! \tparam MigrCritSize threshold value for number of elements when
//! stxxl::migrating_stack migrates to the external memory, default: 2 x BlocksPerPage x BlockSize.
//!
//! \tparam AllocStr one of allocation strategies: striping, RC, SR, or FR. Default is \b RC.
//!
//! \tparam SizeType size type, default is \b stxxl::uint64.
//!
//! The configured stack type is available as STACK_GENERATOR<>::result.
//!
template <
class ValueType,
stack_externality Externality = external,
stack_behaviour Behaviour = normal,
unsigned BlocksPerPage = 4,
unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
class IntStackType = std::stack,
unsigned_type MigrCritSize = (2* BlocksPerPage* BlockSize),
class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
class SizeType = stxxl::uint64
>
class STACK_GENERATOR
{
typedef stack_config_generator cfg;
typedef typename IF,
grow_shrink_stack2 >::result GrShrTp;
typedef typename IF, GrShrTp>::result ExtStackType;
typedef typename IF, ExtStackType>::result MigrOrNotStackType;
public:
typedef typename IF::result result;
};
//! \}
STXXL_END_NAMESPACE
namespace std {
template
void swap(stxxl::normal_stack& a,
stxxl::normal_stack& b)
{
a.swap(b);
}
template
void swap(stxxl::grow_shrink_stack& a,
stxxl::grow_shrink_stack& b)
{
a.swap(b);
}
template
void swap(stxxl::grow_shrink_stack2& a,
stxxl::grow_shrink_stack2& b)
{
a.swap(b);
}
template
void swap(stxxl::migrating_stack& a,
stxxl::migrating_stack& b)
{
a.swap(b);
}
} // namespace std
#endif // !STXXL_CONTAINERS_STACK_HEADER
// vim: et:ts=4:sw=4