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 >:

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

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_type &	reference
typedef const value_type &	const_reference
typedef value_type *	pointer
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< SelfType >	iterator
typedef btree_const_iterator < SelfType >	const_iterator
typedef iterator_map< SelfType >	iterator_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_type &	operator[] (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, 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)
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_manager *	bm_
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]

Definition at line 523 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::begin(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::begin().

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 >::begin

(

)

const [inline]

Definition at line 552 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::begin(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::begin().

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]

Definition at line 222 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::end().

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]

Definition at line 231 of file btree.h.

References stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::deallocate_children().

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]

Definition at line 807 of file btree.h.

References stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::back(), stxxl::element_block< T, Size_ >::begin(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::block(), stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::erase(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::size(), and stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::underflows().

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 >::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]

Definition at line 593 of file btree.h.

References stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::find(), and stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::find().

Referenced by main().

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]

Definition at line 624 of file btree.h.

References stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::find(), and stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::find().

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]

Definition at line 466 of file btree.h.

References stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::insert(), and stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::insert().

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 >::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]

Definition at line 109 of file btree.h.

References stxxl::element_block< T, Size_ >::begin(), stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::block(), stxxl::block_w_info< T_, RawSize_, NBids_, InfoType_ >::info, stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::size(), and STXXL_THROW.

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]

Definition at line 655 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::lower_bound(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::lower_bound().

Referenced by main().

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]

Definition at line 684 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::lower_bound(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::lower_bound().

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]

Definition at line 714 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::upper_bound(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::upper_bound().

Referenced by main().

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]

Definition at line 744 of file btree.h.

References stxxl::btree::normal_leaf< KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType >::upper_bound(), and stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::upper_bound().

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:

• include/stxxl/bits/containers/btree/btree.h