Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes
stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > Class Template Reference

#include <btree.h>

Inheritance diagram for stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >:
Collaboration graph
[legend]

List of all members.

Public Types

enum  { min_node_size = node_type::min_size, max_node_size = node_type::max_size, min_leaf_size = leaf_type::min_size, max_leaf_size = leaf_type::max_size }
typedef KeyType key_type
typedef DataType data_type
typedef CompareType key_compare
typedef btree< KeyType,
DataType, CompareType,
RawNodeSize, RawLeafSize,
PDAllocStrategy > 
SelfType
typedef PDAllocStrategy alloc_strategy_type
typedef stxxl::uint64 size_type
typedef stxxl::int64 difference_type
typedef std::pair< const
key_type, data_type
value_type
typedef value_typereference
typedef const value_typeconst_reference
typedef value_typepointer
typedef value_type const * const_pointer
typedef normal_leaf< key_type,
data_type, key_compare,
RawLeafSize, SelfType
leaf_type
typedef leaf_type::block_type leaf_block_type
typedef leaf_type::bid_type leaf_bid_type
typedef node_cache< leaf_type,
SelfType
leaf_cache_type
typedef btree_iterator< SelfTypeiterator
typedef btree_const_iterator
< SelfType
const_iterator
typedef iterator_map< SelfTypeiterator_map_type
typedef normal_node< key_type,
key_compare, RawNodeSize,
SelfType
node_type
typedef node_type::block_type node_block_type
typedef node_type::bid_type node_bid_type
typedef node_cache< node_type,
SelfType
node_cache_type
typedef leaf_type::value_compare value_compare

