11#ifndef TLX_CONTAINER_BTREE_HEADER
12#define TLX_CONTAINER_BTREE_HEADER
42#define TLX_BTREE_PRINT(x) \
43 do { if (debug) (std::cout << x << std::endl); } while (0)
46#define TLX_BTREE_ASSERT(x) \
47 do { assert(x); } while (0)
52#define TLX_BTREE_PRINT(x) do { } while (0)
55#define TLX_BTREE_ASSERT(x) do { } while (0)
60#define TLX_BTREE_MAX(a, b) ((a) < (b) ? (b) : (a))
62#ifndef TLX_BTREE_FRIENDS
66#define TLX_BTREE_FRIENDS friend class btree_friend
73template <
typename Key,
typename Value>
84 static const bool debug =
false;
118template <
typename Key,
typename Value,
120 typename Compare = std::less<Key>,
122 bool Duplicates =
false,
123 typename Allocator = std::allocator<Value> >
203 static const bool debug = traits::debug;
237 typedef typename std::allocator_traits<Allocator>::template rebind_alloc<InnerNode>
alloc_type;
275 typedef typename std::allocator_traits<Allocator>::template rebind_alloc<LeafNode>
alloc_type;
294 return key_of_value::get(
slotdata[s]);
327 class const_iterator;
328 class reverse_iterator;
329 class const_reverse_iterator;
1119 template <
class InputIterator>
1120 BTree(InputIterator first, InputIterator last,
1130 template <
class InputIterator>
1274 std::allocator_traits<typename LeafNode::alloc_type>::destroy(a, ln);
1275 std::allocator_traits<typename LeafNode::alloc_type>::deallocate(a, ln, 1);
1281 std::allocator_traits<typename InnerNode::alloc_type>::destroy(a, in);
1282 std::allocator_traits<typename InnerNode::alloc_type>::deallocate(a, in, 1);
1316 for (
unsigned short slot = 0; slot < leafnode->
slotuse; ++slot)
1325 for (
unsigned short slot = 0; slot < innernode->
slotuse + 1; ++slot)
1397 template <
typename node_type>
1399 if (
sizeof(*n) > traits::binsearch_threshold)
1401 if (n->slotuse == 0)
return 0;
1403 unsigned short lo = 0, hi = n->slotuse;
1407 unsigned short mid = (lo + hi) >> 1;
1418 " key " << key <<
" -> " << lo <<
" / " << hi);
1423 unsigned short i = 0;
1424 while (i < n->slotuse &&
key_less(n->key(i), key)) ++i;
1434 unsigned short lo = 0;
1435 while (lo < n->slotuse &&
key_less(n->key(lo), key)) ++lo;
1444 template <
typename node_type>
1446 if (
sizeof(*n) > traits::binsearch_threshold)
1448 if (n->slotuse == 0)
return 0;
1450 unsigned short lo = 0, hi = n->slotuse;
1454 unsigned short mid = (lo + hi) >> 1;
1465 " key " << key <<
" -> " << lo <<
" / " << hi);
1470 unsigned short i = 0;
1471 while (i < n->slotuse &&
key_lessequal(n->key(i), key)) ++i;
1481 unsigned short lo = 0;
1482 while (lo < n->slotuse &&
key_lessequal(n->key(lo), key)) ++lo;
1524 if (!n)
return false;
1529 unsigned short slot =
find_lower(inner, key);
1537 return (slot < leaf->slotuse &&
key_equal(key, leaf->
key(slot)));
1544 if (!n)
return end();
1549 unsigned short slot =
find_lower(inner, key);
1557 return (slot < leaf->slotuse &&
key_equal(key, leaf->
key(slot)))
1565 if (!n)
return end();
1570 unsigned short slot =
find_lower(inner, key);
1578 return (slot < leaf->slotuse &&
key_equal(key, leaf->
key(slot)))
1591 unsigned short slot =
find_lower(inner, key);
1601 while (leaf && slot < leaf->slotuse &&
key_equal(key, leaf->
key(slot)))
1618 if (!n)
return end();
1623 unsigned short slot =
find_lower(inner, key);
1638 if (!n)
return end();
1643 unsigned short slot =
find_lower(inner, key);
1658 if (!n)
return end();
1663 unsigned short slot =
find_upper(inner, key);
1678 if (!n)
return end();
1683 unsigned short slot =
find_upper(inner, key);
1696 return std::pair<iterator, iterator>(
1701 std::pair<const_iterator, const_iterator>
1703 return std::pair<const_iterator, const_iterator>(
1723 return !(*
this == other);
1729 return std::lexicographical_compare(
1735 return other < *
this;
1740 return !(other < *
this);
1745 return !(*
this < other);
1763 if (other.
size() != 0)
1829 for (
unsigned short slot = 0; slot <= inner->
slotuse; ++slot)
1859 template <
typename InputIterator>
1860 void insert(InputIterator first, InputIterator last) {
1861 InputIterator iter = first;
1862 while (iter != last)
1877 std::pair<iterator, bool>
1880 node* newchild =
nullptr;
1883 if (
root_ ==
nullptr) {
1887 std::pair<iterator, bool> r =
1899 newroot->
childid[1] = newchild;
1909#ifdef TLX_BTREE_DEBUG
1910 if (
debug) print(std::cout);
1937 node* newchild =
nullptr;
1939 unsigned short slot =
find_lower(inner, key);
1942 "BTree::insert_descend into " << inner->
childid[slot]);
1944 std::pair<iterator, bool> r =
1946 key, value, &newkey, &newchild);
1951 " with key " << newkey <<
1952 " node " << newchild <<
" at slot " << slot);
1959 " putslot: " << slot <<
1960 " putkey: " << newkey <<
1961 " upkey: " << *splitkey);
1963#ifdef TLX_BTREE_DEBUG
1966 print_node(std::cout, inner);
1967 print_node(std::cout, *splitnode);
1973 << slot <<
" > " << inner->
slotuse + 1);
1975 if (slot == inner->
slotuse + 1 &&
1976 inner->
slotuse < (*splitnode)->slotuse)
1993 split->childid[0] = newchild;
1998 else if (slot >= inner->
slotuse + 1)
2004 inner =
static_cast<InnerNode*
>(*splitnode);
2006 "BTree::insert_descend switching to "
2007 "splitted node " << inner <<
" slot " << slot);
2021 inner->
slotkey[slot] = newkey;
2022 inner->
childid[slot + 1] = newchild;
2035 slot < leaf->slotuse &&
key_equal(key, leaf->
key(slot))) {
2036 return std::pair<iterator, bool>(
iterator(leaf, slot),
false);
2047 leaf =
static_cast<LeafNode*
>(*splitnode);
2061 if (splitnode && leaf != *splitnode && slot == leaf->
slotuse - 1)
2068 return std::pair<iterator, bool>(
iterator(leaf, slot),
true);
2078 unsigned short mid = (leaf->
slotuse >> 1);
2103 *out_newleaf = newleaf;
2111 node** out_newinner,
unsigned int addslot) {
2114 unsigned short mid = (inner->
slotuse >> 1);
2117 " addslot " << addslot);
2121 if (addslot <= mid && mid > inner->
slotuse - (mid + 1))
2125 " addslot " << addslot);
2128 " into two nodes " << mid <<
" and " <<
2129 inner->
slotuse - (mid + 1) <<
" sized");
2142 *out_newkey = inner->
key(mid);
2143 *out_newinner = newinner;
2154 template <
typename Iterator>
2161 size_t num_items = iend - ibegin;
2165 " items into " << num_leaves <<
2166 " leaves with up to " <<
2167 ((iend - ibegin + num_leaves - 1) / num_leaves) <<
2168 " items per leaf.");
2170 Iterator it = ibegin;
2171 for (
size_t i = 0; i < num_leaves; ++i)
2178 leaf->
slotuse =
static_cast<int>(num_items / (num_leaves - i));
2179 for (
size_t s = 0; s < leaf->
slotuse; ++s, ++it)
2205 size_t num_parents =
2209 num_leaves <<
" leaves in " <<
2210 num_parents <<
" inner nodes with up to " <<
2211 ((num_leaves + num_parents - 1) / num_parents) <<
2212 " leaves per inner node.");
2215 typedef std::pair<InnerNode*, const key_type*> nextlevel_type;
2216 nextlevel_type* nextlevel =
new nextlevel_type[num_parents];
2219 for (
size_t i = 0; i < num_parents; ++i)
2224 n->
slotuse =
static_cast<int>(num_leaves / (num_parents - i));
2230 for (
unsigned short s = 0; s < n->
slotuse; ++s)
2239 nextlevel[i].first = n;
2240 nextlevel[i].second = &leaf->
key(leaf->
slotuse - 1);
2249 for (
int level = 2; num_parents != 1; ++level)
2251 size_t num_children = num_parents;
2256 "BTree::bulk_load, level " << level <<
2257 ": " << num_children <<
" children in " <<
2258 num_parents <<
" inner nodes with up to " <<
2259 ((num_children + num_parents - 1) / num_parents) <<
2260 " children per inner node.");
2262 size_t inner_index = 0;
2263 for (
size_t i = 0; i < num_parents; ++i)
2268 n->
slotuse =
static_cast<int>(num_children / (num_parents - i));
2274 for (
unsigned short s = 0; s < n->
slotuse; ++s)
2276 n->
slotkey[s] = *nextlevel[inner_index].second;
2277 n->
childid[s] = nextlevel[inner_index].first;
2284 nextlevel[i].first = n;
2285 nextlevel[i].second = nextlevel[inner_index].second;
2288 num_children -= n->
slotuse + 1;
2294 root_ = nextlevel[0].first;
2345 return (
flags & f) != 0;
2370 ") on btree size " <<
size());
2374 if (!
root_)
return false;
2377 key,
root_,
nullptr,
nullptr,
nullptr,
nullptr,
nullptr, 0);
2382#ifdef TLX_BTREE_DEBUG
2383 if (
debug) print(std::cout);
2414 iter,
root_,
nullptr,
nullptr,
nullptr,
nullptr,
nullptr, 0);
2419#ifdef TLX_BTREE_DEBUG
2420 if (
debug) print(std::cout);
2428 void erase(iterator , iterator ) {
2453 InnerNode* parent,
unsigned int parentslot) {
2470 "Found key in leaf " << curr <<
" at slot " << slot);
2483 if (parent && parentslot < parent->slotuse)
2510 if (left_leaf ==
nullptr && right_leaf ==
nullptr)
2517 root_ = leaf =
nullptr;
2530 else if ((left_leaf ==
nullptr || left_leaf->
is_few()) &&
2531 (right_leaf ==
nullptr || right_leaf->
is_few()))
2533 if (left_parent == parent)
2540 else if ((left_leaf !=
nullptr && left_leaf->
is_few()) &&
2541 (right_leaf !=
nullptr && !right_leaf->
is_few()))
2543 if (right_parent == parent)
2545 leaf, right_leaf, right_parent, parentslot);
2551 else if ((left_leaf !=
nullptr && !left_leaf->
is_few()) &&
2552 (right_leaf !=
nullptr && right_leaf->
is_few()))
2554 if (left_parent == parent)
2556 left_leaf, leaf, left_parent, parentslot - 1);
2562 else if (left_parent == right_parent)
2566 leaf, right_leaf, right_parent, parentslot);
2569 left_leaf, leaf, left_parent, parentslot - 1);
2573 if (left_parent == parent)
2575 left_leaf, leaf, left_parent, parentslot - 1);
2578 leaf, right_leaf, right_parent, parentslot);
2590 node* myleft, * myright;
2591 InnerNode* myleft_parent, * myright_parent;
2593 unsigned short slot =
find_lower(inner, key);
2597 (left ==
nullptr) ?
nullptr :
2599 myleft_parent = left_parent;
2602 myleft = inner->
childid[slot - 1];
2603 myleft_parent = inner;
2608 (right ==
nullptr) ?
nullptr :
2609 static_cast<InnerNode*
>(right)->childid[0];
2610 myright_parent = right_parent;
2613 myright = inner->
childid[slot + 1];
2614 myright_parent = inner;
2623 myleft_parent, myright_parent,
2635 if (parent && parentslot < parent->slotuse)
2638 result.
lastkey <<
" into parent " <<
2639 parent <<
" at parentslot " <<
2648 "Forwarding lastkeyupdate: key " << result.
lastkey);
2675 if (inner->
level == 1)
2690 if (left_inner ==
nullptr && right_inner ==
nullptr)
2705 else if ((left_inner ==
nullptr || left_inner->
is_few()) &&
2706 (right_inner ==
nullptr || right_inner->
is_few()))
2708 if (left_parent == parent)
2710 left_inner, inner, left_parent, parentslot - 1);
2713 inner, right_inner, right_parent, parentslot);
2717 else if ((left_inner !=
nullptr && left_inner->
is_few()) &&
2718 (right_inner !=
nullptr && !right_inner->
is_few()))
2720 if (right_parent == parent)
2722 inner, right_inner, right_parent, parentslot);
2725 left_inner, inner, left_parent, parentslot - 1);
2729 else if ((left_inner !=
nullptr && !left_inner->
is_few()) &&
2730 (right_inner !=
nullptr && right_inner->
is_few()))
2732 if (left_parent == parent)
2734 left_inner, inner, left_parent, parentslot - 1);
2737 inner, right_inner, right_parent, parentslot);
2741 else if (left_parent == right_parent)
2745 inner, right_inner, right_parent, parentslot);
2748 left_inner, inner, left_parent, parentslot - 1);
2752 if (left_parent == parent)
2754 left_inner, inner, left_parent, parentslot - 1);
2757 inner, right_inner, right_parent, parentslot);
2783 InnerNode* parent,
unsigned int parentslot) {
2801 ") to erase. Invalid leaf node?");
2809 curr <<
" at slot " << slot);
2822 if (parent && parentslot < parent->slotuse)
2849 if (left_leaf ==
nullptr && right_leaf ==
nullptr)
2856 root_ = leaf =
nullptr;
2869 else if ((left_leaf ==
nullptr || left_leaf->
is_few()) &&
2870 (right_leaf ==
nullptr || right_leaf->
is_few()))
2872 if (left_parent == parent)
2879 else if ((left_leaf !=
nullptr && left_leaf->
is_few()) &&
2880 (right_leaf !=
nullptr && !right_leaf->
is_few()))
2882 if (right_parent == parent) {
2884 leaf, right_leaf, right_parent, parentslot);
2892 else if ((left_leaf !=
nullptr && !left_leaf->
is_few()) &&
2893 (right_leaf !=
nullptr && right_leaf->
is_few()))
2895 if (left_parent == parent) {
2897 left_leaf, leaf, left_parent, parentslot - 1);
2905 else if (left_parent == right_parent)
2909 leaf, right_leaf, right_parent, parentslot);
2913 left_leaf, leaf, left_parent, parentslot - 1);
2918 if (left_parent == parent) {
2920 left_leaf, leaf, left_parent, parentslot - 1);
2924 leaf, right_leaf, right_parent, parentslot);
2943 while (slot <= inner->slotuse)
2945 node* myleft, * myright;
2946 InnerNode* myleft_parent, * myright_parent;
2949 myleft = (left ==
nullptr) ?
nullptr
2950 :
static_cast<InnerNode*
>(left)->childid[
2952 myleft_parent = left_parent;
2955 myleft = inner->
childid[slot - 1];
2956 myleft_parent = inner;
2960 myright = (right ==
nullptr) ?
nullptr
2961 :
static_cast<InnerNode*
>(right)->childid[0];
2962 myright_parent = right_parent;
2965 myright = inner->
childid[slot + 1];
2966 myright_parent = inner;
2975 myleft_parent, myright_parent,
2983 if (slot < inner->slotuse &&
2997 if (parent && parentslot < parent->slotuse)
3000 result.
lastkey <<
" into parent " <<
3001 parent <<
" at parentslot " << parentslot);
3009 "Forwarding lastkeyupdate: key " << result.
lastkey);
3036 if (inner->
level == 1)
3051 if (left_inner ==
nullptr && right_inner ==
nullptr)
3066 else if ((left_inner ==
nullptr || left_inner->
is_few()) &&
3067 (right_inner ==
nullptr || right_inner->
is_few()))
3069 if (left_parent == parent) {
3071 left_inner, inner, left_parent, parentslot - 1);
3075 inner, right_inner, right_parent, parentslot);
3080 else if ((left_inner !=
nullptr && left_inner->
is_few()) &&
3081 (right_inner !=
nullptr && !right_inner->
is_few()))
3083 if (right_parent == parent) {
3085 inner, right_inner, right_parent, parentslot);
3089 left_inner, inner, left_parent, parentslot - 1);
3094 else if ((left_inner !=
nullptr && !left_inner->
is_few()) &&
3095 (right_inner !=
nullptr && right_inner->
is_few()))
3097 if (left_parent == parent) {
3099 left_inner, inner, left_parent, parentslot - 1);
3103 inner, right_inner, right_parent, parentslot);
3108 else if (left_parent == right_parent)
3112 inner, right_inner, right_parent, parentslot);
3116 left_inner, inner, left_parent, parentslot - 1);
3121 if (left_parent == parent) {
3123 left_inner, inner, left_parent, parentslot - 1);
3127 inner, right_inner, right_parent, parentslot);
3142 " with common parent " << parent <<
".");
3170 InnerNode* parent,
unsigned int parentslot) {
3172 " with common parent " << parent <<
".");
3184 unsigned int leftslot = 0;
3185 while (leftslot <= parent->slotuse &&
3186 parent->
childid[leftslot] != left)
3217 InnerNode* parent,
unsigned int parentslot) {
3230 TLX_BTREE_PRINT(
"Shifting (leaf) " << shiftnum <<
" entries to left " <<
3231 left <<
" from right " << right <<
3232 " with common parent " << parent <<
".");
3252 if (parentslot < parent->slotuse) {
3265 InnerNode* parent,
unsigned int parentslot) {
3275 " entries to left " << left <<
3276 " from right " << right <<
3277 " with common parent " << parent <<
".");
3286 unsigned int leftslot = 0;
3287 while (leftslot <= parent->slotuse &&
3288 parent->
childid[leftslot] != left)
3310 left->
slotuse += shiftnum - 1;
3330 InnerNode* parent,
unsigned int parentslot) {
3343 " entries to right " << right <<
3344 " from left " << left <<
3345 " with common parent " << parent <<
".");
3350 unsigned int leftslot = 0;
3351 while (leftslot <= parent->slotuse &&
3352 parent->
childid[leftslot] != left)
3386 InnerNode* parent,
unsigned int parentslot) {
3396 " entries to right " << right <<
3397 " from left " << left <<
3398 " with common parent " << parent <<
".");
3403 unsigned int leftslot = 0;
3404 while (leftslot <= parent->slotuse &&
3405 parent->
childid[leftslot] != left)
3450#ifdef TLX_BTREE_DEBUG
3459 void print(std::ostream& os)
const {
3461 print_node(os,
root_, 0,
true);
3466 void print_leaves(std::ostream& os)
const {
3467 os <<
"leaves:" << std::endl;
3473 os <<
" " << n << std::endl;
3481 static void print_node(std::ostream& os,
const node* node,
3482 unsigned int depth = 0,
bool recursive =
false) {
3483 for (
unsigned int i = 0; i < depth; i++) os <<
" ";
3485 os <<
"node " << node <<
" level " << node->level <<
3486 " slotuse " << node->slotuse << std::endl;
3488 if (node->is_leafnode())
3490 const LeafNode* leafnode =
static_cast<const LeafNode*
>(node);
3492 for (
unsigned int i = 0; i < depth; i++) os <<
" ";
3493 os <<
" leaf prev " << leafnode->prev_leaf <<
3494 " next " << leafnode->next_leaf << std::endl;
3496 for (
unsigned int i = 0; i < depth; i++) os <<
" ";
3498 for (
unsigned short slot = 0; slot < leafnode->slotuse; ++slot)
3502 os << leafnode->key(slot) <<
" ";
3508 const InnerNode* innernode =
static_cast<const InnerNode*
>(node);
3510 for (
unsigned int i = 0; i < depth; i++) os <<
" ";
3512 for (
unsigned short slot = 0; slot < innernode->slotuse; ++slot)
3514 os <<
"(" << innernode->childid[slot] <<
") "
3515 << innernode->slotkey[slot] <<
" ";
3517 os <<
"(" << innernode->childid[innernode->slotuse] <<
")"
3522 for (
unsigned short slot = 0;
3523 slot < innernode->slotuse + 1; ++slot)
3526 os, innernode->childid[slot], depth + 1, recursive);
3570 for (
unsigned short slot = 0; slot < leaf->
slotuse - 1; ++slot)
3576 *minkey = leaf->
key(0);
3590 for (
unsigned short slot = 0; slot < inner->
slotuse - 1; ++slot)
3596 for (
unsigned short slot = 0; slot <= inner->
slotuse; ++slot)
3603 verify_node(subnode, &subminkey, &submaxkey, vstats);
3606 ": " << subminkey <<
3607 " - " << submaxkey);
3610 *minkey = subminkey;
3616 *maxkey = submaxkey;
3620 if (inner->
level == 1 && slot < inner->slotuse)
3632 if (inner->
level == 2 && slot < inner->slotuse)
3659 unsigned int testcount = 0;
3666 for (
unsigned short slot = 0; slot < n->
slotuse - 1; ++slot)
STL-like read-only iterator object for B+ tree items.
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
const value_type * pointer
Pointer to the value_type. STL required.
const_iterator self
Our own type.
const value_type & reference
Reference to the value_type. STL required.
const BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
BTree::key_type key_type
The key type of the btree. Returned by key().
const_iterator & operator++()
Prefix++ advance the iterator to the next slot.
ptrdiff_t difference_type
STL-magic.
reference operator*() const
Dereference the iterator.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
bool operator!=(const const_iterator &x) const
Inequality of iterators.
const_iterator()
Default-Constructor of a const iterator.
bool operator==(const const_iterator &x) const
Equality of iterators.
const_iterator(const const_reverse_iterator &it)
Copy-constructor from a const reverse iterator.
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
const key_type & key() const
Key of the current slot.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
unsigned short curr_slot
Current key/data slot referenced.
pointer operator->() const
Dereference the iterator.
const_iterator & operator--()
Prefix– backstep the iterator to the last slot.
const_iterator(const typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a const iterator.
STL-like read-only reverse iterator object for B+ tree items.
const value_type * pointer
Pointer to the value_type. STL required.
const value_type & reference
Reference to the value_type. STL required.
const BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
const_reverse_iterator & operator--()
Prefix– backstep the iterator to the next slot.
const_reverse_iterator & operator++()
Prefix++ advance the iterator to the previous slot.
const_reverse_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
const_reverse_iterator(const typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a const reverse iterator.
BTree::key_type key_type
The key type of the btree. Returned by key().
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
const_reverse_iterator self
Our own type.
ptrdiff_t difference_type
STL-magic.
bool operator==(const const_reverse_iterator &x) const
Equality of iterators.
reference operator*() const
Dereference the iterator.
const_reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
const key_type & key() const
Key of the current slot.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
unsigned short curr_slot
One slot past the current key/data slot referenced.
pointer operator->() const
Dereference the iterator.
bool operator!=(const const_reverse_iterator &x) const
Inequality of iterators.
STL-like iterator object for B+ tree items.
iterator(const reverse_iterator &it)
Copy-constructor from a reverse iterator.
value_type & reference
Reference to the value_type. STL required.
bool operator==(const iterator &x) const
Equality of iterators.
iterator self
Our own type.
bool operator!=(const iterator &x) const
Inequality of iterators.
BTree::key_type key_type
The key type of the btree. Returned by key().
iterator()
Default-Constructor of a mutable iterator.
iterator & operator--()
Prefix– backstep the iterator to the last slot.
ptrdiff_t difference_type
STL-magic.
value_type * pointer
Pointer to the value_type. STL required.
reference operator*() const
Dereference the iterator.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
iterator & operator++()
Prefix++ advance the iterator to the next slot.
BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
const key_type & key() const
Key of the current slot.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
unsigned short curr_slot
Current key/data slot referenced.
pointer operator->() const
Dereference the iterator.
iterator(typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a mutable iterator.
STL-like mutable reverse iterator object for B+ tree items.
value_type & reference
Reference to the value_type. STL required.
bool operator!=(const reverse_iterator &x) const
Inequality of iterators.
reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
reverse_iterator self
Our own type.
reverse_iterator & operator++()
Prefix++ advance the iterator to the next slot.
BTree::key_type key_type
The key type of the btree. Returned by key().
bool operator==(const reverse_iterator &x) const
Equality of iterators.
reverse_iterator(typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a mutable reverse iterator.
ptrdiff_t difference_type
STL-magic.
value_type * pointer
Pointer to the value_type. STL required.
reverse_iterator()
Default-Constructor of a reverse iterator.
reference operator*() const
Dereference the iterator.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
reverse_iterator & operator--()
Prefix– backstep the iterator to the last slot.
const key_type & key() const
Key of the current slot.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
unsigned short curr_slot
One slot past the current key/data slot referenced.
pointer operator->() const
Dereference the iterator.
Function class to compare value_type objects. Required by the STL.
value_compare(key_compare kc)
Constructor called from BTree::value_comp()
bool operator()(const value_type &x, const value_type &y) const
Function call "less"-operator resulting in true if x < y.
key_compare key_comp
Key comparison function from the template parameter.
Basic class implementing a B+ tree data structure in memory.
static const unsigned short inner_slotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
void clear_recursive(node *n)
Recursively free up nodes.
void verify_leaflinks() const
Verify the double linked list of leaves.
static result_t merge_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Merge two inner nodes.
const_reverse_iterator rend() const
Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tre...
void swap(BTree &from)
Fast swapping of two identical B+ tree objects.
std::pair< iterator, bool > insert_descend(node *n, const key_type &key, const value_type &value, key_type *splitkey, node **splitnode)
Insert an item into the B+ tree.
void split_leaf_node(LeafNode *leaf, key_type *out_newkey, node **out_newleaf)
Split up a leaf node into two equally-filled sibling leaves.
void free_node(node *n)
Correctly free either inner or leaf node, destructs all contained key and value objects.
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
bool operator>=(const BTree &other) const
Greater-equal relation. Based on operator<.
BTree & operator=(const BTree &other)
Assignment operator. All the key/data pairs are copied.
KeyOfValue key_of_value
Third template: key extractor class to pull key_type from value_type.
Allocator allocator_type
Seventh template parameter: STL allocator for tree nodes.
bool operator==(const BTree &other) const
Equality relation of B+ trees of the same type.
bool key_less(const key_type &a, const key_type &b) const
True if a < b ? "constructed" from key_less_()
size_t size_type
Size type used to count keys.
static void shift_left_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Balance two inner nodes.
BTree< key_type, value_type, key_of_value, key_compare, traits, allow_duplicates, allocator_type > Self
Typedef of our own type.
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
LeafNode::alloc_type leaf_node_allocator()
Return an allocator for LeafNode objects.
iterator lower_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair equal to or greater than key,...
result_flags_t
Result flags of recursive deletion.
@ btree_fixmerge
Deletion successful, children nodes were merged and the parent needs to remove the empty node.
@ btree_not_found
Deletion not successful because key was not found.
@ btree_update_lastkey
Deletion successful, the last key was updated so parent slotkeys need updates.
@ btree_ok
Deletion successful and no fix-ups necessary.
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
struct node * copy_recursive(const node *n)
Recursively copy nodes from another B+ tree object.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
static void shift_right_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Balance two inner nodes.
iterator insert(iterator, const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
const_iterator lower_bound(const key_type &key) const
Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key,...
iterator upper_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Searches the B+ tree and returns both lower_bound() and upper_bound().
Traits traits
Fifth template parameter: Traits object used to define more parameters of the B+ tree.
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Value value_type
Second template parameter: Composition pair of key and data types, or just the key for set containers...
LeafNode * allocate_leaf()
Allocate and initialize a leaf node.
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
result_t erase_iter_descend(const iterator &iter, node *curr, node *left, node *right, InnerNode *left_parent, InnerNode *right_parent, InnerNode *parent, unsigned int parentslot)
Erase one key/data pair referenced by an iterator in the B+ tree.
key_compare key_less_
Key comparison object.
size_type size() const
Return the number of key/data pairs in the B+ tree.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
BTree(const BTree &other)
Copy constructor.
size_type count(const key_type &key) const
Tries to locate a key in the B+ tree and returns the number of identical key entries found.
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
LeafNode * tail_leaf_
Pointer to last leaf in the double linked leaf chain.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
bool key_greaterequal(const key_type &a, const key_type &b) const
True if a >= b ? constructed from key_less()
BTree(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last).
allocator_type get_allocator() const
Return the base node allocator provided during construction.
BTree(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function.
unsigned short find_lower(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater or equal to key.
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
InnerNode::alloc_type inner_node_allocator()
Return an allocator for InnerNode objects.
static void shift_right_leaf(LeafNode *left, LeafNode *right, InnerNode *parent, unsigned int parentslot)
Balance two leaf nodes.
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
unsigned short find_upper(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater than key.
allocator_type allocator_
Memory allocator.
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
LeafNode * head_leaf_
Pointer to first leaf in the double linked leaf chain.
void verify() const
Run a thorough verification of all B+ tree invariants.
BTree(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
bool operator!=(const BTree &other) const
Inequality relation. Based on operator==.
iterator find(const key_type &key)
Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
result_t erase_one_descend(const key_type &key, node *curr, node *left, node *right, InnerNode *left_parent, InnerNode *right_parent, InnerNode *parent, unsigned int parentslot)
Erase one (the first) key/data pair in the B+ tree matching key.
bool operator>(const BTree &other) const
Greater relation. Based on operator<.
const_iterator upper_bound(const key_type &key) const
Searches the B+ tree and returns a constant iterator to the first pair greater than key,...
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
std::pair< iterator, bool > insert_start(const key_type &key, const value_type &value)
Start the insertion descent at the current root and handle root splits.
Key key_type
First template parameter: The key type of the B+ tree.
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ? constructed from key_less().
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
void verify_node(const node *n, key_type *minkey, key_type *maxkey, tree_stats &vstats) const
Recursively descend down the tree and verify each node.
void clear()
Frees all key/data pairs and all nodes of the tree.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Compare key_compare
Fourth template parameter: key_type comparison function object.
BTree(InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
static result_t shift_left_leaf(LeafNode *left, LeafNode *right, InnerNode *parent, unsigned int parentslot)
Balance two leaf nodes.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
bool key_lessequal(const key_type &a, const key_type &b) const
True if a <= b ? constructed from key_less()
result_t merge_leaves(LeafNode *left, LeafNode *right, InnerNode *parent)
Merge two leaf nodes.
InnerNode * allocate_inner(unsigned short level)
Allocate and initialize an inner node.
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
node * root_
Pointer to the B+ tree's root node, either leaf or inner node.
tree_stats stats_
Other small statistics about the B+ tree.
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
bool operator<=(const BTree &other) const
Less-equal relation. Based on operator<.
const_iterator find(const key_type &key) const
Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found.
~BTree()
Frees up all used B+ tree memory pages.
bool operator<(const BTree &other) const
Total ordering relation of B+ trees of the same type.
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
void split_inner_node(InnerNode *inner, key_type *out_newkey, node **out_newinner, unsigned int addslot)
Split up an inner node into two equally-filled sibling nodes.
#define tlx_die_unless(X)
Check condition X and die miserably if false.
#define TLX_BTREE_MAX(a, b)
The maximum of a and b. Used in some compile-time formulas.
#define TLX_BTREE_PRINT(x)
Print out debug information to std::cout if TLX_BTREE_DEBUG is defined.
#define TLX_BTREE_ASSERT(x)
Assertion only if TLX_BTREE_DEBUG is defined. This is not used in verify().
std::vector< std::string > split(char sep, const std::string &str, std::string::size_type limit)
Split the given string at each separator character into distinct substrings.
Extended structure of a inner node in-memory.
node * childid[inner_slotmax+1]
Pointers to children.
void initialize(const unsigned short l)
Set variables to initial values.
const key_type & key(size_t s) const
Return key in slot s.
bool is_few() const
True if few used entries, less than half full.
key_type slotkey[inner_slotmax]
Keys of children or data pointers.
bool is_underflow() const
True if node has too few entries.
std::allocator_traits< Allocator >::template rebind_alloc< InnerNode > alloc_type
Define an related allocator for the InnerNode structs.
bool is_full() const
True if the node's slots are full.
Extended structure of a leaf node in memory.
value_type slotdata[leaf_slotmax]
Array of (key, data) pairs.
void initialize()
Set variables to initial values.
LeafNode * prev_leaf
Double linked list pointers to traverse the leaves.
LeafNode * next_leaf
Double linked list pointers to traverse the leaves.
const key_type & key(size_t s) const
Return key in slot s.
bool is_few() const
True if few used entries, less than half full.
bool is_underflow() const
True if node has too few entries.
void set_slot(unsigned short slot, const value_type &value)
Set the (key,data) pair in slot.
std::allocator_traits< Allocator >::template rebind_alloc< LeafNode > alloc_type
Define an related allocator for the LeafNode structs.
bool is_full() const
True if the node's slots are full.
The header structure of each node in-memory.
unsigned short level
Level in the b-tree, if level == 0 -> leaf node.
unsigned short slotuse
Number of key slotuse use, so the number of valid children or data pointers.
bool is_leafnode() const
True if this is a leaf node.
void initialize(const unsigned short l)
Delayed initialisation of constructed node.
B+ tree recursive deletion has much information which is needs to be passed upward.
result_t(result_flags_t f=btree_ok)
Constructor of a result with a specific flag, this can also be used as for implicit conversion.
result_flags_t flags
Merged result flags.
key_type lastkey
The key to be updated at the parent's slot.
result_t & operator|=(const result_t &other)
Merge two results OR-ing the result flags and overwriting lastkeys.
bool has(result_flags_t f) const
Test if this result object has a given flag set.
result_t(result_flags_t f, const key_type &k)
Constructor with a lastkey value.
A small struct containing basic statistics about the B+ tree.
double avgfill_leaves() const
Return the average fill of leaves.
size_type inner_nodes
Number of inner nodes in the B+ tree.
size_type leaves
Number of leaves in the B+ tree.
size_type size
Number of items in the B+ tree.
static const unsigned short inner_slots
Base B+ tree parameter: The number of key slots in each inner node.
static const unsigned short leaf_slots
Base B+ tree parameter: The number of key/data slots in each leaf.
size_type nodes() const
Return the total number of nodes.
tree_stats()
Zero initialized.
Generates default traits for a B+ tree used as a set or map.
static const size_t binsearch_threshold
As of stx-btree-0.9, the code does linear search in find_lower() and find_upper() instead of binary_s...
static const int inner_slots
Number of slots in each inner node of the tree.
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
static const bool self_verify
If true, the tree will self verify its invariants after each insert() or erase().
static const int leaf_slots
Number of slots in each leaf of the tree.