Created
October 4, 2013 14:11
-
-
Save kernelhcy/6826553 to your computer and use it in GitHub Desktop.
STX B+ Tree实现
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* \file include/stx/btree.h | |
* Contains the main B+ tree implementation template class btree. | |
*/ | |
/* | |
* STX B+ Tree Template Classes v0.9 | |
* Copyright (C) 2008-2013 Timo Bingmann <tb@panthema.net> | |
* | |
* Boost Software License - Version 1.0 - August 17th, 2003 | |
* | |
* Permission is hereby granted, free of charge, to any person or organization | |
* obtaining a copy of the software and accompanying documentation covered by | |
* this license (the "Software") to use, reproduce, display, distribute, | |
* execute, and transmit the Software, and to prepare derivative works of the | |
* Software, and to permit third-parties to whom the Software is furnished to | |
* do so, all subject to the following: | |
* | |
* The copyright notices in the Software and this entire statement, including | |
* the above license grant, this restriction and the following disclaimer, must | |
* be included in all copies of the Software, in whole or in part, and all | |
* derivative works of the Software, unless such copies or derivative works are | |
* solely in the form of machine-executable object code generated by a source | |
* language processor. | |
* | |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
* FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT | |
* SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE | |
* FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, | |
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | |
* DEALINGS IN THE SOFTWARE. | |
*/ | |
#ifndef _STX_BTREE_H_ | |
#define _STX_BTREE_H_ | |
// *** Required Headers from the STL | |
#include <algorithm> | |
#include <functional> | |
#include <istream> | |
#include <ostream> | |
#include <memory> | |
#include <cstddef> | |
#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 << std::endl); } 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*)) ); | |
/// As of stx-btree-0.9, the code does linear search in find_lower() and | |
/// find_upper() instead of binary_search, unless the node size is larger | |
/// than this threshold. See notes at | |
/// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search | |
static const size_t binsearch_threshold = 256; | |
}; | |
/** 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*)) ); | |
/// As of stx-btree-0.9, the code does linear search in find_lower() and | |
/// find_upper() instead of binary_search, unless the node size is larger | |
/// than this threshold. See notes at | |
/// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search | |
static const size_t binsearch_threshold = 256; | |
}; | |
/** @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, | |
typename _Alloc = std::allocator<_Value>, | |
bool _UsedAsSet = 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; | |
/// Seventh template parameter: STL allocator for tree nodes | |
typedef _Alloc allocator_type; | |
/// Eighth template parameter: boolean indicator whether the btree is used | |
/// as a set. In this case all operations on the data arrays are | |
/// omitted. This flag is kind of hacky, but required because | |
/// sizeof(empty_struct) = 1 due to the C standard. Without the flag, lots | |
/// of superfluous copying would occur. | |
static const bool used_as_set = _UsedAsSet; | |
// 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, allocator_type, used_as_set> 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 | |
{ | |
/// Define an related allocator for the inner_node structs. | |
typedef typename _Alloc::template rebind<inner_node>::other alloc_type; | |
/// 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 | |
{ | |
/// Define an related allocator for the leaf_node structs. | |
typedef typename _Alloc::template rebind<leaf_node>::other alloc_type; | |
/// 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[used_as_set ? 1 : 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); | |
} | |
/// Set the (key,data) pair in slot. Overloaded function used by | |
/// bulk_load(). | |
inline void set_slot(unsigned short slot, const pair_type& value) | |
{ | |
BTREE_ASSERT(used_as_set == false); | |
BTREE_ASSERT(slot < node::slotuse); | |
slotkey[slot] = value.first; | |
slotdata[slot] = value.second; | |
} | |
/// Set the key pair in slot. Overloaded function used by | |
/// bulk_load(). | |
inline void set_slot(unsigned short slot, const key_type& key) | |
{ | |
BTREE_ASSERT(used_as_set == true); | |
BTREE_ASSERT(slot < node::slotuse); | |
slotkey[slot] = key; | |
} | |
}; | |
private: | |
// *** Template Magic to Convert a pair or key/data types to a value_type | |
/// 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; | |
} | |
}; | |
/// 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; | |
/// Also friendly to the base btree class, because erase_iter() needs | |
/// to read the currnode and currslot values directly. | |
friend class btree<key_type, data_type, value_type, key_compare, | |
traits, allow_duplicates, allocator_type, used_as_set>; | |
/// 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(key(),data()) ); | |
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(key(),data()) ); | |
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[used_as_set ? 0 : 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(key(),data()) ); | |
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(key(),data()) ); | |
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[used_as_set ? 0 : 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(key(),data()) ); | |
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(key(),data()) ); | |
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[used_as_set ? 0 : 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(key(),data()) ); | |
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(key(),data()) ); | |
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[used_as_set ? 0 : 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* m_root; | |
/// Pointer to first leaf in the double linked leaf chain | |
leaf_node *m_headleaf; | |
/// Pointer to last leaf in the double linked leaf chain | |
leaf_node *m_tailleaf; | |
/// Other small statistics about the B+ tree | |
tree_stats m_stats; | |
/// Key comparison object. More comparison functions are generated from | |
/// this < relation. | |
key_compare m_key_less; | |
/// Memory allocator. | |
allocator_type m_allocator; | |
public: | |
// *** Constructors and Destructor | |
/// Default constructor initializing an empty B+ tree with the standard key | |
/// comparison function | |
explicit inline btree(const allocator_type &alloc = allocator_type()) | |
: m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), m_allocator(alloc) | |
{ | |
} | |
/// Constructor initializing an empty B+ tree with a special key | |
/// comparison object | |
explicit inline btree(const key_compare &kcf, | |
const allocator_type &alloc = allocator_type()) | |
: m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), | |
m_key_less(kcf), m_allocator(alloc) | |
{ | |
} | |
/// Constructor initializing a B+ tree with the range [first,last). The | |
/// range need not be sorted. To create a B+ tree from a sorted range, use | |
/// bulk_load(). | |
template <class InputIterator> | |
inline btree(InputIterator first, InputIterator last, | |
const allocator_type &alloc = allocator_type()) | |
: m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), m_allocator(alloc) | |
{ | |
insert(first, last); | |
} | |
/// Constructor initializing a B+ tree with the range [first,last) and a | |
/// special key comparison object. The range need not be sorted. To create | |
/// a B+ tree from a sorted range, use bulk_load(). | |
template <class InputIterator> | |
inline btree(InputIterator first, InputIterator last, const key_compare &kcf, | |
const allocator_type &alloc = allocator_type()) | |
: m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), | |
m_key_less(kcf), m_allocator(alloc) | |
{ | |
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(m_root, from.m_root); | |
std::swap(m_headleaf, from.m_headleaf); | |
std::swap(m_tailleaf, from.m_tailleaf); | |
std::swap(m_stats, from.m_stats); | |
std::swap(m_key_less, from.m_key_less); | |
std::swap(m_allocator, from.m_allocator); | |
} | |
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, allocator_type, used_as_set>; | |
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 m_key_less; | |
} | |
/// Constant access to a constructed value_type comparison object. Required | |
/// by the STL | |
inline value_compare value_comp() const | |
{ | |
return value_compare(m_key_less); | |
} | |
private: | |
// *** Convenient Key Comparison Functions Generated From key_less | |
/// True if a < b ? "constructed" from m_key_less() | |
inline bool key_less(const key_type &a, const key_type b) const | |
{ | |
return m_key_less(a, b); | |
} | |
/// True if a <= b ? constructed from key_less() | |
inline bool key_lessequal(const key_type &a, const key_type b) const | |
{ | |
return !m_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 m_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 !m_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 !m_key_less(a, b) && !m_key_less(b, a); | |
} | |
public: | |
// *** Allocators | |
/// Return the base node allocator provided during construction. | |
allocator_type get_allocator() const | |
{ | |
return m_allocator; | |
} | |
private: | |
// *** Node Object Allocation and Deallocation Functions | |
/// Return an allocator for leaf_node objects | |
typename leaf_node::alloc_type leaf_node_allocator() | |
{ | |
return typename leaf_node::alloc_type(m_allocator); | |
} | |
/// Return an allocator for inner_node objects | |
typename inner_node::alloc_type inner_node_allocator() | |
{ | |
return typename inner_node::alloc_type(m_allocator); | |
} | |
/// Allocate and initialize a leaf node | |
inline leaf_node* allocate_leaf() | |
{ | |
leaf_node *n = new (leaf_node_allocator().allocate(1)) leaf_node(); | |
n->initialize(); | |
m_stats.leaves++; | |
return n; | |
} | |
/// Allocate and initialize an inner node | |
inline inner_node* allocate_inner(unsigned short level) | |
{ | |
inner_node *n = new (inner_node_allocator().allocate(1)) inner_node(); | |
n->initialize(level); | |
m_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()) { | |
leaf_node *ln = static_cast<leaf_node*>(n); | |
typename leaf_node::alloc_type a(leaf_node_allocator()); | |
a.destroy(ln); | |
a.deallocate(ln, 1); | |
m_stats.leaves--; | |
} | |
else { | |
inner_node *in = static_cast<inner_node*>(n); | |
typename inner_node::alloc_type a(inner_node_allocator()); | |
a.destroy(in); | |
a.deallocate(in, 1); | |
m_stats.innernodes--; | |
} | |
} | |
/// Convenient template function for conditional copying of slotdata. This | |
/// should be used instead of std::copy for all slotdata manipulations. | |
template<class InputIterator, class OutputIterator> | |
static OutputIterator data_copy (InputIterator first, InputIterator last, | |
OutputIterator result) | |
{ | |
if (used_as_set) return result; // no operation | |
else return std::copy(first, last, result); | |
} | |
/// Convenient template function for conditional copying of slotdata. This | |
/// should be used instead of std::copy for all slotdata manipulations. | |
template<class InputIterator, class OutputIterator> | |
static OutputIterator data_copy_backward (InputIterator first, InputIterator last, | |
OutputIterator result) | |
{ | |
if (used_as_set) return result; // no operation | |
else return std::copy_backward(first, last, result); | |
} | |
public: | |
// *** Fast Destruction of the B+ Tree | |
/// Frees all key/data pairs and all nodes of the tree | |
void clear() | |
{ | |
if (m_root) | |
{ | |
clear_recursive(m_root); | |
free_node(m_root); | |
m_root = NULL; | |
m_headleaf = m_tailleaf = NULL; | |
m_stats = tree_stats(); | |
} | |
BTREE_ASSERT(m_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(m_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(m_tailleaf, m_tailleaf ? m_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(m_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(m_tailleaf, m_tailleaf ? m_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 greater 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 ( 0 && sizeof(n->slotkey) > traits::binsearch_threshold ) | |
{ | |
if (n->slotuse == 0) return 0; | |
int lo = 0, hi = n->slotuse; | |
while (lo < hi) | |
{ | |
int mid = (lo + hi) >> 1; | |
if (key_lessequal(key, n->slotkey[mid])) { | |
hi = mid; // key <= mid | |
} | |
else { | |
lo = mid + 1; // key > mid | |
} | |
} | |
BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> " << lo << " / " << hi); | |
// verify result using simple linear search | |
if (selfverify) | |
{ | |
int i = 0; | |
while (i < n->slotuse && key_less(n->slotkey[i],key)) ++i; | |
BTREE_PRINT("btree::find_lower: testfind: " << i); | |
BTREE_ASSERT(i == lo); | |
} | |
return lo; | |
} | |
else // for nodes <= binsearch_threshold do linear search. | |
{ | |
int lo = 0; | |
while (lo < n->slotuse && key_less(n->slotkey[lo],key)) ++lo; | |
return lo; | |
} | |
} | |
/// Searches for the first key in the node n greater than 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_upper(const node_type *n, const key_type& key) const | |
{ | |
if ( 0 && sizeof(n->slotkey) > traits::binsearch_threshold ) | |
{ | |
if (n->slotuse == 0) return 0; | |
int lo = 0, hi = n->slotuse; | |
while (lo < hi) | |
{ | |
int mid = (lo + hi) >> 1; | |
if (key_less(key, n->slotkey[mid])) { | |
hi = mid; // key < mid | |
} | |
else { | |
lo = mid + 1; // key >= mid | |
} | |
} | |
BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> " << lo << " / " << hi); | |
// verify result using simple linear search | |
if (selfverify) | |
{ | |
int i = 0; | |
while (i < n->slotuse && key_lessequal(n->slotkey[i],key)) ++i; | |
BTREE_PRINT("btree::find_upper testfind: " << i); | |
BTREE_ASSERT(i == hi); | |
} | |
return lo; | |
} | |
else // for nodes <= binsearch_threshold do linear search. | |
{ | |
int lo = 0; | |
while (lo < n->slotuse && key_lessequal(n->slotkey[lo],key)) ++lo; | |
return lo; | |
} | |
} | |
public: | |
// *** Access Functions to the Item Count | |
/// Return the number of key/data pairs in the B+ tree | |
inline size_type size() const | |
{ | |
return m_stats.itemcount; | |
} | |
/// Returns true if there is at least one key/data pair in the B+ tree | |
inline bool empty() const | |
{ | |
return (size() == size_type(0)); | |
} | |
/// Returns the largest possible size of the B+ Tree. This is just a | |
/// function required by the STL standard, the B+ Tree can hold more items. | |
inline size_type max_size() const | |
{ | |
return size_type(-1); | |
} | |
/// Return a const reference to the current statistics. | |
inline const struct tree_stats& get_stats() const | |
{ | |
return m_stats; | |
} | |
public: | |
// *** Standard Access Functions Querying the Tree by Descending to a Leaf | |
/// Non-STL function checking whether a key is in the B+ tree. The same as | |
/// (find(k) != end()) or (count() != 0). | |
bool exists(const key_type &key) const | |
{ | |
const node *n = m_root; | |
if (!n) return false; | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_lower(inner, key); | |
n = inner->childid[slot]; | |
} | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])); | |
} | |
/// Tries to locate a key in the B+ tree and returns an iterator to the | |
/// key/data slot if found. If unsuccessful it returns end(). | |
iterator find(const key_type &key) | |
{ | |
node *n = m_root; | |
if (!n) return end(); | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_lower(inner, key); | |
n = inner->childid[slot]; | |
} | |
leaf_node *leaf = static_cast<leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) | |
? iterator(leaf, slot) : end(); | |
} | |
/// Tries to locate a key in the B+ tree and returns an constant iterator | |
/// to the key/data slot if found. If unsuccessful it returns end(). | |
const_iterator find(const key_type &key) const | |
{ | |
const node *n = m_root; | |
if (!n) return end(); | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_lower(inner, key); | |
n = inner->childid[slot]; | |
} | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) | |
? const_iterator(leaf, slot) : end(); | |
} | |
/// Tries to locate a key in the B+ tree and returns the number of | |
/// identical key entries found. | |
size_type count(const key_type &key) const | |
{ | |
const node *n = m_root; | |
if (!n) return 0; | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_lower(inner, key); | |
n = inner->childid[slot]; | |
} | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
size_type num = 0; | |
while (leaf && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) | |
{ | |
++num; | |
if (++slot >= leaf->slotuse) | |
{ | |
leaf = leaf->nextleaf; | |
slot = 0; | |
} | |
} | |
return num; | |
} | |
/// Searches the B+ tree and returns an iterator to the first pair | |
/// equal to or greater than key, or end() if all keys are smaller. | |
iterator lower_bound(const key_type& key) | |
{ | |
node *n = m_root; | |
if (!n) return end(); | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_lower(inner, key); | |
n = inner->childid[slot]; | |
} | |
leaf_node *leaf = static_cast<leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
return iterator(leaf, slot); | |
} | |
/// Searches the B+ tree and returns a constant iterator to the | |
/// first pair equal to or greater than key, or end() if all keys | |
/// are smaller. | |
const_iterator lower_bound(const key_type& key) const | |
{ | |
const node *n = m_root; | |
if (!n) return end(); | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_lower(inner, key); | |
n = inner->childid[slot]; | |
} | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
return const_iterator(leaf, slot); | |
} | |
/// Searches the B+ tree and returns an iterator to the first pair | |
/// greater than key, or end() if all keys are smaller or equal. | |
iterator upper_bound(const key_type& key) | |
{ | |
node *n = m_root; | |
if (!n) return end(); | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_upper(inner, key); | |
n = inner->childid[slot]; | |
} | |
leaf_node *leaf = static_cast<leaf_node*>(n); | |
int slot = find_upper(leaf, key); | |
return iterator(leaf, slot); | |
} | |
/// Searches the B+ tree and returns a constant iterator to the | |
/// first pair greater than key, or end() if all keys are smaller | |
/// or equal. | |
const_iterator upper_bound(const key_type& key) const | |
{ | |
const node *n = m_root; | |
if (!n) return end(); | |
while(!n->isleafnode()) | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
int slot = find_upper(inner, key); | |
n = inner->childid[slot]; | |
} | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
int slot = find_upper(leaf, key); | |
return const_iterator(leaf, slot); | |
} | |
/// Searches the B+ tree and returns both lower_bound() and upper_bound(). | |
inline std::pair<iterator, iterator> equal_range(const key_type& key) | |
{ | |
return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key)); | |
} | |
/// Searches the B+ tree and returns both lower_bound() and upper_bound(). | |
inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const | |
{ | |
return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key)); | |
} | |
public: | |
// *** B+ Tree Object Comparison Functions | |
/// Equality relation of B+ trees of the same type. B+ trees of the same | |
/// size and equal elements (both key and data) are considered | |
/// equal. Beware of the random ordering of duplicate keys. | |
inline bool operator==(const btree_self &other) const | |
{ | |
return (size() == other.size()) && std::equal(begin(), end(), other.begin()); | |
} | |
/// Inequality relation. Based on operator==. | |
inline bool operator!=(const btree_self &other) const | |
{ | |
return !(*this == other); | |
} | |
/// Total ordering relation of B+ trees of the same type. It uses | |
/// std::lexicographical_compare() for the actual comparison of elements. | |
inline bool operator<(const btree_self &other) const | |
{ | |
return std::lexicographical_compare(begin(), end(), other.begin(), other.end()); | |
} | |
/// Greater relation. Based on operator<. | |
inline bool operator>(const btree_self &other) const | |
{ | |
return other < *this; | |
} | |
/// Less-equal relation. Based on operator<. | |
inline bool operator<=(const btree_self &other) const | |
{ | |
return !(other < *this); | |
} | |
/// Greater-equal relation. Based on operator<. | |
inline bool operator>=(const btree_self &other) const | |
{ | |
return !(*this < other); | |
} | |
public: | |
/// *** Fast Copy: Assign Operator and Copy Constructors | |
/// Assignment operator. All the key/data pairs are copied | |
inline btree_self& operator= (const btree_self &other) | |
{ | |
if (this != &other) | |
{ | |
clear(); | |
m_key_less = other.key_comp(); | |
m_allocator = other.get_allocator(); | |
if (other.size() != 0) | |
{ | |
m_stats.leaves = m_stats.innernodes = 0; | |
if (other.m_root) { | |
m_root = copy_recursive(other.m_root); | |
} | |
m_stats = other.m_stats; | |
} | |
if (selfverify) verify(); | |
} | |
return *this; | |
} | |
/// Copy constructor. The newly initialized B+ tree object will contain a | |
/// copy of all key/data pairs. | |
inline btree(const btree_self &other) | |
: m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), | |
m_stats( other.m_stats ), | |
m_key_less( other.key_comp() ), | |
m_allocator( other.get_allocator() ) | |
{ | |
if (size() > 0) | |
{ | |
m_stats.leaves = m_stats.innernodes = 0; | |
if (other.m_root) { | |
m_root = copy_recursive(other.m_root); | |
} | |
if (selfverify) verify(); | |
} | |
} | |
private: | |
/// Recursively copy nodes from another B+ tree object | |
struct node* copy_recursive(const node *n) | |
{ | |
if (n->isleafnode()) | |
{ | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
leaf_node *newleaf = allocate_leaf(); | |
newleaf->slotuse = leaf->slotuse; | |
std::copy(leaf->slotkey, leaf->slotkey + leaf->slotuse, newleaf->slotkey); | |
data_copy(leaf->slotdata, leaf->slotdata + leaf->slotuse, newleaf->slotdata); | |
if (m_headleaf == NULL) | |
{ | |
m_headleaf = m_tailleaf = newleaf; | |
newleaf->prevleaf = newleaf->nextleaf = NULL; | |
} | |
else | |
{ | |
newleaf->prevleaf = m_tailleaf; | |
m_tailleaf->nextleaf = newleaf; | |
m_tailleaf = newleaf; | |
} | |
return newleaf; | |
} | |
else | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
inner_node *newinner = allocate_inner(inner->level); | |
newinner->slotuse = inner->slotuse; | |
std::copy(inner->slotkey, inner->slotkey + inner->slotuse, newinner->slotkey); | |
for (unsigned short slot = 0; slot <= inner->slotuse; ++slot) | |
{ | |
newinner->childid[slot] = copy_recursive(inner->childid[slot]); | |
} | |
return newinner; | |
} | |
} | |
public: | |
// *** Public Insertion Functions | |
/// Attempt to insert a key/data pair into the B+ tree. If the tree does not | |
/// allow duplicate keys, then the insert may fail if it is already | |
/// present. | |
inline std::pair<iterator, bool> insert(const pair_type& x) | |
{ | |
return insert_start(x.first, x.second); | |
} | |
/// Attempt to insert a key/data pair into the B+ tree. Beware that if | |
/// key_type == data_type, then the template iterator insert() is called | |
/// instead. If the tree does not allow duplicate keys, then the insert may | |
/// fail if it is already present. | |
inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data) | |
{ | |
return insert_start(key, data); | |
} | |
/// Attempt to insert a key/data pair into the B+ tree. This function is the | |
/// same as the other insert, however if key_type == data_type then the | |
/// non-template function cannot be called. If the tree does not allow | |
/// duplicate keys, then the insert may fail if it is already present. | |
inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data) | |
{ | |
return insert_start(key, data); | |
} | |
/// Attempt to insert a key/data pair into the B+ tree. The iterator hint | |
/// is currently ignored by the B+ tree insertion routine. | |
inline iterator insert(iterator /* hint */, const pair_type &x) | |
{ | |
return insert_start(x.first, x.second).first; | |
} | |
/// Attempt to insert a key/data pair into the B+ tree. The iterator hint is | |
/// currently ignored by the B+ tree insertion routine. | |
inline iterator insert2(iterator /* hint */, const key_type& key, const data_type& data) | |
{ | |
return insert_start(key, data).first; | |
} | |
/// Attempt to insert the range [first,last) of value_type pairs into the | |
/// B+ tree. Each key/data pair is inserted individually; to bulk load the | |
/// tree, use a constructor with range. | |
template <typename InputIterator> | |
inline void insert(InputIterator first, InputIterator last) | |
{ | |
InputIterator iter = first; | |
while(iter != last) | |
{ | |
insert(*iter); | |
++iter; | |
} | |
} | |
private: | |
// *** Private Insertion Functions | |
/// Start the insertion descent at the current root and handle root | |
/// splits. Returns true if the item was inserted | |
std::pair<iterator, bool> insert_start(const key_type& key, const data_type& value) | |
{ | |
node *newchild = NULL; | |
key_type newkey = key_type(); | |
if (m_root == NULL) { | |
m_root = m_headleaf = m_tailleaf = allocate_leaf(); | |
} | |
std::pair<iterator, bool> r = insert_descend(m_root, key, value, &newkey, &newchild); | |
if (newchild) | |
{ | |
inner_node *newroot = allocate_inner(m_root->level + 1); | |
newroot->slotkey[0] = newkey; | |
newroot->childid[0] = m_root; | |
newroot->childid[1] = newchild; | |
newroot->slotuse = 1; | |
m_root = newroot; | |
} | |
// increment itemcount if the item was inserted | |
if (r.second) ++m_stats.itemcount; | |
#ifdef BTREE_DEBUG | |
if (debug) print(std::cout); | |
#endif | |
if (selfverify) { | |
verify(); | |
BTREE_ASSERT(exists(key)); | |
} | |
return r; | |
} | |
/** | |
* @brief Insert an item into the B+ tree. | |
* | |
* Descend down the nodes to a leaf, insert the key/data pair in a free | |
* slot. If the node overflows, then it must be split and the new split | |
* node inserted into the parent. Unroll / this splitting up to the root. | |
*/ | |
std::pair<iterator, bool> insert_descend(node* n, | |
const key_type& key, const data_type& value, | |
key_type* splitkey, node** splitnode) | |
{ | |
if (!n->isleafnode()) | |
{ | |
inner_node *inner = static_cast<inner_node*>(n); | |
key_type newkey = key_type(); | |
node *newchild = NULL; | |
int slot = find_lower(inner, key); | |
BTREE_PRINT("btree::insert_descend into " << inner->childid[slot]); | |
std::pair<iterator, bool> r = insert_descend(inner->childid[slot], | |
key, value, &newkey, &newchild); | |
if (newchild) | |
{ | |
BTREE_PRINT("btree::insert_descend newchild with key " << newkey << " node " << newchild << " at slot " << slot); | |
if (inner->isfull()) | |
{ | |
split_inner_node(inner, splitkey, splitnode, slot); | |
BTREE_PRINT("btree::insert_descend done split_inner: putslot: " << slot << " putkey: " << newkey << " upkey: " << *splitkey); | |
#ifdef BTREE_DEBUG | |
if (debug) | |
{ | |
print_node(std::cout, inner); | |
print_node(std::cout, *splitnode); | |
} | |
#endif | |
// check if insert slot is in the split sibling node | |
BTREE_PRINT("btree::insert_descend switch: " << slot << " > " << inner->slotuse+1); | |
if (slot == inner->slotuse+1 && inner->slotuse < (*splitnode)->slotuse) | |
{ | |
// special case when the insert slot matches the split | |
// place between the two nodes, then the insert key | |
// becomes the split key. | |
BTREE_ASSERT(inner->slotuse + 1 < innerslotmax); | |
inner_node *splitinner = static_cast<inner_node*>(*splitnode); | |
// move the split key and it's datum into the left node | |
inner->slotkey[inner->slotuse] = *splitkey; | |
inner->childid[inner->slotuse+1] = splitinner->childid[0]; | |
inner->slotuse++; | |
// set new split key and move corresponding datum into right node | |
splitinner->childid[0] = newchild; | |
*splitkey = newkey; | |
return r; | |
} | |
else if (slot >= inner->slotuse+1) | |
{ | |
// in case the insert slot is in the newly create split | |
// node, we reuse the code below. | |
slot -= inner->slotuse+1; | |
inner = static_cast<inner_node*>(*splitnode); | |
BTREE_PRINT("btree::insert_descend switching to splitted node " << inner << " slot " << slot); | |
} | |
} | |
// move items and put pointer to child node into correct slot | |
BTREE_ASSERT(slot >= 0 && slot <= inner->slotuse); | |
std::copy_backward(inner->slotkey + slot, inner->slotkey + inner->slotuse, | |
inner->slotkey + inner->slotuse+1); | |
std::copy_backward(inner->childid + slot, inner->childid + inner->slotuse+1, | |
inner->childid + inner->slotuse+2); | |
inner->slotkey[slot] = newkey; | |
inner->childid[slot + 1] = newchild; | |
inner->slotuse++; | |
} | |
return r; | |
} | |
else // n->isleafnode() == true | |
{ | |
leaf_node *leaf = static_cast<leaf_node*>(n); | |
int slot = find_lower(leaf, key); | |
if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) { | |
return std::pair<iterator, bool>(iterator(leaf, slot), false); | |
} | |
if (leaf->isfull()) | |
{ | |
split_leaf_node(leaf, splitkey, splitnode); | |
// check if insert slot is in the split sibling node | |
if (slot >= leaf->slotuse) | |
{ | |
slot -= leaf->slotuse; | |
leaf = static_cast<leaf_node*>(*splitnode); | |
} | |
} | |
// move items and put data item into correct data slot | |
BTREE_ASSERT(slot >= 0 && slot <= leaf->slotuse); | |
std::copy_backward(leaf->slotkey + slot, leaf->slotkey + leaf->slotuse, | |
leaf->slotkey + leaf->slotuse+1); | |
data_copy_backward(leaf->slotdata + slot, leaf->slotdata + leaf->slotuse, | |
leaf->slotdata + leaf->slotuse+1); | |
leaf->slotkey[slot] = key; | |
if (!used_as_set) leaf->slotdata[slot] = value; | |
leaf->slotuse++; | |
if (splitnode && leaf != *splitnode && slot == leaf->slotuse-1) | |
{ | |
// special case: the node was split, and the insert is at the | |
// last slot of the old node. then the splitkey must be | |
// updated. | |
*splitkey = key; | |
} | |
return std::pair<iterator, bool>(iterator(leaf, slot), true); | |
} | |
} | |
/// Split up a leaf node into two equally-filled sibling leaves. Returns | |
/// the new nodes and it's insertion key in the two parameters. | |
void split_leaf_node(leaf_node* leaf, key_type* _newkey, node** _newleaf) | |
{ | |
BTREE_ASSERT(leaf->isfull()); | |
unsigned int mid = (leaf->slotuse >> 1); | |
BTREE_PRINT("btree::split_leaf_node on " << leaf); | |
leaf_node *newleaf = allocate_leaf(); | |
newleaf->slotuse = leaf->slotuse - mid; | |
newleaf->nextleaf = leaf->nextleaf; | |
if (newleaf->nextleaf == NULL) { | |
BTREE_ASSERT(leaf == m_tailleaf); | |
m_tailleaf = newleaf; | |
} | |
else { | |
newleaf->nextleaf->prevleaf = newleaf; | |
} | |
std::copy(leaf->slotkey + mid, leaf->slotkey + leaf->slotuse, | |
newleaf->slotkey); | |
data_copy(leaf->slotdata + mid, leaf->slotdata + leaf->slotuse, | |
newleaf->slotdata); | |
leaf->slotuse = mid; | |
leaf->nextleaf = newleaf; | |
newleaf->prevleaf = leaf; | |
*_newkey = leaf->slotkey[leaf->slotuse-1]; | |
*_newleaf = newleaf; | |
} | |
/// Split up an inner node into two equally-filled sibling nodes. Returns | |
/// the new nodes and it's insertion key in the two parameters. Requires | |
/// the slot of the item will be inserted, so the nodes will be the same | |
/// size after the insert. | |
void split_inner_node(inner_node* inner, key_type* _newkey, node** _newinner, unsigned int addslot) | |
{ | |
BTREE_ASSERT(inner->isfull()); | |
unsigned int mid = (inner->slotuse >> 1); | |
BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot); | |
// if the split is uneven and the overflowing item will be put into the | |
// larger node, then the smaller split node may underflow | |
if (addslot <= mid && mid > inner->slotuse - (mid + 1)) | |
mid--; | |
BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot); | |
BTREE_PRINT("btree::split_inner_node on " << inner << " into two nodes " << mid << " and " << inner->slotuse - (mid + 1) << " sized"); | |
inner_node *newinner = allocate_inner(inner->level); | |
newinner->slotuse = inner->slotuse - (mid + 1); | |
std::copy(inner->slotkey + mid+1, inner->slotkey + inner->slotuse, | |
newinner->slotkey); | |
std::copy(inner->childid + mid+1, inner->childid + inner->slotuse+1, | |
newinner->childid); | |
inner->slotuse = mid; | |
*_newkey = inner->slotkey[mid]; | |
*_newinner = newinner; | |
} | |
public: | |
// *** Bulk Loader - Construct Tree from Sorted Sequence | |
/// Bulk load a sorted range. Loads items into leaves and constructs a | |
/// B-tree above them. The tree must be empty when calling this function. | |
template <typename Iterator> | |
void bulk_load(Iterator ibegin, Iterator iend) | |
{ | |
BTREE_ASSERT(empty()); | |
m_stats.itemcount = iend - ibegin; | |
// calculate number of leaves needed, round up. | |
size_t num_items = iend - ibegin; | |
size_t num_leaves = (num_items + leafslotmax-1) / leafslotmax; | |
BTREE_PRINT("btree::bulk_load, level 0: " << m_stats.itemcount << " items into " << num_leaves << " leaves with up to " << ((iend - ibegin + num_leaves-1) / num_leaves) << " items per leaf."); | |
Iterator it = ibegin; | |
for (size_t i = 0; i < num_leaves; ++i) | |
{ | |
// allocate new leaf node | |
leaf_node* leaf = allocate_leaf(); | |
// copy keys or (key,value) pairs into leaf nodes, uses template | |
// switch leaf->set_slot(). | |
leaf->slotuse = static_cast<int>(num_items / (num_leaves-i)); | |
for (size_t s = 0; s < leaf->slotuse; ++s, ++it) | |
leaf->set_slot(s, *it); | |
if (m_tailleaf != NULL) { | |
m_tailleaf->nextleaf = leaf; | |
leaf->prevleaf = m_tailleaf; | |
} | |
else { | |
m_headleaf = leaf; | |
} | |
m_tailleaf = leaf; | |
num_items -= leaf->slotuse; | |
} | |
BTREE_ASSERT( it == iend && num_items == 0 ); | |
// if the btree is so small to fit into one leaf, then we're done. | |
if (m_headleaf == m_tailleaf) { | |
m_root = m_headleaf; | |
return; | |
} | |
BTREE_ASSERT( m_stats.leaves == num_leaves ); | |
// create first level of inner nodes, pointing to the leaves. | |
size_t num_parents = (num_leaves + (innerslotmax+1)-1) / (innerslotmax+1); | |
BTREE_PRINT("btree::bulk_load, level 1: " << num_leaves << " leaves in " << num_parents << " inner nodes with up to " << ((num_leaves + num_parents-1) / num_parents) << " leaves per inner node."); | |
// save inner nodes and maxkey for next level. | |
typedef std::pair<inner_node*, const key_type*> nextlevel_type; | |
nextlevel_type* nextlevel = new nextlevel_type[num_parents]; | |
leaf_node* leaf = m_headleaf; | |
for (size_t i = 0; i < num_parents; ++i) | |
{ | |
// allocate new inner node at level 1 | |
inner_node* n = allocate_inner(1); | |
n->slotuse = static_cast<int>(num_leaves / (num_parents-i)); | |
BTREE_ASSERT(n->slotuse > 0); | |
--n->slotuse; // this counts keys, but an inner node has keys+1 children. | |
// copy last key from each leaf and set child | |
for (unsigned short s = 0; s < n->slotuse; ++s) | |
{ | |
n->slotkey[s] = leaf->slotkey[leaf->slotuse-1]; | |
n->childid[s] = leaf; | |
leaf = leaf->nextleaf; | |
} | |
n->childid[n->slotuse] = leaf; | |
// track max key of any descendant. | |
nextlevel[i].first = n; | |
nextlevel[i].second = &leaf->slotkey[leaf->slotuse-1]; | |
leaf = leaf->nextleaf; | |
num_leaves -= n->slotuse+1; | |
} | |
BTREE_ASSERT( leaf == NULL && num_leaves == 0 ); | |
// recursively build inner nodes pointing to inner nodes. | |
for (int level = 2; num_parents != 1; ++level) | |
{ | |
size_t num_children = num_parents; | |
num_parents = (num_children + (innerslotmax+1)-1) / (innerslotmax+1); | |
BTREE_PRINT("btree::bulk_load, level " << level << ": " << num_children << " children in " << num_parents << " inner nodes with up to " << ((num_children + num_parents-1) / num_parents) << " children per inner node."); | |
size_t inner_index = 0; | |
for (size_t i = 0; i < num_parents; ++i) | |
{ | |
// allocate new inner node at level | |
inner_node* n = allocate_inner(level); | |
n->slotuse = static_cast<int>(num_children / (num_parents-i)); | |
BTREE_ASSERT(n->slotuse > 0); | |
--n->slotuse; // this counts keys, but an inner node has keys+1 children. | |
// copy children and maxkeys from nextlevel | |
for (unsigned short s = 0; s < n->slotuse; ++s) | |
{ | |
n->slotkey[s] = *nextlevel[inner_index].second; | |
n->childid[s] = nextlevel[inner_index].first; | |
++inner_index; | |
} | |
n->childid[n->slotuse] = nextlevel[inner_index].first; | |
// reuse nextlevel array for parents, because we can overwrite | |
// slots we've already consumed. | |
nextlevel[i].first = n; | |
nextlevel[i].second = nextlevel[inner_index].second; | |
++inner_index; | |
num_children -= n->slotuse+1; | |
} | |
BTREE_ASSERT( num_children == 0 ); | |
} | |
m_root = nextlevel[0].first; | |
delete [] nextlevel; | |
if (selfverify) verify(); | |
} | |
private: | |
// *** Support Class Encapsulating Deletion Results | |
/// Result flags of recursive deletion. | |
enum result_flags_t | |
{ | |
/// Deletion successful and no fix-ups necessary. | |
btree_ok = 0, | |
/// Deletion not successful because key was not found. | |
btree_not_found = 1, | |
/// Deletion successful, the last key was updated so parent slotkeys | |
/// need updates. | |
btree_update_lastkey = 2, | |
/// Deletion successful, children nodes were merged and the parent | |
/// needs to remove the empty node. | |
btree_fixmerge = 4 | |
}; | |
/// B+ tree recursive deletion has much information which is needs to be | |
/// passed upward. | |
struct result_t | |
{ | |
/// Merged result flags | |
result_flags_t flags; | |
/// The key to be updated at the parent's slot | |
key_type lastkey; | |
/// Constructor of a result with a specific flag, this can also be used | |
/// as for implicit conversion. | |
inline result_t(result_flags_t f = btree_ok) | |
: flags(f), lastkey() | |
{ } | |
/// Constructor with a lastkey value. | |
inline result_t(result_flags_t f, const key_type &k) | |
: flags(f), lastkey(k) | |
{ } | |
/// Test if this result object has a given flag set. | |
inline bool has(result_flags_t f) const | |
{ | |
return (flags & f) != 0; | |
} | |
/// Merge two results OR-ing the result flags and overwriting lastkeys. | |
inline result_t& operator|= (const result_t &other) | |
{ | |
flags = result_flags_t(flags | other.flags); | |
// we overwrite existing lastkeys on purpose | |
if (other.has(btree_update_lastkey)) | |
lastkey = other.lastkey; | |
return *this; | |
} | |
}; | |
public: | |
// *** Public Erase Functions | |
/// Erases one (the first) of the key/data pairs associated with the given | |
/// key. | |
bool erase_one(const key_type &key) | |
{ | |
BTREE_PRINT("btree::erase_one(" << key << ") on btree size " << size()); | |
if (selfverify) verify(); | |
if (!m_root) return false; | |
result_t result = erase_one_descend(key, m_root, NULL, NULL, NULL, NULL, NULL, 0); | |
if (!result.has(btree_not_found)) | |
--m_stats.itemcount; | |
#ifdef BTREE_DEBUG | |
if (debug) print(std::cout); | |
#endif | |
if (selfverify) verify(); | |
return !result.has(btree_not_found); | |
} | |
/// Erases all the key/data pairs associated with the given key. This is | |
/// implemented using erase_one(). | |
size_type erase(const key_type &key) | |
{ | |
size_type c = 0; | |
while( erase_one(key) ) | |
{ | |
++c; | |
if (!allow_duplicates) break; | |
} | |
return c; | |
} | |
/// Erase the key/data pair referenced by the iterator. | |
void erase(iterator iter) | |
{ | |
BTREE_PRINT("btree::erase_iter(" << iter.currnode << "," << iter.currslot << ") on btree size " << size()); | |
if (selfverify) verify(); | |
if (!m_root) return; | |
result_t result = erase_iter_descend(iter, m_root, NULL, NULL, NULL, NULL, NULL, 0); | |
if (!result.has(btree_not_found)) | |
--m_stats.itemcount; | |
#ifdef BTREE_DEBUG | |
if (debug) print(std::cout); | |
#endif | |
if (selfverify) verify(); | |
} | |
#ifdef BTREE_TODO | |
/// Erase all key/data pairs in the range [first,last). This function is | |
/// currently not implemented by the B+ Tree. | |
void erase(iterator /* first */, iterator /* last */) | |
{ | |
abort(); | |
} | |
#endif | |
private: | |
// *** Private Erase Functions | |
/** @brief Erase one (the first) key/data pair in the B+ tree matching key. | |
* | |
* Descends down the tree in search of key. During the descent the parent, | |
* left and right siblings and their parents are computed and passed | |
* down. Once the key/data pair is found, it is removed from the leaf. If | |
* the leaf underflows 6 different cases are handled. These cases resolve | |
* the underflow by shifting key/data pairs from adjacent sibling nodes, | |
* merging two sibling nodes or trimming the tree. | |
*/ | |
result_t erase_one_descend(const key_type& key, | |
node *curr, | |
node *left, node *right, | |
inner_node *leftparent, inner_node *rightparent, | |
inner_node *parent, unsigned int parentslot) | |
{ | |
if (curr->isleafnode()) | |
{ | |
leaf_node *leaf = static_cast<leaf_node*>(curr); | |
leaf_node *leftleaf = static_cast<leaf_node*>(left); | |
leaf_node *rightleaf = static_cast<leaf_node*>(right); | |
int slot = find_lower(leaf, key); | |
if (slot >= leaf->slotuse || !key_equal(key, leaf->slotkey[slot])) | |
{ | |
BTREE_PRINT("Could not find key " << key << " to erase."); | |
return btree_not_found; | |
} | |
BTREE_PRINT("Found key in leaf " << curr << " at slot " << slot); | |
std::copy(leaf->slotkey + slot+1, leaf->slotkey + leaf->slotuse, | |
leaf->slotkey + slot); | |
data_copy(leaf->slotdata + slot+1, leaf->slotdata + leaf->slotuse, | |
leaf->slotdata + slot); | |
leaf->slotuse--; | |
result_t myres = btree_ok; | |
// if the last key of the leaf was changed, the parent is notified | |
// and updates the key of this leaf | |
if (slot == leaf->slotuse) | |
{ | |
if (parent && parentslot < parent->slotuse) | |
{ | |
BTREE_ASSERT(parent->childid[parentslot] == curr); | |
parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1]; | |
} | |
else | |
{ | |
if (leaf->slotuse >= 1) | |
{ | |
BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1]); | |
myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]); | |
} | |
else | |
{ | |
BTREE_ASSERT(leaf == m_root); | |
} | |
} | |
} | |
if (leaf->isunderflow() && !(leaf == m_root && leaf->slotuse >= 1)) | |
{ | |
// determine what to do about the underflow | |
// case : if this empty leaf is the root, then delete all nodes | |
// and set root to NULL. | |
if (leftleaf == NULL && rightleaf == NULL) | |
{ | |
BTREE_ASSERT(leaf == m_root); | |
BTREE_ASSERT(leaf->slotuse == 0); | |
free_node(m_root); | |
m_root = leaf = NULL; | |
m_headleaf = m_tailleaf = NULL; | |
// will be decremented soon by insert_start() | |
BTREE_ASSERT(m_stats.itemcount == 1); | |
BTREE_ASSERT(m_stats.leaves == 0); | |
BTREE_ASSERT(m_stats.innernodes == 0); | |
return btree_ok; | |
} | |
// case : if both left and right leaves would underflow in case of | |
// a shift, then merging is necessary. choose the more local merger | |
// with our parent | |
else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) ) | |
{ | |
if (leftparent == parent) | |
myres |= merge_leaves(leftleaf, leaf, leftparent); | |
else | |
myres |= merge_leaves(leaf, rightleaf, rightparent); | |
} | |
// case : the right leaf has extra data, so balance right with current | |
else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) ) | |
{ | |
if (rightparent == parent) | |
myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot); | |
else | |
myres |= merge_leaves(leftleaf, leaf, leftparent); | |
} | |
// case : the left leaf has extra data, so balance left with current | |
else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) ) | |
{ | |
if (leftparent == parent) | |
shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1); | |
else | |
myres |= merge_leaves(leaf, rightleaf, rightparent); | |
} | |
// case : both the leaf and right leaves have extra data and our | |
// parent, choose the leaf with more data | |
else if (leftparent == rightparent) | |
{ | |
if (leftleaf->slotuse <= rightleaf->slotuse) | |
myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot); | |
else | |
shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1); | |
} | |
else | |
{ | |
if (leftparent == parent) | |
shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1); | |
else | |
myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot); | |
} | |
} | |
return myres; | |
} | |
else // !curr->isleafnode() | |
{ | |
inner_node *inner = static_cast<inner_node*>(curr); | |
inner_node *leftinner = static_cast<inner_node*>(left); | |
inner_node *rightinner = static_cast<inner_node*>(right); | |
node *myleft, *myright; | |
inner_node *myleftparent, *myrightparent; | |
int slot = find_lower(inner, key); | |
if (slot == 0) { | |
myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1]; | |
myleftparent = leftparent; | |
} | |
else { | |
myleft = inner->childid[slot - 1]; | |
myleftparent = inner; | |
} | |
if (slot == inner->slotuse) { | |
myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0]; | |
myrightparent = rightparent; | |
} | |
else { | |
myright = inner->childid[slot + 1]; | |
myrightparent = inner; | |
} | |
BTREE_PRINT("erase_one_descend into " << inner->childid[slot]); | |
result_t result = erase_one_descend(key, | |
inner->childid[slot], | |
myleft, myright, | |
myleftparent, myrightparent, | |
inner, slot); | |
result_t myres = btree_ok; | |
if (result.has(btree_not_found)) | |
{ | |
return result; | |
} | |
if (result.has(btree_update_lastkey)) | |
{ | |
if (parent && parentslot < parent->slotuse) | |
{ | |
BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot); | |
BTREE_ASSERT(parent->childid[parentslot] == curr); | |
parent->slotkey[parentslot] = result.lastkey; | |
} | |
else | |
{ | |
BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey); | |
myres |= result_t(btree_update_lastkey, result.lastkey); | |
} | |
} | |
if (result.has(btree_fixmerge)) | |
{ | |
// either the current node or the next is empty and should be removed | |
if (inner->childid[slot]->slotuse != 0) | |
slot++; | |
// this is the child slot invalidated by the merge | |
BTREE_ASSERT(inner->childid[slot]->slotuse == 0); | |
free_node(inner->childid[slot]); | |
std::copy(inner->slotkey + slot, inner->slotkey + inner->slotuse, | |
inner->slotkey + slot-1); | |
std::copy(inner->childid + slot+1, inner->childid + inner->slotuse+1, | |
inner->childid + slot); | |
inner->slotuse--; | |
if (inner->level == 1) | |
{ | |
// fix split key for children leaves | |
slot--; | |
leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]); | |
inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ]; | |
} | |
} | |
if (inner->isunderflow() && !(inner == m_root && inner->slotuse >= 1)) | |
{ | |
// case: the inner node is the root and has just one child. that child becomes the new root | |
if (leftinner == NULL && rightinner == NULL) | |
{ | |
BTREE_ASSERT(inner == m_root); | |
BTREE_ASSERT(inner->slotuse == 0); | |
m_root = inner->childid[0]; | |
inner->slotuse = 0; | |
free_node(inner); | |
return btree_ok; | |
} | |
// case : if both left and right leaves would underflow in case of | |
// a shift, then merging is necessary. choose the more local merger | |
// with our parent | |
else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) ) | |
{ | |
if (leftparent == parent) | |
myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1); | |
else | |
myres |= merge_inner(inner, rightinner, rightparent, parentslot); | |
} | |
// case : the right leaf has extra data, so balance right with current | |
else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) ) | |
{ | |
if (rightparent == parent) | |
shift_left_inner(inner, rightinner, rightparent, parentslot); | |
else | |
myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1); | |
} | |
// case : the left leaf has extra data, so balance left with current | |
else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) ) | |
{ | |
if (leftparent == parent) | |
shift_right_inner(leftinner, inner, leftparent, parentslot - 1); | |
else | |
myres |= merge_inner(inner, rightinner, rightparent, parentslot); | |
} | |
// case : both the leaf and right leaves have extra data and our | |
// parent, choose the leaf with more data | |
else if (leftparent == rightparent) | |
{ | |
if (leftinner->slotuse <= rightinner->slotuse) | |
shift_left_inner(inner, rightinner, rightparent, parentslot); | |
else | |
shift_right_inner(leftinner, inner, leftparent, parentslot - 1); | |
} | |
else | |
{ | |
if (leftparent == parent) | |
shift_right_inner(leftinner, inner, leftparent, parentslot - 1); | |
else | |
shift_left_inner(inner, rightinner, rightparent, parentslot); | |
} | |
} | |
return myres; | |
} | |
} | |
/** @brief Erase one key/data pair referenced by an iterator in the B+ | |
* tree. | |
* | |
* Descends down the tree in search of an iterator. During the descent the | |
* parent, left and right siblings and their parents are computed and | |
* passed down. The difficulty is that the iterator contains only a pointer | |
* to a leaf_node, which means that this function must do a recursive depth | |
* first search for that leaf node in the subtree containing all pairs of | |
* the same key. This subtree can be very large, even the whole tree, | |
* though in practice it would not make sense to have so many duplicate | |
* keys. | |
* | |
* Once the referenced key/data pair is found, it is removed from the leaf | |
* and the same underflow cases are handled as in erase_one_descend. | |
*/ | |
result_t erase_iter_descend(const iterator& iter, | |
node *curr, | |
node *left, node *right, | |
inner_node *leftparent, inner_node *rightparent, | |
inner_node *parent, unsigned int parentslot) | |
{ | |
if (curr->isleafnode()) | |
{ | |
leaf_node *leaf = static_cast<leaf_node*>(curr); | |
leaf_node *leftleaf = static_cast<leaf_node*>(left); | |
leaf_node *rightleaf = static_cast<leaf_node*>(right); | |
// if this is not the correct leaf, get next step in recursive | |
// search | |
if (leaf != iter.currnode) | |
{ | |
return btree_not_found; | |
} | |
if (iter.currslot >= leaf->slotuse) | |
{ | |
BTREE_PRINT("Could not find iterator (" << iter.currnode << "," << iter.currslot << ") to erase. Invalid leaf node?"); | |
return btree_not_found; | |
} | |
int slot = iter.currslot; | |
BTREE_PRINT("Found iterator in leaf " << curr << " at slot " << slot); | |
std::copy(leaf->slotkey + slot+1, leaf->slotkey + leaf->slotuse, | |
leaf->slotkey + slot); | |
data_copy(leaf->slotdata + slot+1, leaf->slotdata + leaf->slotuse, | |
leaf->slotdata + slot); | |
leaf->slotuse--; | |
result_t myres = btree_ok; | |
// if the last key of the leaf was changed, the parent is notified | |
// and updates the key of this leaf | |
if (slot == leaf->slotuse) | |
{ | |
if (parent && parentslot < parent->slotuse) | |
{ | |
BTREE_ASSERT(parent->childid[parentslot] == curr); | |
parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1]; | |
} | |
else | |
{ | |
if (leaf->slotuse >= 1) | |
{ | |
BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1]); | |
myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]); | |
} | |
else | |
{ | |
BTREE_ASSERT(leaf == m_root); | |
} | |
} | |
} | |
if (leaf->isunderflow() && !(leaf == m_root && leaf->slotuse >= 1)) | |
{ | |
// determine what to do about the underflow | |
// case : if this empty leaf is the root, then delete all nodes | |
// and set root to NULL. | |
if (leftleaf == NULL && rightleaf == NULL) | |
{ | |
BTREE_ASSERT(leaf == m_root); | |
BTREE_ASSERT(leaf->slotuse == 0); | |
free_node(m_root); | |
m_root = leaf = NULL; | |
m_headleaf = m_tailleaf = NULL; | |
// will be decremented soon by insert_start() | |
BTREE_ASSERT(m_stats.itemcount == 1); | |
BTREE_ASSERT(m_stats.leaves == 0); | |
BTREE_ASSERT(m_stats.innernodes == 0); | |
return btree_ok; | |
} | |
// case : if both left and right leaves would underflow in case of | |
// a shift, then merging is necessary. choose the more local merger | |
// with our parent | |
else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) ) | |
{ | |
if (leftparent == parent) | |
myres |= merge_leaves(leftleaf, leaf, leftparent); | |
else | |
myres |= merge_leaves(leaf, rightleaf, rightparent); | |
} | |
// case : the right leaf has extra data, so balance right with current | |
else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) ) | |
{ | |
if (rightparent == parent) | |
myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot); | |
else | |
myres |= merge_leaves(leftleaf, leaf, leftparent); | |
} | |
// case : the left leaf has extra data, so balance left with current | |
else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) ) | |
{ | |
if (leftparent == parent) | |
shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1); | |
else | |
myres |= merge_leaves(leaf, rightleaf, rightparent); | |
} | |
// case : both the leaf and right leaves have extra data and our | |
// parent, choose the leaf with more data | |
else if (leftparent == rightparent) | |
{ | |
if (leftleaf->slotuse <= rightleaf->slotuse) | |
myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot); | |
else | |
shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1); | |
} | |
else | |
{ | |
if (leftparent == parent) | |
shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1); | |
else | |
myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot); | |
} | |
} | |
return myres; | |
} | |
else // !curr->isleafnode() | |
{ | |
inner_node *inner = static_cast<inner_node*>(curr); | |
inner_node *leftinner = static_cast<inner_node*>(left); | |
inner_node *rightinner = static_cast<inner_node*>(right); | |
// find first slot below which the searched iterator might be | |
// located. | |
result_t result; | |
int slot = find_lower(inner, iter.key()); | |
while (slot <= inner->slotuse) | |
{ | |
node *myleft, *myright; | |
inner_node *myleftparent, *myrightparent; | |
if (slot == 0) { | |
myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1]; | |
myleftparent = leftparent; | |
} | |
else { | |
myleft = inner->childid[slot - 1]; | |
myleftparent = inner; | |
} | |
if (slot == inner->slotuse) { | |
myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0]; | |
myrightparent = rightparent; | |
} | |
else { | |
myright = inner->childid[slot + 1]; | |
myrightparent = inner; | |
} | |
BTREE_PRINT("erase_iter_descend into " << inner->childid[slot]); | |
result = erase_iter_descend(iter, | |
inner->childid[slot], | |
myleft, myright, | |
myleftparent, myrightparent, | |
inner, slot); | |
if (!result.has(btree_not_found)) | |
break; | |
// continue recursive search for leaf on next slot | |
if (slot < inner->slotuse && key_less(inner->slotkey[slot],iter.key())) | |
return btree_not_found; | |
++slot; | |
} | |
if (slot > inner->slotuse) | |
return btree_not_found; | |
result_t myres = btree_ok; | |
if (result.has(btree_update_lastkey)) | |
{ | |
if (parent && parentslot < parent->slotuse) | |
{ | |
BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot); | |
BTREE_ASSERT(parent->childid[parentslot] == curr); | |
parent->slotkey[parentslot] = result.lastkey; | |
} | |
else | |
{ | |
BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey); | |
myres |= result_t(btree_update_lastkey, result.lastkey); | |
} | |
} | |
if (result.has(btree_fixmerge)) | |
{ | |
// either the current node or the next is empty and should be removed | |
if (inner->childid[slot]->slotuse != 0) | |
slot++; | |
// this is the child slot invalidated by the merge | |
BTREE_ASSERT(inner->childid[slot]->slotuse == 0); | |
free_node(inner->childid[slot]); | |
std::copy(inner->slotkey + slot, inner->slotkey + inner->slotuse, | |
inner->slotkey + slot-1); | |
std::copy(inner->childid + slot+1, inner->childid + inner->slotuse+1, | |
inner->childid + slot); | |
inner->slotuse--; | |
if (inner->level == 1) | |
{ | |
// fix split key for children leaves | |
slot--; | |
leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]); | |
inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ]; | |
} | |
} | |
if (inner->isunderflow() && !(inner == m_root && inner->slotuse >= 1)) | |
{ | |
// case: the inner node is the root and has just one | |
// child. that child becomes the new root | |
if (leftinner == NULL && rightinner == NULL) | |
{ | |
BTREE_ASSERT(inner == m_root); | |
BTREE_ASSERT(inner->slotuse == 0); | |
m_root = inner->childid[0]; | |
inner->slotuse = 0; | |
free_node(inner); | |
return btree_ok; | |
} | |
// case : if both left and right leaves would underflow in case of | |
// a shift, then merging is necessary. choose the more local merger | |
// with our parent | |
else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) ) | |
{ | |
if (leftparent == parent) | |
myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1); | |
else | |
myres |= merge_inner(inner, rightinner, rightparent, parentslot); | |
} | |
// case : the right leaf has extra data, so balance right with current | |
else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) ) | |
{ | |
if (rightparent == parent) | |
shift_left_inner(inner, rightinner, rightparent, parentslot); | |
else | |
myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1); | |
} | |
// case : the left leaf has extra data, so balance left with current | |
else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) ) | |
{ | |
if (leftparent == parent) | |
shift_right_inner(leftinner, inner, leftparent, parentslot - 1); | |
else | |
myres |= merge_inner(inner, rightinner, rightparent, parentslot); | |
} | |
// case : both the leaf and right leaves have extra data and our | |
// parent, choose the leaf with more data | |
else if (leftparent == rightparent) | |
{ | |
if (leftinner->slotuse <= rightinner->slotuse) | |
shift_left_inner(inner, rightinner, rightparent, parentslot); | |
else | |
shift_right_inner(leftinner, inner, leftparent, parentslot - 1); | |
} | |
else | |
{ | |
if (leftparent == parent) | |
shift_right_inner(leftinner, inner, leftparent, parentslot - 1); | |
else | |
shift_left_inner(inner, rightinner, rightparent, parentslot); | |
} | |
} | |
return myres; | |
} | |
} | |
/// Merge two leaf nodes. The function moves all key/data pairs from right | |
/// to left and sets right's slotuse to zero. The right slot is then | |
/// removed by the calling parent node. | |
result_t merge_leaves(leaf_node* left, leaf_node* right, inner_node* parent) | |
{ | |
BTREE_PRINT("Merge leaf nodes " << left << " and " << right << " with common parent " << parent << "."); | |
(void)parent; | |
BTREE_ASSERT(left->isleafnode() && right->isleafnode()); | |
BTREE_ASSERT(parent->level == 1); | |
BTREE_ASSERT(left->slotuse + right->slotuse < leafslotmax); | |
std::copy(right->slotkey, right->slotkey + right->slotuse, | |
left->slotkey + left->slotuse); | |
data_copy(right->slotdata, right->slotdata + right->slotuse, | |
left->slotdata + left->slotuse); | |
left->slotuse += right->slotuse; | |
left->nextleaf = right->nextleaf; | |
if (left->nextleaf) | |
left->nextleaf->prevleaf = left; | |
else | |
m_tailleaf = left; | |
right->slotuse = 0; | |
return btree_fixmerge; | |
} | |
/// Merge two inner nodes. The function moves all key/childid pairs from | |
/// right to left and sets right's slotuse to zero. The right slot is then | |
/// removed by the calling parent node. | |
static result_t merge_inner(inner_node* left, inner_node* right, inner_node* parent, unsigned int parentslot) | |
{ | |
BTREE_PRINT("Merge inner nodes " << left << " and " << right << " with common parent " << parent << "."); | |
BTREE_ASSERT(left->level == right->level); | |
BTREE_ASSERT(parent->level == left->level + 1); | |
BTREE_ASSERT(parent->childid[parentslot] == left); | |
BTREE_ASSERT(left->slotuse + right->slotuse < innerslotmax); | |
if (selfverify) | |
{ | |
// find the left node's slot in the parent's children | |
unsigned int leftslot = 0; | |
while(leftslot <= parent->slotuse && parent->childid[leftslot] != left) | |
++leftslot; | |
BTREE_ASSERT(leftslot < parent->slotuse); | |
BTREE_ASSERT(parent->childid[leftslot] == left); | |
BTREE_ASSERT(parent->childid[leftslot+1] == right); | |
BTREE_ASSERT(parentslot == leftslot); | |
} | |
// retrieve the decision key from parent | |
left->slotkey[left->slotuse] = parent->slotkey[parentslot]; | |
left->slotuse++; | |
// copy over keys and children from right | |
std::copy(right->slotkey, right->slotkey + right->slotuse, | |
left->slotkey + left->slotuse); | |
std::copy(right->childid, right->childid + right->slotuse+1, | |
left->childid + left->slotuse); | |
left->slotuse += right->slotuse; | |
right->slotuse = 0; | |
return btree_fixmerge; | |
} | |
/// Balance two leaf nodes. The function moves key/data pairs from right to | |
/// left so that both nodes are equally filled. The parent node is updated | |
/// if possible. | |
static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot) | |
{ | |
BTREE_ASSERT(left->isleafnode() && right->isleafnode()); | |
BTREE_ASSERT(parent->level == 1); | |
BTREE_ASSERT(left->nextleaf == right); | |
BTREE_ASSERT(left == right->prevleaf); | |
BTREE_ASSERT(left->slotuse < right->slotuse); | |
BTREE_ASSERT(parent->childid[parentslot] == left); | |
unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1; | |
BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "."); | |
BTREE_ASSERT(left->slotuse + shiftnum < leafslotmax); | |
// copy the first items from the right node to the last slot in the left node. | |
std::copy(right->slotkey, right->slotkey + shiftnum, | |
left->slotkey + left->slotuse); | |
data_copy(right->slotdata, right->slotdata + shiftnum, | |
left->slotdata + left->slotuse); | |
left->slotuse += shiftnum; | |
// shift all slots in the right node to the left | |
std::copy(right->slotkey + shiftnum, right->slotkey + right->slotuse, | |
right->slotkey); | |
data_copy(right->slotdata + shiftnum, right->slotdata + right->slotuse, | |
right->slotdata); | |
right->slotuse -= shiftnum; | |
// fixup parent | |
if (parentslot < parent->slotuse) { | |
parent->slotkey[parentslot] = left->slotkey[left->slotuse - 1]; | |
return btree_ok; | |
} | |
else { // the update is further up the tree | |
return result_t(btree_update_lastkey, left->slotkey[left->slotuse - 1]); | |
} | |
} | |
/// Balance two inner nodes. The function moves key/data pairs from right | |
/// to left so that both nodes are equally filled. The parent node is | |
/// updated if possible. | |
static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) | |
{ | |
BTREE_ASSERT(left->level == right->level); | |
BTREE_ASSERT(parent->level == left->level + 1); | |
BTREE_ASSERT(left->slotuse < right->slotuse); | |
BTREE_ASSERT(parent->childid[parentslot] == left); | |
unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1; | |
BTREE_PRINT("Shifting (inner) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "."); | |
BTREE_ASSERT(left->slotuse + shiftnum < innerslotmax); | |
if (selfverify) | |
{ | |
// find the left node's slot in the parent's children and compare to parentslot | |
unsigned int leftslot = 0; | |
while(leftslot <= parent->slotuse && parent->childid[leftslot] != left) | |
++leftslot; | |
BTREE_ASSERT(leftslot < parent->slotuse); | |
BTREE_ASSERT(parent->childid[leftslot] == left); | |
BTREE_ASSERT(parent->childid[leftslot+1] == right); | |
BTREE_ASSERT(leftslot == parentslot); | |
} | |
// copy the parent's decision slotkey and childid to the first new key on the left | |
left->slotkey[left->slotuse] = parent->slotkey[parentslot]; | |
left->slotuse++; | |
// copy the other items from the right node to the last slots in the left node. | |
std::copy(right->slotkey, right->slotkey + shiftnum-1, | |
left->slotkey + left->slotuse); | |
std::copy(right->childid, right->childid + shiftnum, | |
left->childid + left->slotuse); | |
left->slotuse += shiftnum - 1; | |
// fixup parent | |
parent->slotkey[parentslot] = right->slotkey[shiftnum - 1]; | |
// shift all slots in the right node | |
std::copy(right->slotkey + shiftnum, right->slotkey + right->slotuse, | |
right->slotkey); | |
std::copy(right->childid + shiftnum, right->childid + right->slotuse+1, | |
right->childid); | |
right->slotuse -= shiftnum; | |
} | |
/// Balance two leaf nodes. The function moves key/data pairs from left to | |
/// right so that both nodes are equally filled. The parent node is updated | |
/// if possible. | |
static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot) | |
{ | |
BTREE_ASSERT(left->isleafnode() && right->isleafnode()); | |
BTREE_ASSERT(parent->level == 1); | |
BTREE_ASSERT(left->nextleaf == right); | |
BTREE_ASSERT(left == right->prevleaf); | |
BTREE_ASSERT(parent->childid[parentslot] == left); | |
BTREE_ASSERT(left->slotuse > right->slotuse); | |
unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1; | |
BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "."); | |
if (selfverify) | |
{ | |
// find the left node's slot in the parent's children | |
unsigned int leftslot = 0; | |
while(leftslot <= parent->slotuse && parent->childid[leftslot] != left) | |
++leftslot; | |
BTREE_ASSERT(leftslot < parent->slotuse); | |
BTREE_ASSERT(parent->childid[leftslot] == left); | |
BTREE_ASSERT(parent->childid[leftslot+1] == right); | |
BTREE_ASSERT(leftslot == parentslot); | |
} | |
// shift all slots in the right node | |
BTREE_ASSERT(right->slotuse + shiftnum < leafslotmax); | |
std::copy_backward(right->slotkey, right->slotkey + right->slotuse, | |
right->slotkey + right->slotuse + shiftnum); | |
data_copy_backward(right->slotdata, right->slotdata + right->slotuse, | |
right->slotdata + right->slotuse + shiftnum); | |
right->slotuse += shiftnum; | |
// copy the last items from the left node to the first slot in the right node. | |
std::copy(left->slotkey + left->slotuse - shiftnum, left->slotkey + left->slotuse, | |
right->slotkey); | |
data_copy(left->slotdata + left->slotuse - shiftnum, left->slotdata + left->slotuse, | |
right->slotdata); | |
left->slotuse -= shiftnum; | |
parent->slotkey[parentslot] = left->slotkey[left->slotuse-1]; | |
} | |
/// Balance two inner nodes. The function moves key/data pairs from left to | |
/// right so that both nodes are equally filled. The parent node is updated | |
/// if possible. | |
static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) | |
{ | |
BTREE_ASSERT(left->level == right->level); | |
BTREE_ASSERT(parent->level == left->level + 1); | |
BTREE_ASSERT(left->slotuse > right->slotuse); | |
BTREE_ASSERT(parent->childid[parentslot] == left); | |
unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1; | |
BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "."); | |
if (selfverify) | |
{ | |
// find the left node's slot in the parent's children | |
unsigned int leftslot = 0; | |
while(leftslot <= parent->slotuse && parent->childid[leftslot] != left) | |
++leftslot; | |
BTREE_ASSERT(leftslot < parent->slotuse); | |
BTREE_ASSERT(parent->childid[leftslot] == left); | |
BTREE_ASSERT(parent->childid[leftslot+1] == right); | |
BTREE_ASSERT(leftslot == parentslot); | |
} | |
// shift all slots in the right node | |
BTREE_ASSERT(right->slotuse + shiftnum < innerslotmax); | |
std::copy_backward(right->slotkey, right->slotkey + right->slotuse, | |
right->slotkey + right->slotuse + shiftnum); | |
std::copy_backward(right->childid, right->childid + right->slotuse+1, | |
right->childid + right->slotuse+1 + shiftnum); | |
right->slotuse += shiftnum; | |
// copy the parent's decision slotkey and childid to the last new key on the right | |
right->slotkey[shiftnum - 1] = parent->slotkey[parentslot]; | |
// copy the remaining last items from the left node to the first slot in the right node. | |
std::copy(left->slotkey + left->slotuse - shiftnum+1, left->slotkey + left->slotuse, | |
right->slotkey); | |
std::copy(left->childid + left->slotuse - shiftnum+1, left->childid + left->slotuse+1, | |
right->childid); | |
// copy the first to-be-removed key from the left node to the parent's decision slot | |
parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum]; | |
left->slotuse -= shiftnum; | |
} | |
#ifdef BTREE_DEBUG | |
public: | |
// *** Debug Printing | |
/// Print out the B+ tree structure with keys onto the given ostream. This | |
/// function requires that the header is compiled with BTREE_DEBUG and that | |
/// key_type is printable via std::ostream. | |
void print(std::ostream &os) const | |
{ | |
if (m_root) { | |
print_node(os, m_root, 0, true); | |
} | |
} | |
/// Print out only the leaves via the double linked list. | |
void print_leaves(std::ostream &os) const | |
{ | |
os << "leaves:" << std::endl; | |
const leaf_node *n = m_headleaf; | |
while(n) | |
{ | |
os << " " << n << std::endl; | |
n = n->nextleaf; | |
} | |
} | |
private: | |
/// Recursively descend down the tree and print out nodes. | |
static void print_node(std::ostream &os, const node* node, unsigned int depth=0, bool recursive=false) | |
{ | |
for(unsigned int i = 0; i < depth; i++) os << " "; | |
os << "node " << node << " level " << node->level << " slotuse " << node->slotuse << std::endl; | |
if (node->isleafnode()) | |
{ | |
const leaf_node *leafnode = static_cast<const leaf_node*>(node); | |
for(unsigned int i = 0; i < depth; i++) os << " "; | |
os << " leaf prev " << leafnode->prevleaf << " next " << leafnode->nextleaf << std::endl; | |
for(unsigned int i = 0; i < depth; i++) os << " "; | |
for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot) | |
{ | |
os << leafnode->slotkey[slot] << " "; // << "(data: " << leafnode->slotdata[slot] << ") "; | |
} | |
os << std::endl; | |
} | |
else | |
{ | |
const inner_node *innernode = static_cast<const inner_node*>(node); | |
for(unsigned int i = 0; i < depth; i++) os << " "; | |
for (unsigned short slot = 0; slot < innernode->slotuse; ++slot) | |
{ | |
os << "(" << innernode->childid[slot] << ") " << innernode->slotkey[slot] << " "; | |
} | |
os << "(" << innernode->childid[innernode->slotuse] << ")" << std::endl; | |
if (recursive) | |
{ | |
for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot) | |
{ | |
print_node(os, innernode->childid[slot], depth + 1, recursive); | |
} | |
} | |
} | |
} | |
#endif | |
public: | |
// *** Verification of B+ Tree Invariants | |
/// Run a thorough verification of all B+ tree invariants. The program | |
/// aborts via assert() if something is wrong. | |
void verify() const | |
{ | |
key_type minkey, maxkey; | |
tree_stats vstats; | |
if (m_root) | |
{ | |
verify_node(m_root, &minkey, &maxkey, vstats); | |
assert( vstats.itemcount == m_stats.itemcount ); | |
assert( vstats.leaves == m_stats.leaves ); | |
assert( vstats.innernodes == m_stats.innernodes ); | |
verify_leaflinks(); | |
} | |
} | |
private: | |
/// Recursively descend down the tree and verify each node | |
void verify_node(const node* n, key_type* minkey, key_type* maxkey, tree_stats &vstats) const | |
{ | |
BTREE_PRINT("verifynode " << n); | |
if (n->isleafnode()) | |
{ | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
assert( leaf == m_root || !leaf->isunderflow() ); | |
assert( leaf->slotuse > 0 ); | |
for(unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot) | |
{ | |
assert(key_lessequal(leaf->slotkey[slot], leaf->slotkey[slot + 1])); | |
} | |
*minkey = leaf->slotkey[0]; | |
*maxkey = leaf->slotkey[leaf->slotuse - 1]; | |
vstats.leaves++; | |
vstats.itemcount += leaf->slotuse; | |
} | |
else // !n->isleafnode() | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
vstats.innernodes++; | |
assert( inner == m_root || !inner->isunderflow() ); | |
assert( inner->slotuse > 0 ); | |
for(unsigned short slot = 0; slot < inner->slotuse - 1; ++slot) | |
{ | |
assert(key_lessequal(inner->slotkey[slot], inner->slotkey[slot + 1])); | |
} | |
for(unsigned short slot = 0; slot <= inner->slotuse; ++slot) | |
{ | |
const node *subnode = inner->childid[slot]; | |
key_type subminkey = key_type(); | |
key_type submaxkey = key_type(); | |
assert(subnode->level + 1 == inner->level); | |
verify_node(subnode, &subminkey, &submaxkey, vstats); | |
BTREE_PRINT("verify subnode " << subnode << ": " << subminkey << " - " << submaxkey); | |
if (slot == 0) | |
*minkey = subminkey; | |
else | |
assert(key_greaterequal(subminkey, inner->slotkey[slot-1])); | |
if (slot == inner->slotuse) | |
*maxkey = submaxkey; | |
else | |
assert(key_equal(inner->slotkey[slot], submaxkey)); | |
if (inner->level == 1 && slot < inner->slotuse) | |
{ | |
// children are leaves and must be linked together in the | |
// correct order | |
const leaf_node *leafa = static_cast<const leaf_node*>(inner->childid[slot]); | |
const leaf_node *leafb = static_cast<const leaf_node*>(inner->childid[slot + 1]); | |
assert(leafa->nextleaf == leafb); | |
assert(leafa == leafb->prevleaf); | |
(void)leafa; (void)leafb; | |
} | |
if (inner->level == 2 && slot < inner->slotuse) | |
{ | |
// verify leaf links between the adjacent inner nodes | |
const inner_node *parenta = static_cast<const inner_node*>(inner->childid[slot]); | |
const inner_node *parentb = static_cast<const inner_node*>(inner->childid[slot+1]); | |
const leaf_node *leafa = static_cast<const leaf_node*>(parenta->childid[parenta->slotuse]); | |
const leaf_node *leafb = static_cast<const leaf_node*>(parentb->childid[0]); | |
assert(leafa->nextleaf == leafb); | |
assert(leafa == leafb->prevleaf); | |
(void)leafa; (void)leafb; | |
} | |
} | |
} | |
} | |
/// Verify the double linked list of leaves. | |
void verify_leaflinks() const | |
{ | |
const leaf_node *n = m_headleaf; | |
assert(n->level == 0); | |
assert(!n || n->prevleaf == NULL); | |
unsigned int testcount = 0; | |
while(n) | |
{ | |
assert(n->level == 0); | |
assert(n->slotuse > 0); | |
for(unsigned short slot = 0; slot < n->slotuse - 1; ++slot) | |
{ | |
assert(key_lessequal(n->slotkey[slot], n->slotkey[slot + 1])); | |
} | |
testcount += n->slotuse; | |
if (n->nextleaf) | |
{ | |
assert(key_lessequal(n->slotkey[n->slotuse-1], n->nextleaf->slotkey[0])); | |
assert(n == n->nextleaf->prevleaf); | |
} | |
else | |
{ | |
assert(m_tailleaf == n); | |
} | |
n = n->nextleaf; | |
} | |
assert(testcount == size()); | |
} | |
private: | |
// *** Dump and Restore of B+ Trees | |
/// A header for the binary image containing the base properties of the B+ | |
/// tree. These properties have to match the current template | |
/// instantiation. | |
struct dump_header | |
{ | |
/// "stx-btree", just to stop the restore() function from loading garbage | |
char signature[12]; | |
/// Currently 0 | |
unsigned short version; | |
/// sizeof(key_type) | |
unsigned short key_type_size; | |
/// sizeof(data_type) | |
unsigned short data_type_size; | |
/// Number of slots in the leaves | |
unsigned short leafslots; | |
/// Number of slots in the inner nodes | |
unsigned short innerslots; | |
/// Allow duplicates | |
bool allow_duplicates; | |
/// The item count of the tree | |
size_type itemcount; | |
/// Fill the struct with the current B+ tree's properties, itemcount is | |
/// not filled. | |
inline void fill() | |
{ | |
// don't want to include string.h just for this signature | |
signature[0] = 's'; signature[1] = 't'; signature[2] = 'x'; signature[3] = '-'; | |
signature[4] = 'b'; signature[5] = 't'; signature[6] = 'r'; signature[7] = 'e'; | |
signature[8] = 'e'; signature[9] = 0; signature[10] = 0; signature[11] = 0; | |
version = 0; | |
key_type_size = sizeof(typename btree_self::key_type); | |
data_type_size = sizeof(typename btree_self::data_type); | |
leafslots = btree_self::leafslotmax; | |
innerslots = btree_self::innerslotmax; | |
allow_duplicates = btree_self::allow_duplicates; | |
} | |
/// Returns true if the headers have the same vital properties | |
inline bool same(const struct dump_header &o) const | |
{ | |
return (signature[0] == 's' && signature[1] == 't' && signature[2] == 'x' && signature[3] == '-' && | |
signature[4] == 'b' && signature[5] == 't' && signature[6] == 'r' && signature[7] == 'e' && | |
signature[8] == 'e' && signature[9] == 0 && signature[10] == 0 && signature[11] == 0) | |
&& (version == o.version) | |
&& (key_type_size == o.key_type_size) | |
&& (data_type_size == o.data_type_size) | |
&& (leafslots == o.leafslots) | |
&& (innerslots == o.innerslots) | |
&& (allow_duplicates == o.allow_duplicates); | |
} | |
}; | |
public: | |
/// Dump the contents of the B+ tree out onto an ostream as a binary | |
/// image. The image contains memory pointers which will be fixed when the | |
/// image is restored. For this to work your key_type and data_type must be | |
/// integral types and contain no pointers or references. | |
void dump(std::ostream &os) const | |
{ | |
struct dump_header header; | |
header.fill(); | |
header.itemcount = size(); | |
os.write(reinterpret_cast<char*>(&header), sizeof(header)); | |
if (m_root) { | |
dump_node(os, m_root); | |
} | |
} | |
/// Restore a binary image of a dumped B+ tree from an istream. The B+ tree | |
/// pointers are fixed using the dump order. For dump and restore to work | |
/// your key_type and data_type must be integral types and contain no | |
/// pointers or references. Returns true if the restore was successful. | |
bool restore(std::istream &is) | |
{ | |
struct dump_header fileheader; | |
is.read(reinterpret_cast<char*>(&fileheader), sizeof(fileheader)); | |
if (!is.good()) return false; | |
struct dump_header myheader; | |
myheader.fill(); | |
myheader.itemcount = fileheader.itemcount; | |
if (!myheader.same(fileheader)) | |
{ | |
BTREE_PRINT("btree::restore: file header does not match instantiation signature."); | |
return false; | |
} | |
clear(); | |
if (fileheader.itemcount > 0) | |
{ | |
m_root = restore_node(is); | |
if (m_root == NULL) return false; | |
m_stats.itemcount = fileheader.itemcount; | |
} | |
#ifdef BTREE_DEBUG | |
if (debug) print(std::cout); | |
#endif | |
if (selfverify) verify(); | |
return true; | |
} | |
private: | |
/// Recursively descend down the tree and dump each node in a precise order | |
void dump_node(std::ostream &os, const node* n) const | |
{ | |
BTREE_PRINT("dump_node " << n << std::endl); | |
if (n->isleafnode()) | |
{ | |
const leaf_node *leaf = static_cast<const leaf_node*>(n); | |
os.write(reinterpret_cast<const char*>(leaf), sizeof(*leaf)); | |
} | |
else // !n->isleafnode() | |
{ | |
const inner_node *inner = static_cast<const inner_node*>(n); | |
os.write(reinterpret_cast<const char*>(inner), sizeof(*inner)); | |
for(unsigned short slot = 0; slot <= inner->slotuse; ++slot) | |
{ | |
const node *subnode = inner->childid[slot]; | |
dump_node(os, subnode); | |
} | |
} | |
} | |
/// Read the dump image and construct a tree from the node order in the | |
/// serialization. | |
node* restore_node(std::istream &is) | |
{ | |
union { | |
node top; | |
leaf_node leaf; | |
inner_node inner; | |
} nu; | |
// first read only the top of the node | |
is.read(reinterpret_cast<char*>(&nu.top), sizeof(nu.top)); | |
if (!is.good()) return NULL; | |
if (nu.top.isleafnode()) | |
{ | |
// read remaining data of leaf node | |
is.read(reinterpret_cast<char*>(&nu.leaf) + sizeof(nu.top), sizeof(nu.leaf) - sizeof(nu.top)); | |
if (!is.good()) return NULL; | |
leaf_node *newleaf = allocate_leaf(); | |
// copy over all data, the leaf nodes contain only their double linked list pointers | |
*newleaf = nu.leaf; | |
// reconstruct the linked list from the order in the file | |
if (m_headleaf == NULL) { | |
BTREE_ASSERT(newleaf->prevleaf == NULL); | |
m_headleaf = m_tailleaf = newleaf; | |
} | |
else { | |
newleaf->prevleaf = m_tailleaf; | |
m_tailleaf->nextleaf = newleaf; | |
m_tailleaf = newleaf; | |
} | |
return newleaf; | |
} | |
else | |
{ | |
// read remaining data of inner node | |
is.read(reinterpret_cast<char*>(&nu.inner) + sizeof(nu.top), sizeof(nu.inner) - sizeof(nu.top)); | |
if (!is.good()) return NULL; | |
inner_node *newinner = allocate_inner(0); | |
// copy over all data, the inner nodes contain only pointers to their children | |
*newinner = nu.inner; | |
for(unsigned short slot = 0; slot <= newinner->slotuse; ++slot) | |
{ | |
newinner->childid[slot] = restore_node(is); | |
} | |
return newinner; | |
} | |
} | |
}; | |
} // namespace stx | |
#endif // _STX_BTREE_H_ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment