55 #define BTREE_PRINT(x) do { if (debug) (std::cout << x << std::endl); } while(0)
58 #define BTREE_ASSERT(x) do { assert(x); } while(0)
63 #define BTREE_PRINT(x) do { } while(0)
66 #define BTREE_ASSERT(x) do { } while(0)
71 #define BTREE_MAX(a,b) ((a) < (b) ? (b) : (a))
77 #define BTREE_FRIENDS friend class btree_friend;
85 template <
typename _Key>
96 static const bool debug =
false;
115 template <
typename _Key,
typename _Data>
156 template <
typename _Key,
typename _Data,
157 typename _Value = std::pair<_Key, _Data>,
158 typename _Compare = std::less<_Key>,
160 bool _Duplicates =
false,
161 typename _Alloc = std::allocator<_Value>,
162 bool _UsedAsSet =
false >
248 static const bool debug = traits::debug;
283 typedef typename _Alloc::template rebind<inner_node>::other
alloc_type;
322 typedef typename _Alloc::template rebind<leaf_node>::other
alloc_type;
386 template <
typename value_type,
typename pair_type>
400 template <
typename value_type>
421 class const_iterator;
422 class reverse_iterator;
423 class const_reverse_iterator;
989 if (currslot < currnode->slotuse) {
1009 if (currslot < currnode->slotuse) {
1196 if (currslot < currnode->slotuse) {
1216 if (currslot < currnode->slotuse) {
1330 template <
class InputIterator>
1331 inline btree(InputIterator first, InputIterator last,
1341 template <
class InputIterator>
1487 if (n->isleafnode()) {
1488 leaf_node *ln =
static_cast<leaf_node*
>(n);
1491 a.deallocate(ln, 1);
1495 inner_node *in =
static_cast<inner_node*
>(n);
1498 a.deallocate(in, 1);
1505 template<
class InputIterator,
class OutputIterator>
1506 static OutputIterator
data_copy (InputIterator first, InputIterator last,
1507 OutputIterator result)
1510 else return std::copy(first, last, result);
1515 template<
class InputIterator,
class OutputIterator>
1517 OutputIterator result)
1520 else return std::copy_backward(first, last, result);
1547 if (n->isleafnode())
1549 leaf_node *leafnode =
static_cast<leaf_node*
>(n);
1551 for (
unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
1558 inner_node *innernode =
static_cast<inner_node*
>(n);
1560 for (
unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
1594 inline const_iterator
end()
const
1603 return reverse_iterator(
end());
1610 return reverse_iterator(
begin());
1617 return const_reverse_iterator(
end());
1622 inline const_reverse_iterator
rend()
const
1624 return const_reverse_iterator(
begin());
1634 template <
typename node_type>
1637 if ( 0 &&
sizeof(n->slotkey) > traits::binsearch_threshold )
1639 if (n->slotuse == 0)
return 0;
1641 int lo = 0, hi = n->slotuse;
1645 int mid = (lo + hi) >> 1;
1655 BTREE_PRINT(
"btree::find_lower: on " << n <<
" key " << key <<
" -> " << lo <<
" / " << hi);
1661 while (i < n->slotuse &&
key_less(n->slotkey[i],key)) ++i;
1663 BTREE_PRINT(
"btree::find_lower: testfind: " << i);
1672 while (lo < n->slotuse &&
key_less(n->slotkey[lo],key)) ++lo;
1681 template <
typename node_type>
1684 if ( 0 &&
sizeof(n->slotkey) > traits::binsearch_threshold )
1686 if (n->slotuse == 0)
return 0;
1688 int lo = 0, hi = n->slotuse;
1692 int mid = (lo + hi) >> 1;
1694 if (
key_less(key, n->slotkey[mid])) {
1702 BTREE_PRINT(
"btree::find_upper: on " << n <<
" key " << key <<
" -> " << lo <<
" / " << hi);
1708 while (i < n->slotuse &&
key_lessequal(n->slotkey[i],key)) ++i;
1719 while (lo < n->slotuse &&
key_lessequal(n->slotkey[lo],key)) ++lo;
1760 if (!n)
return false;
1762 while(!n->isleafnode())
1764 const inner_node *inner =
static_cast<const inner_node*
>(n);
1767 n = inner->childid[slot];
1770 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1773 return (slot < leaf->slotuse &&
key_equal(key, leaf->slotkey[slot]));
1781 if (!n)
return end();
1783 while(!n->isleafnode())
1785 const inner_node *inner =
static_cast<const inner_node*
>(n);
1788 n = inner->childid[slot];
1791 leaf_node *leaf =
static_cast<leaf_node*
>(n);
1794 return (slot < leaf->slotuse &&
key_equal(key, leaf->slotkey[slot]))
1795 ? iterator(leaf, slot) :
end();
1803 if (!n)
return end();
1805 while(!n->isleafnode())
1807 const inner_node *inner =
static_cast<const inner_node*
>(n);
1810 n = inner->childid[slot];
1813 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1816 return (slot < leaf->slotuse &&
key_equal(key, leaf->slotkey[slot]))
1817 ? const_iterator(leaf, slot) :
end();
1827 while(!n->isleafnode())
1829 const inner_node *inner =
static_cast<const inner_node*
>(n);
1832 n = inner->childid[slot];
1835 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1840 while (leaf && slot < leaf->slotuse &&
key_equal(key, leaf->slotkey[slot]))
1843 if (++slot >= leaf->slotuse)
1845 leaf = leaf->nextleaf;
1858 if (!n)
return end();
1860 while(!n->isleafnode())
1862 const inner_node *inner =
static_cast<const inner_node*
>(n);
1865 n = inner->childid[slot];
1868 leaf_node *leaf =
static_cast<leaf_node*
>(n);
1871 return iterator(leaf, slot);
1880 if (!n)
return end();
1882 while(!n->isleafnode())
1884 const inner_node *inner =
static_cast<const inner_node*
>(n);
1887 n = inner->childid[slot];
1890 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1893 return const_iterator(leaf, slot);
1901 if (!n)
return end();
1903 while(!n->isleafnode())
1905 const inner_node *inner =
static_cast<const inner_node*
>(n);
1908 n = inner->childid[slot];
1911 leaf_node *leaf =
static_cast<leaf_node*
>(n);
1914 return iterator(leaf, slot);
1923 if (!n)
return end();
1925 while(!n->isleafnode())
1927 const inner_node *inner =
static_cast<const inner_node*
>(n);
1930 n = inner->childid[slot];
1933 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1936 return const_iterator(leaf, slot);
1965 return !(*
this == other);
1972 return std::lexicographical_compare(
begin(),
end(), other.
begin(), other.
end());
1978 return other < *
this;
1984 return !(other < *
this);
1990 return !(*
this < other);
2006 if (other.
size() != 0)
2042 if (n->isleafnode())
2044 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
2047 newleaf->slotuse = leaf->slotuse;
2048 std::copy(leaf->slotkey, leaf->slotkey + leaf->slotuse, newleaf->slotkey);
2049 data_copy(leaf->slotdata, leaf->slotdata + leaf->slotuse, newleaf->slotdata);
2067 const inner_node *inner =
static_cast<const inner_node*
>(n);
2070 newinner->slotuse = inner->slotuse;
2071 std::copy(inner->slotkey, inner->slotkey + inner->slotuse, newinner->slotkey);
2073 for (
unsigned short slot = 0; slot <= inner->slotuse; ++slot)
2128 template <
typename InputIterator>
2129 inline void insert(InputIterator first, InputIterator last)
2131 InputIterator iter = first;
2146 node *newchild = NULL;
2158 newroot->slotkey[0] = newkey;
2160 newroot->childid[0] =
m_root;
2161 newroot->childid[1] = newchild;
2192 key_type* splitkey, node** splitnode)
2194 if (!n->isleafnode())
2196 inner_node *inner =
static_cast<inner_node*
>(n);
2199 node *newchild = NULL;
2203 BTREE_PRINT(
"btree::insert_descend into " << inner->childid[slot]);
2205 std::pair<iterator, bool> r =
insert_descend(inner->childid[slot],
2206 key, value, &newkey, &newchild);
2210 BTREE_PRINT(
"btree::insert_descend newchild with key " << newkey <<
" node " << newchild <<
" at slot " << slot);
2212 if (inner->isfull())
2216 BTREE_PRINT(
"btree::insert_descend done split_inner: putslot: " << slot <<
" putkey: " << newkey <<
" upkey: " << *splitkey);
2227 BTREE_PRINT(
"btree::insert_descend switch: " << slot <<
" > " << inner->slotuse+1);
2229 if (slot == inner->slotuse+1 && inner->slotuse < (*splitnode)->slotuse)
2237 inner_node *splitinner =
static_cast<inner_node*
>(*splitnode);
2240 inner->slotkey[inner->slotuse] = *splitkey;
2241 inner->childid[inner->slotuse+1] = splitinner->childid[0];
2245 splitinner->childid[0] = newchild;
2250 else if (slot >= inner->slotuse+1)
2255 slot -= inner->slotuse+1;
2256 inner =
static_cast<inner_node*
>(*splitnode);
2257 BTREE_PRINT(
"btree::insert_descend switching to splitted node " << inner <<
" slot " << slot);
2264 std::copy_backward(inner->slotkey + slot, inner->slotkey + inner->slotuse,
2265 inner->slotkey + inner->slotuse+1);
2266 std::copy_backward(inner->childid + slot, inner->childid + inner->slotuse+1,
2267 inner->childid + inner->slotuse+2);
2269 inner->slotkey[slot] = newkey;
2270 inner->childid[slot + 1] = newchild;
2278 leaf_node *leaf =
static_cast<leaf_node*
>(n);
2283 return std::pair<iterator, bool>(iterator(leaf, slot),
false);
2291 if (slot >= leaf->slotuse)
2293 slot -= leaf->slotuse;
2294 leaf =
static_cast<leaf_node*
>(*splitnode);
2301 std::copy_backward(leaf->slotkey + slot, leaf->slotkey + leaf->slotuse,
2302 leaf->slotkey + leaf->slotuse+1);
2304 leaf->slotdata + leaf->slotuse+1);
2306 leaf->slotkey[slot] = key;
2310 if (splitnode && leaf != *splitnode && slot == leaf->slotuse-1)
2318 return std::pair<iterator, bool>(iterator(leaf, slot),
true);
2328 unsigned int mid = (leaf->slotuse >> 1);
2330 BTREE_PRINT(
"btree::split_leaf_node on " << leaf);
2334 newleaf->slotuse = leaf->slotuse - mid;
2336 newleaf->nextleaf = leaf->nextleaf;
2337 if (newleaf->nextleaf == NULL) {
2345 std::copy(leaf->slotkey + mid, leaf->slotkey + leaf->slotuse,
2347 data_copy(leaf->slotdata + mid, leaf->slotdata + leaf->slotuse,
2350 leaf->slotuse = mid;
2351 leaf->nextleaf = newleaf;
2352 newleaf->prevleaf = leaf;
2354 *_newkey = leaf->slotkey[leaf->slotuse-1];
2355 *_newleaf = newleaf;
2366 unsigned int mid = (inner->slotuse >> 1);
2368 BTREE_PRINT(
"btree::split_inner: mid " << mid <<
" addslot " << addslot);
2372 if (addslot <= mid && mid > inner->slotuse - (mid + 1))
2375 BTREE_PRINT(
"btree::split_inner: mid " << mid <<
" addslot " << addslot);
2377 BTREE_PRINT(
"btree::split_inner_node on " << inner <<
" into two nodes " << mid <<
" and " << inner->slotuse - (mid + 1) <<
" sized");
2381 newinner->slotuse = inner->slotuse - (mid + 1);
2383 std::copy(inner->slotkey + mid+1, inner->slotkey + inner->slotuse,
2385 std::copy(inner->childid + mid+1, inner->childid + inner->slotuse+1,
2388 inner->slotuse = mid;
2390 *_newkey = inner->slotkey[mid];
2391 *_newinner = newinner;
2400 template <
typename Iterator>
2408 size_t num_items = iend - ibegin;
2411 BTREE_PRINT(
"btree::bulk_load, level 0: " <<
m_stats.
itemcount <<
" items into " << num_leaves <<
" leaves with up to " << ((iend - ibegin + num_leaves-1) / num_leaves) <<
" items per leaf.");
2413 Iterator it = ibegin;
2414 for (
size_t i = 0; i < num_leaves; ++i)
2421 leaf->slotuse =
static_cast<int>(num_items / (num_leaves-i));
2422 for (
size_t s = 0; s < leaf->slotuse; ++s, ++it)
2423 leaf->set_slot(s, *it);
2450 BTREE_PRINT(
"btree::bulk_load, level 1: " << num_leaves <<
" leaves in " << num_parents <<
" inner nodes with up to " << ((num_leaves + num_parents-1) / num_parents) <<
" leaves per inner node.");
2453 typedef std::pair<inner_node*, const key_type*> nextlevel_type;
2454 nextlevel_type* nextlevel =
new nextlevel_type[num_parents];
2457 for (
size_t i = 0; i < num_parents; ++i)
2462 n->slotuse =
static_cast<int>(num_leaves / (num_parents-i));
2467 for (
unsigned short s = 0; s < n->slotuse; ++s)
2469 n->slotkey[s] = leaf->slotkey[leaf->slotuse-1];
2470 n->childid[s] = leaf;
2471 leaf = leaf->nextleaf;
2473 n->childid[n->slotuse] = leaf;
2476 nextlevel[i].first = n;
2477 nextlevel[i].second = &leaf->slotkey[leaf->slotuse-1];
2479 leaf = leaf->nextleaf;
2480 num_leaves -= n->slotuse+1;
2486 for (
int level = 2; num_parents != 1; ++level)
2488 size_t num_children = num_parents;
2491 BTREE_PRINT(
"btree::bulk_load, level " << level <<
": " << num_children <<
" children in " << num_parents <<
" inner nodes with up to " << ((num_children + num_parents-1) / num_parents) <<
" children per inner node.");
2493 size_t inner_index = 0;
2494 for (
size_t i = 0; i < num_parents; ++i)
2499 n->slotuse =
static_cast<int>(num_children / (num_parents-i));
2504 for (
unsigned short s = 0; s < n->slotuse; ++s)
2506 n->slotkey[s] = *nextlevel[inner_index].second;
2507 n->childid[s] = nextlevel[inner_index].first;
2510 n->childid[n->slotuse] = nextlevel[inner_index].first;
2514 nextlevel[i].first = n;
2515 nextlevel[i].second = nextlevel[inner_index].second;
2518 num_children -= n->slotuse+1;
2524 m_root = nextlevel[0].first;
2525 delete [] nextlevel;
2575 return (
flags & f) != 0;
2598 BTREE_PRINT(
"btree::erase_one(" << key <<
") on btree size " <<
size());
2602 if (!
m_root)
return false;
2635 BTREE_PRINT(
"btree::erase_iter(" << iter.currnode <<
"," << iter.currslot <<
") on btree size " <<
size());
2675 node *left, node *right,
2676 inner_node *leftparent, inner_node *rightparent,
2677 inner_node *parent,
unsigned int parentslot)
2679 if (curr->isleafnode())
2681 leaf_node *leaf =
static_cast<leaf_node*
>(curr);
2682 leaf_node *leftleaf =
static_cast<leaf_node*
>(left);
2683 leaf_node *rightleaf =
static_cast<leaf_node*
>(right);
2687 if (slot >= leaf->slotuse || !
key_equal(key, leaf->slotkey[slot]))
2689 BTREE_PRINT(
"Could not find key " << key <<
" to erase.");
2694 BTREE_PRINT(
"Found key in leaf " << curr <<
" at slot " << slot);
2696 std::copy(leaf->slotkey + slot+1, leaf->slotkey + leaf->slotuse,
2697 leaf->slotkey + slot);
2698 data_copy(leaf->slotdata + slot+1, leaf->slotdata + leaf->slotuse,
2699 leaf->slotdata + slot);
2707 if (slot == leaf->slotuse)
2709 if (parent && parentslot < parent->slotuse)
2712 parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
2716 if (leaf->slotuse >= 1)
2718 BTREE_PRINT(
"Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1]);
2728 if (leaf->isunderflow() && !(leaf ==
m_root && leaf->
slotuse >= 1))
2734 if (leftleaf == NULL && rightleaf == NULL)
2754 else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
2756 if (leftparent == parent)
2762 else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
2764 if (rightparent == parent)
2770 else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
2772 if (leftparent == parent)
2779 else if (leftparent == rightparent)
2781 if (leftleaf->slotuse <= rightleaf->slotuse)
2788 if (leftparent == parent)
2799 inner_node *inner =
static_cast<inner_node*
>(curr);
2800 inner_node *leftinner =
static_cast<inner_node*
>(left);
2801 inner_node *rightinner =
static_cast<inner_node*
>(right);
2803 node *myleft, *myright;
2804 inner_node *myleftparent, *myrightparent;
2809 myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
2810 myleftparent = leftparent;
2813 myleft = inner->childid[slot - 1];
2814 myleftparent = inner;
2817 if (slot == inner->slotuse) {
2818 myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
2819 myrightparent = rightparent;
2822 myright = inner->childid[slot + 1];
2823 myrightparent = inner;
2826 BTREE_PRINT(
"erase_one_descend into " << inner->childid[slot]);
2829 inner->childid[slot],
2831 myleftparent, myrightparent,
2843 if (parent && parentslot < parent->slotuse)
2845 BTREE_PRINT(
"Fixing lastkeyupdate: key " << result.lastkey <<
" into parent " << parent <<
" at parentslot " << parentslot);
2848 parent->slotkey[parentslot] = result.lastkey;
2852 BTREE_PRINT(
"Forwarding lastkeyupdate: key " << result.lastkey);
2860 if (inner->childid[slot]->slotuse != 0)
2868 std::copy(inner->slotkey + slot, inner->slotkey + inner->slotuse,
2869 inner->slotkey + slot-1);
2870 std::copy(inner->childid + slot+1, inner->childid + inner->slotuse+1,
2871 inner->childid + slot);
2875 if (inner->level == 1)
2879 leaf_node *child =
static_cast<leaf_node*
>(inner->childid[slot]);
2880 inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
2884 if (inner->isunderflow() && !(inner ==
m_root && inner->
slotuse >= 1))
2887 if (leftinner == NULL && rightinner == NULL)
2892 m_root = inner->childid[0];
2902 else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
2904 if (leftparent == parent)
2905 myres |=
merge_inner(leftinner, inner, leftparent, parentslot - 1);
2907 myres |=
merge_inner(inner, rightinner, rightparent, parentslot);
2910 else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
2912 if (rightparent == parent)
2915 myres |=
merge_inner(leftinner, inner, leftparent, parentslot - 1);
2918 else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
2920 if (leftparent == parent)
2923 myres |=
merge_inner(inner, rightinner, rightparent, parentslot);
2927 else if (leftparent == rightparent)
2929 if (leftinner->slotuse <= rightinner->slotuse)
2936 if (leftparent == parent)
2964 node *left, node *right,
2965 inner_node *leftparent, inner_node *rightparent,
2966 inner_node *parent,
unsigned int parentslot)
2968 if (curr->isleafnode())
2970 leaf_node *leaf =
static_cast<leaf_node*
>(curr);
2971 leaf_node *leftleaf =
static_cast<leaf_node*
>(left);
2972 leaf_node *rightleaf =
static_cast<leaf_node*
>(right);
2976 if (leaf != iter.currnode)
2981 if (iter.currslot >= leaf->slotuse)
2983 BTREE_PRINT(
"Could not find iterator (" << iter.currnode <<
"," << iter.currslot <<
") to erase. Invalid leaf node?");
2988 int slot = iter.currslot;
2990 BTREE_PRINT(
"Found iterator in leaf " << curr <<
" at slot " << slot);
2992 std::copy(leaf->slotkey + slot+1, leaf->slotkey + leaf->slotuse,
2993 leaf->slotkey + slot);
2994 data_copy(leaf->slotdata + slot+1, leaf->slotdata + leaf->slotuse,
2995 leaf->slotdata + slot);
3003 if (slot == leaf->slotuse)
3005 if (parent && parentslot < parent->slotuse)
3008 parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
3012 if (leaf->slotuse >= 1)
3014 BTREE_PRINT(
"Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1]);
3024 if (leaf->isunderflow() && !(leaf ==
m_root && leaf->
slotuse >= 1))
3030 if (leftleaf == NULL && rightleaf == NULL)
3050 else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
3052 if (leftparent == parent)
3058 else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
3060 if (rightparent == parent)
3066 else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
3068 if (leftparent == parent)
3075 else if (leftparent == rightparent)
3077 if (leftleaf->slotuse <= rightleaf->slotuse)
3084 if (leftparent == parent)
3095 inner_node *inner =
static_cast<inner_node*
>(curr);
3096 inner_node *leftinner =
static_cast<inner_node*
>(left);
3097 inner_node *rightinner =
static_cast<inner_node*
>(right);
3105 while (slot <= inner->slotuse)
3107 node *myleft, *myright;
3108 inner_node *myleftparent, *myrightparent;
3111 myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
3112 myleftparent = leftparent;
3115 myleft = inner->childid[slot - 1];
3116 myleftparent = inner;
3119 if (slot == inner->slotuse) {
3120 myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
3121 myrightparent = rightparent;
3124 myright = inner->childid[slot + 1];
3125 myrightparent = inner;
3128 BTREE_PRINT(
"erase_iter_descend into " << inner->childid[slot]);
3131 inner->childid[slot],
3133 myleftparent, myrightparent,
3141 if (slot < inner->slotuse &&
key_less(inner->slotkey[slot],iter.key()))
3147 if (slot > inner->slotuse)
3154 if (parent && parentslot < parent->slotuse)
3156 BTREE_PRINT(
"Fixing lastkeyupdate: key " << result.lastkey <<
" into parent " << parent <<
" at parentslot " << parentslot);
3159 parent->slotkey[parentslot] = result.lastkey;
3163 BTREE_PRINT(
"Forwarding lastkeyupdate: key " << result.lastkey);
3171 if (inner->childid[slot]->slotuse != 0)
3179 std::copy(inner->slotkey + slot, inner->slotkey + inner->slotuse,
3180 inner->slotkey + slot-1);
3181 std::copy(inner->childid + slot+1, inner->childid + inner->slotuse+1,
3182 inner->childid + slot);
3186 if (inner->level == 1)
3190 leaf_node *child =
static_cast<leaf_node*
>(inner->childid[slot]);
3191 inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
3195 if (inner->isunderflow() && !(inner ==
m_root && inner->
slotuse >= 1))
3199 if (leftinner == NULL && rightinner == NULL)
3204 m_root = inner->childid[0];
3214 else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
3216 if (leftparent == parent)
3217 myres |=
merge_inner(leftinner, inner, leftparent, parentslot - 1);
3219 myres |=
merge_inner(inner, rightinner, rightparent, parentslot);
3222 else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
3224 if (rightparent == parent)
3227 myres |=
merge_inner(leftinner, inner, leftparent, parentslot - 1);
3230 else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
3232 if (leftparent == parent)
3235 myres |=
merge_inner(inner, rightinner, rightparent, parentslot);
3239 else if (leftparent == rightparent)
3241 if (leftinner->slotuse <= rightinner->slotuse)
3248 if (leftparent == parent)
3262 result_t
merge_leaves(leaf_node* left, leaf_node* right, inner_node* parent)
3264 BTREE_PRINT(
"Merge leaf nodes " << left <<
" and " << right <<
" with common parent " << parent <<
".");
3267 BTREE_ASSERT(left->isleafnode() && right->isleafnode());
3272 std::copy(right->slotkey, right->slotkey + right->slotuse,
3273 left->slotkey + left->slotuse);
3274 data_copy(right->slotdata, right->slotdata + right->slotuse,
3275 left->slotdata + left->slotuse);
3277 left->slotuse += right->slotuse;
3279 left->nextleaf = right->nextleaf;
3281 left->nextleaf->prevleaf = left;
3293 static result_t
merge_inner(inner_node* left, inner_node* right, inner_node* parent,
unsigned int parentslot)
3295 BTREE_PRINT(
"Merge inner nodes " << left <<
" and " << right <<
" with common parent " << parent <<
".");
3307 unsigned int leftslot = 0;
3308 while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3319 left->slotkey[left->slotuse] = parent->slotkey[parentslot];
3323 std::copy(right->slotkey, right->slotkey + right->slotuse,
3324 left->slotkey + left->slotuse);
3325 std::copy(right->childid, right->childid + right->slotuse+1,
3326 left->childid + left->slotuse);
3328 left->slotuse += right->slotuse;
3337 static result_t
shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent,
unsigned int parentslot)
3339 BTREE_ASSERT(left->isleafnode() && right->isleafnode());
3348 unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1;
3350 BTREE_PRINT(
"Shifting (leaf) " << shiftnum <<
" entries to left " << left <<
" from right " << right <<
" with common parent " << parent <<
".");
3356 std::copy(right->slotkey, right->slotkey + shiftnum,
3357 left->slotkey + left->slotuse);
3358 data_copy(right->slotdata, right->slotdata + shiftnum,
3359 left->slotdata + left->slotuse);
3361 left->slotuse += shiftnum;
3365 std::copy(right->slotkey + shiftnum, right->slotkey + right->slotuse,
3367 data_copy(right->slotdata + shiftnum, right->slotdata + right->slotuse,
3370 right->slotuse -= shiftnum;
3373 if (parentslot < parent->slotuse) {
3374 parent->slotkey[parentslot] = left->slotkey[left->slotuse - 1];
3385 static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent,
unsigned int parentslot)
3393 unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1;
3395 BTREE_PRINT(
"Shifting (inner) " << shiftnum <<
" entries to left " << left <<
" from right " << right <<
" with common parent " << parent <<
".");
3403 unsigned int leftslot = 0;
3404 while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3415 left->slotkey[left->slotuse] = parent->slotkey[parentslot];
3420 std::copy(right->slotkey, right->slotkey + shiftnum-1,
3421 left->slotkey + left->slotuse);
3422 std::copy(right->childid, right->childid + shiftnum,
3423 left->childid + left->slotuse);
3425 left->slotuse += shiftnum - 1;
3428 parent->slotkey[parentslot] = right->slotkey[shiftnum - 1];
3432 std::copy(right->slotkey + shiftnum, right->slotkey + right->slotuse,
3434 std::copy(right->childid + shiftnum, right->childid + right->slotuse+1,
3437 right->slotuse -= shiftnum;
3443 static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent,
unsigned int parentslot)
3445 BTREE_ASSERT(left->isleafnode() && right->isleafnode());
3454 unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1;
3456 BTREE_PRINT(
"Shifting (leaf) " << shiftnum <<
" entries to right " << right <<
" from left " << left <<
" with common parent " << parent <<
".");
3461 unsigned int leftslot = 0;
3462 while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3476 std::copy_backward(right->slotkey, right->slotkey + right->slotuse,
3477 right->slotkey + right->slotuse + shiftnum);
3479 right->slotdata + right->slotuse + shiftnum);
3481 right->slotuse += shiftnum;
3484 std::copy(left->slotkey + left->slotuse - shiftnum, left->slotkey + left->slotuse,
3486 data_copy(left->slotdata + left->slotuse - shiftnum, left->slotdata + left->slotuse,
3489 left->slotuse -= shiftnum;
3491 parent->slotkey[parentslot] = left->slotkey[left->slotuse-1];
3497 static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent,
unsigned int parentslot)
3505 unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1;
3507 BTREE_PRINT(
"Shifting (leaf) " << shiftnum <<
" entries to right " << right <<
" from left " << left <<
" with common parent " << parent <<
".");
3512 unsigned int leftslot = 0;
3513 while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3527 std::copy_backward(right->slotkey, right->slotkey + right->slotuse,
3528 right->slotkey + right->slotuse + shiftnum);
3529 std::copy_backward(right->childid, right->childid + right->slotuse+1,
3530 right->childid + right->slotuse+1 + shiftnum);
3532 right->slotuse += shiftnum;
3535 right->slotkey[shiftnum - 1] = parent->slotkey[parentslot];
3538 std::copy(left->slotkey + left->slotuse - shiftnum+1, left->slotkey + left->slotuse,
3540 std::copy(left->childid + left->slotuse - shiftnum+1, left->childid + left->slotuse+1,
3544 parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum];
3546 left->slotuse -= shiftnum;
3566 os <<
"leaves:" << std::endl;
3572 os <<
" " << n << std::endl;
3581 static void print_node(std::ostream &os,
const node* node,
unsigned int depth=0,
bool recursive=
false)
3583 for(
unsigned int i = 0; i < depth; i++) os <<
" ";
3585 os <<
"node " << node <<
" level " << node->level <<
" slotuse " << node->slotuse << std::endl;
3587 if (node->isleafnode())
3589 const leaf_node *leafnode =
static_cast<const leaf_node*
>(node);
3591 for(
unsigned int i = 0; i < depth; i++) os <<
" ";
3592 os <<
" leaf prev " << leafnode->prevleaf <<
" next " << leafnode->nextleaf << std::endl;
3594 for(
unsigned int i = 0; i < depth; i++) os <<
" ";
3596 for (
unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
3598 os << leafnode->slotkey[slot] <<
" ";
3604 const inner_node *innernode =
static_cast<const inner_node*
>(node);
3606 for(
unsigned int i = 0; i < depth; i++) os <<
" ";
3608 for (
unsigned short slot = 0; slot < innernode->slotuse; ++slot)
3610 os <<
"(" << innernode->childid[slot] <<
") " << innernode->slotkey[slot] <<
" ";
3612 os <<
"(" << innernode->childid[innernode->slotuse] <<
")" << std::endl;
3616 for (
unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
3618 print_node(os, innernode->childid[slot], depth + 1, recursive);
3654 if (n->isleafnode())
3656 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
3658 assert( leaf ==
m_root || !leaf->isunderflow() );
3659 assert( leaf->slotuse > 0 );
3661 for(
unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot)
3663 assert(
key_lessequal(leaf->slotkey[slot], leaf->slotkey[slot + 1]));
3666 *minkey = leaf->slotkey[0];
3667 *maxkey = leaf->slotkey[leaf->slotuse - 1];
3670 vstats.itemcount += leaf->slotuse;
3674 const inner_node *inner =
static_cast<const inner_node*
>(n);
3675 vstats.innernodes++;
3677 assert( inner ==
m_root || !inner->isunderflow() );
3678 assert( inner->slotuse > 0 );
3680 for(
unsigned short slot = 0; slot < inner->slotuse - 1; ++slot)
3682 assert(
key_lessequal(inner->slotkey[slot], inner->slotkey[slot + 1]));
3685 for(
unsigned short slot = 0; slot <= inner->slotuse; ++slot)
3687 const node *subnode = inner->childid[slot];
3691 assert(subnode->level + 1 == inner->level);
3692 verify_node(subnode, &subminkey, &submaxkey, vstats);
3694 BTREE_PRINT(
"verify subnode " << subnode <<
": " << subminkey <<
" - " << submaxkey);
3697 *minkey = subminkey;
3701 if (slot == inner->slotuse)
3702 *maxkey = submaxkey;
3704 assert(
key_equal(inner->slotkey[slot], submaxkey));
3706 if (inner->level == 1 && slot < inner->slotuse)
3710 const leaf_node *leafa =
static_cast<const leaf_node*
>(inner->childid[slot]);
3711 const leaf_node *leafb =
static_cast<const leaf_node*
>(inner->childid[slot + 1]);
3713 assert(leafa->nextleaf == leafb);
3714 assert(leafa == leafb->prevleaf);
3715 (void)leafa; (void)leafb;
3717 if (inner->level == 2 && slot < inner->slotuse)
3720 const inner_node *parenta =
static_cast<const inner_node*
>(inner->childid[slot]);
3721 const inner_node *parentb =
static_cast<const inner_node*
>(inner->childid[slot+1]);
3723 const leaf_node *leafa =
static_cast<const leaf_node*
>(parenta->childid[parenta->slotuse]);
3724 const leaf_node *leafb =
static_cast<const leaf_node*
>(parentb->childid[0]);
3726 assert(leafa->nextleaf == leafb);
3727 assert(leafa == leafb->prevleaf);
3728 (void)leafa; (void)leafb;
3739 assert(n->level == 0);
3740 assert(!n || n->prevleaf == NULL);
3742 unsigned int testcount = 0;
3746 assert(n->level == 0);
3747 assert(n->slotuse > 0);
3749 for(
unsigned short slot = 0; slot < n->slotuse - 1; ++slot)
3751 assert(
key_lessequal(n->slotkey[slot], n->slotkey[slot + 1]));
3754 testcount += n->slotuse;
3758 assert(
key_lessequal(n->slotkey[n->slotuse-1], n->nextleaf->slotkey[0]));
3760 assert(n == n->nextleaf->prevleaf);
3770 assert(testcount ==
size());
3845 struct dump_header header;
3847 header.itemcount =
size();
3849 os.write(reinterpret_cast<char*>(&header),
sizeof(header));
3862 struct dump_header fileheader;
3863 is.read(reinterpret_cast<char*>(&fileheader),
sizeof(fileheader));
3864 if (!is.good())
return false;
3866 struct dump_header myheader;
3868 myheader.itemcount = fileheader.itemcount;
3870 if (!myheader.same(fileheader))
3872 BTREE_PRINT(
"btree::restore: file header does not match instantiation signature.");
3878 if (fileheader.itemcount > 0)
3881 if (
m_root == NULL)
return false;
3901 if (n->isleafnode())
3903 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
3905 os.write(reinterpret_cast<const char*>(leaf),
sizeof(*leaf));
3909 const inner_node *inner =
static_cast<const inner_node*
>(n);
3911 os.write(reinterpret_cast<const char*>(inner),
sizeof(*inner));
3913 for(
unsigned short slot = 0; slot <= inner->slotuse; ++slot)
3915 const node *subnode = inner->childid[slot];
3933 is.read(reinterpret_cast<char*>(&nu.top),
sizeof(nu.top));
3934 if (!is.good())
return NULL;
3936 if (nu.top.isleafnode())
3939 is.read(reinterpret_cast<char*>(&nu.leaf) +
sizeof(nu.top),
sizeof(nu.leaf) -
sizeof(nu.top));
3940 if (!is.good())
return NULL;
3963 is.read(reinterpret_cast<char*>(&nu.inner) +
sizeof(nu.top),
sizeof(nu.inner) -
sizeof(nu.top));
3964 if (!is.good())
return NULL;
3969 *newinner = nu.inner;
3971 for(
unsigned short slot = 0; slot <= newinner->slotuse; ++slot)
3983 #endif // _STX_BTREE_H_
static OutputIterator data_copy_backward(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
static const bool selfverify
If true, the tree will self verify it's invariants after each insert() or erase().
node * restore_node(std::istream &is)
Read the dump image and construct a tree from the node order in the serialization.
bool allow_duplicates
Allow duplicates.
_Alloc::template rebind< inner_node >::other alloc_type
Define an related allocator for the inner_node structs.
static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
Function class to compare value_type objects. Required by the STL.
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
void swap(btree_self &from)
Fast swapping of two identical B+ tree objects.
tree_stats m_stats
Other small statistics about the B+ tree.
size_type size() const
Return the number of key/data pairs in the B+ tree.
bool isunderflow() const
True if node has too few entries.
struct node * copy_recursive(const node *n)
Recursively copy nodes from another B+ tree object.
STL-like read-only iterator object for B+ tree items.
self operator--(int)
Postfix– backstep the iterator to the last slot.
void split_leaf_node(leaf_node *leaf, key_type *_newkey, node **_newleaf)
Split up a leaf node into two equally-filled sibling leaves.
bool has(result_flags_t f) const
Test if this result object has a given flag set.
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
void set_slot(unsigned short slot, const key_type &key)
Set the key pair in slot.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
bool isfull() const
True if the node's slots are full.
void verify_leaflinks() const
Verify the double linked list of leaves.
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...
btree::key_type key_type
The key type of the btree. Returned by key().
const key_type & key() const
Key of the current slot.
size_t size_type
Size type used to count keys.
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.
btree::value_type value_type
The value type of the btree. Returned by operator*().
size_type innernodes
Number of inner nodes in the B+ tree.
bool key_less(const key_type &a, const key_type b) const
True if a < b ? "constructed" from m_key_less()
Extended structure of a inner node in-memory.
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ? constructed from key_less().
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
static const unsigned short leafslots
Base B+ tree parameter: The number of key/data slots in each leaf.
pointer operator->() const
Dereference the iterator.
Generates default traits for a B+ tree used as a set.
bool operator<(const btree_self &other) const
Total ordering relation of B+ trees of the same type.
ptrdiff_t difference_type
STL-magic.
btree::pair_type pair_type
The pair type of the btree.
btree::value_type value_type
The value type of the btree. Returned by operator*().
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
data_type & data() const
Writable reference to the current data object.
value_type operator()(pair_type &p) const
Identity "convert" a real pair type to just the first component.
Basic class implementing a base B+ tree data structure in memory.
result_t(result_flags_t f, const key_type &k)
Constructor with a lastkey value.
void clear_recursive(node *n)
Recursively free up nodes.
data_type slotdata[used_as_set?1:leafslotmax]
Array of data.
iterator(const reverse_iterator &it)
Copy-constructor from a reverse iterator.
bool isfull() const
True if the node's slots are full.
leaf_node * allocate_leaf()
Allocate and initialize a leaf node.
double avgfill_leaves() const
Return the average fill of leaves.
static const unsigned short innerslots
Base B+ tree parameter: The number of key slots in each inner node.
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().
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
static result_t merge_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Merge two inner nodes.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
bool operator<=(const btree_self &other) const
Less-equal relation. Based on operator<.
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
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::leaf_node * currnode
The currently referenced leaf node of the 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...
node * childid[innerslotmax+1]
Pointers to children.
unsigned short leafslots
Number of slots in the leaves.
bool isfew() const
True if few used entries, less than half full.
const value_type * pointer
Pointer to the value_type. STL required.
pointer operator->() const
Dereference the iterator.
reference operator*() const
Dereference the iterator.
leaf_node::alloc_type leaf_node_allocator()
Return an allocator for leaf_node objects.
value_type * pointer
Pointer to the value_type. STL required.
btree(const btree_self &other)
Copy constructor.
void initialize()
Set variables to initial values.
self operator++(int)
Postfix++ advance the iterator to the next slot.
result_t & operator|=(const result_t &other)
Merge two results OR-ing the result flags and overwriting lastkeys.
A small struct containing basic statistics about the B+ tree.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
reference operator*() const
Dereference the iterator.
self & operator--()
Prefix– backstep the iterator to the next slot.
btree::pair_type pair_type
The pair type of the btree.
Deletion successful and no fix-ups necessary.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
bool operator>(const btree_self &other) const
Greater relation. Based on operator<.
void verify() const
Run a thorough verification of all B+ tree invariants.
bool key_lessequal(const key_type &a, const key_type b) const
True if a <= b ? constructed from key_less()
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...
key_compare key_comp
Key comparison function from the template parameter.
unsigned short currslot
Current key/data slot referenced.
leaf_node * m_tailleaf
Pointer to last leaf in the double linked leaf chain.
ptrdiff_t difference_type
STL-magic.
void initialize(const unsigned short l)
Delayed initialisation of constructed node.
leaf_node * m_headleaf
Pointer to first leaf in the double linked leaf chain.
self operator--(int)
Postfix– backstep the iterator to the last slot.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
size_type leaves
Number of leaves in the B+ tree.
iterator insert(iterator, const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
result_flags_t flags
Merged result flags.
btree::leaf_node * currnode
The currently referenced leaf node of the tree.
value_type operator()(const pair_type &p) const
Identity "convert" a real pair type to just the first component.
self & operator++()
Prefix++ advance the iterator to the next slot.
The header structure of each node in-memory.
unsigned short slotuse
Number of key slotuse use, so number of valid children or data pointers.
self operator++(int)
Postfix++ advance the iterator to the previous slot.
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...
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
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...
self & operator--()
Prefix– backstep the iterator to the last slot.
const value_type & reference
Reference to the value_type. STL required.
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...
bool operator!=(const self &x) const
Inequality of iterators.
inner_node * allocate_inner(unsigned short level)
Allocate and initialize an inner node.
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
bool operator==(const self &x) const
Equality of iterators.
const_iterator(const const_reverse_iterator &it)
Copy-constructor from a const reverse iterator.
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
result_flags_t
Result flags of recursive deletion.
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
bool operator>=(const btree_self &other) const
Greater-equal relation. Based on operator<.
_Data data_type
Second template parameter: The data type associated with each key.
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...
const_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const iterator.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
static const int innerslots
Number of slots in each inner node of the tree.
std::pair< iterator, bool > insert_start(const key_type &key, const data_type &value)
Start the insertion descent at the current root and handle root splits.
Deletion successful, children nodes were merged and the parent needs to remove the empty node...
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Deletion successful, the last key was updated so parent slotkeys need updates.
bool same(const struct dump_header &o) const
Returns true if the headers have the same vital properties.
~btree()
Frees up all used B+ tree memory pages.
btree::data_type data_type
The data type of the btree. Returned by data().
btree(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
const key_type & key() const
Key of the current slot.
unsigned short currslot
Current key/data slot referenced.
result_t erase_iter_descend(const iterator &iter, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot)
Erase one key/data pair referenced by an iterator in the B+ tree.
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
data_type & data() const
Writable reference to the current data object.
unsigned short currslot
One slot past the current key/data slot referenced.
key_type slotkey[leafslotmax]
Keys of children or data pointers.
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
int find_upper(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater than key.
leaf_node * nextleaf
Double linked list pointers to traverse the leaves.
btree::value_type value_type
The value type of the btree. Returned by operator*().
node * m_root
Pointer to the B+ tree's root node, either leaf or inner node.
size_type nodes() const
Return the total number of nodes.
value_compare(key_compare kc)
Constructor called from btree::value_comp()
key_compare m_key_less
Key comparison object.
btree::data_type data_type
The data type of the btree. Returned by data().
bool operator()(const value_type &x, const value_type &y) const
Function call "less"-operator resulting in true if x < y.
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
bool isleafnode() const
True if this is a leaf node.
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...
A header for the binary image containing the base properties of the B+ tree.
self & operator++()
Prefix++ advance the iterator to the previous slot.
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
value_type & reference
Reference to the value_type. STL required.
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
btree::pair_type pair_type
The pair type of the btree.
btree(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last).
const key_type & key() const
Key of the current slot.
btree(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
const_reverse_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const reverse iterator.
const data_type & data() const
Read-only reference to the current data object.
inner_node::alloc_type inner_node_allocator()
Return an allocator for inner_node objects.
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
#define BTREE_MAX(a, b)
The maximum of a and b. Used in some compile-time formulas.
static const int leafslots
Number of slots in each leaf of the tree.
allocator_type m_allocator
Memory allocator.
bool operator!=(const btree_self &other) const
Inequality relation. Based on operator==.
Extended structure of a leaf node in memory.
const_reverse_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
static void print_node(std::ostream &os, const node *node, unsigned int depth=0, bool recursive=false)
Recursively descend down the tree and print out nodes.
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 exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
bool isunderflow() const
True if node has too few entries.
key_type slotkey[innerslotmax]
Keys of children or data pointers.
unsigned short data_type_size
sizeof(data_type)
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
_Value value_type
Third template parameter: Composition pair of key and data types, this is required by the STL standar...
self & operator++()
Prefix++ advance the iterator to the next slot.
self operator++(int)
Postfix++ advance the iterator to the next slot.
reverse_iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable reverse iterator.
ptrdiff_t difference_type
STL-magic.
btree::value_type value_type
The value type of the btree. Returned by operator*().
_Compare key_compare
Fourth template parameter: Key comparison function object.
STL-like mutable reverse iterator object for B+ tree items.
static const bool selfverify
If true, the tree will self verify it's invariants after each insert() or erase().
void split_inner_node(inner_node *inner, key_type *_newkey, node **_newinner, unsigned int addslot)
Split up an inner node into two equally-filled sibling nodes.
#define BTREE_PRINT(x)
Print out debug information to std::cout if BTREE_DEBUG is defined.
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
size_type itemcount
The item count of the tree.
_Traits traits
Fifth template parameter: Traits object used to define more parameters of the B+ tree.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
const_iterator()
Default-Constructor of a const iterator.
iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable iterator.
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...
key_type lastkey
The key to be updated at the parent's slot.
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
value_type operator()(const pair_type &p) const
Convert a fake pair type to just the first component.
bool operator==(const self &x) const
Equality of iterators.
tree_stats()
Zero initialized.
value_type * pointer
Pointer to the value_type. STL required.
void initialize(const unsigned short l)
Set variables to initial values.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
size_type itemcount
Number of items in the B+ tree.
char signature[12]
"stx-btree", just to stop the restore() function from loading garbage
const value_type * pointer
Pointer to the value_type. STL required.
const key_type & key() const
Key of the current slot.
static const bool used_as_set
Eighth template parameter: boolean indicator whether the btree is used as a set.
bool operator!=(const self &x) const
Inequality of iterators.
bool operator!=(const self &x) const
Inequality of iterators.
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
btree_pair_to_value< value_type, pair_type > pair_to_value_type
Using template specialization select the correct converter used by the iterators. ...
Deletion not successful because key was not found.
static const int innerslots
Number of slots in each inner node of the tree.
self & operator--()
Prefix– backstep the iterator to the last slot.
const value_type & reference
Reference to the value_type. STL required.
self operator--(int)
Postfix– backstep the iterator to the last slot.
STL-like read-only reverse iterator object for B+ tree items.
btree::key_type key_type
The key type of the btree. Returned by key().
leaf_node * prevleaf
Double linked list pointers to traverse the leaves.
void fill()
Fill the struct with the current B+ tree's properties, itemcount is not filled.
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
iterator insert2(iterator, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
unsigned short innerslots
Number of slots in the inner nodes.
bool key_greaterequal(const key_type &a, const key_type b) const
True if a >= b ? constructed from key_less()
self & operator++()
Prefix++ advance the iterator to the next slot.
static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
value_type & reference
Reference to the value_type. STL required.
result_t erase_one_descend(const key_type &key, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot)
Erase one (the first) key/data pair in the B+ tree matching key.
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
_Key key_type
First template parameter: The key type of the B+ tree.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
void set_slot(unsigned short slot, const pair_type &value)
Set the (key,data) pair in slot.
self operator--(int)
Postfix– backstep the iterator to the next slot.
int 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.
void free_node(node *n)
Correctly free either inner or leaf node, destructs all contained key and value objects.
unsigned short key_type_size
sizeof(key_type)
unsigned short version
Currently 0.
reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
unsigned short level
Level in the b-tree, if level == 0 -> leaf node.
_Alloc allocator_type
Seventh template parameter: STL allocator for tree nodes.
iterator()
Default-Constructor of a mutable iterator.
void dump_node(std::ostream &os, const node *n) const
Recursively descend down the tree and dump each node in a precise order.
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
std::pair< iterator, bool > insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
result_t merge_leaves(leaf_node *left, leaf_node *right, inner_node *parent)
Merge two leaf nodes.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
std::pair< key_type, data_type > pair_type
The pair of key_type and data_type, this may be different from value_type.
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...
btree::key_type key_type
The key type of the btree. Returned by key().
std::pair< iterator, bool > insert(const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
static OutputIterator data_copy(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
const data_type & data() const
Read-only reference to the current data object.
bool operator==(const btree_self &other) const
Equality relation of B+ trees of the same type.
static const int leafslots
Number of slots in each leaf of the tree.
pointer operator->() const
Dereference the iterator.
#define BTREE_ASSERT(x)
Assertion only if BTREE_DEBUG is defined. This is not used in verify().
ptrdiff_t difference_type
STL-magic.
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
bool operator==(const self &x) const
Equality of iterators.
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
btree< key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set > btree_self
Typedef of our own type.
bool operator==(const self &x) const
Equality of iterators.
_Alloc::template rebind< leaf_node >::other alloc_type
Define an related allocator for the leaf_node structs.
bool isfew() const
True if few used entries, less than half full.
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...
btree::data_type data_type
The data type of the btree. Returned by data().
bool operator!=(const self &x) const
Inequality of iterators.
STL-like iterator object for B+ tree items.
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
unsigned short currslot
One slot past the current key/data slot referenced.
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
self & operator--()
Prefix– backstep the iterator to the last slot.
btree::data_type data_type
The data type of the btree. Returned by data().
std::pair< iterator, bool > insert_descend(node *n, const key_type &key, const data_type &value, key_type *splitkey, node **splitnode)
Insert an item into the B+ tree.
btree_self & operator=(const btree_self &other)
*** Fast Copy: Assign Operator and Copy Constructors
static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
Generates default traits for a B+ tree used as a map.
const_reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
static const unsigned short innerslotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
allocator_type get_allocator() const
Return the base node allocator provided during construction.
reverse_iterator()
Default-Constructor of a reverse iterator.
btree::pair_type pair_type
The pair type of the btree.
void clear()
Frees all key/data pairs and all nodes of the tree.
pointer operator->() const
Dereference the iterator.
value_type operator()(pair_type &p) const
Convert a fake pair type to just the first component.
B+ tree recursive deletion has much information which is needs to be passed upward.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
self operator++(int)
Postfix++ advance the iterator to the next slot.
For sets the second pair_type is an empty struct, so the value_type should only be the first...
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
btree::key_type key_type
The key type of the btree. Returned by key().