11 #ifndef TLX_CONTAINER_BTREE_HEADER
12 #define TLX_CONTAINER_BTREE_HEADER
37 #ifdef TLX_BTREE_DEBUG
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
73 template <
typename Key,
typename Value>
74 struct btree_default_traits {
84 static const bool debug =
false;
118 template <
typename Key,
typename Value,
120 typename Compare = std::less<Key>,
122 bool Duplicates =
false,
123 typename Allocator = std::allocator<Value> >
180 static const unsigned short leaf_slotmax = traits::leaf_slots;
184 static const unsigned short inner_slotmax = traits::inner_slots;
198 static const bool self_verify = traits::self_verify;
203 static const bool debug = traits::debug;
215 unsigned short level;
235 struct InnerNode :
public node {
237 typedef typename Allocator::template rebind<InnerNode>::other
alloc_type;
275 typedef typename Allocator::template rebind<LeafNode>::other
alloc_type;
294 return key_of_value::get(
slotdata[s]);
425 if (
curr_slot + 1u < curr_leaf->slotuse) {
444 if (
curr_slot + 1u < curr_leaf->slotuse) {
597 if (
curr_slot + 1u < curr_leaf->slotuse) {
616 if (
curr_slot + 1u < curr_leaf->slotuse) {
806 if (curr_slot < curr_leaf->slotuse) {
825 if (curr_slot < curr_leaf->slotuse) {
982 if (curr_slot < curr_leaf->slotuse) {
1001 if (curr_slot < curr_leaf->slotuse) {
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);
1275 a.deallocate(ln, 1);
1279 InnerNode* in =
static_cast<InnerNode*
>(n);
1282 a.deallocate(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)
1353 const_iterator
begin()
const {
1359 const_iterator
end()
const {
1365 reverse_iterator
rbegin() {
1366 return reverse_iterator(
end());
1371 reverse_iterator
rend() {
1372 return reverse_iterator(
begin());
1377 const_reverse_iterator
rbegin()
const {
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;
1499 bool empty()
const {
1510 const struct tree_stats&
get_stats()
const {
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);
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,
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;
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) {
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>
2155 void bulk_load(Iterator ibegin, Iterator iend) {
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);
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);
2405 void erase(iterator iter) {
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)
3157 left->next_leaf->prev_leaf = left;
3169 static result_t
merge_inner(InnerNode* left, InnerNode* right,
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 <<
" ";
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);
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)));
3699 #endif // !TLX_CONTAINER_BTREE_HEADER