|
STX B+ Tree Template Classes
0.9
|
|
STX B+ Tree Template Classes
0.9
|
Basic class implementing a base B+ tree data structure in memory. More...
#include <btree.h>
Classes | |
| struct | btree_pair_to_value |
| For sets the second pair_type is an empty struct, so the value_type should only be the first. More... | |
| struct | btree_pair_to_value< value_type, value_type > |
| For maps value_type is the same as the pair_type. More... | |
| class | const_iterator |
| STL-like read-only iterator object for B+ tree items. More... | |
| class | const_reverse_iterator |
| STL-like read-only reverse iterator object for B+ tree items. More... | |
| struct | dump_header |
| A header for the binary image containing the base properties of the B+ tree. More... | |
| struct | inner_node |
| Extended structure of a inner node in-memory. More... | |
| class | iterator |
| STL-like iterator object for B+ tree items. More... | |
| struct | leaf_node |
| Extended structure of a leaf node in memory. More... | |
| struct | node |
| The header structure of each node in-memory. More... | |
| struct | result_t |
| B+ tree recursive deletion has much information which is needs to be passed upward. More... | |
| class | reverse_iterator |
| STL-like mutable reverse iterator object for B+ tree items. More... | |
| struct | tree_stats |
| A small struct containing basic statistics about the B+ tree. More... | |
| class | value_compare |
| Function class to compare value_type objects. Required by the STL. More... | |
Public Types | |
| typedef _Key | key_type |
| First template parameter: The key type of the B+ tree. | |
| typedef _Data | data_type |
| Second template parameter: The data type associated with each key. | |
| typedef _Value | value_type |
| Third template parameter: Composition pair of key and data types, this is required by the STL standard. | |
| typedef _Compare | key_compare |
| Fourth template parameter: Key comparison function object. | |
| typedef _Traits | traits |
| Fifth template parameter: Traits object used to define more parameters of the B+ tree. | |
| typedef _Alloc | allocator_type |
| Seventh template parameter: STL allocator for tree nodes. | |
| typedef btree< key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set > | btree_self |
| Typedef of our own type. | |
| typedef size_t | size_type |
| Size type used to count keys. | |
| typedef std::pair< key_type, data_type > | pair_type |
| The pair of key_type and data_type, this may be different from value_type. | |
Public Member Functions | |
| btree (const allocator_type &alloc=allocator_type()) | |
| Default constructor initializing an empty B+ tree with the standard key comparison function. | |
| btree (const key_compare &kcf, const allocator_type &alloc=allocator_type()) | |
| Constructor initializing an empty B+ tree with a special key comparison object. | |
| template<class InputIterator > | |
| btree (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type()) | |
| Constructor initializing a B+ tree with the range [first,last). | |
| template<class InputIterator > | |
| btree (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type()) | |
| Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. | |
| ~btree () | |
| Frees up all used B+ tree memory pages. | |
| void | swap (btree_self &from) |
| Fast swapping of two identical B+ tree objects. | |
| key_compare | key_comp () const |
| Constant access to the key comparison object sorting the B+ tree. | |
| value_compare | value_comp () const |
| Constant access to a constructed value_type comparison object. | |
| allocator_type | get_allocator () const |
| Return the base node allocator provided during construction. | |
| void | clear () |
| Frees all key/data pairs and all nodes of the tree. | |
| iterator | begin () |
| Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree. | |
| iterator | end () |
| Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree. | |
| const_iterator | begin () const |
| Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree. | |
| const_iterator | end () const |
| Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree. | |
| reverse_iterator | rbegin () |
| Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. | |
| reverse_iterator | rend () |
| Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. | |
| const_reverse_iterator | rbegin () const |
| Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. | |
| const_reverse_iterator | rend () const |
| Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree. | |
| size_type | size () const |
| Return the number of key/data pairs in the B+ tree. | |
| bool | empty () const |
| Returns true if there is at least one key/data pair in the B+ tree. | |
| size_type | max_size () const |
| Returns the largest possible size of the B+ Tree. | |
| struct tree_stats & | get_stats () const |
| Return a const reference to the current statistics. | |
| bool | exists (const key_type &key) const |
| Non-STL function checking whether a key is in the B+ tree. | |
| iterator | find (const key_type &key) |
| Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found. | |
| const_iterator | find (const key_type &key) const |
| Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found. | |
| size_type | count (const key_type &key) const |
| Tries to locate a key in the B+ tree and returns the number of identical key entries found. | |
| iterator | lower_bound (const key_type &key) |
| Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller. | |
| const_iterator | lower_bound (const key_type &key) const |
| Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller. | |
| iterator | upper_bound (const key_type &key) |
| Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal. | |
| const_iterator | upper_bound (const key_type &key) const |
| Searches the B+ tree and returns a constant iterator to the first pair greater than key, or end() if all keys are smaller or equal. | |
| std::pair< iterator, iterator > | equal_range (const key_type &key) |
| Searches the B+ tree and returns both lower_bound() and upper_bound(). | |
| std::pair< const_iterator, const_iterator > | equal_range (const key_type &key) const |
| Searches the B+ tree and returns both lower_bound() and upper_bound(). | |
| bool | operator== (const btree_self &other) const |
| Equality relation of B+ trees of the same type. | |
| bool | operator!= (const btree_self &other) const |
| Inequality relation. Based on operator==. | |
| bool | operator< (const btree_self &other) const |
| Total ordering relation of B+ trees of the same type. | |
| bool | operator> (const btree_self &other) const |
| Greater relation. Based on operator<. | |
| bool | operator<= (const btree_self &other) const |
| Less-equal relation. Based on operator<. | |
| bool | operator>= (const btree_self &other) const |
| Greater-equal relation. Based on operator<. | |
| btree_self & | operator= (const btree_self &other) |
| *** Fast Copy: Assign Operator and Copy Constructors | |
| btree (const btree_self &other) | |
| Copy constructor. | |
| std::pair< iterator, bool > | insert (const pair_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| std::pair< iterator, bool > | insert (const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| std::pair< iterator, bool > | insert2 (const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert (iterator, const pair_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert2 (iterator, const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| template<typename InputIterator > | |
| void | insert (InputIterator first, InputIterator last) |
| Attempt to insert the range [first,last) of value_type pairs into the B+ tree. | |
| template<typename Iterator > | |
| void | bulk_load (Iterator ibegin, Iterator iend) |
| Bulk load a sorted range. | |
| bool | erase_one (const key_type &key) |
| Erases one (the first) of the key/data pairs associated with the given key. | |
| size_type | erase (const key_type &key) |
| Erases all the key/data pairs associated with the given key. | |
| void | erase (iterator iter) |
| Erase the key/data pair referenced by the iterator. | |
| void | erase (iterator, iterator) |
| Erase all key/data pairs in the range [first,last). | |
| void | print (std::ostream &os) const |
| Print out the B+ tree structure with keys onto the given ostream. | |
| void | print_leaves (std::ostream &os) const |
| Print out only the leaves via the double linked list. | |
| void | verify () const |
| Run a thorough verification of all B+ tree invariants. | |
| void | dump (std::ostream &os) const |
| Dump the contents of the B+ tree out onto an ostream as a binary image. | |
| bool | restore (std::istream &is) |
| Restore a binary image of a dumped B+ tree from an istream. | |
Static Public Attributes | |
| static const bool | allow_duplicates = _Duplicates |
| Sixth template parameter: Allow duplicate keys in the B+ tree. | |
| static const bool | used_as_set = _UsedAsSet |
| Eighth template parameter: boolean indicator whether the btree is used as a set. | |
| static const unsigned short | leafslotmax = traits::leafslots |
| Base B+ tree parameter: The number of key/data slots in each leaf. | |
| static const unsigned short | innerslotmax = traits::innerslots |
| Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf. | |
| static const unsigned short | minleafslots = (leafslotmax / 2) |
| Computed B+ tree parameter: The minimum number of key/data slots used in a leaf. | |
| static const unsigned short | mininnerslots = (innerslotmax / 2) |
| Computed B+ tree parameter: The minimum number of key slots used in an inner node. | |
| static const bool | selfverify = traits::selfverify |
| Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation. | |
| static const bool | debug = traits::debug |
| Debug parameter: Prints out lots of debug information about how the algorithms change the tree. | |
Private Types | |
| enum | result_flags_t { btree_ok = 0, btree_not_found = 1, btree_update_lastkey = 2, btree_fixmerge = 4 } |
| Result flags of recursive deletion. More... | |
| typedef btree_pair_to_value < value_type, pair_type > | pair_to_value_type |
| Using template specialization select the correct converter used by the iterators. | |
Private Member Functions | |
| bool | key_less (const key_type &a, const key_type b) const |
| True if a < b ? "constructed" from m_key_less() | |
| bool | key_lessequal (const key_type &a, const key_type b) const |
| True if a <= b ? constructed from key_less() | |
| bool | key_greater (const key_type &a, const key_type &b) const |
| True if a > b ? constructed from key_less() | |
| bool | key_greaterequal (const key_type &a, const key_type b) const |
| True if a >= b ? constructed from key_less() | |
| bool | key_equal (const key_type &a, const key_type &b) const |
| True if a == b ? constructed from key_less(). | |
| leaf_node::alloc_type | leaf_node_allocator () |
| Return an allocator for leaf_node objects. | |
| inner_node::alloc_type | inner_node_allocator () |
| Return an allocator for inner_node objects. | |
| leaf_node * | allocate_leaf () |
| Allocate and initialize a leaf node. | |
| inner_node * | allocate_inner (unsigned short level) |
| Allocate and initialize an inner node. | |
| void | free_node (node *n) |
| Correctly free either inner or leaf node, destructs all contained key and value objects. | |
| void | clear_recursive (node *n) |
| Recursively free up nodes. | |
| template<typename node_type > | |
| int | find_lower (const node_type *n, const key_type &key) const |
| Searches for the first key in the node n greater or equal to key. | |
| template<typename node_type > | |
| int | find_upper (const node_type *n, const key_type &key) const |
| Searches for the first key in the node n greater than key. | |
| struct node * | copy_recursive (const node *n) |
| Recursively copy nodes from another B+ tree object. | |
| std::pair< iterator, bool > | insert_start (const key_type &key, const data_type &value) |
| Start the insertion descent at the current root and handle root splits. | |
| std::pair< iterator, bool > | insert_descend (node *n, const key_type &key, const data_type &value, key_type *splitkey, node **splitnode) |
| Insert an item into the B+ tree. | |
| void | split_leaf_node (leaf_node *leaf, key_type *_newkey, node **_newleaf) |
| Split up a leaf node into two equally-filled sibling leaves. | |
| void | split_inner_node (inner_node *inner, key_type *_newkey, node **_newinner, unsigned int addslot) |
| Split up an inner node into two equally-filled sibling nodes. | |
| result_t | erase_one_descend (const key_type &key, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot) |
| Erase one (the first) key/data pair in the B+ tree matching key. | |
| result_t | erase_iter_descend (const iterator &iter, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot) |
| Erase one key/data pair referenced by an iterator in the B+ tree. | |
| result_t | merge_leaves (leaf_node *left, leaf_node *right, inner_node *parent) |
| Merge two leaf nodes. | |
| void | verify_node (const node *n, key_type *minkey, key_type *maxkey, tree_stats &vstats) const |
| Recursively descend down the tree and verify each node. | |
| void | verify_leaflinks () const |
| Verify the double linked list of leaves. | |
| void | dump_node (std::ostream &os, const node *n) const |
| Recursively descend down the tree and dump each node in a precise order. | |
| node * | restore_node (std::istream &is) |
| Read the dump image and construct a tree from the node order in the serialization. | |
Static Private Member Functions | |
| template<class InputIterator , class OutputIterator > | |
| static OutputIterator | data_copy (InputIterator first, InputIterator last, OutputIterator result) |
| Convenient template function for conditional copying of slotdata. | |
| template<class InputIterator , class OutputIterator > | |
| static OutputIterator | data_copy_backward (InputIterator first, InputIterator last, OutputIterator result) |
| Convenient template function for conditional copying of slotdata. | |
| static result_t | merge_inner (inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) |
| Merge two inner nodes. | |
| static result_t | shift_left_leaf (leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two leaf nodes. | |
| static void | shift_left_inner (inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two inner nodes. | |
| static void | shift_right_leaf (leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two leaf nodes. | |
| static void | shift_right_inner (inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two inner nodes. | |
| static void | print_node (std::ostream &os, const node *node, unsigned int depth=0, bool recursive=false) |
| Recursively descend down the tree and print out nodes. | |
Private Attributes | |
| node * | m_root |
| Pointer to the B+ tree's root node, either leaf or inner node. | |
| leaf_node * | m_headleaf |
| Pointer to first leaf in the double linked leaf chain. | |
| leaf_node * | m_tailleaf |
| Pointer to last leaf in the double linked leaf chain. | |
| tree_stats | m_stats |
| Other small statistics about the B+ tree. | |
| key_compare | m_key_less |
| Key comparison object. | |
| allocator_type | m_allocator |
| Memory allocator. | |
Basic class implementing a base B+ tree data structure in memory.
The base implementation of a memory B+ tree. It is based on the implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. Almost all STL-required function calls are implemented. The asymptotic time requirements of the STL are not always fulfilled in theory, however in practice this B+ tree performs better than a red-black tree by using more memory. The insertion function splits the nodes on the recursion unroll. Erase is largely based on Jannink's ideas.
This class is specialized into btree_set, btree_multiset, btree_map and btree_multimap using default template parameters and facade functions.
| typedef _Alloc stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allocator_type |
| typedef btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree_self |
| typedef _Data stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::data_type |
| typedef _Compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_compare |
| typedef _Key stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_type |
typedef btree_pair_to_value<value_type, pair_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::pair_to_value_type [private] |
| typedef std::pair<key_type, data_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::pair_type |
| typedef size_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::size_type |
| typedef _Traits stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::traits |
| typedef _Value stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::value_type |
enum stx::btree::result_flags_t [private] |
Result flags of recursive deletion.
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree | ( | const allocator_type & | alloc = allocator_type() | ) | [inline, explicit] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree | ( | const key_compare & | kcf, |
| const allocator_type & | alloc = allocator_type() |
||
| ) | [inline, explicit] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree | ( | InputIterator | first, |
| InputIterator | last, | ||
| const allocator_type & | alloc = allocator_type() |
||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last).
The range need not be sorted. To create a B+ tree from a sorted range, use bulk_load().
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree | ( | InputIterator | first, |
| InputIterator | last, | ||
| const key_compare & | kcf, | ||
| const allocator_type & | alloc = allocator_type() |
||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
The range need not be sorted. To create a B+ tree from a sorted range, use bulk_load().
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::~btree | ( | ) | [inline] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree | ( | const btree_self & | other | ) | [inline] |
| inner_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allocate_inner | ( | unsigned short | level | ) | [inline, private] |
Allocate and initialize an inner node.
Definition at line 1475 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_inner_node().
| leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allocate_leaf | ( | ) | [inline, private] |
Allocate and initialize a leaf node.
Definition at line 1466 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::begin | ( | ) | [inline] |
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Definition at line 1573 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::begin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::begin(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::begin(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::begin(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator<(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator==(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::rend().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::begin | ( | ) | const [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::bulk_load | ( | Iterator | ibegin, |
| Iterator | iend | ||
| ) | [inline] |
Bulk load a sorted range.
Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function.
Definition at line 2401 of file btree.h.
Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::bulk_load(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::bulk_load(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::bulk_load(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::bulk_load().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::clear | ( | ) | [inline] |
Frees all key/data pairs and all nodes of the tree.
Definition at line 1527 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::clear(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::clear(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::clear(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::~btree().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::clear_recursive | ( | node * | n | ) | [inline, private] |
Recursively free up nodes.
Definition at line 1545 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear_recursive().
| struct node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::copy_recursive | ( | const node * | n | ) | [inline, read, private] |
Recursively copy nodes from another B+ tree object.
Definition at line 2040 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::count | ( | const key_type & | key | ) | const [inline] |
Tries to locate a key in the B+ tree and returns the number of identical key entries found.
Definition at line 1822 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::count(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::count(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::count(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::count().
| static OutputIterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::data_copy | ( | InputIterator | first, |
| InputIterator | last, | ||
| OutputIterator | result | ||
| ) | [inline, static, private] |
Convenient template function for conditional copying of slotdata.
This should be used instead of std::copy for all slotdata manipulations.
Definition at line 1506 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().
| static OutputIterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::data_copy_backward | ( | InputIterator | first, |
| InputIterator | last, | ||
| OutputIterator | result | ||
| ) | [inline, static, private] |
Convenient template function for conditional copying of slotdata.
This should be used instead of std::copy for all slotdata manipulations.
Definition at line 1516 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump | ( | std::ostream & | os | ) | const [inline] |
Dump the contents of the B+ tree out onto an ostream as a binary image.
The image contains memory pointers which will be fixed when the image is restored. For this to work your key_type and data_type must be integral types and contain no pointers or references.
Definition at line 3843 of file btree.h.
Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::dump(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::dump(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::dump(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::dump().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_node | ( | std::ostream & | os, |
| const node * | n | ||
| ) | const [inline, private] |
Recursively descend down the tree and dump each node in a precise order.
Definition at line 3897 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::dump(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::dump_node().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::empty | ( | ) | const [inline] |
Returns true if there is at least one key/data pair in the B+ tree.
Definition at line 1734 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::empty(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::empty(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::empty(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::empty().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::end | ( | ) | [inline] |
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree.
Definition at line 1580 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::end(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::end(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::end(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::end(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::lower_bound(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator<(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator==(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::rbegin(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::upper_bound().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::end | ( | ) | const [inline] |
| std::pair<iterator, iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::equal_range | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 1940 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::equal_range(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::equal_range().
| std::pair<const_iterator, const_iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::equal_range | ( | const key_type & | key | ) | const [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase | ( | const key_type & | key | ) | [inline] |
Erases all the key/data pairs associated with the given key.
This is implemented using erase_one().
Definition at line 2619 of file btree.h.
Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::erase(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase | ( | iterator | iter | ) | [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase | ( | iterator | , |
| iterator | |||
| ) | [inline] |
| result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_iter_descend | ( | const iterator & | iter, |
| node * | curr, | ||
| node * | left, | ||
| node * | right, | ||
| inner_node * | leftparent, | ||
| inner_node * | rightparent, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, private] |
Erase one key/data pair referenced by an iterator in the B+ tree.
Descends down the tree in search of an iterator. During the descent the parent, left and right siblings and their parents are computed and passed down. The difficulty is that the iterator contains only a pointer to a leaf_node, which means that this function must do a recursive depth first search for that leaf node in the subtree containing all pairs of the same key. This subtree can be very large, even the whole tree, though in practice it would not make sense to have so many duplicate keys.
Once the referenced key/data pair is found, it is removed from the leaf and the same underflow cases are handled as in erase_one_descend.
Definition at line 2962 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_one | ( | const key_type & | key | ) | [inline] |
Erases one (the first) of the key/data pairs associated with the given key.
Definition at line 2596 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::erase_one(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase_one(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one().
| result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_one_descend | ( | const key_type & | key, |
| node * | curr, | ||
| node * | left, | ||
| node * | right, | ||
| inner_node * | leftparent, | ||
| inner_node * | rightparent, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, private] |
Erase one (the first) key/data pair in the B+ tree matching key.
Descends down the tree in search of key. During the descent the parent, left and right siblings and their parents are computed and passed down. Once the key/data pair is found, it is removed from the leaf. If the leaf underflows 6 different cases are handled. These cases resolve the underflow by shifting key/data pairs from adjacent sibling nodes, merging two sibling nodes or trimming the tree.
Definition at line 2673 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::exists | ( | const key_type & | key | ) | const [inline] |
Non-STL function checking whether a key is in the B+ tree.
The same as (find(k) != end()) or (count() != 0).
Definition at line 1757 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::exists(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::exists(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::exists(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::exists(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find | ( | const key_type & | key | ) | [inline] |
Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
If unsuccessful it returns end().
Definition at line 1778 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::find(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::find(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::find(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::find().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find | ( | const key_type & | key | ) | const [inline] |
| int stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find_lower | ( | const node_type * | n, |
| const key_type & | key | ||
| ) | const [inline, private] |
Searches for the first key in the node n greater or equal to key.
Uses binary search with an optional linear self-verification. This is a template function, because the slotkey array is located at different places in leaf_node and inner_node.
Definition at line 1635 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::count(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::exists(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::lower_bound().
| int stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find_upper | ( | const node_type * | n, |
| const key_type & | key | ||
| ) | const [inline, private] |
Searches for the first key in the node n greater than key.
Uses binary search with an optional linear self-verification. This is a template function, because the slotkey array is located at different places in leaf_node and inner_node.
Definition at line 1682 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::upper_bound().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::free_node | ( | node * | n | ) | [inline, private] |
Correctly free either inner or leaf node, destructs all contained key and value objects.
Definition at line 1485 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| allocator_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::get_allocator | ( | ) | const [inline] |
Return the base node allocator provided during construction.
Definition at line 1445 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::get_allocator(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=().
| struct tree_stats& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::get_stats | ( | ) | const [inline, read] |
Return a const reference to the current statistics.
Definition at line 1747 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_stats(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::get_stats().
| inner_node::alloc_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node_allocator | ( | ) | [inline, private] |
Return an allocator for inner_node objects.
Definition at line 1460 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_inner(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::free_node().
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert | ( | const pair_type & | x | ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
If the tree does not allow duplicate keys, then the insert may fail if it is already present.
Definition at line 2088 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert().
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert | ( | const key_type & | key, |
| const data_type & | data | ||
| ) | [inline] |
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert | ( | iterator | , |
| const pair_type & | x | ||
| ) | [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert | ( | InputIterator | first, |
| InputIterator | last | ||
| ) | [inline] |
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2 | ( | const key_type & | key, |
| const data_type & | data | ||
| ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
This function is the same as the other insert, however if key_type == data_type then the non-template function cannot be called. If the tree does not allow duplicate keys, then the insert may fail if it is already present.
Definition at line 2106 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert2().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2 | ( | iterator | , |
| const key_type & | key, | ||
| const data_type & | data | ||
| ) | [inline] |
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert_descend | ( | node * | n, |
| const key_type & | key, | ||
| const data_type & | value, | ||
| key_type * | splitkey, | ||
| node ** | splitnode | ||
| ) | [inline, private] |
Insert an item into the B+ tree.
Descend down the nodes to a leaf, insert the key/data pair in a free slot. If the node overflows, then it must be split and the new split node inserted into the parent. Unroll / this splitting up to the root.
Definition at line 2190 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start().
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert_start | ( | const key_type & | key, |
| const data_type & | value | ||
| ) | [inline, private] |
Start the insertion descent at the current root and handle root splits.
Returns true if the item was inserted
Definition at line 2144 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert2().
| key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_comp | ( | ) | const [inline] |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 1395 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::key_comp(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_equal | ( | const key_type & | a, |
| const key_type & | b | ||
| ) | const [inline, private] |
True if a == b ? constructed from key_less().
This requires the < relation to be a total order, otherwise the B+ tree cannot be sorted.
Definition at line 1436 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::count(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::exists(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_greater | ( | const key_type & | a, |
| const key_type & | b | ||
| ) | const [inline, private] |
True if a > b ? constructed from key_less()
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_greaterequal | ( | const key_type & | a, |
| const key_type | b | ||
| ) | const [inline, private] |
True if a >= b ? constructed from key_less()
Definition at line 1429 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_less | ( | const key_type & | a, |
| const key_type | b | ||
| ) | const [inline, private] |
True if a < b ? "constructed" from m_key_less()
Definition at line 1411 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_lower(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_upper().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_lessequal | ( | const key_type & | a, |
| const key_type | b | ||
| ) | const [inline, private] |
True if a <= b ? constructed from key_less()
Definition at line 1417 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_lower(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_upper(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_leaflinks(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().
| leaf_node::alloc_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node_allocator | ( | ) | [inline, private] |
Return an allocator for leaf_node objects.
Definition at line 1454 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_leaf(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::free_node().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::lower_bound | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller.
Definition at line 1855 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::equal_range(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::lower_bound(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::lower_bound().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::lower_bound | ( | const key_type & | key | ) | const [inline] |
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::max_size | ( | ) | const [inline] |
Returns the largest possible size of the B+ Tree.
This is just a function required by the STL standard, the B+ Tree can hold more items.
Definition at line 1741 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::max_size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::max_size(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::max_size(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::max_size().
| static result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::merge_inner | ( | inner_node * | left, |
| inner_node * | right, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, static, private] |
Merge two inner nodes.
The function moves all key/childid pairs from right to left and sets right's slotuse to zero. The right slot is then removed by the calling parent node.
Definition at line 3293 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::merge_leaves | ( | leaf_node * | left, |
| leaf_node * | right, | ||
| inner_node * | parent | ||
| ) | [inline, private] |
Merge two leaf nodes.
The function moves all key/data pairs from right to left and sets right's slotuse to zero. The right slot is then removed by the calling parent node.
Definition at line 3262 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator!= | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator< | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator<= | ( | const btree_self & | other | ) | const [inline] |
| btree_self& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator= | ( | const btree_self & | other | ) | [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator== | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator> | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator>= | ( | const btree_self & | other | ) | const [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print | ( | std::ostream & | os | ) | const [inline] |
Print out the B+ tree structure with keys onto the given ostream.
This function requires that the header is compiled with BTREE_DEBUG and that key_type is printable via std::ostream.
Definition at line 3556 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::print(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::print(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print_leaves | ( | std::ostream & | os | ) | const [inline] |
Print out only the leaves via the double linked list.
Definition at line 3564 of file btree.h.
Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::print_leaves(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print_leaves(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print_leaves(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::print_leaves().
| static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print_node | ( | std::ostream & | os, |
| const node * | node, | ||
| unsigned int | depth = 0, |
||
| bool | recursive = false |
||
| ) | [inline, static, private] |
Recursively descend down the tree and print out nodes.
Definition at line 3581 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print_node().
| reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rbegin | ( | ) | [inline] |
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree.
Uses STL magic.
Definition at line 1601 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rbegin(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::rbegin().
| const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rbegin | ( | ) | const [inline] |
| reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rend | ( | ) | [inline] |
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree.
Uses STL magic.
Definition at line 1608 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::rend(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rend(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rend(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::rend().
| const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rend | ( | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::restore | ( | std::istream & | is | ) | [inline] |
Restore a binary image of a dumped B+ tree from an istream.
The B+ tree pointers are fixed using the dump order. For dump and restore to work your key_type and data_type must be integral types and contain no pointers or references. Returns true if the restore was successful.
Definition at line 3860 of file btree.h.
Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::restore(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::restore(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::restore(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::restore().
| node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::restore_node | ( | std::istream & | is | ) | [inline, private] |
Read the dump image and construct a tree from the node order in the serialization.
Definition at line 3924 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node().
| static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_left_inner | ( | inner_node * | left, |
| inner_node * | right, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, static, private] |
Balance two inner nodes.
The function moves key/data pairs from right to left so that both nodes are equally filled. The parent node is updated if possible.
Definition at line 3385 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| static result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_left_leaf | ( | leaf_node * | left, |
| leaf_node * | right, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, static, private] |
Balance two leaf nodes.
The function moves key/data pairs from right to left so that both nodes are equally filled. The parent node is updated if possible.
Definition at line 3337 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_right_inner | ( | inner_node * | left, |
| inner_node * | right, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, static, private] |
Balance two inner nodes.
The function moves key/data pairs from left to right so that both nodes are equally filled. The parent node is updated if possible.
Definition at line 3497 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_right_leaf | ( | leaf_node * | left, |
| leaf_node * | right, | ||
| inner_node * | parent, | ||
| unsigned int | parentslot | ||
| ) | [inline, static, private] |
Balance two leaf nodes.
The function moves key/data pairs from left to right so that both nodes are equally filled. The parent node is updated if possible.
Definition at line 3443 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::size | ( | ) | const [inline] |
Return the number of key/data pairs in the B+ tree.
Definition at line 1728 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::dump(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::empty(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator==(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::size(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::size(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::size(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_leaflinks().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::split_inner_node | ( | inner_node * | inner, |
| key_type * | _newkey, | ||
| node ** | _newinner, | ||
| unsigned int | addslot | ||
| ) | [inline, private] |
Split up an inner node into two equally-filled sibling nodes.
Returns the new nodes and it's insertion key in the two parameters. Requires the slot of the item will be inserted, so the nodes will be the same size after the insert.
Definition at line 2362 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::split_leaf_node | ( | leaf_node * | leaf, |
| key_type * | _newkey, | ||
| node ** | _newleaf | ||
| ) | [inline, private] |
Split up a leaf node into two equally-filled sibling leaves.
Returns the new nodes and it's insertion key in the two parameters.
Definition at line 2324 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::swap | ( | btree_self & | from | ) | [inline] |
Fast swapping of two identical B+ tree objects.
Definition at line 1357 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::upper_bound | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal.
Definition at line 1898 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::equal_range(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::upper_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::upper_bound(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::upper_bound(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::upper_bound().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::upper_bound | ( | const key_type & | key | ) | const [inline] |
| value_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::value_comp | ( | ) | const [inline] |
Constant access to a constructed value_type comparison object.
Required by the STL
Definition at line 1402 of file btree.h.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::value_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::value_comp(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::value_comp(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::value_comp().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify | ( | ) | const [inline] |
Run a thorough verification of all B+ tree invariants.
The program aborts via assert() if something is wrong.
Definition at line 3630 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::verify(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::verify(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::verify(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::verify().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify_leaflinks | ( | ) | const [inline, private] |
Verify the double linked list of leaves.
Definition at line 3735 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify_node | ( | const node * | n, |
| key_type * | minkey, | ||
| key_type * | maxkey, | ||
| tree_stats & | vstats | ||
| ) | const [inline, private] |
Recursively descend down the tree and verify each node.
Definition at line 3650 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allow_duplicates = _Duplicates [static] |
Sixth template parameter: Allow duplicate keys in the B+ tree.
Used to implement multiset and multimap.
Definition at line 191 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend().
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::debug = traits::debug [static] |
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Requires the header file to be compiled with BTREE_DEBUG and the key type must be std::ostream printable.
Definition at line 248 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore().
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::innerslotmax = traits::innerslots [static] |
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf.
Definition at line 229 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_header::fill(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node::isfull(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_inner(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_inner().
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leafslotmax = traits::leafslots [static] |
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition at line 225 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_header::fill(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfull(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_leaf(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf().
allocator_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_allocator [private] |
Memory allocator.
Definition at line 1306 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::get_allocator(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::inner_node_allocator(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::leaf_node_allocator(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap().
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_headleaf [private] |
Pointer to first leaf in the double linked leaf chain.
Definition at line 1293 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::begin(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_leaflinks().
key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_key_less [private] |
Key comparison object.
More comparison functions are generated from this < relation.
Definition at line 1303 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::key_comp(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::key_equal(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::key_greater(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::key_greaterequal(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::key_less(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::key_lessequal(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::value_comp().
node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_root [private] |
Pointer to the B+ tree's root node, either leaf or inner node.
Definition at line 1290 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::count(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::dump(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::exists(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::lower_bound(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::upper_bound(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().
tree_stats stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_stats [private] |
Other small statistics about the B+ tree.
Definition at line 1299 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::free_node(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::get_stats(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::size(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify().
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_tailleaf [private] |
Pointer to last leaf in the double linked leaf chain.
Definition at line 1296 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::end(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_leaflinks().
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::mininnerslots = (innerslotmax / 2) [static] |
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
If fewer slots are used, the inner node will be merged or slots shifted from it's siblings.
Definition at line 239 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node::isfew(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node::isunderflow().
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::minleafslots = (leafslotmax / 2) [static] |
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
If fewer slots are used, the leaf will be merged or slots shifted from it's siblings.
Definition at line 234 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfew(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isunderflow().
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::selfverify = traits::selfverify [static] |
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
Definition at line 243 of file btree.h.
Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_lower(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_upper(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_inner(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf().
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::used_as_set = _UsedAsSet [static] |
Eighth template parameter: boolean indicator whether the btree is used as a set.
In this case all operations on the data arrays are omitted. This flag is kind of hacky, but required because sizeof(empty_struct) = 1 due to the C standard. Without the flag, lots of superfluous copying would occur.
Definition at line 201 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::data(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::data_copy(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::data_copy_backward(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot().
1.7.6.1
