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

Detailed Description

template<class StackConfig>
class stxxl::normal_stack< StackConfig >

External stack container. Introduction to stack container: see STXXL Stack tutorial.
Design and Internals of stack container: see 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 std::stack.
To gain full bandwidth of disks StackConfig::BlocksPerPage must >= number of disks

Definition at line 61 of file stack.h.

+ Inheritance diagram for stxxl::normal_stack< StackConfig >:
+ Collaboration diagram for stxxl::normal_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/Destructors
 normal_stack ()
 Default constructor: creates empty stack. More...
 
template<class StackType >
 normal_stack (const StackType &stack_)
 Copy-construction from a another stack of any type. More...
 
virtual ~normal_stack ()
 
Accessor Functions
void swap (normal_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...
 
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 Member Functions

value_type * element (unsigned_type offset)
 
- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Private Attributes

alloc_strategy_type alloc_strategy
 
simple_vector< block_type >
::iterator 		back_page
 
std::vector< bid_type > bids
 
simple_vector< block_type > cache
 
unsigned_type cache_offset
 
value_type * current_element
 
simple_vector< block_type >
::iterator 		front_page
 
size_type m_size
 

Member Typedef Documentation

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

Definition at line 67 of file stack.h.

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

Definition at line 77 of file stack.h.

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

type of block used in disk-memory transfers

Definition at line 76 of file stack.h.

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

Definition at line 64 of file stack.h.

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

type for sizes (64-bit)

Definition at line 69 of file stack.h.

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

type of the elements stored in the stack

Definition at line 66 of file stack.h.

Member Enumeration Documentation

template<class StackConfig>
anonymous enum
Enumerator
blocks_per_page 
block_size 

Definition at line 70 of file stack.h.

Constructor & Destructor Documentation

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

Default constructor: creates empty stack.

Definition at line 94 of file stack.h.

template<class StackConfig>
template<class StackType >
stxxl::normal_stack< StackConfig >::normal_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 130 of file stack.h.

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

Definition at line 155 of file stack.h.

References STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE.

Member Function Documentation

template<class StackConfig>
value_type* stxxl::normal_stack< StackConfig >::element ( unsigned_type  offset)
inlineprivate

Definition at line 286 of file stack.h.

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

Returns true if the stack is empty.

Definition at line 173 of file stack.h.

template<class StackConfig>
void stxxl::normal_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 244 of file stack.h.

References stxxl::simple_vector< ValueType >::begin(), STXXL_VERBOSE2, UNLIKELY, and stxxl::wait_all().

template<class StackConfig>
void stxxl::normal_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 201 of file stack.h.

References stxxl::simple_vector< ValueType >::begin(), STXXL_VERBOSE2, UNLIKELY, and stxxl::wait_all().

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

Returns the number of elements contained in the stack.

Definition at line 167 of file stack.h.

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

Definition at line 109 of file stack.h.

References stxxl::normal_stack< StackConfig >::alloc_strategy, stxxl::normal_stack< StackConfig >::back_page, stxxl::normal_stack< StackConfig >::bids, stxxl::normal_stack< StackConfig >::cache, stxxl::normal_stack< StackConfig >::cache_offset, stxxl::normal_stack< StackConfig >::current_element, stxxl::normal_stack< StackConfig >::front_page, and stxxl::normal_stack< StackConfig >::m_size.

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

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

Definition at line 185 of file stack.h.

template<class StackConfig>
const value_type& stxxl::normal_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 193 of file stack.h.

Member Data Documentation

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

Definition at line 87 of file stack.h.

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

template<class StackConfig>
simple_vector<block_type>::iterator stxxl::normal_stack< StackConfig >::back_page
private

Definition at line 85 of file stack.h.

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

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

Definition at line 86 of file stack.h.

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

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

Definition at line 83 of file stack.h.

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

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

Definition at line 81 of file stack.h.

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

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

Definition at line 82 of file stack.h.

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

template<class StackConfig>
simple_vector<block_type>::iterator stxxl::normal_stack< StackConfig >::front_page
private

Definition at line 84 of file stack.h.

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

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

Definition at line 80 of file stack.h.

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

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