STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType > Class Template Reference

Detailed Description

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
class stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >

External sequence or deque container without random access.
Introduction to sequence container: see STXXL Sequence tutorial.
Design and Internals of sequence container: see Queue.

Sequence is a primitive container consisting of only a sequence of blocks in external memory. The sequence provides appending methods similar to a deque: push_back and push_front; and also the corresponding pop functions. However, different from stxxl::deque (which is a vector in disguise), the sequence does not allow random access. Instead, the sequence can only be iterated using streams: either from front to back or in reverse.

As with queue and stack, sequences of pushes and pops are made efficient using overlapping or read-ahead via block pools. The stream access likewise uses overlapped I/O, just like stream::vector_iterator2stream.

Template Parameters
ValueTypetype of the contained objects (POD with no references to internal memory)
BlockSizesize of the external memory block in bytes, default is STXXL_DEFAULT_BLOCK_SIZE(ValTp)
AllocStrparallel disk allocation strategy, default is STXXL_DEFAULT_ALLOC_STRATEGY
SizeTypesize data type, default is stxxl::uint64
Examples:
examples/containers/sequence1.cpp.

Definition at line 62 of file sequence.h.

+ Inheritance diagram for stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >:
+ Collaboration diagram for stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >:

Classes

class  reverse_stream
 
class  stream
 

Public Types

enum  { block_size = BlockSize }
 
typedef AllocStr alloc_strategy_type
 
typedef std::deque< bid_typebid_deque_type
 
typedef BID< block_sizebid_type
 
typedef typed_block
< block_size, value_type
block_type
 
typedef SizeType size_type
 
typedef ValueType value_type
 

Public Member Functions

Constructors/Destructors
 sequence (int_type D=-1)
 Constructs empty sequence with own write and prefetch block pool. More...
 
 sequence (unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch=-1)
 Constructs empty sequence with own write and prefetch block pool. More...
 
 sequence (pool_type &pool, int blocks2prefetch=-1)
 Constructs empty sequence. More...
 
 ~sequence ()
 
Modifiers
void swap (sequence &obj)
 
void push_front (const value_type &val)
 Adds an element to the front of the sequence. More...
 
void push_back (const value_type &val)
 Adds an element to the end of the sequence. More...
 
void pop_front ()
 Removes element from the front of the sequence. More...
 
void pop_back ()
 Removes element from the back of the sequence. More...
 
Miscellaneous
void set_prefetch_aggr (int_type blocks2prefetch)
 Defines the number of blocks to prefetch (front side). This method should be called whenever the prefetch pool is resized. More...
 
unsigned_type get_prefetch_aggr () const
 Returns the number of blocks prefetched from the front side. More...
 
stream get_stream ()
 construct a forward stream from this sequence More...
 
reverse_stream get_reverse_stream ()
 construct a reverse stream from this sequence More...
 
Capacity
size_type size () const
 Returns the size of the sequence. More...
 
bool empty () const
 Returns true if sequence is empty. More...
 
Operators
value_typeback ()
 Returns a mutable reference at the back of the sequence. More...
 
const value_typeback () const
 Returns a const reference at the back of the sequence. More...
 
value_typefront ()
 Returns a mutable reference at the front of the sequence. More...
 
const value_typefront () const
 Returns a const reference at the front of the sequence. More...
 

Private Types

typedef read_write_pool
< block_type
pool_type
 

Private Member Functions

void init (int blocks2prefetch=-1)
 
- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Private Attributes

unsigned_type m_alloc_count
 block allocation counter More...
 
alloc_strategy_type m_alloc_strategy
 block allocation strategy More...
 
block_typem_back_block
 current back block of sequence More...
 
value_typem_back_element
 pointer to current back element in m_back_block More...
 
bid_deque_type m_bids
 allocated block identifiers More...
 
unsigned_type m_blocks2prefetch
 number of blocks to prefetch More...
 
block_managerm_bm
 block manager used More...
 
block_typem_front_block
 current front block of sequence More...
 
value_typem_front_element
 pointer to current front element in m_front_block More...
 
bool m_owns_pool
 whether the m_pool object is own and should be deleted. More...
 
pool_typem_pool
 read_write_pool of blocks More...
 
size_type m_size
 current number of items in the sequence More...
 

Member Typedef Documentation

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef AllocStr stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::alloc_strategy_type

Definition at line 66 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef std::deque<bid_type> stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::bid_deque_type

Definition at line 75 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef BID<block_size> stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::bid_type

Definition at line 73 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef typed_block<block_size, value_type> stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::block_type

Definition at line 72 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef read_write_pool<block_type> stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::pool_type
private

Definition at line 78 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef SizeType stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::size_type

Definition at line 67 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef ValueType stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::value_type

Definition at line 65 of file sequence.h.

Member Enumeration Documentation

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
anonymous enum
Enumerator
block_size 

Definition at line 68 of file sequence.h.

Constructor & Destructor Documentation

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::sequence ( int_type  D = -1)
inlineexplicit

Constructs empty sequence with own write and prefetch block pool.

Parameters
Dnumber of parallel disks, defaulting to the configured number of scratch disks, memory consumption will be 2 * D + 2 blocks (first and last block, D blocks as write cache, D block for prefetching)

