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;
428 else if (
curr_leaf->next_leaf !=
nullptr) {
447 else if (
curr_leaf->next_leaf !=
nullptr) {
464 else if (
curr_leaf->prev_leaf !=
nullptr) {
483 else if (
curr_leaf->prev_leaf !=
nullptr) {
600 else if (
curr_leaf->next_leaf !=
nullptr) {
619 else if (
curr_leaf->next_leaf !=
nullptr) {
636 else if (
curr_leaf->prev_leaf !=
nullptr) {
655 else if (
curr_leaf->prev_leaf !=
nullptr) {
773 else if (
curr_leaf->prev_leaf !=
nullptr) {
792 else if (
curr_leaf->prev_leaf !=
nullptr) {
809 else if (
curr_leaf->next_leaf !=
nullptr) {
828 else if (
curr_leaf->next_leaf !=
nullptr) {
949 else if (
curr_leaf->prev_leaf !=
nullptr) {
968 else if (
curr_leaf->prev_leaf !=
nullptr) {
985 else if (
curr_leaf->next_leaf !=
nullptr) {
1004 else if (
curr_leaf->next_leaf !=
nullptr) {
1119 template <
class InputIterator>
1120 BTree(InputIterator first, InputIterator last,
1130 template <
class InputIterator>
1263 n->initialize(level);
1271 if (n->is_leafnode()) {
1272 LeafNode* ln =
static_cast<LeafNode*
>(n);
1274 std::allocator_traits<typename LeafNode::alloc_type>::destroy(a, ln);
1275 std::allocator_traits<typename LeafNode::alloc_type>::deallocate(a, ln, 1);
1279 InnerNode* in =
static_cast<InnerNode*
>(n);
1281 std::allocator_traits<typename InnerNode::alloc_type>::destroy(a, in);
1282 std::allocator_traits<typename InnerNode::alloc_type>::deallocate(a, in, 1);
1312 if (n->is_leafnode())
1314 LeafNode* leafnode =
static_cast<LeafNode*
>(n);
1316 for (
unsigned short slot = 0; slot < leafnode->slotuse; ++slot)
1323 InnerNode* innernode =
static_cast<InnerNode*
>(n);
1325 for (
unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
1366 return reverse_iterator(
end());
1372 return reverse_iterator(
begin());
1378 return const_reverse_iterator(
end());
1383 const_reverse_iterator
rend()
const {
1384 return const_reverse_iterator(
begin());
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;
1523 const node* n =
root_;
1524 if (!n)
return false;
1526 while (!n->is_leafnode())
1528 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1529 unsigned short slot =
find_lower(inner, key);
1531 n = inner->childid[slot];
1534 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
1537 return (slot < leaf->slotuse &&
key_equal(key, leaf->key(slot)));
1544 if (!n)
return end();
1546 while (!n->is_leafnode())
1548 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1549 unsigned short slot =
find_lower(inner, key);
1551 n = inner->childid[slot];
1554 LeafNode* leaf =
static_cast<LeafNode*
>(n);
1557 return (slot < leaf->slotuse &&
key_equal(key, leaf->key(slot)))
1558 ? iterator(leaf, slot) :
end();
1564 const node* n =
root_;
1565 if (!n)
return end();
1567 while (!n->is_leafnode())
1569 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1570 unsigned short slot =
find_lower(inner, key);
1572 n = inner->childid[slot];
1575 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
1578 return (slot < leaf->slotuse &&
key_equal(key, leaf->key(slot)))
1579 ? const_iterator(leaf, slot) :
end();
1585 const node* n =
root_;
1588 while (!n->is_leafnode())
1590 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1591 unsigned short slot =
find_lower(inner, key);
1593 n = inner->childid[slot];
1596 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
1601 while (leaf && slot < leaf->slotuse &&
key_equal(key, leaf->key(slot)))
1604 if (++slot >= leaf->slotuse)
1606 leaf = leaf->next_leaf;
1618 if (!n)
return end();
1620 while (!n->is_leafnode())
1622 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1623 unsigned short slot =
find_lower(inner, key);
1625 n = inner->childid[slot];
1628 LeafNode* leaf =
static_cast<LeafNode*
>(n);
1631 return iterator(leaf, slot);
1637 const node* n =
root_;
1638 if (!n)
return end();
1640 while (!n->is_leafnode())
1642 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1643 unsigned short slot =
find_lower(inner, key);
1645 n = inner->childid[slot];
1648 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
1651 return const_iterator(leaf, slot);
1658 if (!n)
return end();
1660 while (!n->is_leafnode())
1662 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1663 unsigned short slot =
find_upper(inner, key);
1665 n = inner->childid[slot];
1668 LeafNode* leaf =
static_cast<LeafNode*
>(n);
1671 return iterator(leaf, slot);
1677 const node* n =
root_;
1678 if (!n)
return end();
1680 while (!n->is_leafnode())
1682 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1683 unsigned short slot =
find_upper(inner, key);
1685 n = inner->childid[slot];
1688 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
1691 return const_iterator(leaf, slot);
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)
1797 if (n->is_leafnode())
1799 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
1802 newleaf->slotuse = leaf->slotuse;
1803 std::copy(leaf->slotdata, leaf->slotdata + leaf->slotuse,
1809 newleaf->prev_leaf = newleaf->next_leaf =
nullptr;
1822 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
1825 newinner->slotuse = inner->slotuse;
1826 std::copy(inner->slotkey, inner->slotkey + inner->slotuse,
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 =
1896 newroot->slotkey[0] = newkey;
1898 newroot->childid[0] =
root_;
1899 newroot->childid[1] = newchild;
1901 newroot->slotuse = 1;
1907 if (r.second) ++
stats_.size;
1909#ifdef TLX_BTREE_DEBUG
1910 if (
debug) print(std::cout);
1930 key_type* splitkey, node** splitnode) {
1932 if (!n->is_leafnode())
1934 InnerNode* inner =
static_cast<InnerNode*
>(n);
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);
1954 if (inner->is_full())
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)
1984 InnerNode*
split =
static_cast<InnerNode*
>(*splitnode);
1987 inner->slotkey[inner->slotuse] = *splitkey;
1988 inner->childid[inner->slotuse + 1] =
split->childid[0];
1993 split->childid[0] = newchild;
1998 else if (slot >= inner->slotuse + 1)
2003 slot -= inner->slotuse + 1;
2004 inner =
static_cast<InnerNode*
>(*splitnode);
2006 "BTree::insert_descend switching to "
2007 "splitted node " << inner <<
" slot " << slot);
2015 inner->slotkey + slot, inner->slotkey + inner->slotuse,
2016 inner->slotkey + inner->slotuse + 1);
2018 inner->childid + slot, inner->childid + inner->slotuse + 1,
2019 inner->childid + inner->slotuse + 2);
2021 inner->slotkey[slot] = newkey;
2022 inner->childid[slot + 1] = newchild;
2030 LeafNode* leaf =
static_cast<LeafNode*
>(n);
2035 slot < leaf->slotuse &&
key_equal(key, leaf->key(slot))) {
2036 return std::pair<iterator, bool>(iterator(leaf, slot),
false);
2039 if (leaf->is_full())
2044 if (slot >= leaf->slotuse)
2046 slot -= leaf->slotuse;
2047 leaf =
static_cast<LeafNode*
>(*splitnode);
2055 leaf->slotdata + slot, leaf->slotdata + leaf->slotuse,
2056 leaf->slotdata + leaf->slotuse + 1);
2058 leaf->slotdata[slot] = value;
2061 if (splitnode && leaf != *splitnode && slot == leaf->slotuse - 1)
2068 return std::pair<iterator, bool>(iterator(leaf, slot),
true);
2075 key_type* out_newkey, node** out_newleaf) {
2078 unsigned short mid = (leaf->slotuse >> 1);
2084 newleaf->slotuse = leaf->slotuse - mid;
2086 newleaf->next_leaf = leaf->next_leaf;
2087 if (newleaf->next_leaf ==
nullptr) {
2092 newleaf->next_leaf->
prev_leaf = newleaf;
2095 std::copy(leaf->slotdata + mid, leaf->slotdata + leaf->slotuse,
2098 leaf->slotuse = mid;
2099 leaf->next_leaf = newleaf;
2100 newleaf->prev_leaf = leaf;
2102 *out_newkey = leaf->key(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");
2133 newinner->slotuse = inner->slotuse - (mid + 1);
2135 std::copy(inner->slotkey + mid + 1, inner->slotkey + inner->slotuse,
2137 std::copy(inner->childid + mid + 1, inner->childid + inner->slotuse + 1,
2140 inner->slotuse = mid;
2142 *out_newkey = inner->key(mid);
2143 *out_newinner = newinner;
2154 template <
typename Iterator>
2158 stats_.size = iend - ibegin;
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)
2180 leaf->set_slot(s, *it);
2191 num_items -= leaf->slotuse;
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)
2232 n->slotkey[s] = leaf->key(leaf->slotuse - 1);
2233 n->childid[s] = leaf;
2234 leaf = leaf->next_leaf;
2236 n->childid[n->slotuse] = leaf;
2239 nextlevel[i].first = n;
2240 nextlevel[i].second = &leaf->key(leaf->slotuse - 1);
2242 leaf = leaf->next_leaf;
2243 num_leaves -= n->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;
2280 n->childid[n->slotuse] = 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);
2407 "," << iter.curr_slot <<
") on btree size " <<
size());
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 ) {
2451 node* left, node* right,
2452 InnerNode* left_parent, InnerNode* right_parent,
2453 InnerNode* parent,
unsigned int parentslot) {
2454 if (curr->is_leafnode())
2456 LeafNode* leaf =
static_cast<LeafNode*
>(curr);
2457 LeafNode* left_leaf =
static_cast<LeafNode*
>(left);
2458 LeafNode* right_leaf =
static_cast<LeafNode*
>(right);
2462 if (slot >= leaf->slotuse || !
key_equal(key, leaf->key(slot)))
2470 "Found key in leaf " << curr <<
" at slot " << slot);
2472 std::copy(leaf->slotdata + slot + 1, leaf->slotdata + leaf->slotuse,
2473 leaf->slotdata + slot);
2481 if (slot == leaf->slotuse)
2483 if (parent && parentslot < parent->slotuse)
2486 parent->slotkey[parentslot] = leaf->key(leaf->slotuse - 1);
2490 if (leaf->slotuse >= 1)
2493 leaf->key(leaf->slotuse - 1));
2504 if (leaf->is_underflow() && !(leaf ==
root_ && leaf->slotuse >= 1))
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)
2564 if (left_leaf->slotuse <= right_leaf->slotuse)
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);
2586 InnerNode* inner =
static_cast<InnerNode*
>(curr);
2587 InnerNode* left_inner =
static_cast<InnerNode*
>(left);
2588 InnerNode* right_inner =
static_cast<InnerNode*
>(right);
2590 node* myleft, * myright;
2591 InnerNode* myleft_parent, * myright_parent;
2593 unsigned short slot =
find_lower(inner, key);
2597 (left ==
nullptr) ?
nullptr :
2598 static_cast<InnerNode*
>(left)->childid[left->slotuse - 1];
2599 myleft_parent = left_parent;
2602 myleft = inner->childid[slot - 1];
2603 myleft_parent = inner;
2606 if (slot == inner->slotuse) {
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;
2621 inner->childid[slot],
2623 myleft_parent, myright_parent,
2635 if (parent && parentslot < parent->slotuse)
2638 result.lastkey <<
" into parent " <<
2639 parent <<
" at parentslot " <<
2643 parent->slotkey[parentslot] = result.lastkey;
2648 "Forwarding lastkeyupdate: key " << result.lastkey);
2657 if (inner->childid[slot]->
slotuse != 0)
2666 inner->slotkey + slot, inner->slotkey + inner->slotuse,
2667 inner->slotkey + slot - 1);
2669 inner->childid + slot + 1,
2670 inner->childid + inner->slotuse + 1,
2671 inner->childid + slot);
2675 if (inner->level == 1)
2680 static_cast<LeafNode*
>(inner->childid[slot]);
2681 inner->slotkey[slot] = child->key(child->slotuse - 1);
2685 if (inner->is_underflow() &&
2686 !(inner ==
root_ && inner->slotuse >= 1))
2690 if (left_inner ==
nullptr && right_inner ==
nullptr)
2695 root_ = inner->childid[0];
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)
2743 if (left_inner->slotuse <= right_inner->slotuse)
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);
2781 node* left, node* right,
2782 InnerNode* left_parent, InnerNode* right_parent,
2783 InnerNode* parent,
unsigned int parentslot) {
2784 if (curr->is_leafnode())
2786 LeafNode* leaf =
static_cast<LeafNode*
>(curr);
2787 LeafNode* left_leaf =
static_cast<LeafNode*
>(left);
2788 LeafNode* right_leaf =
static_cast<LeafNode*
>(right);
2792 if (leaf != iter.curr_leaf)
2797 if (iter.curr_slot >= leaf->slotuse)
2800 iter.curr_leaf <<
"," << iter.curr_slot <<
2801 ") to erase. Invalid leaf node?");
2806 unsigned short slot = iter.curr_slot;
2809 curr <<
" at slot " << slot);
2811 std::copy(leaf->slotdata + slot + 1, leaf->slotdata + leaf->slotuse,
2812 leaf->slotdata + slot);
2820 if (slot == leaf->slotuse)
2822 if (parent && parentslot < parent->slotuse)
2825 parent->slotkey[parentslot] = leaf->key(leaf->slotuse - 1);
2829 if (leaf->slotuse >= 1)
2832 leaf->key(leaf->slotuse - 1));
2843 if (leaf->is_underflow() && !(leaf ==
root_ && leaf->slotuse >= 1))
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)
2907 if (left_leaf->slotuse <= right_leaf->slotuse) {
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);
2933 InnerNode* inner =
static_cast<InnerNode*
>(curr);
2934 InnerNode* left_inner =
static_cast<InnerNode*
>(left);
2935 InnerNode* right_inner =
static_cast<InnerNode*
>(right);
2941 unsigned short slot =
find_lower(inner, iter.key());
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;
2959 if (slot == inner->slotuse) {
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;
2970 inner->childid[slot]);
2973 inner->childid[slot],
2975 myleft_parent, myright_parent,
2983 if (slot < inner->slotuse &&
2984 key_less(inner->slotkey[slot], iter.key()))
2990 if (slot > inner->slotuse)
2997 if (parent && parentslot < parent->slotuse)
3000 result.lastkey <<
" into parent " <<
3001 parent <<
" at parentslot " << parentslot);
3004 parent->slotkey[parentslot] = result.lastkey;
3009 "Forwarding lastkeyupdate: key " << result.lastkey);
3018 if (inner->childid[slot]->
slotuse != 0)
3027 inner->slotkey + slot, inner->slotkey + inner->slotuse,
3028 inner->slotkey + slot - 1);
3030 inner->childid + slot + 1,
3031 inner->childid + inner->slotuse + 1,
3032 inner->childid + slot);
3036 if (inner->level == 1)
3041 static_cast<LeafNode*
>(inner->childid[slot]);
3042 inner->slotkey[slot] = child->key(child->slotuse - 1);
3046 if (inner->is_underflow() &&
3047 !(inner ==
root_ && inner->slotuse >= 1))
3051 if (left_inner ==
nullptr && right_inner ==
nullptr)
3056 root_ = inner->childid[0];
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)
3110 if (left_inner->slotuse <= right_inner->slotuse) {
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);
3140 InnerNode* parent) {
3142 " with common parent " << parent <<
".");
3150 std::copy(right->slotdata, right->slotdata + right->slotuse,
3151 left->slotdata + left->slotuse);
3153 left->slotuse += right->slotuse;
3155 left->next_leaf = right->next_leaf;
3156 if (left->next_leaf)
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)
3197 left->slotkey[left->slotuse] = parent->slotkey[parentslot];
3201 std::copy(right->slotkey, right->slotkey + right->slotuse,
3202 left->slotkey + left->slotuse);
3203 std::copy(right->childid, right->childid + right->slotuse + 1,
3204 left->childid + left->slotuse);
3206 left->slotuse += right->slotuse;
3216 LeafNode* left, LeafNode* right,
3217 InnerNode* parent,
unsigned int parentslot) {
3228 unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1;
3230 TLX_BTREE_PRINT(
"Shifting (leaf) " << shiftnum <<
" entries to left " <<
3231 left <<
" from right " << right <<
3232 " with common parent " << parent <<
".");
3239 std::copy(right->slotdata, right->slotdata + shiftnum,
3240 left->slotdata + left->slotuse);
3242 left->slotuse += shiftnum;
3246 std::copy(right->slotdata + shiftnum, right->slotdata + right->slotuse,
3249 right->slotuse -= shiftnum;
3252 if (parentslot < parent->slotuse) {
3253 parent->slotkey[parentslot] = left->key(left->slotuse - 1);
3265 InnerNode* parent,
unsigned int parentslot) {
3272 unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1;
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)
3300 left->slotkey[left->slotuse] = parent->slotkey[parentslot];
3305 std::copy(right->slotkey, right->slotkey + shiftnum - 1,
3306 left->slotkey + left->slotuse);
3307 std::copy(right->childid, right->childid + shiftnum,
3308 left->childid + left->slotuse);
3310 left->slotuse += shiftnum - 1;
3313 parent->slotkey[parentslot] = right->slotkey[shiftnum - 1];
3317 right->slotkey + shiftnum, right->slotkey + right->slotuse,
3320 right->childid + shiftnum, right->childid + right->slotuse + 1,
3323 right->slotuse -= shiftnum;
3330 InnerNode* parent,
unsigned int parentslot) {
3340 unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1;
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)
3366 std::copy_backward(right->slotdata, right->slotdata + right->slotuse,
3367 right->slotdata + right->slotuse + shiftnum);
3369 right->slotuse += shiftnum;
3373 std::copy(left->slotdata + left->slotuse - shiftnum,
3374 left->slotdata + left->slotuse,
3377 left->slotuse -= shiftnum;
3379 parent->slotkey[parentslot] = left->key(left->slotuse - 1);
3386 InnerNode* parent,
unsigned int parentslot) {
3393 unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1;
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)
3420 right->slotkey, right->slotkey + right->slotuse,
3421 right->slotkey + right->slotuse + shiftnum);
3423 right->childid, right->childid + right->slotuse + 1,
3424 right->childid + right->slotuse + 1 + shiftnum);
3426 right->slotuse += shiftnum;
3430 right->slotkey[shiftnum - 1] = parent->slotkey[parentslot];
3434 std::copy(left->slotkey + left->slotuse - shiftnum + 1,
3435 left->slotkey + left->slotuse,
3437 std::copy(left->childid + left->slotuse - shiftnum + 1,
3438 left->childid + left->slotuse + 1,
3443 parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum];
3445 left->slotuse -= shiftnum;
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 <<
" ";
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) <<
" ";
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);
3560 tree_stats& vstats)
const {
3563 if (n->is_leafnode())
3565 const LeafNode* leaf =
static_cast<const LeafNode*
>(n);
3570 for (
unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot)
3576 *minkey = leaf->key(0);
3577 *maxkey = leaf->key(leaf->slotuse - 1);
3580 vstats.size += leaf->slotuse;
3584 const InnerNode* inner =
static_cast<const InnerNode*
>(n);
3585 vstats.inner_nodes++;
3590 for (
unsigned short slot = 0; slot < inner->slotuse - 1; ++slot)
3596 for (
unsigned short slot = 0; slot <= inner->slotuse; ++slot)
3598 const node* subnode = inner->childid[slot];
3603 verify_node(subnode, &subminkey, &submaxkey, vstats);
3606 ": " << subminkey <<
3607 " - " << submaxkey);
3610 *minkey = subminkey;
3615 if (slot == inner->slotuse)
3616 *maxkey = submaxkey;
3620 if (inner->level == 1 && slot < inner->slotuse)
3624 const LeafNode* leafa =
static_cast<const LeafNode*
>(
3625 inner->childid[slot]);
3626 const LeafNode* leafb =
static_cast<const LeafNode*
>(
3627 inner->childid[slot + 1]);
3632 if (inner->level == 2 && slot < inner->slotuse)
3635 const InnerNode* parenta =
static_cast<const InnerNode*
>(
3636 inner->childid[slot]);
3637 const InnerNode* parentb =
static_cast<const InnerNode*
>(
3638 inner->childid[slot + 1]);
3640 const LeafNode* leafa =
static_cast<const LeafNode*
>(
3641 parenta->childid[parenta->slotuse]);
3642 const LeafNode* leafb =
static_cast<const LeafNode*
>(
3643 parentb->childid[0]);
3659 unsigned int testcount = 0;
3666 for (
unsigned short slot = 0; slot < n->slotuse - 1; ++slot)
3671 testcount += n->slotuse;
3676 n->next_leaf->
key(0)));
STL-like read-only iterator object for B+ tree items.
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
BTree::key_type key_type
The key type of the btree. Returned by key().
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
const BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
friend class const_reverse_iterator
Friendly to the reverse_const_iterator, so it may access the two data items directly.
const_iterator self
Our own type.
const_iterator & operator++()
Prefix++ advance the iterator to the next slot.
const value_type & reference
Reference to the value_type. STL required.
reference operator*() const
Dereference the iterator.
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 value_type * pointer
Pointer to the value_type. STL required.
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
ptrdiff_t difference_type
STL-magic.
const key_type & key() const
Key of the current slot.
unsigned short curr_slot
Current key/data slot referenced.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
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.
BTree::key_type key_type
The key type of the btree. Returned by key().
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
const BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
const_reverse_iterator self
Our own type.
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.
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
const value_type & reference
Reference to the value_type. STL required.
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.
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
const value_type * pointer
Pointer to the value_type. STL required.
ptrdiff_t difference_type
STL-magic.
const key_type & key() const
Key of the current slot.
unsigned short curr_slot
One slot past the current key/data slot referenced.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
pointer operator->() const
Dereference the iterator.
friend class reverse_iterator
Friendly to the const_iterator, so it may access the two data items directly.
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.
BTree::key_type key_type
The key type of the btree. Returned by key().
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
bool operator==(const iterator &x) const
Equality of iterators.
iterator self
Our own type.
bool operator!=(const iterator &x) const
Inequality of iterators.
iterator()
Default-Constructor of a mutable iterator.
friend class const_reverse_iterator
Also friendly to the const_reverse_iterator, so it may access the two data items directly.
iterator & operator--()
Prefix– backstep the iterator to the last slot.
reference operator*() const
Dereference the iterator.
value_type & reference
Reference to the value_type. STL required.
iterator & operator++()
Prefix++ advance the iterator to the next slot.
friend class const_iterator
Friendly to the const_iterator, so it may access the two data items directly.
ptrdiff_t difference_type
STL-magic.
BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
value_type * pointer
Pointer to the value_type. STL required.
const key_type & key() const
Key of the current slot.
unsigned short curr_slot
Current key/data slot referenced.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
pointer operator->() const
Dereference the iterator.
friend class reverse_iterator
Also friendly to the reverse_iterator, so it may access the two data items directly.
iterator(typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a mutable iterator.
STL-like mutable reverse iterator object for B+ tree items.
BTree::key_type key_type
The key type of the btree. Returned by key().
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
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.
friend class iterator
Friendly to the const_iterator, so it may access the two data items directly.
friend class const_reverse_iterator
Also friendly to the const_iterator, so it may access the two data items directly.
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.
reverse_iterator()
Default-Constructor of a reverse iterator.
reference operator*() const
Dereference the iterator.
value_type & reference
Reference to the value_type. STL required.
friend class const_iterator
Also friendly to the const_iterator, so it may access the two data items directly.
ptrdiff_t difference_type
STL-magic.
BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
value_type * pointer
Pointer to the value_type. STL required.
reverse_iterator & operator--()
Prefix– backstep the iterator to the last slot.
const key_type & key() const
Key of the current slot.
unsigned short curr_slot
One slot past the current key/data slot referenced.
BTree::value_type value_type
The value type of the btree. Returned by operator*().
pointer operator->() const
Dereference the iterator.
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.
static const unsigned short inner_slotmax
void clear_recursive(node *n)
Recursively free up nodes.
Value value_type
Second template parameter: Composition pair of key and data types, or just the key for set containers...
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.
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_()
KeyOfValue key_of_value
Third template: key extractor class to pull key_type from value_type.
static void shift_left_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Balance two inner nodes.
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
BTree< key_type, value_type, key_of_value, key_compare, traits, allow_duplicates, allocator_type > Self
Typedef of our own type.
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,...
Key key_type
First template parameter: The key type of the B+ tree.
result_flags_t
Result flags of recursive deletion.
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
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().
static const bool allow_duplicates
LeafNode * allocate_leaf()
Allocate and initialize a leaf node.
static const unsigned short leaf_slotmax
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.
size_type size() const
Return the number of key/data pairs in the B+ 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.
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.
Compare key_compare
Fourth template parameter: key_type comparison function object.
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
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_
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
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<.
Traits traits
Fifth template parameter: Traits object used to define more parameters of the B+ tree.
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.
static const unsigned short leaf_slotmin
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ?
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.
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.
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.
Allocator allocator_type
Seventh template parameter: STL allocator for tree 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.
std::allocator_traits< Allocator >::template rebind_alloc< InnerNode > alloc_type
Define an related allocator for the InnerNode structs.
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.
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.
std::allocator_traits< Allocator >::template rebind_alloc< LeafNode > alloc_type
Define an related allocator for the LeafNode structs.
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.
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.
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.
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.