STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Private Attributes | List of all members
stxxl::grow_shrink_stack< StackConfig > Class Template Reference
stack

Detailed Description

template<class StackConfig>
class stxxl::grow_shrink_stack< StackConfig >

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 std::stack.

Warning
The amortized complexity of operation is not O(1/DB), rather O(DB)

Definition at line 302 of file stack.h.

+ Inheritance diagram for stxxl::grow_shrink_stack< StackConfig >:
+ Collaboration diagram for stxxl::grow_shrink_stack< StackConfig >:

Public Types

enum  { blocks_per_page = cfg::blocks_per_page, block_size = cfg::block_size }
 
typedef cfg::alloc_strategy alloc_strategy_type
 
typedef BID< block_size > bid_type
 
typedef typed_block
< block_size, value_type > 		block_type
 type of block used in disk-memory transfers More...
 
typedef StackConfig cfg
 
typedef cfg::size_type size_type
 type for sizes (64-bit) More...
 
typedef cfg::value_type value_type
 type of the elements stored in the stack More...
 

Public Member Functions

Constructors/Destructor
 grow_shrink_stack ()
 Default constructor: creates empty stack. More...
 
Accessor Functions
void swap (grow_shrink_stack &obj)
 
value_type & top ()
 Return mutable reference to the element at the top of the stack. Precondition: stack is not empty(). More...
 
const value_type & top () const
 Return constant reference to the element at the top of the stack. Precondition: stack is not empty(). More...
 
void push (const value_type &val)
 Inserts an element at the top of the stack. Postconditions: size() is incremented by 1, and top() is the inserted element. More...
 
void pop ()
 Removes the element at the top of the stack. Precondition: stack is not empty(). Postcondition: size() is decremented. More...
 
Constructors/Destructors
template<class StackType >
 grow_shrink_stack (const StackType &stack_)
 Copy-construction from a another stack of any type. More...
 
virtual ~grow_shrink_stack ()
 
Capacity
size_type size () const
 Returns the number of elements contained in the stack. More...
 
bool empty () const
 Returns true if the stack is empty. More...
 

Private Attributes

alloc_strategy_type alloc_strategy
 
std::vector< bid_type > bids
 
simple_vector< block_type > cache
 
simple_vector< block_type >
::iterator 		cache_buffers
 
unsigned_type cache_offset
 
value_type * current_element
 
size_type m_size
 
simple_vector< block_type >
::iterator 		overlap_buffers
 
simple_vector< request_ptr > requests
 

Additional Inherited Members

- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Member Typedef Documentation

template<class StackConfig>
typedef cfg::alloc_strategy stxxl::grow_shrink_stack< StackConfig >::alloc_strategy_type

Definition at line 308 of file stack.h.

template<class StackConfig>
typedef BID<block_size> stxxl::grow_shrink_stack< StackConfig >::bid_type

Definition at line 318 of file stack.h.

template<class StackConfig>
typedef typed_block<block_size, value_type> stxxl::grow_shrink_stack< StackConfig >::block_type

type of block used in disk-memory transfers

Definition at line 317 of file stack.h.

template<class StackConfig>
typedef StackConfig stxxl::grow_shrink_stack< StackConfig >::cfg

Definition at line 305 of file stack.h.

template<class StackConfig>
typedef cfg::size_type stxxl::grow_shrink_stack< StackConfig >::size_type

type for sizes (64-bit)

Definition at line 310 of file stack.h.

template<class StackConfig>
typedef cfg::value_type stxxl::grow_shrink_stack< StackConfig >::value_type

type of the elements stored in the stack

Definition at line 307 of file stack.h.

Member Enumeration Documentation

template<class StackConfig>
anonymous enum
Enumerator
blocks_per_page 
block_size 

Definition at line 311 of file stack.h.

Constructor & Destructor Documentation

template<class StackConfig>
stxxl::grow_shrink_stack< StackConfig >::grow_shrink_stack ( )
inline

Default constructor: creates empty stack.

Definition at line 336 of file stack.h.

template<class StackConfig>
template<class StackType >
stxxl::grow_shrink_stack< StackConfig >::grow_shrink_stack ( const StackType &  stack_)
inline

