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>
120 static const bool selfverify =
false;
126 static const bool debug =
false;
130 static const int leafslots =
BTREE_MAX( 8, 256 / (
sizeof(_Key) +
sizeof(_Data)) );
134 static const int innerslots =
BTREE_MAX( 8, 256 / (
sizeof(_Key) +
sizeof(
void*)) );
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 >
191 static const bool allow_duplicates = _Duplicates;
201 static const bool used_as_set = _UsedAsSet;
212 typedef btree<key_type, data_type, value_type, key_compare,
213 traits, allow_duplicates, allocator_type, used_as_set>
btree_self;
225 static const unsigned short leafslotmax = traits::leafslots;
229 static const unsigned short innerslotmax = traits::innerslots;
234 static const unsigned short minleafslots = (leafslotmax / 2);
239 static const unsigned short mininnerslots = (innerslotmax / 2);
243 static const bool selfverify = traits::selfverify;
248 static const bool debug = traits::debug;
283 typedef typename _Alloc::template rebind<inner_node>::other
alloc_type;
286 key_type slotkey[innerslotmax];
300 return (node::slotuse == innerslotmax);
306 return (node::slotuse <= mininnerslots);
312 return (node::slotuse < mininnerslots);
322 typedef typename _Alloc::template rebind<leaf_node>::other
alloc_type;
331 key_type slotkey[leafslotmax];
334 data_type slotdata[used_as_set ? 1 : leafslotmax];
340 prevleaf = nextleaf = NULL;
346 return (node::slotuse == leafslotmax);
352 return (node::slotuse <= minleafslots);
358 return (node::slotuse < minleafslots);
363 inline void set_slot(
unsigned short slot,
const pair_type& value)
367 slotkey[slot] = value.first;
368 slotdata[slot] = value.second;
373 inline void set_slot(
unsigned short slot,
const key_type& key)
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;
482 friend class btree<key_type, data_type, value_type, key_compare,
483 traits, allow_duplicates, allocator_type, used_as_set>;
499 : currnode(NULL), currslot(0)
504 : currnode(l), currslot(s)
509 : currnode(it.currnode), currslot(it.currslot)
516 temp_value = pair_to_value_type()( pair_type(key(),data()) );
525 temp_value = pair_to_value_type()( pair_type(key(),data()) );
530 inline const key_type&
key()
const 532 return currnode->
slotkey[currslot];
538 return currnode->
slotdata[used_as_set ? 0 : currslot];
544 if (currslot + 1 < currnode->
slotuse) {
547 else if (currnode->
nextleaf != NULL) {
564 if (currslot + 1 < currnode->
slotuse) {
567 else if (currnode->
nextleaf != NULL) {
585 else if (currnode->
prevleaf != NULL) {
587 currslot = currnode->
slotuse - 1;
605 else if (currnode->
prevleaf != NULL) {
607 currslot = currnode->
slotuse - 1;
620 return (x.currnode == currnode) && (x.currslot == currslot);
626 return (x.currnode != currnode) || (x.currslot != currslot);
691 : currnode(NULL), currslot(0)
696 : currnode(l), currslot(s)
701 : currnode(it.currnode), currslot(it.currslot)
706 : currnode(it.currnode), currslot(it.currslot)
711 : currnode(it.currnode), currslot(it.currslot)
719 temp_value = pair_to_value_type()( pair_type(key(),data()) );
728 temp_value = pair_to_value_type()( pair_type(key(),data()) );
733 inline const key_type&
key()
const 735 return currnode->
slotkey[currslot];
739 inline const data_type&
data()
const 741 return currnode->
slotdata[used_as_set ? 0 : currslot];
747 if (currslot + 1 < currnode->
slotuse) {
750 else if (currnode->
nextleaf != NULL) {
767 if (currslot + 1 < currnode->
slotuse) {
770 else if (currnode->
nextleaf != NULL) {
788 else if (currnode->
prevleaf != NULL) {
790 currslot = currnode->
slotuse - 1;
808 else if (currnode->
prevleaf != NULL) {
810 currslot = currnode->
slotuse - 1;
823 return (x.currnode == currnode) && (x.currslot == currslot);
829 return (x.currnode != currnode) || (x.currslot != currslot);
902 : currnode(NULL), currslot(0)
907 : currnode(l), currslot(s)
912 : currnode(it.currnode), currslot(it.currslot)
920 temp_value = pair_to_value_type()( pair_type(key(),data()) );
930 temp_value = pair_to_value_type()( pair_type(key(),data()) );
935 inline const key_type&
key()
const 938 return currnode->
slotkey[currslot - 1];
945 return currnode->
slotdata[used_as_set ? 0 : currslot-1];
954 else if (currnode->
prevleaf != NULL) {
974 else if (currnode->
prevleaf != NULL) {
989 if (currslot < currnode->slotuse) {
992 else if (currnode->
nextleaf != NULL) {
1009 if (currslot < currnode->slotuse) {
1012 else if (currnode->
nextleaf != NULL) {
1027 return (x.currnode == currnode) && (x.currslot == currslot);
1033 return (x.currnode != currnode) || (x.currslot != currslot);
1098 : currnode(NULL), currslot(0)
1103 : currnode(l), currslot(s)
1108 : currnode(it.currnode), currslot(it.currslot)
1113 : currnode(it.currnode), currslot(it.currslot)
1118 : currnode(it.currnode), currslot(it.currslot)
1127 temp_value = pair_to_value_type()( pair_type(key(),data()) );
1137 temp_value = pair_to_value_type()( pair_type(key(),data()) );
1142 inline const key_type&
key()
const 1145 return currnode->
slotkey[currslot - 1];
1149 inline const data_type&
data()
const 1152 return currnode->
slotdata[used_as_set ? 0 : currslot-1];
1161 else if (currnode->
prevleaf != NULL) {
1181 else if (currnode->
prevleaf != NULL) {
1196 if (currslot < currnode->slotuse) {
1199 else if (currnode->
nextleaf != NULL) {
1216 if (currslot < currnode->slotuse) {
1219 else if (currnode->
nextleaf != NULL) {
1234 return (x.currnode == currnode) && (x.currslot == currslot);
1240 return (x.currnode != currnode) || (x.currslot != currslot);
1261 static const unsigned short leafslots = btree_self::leafslotmax;
1264 static const unsigned short innerslots = btree_self::innerslotmax;
1269 leaves(0), innernodes(0)
1276 return innernodes + leaves;
1282 return static_cast<double>(itemcount) / (leaves * leafslots);
1313 explicit inline btree(
const allocator_type &alloc = allocator_type())
1314 : m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), m_allocator(alloc)
1320 explicit inline btree(
const key_compare &kcf,
1321 const allocator_type &alloc = allocator_type())
1322 : m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL),
1323 m_key_less(kcf), m_allocator(alloc)
1330 template <
class InputIterator>
1331 inline btree(InputIterator first, InputIterator last,
1332 const allocator_type &alloc = allocator_type())
1333 : m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), m_allocator(alloc)
1335 insert(first, last);
1341 template <
class InputIterator>
1342 inline btree(InputIterator first, InputIterator last,
const key_compare &kcf,
1343 const allocator_type &alloc = allocator_type())
1344 : m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL),
1345 m_key_less(kcf), m_allocator(alloc)
1347 insert(first, last);
1359 std::swap(m_root, from.
m_root);
1362 std::swap(m_stats, from.
m_stats);
1383 friend class btree<key_type, data_type, value_type, key_compare,
1384 traits, allow_duplicates, allocator_type, used_as_set>;
1388 inline bool operator()(
const value_type& x,
const value_type& y)
const 1390 return key_comp(x.first, y.first);
1404 return value_compare(m_key_less);
1411 inline bool key_less(
const key_type &a,
const key_type b)
const 1413 return m_key_less(a, b);
1419 return !m_key_less(b, a);
1425 return m_key_less(b, a);
1431 return !m_key_less(a, b);
1436 inline bool key_equal(
const key_type &a,
const key_type &b)
const 1438 return !m_key_less(a, b) && !m_key_less(b, a);
1456 return typename leaf_node::alloc_type(m_allocator);
1462 return typename inner_node::alloc_type(m_allocator);
1468 leaf_node *n =
new (leaf_node_allocator().allocate(1)) leaf_node();
1477 inner_node *n =
new (inner_node_allocator().allocate(1)) inner_node();
1478 n->initialize(level);
1479 m_stats.innernodes++;
1487 if (n->isleafnode()) {
1488 leaf_node *ln =
static_cast<leaf_node*
>(n);
1489 typename leaf_node::alloc_type a(leaf_node_allocator());
1491 a.deallocate(ln, 1);
1495 inner_node *in =
static_cast<inner_node*
>(n);
1496 typename inner_node::alloc_type a(inner_node_allocator());
1498 a.deallocate(in, 1);
1499 m_stats.innernodes--;
1505 template<
class InputIterator,
class OutputIterator>
1506 static OutputIterator
data_copy (InputIterator first, InputIterator last,
1507 OutputIterator result)
1509 if (used_as_set)
return result;
1510 else return std::copy(first, last, result);
1515 template<
class InputIterator,
class OutputIterator>
1517 OutputIterator result)
1519 if (used_as_set)
return result;
1520 else return std::copy_backward(first, last, result);
1531 clear_recursive(m_root);
1535 m_headleaf = m_tailleaf = NULL;
1537 m_stats = tree_stats();
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)
1562 clear_recursive(innernode->childid[slot]);
1563 free_node(innernode->childid[slot]);
1575 return iterator(m_headleaf, 0);
1582 return iterator(m_tailleaf, m_tailleaf ? m_tailleaf->slotuse : 0);
1589 return const_iterator(m_headleaf, 0);
1594 inline const_iterator
end()
const 1596 return const_iterator(m_tailleaf, m_tailleaf ? m_tailleaf->slotuse : 0);
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>
1635 inline int find_lower(
const node_type *n,
const key_type& key)
const 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;
1647 if (key_lessequal(key, n->slotkey[mid])) {
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>
1682 inline int find_upper(
const node_type *n,
const key_type& key)
const 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;
1730 return m_stats.itemcount;
1736 return (size() == size_type(0));
1743 return size_type(-1);
1759 const node *n = m_root;
1760 if (!n)
return false;
1762 while(!n->isleafnode())
1764 const inner_node *inner =
static_cast<const inner_node*
>(n);
1765 int slot = find_lower(inner, key);
1767 n = inner->childid[slot];
1770 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1772 int slot = find_lower(leaf, key);
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);
1786 int slot = find_lower(inner, key);
1788 n = inner->childid[slot];
1791 leaf_node *leaf =
static_cast<leaf_node*
>(n);
1793 int slot = find_lower(leaf, key);
1794 return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
1795 ? iterator(leaf, slot) : end();
1800 const_iterator
find(
const key_type &key)
const 1802 const node *n = m_root;
1803 if (!n)
return end();
1805 while(!n->isleafnode())
1807 const inner_node *inner =
static_cast<const inner_node*
>(n);
1808 int slot = find_lower(inner, key);
1810 n = inner->childid[slot];
1813 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1815 int slot = find_lower(leaf, key);
1816 return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
1817 ? const_iterator(leaf, slot) : end();
1822 size_type
count(
const key_type &key)
const 1824 const node *n = m_root;
1827 while(!n->isleafnode())
1829 const inner_node *inner =
static_cast<const inner_node*
>(n);
1830 int slot = find_lower(inner, key);
1832 n = inner->childid[slot];
1835 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1837 int slot = find_lower(leaf, key);
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);
1863 int slot = find_lower(inner, key);
1865 n = inner->childid[slot];
1868 leaf_node *leaf =
static_cast<leaf_node*
>(n);
1870 int slot = find_lower(leaf, key);
1871 return iterator(leaf, slot);
1879 const node *n = m_root;
1880 if (!n)
return end();
1882 while(!n->isleafnode())
1884 const inner_node *inner =
static_cast<const inner_node*
>(n);
1885 int slot = find_lower(inner, key);
1887 n = inner->childid[slot];
1890 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1892 int slot = find_lower(leaf, key);
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);
1906 int slot = find_upper(inner, key);
1908 n = inner->childid[slot];
1911 leaf_node *leaf =
static_cast<leaf_node*
>(n);
1913 int slot = find_upper(leaf, key);
1914 return iterator(leaf, slot);
1922 const node *n = m_root;
1923 if (!n)
return end();
1925 while(!n->isleafnode())
1927 const inner_node *inner =
static_cast<const inner_node*
>(n);
1928 int slot = find_upper(inner, key);
1930 n = inner->childid[slot];
1933 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
1935 int slot = find_upper(leaf, key);
1936 return const_iterator(leaf, slot);
1942 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
1946 inline std::pair<const_iterator, const_iterator>
equal_range(
const key_type& key)
const 1948 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
1959 return (size() == other.
size()) && std::equal(begin(), end(), other.
begin());
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);
1997 inline btree_self& operator= (
const btree_self &other)
2006 if (other.
size() != 0)
2008 m_stats.leaves = m_stats.innernodes = 0;
2010 m_root = copy_recursive(other.
m_root);
2015 if (selfverify) verify();
2023 : m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL),
2024 m_stats( other.m_stats ),
2025 m_key_less( other.key_comp() ),
2026 m_allocator( other.get_allocator() )
2030 m_stats.leaves = m_stats.innernodes = 0;
2032 m_root = copy_recursive(other.
m_root);
2034 if (selfverify) verify();
2042 if (n->isleafnode())
2044 const leaf_node *leaf =
static_cast<const leaf_node*
>(n);
2045 leaf_node *newleaf = allocate_leaf();
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);
2051 if (m_headleaf == NULL)
2053 m_headleaf = m_tailleaf = newleaf;
2054 newleaf->prevleaf = newleaf->nextleaf = NULL;
2058 newleaf->prevleaf = m_tailleaf;
2059 m_tailleaf->nextleaf = newleaf;
2060 m_tailleaf = newleaf;
2067 const inner_node *inner =
static_cast<const inner_node*
>(n);
2068 inner_node *newinner = allocate_inner(inner->level);
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)
2075 newinner->childid[slot] = copy_recursive(inner->childid[slot]);
2088 inline std::pair<iterator, bool>
insert(
const pair_type& x)
2090 return insert_start(x.first, x.second);
2097 inline std::pair<iterator, bool>
insert(
const key_type& key,
const data_type& data)
2099 return insert_start(key, data);
2106 inline std::pair<iterator, bool>
insert2(
const key_type& key,
const data_type& data)
2108 return insert_start(key, data);
2113 inline iterator
insert(iterator ,
const pair_type &x)
2115 return insert_start(x.first, x.second).first;
2120 inline iterator
insert2(iterator ,
const key_type& key,
const data_type& data)
2122 return insert_start(key, data).first;
2128 template <
typename InputIterator>
2129 inline void insert(InputIterator first, InputIterator last)
2131 InputIterator iter = first;
2144 std::pair<iterator, bool>
insert_start(
const key_type& key,
const data_type& value)
2146 node *newchild = NULL;
2147 key_type newkey = key_type();
2149 if (m_root == NULL) {
2150 m_root = m_headleaf = m_tailleaf = allocate_leaf();
2153 std::pair<iterator, bool> r = insert_descend(m_root, key, value, &newkey, &newchild);
2157 inner_node *newroot = allocate_inner(m_root->level + 1);
2158 newroot->slotkey[0] = newkey;
2160 newroot->childid[0] = m_root;
2161 newroot->childid[1] = newchild;
2163 newroot->slotuse = 1;
2169 if (r.second) ++m_stats.itemcount;
2172 if (debug) print(std::cout);
2191 const key_type& key,
const data_type& value,
2192 key_type* splitkey, node** splitnode)
2194 if (!n->isleafnode())
2196 inner_node *inner =
static_cast<inner_node*
>(n);
2198 key_type newkey = key_type();
2199 node *newchild = NULL;
2201 int slot = find_lower(inner, key);
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())
2214 split_inner_node(inner, splitkey, splitnode, slot);
2216 BTREE_PRINT(
"btree::insert_descend done split_inner: putslot: " << slot <<
" putkey: " << newkey <<
" upkey: " << *splitkey);
2221 print_node(std::cout, inner);
2222 print_node(std::cout, *splitnode);
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);
2280 int slot = find_lower(leaf, key);
2282 if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) {
2283 return std::pair<iterator, bool>(iterator(leaf, slot),
false);
2288 split_leaf_node(leaf, splitkey, splitnode);
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);
2303 data_copy_backward(leaf->slotdata + slot, leaf->slotdata + leaf->slotuse,
2304 leaf->slotdata + leaf->slotuse+1);
2306 leaf->slotkey[slot] = key;
2307 if (!used_as_set) leaf->slotdata[slot] = value;
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);
2332 leaf_node *newleaf = allocate_leaf();
2334 newleaf->slotuse = leaf->slotuse - mid;
2336 newleaf->nextleaf = leaf->nextleaf;
2337 if (newleaf->nextleaf == NULL) {
2339 m_tailleaf = newleaf;
2342 newleaf->nextleaf->prevleaf = newleaf;
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;
2362 void split_inner_node(inner_node* inner, key_type* _newkey, node** _newinner,
unsigned int addslot)
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");
2379 inner_node *newinner = allocate_inner(inner->level);
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>
2405 m_stats.itemcount = iend - ibegin;
2408 size_t num_items = iend - ibegin;
2409 size_t num_leaves = (num_items + leafslotmax-1) / leafslotmax;
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)
2417 leaf_node* leaf = allocate_leaf();
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);
2425 if (m_tailleaf != NULL) {
2426 m_tailleaf->nextleaf = leaf;
2427 leaf->prevleaf = m_tailleaf;
2434 num_items -= leaf->slotuse;
2440 if (m_headleaf == m_tailleaf) {
2441 m_root = m_headleaf;
2448 size_t num_parents = (num_leaves + (innerslotmax+1)-1) / (innerslotmax+1);
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];
2456 leaf_node* leaf = m_headleaf;
2457 for (
size_t i = 0; i < num_parents; ++i)
2460 inner_node* n = allocate_inner(1);
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;
2489 num_parents = (num_children + (innerslotmax+1)-1) / (innerslotmax+1);
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)
2497 inner_node* n = allocate_inner(level);
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;
2527 if (selfverify) verify();
2540 btree_not_found = 1,
2544 btree_update_lastkey = 2,
2564 : flags(f), lastkey()
2569 : flags(f), lastkey(k)
2575 return (flags & f) != 0;
2584 if (other.
has(btree_update_lastkey))
2598 BTREE_PRINT(
"btree::erase_one(" << key <<
") on btree size " << size());
2600 if (selfverify) verify();
2602 if (!m_root)
return false;
2604 result_t result = erase_one_descend(key, m_root, NULL, NULL, NULL, NULL, NULL, 0);
2606 if (!result.has(btree_not_found))
2607 --m_stats.itemcount;
2610 if (debug) print(std::cout);
2612 if (selfverify) verify();
2614 return !result.has(btree_not_found);
2623 while( erase_one(key) )
2626 if (!allow_duplicates)
break;
2635 BTREE_PRINT(
"btree::erase_iter(" << iter.currnode <<
"," << iter.currslot <<
") on btree size " << size());
2637 if (selfverify) verify();
2639 if (!m_root)
return;
2641 result_t result = erase_iter_descend(iter, m_root, NULL, NULL, NULL, NULL, NULL, 0);
2643 if (!result.has(btree_not_found))
2644 --m_stats.itemcount;
2647 if (debug) print(std::cout);
2649 if (selfverify) verify();
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);
2685 int slot = find_lower(leaf, key);
2687 if (slot >= leaf->slotuse || !key_equal(key, leaf->slotkey[slot]))
2689 BTREE_PRINT(
"Could not find key " << key <<
" to erase.");
2691 return btree_not_found;
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);
2703 result_t myres = btree_ok;
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]);
2719 myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
2728 if (leaf->isunderflow() && !(leaf == m_root && leaf->slotuse >= 1))
2734 if (leftleaf == NULL && rightleaf == NULL)
2741 m_root = leaf = NULL;
2742 m_headleaf = m_tailleaf = NULL;
2754 else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
2756 if (leftparent == parent)
2757 myres |= merge_leaves(leftleaf, leaf, leftparent);
2759 myres |= merge_leaves(leaf, rightleaf, rightparent);
2762 else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
2764 if (rightparent == parent)
2765 myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2767 myres |= merge_leaves(leftleaf, leaf, leftparent);
2770 else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
2772 if (leftparent == parent)
2773 shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2775 myres |= merge_leaves(leaf, rightleaf, rightparent);
2779 else if (leftparent == rightparent)
2781 if (leftleaf->slotuse <= rightleaf->slotuse)
2782 myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2784 shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2788 if (leftparent == parent)
2789 shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2791 myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
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;
2806 int slot = find_lower(inner, key);
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]);
2828 result_t result = erase_one_descend(key,
2829 inner->childid[slot],
2831 myleftparent, myrightparent,
2834 result_t myres = btree_ok;
2836 if (result.has(btree_not_found))
2841 if (result.has(btree_update_lastkey))
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);
2853 myres |= result_t(btree_update_lastkey, result.lastkey);
2857 if (result.has(btree_fixmerge))
2860 if (inner->childid[slot]->slotuse != 0)
2866 free_node(inner->childid[slot]);
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)
2913 shift_left_inner(inner, rightinner, rightparent, parentslot);
2915 myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
2918 else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
2920 if (leftparent == parent)
2921 shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2923 myres |= merge_inner(inner, rightinner, rightparent, parentslot);
2927 else if (leftparent == rightparent)
2929 if (leftinner->slotuse <= rightinner->slotuse)
2930 shift_left_inner(inner, rightinner, rightparent, parentslot);
2932 shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2936 if (leftparent == parent)
2937 shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2939 shift_left_inner(inner, rightinner, rightparent, parentslot);
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)
2978 return btree_not_found;
2981 if (iter.currslot >= leaf->slotuse)
2983 BTREE_PRINT(
"Could not find iterator (" << iter.currnode <<
"," << iter.currslot <<
") to erase. Invalid leaf node?");
2985 return btree_not_found;
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);
2999 result_t myres = btree_ok;
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]);
3015 myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
3024 if (leaf->isunderflow() && !(leaf == m_root && leaf->slotuse >= 1))
3030 if (leftleaf == NULL && rightleaf == NULL)
3037 m_root = leaf = NULL;
3038 m_headleaf = m_tailleaf = NULL;
3050 else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
3052 if (leftparent == parent)
3053 myres |= merge_leaves(leftleaf, leaf, leftparent);
3055 myres |= merge_leaves(leaf, rightleaf, rightparent);
3058 else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
3060 if (rightparent == parent)
3061 myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
3063 myres |= merge_leaves(leftleaf, leaf, leftparent);
3066 else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
3068 if (leftparent == parent)
3069 shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
3071 myres |= merge_leaves(leaf, rightleaf, rightparent);
3075 else if (leftparent == rightparent)
3077 if (leftleaf->slotuse <= rightleaf->slotuse)
3078 myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
3080 shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
3084 if (leftparent == parent)
3085 shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
3087 myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
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);
3103 int slot = find_lower(inner, iter.key());
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]);
3130 result = erase_iter_descend(iter,
3131 inner->childid[slot],
3133 myleftparent, myrightparent,
3136 if (!result.has(btree_not_found))
3141 if (slot < inner->slotuse && key_less(inner->slotkey[slot],iter.key()))
3142 return btree_not_found;
3147 if (slot > inner->slotuse)
3148 return btree_not_found;
3150 result_t myres = btree_ok;
3152 if (result.has(btree_update_lastkey))
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);
3164 myres |= result_t(btree_update_lastkey, result.lastkey);
3168 if (result.has(btree_fixmerge))
3171 if (inner->childid[slot]->slotuse != 0)
3177 free_node(inner->childid[slot]);
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)
3225 shift_left_inner(inner, rightinner, rightparent, parentslot);
3227 myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
3230 else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
3232 if (leftparent == parent)
3233 shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
3235 myres |= merge_inner(inner, rightinner, rightparent, parentslot);
3239 else if (leftparent == rightparent)
3241 if (leftinner->slotuse <= rightinner->slotuse)
3242 shift_left_inner(inner, rightinner, rightparent, parentslot);
3244 shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
3248 if (leftparent == parent)
3249 shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
3251 shift_left_inner(inner, rightinner, rightparent, parentslot);
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());
3270 BTREE_ASSERT(left->slotuse + right->slotuse < leafslotmax);
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;
3287 return btree_fixmerge;
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 <<
".");
3302 BTREE_ASSERT(left->slotuse + right->slotuse < innerslotmax);
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;
3331 return btree_fixmerge;
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];
3378 return result_t(btree_update_lastkey, 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);
3478 data_copy_backward(right->slotdata, right->slotdata + right->slotuse,
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)
3525 BTREE_ASSERT(right->slotuse + shiftnum < innerslotmax);
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;
3559 print_node(os, m_root, 0,
true);
3566 os <<
"leaves:" << std::endl;
3568 const leaf_node *n = m_headleaf;
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);
3632 key_type minkey, maxkey;
3637 verify_node(m_root, &minkey, &maxkey, vstats);
3639 assert( vstats.itemcount == m_stats.itemcount );
3640 assert( vstats.leaves == m_stats.leaves );
3641 assert( vstats.innernodes == m_stats.innernodes );
3650 void verify_node(
const node* n, key_type* minkey, key_type* maxkey, tree_stats &vstats)
const 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];
3688 key_type subminkey = key_type();
3689 key_type submaxkey = key_type();
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;
3699 assert(key_greaterequal(subminkey, inner->slotkey[slot-1]));
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;
3737 const leaf_node *n = m_headleaf;
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);
3764 assert(m_tailleaf == n);
3770 assert(testcount == size());
3810 signature[0] =
's'; signature[1] =
't'; signature[2] =
'x'; signature[3] =
'-';
3811 signature[4] =
'b'; signature[5] =
't'; signature[6] =
'r'; signature[7] =
'e';
3812 signature[8] =
'e'; signature[9] = 0; signature[10] = 0; signature[11] = 0;
3817 leafslots = btree_self::leafslotmax;
3818 innerslots = btree_self::innerslotmax;
3819 allow_duplicates = btree_self::allow_duplicates;
3825 return (signature[0] ==
's' && signature[1] ==
't' && signature[2] ==
'x' && signature[3] ==
'-' &&
3826 signature[4] ==
'b' && signature[5] ==
't' && signature[6] ==
'r' && signature[7] ==
'e' &&
3827 signature[8] ==
'e' && signature[9] == 0 && signature[10] == 0 && signature[11] == 0)
3845 struct dump_header header;
3847 header.itemcount = size();
3849 os.write(reinterpret_cast<char*>(&header),
sizeof(header));
3852 dump_node(os, m_root);
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)
3880 m_root = restore_node(is);
3881 if (m_root == NULL)
return false;
3883 m_stats.itemcount = fileheader.itemcount;
3887 if (debug) print(std::cout);
3889 if (selfverify) verify();
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];
3917 dump_node(os, subnode);
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;
3942 leaf_node *newleaf = allocate_leaf();
3948 if (m_headleaf == NULL) {
3950 m_headleaf = m_tailleaf = newleaf;
3953 newleaf->prevleaf = m_tailleaf;
3954 m_tailleaf->nextleaf = newleaf;
3955 m_tailleaf = newleaf;
3963 is.read(reinterpret_cast<char*>(&nu.inner) +
sizeof(nu.top),
sizeof(nu.inner) -
sizeof(nu.top));
3964 if (!is.good())
return NULL;
3966 inner_node *newinner = allocate_inner(0);
3969 *newinner = nu.inner;
3971 for(
unsigned short slot = 0; slot <= newinner->slotuse; ++slot)
3973 newinner->childid[slot] = restore_node(is);
3983 #endif // _STX_BTREE_H_ std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
self operator--(int)
Postfix– backstep the iterator to the last slot.
For sets the second pair_type is an empty struct, so the value_type should only be the first...
btree::value_type value_type
The value type of the btree. Returned by operator*().
struct node * copy_recursive(const node *n)
Recursively copy nodes from another B+ tree object.
unsigned short currslot
Current key/data slot referenced.
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
static OutputIterator data_copy(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
btree::value_type value_type
The value type of the btree. Returned by operator*().
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
bool isunderflow() const
True if node has too few entries.
leaf_node::alloc_type leaf_node_allocator()
Return an allocator for leaf_node objects.
btree::data_type data_type
The data type of the btree. Returned by data().
self & operator--()
Prefix– backstep the iterator to the last slot.
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
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.
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...
node * restore_node(std::istream &is)
Read the dump image and construct a tree from the node order in the serialization.
data_type & data() const
Writable reference to the current data object.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
const_iterator()
Default-Constructor of a const iterator.
bool isfew() const
True if few used entries, less than half full.
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...
B+ tree recursive deletion has much information which is needs to be passed upward.
leaf_node * m_tailleaf
Pointer to last leaf in the double linked leaf chain.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
pointer operator->() const
Dereference the iterator.
#define BTREE_MAX(a, b)
The maximum of a and b. Used in some compile-time formulas.
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
leaf_node * m_headleaf
Pointer to first leaf in the double linked leaf chain.
bool operator>(const btree_self &other) const
Greater relation. Based on operator<.
Basic class implementing a base B+ tree data structure in memory.
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...
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
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...
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
STL-like read-only reverse iterator object for B+ tree items.
result_flags_t flags
Merged result flags.
const value_type & reference
Reference to the value_type. STL required.
btree(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
_Key key_type
First template parameter: The key type of the B+ tree.
STL-like iterator object for B+ tree items.
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.
Extended structure of a leaf node in memory.
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
bool operator!=(const self &x) const
Inequality of iterators.
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
static result_t merge_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Merge two inner nodes.
btree::key_type key_type
The key type of the btree. Returned by key().
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
#define BTREE_PRINT(x)
Print out debug information to std::cout if BTREE_DEBUG is defined.
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
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...
unsigned short currslot
One slot past the current key/data slot referenced.
const key_type & key() const
Key of the current slot.
bool isleafnode() const
True if this is a leaf node.
reverse_iterator()
Default-Constructor of a reverse iterator.
bool allow_duplicates
Allow duplicates.
void free_node(node *n)
Correctly free either inner or leaf node, destructs all contained key and value objects.
bool operator>=(const btree_self &other) const
Greater-equal relation. Based on operator<.
reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
STX - Some Template Extensions namespace.
Function class to compare value_type objects. Required by the STL.
data_type & data() const
Writable reference to the current data object.
size_type innernodes
Number of inner nodes in the B+ tree.
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
STL-like mutable reverse iterator object for B+ tree items.
reference operator*() const
Dereference the iterator.
bool key_less(const key_type &a, const key_type b) const
True if a < b ? "constructed" from m_key_less()
int find_upper(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater than key.
key_type slotkey[leafslotmax]
Keys of children or data pointers.
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
std::pair< key_type, data_type > pair_type
The pair of key_type and data_type, this may be different from value_type.
_Data data_type
Second template parameter: The data type associated with each key.
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.
reference operator*() const
Dereference the iterator.
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.
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
btree_pair_to_value< value_type, pair_type > pair_to_value_type
Using template specialization select the correct converter used by the iterators. ...
result_t merge_leaves(leaf_node *left, leaf_node *right, inner_node *parent)
Merge two leaf nodes.
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...
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
unsigned short innerslots
Number of slots in the inner nodes.
bool operator!=(const btree_self &other) const
Inequality relation. Based on operator==.
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...
void set_slot(unsigned short slot, const key_type &key)
Set the key pair in slot.
ptrdiff_t difference_type
STL-magic.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
key_type lastkey
The key to be updated at the parent's slot.
result_flags_t
Result flags of recursive deletion.
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
bool operator!=(const self &x) const
Inequality of iterators.
self & operator++()
Prefix++ advance the iterator to the next slot.
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
A header for the binary image containing the base properties of the B+ tree.
leaf_node * prevleaf
Double linked list pointers to traverse the 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...
void initialize()
Set variables to initial values.
static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
result_t(result_flags_t f, const key_type &k)
Constructor with a lastkey value.
static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
bool isunderflow() const
True if node has too few entries.
key_compare m_key_less
Key comparison object.
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.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
unsigned short currslot
Current key/data slot referenced.
std::pair< iterator, bool > insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
bool operator==(const self &x) const
Equality of iterators.
Extended structure of a inner node in-memory.
void clear()
Frees all key/data pairs and all nodes of the tree.
reverse_iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable reverse iterator.
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
btree(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last).
Generates default traits for a B+ tree used as a map.
leaf_node * nextleaf
Double linked list pointers to traverse the leaves.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
ptrdiff_t difference_type
STL-magic.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
ptrdiff_t difference_type
STL-magic.
bool operator==(const self &x) const
Equality of iterators.
allocator_type m_allocator
Memory allocator.
static OutputIterator data_copy_backward(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
void verify_leaflinks() const
Verify the double linked list of leaves.
void dump_node(std::ostream &os, const node *n) const
Recursively descend down the tree and dump each node in a precise order.
unsigned short version
Currently 0.
btree::key_type key_type
The key type of the btree. Returned by key().
bool has(result_flags_t f) const
Test if this result object has a given flag set.
iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable iterator.
tree_stats m_stats
Other small statistics about the B+ tree.
btree::value_type value_type
The value type of the btree. Returned by operator*().
bool operator==(const self &x) const
Equality of iterators.
unsigned short leafslots
Number of slots in the leaves.
value_compare(key_compare kc)
Constructor called from btree::value_comp()
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().
std::pair< iterator, bool > insert(const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
_Value value_type
Third template parameter: Composition pair of key and data types, this is required by the STL standar...
bool operator()(const value_type &x, const value_type &y) const
Function call "less"-operator resulting in true if x < y.
bool operator<(const btree_self &other) const
Total ordering relation of B+ trees of the same type.
size_t size_type
Size type used to count keys.
ptrdiff_t difference_type
STL-magic.
The header structure of each node in-memory.
btree::pair_type pair_type
The pair type of the btree.
btree(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
self operator--(int)
Postfix– backstep the iterator to the next slot.
Generates default traits for a B+ tree used as a set.
size_type itemcount
The item count of the tree.
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
const_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const iterator.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
key_compare key_comp
Key comparison function from the template parameter.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
iterator insert2(iterator, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
iterator(const reverse_iterator &it)
Copy-constructor from a reverse iterator.
self operator++(int)
Postfix++ advance the iterator to the next slot.
iterator insert(iterator, const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
bool operator!=(const self &x) const
Inequality of iterators.
_Compare key_compare
Fourth template parameter: Key comparison function object.
btree::data_type data_type
The data type of the btree. Returned by data().
bool isfew() const
True if few used entries, less than half full.
bool isfull() const
True if the node's slots are full.
const_reverse_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const reverse iterator.
inner_node * allocate_inner(unsigned short level)
Allocate and initialize an inner node.
void fill()
Fill the struct with the current B+ tree's properties, itemcount is not filled.
#define BTREE_ASSERT(x)
Assertion only if BTREE_DEBUG is defined. This is not used in verify().
leaf_node * allocate_leaf()
Allocate and initialize a leaf node.
self & operator++()
Prefix++ advance the iterator to the next slot.
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
const value_type * pointer
Pointer to the value_type. STL required.
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
const key_type & key() const
Key of the current slot.
unsigned short key_type_size
sizeof(key_type)
btree::key_type key_type
The key type of the btree. Returned by key().
size_type nodes() const
Return the total number of nodes.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
btree(const btree_self &other)
Copy constructor.
const key_type & key() const
Key of the current slot.
size_type leaves
Number of leaves in the B+ tree.
unsigned short level
Level in the b-tree, if level == 0 -> leaf node.
self & operator++()
Prefix++ advance the iterator to the previous slot.
value_type * pointer
Pointer to the value_type. STL required.
value_type & reference
Reference to the value_type. STL required.
btree::pair_type pair_type
The pair type of the btree.
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
void set_slot(unsigned short slot, const pair_type &value)
Set the (key,data) pair in slot.
double avgfill_leaves() const
Return the average fill of leaves.
const value_type * pointer
Pointer to the value_type. STL required.
const_reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
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...
static const bool selfverify
If true, the tree will self verify it's invariants after each insert() or erase().
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
const value_type & reference
Reference to the value_type. STL required.
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...
bool key_greaterequal(const key_type &a, const key_type b) const
True if a >= b ? constructed from key_less()
self & operator--()
Prefix– backstep the iterator to the last slot.
value_type & reference
Reference to the value_type. STL required.
btree::data_type data_type
The data type of the btree. Returned by data().
void initialize(const unsigned short l)
Set variables to initial values.
btree::pair_type pair_type
The pair type of the btree.
const data_type & data() const
Read-only reference to the current data object.
unsigned short data_type_size
sizeof(data_type)
unsigned short currslot
One slot past the current key/data slot referenced.
self operator++(int)
Postfix++ advance the iterator to the next slot.
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
btree::leaf_node * currnode
The currently referenced leaf node of the tree.
const_iterator(const const_reverse_iterator &it)
Copy-constructor from a const reverse iterator.
btree::data_type data_type
The data type of the btree. Returned by data().
size_type size() const
Return the number of key/data pairs in the B+ tree.
btree::value_type value_type
The value type of the btree. Returned by operator*().
bool operator==(const btree_self &other) const
Equality relation of B+ trees of the same type.
btree::leaf_node * currnode
The currently referenced leaf node of the tree.
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.
_Traits traits
Fifth template parameter: Traits object used to define more parameters of the B+ tree.
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
A small struct containing basic statistics about the B+ tree.
value_type operator()(const pair_type &p) const
Convert a fake pair type to just the first component.
btree::pair_type pair_type
The pair type of the btree.
bool operator<=(const btree_self &other) const
Less-equal relation. Based on operator<.
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::key_type key_type
The key type of the btree. Returned by key().
bool key_lessequal(const key_type &a, const key_type b) const
True if a <= b ? constructed from key_less()
bool isfull() const
True if the node's slots are full.
~btree()
Frees up all used B+ tree memory pages.
void verify() const
Run a thorough verification of all B+ tree invariants.
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
self operator++(int)
Postfix++ advance the iterator to the previous slot.
_Alloc allocator_type
Seventh template parameter: STL allocator for tree nodes.
tree_stats()
Zero initialized.
self & operator--()
Prefix– backstep the iterator to the last slot.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
btree< key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set > btree_self
Typedef of our own type.
pointer operator->() const
Dereference the iterator.
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ? constructed from key_less().
static const int innerslots
Number of slots in each inner node of the tree.
inner_node::alloc_type inner_node_allocator()
Return an allocator for inner_node objects.
const data_type & data() const
Read-only reference to the current data object.
value_type operator()(const pair_type &p) const
Identity "convert" a real pair type to just the first component.
void swap(btree_self &from)
Fast swapping of two identical B+ tree objects.
value_type * pointer
Pointer to the value_type. STL required.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
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.
data_type slotdata[used_as_set ? 1 :leafslotmax]
Array of data.
void clear_recursive(node *n)
Recursively free up nodes.
void split_leaf_node(leaf_node *leaf, key_type *_newkey, node **_newleaf)
Split up a leaf node into two equally-filled sibling leaves.
node * m_root
Pointer to the B+ tree's root node, either leaf or inner node.
_Alloc::template rebind< inner_node >::other alloc_type
Define an related allocator for the inner_node structs.
unsigned short slotuse
Number of key slotuse use, so number of valid children or data pointers.
self & operator--()
Prefix– backstep the iterator to the next slot.
self & operator++()
Prefix++ advance the iterator to the next slot.
iterator()
Default-Constructor of a mutable iterator.
static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
void initialize(const unsigned short l)
Delayed initialisation of constructed node.
self operator++(int)
Postfix++ advance the iterator to the next slot.
pointer operator->() const
Dereference the iterator.
self operator--(int)
Postfix– backstep the iterator to the last slot.
size_type itemcount
Number of items in the B+ tree.
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.
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
static const int leafslots
Number of slots in each leaf of the tree.
STL-like read-only iterator object for B+ tree items.
value_type operator()(pair_type &p) const
Convert a fake pair type to just the first component.
bool operator!=(const self &x) const
Inequality of iterators.
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...
pointer operator->() const
Dereference the iterator.
bool same(const struct dump_header &o) const
Returns true if the headers have the same vital properties.
const key_type & key() const
Key of the current slot.
value_type operator()(pair_type &p) const
Identity "convert" a real pair type to just the first component.
self operator--(int)
Postfix– backstep the iterator to the last slot.