STX B+ Tree Template Classes  0.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Types | Public Member Functions | Public Attributes | List of all members
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node Struct Reference

Extended structure of a leaf node in memory. More...

Public Types

typedef _Alloc::template
rebind< leaf_node >::other 
alloc_type
 Define an related allocator for the leaf_node structs. More...
 

Public Member Functions

void initialize ()
 Set variables to initial values. More...
 
bool isfull () const
 True if the node's slots are full. More...
 
bool isfew () const
 True if few used entries, less than half full. More...
 
bool isunderflow () const
 True if node has too few entries. More...
 
void set_slot (unsigned short slot, const pair_type &value)
 Set the (key,data) pair in slot. More...
 
void set_slot (unsigned short slot, const key_type &key)
 Set the key pair in slot. More...
 
- Public Member Functions inherited from stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node
void initialize (const unsigned short l)
 Delayed initialisation of constructed node. More...
 
bool isleafnode () const
 True if this is a leaf node. More...
 

Public Attributes

leaf_nodeprevleaf
 Double linked list pointers to traverse the leaves. More...
 
leaf_nodenextleaf
 Double linked list pointers to traverse the leaves. More...
 
key_type slotkey [leafslotmax]
 Keys of children or data pointers. More...
 
data_type slotdata [used_as_set?1:leafslotmax]
 Array of data. More...
 
- Public Attributes inherited from stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node
unsigned short level
 Level in the b-tree, if level == 0 -> leaf node. More...
 
unsigned short slotuse
 Number of key slotuse use, so number of valid children or data pointers. More...
 

Detailed Description

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
struct stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node

Extended structure of a leaf node in memory.

Contains pairs of keys and data items. Key and data slots are kept in separate arrays, because the key array is traversed very often compared to accessing the data items.

Definition at line 319 of file btree.h.

Member Typedef Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
typedef _Alloc::template rebind<leaf_node>::other stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::alloc_type

Define an related allocator for the leaf_node structs.

Definition at line 322 of file btree.h.

Member Function Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::initialize ( )
inline
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfew ( ) const
inline
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfull ( ) const
inline
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isunderflow ( ) const
inline
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot ( unsigned short  slot,
const pair_type value 
)
inline
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot ( unsigned short  slot,
const key_type key 
)
inline

Member Data Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::nextleaf
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::prevleaf
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
data_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotdata[used_as_set?1:leafslotmax]
template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
key_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotkey[leafslotmax]

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