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...
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

(

x

)

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, _Value, _Compare, _Traits, _Duplicates >::clear(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find_lower(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find_upper(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert_start(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_inner(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::restore_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_inner(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_inner(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_inner_node(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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,
		b		)	((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

(

x

)

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, _Value, _Compare, _Traits, _Duplicates >::dump_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find_lower(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find_upper(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_inner(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::merge_leaves(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::restore(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_inner(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_left_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_inner(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::shift_right_leaf(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_inner_node(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::split_leaf_node(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify_node().

---