Public Member Functions

 btree (unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
 btree (const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
virtual ~btree ()
size_type size () const
size_type max_size () const
bool empty () const
std::pair< iterator, bool > insert (const value_type &x)
iterator begin ()
const_iterator begin () const
iterator end ()
const_iterator end () const
data_typeoperator[] (const key_type &k)
iterator find (const key_type &k)
const_iterator find (const key_type &k) const
iterator lower_bound (const key_type &k)
const_iterator lower_bound (const key_type &k) const
iterator upper_bound (const key_type &k)
const_iterator upper_bound (const key_type &k) const
std::pair< iterator, iteratorequal_range (const key_type &k)
std::pair< const_iterator,
const_iterator
equal_range (const key_type &k) const
size_type erase (const key_type &k)
size_type count (const key_type &k)
void erase (iterator pos)
iterator insert (iterator, const value_type &x)
void clear ()
template<class InputIterator >
void insert (InputIterator b, InputIterator e)
template<class InputIterator >
 btree (InputIterator b, InputIterator e, const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes, bool range_sorted=false, double node_fill_factor=0.75, double leaf_fill_factor=0.6)
template<class InputIterator >
 btree (InputIterator b, InputIterator e, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes, bool range_sorted=false, double node_fill_factor=0.75, double leaf_fill_factor=0.6)
void erase (iterator first, iterator last)
key_compare key_comp () const
value_compare value_comp () const
void swap (btree &obj)
void enable_prefetching ()
void disable_prefetching ()
bool prefetching_enabled ()
void print_statistics (std::ostream &o) const
void reset_statistics ()

Private Types

typedef std::map< key_type,
node_bid_type, key_compare
root_node_type
typedef root_node_type::iterator root_node_iterator_type
typedef
root_node_type::const_iterator 
root_node_const_iterator_type
typedef std::pair< key_type,
node_bid_type
root_node_pair_type

Private Member Functions

void insert_into_root (const std::pair< key_type, node_bid_type > &splitter)
template<class CacheType >
void fuse_or_balance (root_node_iterator_type UIt, CacheType &cache_)
void create_empty_leaf ()
void deallocate_children ()
template<class InputIterator >
void bulk_construction (InputIterator b, InputIterator e, double node_fill_factor, double leaf_fill_factor)

Private Attributes

key_compare key_compare_
node_cache_type node_cache_
leaf_cache_type leaf_cache_
iterator_map_type iterator_map_
size_type size_
unsigned_type height_
bool prefetching_enabled_
block_managerbm_
alloc_strategy_type alloc_strategy_
root_node_type root_node_
iterator end_iterator

Detailed Description

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
class stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >

Definition at line 38 of file btree.h.


Member Typedef Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef PDAllocStrategy stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::alloc_strategy_type

Definition at line 47 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef btree_const_iterator<SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::const_iterator

Definition at line 67 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef value_type const* stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::const_pointer

Definition at line 55 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef const value_type& stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::const_reference

Definition at line 53 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef DataType stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::data_type

Definition at line 42 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef stxxl::int64 stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::difference_type

Definition at line 50 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef btree_iterator<SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::iterator

Definition at line 66 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef iterator_map<SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::iterator_map_type

Definition at line 70 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef CompareType stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::key_compare

Definition at line 43 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef KeyType stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::key_type

Definition at line 41 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef leaf_type::bid_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::leaf_bid_type

Definition at line 62 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef leaf_type::block_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::leaf_block_type

Definition at line 61 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef node_cache<leaf_type, SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::leaf_cache_type

Definition at line 63 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::leaf_type

Definition at line 59 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef node_type::bid_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::node_bid_type

Definition at line 75 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef node_type::block_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::node_block_type

Definition at line 73 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef node_cache<node_type, SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::node_cache_type

Definition at line 76 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef normal_node<key_type, key_compare, RawNodeSize, SelfType> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::node_type

Definition at line 72 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef value_type* stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::pointer

Definition at line 54 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef value_type& stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::reference

Definition at line 52 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef root_node_type::const_iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::root_node_const_iterator_type [private]

Definition at line 101 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef root_node_type::iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::root_node_iterator_type [private]

Definition at line 100 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef std::pair<key_type, node_bid_type> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::root_node_pair_type [private]

Definition at line 102 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef std::map<key_type, node_bid_type, key_compare> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::root_node_type [private]

Definition at line 99 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::SelfType

Definition at line 45 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef stxxl::uint64 stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::size_type

Definition at line 49 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef leaf_type::value_compare stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::value_compare

Definition at line 79 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
typedef std::pair<const key_type, data_type> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::value_type

Definition at line 51 of file btree.h.


Member Enumeration Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
anonymous enum
Enumerator:
min_node_size 
max_node_size 
min_leaf_size 
max_leaf_size 

Definition at line 81 of file btree.h.


Constructor & Destructor Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::btree ( unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes 
) [inline]

Definition at line 397 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::btree ( const key_compare c_,
unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes 
) [inline]

Definition at line 420 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
virtual stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::~btree ( ) [inline, virtual]

Definition at line 440 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
template<class InputIterator >
stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::btree ( InputIterator  b,
InputIterator  e,
const key_compare c_,
unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes,
bool  range_sorted = false,
double  node_fill_factor = 0.75,
double  leaf_fill_factor = 0.6 
) [inline]

Definition at line 926 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
template<class InputIterator >
stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::btree ( InputIterator  b,
InputIterator  e,
unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes,
bool  range_sorted = false,
double  node_fill_factor = 0.75,
double  leaf_fill_factor = 0.6 
) [inline]

Definition at line 964 of file btree.h.


Member Function Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::begin ( ) [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
const_iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::begin ( ) const [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
template<class InputIterator >
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::bulk_construction ( InputIterator  b,
InputIterator  e,
double  node_fill_factor,
double  leaf_fill_factor 
) [inline, private]

Definition at line 258 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::back(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::back(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::balance(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::balance(), stxxl::div_ceil(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::end(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::fuse(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::fuse(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::max_nelements(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::max_nelements(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::min_nelements(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::my_bid(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::overflows(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::overflows(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::pred(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::push_back(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::push_back(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::size(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::size(), STXXL_THROW, stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::succ(), std::swap(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::underflows(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::underflows().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::clear ( ) [inline]

Definition at line 902 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
size_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::count ( const key_type k) [inline]

Definition at line 877 of file btree.h.

References stxxl::find().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::create_empty_leaf ( ) [inline, private]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::deallocate_children ( ) [inline, private]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::disable_prefetching ( ) [inline]

Definition at line 1038 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
bool stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::empty ( ) const [inline]

Definition at line 461 of file btree.h.

Referenced by main().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::enable_prefetching ( ) [inline]

Definition at line 1034 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::end ( ) [inline]

Definition at line 578 of file btree.h.

Referenced by C(), main(), and NC().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
const_iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::end ( ) const [inline]

Definition at line 583 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
std::pair<iterator, iterator> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::equal_range ( const key_type k) [inline]

Definition at line 774 of file btree.h.

Referenced by main().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
std::pair<const_iterator, const_iterator> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::equal_range ( const key_type k) const [inline]

Definition at line 791 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
size_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::erase ( const key_type k) [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::erase ( iterator  pos) [inline]

Definition at line 885 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::erase ( iterator  first,
iterator  last 
) [inline]

Definition at line 998 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::find ( const key_type k) [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
const_iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::find ( const key_type k) const [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
template<class CacheType >
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::fuse_or_balance ( root_node_iterator_type  UIt,
CacheType &  cache_ 
) [inline, private]

Definition at line 171 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
std::pair<iterator, bool> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::insert ( const value_type x) [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::insert ( iterator  ,
const value_type x 
) [inline]

Definition at line 897 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
template<class InputIterator >
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::insert ( InputIterator  b,
InputIterator  e 
) [inline]

Definition at line 917 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::insert_into_root ( const std::pair< key_type, node_bid_type > &  splitter) [inline, private]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
key_compare stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::key_comp ( ) const [inline]

Definition at line 1008 of file btree.h.

Referenced by main().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::lower_bound ( const key_type k) [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
const_iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::lower_bound ( const key_type k) const [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
size_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::max_size ( ) const [inline]

Definition at line 456 of file btree.h.

Referenced by main().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
data_type& stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::operator[] ( const key_type k) [inline]

Definition at line 588 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
bool stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::prefetching_enabled ( ) [inline]

Definition at line 1042 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::print_statistics ( std::ostream &  o) const [inline]

Definition at line 1047 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::reset_statistics ( ) [inline]

Definition at line 1054 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
size_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::size ( ) const [inline]

Definition at line 451 of file btree.h.

Referenced by main().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
void stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::swap ( btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > &  obj) [inline]

Definition at line 1017 of file btree.h.

References std::swap().

Referenced by std::swap().

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::upper_bound ( const key_type k) [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
const_iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::upper_bound ( const key_type k) const [inline]
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
value_compare stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::value_comp ( ) const [inline]

Definition at line 1012 of file btree.h.

Referenced by main().


Member Data Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
alloc_strategy_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::alloc_strategy_ [private]

Definition at line 97 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
block_manager* stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::bm_ [private]

Definition at line 96 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::end_iterator [private]

Definition at line 106 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
unsigned_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::height_ [private]

Definition at line 94 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
iterator_map_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::iterator_map_ [private]

Definition at line 92 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
key_compare stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::key_compare_ [private]

Definition at line 89 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
leaf_cache_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::leaf_cache_ [mutable, private]

Definition at line 91 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
node_cache_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::node_cache_ [mutable, private]

Definition at line 90 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
bool stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::prefetching_enabled_ [private]

Definition at line 95 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
root_node_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::root_node_ [private]

Definition at line 105 of file btree.h.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy>
size_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::size_ [private]

Definition at line 93 of file btree.h.


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