STX B+ Tree Template Classes  0.9
Classes | Namespaces | Defines
stx/btree.h File Reference

Contains the main B+ tree implementation template class btree. More...

#include <algorithm>
#include <functional>
#include <istream>
#include <ostream>
#include <memory>
#include <cstddef>
#include <assert.h>
#include <iostream>

Go to the source code of this file.

Classes

struct  stx::btree_default_set_traits< _Key >
 Generates default traits for a B+ tree used as a set. More...
struct  stx::btree_default_map_traits< _Key, _Data >
 Generates default traits for a B+ tree used as a map. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >
 Basic class implementing a base B+ tree data structure in memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node
 The header structure of each node in-memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node
 Extended structure of a inner node in-memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node
 Extended structure of a leaf node in memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree_pair_to_value< value_type, pair_type >
 For sets the second pair_type is an empty struct, so the value_type should only be the first. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree_pair_to_value< value_type, value_type >
 For maps value_type is the same as the pair_type. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator
 STL-like iterator object for B+ tree items. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator
 STL-like read-only iterator object for B+ tree items. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator
 STL-like mutable reverse iterator object for B+ tree items. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator
 STL-like read-only reverse iterator object for B+ tree items. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::tree_stats
 A small struct containing basic statistics about the B+ tree. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::value_compare
 Function class to compare value_type objects. Required by the STL. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::result_t
 B+ tree recursive deletion has much information which is needs to be passed upward. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_header
 A header for the binary image containing the base properties of the B+ tree. More...

Namespaces

namespace  stx
 

STX - Some Template Extensions namespace.


Defines

#define BTREE_PRINT(x)   do { if (debug) (std::cout << x << std::endl); } while(0)
 Print out debug information to std::cout if BTREE_DEBUG is defined.
#define BTREE_ASSERT(x)   do { assert(x); } while(0)
 Assertion only if BTREE_DEBUG is defined. This is not used in verify().
#define BTREE_MAX(a, b)   ((a) < (b) ? (b) : (a))
 The maximum of a and b. Used in some compile-time formulas.
#define BTREE_FRIENDS   friend class btree_friend;
 The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.

Detailed Description

Contains the main B+ tree implementation template class btree.

Definition in file btree.h.


Define Documentation

#define BTREE_ASSERT (   x)    do { assert(x); } while(0)

Assertion only if BTREE_DEBUG is defined. This is not used in verify().

Definition at line 58 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, _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 >::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 >::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_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::key(), 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 >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::operator*(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::operator*(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::operator->(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::operator->(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot(), 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_left_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_inner_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().

#define BTREE_FRIENDS   friend class btree_friend;

The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.

This was added for wxBTreeDemo to be able to draw the tree.

Definition at line 77 of file btree.h.

#define BTREE_MAX (   a,
 
)    ((a) < (b) ? (b) : (a))

The maximum of a and b. Used in some compile-time formulas.

Definition at line 71 of file btree.h.

#define BTREE_PRINT (   x)    do { if (debug) (std::cout << x << std::endl); } while(0)

Print out debug information to std::cout if BTREE_DEBUG is defined.

Definition at line 55 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 >::dump_node(), 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 >::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_descend(), 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 >::merge_leaves(), 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_left_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_inner_node(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines