STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType > Class Template Reference

Detailed Description

template<class KeyType, class KeyCmp, unsigned RawSize, class BTreeType>
class stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >

Definition at line 27 of file node.h.

+ Inheritance diagram for stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >:
+ Collaboration diagram for stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >:

Classes

struct  metainfo_type
 
struct  value_compare
 

Public Types

enum  { raw_size = RawSize }
 
enum  { nelements = block_type::size - 1, max_size = nelements, min_size = nelements / 2 }
 
typedef BID< raw_sizebid_type
 
typedef block_type::const_iterator block_const_iterator
 
typedef block_type::iterator block_iterator
 
typedef typed_block< raw_size,
value_type, 0, metainfo_type
block_type
 
typedef BTreeType btree_type
 
typedef btree_type::value_type btree_value_type
 
typedef btree_type::const_iterator const_iterator
 
typedef const value_typeconst_reference
 
typedef btree_type::iterator iterator
 
typedef KeyCmp key_compare
 
typedef KeyType key_type
 
typedef btree_type::leaf_bid_type leaf_bid_type
 
typedef btree_type::leaf_type leaf_type
 
typedef bid_type node_bid_type
 
typedef node_cache
< normal_node, btree_type
node_cache_type
 
typedef self_type node_type
 
typedef value_typereference
 
typedef normal_node< KeyType,
KeyCmp, RawSize, BTreeType > 
self_type
 
typedef btree_type::size_type size_type
 
typedef std::pair< key_type,
bid_type
value_type
 

Public Member Functions

 normal_node (btree_type *btree, key_compare cmp)
 
virtual ~normal_node ()
 
reference back ()
 
const_reference back () const
 
key_type balance (normal_node &left, bool check_constraints=true)
 
iterator begin (unsigned height)
 
const_iterator begin (unsigned height) const
 
block_typeblock ()
 
void deallocate_children (unsigned height)
 
size_type erase (const key_type &k, unsigned height)
 
iterator find (const key_type &k, unsigned height)
 
const_iterator find (const key_type &k, unsigned height) const
 
reference front ()
 
const_reference front () const
 
void fuse (const normal_node &src)
 
void init (const bid_type &my_bid_)
 
std::pair< iterator, bool > insert (const btree_value_type &x, unsigned height, std::pair< key_type, bid_type > &splitter)
 
request_ptr load (const bid_type &bid)
 
iterator lower_bound (const key_type &k, unsigned height)
 
const_iterator lower_bound (const key_type &k, unsigned height) const
 
bid_type my_bid () const
 
reference operator[] (int i)
 
const_reference operator[] (int i) const
 
bool overflows () const
 
request_ptr prefetch (const bid_type &bid)
 
void push_back (const value_type &x)
 
void save ()
 
unsigned size () const
 
bool underflows () const
 
iterator upper_bound (const key_type &k, unsigned height)
 
const_iterator upper_bound (const key_type &k, unsigned height) const
 

Static Public Member Functions

static unsigned max_nelements ()
 
static unsigned min_nelements ()
 

Private Member Functions

template<class CacheType >
void fuse_or_balance (block_iterator UIt, CacheType &cache)
 
std::pair< key_type, bid_typeinsert (const std::pair< key_type, bid_type > &splitter, const block_iterator &place2insert)
 
- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Private Attributes

block_typem_block
 
btree_typem_btree
 
key_compare m_cmp
 
value_compare m_vcmp
 

Member Typedef Documentation

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef BID<raw_size> stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::bid_type

Definition at line 40 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef block_type::const_iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::block_const_iterator

Definition at line 60 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef block_type::iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::block_iterator

Definition at line 59 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef typed_block<raw_size, value_type, 0, metainfo_type> stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::block_type

Definition at line 52 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef BTreeType stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::btree_type

Definition at line 62 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef btree_type::value_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::btree_value_type

Definition at line 67 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef btree_type::const_iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::const_iterator

