stx/btree.h File Reference

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

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

Go to the source code of this file.

Namespaces

namespace  stx

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 >
 Basic class implementing a base B+ tree data structure in memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node
 The header structure of each node in-memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::inner_node
 Extended structure of a inner node in-memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node
 Extended structure of a leaf node in memory. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree_pair_to_value< value_type, pair_type >
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree_pair_to_value< value_type, value_type >
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator
 STL-like iterator object for B+ tree items. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator
 STL-like read-only iterator object for B+ tree items. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator
 STL-like mutable reverse iterator object for B+ tree items. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator
 STL-like read-only reverse iterator object for B+ tree items. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats
 A small struct containing basic statistics about the B+ tree. More...
class  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_compare
 Function class to compare value_type objects. Required by the STL. More...
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::result_t
struct  stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::dump_header

Defines

#define BTREE_PRINT(x)   do { if (debug) (std::cout << x); } 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 (  )     do { assert(x); } while(0)

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

Definition at line 46 of file btree.h.

Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::clear(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::data(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one_descend(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_lower(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_upper(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_descend(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_start(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::key(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_inner(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::operator*(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::operator*(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::operator->(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::operator->(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore_node(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_inner(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_leaf(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_inner(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_leaf(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_inner_node(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::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 65 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 59 of file btree.h.

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

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

Definition at line 43 of file btree.h.

Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::dump_node(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one_descend(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_lower(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_upper(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_descend(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_inner(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_leaves(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_inner(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_leaf(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_inner(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_leaf(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_inner_node(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_leaf_node(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::verify_node().


Generated on Sun Sep 7 17:32:39 2008 for STX B+ Tree Template Classes by  doxygen 1.5.6