// $Id: btree.h 113 2008-09-07 15:25:51Z tb $
/** \file btree.h
* Contains the main B+ tree implementation template class btree.
*/
/*
* STX B+ Tree Template Classes v0.8.3
* Copyright (C) 2008 Timo Bingmann
*
* This library is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by the
* Free Software Foundation; either version 2.1 of the License, or (at your
* option) any later version.
*
* This library is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
* for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef _STX_BTREE_H_
#define _STX_BTREE_H_
// *** Required Headers from the STL
#include <algorithm>
#include <functional>
#include <istream>
#include <ostream>
#include <assert.h>
// *** Debugging Macros
#ifdef BTREE_DEBUG
#include <iostream>
/// Print out debug information to std::cout if BTREE_DEBUG is defined.
#define BTREE_PRINT(x) do { if (debug) (std::cout << x); } while(0)
/// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
#define BTREE_ASSERT(x) do { assert(x); } while(0)
#else
/// Print out debug information to std::cout if BTREE_DEBUG is defined.
#define BTREE_PRINT(x) do { } while(0)
/// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
#define BTREE_ASSERT(x) do { } while(0)
#endif
/// The maximum of a and b. Used in some compile-time formulas.
#define BTREE_MAX(a,b) ((a) < (b) ? (b) : (a))
#ifndef BTREE_FRIENDS
/// 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.
#define BTREE_FRIENDS friend class btree_friend;
#endif
/// STX - Some Template Extensions namespace
namespace stx {
/** Generates default traits for a B+ tree used as a set. It estimates leaf and
* inner node sizes by assuming a cache line size of 256 bytes. */
template <typename _Key>
struct btree_default_set_traits
{
/// If true, the tree will self verify it's invariants after each insert()
/// or erase(). The header must have been compiled with BTREE_DEBUG defined.
static const bool selfverify = false;
/// If true, the tree will print out debug information and a tree dump
/// during insert() or erase() operation. The header must have been
/// compiled with BTREE_DEBUG defined and key_type must be std::ostream
/// printable.
static const bool debug = false;
/// Number of slots in each leaf of the tree. Estimated so that each node
/// has a size of about 256 bytes.
static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );
/// Number of slots in each inner node of the tree. Estimated so that each node
/// has a size of about 256 bytes.
static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
};
/** Generates default traits for a B+ tree used as a map. It estimates leaf and
* inner node sizes by assuming a cache line size of 256 bytes. */
template <typename _Key, typename _Data>
struct btree_default_map_traits
{
/// If true, the tree will self verify it's invariants after each insert()
/// or erase(). The header must have been compiled with BTREE_DEBUG defined.
static const bool selfverify = false;
/// If true, the tree will print out debug information and a tree dump
/// during insert() or erase() operation. The header must have been
/// compiled with BTREE_DEBUG defined and key_type must be std::ostream
/// printable.
static const bool debug = false;
/// Number of slots in each leaf of the tree. Estimated so that each node
/// has a size of about 256 bytes.
static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );
/// Number of slots in each inner node of the tree. Estimated so that each node
/// has a size of about 256 bytes.
static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
};
/** @brief 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.
*/
template <typename _Key, typename _Data,
typename _Value = std::pair<_Key, _Data>,
typename _Compare = std::less<_Key>,
typename _Traits = btree_default_map_traits<_Key, _Data>,
bool _Duplicates = false>
class btree
{
public:
// *** Template Parameter Types
/// First template parameter: The key type of the B+ tree. This is stored
/// in inner nodes and leaves
typedef _Key key_type;
/// Second template parameter: The data type associated with each
/// key. Stored in the B+ tree's leaves
typedef _Data data_type;
/// Third template parameter: Composition pair of key and data types, this
/// is required by the STL standard. The B+ tree does not store key and
/// data together. If value_type == key_type then the B+ tree implements a
/// set.
typedef _Value value_type;
/// Fourth template parameter: Key comparison function object
typedef _Compare key_compare;
/// Fifth template parameter: Traits object used to define more parameters
/// of the B+ tree
typedef _Traits traits;
/// Sixth template parameter: Allow duplicate keys in the B+ tree. Used to
/// implement multiset and multimap.
static const bool allow_duplicates = _Duplicates;
// 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.
BTREE_FRIENDS
public:
// *** Constructed Types
/// Typedef of our own type
typedef btree<key_type, data_type, value_type,
key_compare, traits, allow_duplicates> btree_self;
/// Size type used to count keys
typedef size_t size_type;
/// The pair of key_type and data_type, this may be different from value_type.
typedef std::pair<key_type, data_type> pair_type;
public:
// *** Static Constant Options and Values of the B+ Tree
/// Base B+ tree parameter: The number of key/data slots in each leaf
static const unsigned short leafslotmax = traits::leafslots;
/// 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 innerslotmax = traits::innerslots;
/// 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.
static const unsigned short minleafslots = (leafslotmax / 2);
/// 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.
static const unsigned short mininnerslots = (innerslotmax / 2);
/// Debug parameter: Enables expensive and thorough checking of the B+ tree
/// invariants after each insert/erase operation.
static const bool selfverify = traits::selfverify;
/// 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.
static const bool debug = traits::debug;
private:
// *** Node Classes for In-Memory Nodes
/// The header structure of each node in-memory. This structure is extended
/// by inner_node or leaf_node.
struct node
{
/// Level in the b-tree, if level == 0 -> leaf node
unsigned short level;
/// Number of key slotuse use, so number of valid children or data
/// pointers
unsigned short slotuse;
/// Delayed initialisation of constructed node
inline void initialize(const unsigned short l)
{
level = l;
slotuse = 0;
}
/// True if this is a leaf node
inline bool isleafnode() const
{
return (level == 0);
}
};
/// Extended structure of a inner node in-memory. Contains only keys and no
/// data items.
struct inner_node : public node
{
/// Keys of children or data pointers
key_type slotkey[innerslotmax];
/// Pointers to children
node* childid[innerslotmax+1];
/// Set variables to initial values
inline void initialize(const unsigned short l)
{
node::initialize(l);
}
/// True if the node's slots are full
inline bool isfull() const
{
return (node::slotuse == innerslotmax);
}
/// True if few used entries, less than half full
inline bool isfew() const
{
return (node::slotuse <= mininnerslots);
}
/// True if node has too few entries
inline bool isunderflow() const
{
return (node::slotuse < mininnerslots);
}
};
/// Extended structure of a leaf node in memory. Contains pairs of keys and
/// data items. Key and data slots are kept in separate arrays, because the
/// key array is traversed very often compared to accessing the data items.
struct leaf_node : public node
{
/// Double linked list pointers to traverse the leaves
leaf_node *prevleaf;
/// Double linked list pointers to traverse the leaves
leaf_node *nextleaf;
/// Keys of children or data pointers
key_type slotkey[leafslotmax];
/// Array of data
data_type slotdata[leafslotmax];
/// Set variables to initial values
inline void initialize()
{
node::initialize(0);
prevleaf = nextleaf = NULL;
}
/// True if the node's slots are full
inline bool isfull() const
{
return (node::slotuse == leafslotmax);
}
/// True if few used entries, less than half full
inline bool isfew() const
{
return (node::slotuse <= minleafslots);
}
/// True if node has too few entries
inline bool isunderflow() const
{
return (node::slotuse < minleafslots);
}
};
private:
// *** Template Magic to Convert a pair or key/data types to a value_type
/// \internal For sets the second pair_type is an empty struct, so the
/// value_type should only be the first.
template <typename value_type, typename pair_type>
struct btree_pair_to_value
{
/// Convert a fake pair type to just the first component
inline value_type operator()(pair_type& p) const {
return p.first;
}
/// Convert a fake pair type to just the first component
inline value_type operator()(const pair_type& p) const {
return p.first;
}
};
/// \internal For maps value_type is the same as the pair_type
template <typename value_type>
struct btree_pair_to_value<value_type, value_type>
{
/// Identity "convert" a real pair type to just the first component
inline value_type operator()(pair_type& p) const {
return p;
}
/// Identity "convert" a real pair type to just the first component
inline value_type operator()(const pair_type& p) const {
return p;
}
};
/// Using template specialization select the correct converter used by the
/// iterators
typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;
public:
// *** Iterators and Reverse Iterators
class iterator;
class const_iterator;
class reverse_iterator;
class const_reverse_iterator;
/// STL-like iterator object for B+ tree items. The iterator points to a
/// specific slot number in a leaf.
class iterator
{
public:
// *** Types
/// The key type of the btree. Returned by key().
typedef typename btree::key_type key_type;
/// The data type of the btree. Returned by data().
typedef typename btree::data_type data_type;
/// The value type of the btree. Returned by operator*().
typedef typename btree::value_type value_type;
/// The pair type of the btree.
typedef typename btree::pair_type pair_type;
/// Reference to the value_type. STL required.
typedef value_type& reference;
/// Pointer to the value_type. STL required.
typedef value_type* pointer;
/// STL-magic iterator category
typedef std::bidirectional_iterator_tag iterator_category;
/// STL-magic
typedef ptrdiff_t difference_type;
/// Our own type
typedef iterator self;
private:
// *** Members
/// The currently referenced leaf node of the tree
typename btree::leaf_node* currnode;
/// Current key/data slot referenced
unsigned short currslot;
/// Friendly to the const_iterator, so it may access the two data items directly.
friend class const_iterator;
/// Also friendly to the reverse_iterator, so it may access the two data items directly.
friend class reverse_iterator;
/// Also friendly to the const_reverse_iterator, so it may access the two data items directly.
friend class const_reverse_iterator;
/// Evil! A temporary value_type to STL-correctly deliver operator* and
/// operator->
mutable value_type temp_value;
// 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.
BTREE_FRIENDS
public:
// *** Methods
/// Default-Constructor of a mutable iterator
inline iterator()
: currnode(NULL), currslot(0)
{ }
/// Initializing-Constructor of a mutable iterator
inline iterator(typename btree::leaf_node *l, unsigned short s)
: currnode(l), currslot(s)
{ }
/// Copy-constructor from a reverse iterator
inline iterator(const reverse_iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Dereference the iterator, this is not a value_type& because key and
/// value are not stored together
inline reference operator*() const
{
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
currnode->slotdata[currslot]) );
return temp_value;
}
/// Dereference the iterator. Do not use this if possible, use key()
/// and data() instead. The B+ tree does not stored key and data
/// together.
inline pointer operator->() const
{
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
currnode->slotdata[currslot]) );
return &temp_value;
}
/// Key of the current slot
inline const key_type& key() const
{
return currnode->slotkey[currslot];
}
/// Writable reference to the current data object
inline data_type& data() const
{
return currnode->slotdata[currslot];
}
/// Prefix++ advance the iterator to the next slot
inline self& operator++()
{
if (currslot + 1 < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 0;
}
else {
// this is end()
currslot = currnode->slotuse;
}
return *this;
}
/// Postfix++ advance the iterator to the next slot
inline self operator++(int)
{
self tmp = *this; // copy ourselves
if (currslot + 1 < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 0;
}
else {
// this is end()
currslot = currnode->slotuse;
}
return tmp;
}
/// Prefix-- backstep the iterator to the last slot
inline self& operator--()
{
if (currslot > 0) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse - 1;
}
else {
// this is begin()
currslot = 0;
}
return *this;
}
/// Postfix-- backstep the iterator to the last slot
inline self operator--(int)
{
self tmp = *this; // copy ourselves
if (currslot > 0) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse - 1;
}
else {
// this is begin()
currslot = 0;
}
return tmp;
}
/// Equality of iterators
inline bool operator==(const self& x) const
{
return (x.currnode == currnode) && (x.currslot == currslot);
}
/// Inequality of iterators
inline bool operator!=(const self& x) const
{
return (x.currnode != currnode) || (x.currslot != currslot);
}
};
/// STL-like read-only iterator object for B+ tree items. The iterator
/// points to a specific slot number in a leaf.
class const_iterator
{
public:
// *** Types
/// The key type of the btree. Returned by key().
typedef typename btree::key_type key_type;
/// The data type of the btree. Returned by data().
typedef typename btree::data_type data_type;
/// The value type of the btree. Returned by operator*().
typedef typename btree::value_type value_type;
/// The pair type of the btree.
typedef typename btree::pair_type pair_type;
/// Reference to the value_type. STL required.
typedef const value_type& reference;
/// Pointer to the value_type. STL required.
typedef const value_type* pointer;
/// STL-magic iterator category
typedef std::bidirectional_iterator_tag iterator_category;
/// STL-magic
typedef ptrdiff_t difference_type;
/// Our own type
typedef const_iterator self;
private:
// *** Members
/// The currently referenced leaf node of the tree
const typename btree::leaf_node* currnode;
/// Current key/data slot referenced
unsigned short currslot;
/// Friendly to the reverse_const_iterator, so it may access the two data items directly
friend class const_reverse_iterator;
/// Evil! A temporary value_type to STL-correctly deliver operator* and
/// operator->
mutable value_type temp_value;
// 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.
BTREE_FRIENDS
public:
// *** Methods
/// Default-Constructor of a const iterator
inline const_iterator()
: currnode(NULL), currslot(0)
{ }
/// Initializing-Constructor of a const iterator
inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
: currnode(l), currslot(s)
{ }
/// Copy-constructor from a mutable iterator
inline const_iterator(const iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Copy-constructor from a mutable reverse iterator
inline const_iterator(const reverse_iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Copy-constructor from a const reverse iterator
inline const_iterator(const const_reverse_iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Dereference the iterator. Do not use this if possible, use key()
/// and data() instead. The B+ tree does not stored key and data
/// together.
inline reference operator*() const
{
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
currnode->slotdata[currslot]) );
return temp_value;
}
/// Dereference the iterator. Do not use this if possible, use key()
/// and data() instead. The B+ tree does not stored key and data
/// together.
inline pointer operator->() const
{
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
currnode->slotdata[currslot]) );
return &temp_value;
}
/// Key of the current slot
inline const key_type& key() const
{
return currnode->slotkey[currslot];
}
/// Read-only reference to the current data object
inline const data_type& data() const
{
return currnode->slotdata[currslot];
}
/// Prefix++ advance the iterator to the next slot
inline self& operator++()
{
if (currslot + 1 < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 0;
}
else {
// this is end()
currslot = currnode->slotuse;
}
return *this;
}
/// Postfix++ advance the iterator to the next slot
inline self operator++(int)
{
self tmp = *this; // copy ourselves
if (currslot + 1 < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 0;
}
else {
// this is end()
currslot = currnode->slotuse;
}
return tmp;
}
/// Prefix-- backstep the iterator to the last slot
inline self& operator--()
{
if (currslot > 0) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse - 1;
}
else {
// this is begin()
currslot = 0;
}
return *this;
}
/// Postfix-- backstep the iterator to the last slot
inline self operator--(int)
{
self tmp = *this; // copy ourselves
if (currslot > 0) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse - 1;
}
else {
// this is begin()
currslot = 0;
}
return tmp;
}
/// Equality of iterators
inline bool operator==(const self& x) const
{
return (x.currnode == currnode) && (x.currslot == currslot);
}
/// Inequality of iterators
inline bool operator!=(const self& x) const
{
return (x.currnode != currnode) || (x.currslot != currslot);
}
};
/// STL-like mutable reverse iterator object for B+ tree items. The
/// iterator points to a specific slot number in a leaf.
class reverse_iterator
{
public:
// *** Types
/// The key type of the btree. Returned by key().
typedef typename btree::key_type key_type;
/// The data type of the btree. Returned by data().
typedef typename btree::data_type data_type;
/// The value type of the btree. Returned by operator*().
typedef typename btree::value_type value_type;
/// The pair type of the btree.
typedef typename btree::pair_type pair_type;
/// Reference to the value_type. STL required.
typedef value_type& reference;
/// Pointer to the value_type. STL required.
typedef value_type* pointer;
/// STL-magic iterator category
typedef std::bidirectional_iterator_tag iterator_category;
/// STL-magic
typedef ptrdiff_t difference_type;
/// Our own type
typedef reverse_iterator self;
private:
// *** Members
/// The currently referenced leaf node of the tree
typename btree::leaf_node* currnode;
/// One slot past the current key/data slot referenced.
unsigned short currslot;
/// Friendly to the const_iterator, so it may access the two data items directly
friend class iterator;
/// Also friendly to the const_iterator, so it may access the two data items directly
friend class const_iterator;
/// Also friendly to the const_iterator, so it may access the two data items directly
friend class const_reverse_iterator;
/// Evil! A temporary value_type to STL-correctly deliver operator* and
/// operator->
mutable value_type temp_value;
// 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.
BTREE_FRIENDS
public:
// *** Methods
/// Default-Constructor of a reverse iterator
inline reverse_iterator()
: currnode(NULL), currslot(0)
{ }
/// Initializing-Constructor of a mutable reverse iterator
inline reverse_iterator(typename btree::leaf_node *l, unsigned short s)
: currnode(l), currslot(s)
{ }
/// Copy-constructor from a mutable iterator
inline reverse_iterator(const iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Dereference the iterator, this is not a value_type& because key and
/// value are not stored together
inline reference operator*() const
{
BTREE_ASSERT(currslot > 0);
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot - 1],
currnode->slotdata[currslot - 1]) );
return temp_value;
}
/// Dereference the iterator. Do not use this if possible, use key()
/// and data() instead. The B+ tree does not stored key and data
/// together.
inline pointer operator->() const
{
BTREE_ASSERT(currslot > 0);
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot - 1],
currnode->slotdata[currslot - 1]) );
return &temp_value;
}
/// Key of the current slot
inline const key_type& key() const
{
BTREE_ASSERT(currslot > 0);
return currnode->slotkey[currslot - 1];
}
/// Writable reference to the current data object
inline data_type& data() const
{
BTREE_ASSERT(currslot > 0);
return currnode->slotdata[currslot - 1];
}
/// Prefix++ advance the iterator to the next slot
inline self& operator++()
{
if (currslot > 1) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse;
}
else {
// this is begin() == rend()
currslot = 0;
}
return *this;
}
/// Postfix++ advance the iterator to the next slot
inline self operator++(int)
{
self tmp = *this; // copy ourselves
if (currslot > 1) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse;
}
else {
// this is begin() == rend()
currslot = 0;
}
return tmp;
}
/// Prefix-- backstep the iterator to the last slot
inline self& operator--()
{
if (currslot < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 1;
}
else {
// this is end() == rbegin()
currslot = currnode->slotuse;
}
return *this;
}
/// Postfix-- backstep the iterator to the last slot
inline self operator--(int)
{
self tmp = *this; // copy ourselves
if (currslot < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 1;
}
else {
// this is end() == rbegin()
currslot = currnode->slotuse;
}
return tmp;
}
/// Equality of iterators
inline bool operator==(const self& x) const
{
return (x.currnode == currnode) && (x.currslot == currslot);
}
/// Inequality of iterators
inline bool operator!=(const self& x) const
{
return (x.currnode != currnode) || (x.currslot != currslot);
}
};
/// STL-like read-only reverse iterator object for B+ tree items. The
/// iterator points to a specific slot number in a leaf.
class const_reverse_iterator
{
public:
// *** Types
/// The key type of the btree. Returned by key().
typedef typename btree::key_type key_type;
/// The data type of the btree. Returned by data().
typedef typename btree::data_type data_type;
/// The value type of the btree. Returned by operator*().
typedef typename btree::value_type value_type;
/// The pair type of the btree.
typedef typename btree::pair_type pair_type;
/// Reference to the value_type. STL required.
typedef const value_type& reference;
/// Pointer to the value_type. STL required.
typedef const value_type* pointer;
/// STL-magic iterator category
typedef std::bidirectional_iterator_tag iterator_category;
/// STL-magic
typedef ptrdiff_t difference_type;
/// Our own type
typedef const_reverse_iterator self;
private:
// *** Members
/// The currently referenced leaf node of the tree
const typename btree::leaf_node* currnode;
/// One slot past the current key/data slot referenced.
unsigned short currslot;
/// Friendly to the const_iterator, so it may access the two data items directly.
friend class reverse_iterator;
/// Evil! A temporary value_type to STL-correctly deliver operator* and
/// operator->
mutable value_type temp_value;
// 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.
BTREE_FRIENDS
public:
// *** Methods
/// Default-Constructor of a const reverse iterator
inline const_reverse_iterator()
: currnode(NULL), currslot(0)
{ }
/// Initializing-Constructor of a const reverse iterator
inline const_reverse_iterator(const typename btree::leaf_node *l, unsigned short s)
: currnode(l), currslot(s)
{ }
/// Copy-constructor from a mutable iterator
inline const_reverse_iterator(const iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Copy-constructor from a const iterator
inline const_reverse_iterator(const const_iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Copy-constructor from a mutable reverse iterator
inline const_reverse_iterator(const reverse_iterator &it)
: currnode(it.currnode), currslot(it.currslot)
{ }
/// Dereference the iterator. Do not use this if possible, use key()
/// and data() instead. The B+ tree does not stored key and data
/// together.
inline reference operator*() const
{
BTREE_ASSERT(currslot > 0);
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot - 1],
currnode->slotdata[currslot - 1]) );
return temp_value;
}
/// Dereference the iterator. Do not use this if possible, use key()
/// and data() instead. The B+ tree does not stored key and data
/// together.
inline pointer operator->() const
{
BTREE_ASSERT(currslot > 0);
temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot - 1],
currnode->slotdata[currslot - 1]) );
return &temp_value;
}
/// Key of the current slot
inline const key_type& key() const
{
BTREE_ASSERT(currslot > 0);
return currnode->slotkey[currslot - 1];
}
/// Read-only reference to the current data object
inline const data_type& data() const
{
BTREE_ASSERT(currslot > 0);
return currnode->slotdata[currslot - 1];
}
/// Prefix++ advance the iterator to the previous slot
inline self& operator++()
{
if (currslot > 1) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse;
}
else {
// this is begin() == rend()
currslot = 0;
}
return *this;
}
/// Postfix++ advance the iterator to the previous slot
inline self operator++(int)
{
self tmp = *this; // copy ourselves
if (currslot > 1) {
--currslot;
}
else if (currnode->prevleaf != NULL) {
currnode = currnode->prevleaf;
currslot = currnode->slotuse;
}
else {
// this is begin() == rend()
currslot = 0;
}
return tmp;
}
/// Prefix-- backstep the iterator to the next slot
inline self& operator--()
{
if (currslot < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 1;
}
else {
// this is end() == rbegin()
currslot = currnode->slotuse;
}
return *this;
}
/// Postfix-- backstep the iterator to the next slot
inline self operator--(int)
{
self tmp = *this; // copy ourselves
if (currslot < currnode->slotuse) {
++currslot;
}
else if (currnode->nextleaf != NULL) {
currnode = currnode->nextleaf;
currslot = 1;
}
else {
// this is end() == rbegin()
currslot = currnode->slotuse;
}
return tmp;
}
/// Equality of iterators
inline bool operator==(const self& x) const
{
return (x.currnode == currnode) && (x.currslot == currslot);
}
/// Inequality of iterators
inline bool operator!=(const self& x) const
{
return (x.currnode != currnode) || (x.currslot != currslot);
}
};
public:
// *** Small Statistics Structure
/** A small struct containing basic statistics about the B+ tree. It can be
* fetched using get_stats(). */
struct tree_stats
{
/// Number of items in the B+ tree
size_type itemcount;
/// Number of leaves in the B+ tree
size_type leaves;
/// Number of inner nodes in the B+ tree
size_type innernodes;
/// Base B+ tree parameter: The number of key/data slots in each leaf
static const unsigned short leafslots = btree_self::leafslotmax;
/// Base B+ tree parameter: The number of key slots in each inner node.
static const unsigned short innerslots = btree_self::innerslotmax;
/// Zero initialized
inline tree_stats()
: itemcount(0),
leaves(0), innernodes(0)
{
}
/// Return the total number of nodes
inline size_type nodes() const
{
return innernodes + leaves;
}
/// Return the average fill of leaves
inline double avgfill_leaves() const
{
return static_cast<double>(itemcount) / (leaves * leafslots);
}
};
private:
// *** Tree Object Data Members
/// Pointer to the B+ tree's root node, either leaf or inner node
node* root;
/// Pointer to first leaf in the double linked leaf chain
leaf_node *headleaf;
/// Pointer to last leaf in the double linked leaf chain
leaf_node *tailleaf;
/// Other small statistics about the B+ tree
tree_stats stats;
/// Key comparison object. More comparison functions are generated from
/// this < relation.
key_compare key_less;
public:
// *** Constructors and Destructor
/// Default constructor initializing an empty B+ tree with the standard key
/// comparison function
inline btree()
: root(NULL), headleaf(NULL), tailleaf(NULL)
{
}
/// Constructor initializing an empty B+ tree with a special key
/// comparison object
inline btree(const key_compare &kcf)
: root(NULL), headleaf(NULL), tailleaf(NULL),
key_less(kcf)
{
}
/// Constructor initializing a B+ tree with the range [first,last)
template <class InputIterator>
inline btree(InputIterator first, InputIterator last)
: root(NULL), headleaf(NULL), tailleaf(NULL)
{
insert(first, last);
}
/// Constructor initializing a B+ tree with the range [first,last) and a
/// special key comparison object
template <class InputIterator>
inline btree(InputIterator first, InputIterator last, const key_compare &kcf)
: root(NULL), headleaf(NULL), tailleaf(NULL),
key_less(kcf)
{
insert(first, last);
}
/// Frees up all used B+ tree memory pages
inline ~btree()
{
clear();
}
/// Fast swapping of two identical B+ tree objects.
void swap(btree_self& from)
{
std::swap(root, from.root);
std::swap(headleaf, from.headleaf);
std::swap(tailleaf, from.tailleaf);
std::swap(stats, from.stats);
std::swap(key_less, from.key_less);
}
public:
// *** Key and Value Comparison Function Objects
/// Function class to compare value_type objects. Required by the STL
class value_compare
{
protected:
/// Key comparison function from the template parameter
key_compare key_comp;
/// Constructor called from btree::value_comp()
inline value_compare(key_compare kc)
: key_comp(kc)
{ }
/// Friendly to the btree class so it may call the constructor
friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>;
public:
/// Function call "less"-operator resulting in true if x < y.
inline bool operator()(const value_type& x, const value_type& y) const
{
return key_comp(x.first, y.first);
}
};
/// Constant access to the key comparison object sorting the B+ tree
inline key_compare key_comp() const
{
return key_less;
}
/// Constant access to a constructed value_type comparison object. Required
/// by the STL
inline value_compare value_comp() const
{
return value_compare(key_less);
}
private:
// *** Convenient Key Comparison Functions Generated From key_less
/// True if a <= b ? constructed from key_less()
inline bool key_lessequal(const key_type &a, const key_type b) const
{
return !key_less(b, a);
}
/// True if a > b ? constructed from key_less()
inline bool key_greater(const key_type &a, const key_type &b) const
{
return key_less(b, a);
}
/// True if a >= b ? constructed from key_less()
inline bool key_greaterequal(const key_type &a, const key_type b) const
{
return !key_less(a, b);
}
/// True if a == b ? constructed from key_less(). This requires the <
/// relation to be a total order, otherwise the B+ tree cannot be sorted.
inline bool key_equal(const key_type &a, const key_type &b) const
{
return !key_less(a, b) && !key_less(b, a);
}
private:
// *** Node Object Allocation and Deallocation Functions
/// Allocate and initialize a leaf node
inline leaf_node* allocate_leaf()
{
leaf_node* n = new leaf_node;
n->initialize();
stats.leaves++;
return n;
}
/// Allocate and initialize an inner node
inline inner_node* allocate_inner(unsigned short l)
{
inner_node* n = new inner_node;
n->initialize(l);
stats.innernodes++;
return n;
}
/// Correctly free either inner or leaf node, destructs all contained key
/// and value objects
inline void free_node(node *n)
{
if (n->isleafnode()) {
delete static_cast<leaf_node*>(n);
stats.leaves--;
}
else {
delete static_cast<inner_node*>(n);
stats.innernodes--;
}
}
public:
// *** Fast Destruction of the B+ Tree
/// Frees all key/data pairs and all nodes of the tree
void clear()
{
if (root)
{
clear_recursive(root);
free_node(root);
root = NULL;
headleaf = tailleaf = NULL;
stats = tree_stats();
}
BTREE_ASSERT(stats.itemcount == 0);
}
private:
/// Recursively free up nodes
void clear_recursive(node *n)
{
if (n->isleafnode())
{
leaf_node *leafnode = static_cast<leaf_node*>(n);
for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
{
// data objects are deleted by leaf_node's destructor
}
}
else
{
inner_node *innernode = static_cast<inner_node*>(n);
for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
{
clear_recursive(innernode->childid[slot]);
free_node(innernode->childid[slot]);
}
}
}
public:
// *** STL Iterator Construction Functions
/// Constructs a read/data-write iterator that points to the first slot in
/// the first leaf of the B+ tree.
inline iterator begin()
{
return iterator(headleaf, 0);
}
/// Constructs a read/data-write iterator that points to the first invalid
/// slot in the last leaf of the B+ tree.
inline iterator end()
{
return iterator(tailleaf, tailleaf ? tailleaf->slotuse : 0);
}
/// Constructs a read-only constant iterator that points to the first slot
/// in the first leaf of the B+ tree.
inline const_iterator begin() const
{
return const_iterator(headleaf, 0);
}
/// Constructs a read-only constant iterator that points to the first
/// invalid slot in the last leaf of the B+ tree.
inline const_iterator end() const
{
return const_iterator(tailleaf, tailleaf ? tailleaf->slotuse : 0);
}
/// 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.
inline reverse_iterator rbegin()
{
return reverse_iterator(end());
}
/// Constructs a read/data-write reverse iterator that points to the first
/// slot in the first leaf of the B+ tree. Uses STL magic.
inline reverse_iterator rend()
{
return reverse_iterator(begin());
}
/// Constructs a read-only reverse iterator that points to the first
/// invalid slot in the last leaf of the B+ tree. Uses STL magic.
inline const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
/// Constructs a read-only reverse iterator that points to the first slot
/// in the first leaf of the B+ tree. Uses STL magic.
inline const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
private:
// *** B+ Tree Node Binary Search Functions
/// Searches for the first key in the node n less 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.
template <typename node_type>
inline int find_lower(const node_type *n, const key_type& key) const
{
if (n->slotuse == 0) return 0;
int lo = 0,
hi = n->slotuse - 1;
while(lo < hi)
{
int mid = (lo + hi) >> 1;
if (key_lessequal(key, n->slotkey[mid])) {
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
if (hi < 0 || key_less(n->slotkey[hi], key))
hi++;
BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
// verify result using simple linear search
if (selfverify)
{
int i = n->slotuse - 1;
while(i >= 0 && key_lessequal(key, n->slotkey[i]))
i--;
i++;
BTREE_PRINT("testfind: " << i << std::endl);
BTREE_ASSERT(i == hi);
}
else {
BTREE_PRINT(std::endl);
}
return hi;
}
/// Searches for the first key in the node n greater than key.