Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes
stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType > Class Template Reference

External deque container without random access. More...

#include <deque2.h>

Inheritance diagram for stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >:
Collaboration graph
[legend]

List of all members.

Classes

class  reverse_stream
class  stream

Public Types

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

Public Member Functions

 deque2 (int D=-1)
 Constructs empty deque with own write and prefetch block pool.
 deque2 (unsigned_type w_pool_size, unsigned_type p_pool_size, int blocks2prefetch=-1)
 Constructs empty deque2 with own write and prefetch block pool.
 deque2 (pool_type &pool, int blocks2prefetch=-1)
 Constructs empty deque.
void swap (deque2 &obj)
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.
unsigned_type get_prefetch_aggr () const
 Returns the number of blocks prefetched from the front side.
void push_front (const value_type &val)
 Adds an element to the front of the deque.
void push_back (const value_type &val)
 Adds an element to the end of the deque.
void pop_front ()
 Removes element from the front of the deque.
void pop_back ()
 Removes element from the back of the deque.
size_type size () const
 Returns the size of the deque.
bool empty () const
 Returns true if deque is empty.
value_typeback ()
 Returns a mutable reference at the back of the deque.
const value_typeback () const
 Returns a const reference at the back of the deque.
value_typefront ()
 Returns a mutable reference at the front of the deque.
const value_typefront () const
 Returns a const reference at the front of the deque.
 ~deque2 ()
stream get_stream ()
reverse_stream get_reverse_stream ()

Private Types

typedef read_write_pool
< block_type
pool_type

Private Member Functions

void init (int blocks2prefetch=-1)

Private Attributes

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

Detailed Description

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

External deque container without random access.

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)
AllocStrategyparallel disk allocation strategy, default is STXXL_DEFAULT_ALLOC_STRATEGY
SizeTypesize data type, default is stxxl::uint64

Definition at line 47 of file deque2.h.


Member Typedef Documentation

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

Definition at line 51 of file deque2.h.

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

Definition at line 60 of file deque2.h.

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

Definition at line 58 of file deque2.h.

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

Definition at line 57 of file deque2.h.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
typedef read_write_pool<block_type> stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::pool_type [private]

Definition at line 63 of file deque2.h.

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

Definition at line 52 of file deque2.h.

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

Definition at line 50 of file deque2.h.


Member Enumeration Documentation

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

Definition at line 53 of file deque2.h.


Constructor & Destructor Documentation

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::deque2 ( int  D = -1) [inline, explicit]

Constructs empty deque 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 107 of file deque2.h.

References D(), init(), and STXXL_VERBOSE_DEQUE2.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::deque2 ( unsigned_type  w_pool_size,
unsigned_type  p_pool_size,
int  blocks2prefetch = -1 
) [inline, explicit]

Constructs empty deque2 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 125 of file deque2.h.

References init(), and STXXL_VERBOSE_DEQUE2.

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

Constructs empty deque.

Parameters:
pool_block 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 143 of file deque2.h.

References init(), and STXXL_VERBOSE_DEQUE2.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::~deque2 ( ) [inline]

Definition at line 501 of file deque2.h.


Member Function Documentation

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
value_type& stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::back ( ) [inline]

Returns a mutable reference at the back of the deque.

Definition at line 474 of file deque2.h.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
const value_type& stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::back ( ) const [inline]

Returns a const reference at the back of the deque.

Definition at line 481 of file deque2.h.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
bool stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::empty ( ) const [inline]

Returns true if deque is empty.

Definition at line 468 of file deque2.h.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
value_type& stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::front ( ) [inline]

Returns a mutable reference at the front of the deque.

Definition at line 488 of file deque2.h.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
const value_type& stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::front ( ) const [inline]

Returns a const reference at the front of the deque.

Definition at line 495 of file deque2.h.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
unsigned_type stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::get_prefetch_aggr ( ) const [inline]

Returns the number of blocks prefetched from the front side.

Definition at line 208 of file deque2.h.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
reverse_stream stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::get_reverse_stream ( ) [inline]

Definition at line 758 of file deque2.h.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
stream stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::get_stream ( ) [inline]

Definition at line 634 of file deque2.h.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::init ( int  blocks2prefetch = -1) [inline, private]

initialize empty deque

Definition at line 171 of file deque2.h.

References STXXL_MSG.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::pop_back ( ) [inline]

Removes element from the back of the deque.

Definition at line 403 of file deque2.h.

References FMT_BID, STXXL_VERBOSE_DEQUE2, and UNLIKELY.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::pop_front ( ) [inline]

Removes element from the front of the deque.

Definition at line 345 of file deque2.h.

References FMT_BID, STXXL_VERBOSE_DEQUE2, and UNLIKELY.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::push_back ( const value_type val) [inline]

Adds an element to the end of the deque.

Definition at line 284 of file deque2.h.

References FMT_BID, STXXL_VERBOSE_DEQUE2, and UNLIKELY.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::push_front ( const value_type val) [inline]

Adds an element to the front of the deque.

Definition at line 214 of file deque2.h.

References FMT_BID, STXXL_VERBOSE_DEQUE2, and UNLIKELY.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, 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 199 of file deque2.h.

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
size_type stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::size ( ) const [inline]

Returns the size of the deque.

Definition at line 462 of file deque2.h.

Referenced by main().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
void stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap ( deque2< ValueType, BlockSize, AllocStrategy, SizeType > &  obj) [inline]

Member Data Documentation

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
unsigned_type stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::m_alloc_count [private]

block allocation counter

Definition at line 90 of file deque2.h.

Referenced by stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
alloc_strategy_type stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::m_alloc_strategy [private]

block allocation strategy

Definition at line 87 of file deque2.h.

Referenced by stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap().

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

number of blocks to prefetch

Definition at line 99 of file deque2.h.

Referenced by stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
block_manager* stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::m_bm [private]

block manager used

Definition at line 96 of file deque2.h.

Referenced by stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap().

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

whether the m_pool object is own and should be deleted.

Definition at line 69 of file deque2.h.

Referenced by stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap().

template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
pool_type* stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::m_pool [private]
template<class ValueType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, class SizeType = stxxl::uint64>
size_type stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::m_size [private]

current number of items in the deque

Definition at line 66 of file deque2.h.

Referenced by stxxl::deque2< ValueType, BlockSize, AllocStrategy, SizeType >::swap().


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines