Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Private Attributes
stxxl::grow_shrink_stack< Config_ > Class Template Reference

Efficient implementation that uses prefetching and overlapping using internal buffers. More...

#include <stack.h>

Inheritance diagram for stxxl::grow_shrink_stack< Config_ >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::grow_shrink_stack< Config_ >:
Collaboration graph
[legend]

List of all members.

Public Types

enum  { blocks_per_page = cfg::blocks_per_page, block_size = cfg::block_size }
typedef Config_ cfg
typedef cfg::value_type value_type
typedef cfg::alloc_strategy alloc_strategy_type
typedef cfg::size_type size_type
typedef typed_block
< block_size, value_type
block_type
typedef BID< block_sizebid_type

Public Member Functions

 grow_shrink_stack ()
void swap (grow_shrink_stack &obj)
template<class stack_type >
 grow_shrink_stack (const stack_type &stack_)
 Construction from a stack.
virtual ~grow_shrink_stack ()
size_type size () const
bool empty () const
value_typetop ()
const value_typetop () const
void push (const value_type &val)
void pop ()

Private Attributes

size_type size_
unsigned_type cache_offset
value_typecurrent_element
simple_vector< block_typecache
simple_vector< block_type >
::iterator 
cache_buffers
simple_vector< block_type >
::iterator 
overlap_buffers
simple_vector< request_ptrrequests
std::vector< bid_typebids
alloc_strategy_type alloc_strategy

Detailed Description

template<class Config_>
class stxxl::grow_shrink_stack< Config_ >

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 260 of file stack.h.


Member Typedef Documentation

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

Definition at line 265 of file stack.h.

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

Definition at line 273 of file stack.h.

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

Definition at line 272 of file stack.h.

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

Definition at line 263 of file stack.h.

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

Definition at line 266 of file stack.h.

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

Definition at line 264 of file stack.h.


Member Enumeration Documentation

template<class Config_>
anonymous enum
Enumerator:
blocks_per_page 
block_size 

Definition at line 267 of file stack.h.


Constructor & Destructor Documentation

template<class Config_>
stxxl::grow_shrink_stack< Config_ >::grow_shrink_stack ( ) [inline]

Definition at line 287 of file stack.h.

template<class Config_>
template<class stack_type >
stxxl::grow_shrink_stack< Config_ >::grow_shrink_stack ( const stack_type &  stack_) [inline]

Construction from a stack.

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 317 of file stack.h.

template<class Config_>
virtual stxxl::grow_shrink_stack< Config_ >::~grow_shrink_stack ( ) [inline, virtual]

Definition at line 343 of file stack.h.

References STXXL_PRETTY_FUNCTION_NAME, and stxxl::wait_all().


Member Function Documentation

template<class Config_>
bool stxxl::grow_shrink_stack< Config_ >::empty ( ) const [inline]

Definition at line 359 of file stack.h.

template<class Config_>
void stxxl::grow_shrink_stack< Config_ >::pop ( ) [inline]

Definition at line 412 of file stack.h.

References std::swap(), UNLIKELY, and stxxl::wait_all().

template<class Config_>
void stxxl::grow_shrink_stack< Config_ >::push ( const value_type val) [inline]

Definition at line 373 of file stack.h.

References std::swap(), and UNLIKELY.

template<class Config_>
size_type stxxl::grow_shrink_stack< Config_ >::size ( ) const [inline]

Definition at line 355 of file stack.h.

template<class Config_>
void stxxl::grow_shrink_stack< Config_ >::swap ( grow_shrink_stack< Config_ > &  obj) [inline]
template<class Config_>
value_type& stxxl::grow_shrink_stack< Config_ >::top ( ) [inline]

Definition at line 363 of file stack.h.

template<class Config_>
const value_type& stxxl::grow_shrink_stack< Config_ >::top ( ) const [inline]

Definition at line 368 of file stack.h.


Member Data Documentation

template<class Config_>
alloc_strategy_type stxxl::grow_shrink_stack< Config_ >::alloc_strategy [private]

Definition at line 284 of file stack.h.

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

template<class Config_>
std::vector<bid_type> stxxl::grow_shrink_stack< Config_ >::bids [private]

Definition at line 283 of file stack.h.

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

template<class Config_>
simple_vector<block_type> stxxl::grow_shrink_stack< Config_ >::cache [private]

Definition at line 279 of file stack.h.

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

template<class Config_>
simple_vector<block_type>::iterator stxxl::grow_shrink_stack< Config_ >::cache_buffers [private]

Definition at line 280 of file stack.h.

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

template<class Config_>
unsigned_type stxxl::grow_shrink_stack< Config_ >::cache_offset [private]

Definition at line 277 of file stack.h.

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

template<class Config_>
value_type* stxxl::grow_shrink_stack< Config_ >::current_element [private]

Definition at line 278 of file stack.h.

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

template<class Config_>
simple_vector<block_type>::iterator stxxl::grow_shrink_stack< Config_ >::overlap_buffers [private]

Definition at line 281 of file stack.h.

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

template<class Config_>
simple_vector<request_ptr> stxxl::grow_shrink_stack< Config_ >::requests [private]

Definition at line 282 of file stack.h.

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

template<class Config_>
size_type stxxl::grow_shrink_stack< Config_ >::size_ [private]

Definition at line 276 of file stack.h.

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


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