Definition at line 65 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef const value_type& stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::const_reference

Definition at line 45 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef btree_type::iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::iterator

Definition at line 64 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef KeyCmp stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::key_compare

Definition at line 35 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef KeyType stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::key_type

Definition at line 34 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef btree_type::leaf_bid_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::leaf_bid_type

Definition at line 68 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef btree_type::leaf_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::leaf_type

Definition at line 69 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef bid_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::node_bid_type

Definition at line 41 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef node_cache<normal_node, btree_type> stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::node_cache_type

Definition at line 71 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef self_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::node_type

Definition at line 42 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef value_type& stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::reference

Definition at line 44 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef normal_node<KeyType, KeyCmp, RawSize, BTreeType> stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::self_type

Definition at line 30 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef btree_type::size_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::size_type

Definition at line 63 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
typedef std::pair<key_type, bid_type> stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::value_type

Definition at line 43 of file node.h.

Member Enumeration Documentation

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
anonymous enum
Enumerator
raw_size 

Definition at line 37 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
anonymous enum
Enumerator
nelements 
max_size 
min_size 

Definition at line 54 of file node.h.

Constructor & Destructor Documentation

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
virtual stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::~normal_node ( )
inlinevirtual

Definition at line 199 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::normal_node ( btree_type btree,
key_compare  cmp 
)
inline

Definition at line 204 of file node.h.

Member Function Documentation

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_reference stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::back ( ) const
inline

Definition at line 308 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::begin ( unsigned  height)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::begin ( unsigned  height) const
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
block_type& stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::block ( )
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
void stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::deallocate_children ( unsigned  height)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
size_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::erase ( const key_type k,
unsigned  height 
)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::find ( const key_type k,
unsigned  height 
)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::find ( const key_type k,
unsigned  height 
) const
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
reference stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::front ( )
inline

Definition at line 303 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_reference stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::front ( ) const
inline

Definition at line 313 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
template<class CacheType >
void stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::fuse_or_balance ( block_iterator  UIt,
CacheType &  cache 
)
inlineprivate

Definition at line 142 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
void stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::init ( const bid_type my_bid_)
inline

Definition at line 282 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
std::pair<iterator, bool> stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::insert ( const btree_value_type x,
unsigned  height,
std::pair< key_type, bid_type > &  splitter 
)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
request_ptr stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::load ( const bid_type bid)
inline

Definition at line 269 of file node.h.

References stxxl::request_interface::wait().

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::lower_bound ( const key_type k,
unsigned  height 
)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::lower_bound ( const key_type k,
unsigned  height 
) const
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
static unsigned stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::max_nelements ( )
inlinestatic
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
static unsigned stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::min_nelements ( )
inlinestatic
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
bid_type stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::my_bid ( ) const
inline

Definition at line 258 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
reference stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::operator[] ( int  i)
inline

Definition at line 288 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_reference stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::operator[] ( int  i) const
inline

Definition at line 293 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
bool stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::overflows ( ) const
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
request_ptr stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::prefetch ( const bid_type bid)
inline

Definition at line 277 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
void stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::push_back ( const value_type x)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
void stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::save ( )
inline

Definition at line 263 of file node.h.

References stxxl::request_interface::wait().

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
bool stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::underflows ( ) const
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::upper_bound ( const key_type k,
unsigned  height 
)
inline
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
const_iterator stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::upper_bound ( const key_type k,
unsigned  height 
) const
inline

Member Data Documentation

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
block_type* stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::m_block
private
template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
btree_type* stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::m_btree
private

Definition at line 87 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
key_compare stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::m_cmp
private

Definition at line 88 of file node.h.

template<class KeyType , class KeyCmp , unsigned RawSize, class BTreeType >
value_compare stxxl::btree::normal_node< KeyType, KeyCmp, RawSize, BTreeType >::m_vcmp
private

Definition at line 89 of file node.h.


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