Definition at line 125 of file sequence.h.

References STXXL_VERBOSE_SEQUENCE.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::sequence ( unsigned_type  w_pool_size,
unsigned_type  p_pool_size,
int  blocks2prefetch = -1 
)
inlineexplicit

Constructs empty sequence with own write and prefetch block pool.

Parameters
w_pool_sizenumber of blocks in the write pool, must be at least 2, recommended at least 3
p_pool_sizenumber of blocks in the prefetch pool, recommended at least 1
blocks2prefetchdefines the number of blocks to prefetch (front side), default is number of block in the prefetch pool

Definition at line 143 of file sequence.h.

References STXXL_VERBOSE_SEQUENCE.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::sequence ( pool_type pool,
int  blocks2prefetch = -1 
)
inline

Constructs empty sequence.

Parameters
poolblock write/prefetch pool
blocks2prefetchdefines the number of blocks to prefetch (front side), default is number of blocks in the prefetch pool
Warning
Number of blocks in the write pool must be at least 2, recommended at least 3
Number of blocks in the prefetch pool recommended at least 1

Definition at line 160 of file sequence.h.

References STXXL_VERBOSE_SEQUENCE.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::~sequence ( )
inline

Definition at line 548 of file sequence.h.

Member Function Documentation

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
value_type& stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::back ( )
inline

Returns a mutable reference at the back of the sequence.

Definition at line 516 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
const value_type& stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::back ( ) const
inline

Returns a const reference at the back of the sequence.

Definition at line 523 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
bool stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::empty ( ) const
inline

Returns true if sequence is empty.

Definition at line 505 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
value_type& stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::front ( )
inline

Returns a mutable reference at the front of the sequence.

Definition at line 530 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
const value_type& stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::front ( ) const
inline

Returns a const reference at the front of the sequence.

Definition at line 537 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
unsigned_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::get_prefetch_aggr ( ) const
inline

Returns the number of blocks prefetched from the front side.

Definition at line 235 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
reverse_stream stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::get_reverse_stream ( )
inline

construct a reverse stream from this sequence

Definition at line 819 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stream stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::get_stream ( )
inline

construct a forward stream from this sequence

Definition at line 688 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::init ( int  blocks2prefetch = -1)
inlineprivate

initialize empty sequence

Definition at line 195 of file sequence.h.

References STXXL_ERRMSG, and STXXL_MSG.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::pop_back ( )
inline

Removes element from the back of the sequence.

Definition at line 435 of file sequence.h.

References FMT_BID, STXXL_VERBOSE1, STXXL_VERBOSE_SEQUENCE, and UNLIKELY.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::pop_front ( )
inline

Removes element from the front of the sequence.

Definition at line 377 of file sequence.h.

References FMT_BID, STXXL_VERBOSE1, STXXL_VERBOSE_SEQUENCE, and UNLIKELY.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::push_back ( const value_type val)
inline

Adds an element to the end of the sequence.

Examples:
examples/containers/sequence1.cpp.

Definition at line 316 of file sequence.h.

References FMT_BID, STXXL_VERBOSE1, STXXL_VERBOSE_SEQUENCE, and UNLIKELY.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::push_front ( const value_type val)
inline

Adds an element to the front of the sequence.

Definition at line 246 of file sequence.h.

References FMT_BID, STXXL_VERBOSE1, STXXL_VERBOSE_SEQUENCE, and UNLIKELY.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::set_prefetch_aggr ( int_type  blocks2prefetch)
inline

Defines the number of blocks to prefetch (front side). This method should be called whenever the prefetch pool is resized.

Parameters
blocks2prefetchdefines the number of blocks to prefetch (front side), a negative value means to use the number of blocks in the prefetch pool

Definition at line 226 of file sequence.h.

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
size_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::size ( ) const
inline

Returns the size of the sequence.

Definition at line 499 of file sequence.h.

Member Data Documentation

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
unsigned_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_alloc_count
private

block allocation counter

Definition at line 105 of file sequence.h.

Referenced by stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::swap().

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
alloc_strategy_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_alloc_strategy
private

block allocation strategy

Definition at line 102 of file sequence.h.

Referenced by stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::swap().

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
block_type* stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_back_block
private
template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
value_type* stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_back_element
private
template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
bid_deque_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_bids
private
template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
unsigned_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_blocks2prefetch
private

number of blocks to prefetch

Definition at line 114 of file sequence.h.

Referenced by stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::swap().

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
block_manager* stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_bm
private

block manager used

Definition at line 111 of file sequence.h.

Referenced by stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::swap().

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
block_type* stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_front_block
private
template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
value_type* stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_front_element
private
template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
bool stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_owns_pool
private

whether the m_pool object is own and should be deleted.

Definition at line 84 of file sequence.h.

Referenced by stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::swap().

template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
pool_type* stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_pool
private
template<class ValueType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
size_type stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::m_size
private

current number of items in the sequence

Definition at line 81 of file sequence.h.

Referenced by stxxl::sequence< ValueType, BlockSize, AllocStr, SizeType >::swap().


The documentation for this class was generated from the following file: