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_ 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...
reference operator*() const
Dereference the iterator.
btree::pair_type pair_type
The pair type of the btree.
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.
A small struct containing basic statistics about the B+ tree.
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
btree::key_type key_type
The key type of the btree. Returned by key().
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.
result_t merge_leaves(leaf_node *left, leaf_node *right, inner_node *parent)
Merge two leaf nodes.
void verify() const
Run a thorough verification of all B+ tree invariants.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
bool key_lessequal(const key_type &a, const key_type b) const
True if a <= b ? constructed from key_less()
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
const value_type * pointer
Pointer to the value_type. STL required.
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
bool operator==(const self &x) const
Equality of iterators.
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
unsigned short slotuse
Number of key slotuse use, so number of valid children or data pointers.
self operator--(int)
Postfix– backstep the iterator to the last slot.
value_type operator()(pair_type &p) const
Convert a fake pair type to just the first component.
bool operator==(const self &x) const
Equality of iterators.
const value_type & reference
Reference to the value_type. STL required.
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
unsigned short key_type_size
sizeof(key_type)
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
const_iterator(const const_reverse_iterator &it)
Copy-constructor from a const reverse iterator.
bool isfull() const
True if the node's slots are full.
unsigned short currslot
One slot past the current key/data slot referenced.
allocator_type m_allocator
Memory allocator.
bool operator!=(const btree_self &other) const
Inequality relation. Based on operator==.
Generates default traits for a B+ tree used as a map.
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
self & operator--()
Prefix– backstep the iterator to the last slot.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
_Key key_type
First template parameter: The key type of the B+ tree.
pointer operator->() const
Dereference the iterator.
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.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
value_type * pointer
Pointer to the value_type. STL required.
reverse_iterator()
Default-Constructor of a reverse iterator.
value_type operator()(pair_type &p) const
Identity "convert" a real pair type to just the first component.
void fill()
Fill the struct with the current B+ tree's properties, itemcount is not filled.
_Alloc allocator_type
Seventh template parameter: STL allocator for tree nodes.
void dump_node(std::ostream &os, const node *n) const
Recursively descend down the tree and dump each node in a precise order.
leaf_node * nextleaf
Double linked list pointers to traverse the leaves.
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
tree_stats()
Zero initialized.
unsigned short innerslots
Number of slots in the inner nodes.
Function class to compare value_type objects. Required by the STL.
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
void initialize(const unsigned short l)
Set variables to initial values.
bool operator()(const value_type &x, const value_type &y) const
Function call "less"-operator resulting in true if x < y.
unsigned short currslot
Current key/data slot referenced.
unsigned short data_type_size
sizeof(data_type)
bool operator==(const btree_self &other) const
Equality relation of B+ trees of the same type.
void initialize(const unsigned short l)
Delayed initialisation of constructed node.
STL-like mutable reverse iterator object for B+ tree items.
self operator--(int)
Postfix– backstep the iterator to the last slot.
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...
const value_type * pointer
Pointer to the value_type. STL required.
void swap(btree_self &from)
Fast swapping of two identical B+ tree objects.
tree_stats m_stats
Other small statistics about the B+ 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.
btree(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last).
self operator++(int)
Postfix++ advance the iterator to the next slot.
leaf_node * prevleaf
Double linked list pointers to traverse the leaves.
void set_slot(unsigned short slot, const key_type &key)
Set the key pair in slot.
key_type slotkey[leafslotmax]
Keys of children or data pointers.
bool operator==(const self &x) const
Equality of iterators.
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
key_type lastkey
The key to be updated at the parent's slot.
Extended structure of a leaf node in memory.
const_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const iterator.
static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
btree::value_type value_type
The value type of the btree. Returned by operator*().
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
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()
static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
self operator++(int)
Postfix++ advance the iterator to the next slot.
bool operator<(const btree_self &other) const
Total ordering relation of B+ trees of the same type.
void free_node(node *n)
Correctly free either inner or leaf node, destructs all contained key and value objects.
btree::value_type value_type
The value type of the btree. Returned by operator*().
data_type & data() const
Writable reference to the current data object.
void initialize()
Set variables to initial values.
_Compare key_compare
Fourth template parameter: Key comparison function object.
self & operator++()
Prefix++ advance the iterator to the next slot.
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.
self & operator--()
Prefix– backstep the iterator to the last slot.
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...
iterator(const reverse_iterator &it)
Copy-constructor from a reverse iterator.
bool operator==(const self &x) const
Equality of iterators.
double avgfill_leaves() const
Return the average fill of leaves.
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.
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
size_type itemcount
Number of items in the B+ tree.
const data_type & data() const
Read-only reference to the current data object.
static result_t merge_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Merge two inner nodes.
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...
btree::data_type data_type
The data type of the btree. Returned by data().
unsigned short currslot
Current key/data slot referenced.
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
pointer operator->() const
Dereference the iterator.
btree::pair_type pair_type
The pair type of the btree.
btree(const btree_self &other)
Copy constructor.
struct node * copy_recursive(const node *n)
Recursively copy nodes from another B+ tree object.
self & operator--()
Prefix– 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.
const key_type & key() const
Key of the current slot.
data_type & data() const
Writable reference to the current data object.
unsigned short currslot
One slot past the current key/data slot referenced.
unsigned short version
Currently 0.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
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...
const data_type & data() const
Read-only reference to the current data object.
static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
STL-like read-only reverse iterator object for B+ tree items.
void verify_leaflinks() const
Verify the double linked list of leaves.
#define BTREE_MAX(a, b)
The maximum of a and b. Used in some compile-time formulas.
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
ptrdiff_t difference_type
STL-magic.
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.
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.
size_type leaves
Number of leaves in the B+ tree.
const_reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ? constructed from key_less().
self operator--(int)
Postfix– backstep the iterator to the next slot.
STL-like iterator object for B+ tree items.
ptrdiff_t difference_type
STL-magic.
value_type & reference
Reference to the value_type. STL required.
btree::value_type value_type
The value type of the btree. Returned by operator*().
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++(int)
Postfix++ advance the iterator to the previous slot.
bool has(result_flags_t f) const
Test if this result object has a given flag set.
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...
unsigned short level
Level in the b-tree, if level == 0 -> leaf node.
result_flags_t
Result flags of recursive deletion.
leaf_node * allocate_leaf()
Allocate and initialize a leaf node.
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
std::pair< iterator, bool > insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
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<.
std::pair< key_type, data_type > pair_type
The pair of key_type and data_type, this may be different from value_type.
bool isunderflow() const
True if node has too few entries.
static const int innerslots
Number of slots in each inner node of the tree.
B+ tree recursive deletion has much information which is needs to be passed upward.
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...
static OutputIterator data_copy(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
node * restore_node(std::istream &is)
Read the dump image and construct a tree from the node order in the serialization.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
bool operator<=(const btree_self &other) const
Less-equal relation. Based on operator<.
static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
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 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...
bool operator!=(const self &x) const
Inequality of iterators.
bool operator!=(const self &x) const
Inequality of iterators.
ptrdiff_t difference_type
STL-magic.
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
reverse_iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable reverse iterator.
const key_type & key() const
Key of the current slot.
void set_slot(unsigned short slot, const pair_type &value)
Set the (key,data) pair in slot.
STX - Some Template Extensions namespace.
bool isunderflow() const
True if node has too few entries.
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.
self operator--(int)
Postfix– backstep the iterator to the last slot.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
self & operator--()
Prefix– backstep the iterator to the next slot.
bool isfull() const
True if the node's slots are full.
A header for the binary image containing the base properties of the B+ tree.
bool operator>(const btree_self &other) const
Greater relation. Based on operator<.
self & operator++()
Prefix++ advance the iterator to the next slot.
value_compare(key_compare kc)
Constructor called from btree::value_comp()
value_type * pointer
Pointer to the value_type. STL required.
const key_type & key() const
Key of the current slot.
leaf_node * m_tailleaf
Pointer to last leaf in the double linked leaf chain.
bool allow_duplicates
Allow duplicates.
STL-like read-only iterator object for B+ tree items.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
bool same(const struct dump_header &o) const
Returns true if the headers have the same vital properties.
iterator insert(iterator, const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
void clear()
Frees all key/data pairs and all nodes of the tree.
pointer operator->() const
Dereference the iterator.
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
btree::key_type key_type
The key type of the btree. Returned by key().
reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
data_type slotdata[used_as_set?1:leafslotmax]
Array of data.
const_reverse_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const reverse iterator.
bool operator!=(const self &x) const
Inequality of iterators.
static const size_t binsearch_threshold
As of stx-btree-0.9, the code does linear search in find_lower() and find_upper() instead of binary_s...
static const int leafslots
Number of slots in each leaf of the tree.
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
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.
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().
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
For sets the second pair_type is an empty struct, so the value_type should only be the first...
key_compare key_comp
Key comparison function from the template parameter.
static OutputIterator data_copy_backward(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
_Alloc::template rebind< inner_node >::other alloc_type
Define an related allocator for the inner_node structs.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
pointer operator->() const
Dereference the iterator.
value_type & reference
Reference to the value_type. STL required.
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
#define BTREE_ASSERT(x)
Assertion only if BTREE_DEBUG is defined. This is not used in verify().
self & operator++()
Prefix++ advance the iterator to the next slot.
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
size_type size() const
Return the number of key/data pairs in the B+ tree.
reference operator*() const
Dereference the iterator.
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into 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...
_Alloc::template rebind< leaf_node >::other alloc_type
Define an related allocator for the leaf_node structs.
_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.
btree::data_type data_type
The data type of the btree. Returned by data().
iterator()
Default-Constructor of a mutable iterator.
value_type operator()(const pair_type &p) const
Convert a fake pair type to just the first component.
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::value_type value_type
The value type of the btree. Returned by operator*().
key_compare m_key_less
Key comparison object.
btree::data_type data_type
The data type of the btree. Returned by data().
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...
size_t size_type
Size type used to count keys.
btree::key_type key_type
The key type of the btree. Returned by key().
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.
const key_type & key() const
Key of the current slot.
leaf_node * m_headleaf
Pointer to first leaf in the double linked leaf chain.
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Extended structure of a inner node in-memory.
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
self & operator++()
Prefix++ advance the iterator to the previous slot.
ptrdiff_t difference_type
STL-magic.
btree::pair_type pair_type
The pair type of the btree.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
btree_pair_to_value< value_type, pair_type > pair_to_value_type
Using template specialization select the correct converter used by the iterators. ...
Generates default traits for a B+ tree used as a set.
result_flags_t flags
Merged result flags.
btree::pair_type pair_type
The pair type of the btree.
const value_type & reference
Reference to the value_type. STL required.
void clear_recursive(node *n)
Recursively free up nodes.
size_type itemcount
The item count of the tree.
bool isfew() const
True if few used entries, less than half full.
btree(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
inner_node * allocate_inner(unsigned short level)
Allocate and initialize an inner node.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Basic class implementing a base B+ tree data structure in memory.
inner_node::alloc_type inner_node_allocator()
Return an allocator for inner_node objects.
bool operator!=(const self &x) const
Inequality of iterators.
self operator++(int)
Postfix++ advance the iterator to the next slot.
iterator insert2(iterator, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
bool key_greaterequal(const key_type &a, const key_type b) const
True if a >= b ? constructed from key_less()
_Data data_type
Second template parameter: The data type associated with each key.
btree::data_type data_type
The data type of the btree. Returned by data().
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
The header structure of each node in-memory.
static const bool selfverify
If true, the tree will self verify it's invariants after each insert() or erase().
btree::leaf_node * currnode
The currently referenced leaf node of the tree.
_Value value_type
Third template parameter: Composition pair of key and data types, this is required by the STL standar...
~btree()
Frees up all used B+ tree memory pages.
btree(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
unsigned short leafslots
Number of slots in the leaves.
bool isfew() const
True if few used entries, less than half full.
leaf_node::alloc_type leaf_node_allocator()
Return an allocator for leaf_node objects.
result_t(result_flags_t f, const key_type &k)
Constructor with a lastkey value.