stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node Struct Reference

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

Inherits stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node.

List of all members.

Public Member Functions

void initialize ()
 Set variables to initial values.
bool isfull () const
 True if the node's slots are full.
bool isfew () const
 True if few used entries, less than half full.
bool isunderflow () const
 True if node has too few entries.

Public Attributes

leaf_nodeprevleaf
 Double linked list pointers to traverse the leaves.
leaf_nodenextleaf
 Double linked list pointers to traverse the leaves.
key_type slotkey [leafslotmax]
 Keys of children or data pointers.
data_type slotdata [leafslotmax]
 Array of data.


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>
struct stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 280 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>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::initialize (  )  [inline]

Set variables to initial values.

Definition at line 295 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node::initialize(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::nextleaf, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::prevleaf.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::allocate_leaf().

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>
bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::isfull (  )  const [inline]

True if the node's slots are full.

Definition at line 302 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leafslotmax, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node::slotuse.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert_descend(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_leaf_node().

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>
bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::isfew (  )  const [inline]

True if few used entries, less than half full.

Definition at line 308 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::minleafslots, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node::slotuse.

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>
bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::isunderflow (  )  const [inline]

True if node has too few entries.

Definition at line 314 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::minleafslots, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node::slotuse.


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>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::prevleaf

Double linked list pointers to traverse the leaves.

Definition at line 283 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::copy_recursive(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::initialize(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::operator--(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::operator--(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::restore_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_leaf_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify_leaflinks(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify_node().

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>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::nextleaf

Double linked list pointers to traverse the leaves.

Definition at line 286 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::copy_recursive(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::count(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::initialize(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::operator++(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::operator++(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::restore_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_leaf_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify_leaflinks(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify_node().

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>
key_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::slotkey[leafslotmax]

Keys of children or data pointers.

Definition at line 289 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::copy_recursive(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::count(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::exists(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::operator *(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::operator *(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::operator->(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::operator->(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_leaf_node(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify_leaflinks().

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>
data_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node::slotdata[leafslotmax]

Array of data.

Definition at line 292 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::copy_recursive(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::operator *(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::operator *(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator::operator->(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator::operator->(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_leaf(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_leaf_node().


The documentation for this struct was generated from the following file:
Generated on Sun May 13 19:24:42 2007 for STX B+ Tree Template Classes by  doxygen 1.5.2