Copy-construction from a another stack of any type.

Parameters
stack_stack object (could be external or internal, important is that it must have a copy constructor, top() and pop() methods )

Definition at line 376 of file stack.h.

template<class StackConfig>
virtual stxxl::grow_shrink_stack< StackConfig >::~grow_shrink_stack ( )
inlinevirtual

Definition at line 402 of file stack.h.

References STXXL_PRETTY_FUNCTION_NAME, STXXL_VERBOSE, and stxxl::wait_all().

Member Function Documentation

template<class StackConfig>
bool stxxl::grow_shrink_stack< StackConfig >::empty ( ) const
inline

Returns true if the stack is empty.

Definition at line 426 of file stack.h.

template<class StackConfig>
void stxxl::grow_shrink_stack< StackConfig >::pop ( )
inline

Removes the element at the top of the stack. Precondition: stack is not empty(). Postcondition: size() is decremented.

Definition at line 496 of file stack.h.

References STXXL_VERBOSE2, UNLIKELY, and stxxl::wait_all().

template<class StackConfig>
void stxxl::grow_shrink_stack< StackConfig >::push ( const value_type &  val)
inline

Inserts an element at the top of the stack. Postconditions: size() is incremented by 1, and top() is the inserted element.

Definition at line 454 of file stack.h.

References STXXL_VERBOSE2, and UNLIKELY.

template<class StackConfig>
size_type stxxl::grow_shrink_stack< StackConfig >::size ( ) const
inline

Returns the number of elements contained in the stack.

Definition at line 421 of file stack.h.

template<class StackConfig>
void stxxl::grow_shrink_stack< StackConfig >::swap ( grow_shrink_stack< StackConfig > &  obj)
inline

Definition at line 354 of file stack.h.

References stxxl::grow_shrink_stack< StackConfig >::alloc_strategy, stxxl::grow_shrink_stack< StackConfig >::bids, stxxl::grow_shrink_stack< StackConfig >::cache, stxxl::grow_shrink_stack< StackConfig >::cache_buffers, stxxl::grow_shrink_stack< StackConfig >::cache_offset, stxxl::grow_shrink_stack< StackConfig >::current_element, stxxl::grow_shrink_stack< StackConfig >::m_size, stxxl::grow_shrink_stack< StackConfig >::overlap_buffers, and stxxl::grow_shrink_stack< StackConfig >::requests.

template<class StackConfig>
value_type& stxxl::grow_shrink_stack< StackConfig >::top ( )
inline

Return mutable reference to the element at the top of the stack. Precondition: stack is not empty().

Definition at line 438 of file stack.h.

template<class StackConfig>
const value_type& stxxl::grow_shrink_stack< StackConfig >::top ( ) const
inline

Return constant reference to the element at the top of the stack. Precondition: stack is not empty().

Definition at line 446 of file stack.h.

Member Data Documentation

template<class StackConfig>
alloc_strategy_type stxxl::grow_shrink_stack< StackConfig >::alloc_strategy
private

Definition at line 329 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
std::vector<bid_type> stxxl::grow_shrink_stack< StackConfig >::bids
private

Definition at line 328 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
simple_vector<block_type> stxxl::grow_shrink_stack< StackConfig >::cache
private

Definition at line 324 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
simple_vector<block_type>::iterator stxxl::grow_shrink_stack< StackConfig >::cache_buffers
private

Definition at line 325 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
unsigned_type stxxl::grow_shrink_stack< StackConfig >::cache_offset
private

Definition at line 322 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
value_type* stxxl::grow_shrink_stack< StackConfig >::current_element
private

Definition at line 323 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
size_type stxxl::grow_shrink_stack< StackConfig >::m_size
private

Definition at line 321 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
simple_vector<block_type>::iterator stxxl::grow_shrink_stack< StackConfig >::overlap_buffers
private

Definition at line 326 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

template<class StackConfig>
simple_vector<request_ptr> stxxl::grow_shrink_stack< StackConfig >::requests
private

Definition at line 327 of file stack.h.

Referenced by stxxl::grow_shrink_stack< StackConfig >::swap().

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