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,
			b
	)		((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().