Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes
stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType > Class Template Reference

#include <node.h>

Inheritance diagram for stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >:
Collaboration graph
[legend]

List of all members.

Classes

struct  InfoType
struct  value_compare

Public Types

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

Public Member Functions

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

Private Member Functions

std::pair< key_type, bid_typeinsert (const std::pair< key_type, bid_type > &splitter, const block_iterator &place2insert)
template<class CacheType >
void fuse_or_balance (block_iterator UIt, CacheType &cache_)

Private Attributes

block_typeblock_
btree_typebtree_
key_compare cmp_
value_compare vcmp_

Detailed Description

template<class KeyType_, class KeyCmp_, unsigned RawSize_, class BTreeType>
class stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >

Definition at line 28 of file node.h.


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 41 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 62 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 61 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
typedef typed_block<raw_size, value_type, 0, InfoType> stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::block_type

Definition at line 54 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 64 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 69 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 67 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 46 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 66 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 36 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 35 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 70 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 71 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 42 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 73 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
typedef SelfType stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::node_type

Definition at line 43 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 45 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 >::SelfType

Definition at line 31 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 65 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 44 of file node.h.


Member Enumeration Documentation

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
anonymous enum
Enumerator:
raw_size 

Definition at line 38 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
anonymous enum
Enumerator:
nelements 
max_size 
min_size 

Definition at line 56 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 ( ) [inline, virtual]

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 >
reference stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::back ( ) [inline]
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 307 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
key_type stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::balance ( normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType > &  Left) [inline]
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 302 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 312 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
void stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::fuse ( const normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType > &  Src) [inline]
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_ 
) [inline, private]

Definition at line 146 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 281 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
std::pair<key_type, bid_type> stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::insert ( const std::pair< key_type, bid_type > &  splitter,
const block_iterator place2insert 
) [inline, private]
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 268 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 >
unsigned stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::max_nelements ( ) const [inline]
template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
unsigned stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::min_nelements ( ) const [inline]
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 257 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 287 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 292 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 276 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 262 of file node.h.

References stxxl::request_interface::wait().

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
unsigned stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::size ( ) const [inline]
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 >::block_ [private]
template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
btree_type* stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::btree_ [private]

Definition at line 89 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
key_compare stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::cmp_ [private]

Definition at line 90 of file node.h.

template<class KeyType_ , class KeyCmp_ , unsigned RawSize_, class BTreeType >
value_compare stxxl::btree::normal_node< KeyType_, KeyCmp_, RawSize_, BTreeType >::vcmp_ [private]

Definition at line 91 of file node.h.


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