STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > Class Template Reference

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 37 of file btree.h.

+ Inheritance diagram for stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >:
+ Collaboration diagram for stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >:

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 PDAllocStrategy alloc_strategy_type
 
typedef btree_const_iterator
< self_type
const_iterator
 
typedef value_type const * const_pointer
 
typedef const value_typeconst_reference
 
typedef DataType data_type
 
typedef stxxl::int64 difference_type
 
typedef btree_iterator< self_typeiterator
 
typedef iterator_map< self_typeiterator_map_type
 
typedef CompareType key_compare
 
typedef KeyType key_type
 
typedef leaf_type::bid_type leaf_bid_type
 
typedef leaf_type::block_type leaf_block_type
 
typedef node_cache< leaf_type,
self_type
leaf_cache_type
 
typedef normal_leaf< key_type,
data_type, key_compare,
RawLeafSize, self_type
leaf_type
 
typedef node_type::bid_type node_bid_type
 
typedef node_type::block_type node_block_type
 
typedef node_cache< node_type,
self_type
node_cache_type
 
typedef normal_node< key_type,
key_compare, RawNodeSize,
self_type
node_type
 
typedef value_typepointer
 
typedef value_typereference
 
typedef btree< KeyType,
DataType, CompareType,
RawNodeSize, RawLeafSize,
PDAllocStrategy > 
self_type
 
typedef stxxl::uint64 size_type
 
typedef leaf_type::value_compare value_compare
 
typedef std::pair< const
key_type, data_type
value_type
 

Public Member Functions

 btree (unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
 
 btree (const key_compare &key_compare, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
 
template<class InputIterator >
 btree (InputIterator begin, InputIterator end, 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 begin, InputIterator end, 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)
 
virtual ~btree ()
 
iterator begin ()
 
const_iterator begin () const
 
void clear ()
 
size_type count (const key_type &k)
 
void disable_prefetching ()
 
bool empty () const
 
void enable_prefetching ()
 
iterator end ()
 
const_iterator end () 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)
 
void erase (iterator pos)
 
void erase (iterator first, iterator last)
 
iterator find (const key_type &k)
 
const_iterator find (const key_type &k) const
 
std::pair< iterator, bool > insert (const value_type &x)
 
iterator insert (iterator, const value_type &x)
 
template<class InputIterator >
void insert (InputIterator b, InputIterator e)
 
key_compare key_comp () const
 
iterator lower_bound (const key_type &k)
 
const_iterator lower_bound (const key_type &k) const
 
size_type max_size () const
 
data_typeoperator[] (const key_type &k)
 
bool prefetching_enabled ()
 
void print_statistics (std::ostream &o) const
 
void reset_statistics ()
 
size_type size () const
 
void swap (btree &obj)
 
iterator upper_bound (const key_type &k)
 
const_iterator upper_bound (const key_type &k) const
 
value_compare value_comp () const
 

Private Types

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

Private Member Functions

template<class InputIterator >
void bulk_construction (InputIterator begin, InputIterator end, double node_fill_factor, double leaf_fill_factor)
 
void create_empty_leaf ()
 
void deallocate_children ()
 
template<class CacheType >
void fuse_or_balance (root_node_iterator_type uit, CacheType &cache)
 
void insert_into_root (const std::pair< key_type, node_bid_type > &splitter)
 
- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Private Attributes

alloc_strategy_type m_alloc_strategy
 
block_managerm_bm
 
iterator m_end_iterator
 
unsigned int m_height
 
iterator_map_type m_iterator_map
 
key_compare m_key_compare
 
leaf_cache_type m_leaf_cache
 
node_cache_type m_node_cache
 
bool m_prefetching_enabled
 
root_node_type m_root_node
 
size_type m_size
 

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<self_type> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::const_iterator

Definition at line 66 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 41 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<self_type> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::iterator

Definition at line 65 of file btree.h.

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

Definition at line 69 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 42 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 40 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 61 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 60 of file btree.h.

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

Definition at line 62 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, self_type> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::leaf_type

Definition at line 58 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 74 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 72 of file btree.h.

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

Definition at line 75 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, self_type> stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::node_type

Definition at line 71 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 100 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 99 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 101 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 98 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 >::self_type

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 78 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 80 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 433 of file btree.h.

References STXXL_VERBOSE1.

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 key_compare,
unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes 
)
inline

Definition at line 454 of file btree.h.

References STXXL_VERBOSE1.

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

Definition at line 473 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  begin,
InputIterator  end,
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 971 of file btree.h.

References STXXL_VERBOSE1.

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  begin,
InputIterator  end,
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 1007 of file btree.h.

References STXXL_VERBOSE1.

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  begin,
InputIterator  end,
double  node_fill_factor,
double  leaf_fill_factor 
)
inlineprivate

Definition at line 263 of file btree.h.

References stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::back(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::back(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::balance(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::balance(), stxxl::div_ceil(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::end(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::fuse(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::fuse(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, 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, LogNElem, BTreeType >::my_bid(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::overflows(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::overflows(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::pred(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::push_back(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::push_back(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::size(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::size(), STXXL_THROW2, STXXL_VERBOSE1, stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, BTreeType >::succ(), stxxl::btree::normal_leaf< KeyType, DataType, KeyCmp, LogNElem, 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 947 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 921 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 ( )
inlineprivate
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 ( )
inlineprivate
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 1078 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 495 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 >::enable_prefetching ( )
inline

Definition at line 1074 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 613 of file btree.h.

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 618 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 809 of file btree.h.

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 830 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  pos)
inline

Definition at line 929 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 1040 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 
)
inlineprivate

Definition at line 167 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 941 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 962 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)
inlineprivate
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 1049 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 >::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 490 of file btree.h.

References max().

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 623 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 1082 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 1087 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 1094 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 485 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 >::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 1053 of file btree.h.

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 >::m_alloc_strategy
private
template<class KeyType , class DataType , class CompareType , unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy >
block_manager* stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_bm
private

Definition at line 95 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 >::m_end_iterator
private
template<class KeyType , class DataType , class CompareType , unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy >
unsigned int stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_height
private
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 >::m_iterator_map
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 >::m_key_compare
private
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 >::m_leaf_cache
mutableprivate
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 >::m_node_cache
mutableprivate
template<class KeyType , class DataType , class CompareType , unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy >
bool stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_prefetching_enabled
private

Definition at line 94 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 >::m_root_node
private
template<class KeyType , class DataType , class CompareType , unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy >
size_type stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_size
private

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