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.
|
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_type & | const_reference |
|
typedef DataType | data_type |
|
typedef stxxl::int64 | difference_type |
|
typedef btree_iterator< self_type > | iterator |
|
typedef iterator_map< self_type > | iterator_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_type * | pointer |
|
typedef value_type & | reference |
|
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 |
|
|
| 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, iterator > | equal_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_type & | operator[] (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 |
|
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 |
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 |
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 >::create_empty_leaf |
( |
| ) |
|
|
inlineprivate |
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 |
template<class KeyType , class DataType , class CompareType , unsigned RawNodeSize, unsigned RawLeafSize, class PDAllocStrategy >
Definition at line 106 of file btree.h.
References stxxl::mng_local::element_block< Type, Size >::begin(), stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::block(), stxxl::mng_local::block_w_info< Type, RawSize, NBids, MetaInfoType >::info, stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::size(), STXXL_ASSERT, STXXL_THROW2, and STXXL_VERBOSE1.
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 1058 of file btree.h.
References stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_alloc_strategy, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_end_iterator, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_height, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_iterator_map, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_key_compare, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_leaf_cache, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_node_cache, stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_root_node, and stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::m_size.