STX B+ Tree Template Classes  0.9
btree.h
Go to the documentation of this file.
1 /**
2  * \file include/stx/btree.h
3  * Contains the main B+ tree implementation template class btree.
4  */
5 
6 /*
7  * STX B+ Tree Template Classes v0.9
8  * Copyright (C) 2008-2013 Timo Bingmann <tb@panthema.net>
9  *
10  * Boost Software License - Version 1.0 - August 17th, 2003
11  *
12  * Permission is hereby granted, free of charge, to any person or organization
13  * obtaining a copy of the software and accompanying documentation covered by
14  * this license (the "Software") to use, reproduce, display, distribute,
15  * execute, and transmit the Software, and to prepare derivative works of the
16  * Software, and to permit third-parties to whom the Software is furnished to
17  * do so, all subject to the following:
18  *
19  * The copyright notices in the Software and this entire statement, including
20  * the above license grant, this restriction and the following disclaimer, must
21  * be included in all copies of the Software, in whole or in part, and all
22  * derivative works of the Software, unless such copies or derivative works are
23  * solely in the form of machine-executable object code generated by a source
24  * language processor.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
27  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
28  * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
29  * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
30  * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
31  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
32  * DEALINGS IN THE SOFTWARE.
33  */
34 
35 #ifndef _STX_BTREE_H_
36 #define _STX_BTREE_H_
37 
38 // *** Required Headers from the STL
39 
40 #include <algorithm>
41 #include <functional>
42 #include <istream>
43 #include <ostream>
44 #include <memory>
45 #include <cstddef>
46 #include <assert.h>
47 
48 // *** Debugging Macros
49 
50 #ifdef BTREE_DEBUG
51 
52 #include <iostream>
53 
54 /// Print out debug information to std::cout if BTREE_DEBUG is defined.
55 #define BTREE_PRINT(x) do { if (debug) (std::cout << x << std::endl); } while(0)
56 
57 /// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
58 #define BTREE_ASSERT(x) do { assert(x); } while(0)
59 
60 #else
61 
62 /// Print out debug information to std::cout if BTREE_DEBUG is defined.
63 #define BTREE_PRINT(x) do { } while(0)
64 
65 /// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
66 #define BTREE_ASSERT(x) do { } while(0)
67 
68 #endif
69 
70 /// The maximum of a and b. Used in some compile-time formulas.
71 #define BTREE_MAX(a,b) ((a) < (b) ? (b) : (a))
72 
73 #ifndef BTREE_FRIENDS
74 /// The macro BTREE_FRIENDS can be used by outside class to access the B+
75 /// tree internals. This was added for wxBTreeDemo to be able to draw the
76 /// tree.
77 #define BTREE_FRIENDS friend class btree_friend;
78 #endif
79 
80 /// STX - Some Template Extensions namespace
81 namespace stx {
82 
83 /** Generates default traits for a B+ tree used as a set. It estimates leaf and
84  * inner node sizes by assuming a cache line size of 256 bytes. */
85 template <typename _Key>
87 {
88  /// If true, the tree will self verify it's invariants after each insert()
89  /// or erase(). The header must have been compiled with BTREE_DEBUG defined.
90  static const bool selfverify = false;
91 
92  /// If true, the tree will print out debug information and a tree dump
93  /// during insert() or erase() operation. The header must have been
94  /// compiled with BTREE_DEBUG defined and key_type must be std::ostream
95  /// printable.
96  static const bool debug = false;
97 
98  /// Number of slots in each leaf of the tree. Estimated so that each node
99  /// has a size of about 256 bytes.
100  static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );
101 
102  /// Number of slots in each inner node of the tree. Estimated so that each node
103  /// has a size of about 256 bytes.
104  static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
105 
106  /// As of stx-btree-0.9, the code does linear search in find_lower() and
107  /// find_upper() instead of binary_search, unless the node size is larger
108  /// than this threshold. See notes at
109  /// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search
110  static const size_t binsearch_threshold = 256;
111 };
112 
113 /** Generates default traits for a B+ tree used as a map. It estimates leaf and
114  * inner node sizes by assuming a cache line size of 256 bytes. */
115 template <typename _Key, typename _Data>
117 {
118  /// If true, the tree will self verify it's invariants after each insert()
119  /// or erase(). The header must have been compiled with BTREE_DEBUG defined.
120  static const bool selfverify = false;
121 
122  /// If true, the tree will print out debug information and a tree dump
123  /// during insert() or erase() operation. The header must have been
124  /// compiled with BTREE_DEBUG defined and key_type must be std::ostream
125  /// printable.
126  static const bool debug = false;
127 
128  /// Number of slots in each leaf of the tree. Estimated so that each node
129  /// has a size of about 256 bytes.
130  static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );
131 
132  /// Number of slots in each inner node of the tree. Estimated so that each node
133  /// has a size of about 256 bytes.
134  static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
135 
136  /// As of stx-btree-0.9, the code does linear search in find_lower() and
137  /// find_upper() instead of binary_search, unless the node size is larger
138  /// than this threshold. See notes at
139  /// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search
140  static const size_t binsearch_threshold = 256;
141 };
142 
143 /** @brief Basic class implementing a base B+ tree data structure in memory.
144  *
145  * The base implementation of a memory B+ tree. It is based on the
146  * implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper
147  * and other algorithm resources. Almost all STL-required function calls are
148  * implemented. The asymptotic time requirements of the STL are not always
149  * fulfilled in theory, however in practice this B+ tree performs better than a
150  * red-black tree by using more memory. The insertion function splits the nodes
151  * on the recursion unroll. Erase is largely based on Jannink's ideas.
152  *
153  * This class is specialized into btree_set, btree_multiset, btree_map and
154  * btree_multimap using default template parameters and facade functions.
155  */
156 template <typename _Key, typename _Data,
157  typename _Value = std::pair<_Key, _Data>,
158  typename _Compare = std::less<_Key>,
159  typename _Traits = btree_default_map_traits<_Key, _Data>,
160  bool _Duplicates = false,
161  typename _Alloc = std::allocator<_Value>,
162  bool _UsedAsSet = false >
163 class btree
164 {
165 public:
166  // *** Template Parameter Types
167 
168  /// First template parameter: The key type of the B+ tree. This is stored
169  /// in inner nodes and leaves
170  typedef _Key key_type;
171 
172  /// Second template parameter: The data type associated with each
173  /// key. Stored in the B+ tree's leaves
174  typedef _Data data_type;
175 
176  /// Third template parameter: Composition pair of key and data types, this
177  /// is required by the STL standard. The B+ tree does not store key and
178  /// data together. If value_type == key_type then the B+ tree implements a
179  /// set.
180  typedef _Value value_type;
181 
182  /// Fourth template parameter: Key comparison function object
183  typedef _Compare key_compare;
184 
185  /// Fifth template parameter: Traits object used to define more parameters
186  /// of the B+ tree
187  typedef _Traits traits;
188 
189  /// Sixth template parameter: Allow duplicate keys in the B+ tree. Used to
190  /// implement multiset and multimap.
191  static const bool allow_duplicates = _Duplicates;
192 
193  /// Seventh template parameter: STL allocator for tree nodes
194  typedef _Alloc allocator_type;
195 
196  /// Eighth template parameter: boolean indicator whether the btree is used
197  /// as a set. In this case all operations on the data arrays are
198  /// omitted. This flag is kind of hacky, but required because
199  /// sizeof(empty_struct) = 1 due to the C standard. Without the flag, lots
200  /// of superfluous copying would occur.
201  static const bool used_as_set = _UsedAsSet;
202 
203  // The macro BTREE_FRIENDS can be used by outside class to access the B+
204  // tree internals. This was added for wxBTreeDemo to be able to draw the
205  // tree.
207 
208 public:
209  // *** Constructed Types
210 
211  /// Typedef of our own type
212  typedef btree<key_type, data_type, value_type, key_compare,
213  traits, allow_duplicates, allocator_type, used_as_set> btree_self;
214 
215  /// Size type used to count keys
216  typedef size_t size_type;
217 
218  /// The pair of key_type and data_type, this may be different from value_type.
219  typedef std::pair<key_type, data_type> pair_type;
220 
221 public:
222  // *** Static Constant Options and Values of the B+ Tree
223 
224  /// Base B+ tree parameter: The number of key/data slots in each leaf
225  static const unsigned short leafslotmax = traits::leafslots;
226 
227  /// Base B+ tree parameter: The number of key slots in each inner node,
228  /// this can differ from slots in each leaf.
229  static const unsigned short innerslotmax = traits::innerslots;
230 
231  /// Computed B+ tree parameter: The minimum number of key/data slots used
232  /// in a leaf. If fewer slots are used, the leaf will be merged or slots
233  /// shifted from it's siblings.
234  static const unsigned short minleafslots = (leafslotmax / 2);
235 
236  /// Computed B+ tree parameter: The minimum number of key slots used
237  /// in an inner node. If fewer slots are used, the inner node will be
238  /// merged or slots shifted from it's siblings.
239  static const unsigned short mininnerslots = (innerslotmax / 2);
240 
241  /// Debug parameter: Enables expensive and thorough checking of the B+ tree
242  /// invariants after each insert/erase operation.
243  static const bool selfverify = traits::selfverify;
244 
245  /// Debug parameter: Prints out lots of debug information about how the
246  /// algorithms change the tree. Requires the header file to be compiled
247  /// with BTREE_DEBUG and the key type must be std::ostream printable.
248  static const bool debug = traits::debug;
249 
250 private:
251  // *** Node Classes for In-Memory Nodes
252 
253  /// The header structure of each node in-memory. This structure is extended
254  /// by inner_node or leaf_node.
255  struct node
256  {
257  /// Level in the b-tree, if level == 0 -> leaf node
258  unsigned short level;
259 
260  /// Number of key slotuse use, so number of valid children or data
261  /// pointers
262  unsigned short slotuse;
263 
264  /// Delayed initialisation of constructed node
265  inline void initialize(const unsigned short l)
266  {
267  level = l;
268  slotuse = 0;
269  }
270 
271  /// True if this is a leaf node
272  inline bool isleafnode() const
273  {
274  return (level == 0);
275  }
276  };
277 
278  /// Extended structure of a inner node in-memory. Contains only keys and no
279  /// data items.
280  struct inner_node : public node
281  {
282  /// Define an related allocator for the inner_node structs.
283  typedef typename _Alloc::template rebind<inner_node>::other alloc_type;
284 
285  /// Keys of children or data pointers
286  key_type slotkey[innerslotmax];
287 
288  /// Pointers to children
289  node* childid[innerslotmax+1];
290 
291  /// Set variables to initial values
292  inline void initialize(const unsigned short l)
293  {
294  node::initialize(l);
295  }
296 
297  /// True if the node's slots are full
298  inline bool isfull() const
299  {
300  return (node::slotuse == innerslotmax);
301  }
302 
303  /// True if few used entries, less than half full
304  inline bool isfew() const
305  {
306  return (node::slotuse <= mininnerslots);
307  }
308 
309  /// True if node has too few entries
310  inline bool isunderflow() const
311  {
312  return (node::slotuse < mininnerslots);
313  }
314  };
315 
316  /// Extended structure of a leaf node in memory. Contains pairs of keys and
317  /// data items. Key and data slots are kept in separate arrays, because the
318  /// key array is traversed very often compared to accessing the data items.
319  struct leaf_node : public node
320  {
321  /// Define an related allocator for the leaf_node structs.
322  typedef typename _Alloc::template rebind<leaf_node>::other alloc_type;
323 
324  /// Double linked list pointers to traverse the leaves
326 
327  /// Double linked list pointers to traverse the leaves
329 
330  /// Keys of children or data pointers
331  key_type slotkey[leafslotmax];
332 
333  /// Array of data
334  data_type slotdata[used_as_set ? 1 : leafslotmax];
335 
336  /// Set variables to initial values
337  inline void initialize()
338  {
339  node::initialize(0);
340  prevleaf = nextleaf = NULL;
341  }
342 
343  /// True if the node's slots are full
344  inline bool isfull() const
345  {
346  return (node::slotuse == leafslotmax);
347  }
348 
349  /// True if few used entries, less than half full
350  inline bool isfew() const
351  {
352  return (node::slotuse <= minleafslots);
353  }
354 
355  /// True if node has too few entries
356  inline bool isunderflow() const
357  {
358  return (node::slotuse < minleafslots);
359  }
360 
361  /// Set the (key,data) pair in slot. Overloaded function used by
362  /// bulk_load().
363  inline void set_slot(unsigned short slot, const pair_type& value)
364  {
365  BTREE_ASSERT(used_as_set == false);
366  BTREE_ASSERT(slot < node::slotuse);
367  slotkey[slot] = value.first;
368  slotdata[slot] = value.second;
369  }
370 
371  /// Set the key pair in slot. Overloaded function used by
372  /// bulk_load().
373  inline void set_slot(unsigned short slot, const key_type& key)
374  {
375  BTREE_ASSERT(used_as_set == true);
376  BTREE_ASSERT(slot < node::slotuse);
377  slotkey[slot] = key;
378  }
379  };
380 
381 private:
382  // *** Template Magic to Convert a pair or key/data types to a value_type
383 
384  /// For sets the second pair_type is an empty struct, so the value_type
385  /// should only be the first.
386  template <typename value_type, typename pair_type>
388  {
389  /// Convert a fake pair type to just the first component
390  inline value_type operator()(pair_type& p) const {
391  return p.first;
392  }
393  /// Convert a fake pair type to just the first component
394  inline value_type operator()(const pair_type& p) const {
395  return p.first;
396  }
397  };
398 
399  /// For maps value_type is the same as the pair_type
400  template <typename value_type>
401  struct btree_pair_to_value<value_type, value_type>
402  {
403  /// Identity "convert" a real pair type to just the first component
404  inline value_type operator()(pair_type& p) const {
405  return p;
406  }
407  /// Identity "convert" a real pair type to just the first component
408  inline value_type operator()(const pair_type& p) const {
409  return p;
410  }
411  };
412 
413  /// Using template specialization select the correct converter used by the
414  /// iterators
415  typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;
416 
417 public:
418  // *** Iterators and Reverse Iterators
419 
420  class iterator;
421  class const_iterator;
422  class reverse_iterator;
423  class const_reverse_iterator;
424 
425  /// STL-like iterator object for B+ tree items. The iterator points to a
426  /// specific slot number in a leaf.
427  class iterator
428  {
429  public:
430  // *** Types
431 
432  /// The key type of the btree. Returned by key().
433  typedef typename btree::key_type key_type;
434 
435  /// The data type of the btree. Returned by data().
436  typedef typename btree::data_type data_type;
437 
438  /// The value type of the btree. Returned by operator*().
439  typedef typename btree::value_type value_type;
440 
441  /// The pair type of the btree.
442  typedef typename btree::pair_type pair_type;
443 
444  /// Reference to the value_type. STL required.
445  typedef value_type& reference;
446 
447  /// Pointer to the value_type. STL required.
448  typedef value_type* pointer;
449 
450  /// STL-magic iterator category
451  typedef std::bidirectional_iterator_tag iterator_category;
452 
453  /// STL-magic
454  typedef ptrdiff_t difference_type;
455 
456  /// Our own type
457  typedef iterator self;
458 
459  private:
460  // *** Members
461 
462  /// The currently referenced leaf node of the tree
464 
465  /// Current key/data slot referenced
466  unsigned short currslot;
467 
468  /// Friendly to the const_iterator, so it may access the two data items
469  /// directly.
470  friend class const_iterator;
471 
472  /// Also friendly to the reverse_iterator, so it may access the two
473  /// data items directly.
474  friend class reverse_iterator;
475 
476  /// Also friendly to the const_reverse_iterator, so it may access the
477  /// two data items directly.
479 
480  /// Also friendly to the base btree class, because erase_iter() needs
481  /// to read the currnode and currslot values directly.
482  friend class btree<key_type, data_type, value_type, key_compare,
483  traits, allow_duplicates, allocator_type, used_as_set>;
484 
485  /// Evil! A temporary value_type to STL-correctly deliver operator* and
486  /// operator->
487  mutable value_type temp_value;
488 
489  // The macro BTREE_FRIENDS can be used by outside class to access the B+
490  // tree internals. This was added for wxBTreeDemo to be able to draw the
491  // tree.
493 
494  public:
495  // *** Methods
496 
497  /// Default-Constructor of a mutable iterator
498  inline iterator()
499  : currnode(NULL), currslot(0)
500  { }
501 
502  /// Initializing-Constructor of a mutable iterator
503  inline iterator(typename btree::leaf_node *l, unsigned short s)
504  : currnode(l), currslot(s)
505  { }
506 
507  /// Copy-constructor from a reverse iterator
508  inline iterator(const reverse_iterator &it)
509  : currnode(it.currnode), currslot(it.currslot)
510  { }
511 
512  /// Dereference the iterator, this is not a value_type& because key and
513  /// value are not stored together
514  inline reference operator*() const
515  {
516  temp_value = pair_to_value_type()( pair_type(key(),data()) );
517  return temp_value;
518  }
519 
520  /// Dereference the iterator. Do not use this if possible, use key()
521  /// and data() instead. The B+ tree does not stored key and data
522  /// together.
523  inline pointer operator->() const
524  {
525  temp_value = pair_to_value_type()( pair_type(key(),data()) );
526  return &temp_value;
527  }
528 
529  /// Key of the current slot
530  inline const key_type& key() const
531  {
532  return currnode->slotkey[currslot];
533  }
534 
535  /// Writable reference to the current data object
536  inline data_type& data() const
537  {
538  return currnode->slotdata[used_as_set ? 0 : currslot];
539  }
540 
541  /// Prefix++ advance the iterator to the next slot
542  inline self& operator++()
543  {
544  if (currslot + 1 < currnode->slotuse) {
545  ++currslot;
546  }
547  else if (currnode->nextleaf != NULL) {
548  currnode = currnode->nextleaf;
549  currslot = 0;
550  }
551  else {
552  // this is end()
553  currslot = currnode->slotuse;
554  }
555 
556  return *this;
557  }
558 
559  /// Postfix++ advance the iterator to the next slot
560  inline self operator++(int)
561  {
562  self tmp = *this; // copy ourselves
563 
564  if (currslot + 1 < currnode->slotuse) {
565  ++currslot;
566  }
567  else if (currnode->nextleaf != NULL) {
568  currnode = currnode->nextleaf;
569  currslot = 0;
570  }
571  else {
572  // this is end()
573  currslot = currnode->slotuse;
574  }
575 
576  return tmp;
577  }
578 
579  /// Prefix-- backstep the iterator to the last slot
580  inline self& operator--()
581  {
582  if (currslot > 0) {
583  --currslot;
584  }
585  else if (currnode->prevleaf != NULL) {
586  currnode = currnode->prevleaf;
587  currslot = currnode->slotuse - 1;
588  }
589  else {
590  // this is begin()
591  currslot = 0;
592  }
593 
594  return *this;
595  }
596 
597  /// Postfix-- backstep the iterator to the last slot
598  inline self operator--(int)
599  {
600  self tmp = *this; // copy ourselves
601 
602  if (currslot > 0) {
603  --currslot;
604  }
605  else if (currnode->prevleaf != NULL) {
606  currnode = currnode->prevleaf;
607  currslot = currnode->slotuse - 1;
608  }
609  else {
610  // this is begin()
611  currslot = 0;
612  }
613 
614  return tmp;
615  }
616 
617  /// Equality of iterators
618  inline bool operator==(const self& x) const
619  {
620  return (x.currnode == currnode) && (x.currslot == currslot);
621  }
622 
623  /// Inequality of iterators
624  inline bool operator!=(const self& x) const
625  {
626  return (x.currnode != currnode) || (x.currslot != currslot);
627  }
628  };
629 
630  /// STL-like read-only iterator object for B+ tree items. The iterator
631  /// points to a specific slot number in a leaf.
633  {
634  public:
635  // *** Types
636 
637  /// The key type of the btree. Returned by key().
638  typedef typename btree::key_type key_type;
639 
640  /// The data type of the btree. Returned by data().
641  typedef typename btree::data_type data_type;
642 
643  /// The value type of the btree. Returned by operator*().
644  typedef typename btree::value_type value_type;
645 
646  /// The pair type of the btree.
647  typedef typename btree::pair_type pair_type;
648 
649  /// Reference to the value_type. STL required.
650  typedef const value_type& reference;
651 
652  /// Pointer to the value_type. STL required.
653  typedef const value_type* pointer;
654 
655  /// STL-magic iterator category
656  typedef std::bidirectional_iterator_tag iterator_category;
657 
658  /// STL-magic
659  typedef ptrdiff_t difference_type;
660 
661  /// Our own type
662  typedef const_iterator self;
663 
664  private:
665  // *** Members
666 
667  /// The currently referenced leaf node of the tree
668  const typename btree::leaf_node* currnode;
669 
670  /// Current key/data slot referenced
671  unsigned short currslot;
672 
673  /// Friendly to the reverse_const_iterator, so it may access the two
674  /// data items directly
676 
677  /// Evil! A temporary value_type to STL-correctly deliver operator* and
678  /// operator->
679  mutable value_type temp_value;
680 
681  // The macro BTREE_FRIENDS can be used by outside class to access the B+
682  // tree internals. This was added for wxBTreeDemo to be able to draw the
683  // tree.
685 
686  public:
687  // *** Methods
688 
689  /// Default-Constructor of a const iterator
690  inline const_iterator()
691  : currnode(NULL), currslot(0)
692  { }
693 
694  /// Initializing-Constructor of a const iterator
695  inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
696  : currnode(l), currslot(s)
697  { }
698 
699  /// Copy-constructor from a mutable iterator
700  inline const_iterator(const iterator &it)
701  : currnode(it.currnode), currslot(it.currslot)
702  { }
703 
704  /// Copy-constructor from a mutable reverse iterator
706  : currnode(it.currnode), currslot(it.currslot)
707  { }
708 
709  /// Copy-constructor from a const reverse iterator
711  : currnode(it.currnode), currslot(it.currslot)
712  { }
713 
714  /// Dereference the iterator. Do not use this if possible, use key()
715  /// and data() instead. The B+ tree does not stored key and data
716  /// together.
717  inline reference operator*() const
718  {
719  temp_value = pair_to_value_type()( pair_type(key(),data()) );
720  return temp_value;
721  }
722 
723  /// Dereference the iterator. Do not use this if possible, use key()
724  /// and data() instead. The B+ tree does not stored key and data
725  /// together.
726  inline pointer operator->() const
727  {
728  temp_value = pair_to_value_type()( pair_type(key(),data()) );
729  return &temp_value;
730  }
731 
732  /// Key of the current slot
733  inline const key_type& key() const
734  {
735  return currnode->slotkey[currslot];
736  }
737 
738  /// Read-only reference to the current data object
739  inline const data_type& data() const
740  {
741  return currnode->slotdata[used_as_set ? 0 : currslot];
742  }
743 
744  /// Prefix++ advance the iterator to the next slot
745  inline self& operator++()
746  {
747  if (currslot + 1 < currnode->slotuse) {
748  ++currslot;
749  }
750  else if (currnode->nextleaf != NULL) {
751  currnode = currnode->nextleaf;
752  currslot = 0;
753  }
754  else {
755  // this is end()
756  currslot = currnode->slotuse;
757  }
758 
759  return *this;
760  }
761 
762  /// Postfix++ advance the iterator to the next slot
763  inline self operator++(int)
764  {
765  self tmp = *this; // copy ourselves
766 
767  if (currslot + 1 < currnode->slotuse) {
768  ++currslot;
769  }
770  else if (currnode->nextleaf != NULL) {
771  currnode = currnode->nextleaf;
772  currslot = 0;
773  }
774  else {
775  // this is end()
776  currslot = currnode->slotuse;
777  }
778 
779  return tmp;
780  }
781 
782  /// Prefix-- backstep the iterator to the last slot
783  inline self& operator--()
784  {
785  if (currslot > 0) {
786  --currslot;
787  }
788  else if (currnode->prevleaf != NULL) {
789  currnode = currnode->prevleaf;
790  currslot = currnode->slotuse - 1;
791  }
792  else {
793  // this is begin()
794  currslot = 0;
795  }
796 
797  return *this;
798  }
799 
800  /// Postfix-- backstep the iterator to the last slot
801  inline self operator--(int)
802  {
803  self tmp = *this; // copy ourselves
804 
805  if (currslot > 0) {
806  --currslot;
807  }
808  else if (currnode->prevleaf != NULL) {
809  currnode = currnode->prevleaf;
810  currslot = currnode->slotuse - 1;
811  }
812  else {
813  // this is begin()
814  currslot = 0;
815  }
816 
817  return tmp;
818  }
819 
820  /// Equality of iterators
821  inline bool operator==(const self& x) const
822  {
823  return (x.currnode == currnode) && (x.currslot == currslot);
824  }
825 
826  /// Inequality of iterators
827  inline bool operator!=(const self& x) const
828  {
829  return (x.currnode != currnode) || (x.currslot != currslot);
830  }
831  };
832 
833  /// STL-like mutable reverse iterator object for B+ tree items. The
834  /// iterator points to a specific slot number in a leaf.
836  {
837  public:
838  // *** Types
839 
840  /// The key type of the btree. Returned by key().
841  typedef typename btree::key_type key_type;
842 
843  /// The data type of the btree. Returned by data().
844  typedef typename btree::data_type data_type;
845 
846  /// The value type of the btree. Returned by operator*().
847  typedef typename btree::value_type value_type;
848 
849  /// The pair type of the btree.
850  typedef typename btree::pair_type pair_type;
851 
852  /// Reference to the value_type. STL required.
853  typedef value_type& reference;
854 
855  /// Pointer to the value_type. STL required.
856  typedef value_type* pointer;
857 
858  /// STL-magic iterator category
859  typedef std::bidirectional_iterator_tag iterator_category;
860 
861  /// STL-magic
862  typedef ptrdiff_t difference_type;
863 
864  /// Our own type
865  typedef reverse_iterator self;
866 
867  private:
868  // *** Members
869 
870  /// The currently referenced leaf node of the tree
872 
873  /// One slot past the current key/data slot referenced.
874  unsigned short currslot;
875 
876  /// Friendly to the const_iterator, so it may access the two data items
877  /// directly
878  friend class iterator;
879 
880  /// Also friendly to the const_iterator, so it may access the two data
881  /// items directly
882  friend class const_iterator;
883 
884  /// Also friendly to the const_iterator, so it may access the two data
885  /// items directly
887 
888  /// Evil! A temporary value_type to STL-correctly deliver operator* and
889  /// operator->
890  mutable value_type temp_value;
891 
892  // The macro BTREE_FRIENDS can be used by outside class to access the B+
893  // tree internals. This was added for wxBTreeDemo to be able to draw the
894  // tree.
896 
897  public:
898  // *** Methods
899 
900  /// Default-Constructor of a reverse iterator
902  : currnode(NULL), currslot(0)
903  { }
904 
905  /// Initializing-Constructor of a mutable reverse iterator
906  inline reverse_iterator(typename btree::leaf_node *l, unsigned short s)
907  : currnode(l), currslot(s)
908  { }
909 
910  /// Copy-constructor from a mutable iterator
911  inline reverse_iterator(const iterator &it)
912  : currnode(it.currnode), currslot(it.currslot)
913  { }
914 
915  /// Dereference the iterator, this is not a value_type& because key and
916  /// value are not stored together
917  inline reference operator*() const
918  {
919  BTREE_ASSERT(currslot > 0);
920  temp_value = pair_to_value_type()( pair_type(key(),data()) );
921  return temp_value;
922  }
923 
924  /// Dereference the iterator. Do not use this if possible, use key()
925  /// and data() instead. The B+ tree does not stored key and data
926  /// together.
927  inline pointer operator->() const
928  {
929  BTREE_ASSERT(currslot > 0);
930  temp_value = pair_to_value_type()( pair_type(key(),data()) );
931  return &temp_value;
932  }
933 
934  /// Key of the current slot
935  inline const key_type& key() const
936  {
937  BTREE_ASSERT(currslot > 0);
938  return currnode->slotkey[currslot - 1];
939  }
940 
941  /// Writable reference to the current data object
942  inline data_type& data() const
943  {
944  BTREE_ASSERT(currslot > 0);
945  return currnode->slotdata[used_as_set ? 0 : currslot-1];
946  }
947 
948  /// Prefix++ advance the iterator to the next slot
949  inline self& operator++()
950  {
951  if (currslot > 1) {
952  --currslot;
953  }
954  else if (currnode->prevleaf != NULL) {
955  currnode = currnode->prevleaf;
956  currslot = currnode->slotuse;
957  }
958  else {
959  // this is begin() == rend()
960  currslot = 0;
961  }
962 
963  return *this;
964  }
965 
966  /// Postfix++ advance the iterator to the next slot
967  inline self operator++(int)
968  {
969  self tmp = *this; // copy ourselves
970 
971  if (currslot > 1) {
972  --currslot;
973  }
974  else if (currnode->prevleaf != NULL) {
975  currnode = currnode->prevleaf;
976  currslot = currnode->slotuse;
977  }
978  else {
979  // this is begin() == rend()
980  currslot = 0;
981  }
982 
983  return tmp;
984  }
985 
986  /// Prefix-- backstep the iterator to the last slot
987  inline self& operator--()
988  {
989  if (currslot < currnode->slotuse) {
990  ++currslot;
991  }
992  else if (currnode->nextleaf != NULL) {
993  currnode = currnode->nextleaf;
994  currslot = 1;
995  }
996  else {
997  // this is end() == rbegin()
998  currslot = currnode->slotuse;
999  }
1000 
1001  return *this;
1002  }
1003 
1004  /// Postfix-- backstep the iterator to the last slot
1005  inline self operator--(int)
1006  {
1007  self tmp = *this; // copy ourselves
1008 
1009  if (currslot < currnode->slotuse) {
1010  ++currslot;
1011  }
1012  else if (currnode->nextleaf != NULL) {
1013  currnode = currnode->nextleaf;
1014  currslot = 1;
1015  }
1016  else {
1017  // this is end() == rbegin()
1018  currslot = currnode->slotuse;
1019  }
1020 
1021  return tmp;
1022  }
1023 
1024  /// Equality of iterators
1025  inline bool operator==(const self& x) const
1026  {
1027  return (x.currnode == currnode) && (x.currslot == currslot);
1028  }
1029 
1030  /// Inequality of iterators
1031  inline bool operator!=(const self& x) const
1032  {
1033  return (x.currnode != currnode) || (x.currslot != currslot);
1034  }
1035  };
1036 
1037  /// STL-like read-only reverse iterator object for B+ tree items. The
1038  /// iterator points to a specific slot number in a leaf.
1040  {
1041  public:
1042  // *** Types
1043 
1044  /// The key type of the btree. Returned by key().
1045  typedef typename btree::key_type key_type;
1046 
1047  /// The data type of the btree. Returned by data().
1048  typedef typename btree::data_type data_type;
1049 
1050  /// The value type of the btree. Returned by operator*().
1051  typedef typename btree::value_type value_type;
1052 
1053  /// The pair type of the btree.
1054  typedef typename btree::pair_type pair_type;
1055 
1056  /// Reference to the value_type. STL required.
1057  typedef const value_type& reference;
1058 
1059  /// Pointer to the value_type. STL required.
1060  typedef const value_type* pointer;
1061 
1062  /// STL-magic iterator category
1063  typedef std::bidirectional_iterator_tag iterator_category;
1064 
1065  /// STL-magic
1066  typedef ptrdiff_t difference_type;
1067 
1068  /// Our own type
1070 
1071  private:
1072  // *** Members
1073 
1074  /// The currently referenced leaf node of the tree
1075  const typename btree::leaf_node* currnode;
1076 
1077  /// One slot past the current key/data slot referenced.
1078  unsigned short currslot;
1079 
1080  /// Friendly to the const_iterator, so it may access the two data items
1081  /// directly.
1082  friend class reverse_iterator;
1083 
1084  /// Evil! A temporary value_type to STL-correctly deliver operator* and
1085  /// operator->
1086  mutable value_type temp_value;
1087 
1088  // The macro BTREE_FRIENDS can be used by outside class to access the B+
1089  // tree internals. This was added for wxBTreeDemo to be able to draw the
1090  // tree.
1092 
1093  public:
1094  // *** Methods
1095 
1096  /// Default-Constructor of a const reverse iterator
1098  : currnode(NULL), currslot(0)
1099  { }
1100 
1101  /// Initializing-Constructor of a const reverse iterator
1102  inline const_reverse_iterator(const typename btree::leaf_node *l, unsigned short s)
1103  : currnode(l), currslot(s)
1104  { }
1105 
1106  /// Copy-constructor from a mutable iterator
1108  : currnode(it.currnode), currslot(it.currslot)
1109  { }
1110 
1111  /// Copy-constructor from a const iterator
1113  : currnode(it.currnode), currslot(it.currslot)
1114  { }
1115 
1116  /// Copy-constructor from a mutable reverse iterator
1118  : currnode(it.currnode), currslot(it.currslot)
1119  { }
1120 
1121  /// Dereference the iterator. Do not use this if possible, use key()
1122  /// and data() instead. The B+ tree does not stored key and data
1123  /// together.
1124  inline reference operator*() const
1125  {
1126  BTREE_ASSERT(currslot > 0);
1127  temp_value = pair_to_value_type()( pair_type(key(),data()) );
1128  return temp_value;
1129  }
1130 
1131  /// Dereference the iterator. Do not use this if possible, use key()
1132  /// and data() instead. The B+ tree does not stored key and data
1133  /// together.
1134  inline pointer operator->() const
1135  {
1136  BTREE_ASSERT(currslot > 0);
1137  temp_value = pair_to_value_type()( pair_type(key(),data()) );
1138  return &temp_value;
1139  }
1140 
1141  /// Key of the current slot
1142  inline const key_type& key() const
1143  {
1144  BTREE_ASSERT(currslot > 0);
1145  return currnode->slotkey[currslot - 1];
1146  }
1147 
1148  /// Read-only reference to the current data object
1149  inline const data_type& data() const
1150  {
1151  BTREE_ASSERT(currslot > 0);
1152  return currnode->slotdata[used_as_set ? 0 : currslot-1];
1153  }
1154 
1155  /// Prefix++ advance the iterator to the previous slot
1156  inline self& operator++()
1157  {
1158  if (currslot > 1) {
1159  --currslot;
1160  }
1161  else if (currnode->prevleaf != NULL) {
1162  currnode = currnode->prevleaf;
1163  currslot = currnode->slotuse;
1164  }
1165  else {
1166  // this is begin() == rend()
1167  currslot = 0;
1168  }
1169 
1170  return *this;
1171  }
1172 
1173  /// Postfix++ advance the iterator to the previous slot
1174  inline self operator++(int)
1175  {
1176  self tmp = *this; // copy ourselves
1177 
1178  if (currslot > 1) {
1179  --currslot;
1180  }
1181  else if (currnode->prevleaf != NULL) {
1182  currnode = currnode->prevleaf;
1183  currslot = currnode->slotuse;
1184  }
1185  else {
1186  // this is begin() == rend()
1187  currslot = 0;
1188  }
1189 
1190  return tmp;
1191  }
1192 
1193  /// Prefix-- backstep the iterator to the next slot
1194  inline self& operator--()
1195  {
1196  if (currslot < currnode->slotuse) {
1197  ++currslot;
1198  }
1199  else if (currnode->nextleaf != NULL) {
1200  currnode = currnode->nextleaf;
1201  currslot = 1;
1202  }
1203  else {
1204  // this is end() == rbegin()
1205  currslot = currnode->slotuse;
1206  }
1207 
1208  return *this;
1209  }
1210 
1211  /// Postfix-- backstep the iterator to the next slot
1212  inline self operator--(int)
1213  {
1214  self tmp = *this; // copy ourselves
1215 
1216  if (currslot < currnode->slotuse) {
1217  ++currslot;
1218  }
1219  else if (currnode->nextleaf != NULL) {
1220  currnode = currnode->nextleaf;
1221  currslot = 1;
1222  }
1223  else {
1224  // this is end() == rbegin()
1225  currslot = currnode->slotuse;
1226  }
1227 
1228  return tmp;
1229  }
1230 
1231  /// Equality of iterators
1232  inline bool operator==(const self& x) const
1233  {
1234  return (x.currnode == currnode) && (x.currslot == currslot);
1235  }
1236 
1237  /// Inequality of iterators
1238  inline bool operator!=(const self& x) const
1239  {
1240  return (x.currnode != currnode) || (x.currslot != currslot);
1241  }
1242  };
1243 
1244 public:
1245  // *** Small Statistics Structure
1246 
1247  /** A small struct containing basic statistics about the B+ tree. It can be
1248  * fetched using get_stats(). */
1249  struct tree_stats
1250  {
1251  /// Number of items in the B+ tree
1252  size_type itemcount;
1253 
1254  /// Number of leaves in the B+ tree
1255  size_type leaves;
1256 
1257  /// Number of inner nodes in the B+ tree
1258  size_type innernodes;
1259 
1260  /// Base B+ tree parameter: The number of key/data slots in each leaf
1261  static const unsigned short leafslots = btree_self::leafslotmax;
1262 
1263  /// Base B+ tree parameter: The number of key slots in each inner node.
1264  static const unsigned short innerslots = btree_self::innerslotmax;
1265 
1266  /// Zero initialized
1267  inline tree_stats()
1268  : itemcount(0),
1269  leaves(0), innernodes(0)
1270  {
1271  }
1272 
1273  /// Return the total number of nodes
1274  inline size_type nodes() const
1275  {
1276  return innernodes + leaves;
1277  }
1278 
1279  /// Return the average fill of leaves
1280  inline double avgfill_leaves() const
1281  {
1282  return static_cast<double>(itemcount) / (leaves * leafslots);
1283  }
1284  };
1285 
1286 private:
1287  // *** Tree Object Data Members
1288 
1289  /// Pointer to the B+ tree's root node, either leaf or inner node
1290  node* m_root;
1291 
1292  /// Pointer to first leaf in the double linked leaf chain
1293  leaf_node *m_headleaf;
1294 
1295  /// Pointer to last leaf in the double linked leaf chain
1296  leaf_node *m_tailleaf;
1297 
1298  /// Other small statistics about the B+ tree
1299  tree_stats m_stats;
1300 
1301  /// Key comparison object. More comparison functions are generated from
1302  /// this < relation.
1303  key_compare m_key_less;
1304 
1305  /// Memory allocator.
1306  allocator_type m_allocator;
1307 
1308 public:
1309  // *** Constructors and Destructor
1310 
1311  /// Default constructor initializing an empty B+ tree with the standard key
1312  /// comparison function
1313  explicit inline btree(const allocator_type &alloc = allocator_type())
1314  : m_root(NULL), m_headleaf(NULL), m_tailleaf(NULL), m_allocator(alloc)
1315  {
1316  }
1317 
1318  /// Constructor initializing an empty B+ tree with a special key
1319  /// comparison object
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)
1324  {
1325  }
1326 
1327  /// Constructor initializing a B+ tree with the range [first,last). The
1328  /// range need not be sorted. To create a B+ tree from a sorted range, use
1329  /// bulk_load().
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)
1334  {
1335  insert(first, last);
1336  }
1337 
1338  /// Constructor initializing a B+ tree with the range [first,last) and a
1339  /// special key comparison object. The range need not be sorted. To create
1340  /// a B+ tree from a sorted range, use bulk_load().
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)
1346  {
1347  insert(first, last);
1348  }
1349 
1350  /// Frees up all used B+ tree memory pages
1351  inline ~btree()
1352  {
1353  clear();
1354  }
1355 
1356  /// Fast swapping of two identical B+ tree objects.
1357  void swap(btree_self& from)
1358  {
1359  std::swap(m_root, from.m_root);
1360  std::swap(m_headleaf, from.m_headleaf);
1361  std::swap(m_tailleaf, from.m_tailleaf);
1362  std::swap(m_stats, from.m_stats);
1363  std::swap(m_key_less, from.m_key_less);
1364  std::swap(m_allocator, from.m_allocator);
1365  }
1366 
1367 public:
1368  // *** Key and Value Comparison Function Objects
1369 
1370  /// Function class to compare value_type objects. Required by the STL
1372  {
1373  protected:
1374  /// Key comparison function from the template parameter
1375  key_compare key_comp;
1376 
1377  /// Constructor called from btree::value_comp()
1378  inline value_compare(key_compare kc)
1379  : key_comp(kc)
1380  { }
1381 
1382  /// Friendly to the btree class so it may call the constructor
1383  friend class btree<key_type, data_type, value_type, key_compare,
1384  traits, allow_duplicates, allocator_type, used_as_set>;
1385 
1386  public:
1387  /// Function call "less"-operator resulting in true if x < y.
1388  inline bool operator()(const value_type& x, const value_type& y) const
1389  {
1390  return key_comp(x.first, y.first);
1391  }
1392  };
1393 
1394  /// Constant access to the key comparison object sorting the B+ tree
1395  inline key_compare key_comp() const
1396  {
1397  return m_key_less;
1398  }
1399 
1400  /// Constant access to a constructed value_type comparison object. Required
1401  /// by the STL
1402  inline value_compare value_comp() const
1403  {
1404  return value_compare(m_key_less);
1405  }
1406 
1407 private:
1408  // *** Convenient Key Comparison Functions Generated From key_less
1409 
1410  /// True if a < b ? "constructed" from m_key_less()
1411  inline bool key_less(const key_type &a, const key_type b) const
1412  {
1413  return m_key_less(a, b);
1414  }
1415 
1416  /// True if a <= b ? constructed from key_less()
1417  inline bool key_lessequal(const key_type &a, const key_type b) const
1418  {
1419  return !m_key_less(b, a);
1420  }
1421 
1422  /// True if a > b ? constructed from key_less()
1423  inline bool key_greater(const key_type &a, const key_type &b) const
1424  {
1425  return m_key_less(b, a);
1426  }
1427 
1428  /// True if a >= b ? constructed from key_less()
1429  inline bool key_greaterequal(const key_type &a, const key_type b) const
1430  {
1431  return !m_key_less(a, b);
1432  }
1433 
1434  /// True if a == b ? constructed from key_less(). This requires the <
1435  /// relation to be a total order, otherwise the B+ tree cannot be sorted.
1436  inline bool key_equal(const key_type &a, const key_type &b) const
1437  {
1438  return !m_key_less(a, b) && !m_key_less(b, a);
1439  }
1440 
1441 public:
1442  // *** Allocators
1443 
1444  /// Return the base node allocator provided during construction.
1445  allocator_type get_allocator() const
1446  {
1447  return m_allocator;
1448  }
1449 
1450 private:
1451  // *** Node Object Allocation and Deallocation Functions
1452 
1453  /// Return an allocator for leaf_node objects
1454  typename leaf_node::alloc_type leaf_node_allocator()
1455  {
1456  return typename leaf_node::alloc_type(m_allocator);
1457  }
1458 
1459  /// Return an allocator for inner_node objects
1460  typename inner_node::alloc_type inner_node_allocator()
1461  {
1462  return typename inner_node::alloc_type(m_allocator);
1463  }
1464 
1465  /// Allocate and initialize a leaf node
1466  inline leaf_node* allocate_leaf()
1467  {
1468  leaf_node *n = new (leaf_node_allocator().allocate(1)) leaf_node();
1469  n->initialize();
1470  m_stats.leaves++;
1471  return n;
1472  }
1473 
1474  /// Allocate and initialize an inner node
1475  inline inner_node* allocate_inner(unsigned short level)
1476  {
1477  inner_node *n = new (inner_node_allocator().allocate(1)) inner_node();
1478  n->initialize(level);
1479  m_stats.innernodes++;
1480  return n;
1481  }
1482 
1483  /// Correctly free either inner or leaf node, destructs all contained key
1484  /// and value objects
1485  inline void free_node(node *n)
1486  {
1487  if (n->isleafnode()) {
1488  leaf_node *ln = static_cast<leaf_node*>(n);
1489  typename leaf_node::alloc_type a(leaf_node_allocator());
1490  a.destroy(ln);
1491  a.deallocate(ln, 1);
1492  m_stats.leaves--;
1493  }
1494  else {
1495  inner_node *in = static_cast<inner_node*>(n);
1496  typename inner_node::alloc_type a(inner_node_allocator());
1497  a.destroy(in);
1498  a.deallocate(in, 1);
1499  m_stats.innernodes--;
1500  }
1501  }
1502 
1503  /// Convenient template function for conditional copying of slotdata. This
1504  /// should be used instead of std::copy for all slotdata manipulations.
1505  template<class InputIterator, class OutputIterator>
1506  static OutputIterator data_copy (InputIterator first, InputIterator last,
1507  OutputIterator result)
1508  {
1509  if (used_as_set) return result; // no operation
1510  else return std::copy(first, last, result);
1511  }
1512 
1513  /// Convenient template function for conditional copying of slotdata. This
1514  /// should be used instead of std::copy for all slotdata manipulations.
1515  template<class InputIterator, class OutputIterator>
1516  static OutputIterator data_copy_backward (InputIterator first, InputIterator last,
1517  OutputIterator result)
1518  {
1519  if (used_as_set) return result; // no operation
1520  else return std::copy_backward(first, last, result);
1521  }
1522 
1523 public:
1524  // *** Fast Destruction of the B+ Tree
1525 
1526  /// Frees all key/data pairs and all nodes of the tree
1527  void clear()
1528  {
1529  if (m_root)
1530  {
1531  clear_recursive(m_root);
1532  free_node(m_root);
1533 
1534  m_root = NULL;
1535  m_headleaf = m_tailleaf = NULL;
1536 
1537  m_stats = tree_stats();
1538  }
1539 
1540  BTREE_ASSERT(m_stats.itemcount == 0);
1541  }
1542 
1543 private:
1544  /// Recursively free up nodes
1545  void clear_recursive(node *n)
1546  {
1547  if (n->isleafnode())
1548  {
1549  leaf_node *leafnode = static_cast<leaf_node*>(n);
1550 
1551  for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
1552  {
1553  // data objects are deleted by leaf_node's destructor
1554  }
1555  }
1556  else
1557  {
1558  inner_node *innernode = static_cast<inner_node*>(n);
1559 
1560  for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
1561  {
1562  clear_recursive(innernode->childid[slot]);
1563  free_node(innernode->childid[slot]);
1564  }
1565  }
1566  }
1567 
1568 public:
1569  // *** STL Iterator Construction Functions
1570 
1571  /// Constructs a read/data-write iterator that points to the first slot in
1572  /// the first leaf of the B+ tree.
1573  inline iterator begin()
1574  {
1575  return iterator(m_headleaf, 0);
1576  }
1577 
1578  /// Constructs a read/data-write iterator that points to the first invalid
1579  /// slot in the last leaf of the B+ tree.
1580  inline iterator end()
1581  {
1582  return iterator(m_tailleaf, m_tailleaf ? m_tailleaf->slotuse : 0);
1583  }
1584 
1585  /// Constructs a read-only constant iterator that points to the first slot
1586  /// in the first leaf of the B+ tree.
1587  inline const_iterator begin() const
1588  {
1589  return const_iterator(m_headleaf, 0);
1590  }
1591 
1592  /// Constructs a read-only constant iterator that points to the first
1593  /// invalid slot in the last leaf of the B+ tree.
1594  inline const_iterator end() const
1595  {
1596  return const_iterator(m_tailleaf, m_tailleaf ? m_tailleaf->slotuse : 0);
1597  }
1598 
1599  /// Constructs a read/data-write reverse iterator that points to the first
1600  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
1601  inline reverse_iterator rbegin()
1602  {
1603  return reverse_iterator(end());
1604  }
1605 
1606  /// Constructs a read/data-write reverse iterator that points to the first
1607  /// slot in the first leaf of the B+ tree. Uses STL magic.
1608  inline reverse_iterator rend()
1609  {
1610  return reverse_iterator(begin());
1611  }
1612 
1613  /// Constructs a read-only reverse iterator that points to the first
1614  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
1615  inline const_reverse_iterator rbegin() const
1616  {
1617  return const_reverse_iterator(end());
1618  }
1619 
1620  /// Constructs a read-only reverse iterator that points to the first slot
1621  /// in the first leaf of the B+ tree. Uses STL magic.
1622  inline const_reverse_iterator rend() const
1623  {
1624  return const_reverse_iterator(begin());
1625  }
1626 
1627 private:
1628  // *** B+ Tree Node Binary Search Functions
1629 
1630  /// Searches for the first key in the node n greater or equal to key. Uses
1631  /// binary search with an optional linear self-verification. This is a
1632  /// template function, because the slotkey array is located at different
1633  /// places in leaf_node and inner_node.
1634  template <typename node_type>
1635  inline int find_lower(const node_type *n, const key_type& key) const
1636  {
1637  if ( 0 && sizeof(n->slotkey) > traits::binsearch_threshold )
1638  {
1639  if (n->slotuse == 0) return 0;
1640 
1641  int lo = 0, hi = n->slotuse;
1642 
1643  while (lo < hi)
1644  {
1645  int mid = (lo + hi) >> 1;
1646 
1647  if (key_lessequal(key, n->slotkey[mid])) {
1648  hi = mid; // key <= mid
1649  }
1650  else {
1651  lo = mid + 1; // key > mid
1652  }
1653  }
1654 
1655  BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> " << lo << " / " << hi);
1656 
1657  // verify result using simple linear search
1658  if (selfverify)
1659  {
1660  int i = 0;
1661  while (i < n->slotuse && key_less(n->slotkey[i],key)) ++i;
1662 
1663  BTREE_PRINT("btree::find_lower: testfind: " << i);
1664  BTREE_ASSERT(i == lo);
1665  }
1666 
1667  return lo;
1668  }
1669  else // for nodes <= binsearch_threshold do linear search.
1670  {
1671  int lo = 0;
1672  while (lo < n->slotuse && key_less(n->slotkey[lo],key)) ++lo;
1673  return lo;
1674  }
1675  }
1676 
1677  /// Searches for the first key in the node n greater than key. Uses binary
1678  /// search with an optional linear self-verification. This is a template
1679  /// function, because the slotkey array is located at different places in
1680  /// leaf_node and inner_node.
1681  template <typename node_type>
1682  inline int find_upper(const node_type *n, const key_type& key) const
1683  {
1684  if ( 0 && sizeof(n->slotkey) > traits::binsearch_threshold )
1685  {
1686  if (n->slotuse == 0) return 0;
1687 
1688  int lo = 0, hi = n->slotuse;
1689 
1690  while (lo < hi)
1691  {
1692  int mid = (lo + hi) >> 1;
1693 
1694  if (key_less(key, n->slotkey[mid])) {
1695  hi = mid; // key < mid
1696  }
1697  else {
1698  lo = mid + 1; // key >= mid
1699  }
1700  }
1701 
1702  BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> " << lo << " / " << hi);
1703 
1704  // verify result using simple linear search
1705  if (selfverify)
1706  {
1707  int i = 0;
1708  while (i < n->slotuse && key_lessequal(n->slotkey[i],key)) ++i;
1709 
1710  BTREE_PRINT("btree::find_upper testfind: " << i);
1711  BTREE_ASSERT(i == hi);
1712  }
1713 
1714  return lo;
1715  }
1716  else // for nodes <= binsearch_threshold do linear search.
1717  {
1718  int lo = 0;
1719  while (lo < n->slotuse && key_lessequal(n->slotkey[lo],key)) ++lo;
1720  return lo;
1721  }
1722  }
1723 
1724 public:
1725  // *** Access Functions to the Item Count
1726 
1727  /// Return the number of key/data pairs in the B+ tree
1728  inline size_type size() const
1729  {
1730  return m_stats.itemcount;
1731  }
1732 
1733  /// Returns true if there is at least one key/data pair in the B+ tree
1734  inline bool empty() const
1735  {
1736  return (size() == size_type(0));
1737  }
1738 
1739  /// Returns the largest possible size of the B+ Tree. This is just a
1740  /// function required by the STL standard, the B+ Tree can hold more items.
1741  inline size_type max_size() const
1742  {
1743  return size_type(-1);
1744  }
1745 
1746  /// Return a const reference to the current statistics.
1747  inline const struct tree_stats& get_stats() const
1748  {
1749  return m_stats;
1750  }
1751 
1752 public:
1753  // *** Standard Access Functions Querying the Tree by Descending to a Leaf
1754 
1755  /// Non-STL function checking whether a key is in the B+ tree. The same as
1756  /// (find(k) != end()) or (count() != 0).
1757  bool exists(const key_type &key) const
1758  {
1759  const node *n = m_root;
1760  if (!n) return false;
1761 
1762  while(!n->isleafnode())
1763  {
1764  const inner_node *inner = static_cast<const inner_node*>(n);
1765  int slot = find_lower(inner, key);
1766 
1767  n = inner->childid[slot];
1768  }
1769 
1770  const leaf_node *leaf = static_cast<const leaf_node*>(n);
1771 
1772  int slot = find_lower(leaf, key);
1773  return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]));
1774  }
1775 
1776  /// Tries to locate a key in the B+ tree and returns an iterator to the
1777  /// key/data slot if found. If unsuccessful it returns end().
1778  iterator find(const key_type &key)
1779  {
1780  node *n = m_root;
1781  if (!n) return end();
1782 
1783  while(!n->isleafnode())
1784  {
1785  const inner_node *inner = static_cast<const inner_node*>(n);
1786  int slot = find_lower(inner, key);
1787 
1788  n = inner->childid[slot];
1789  }
1790 
1791  leaf_node *leaf = static_cast<leaf_node*>(n);
1792 
1793  int slot = find_lower(leaf, key);
1794  return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
1795  ? iterator(leaf, slot) : end();
1796  }
1797 
1798  /// Tries to locate a key in the B+ tree and returns an constant iterator
1799  /// to the key/data slot if found. If unsuccessful it returns end().
1800  const_iterator find(const key_type &key) const
1801  {
1802  const node *n = m_root;
1803  if (!n) return end();
1804 
1805  while(!n->isleafnode())
1806  {
1807  const inner_node *inner = static_cast<const inner_node*>(n);
1808  int slot = find_lower(inner, key);
1809 
1810  n = inner->childid[slot];
1811  }
1812 
1813  const leaf_node *leaf = static_cast<const leaf_node*>(n);
1814 
1815  int slot = find_lower(leaf, key);
1816  return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
1817  ? const_iterator(leaf, slot) : end();
1818  }
1819 
1820  /// Tries to locate a key in the B+ tree and returns the number of
1821  /// identical key entries found.
1822  size_type count(const key_type &key) const
1823  {
1824  const node *n = m_root;
1825  if (!n) return 0;
1826 
1827  while(!n->isleafnode())
1828  {
1829  const inner_node *inner = static_cast<const inner_node*>(n);
1830  int slot = find_lower(inner, key);
1831 
1832  n = inner->childid[slot];
1833  }
1834 
1835  const leaf_node *leaf = static_cast<const leaf_node*>(n);
1836 
1837  int slot = find_lower(leaf, key);
1838  size_type num = 0;
1839 
1840  while (leaf && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
1841  {
1842  ++num;
1843  if (++slot >= leaf->slotuse)
1844  {
1845  leaf = leaf->nextleaf;
1846  slot = 0;
1847  }
1848  }
1849 
1850  return num;
1851  }
1852 
1853  /// Searches the B+ tree and returns an iterator to the first pair
1854  /// equal to or greater than key, or end() if all keys are smaller.
1855  iterator lower_bound(const key_type& key)
1856  {
1857  node *n = m_root;
1858  if (!n) return end();
1859 
1860  while(!n->isleafnode())
1861  {
1862  const inner_node *inner = static_cast<const inner_node*>(n);
1863  int slot = find_lower(inner, key);
1864 
1865  n = inner->childid[slot];
1866  }
1867 
1868  leaf_node *leaf = static_cast<leaf_node*>(n);
1869 
1870  int slot = find_lower(leaf, key);
1871  return iterator(leaf, slot);
1872  }
1873 
1874  /// Searches the B+ tree and returns a constant iterator to the
1875  /// first pair equal to or greater than key, or end() if all keys
1876  /// are smaller.
1877  const_iterator lower_bound(const key_type& key) const
1878  {
1879  const node *n = m_root;
1880  if (!n) return end();
1881 
1882  while(!n->isleafnode())
1883  {
1884  const inner_node *inner = static_cast<const inner_node*>(n);
1885  int slot = find_lower(inner, key);
1886 
1887  n = inner->childid[slot];
1888  }
1889 
1890  const leaf_node *leaf = static_cast<const leaf_node*>(n);
1891 
1892  int slot = find_lower(leaf, key);
1893  return const_iterator(leaf, slot);
1894  }
1895 
1896  /// Searches the B+ tree and returns an iterator to the first pair
1897  /// greater than key, or end() if all keys are smaller or equal.
1898  iterator upper_bound(const key_type& key)
1899  {
1900  node *n = m_root;
1901  if (!n) return end();
1902 
1903  while(!n->isleafnode())
1904  {
1905  const inner_node *inner = static_cast<const inner_node*>(n);
1906  int slot = find_upper(inner, key);
1907 
1908  n = inner->childid[slot];
1909  }
1910 
1911  leaf_node *leaf = static_cast<leaf_node*>(n);
1912 
1913  int slot = find_upper(leaf, key);
1914  return iterator(leaf, slot);
1915  }
1916 
1917  /// Searches the B+ tree and returns a constant iterator to the
1918  /// first pair greater than key, or end() if all keys are smaller
1919  /// or equal.
1920  const_iterator upper_bound(const key_type& key) const
1921  {
1922  const node *n = m_root;
1923  if (!n) return end();
1924 
1925  while(!n->isleafnode())
1926  {
1927  const inner_node *inner = static_cast<const inner_node*>(n);
1928  int slot = find_upper(inner, key);
1929 
1930  n = inner->childid[slot];
1931  }
1932 
1933  const leaf_node *leaf = static_cast<const leaf_node*>(n);
1934 
1935  int slot = find_upper(leaf, key);
1936  return const_iterator(leaf, slot);
1937  }
1938 
1939  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
1940  inline std::pair<iterator, iterator> equal_range(const key_type& key)
1941  {
1942  return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
1943  }
1944 
1945  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
1946  inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1947  {
1948  return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
1949  }
1950 
1951 public:
1952  // *** B+ Tree Object Comparison Functions
1953 
1954  /// Equality relation of B+ trees of the same type. B+ trees of the same
1955  /// size and equal elements (both key and data) are considered
1956  /// equal. Beware of the random ordering of duplicate keys.
1957  inline bool operator==(const btree_self &other) const
1958  {
1959  return (size() == other.size()) && std::equal(begin(), end(), other.begin());
1960  }
1961 
1962  /// Inequality relation. Based on operator==.
1963  inline bool operator!=(const btree_self &other) const
1964  {
1965  return !(*this == other);
1966  }
1967 
1968  /// Total ordering relation of B+ trees of the same type. It uses
1969  /// std::lexicographical_compare() for the actual comparison of elements.
1970  inline bool operator<(const btree_self &other) const
1971  {
1972  return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
1973  }
1974 
1975  /// Greater relation. Based on operator<.
1976  inline bool operator>(const btree_self &other) const
1977  {
1978  return other < *this;
1979  }
1980 
1981  /// Less-equal relation. Based on operator<.
1982  inline bool operator<=(const btree_self &other) const
1983  {
1984  return !(other < *this);
1985  }
1986 
1987  /// Greater-equal relation. Based on operator<.
1988  inline bool operator>=(const btree_self &other) const
1989  {
1990  return !(*this < other);
1991  }
1992 
1993 public:
1994  /// *** Fast Copy: Assign Operator and Copy Constructors
1995 
1996  /// Assignment operator. All the key/data pairs are copied
1997  inline btree_self& operator= (const btree_self &other)
1998  {
1999  if (this != &other)
2000  {
2001  clear();
2002 
2003  m_key_less = other.key_comp();
2004  m_allocator = other.get_allocator();
2005 
2006  if (other.size() != 0)
2007  {
2008  m_stats.leaves = m_stats.innernodes = 0;
2009  if (other.m_root) {
2010  m_root = copy_recursive(other.m_root);
2011  }
2012  m_stats = other.m_stats;
2013  }
2014 
2015  if (selfverify) verify();
2016  }
2017  return *this;
2018  }
2019 
2020  /// Copy constructor. The newly initialized B+ tree object will contain a
2021  /// copy of all key/data pairs.
2022  inline btree(const btree_self &other)
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() )
2027  {
2028  if (size() > 0)
2029  {
2030  m_stats.leaves = m_stats.innernodes = 0;
2031  if (other.m_root) {
2032  m_root = copy_recursive(other.m_root);
2033  }
2034  if (selfverify) verify();
2035  }
2036  }
2037 
2038 private:
2039  /// Recursively copy nodes from another B+ tree object
2040  struct node* copy_recursive(const node *n)
2041  {
2042  if (n->isleafnode())
2043  {
2044  const leaf_node *leaf = static_cast<const leaf_node*>(n);
2045  leaf_node *newleaf = allocate_leaf();
2046 
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);
2050 
2051  if (m_headleaf == NULL)
2052  {
2053  m_headleaf = m_tailleaf = newleaf;
2054  newleaf->prevleaf = newleaf->nextleaf = NULL;
2055  }
2056  else
2057  {
2058  newleaf->prevleaf = m_tailleaf;
2059  m_tailleaf->nextleaf = newleaf;
2060  m_tailleaf = newleaf;
2061  }
2062 
2063  return newleaf;
2064  }
2065  else
2066  {
2067  const inner_node *inner = static_cast<const inner_node*>(n);
2068  inner_node *newinner = allocate_inner(inner->level);
2069 
2070  newinner->slotuse = inner->slotuse;
2071  std::copy(inner->slotkey, inner->slotkey + inner->slotuse, newinner->slotkey);
2072 
2073  for (unsigned short slot = 0; slot <= inner->slotuse; ++slot)
2074  {
2075  newinner->childid[slot] = copy_recursive(inner->childid[slot]);
2076  }
2077 
2078  return newinner;
2079  }
2080  }
2081 
2082 public:
2083  // *** Public Insertion Functions
2084 
2085  /// Attempt to insert a key/data pair into the B+ tree. If the tree does not
2086  /// allow duplicate keys, then the insert may fail if it is already
2087  /// present.
2088  inline std::pair<iterator, bool> insert(const pair_type& x)
2089  {
2090  return insert_start(x.first, x.second);
2091  }
2092 
2093  /// Attempt to insert a key/data pair into the B+ tree. Beware that if
2094  /// key_type == data_type, then the template iterator insert() is called
2095  /// instead. If the tree does not allow duplicate keys, then the insert may
2096  /// fail if it is already present.
2097  inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
2098  {
2099  return insert_start(key, data);
2100  }
2101 
2102  /// Attempt to insert a key/data pair into the B+ tree. This function is the
2103  /// same as the other insert, however if key_type == data_type then the
2104  /// non-template function cannot be called. If the tree does not allow
2105  /// duplicate keys, then the insert may fail if it is already present.
2106  inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
2107  {
2108  return insert_start(key, data);
2109  }
2110 
2111  /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
2112  /// is currently ignored by the B+ tree insertion routine.
2113  inline iterator insert(iterator /* hint */, const pair_type &x)
2114  {
2115  return insert_start(x.first, x.second).first;
2116  }
2117 
2118  /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
2119  /// currently ignored by the B+ tree insertion routine.
2120  inline iterator insert2(iterator /* hint */, const key_type& key, const data_type& data)
2121  {
2122  return insert_start(key, data).first;
2123  }
2124 
2125  /// Attempt to insert the range [first,last) of value_type pairs into the
2126  /// B+ tree. Each key/data pair is inserted individually; to bulk load the
2127  /// tree, use a constructor with range.
2128  template <typename InputIterator>
2129  inline void insert(InputIterator first, InputIterator last)
2130  {
2131  InputIterator iter = first;
2132  while(iter != last)
2133  {
2134  insert(*iter);
2135  ++iter;
2136  }
2137  }
2138 
2139 private:
2140  // *** Private Insertion Functions
2141 
2142  /// Start the insertion descent at the current root and handle root
2143  /// splits. Returns true if the item was inserted
2144  std::pair<iterator, bool> insert_start(const key_type& key, const data_type& value)
2145  {
2146  node *newchild = NULL;
2147  key_type newkey = key_type();
2148 
2149  if (m_root == NULL) {
2150  m_root = m_headleaf = m_tailleaf = allocate_leaf();
2151  }
2152 
2153  std::pair<iterator, bool> r = insert_descend(m_root, key, value, &newkey, &newchild);
2154 
2155  if (newchild)
2156  {
2157  inner_node *newroot = allocate_inner(m_root->level + 1);
2158  newroot->slotkey[0] = newkey;
2159 
2160  newroot->childid[0] = m_root;
2161  newroot->childid[1] = newchild;
2162 
2163  newroot->slotuse = 1;
2164 
2165  m_root = newroot;
2166  }
2167 
2168  // increment itemcount if the item was inserted
2169  if (r.second) ++m_stats.itemcount;
2170 
2171 #ifdef BTREE_DEBUG
2172  if (debug) print(std::cout);
2173 #endif
2174 
2175  if (selfverify) {
2176  verify();
2177  BTREE_ASSERT(exists(key));
2178  }
2179 
2180  return r;
2181  }
2182 
2183  /**
2184  * @brief Insert an item into the B+ tree.
2185  *
2186  * Descend down the nodes to a leaf, insert the key/data pair in a free
2187  * slot. If the node overflows, then it must be split and the new split
2188  * node inserted into the parent. Unroll / this splitting up to the root.
2189  */
2190  std::pair<iterator, bool> insert_descend(node* n,
2191  const key_type& key, const data_type& value,
2192  key_type* splitkey, node** splitnode)
2193  {
2194  if (!n->isleafnode())
2195  {
2196  inner_node *inner = static_cast<inner_node*>(n);
2197 
2198  key_type newkey = key_type();
2199  node *newchild = NULL;
2200 
2201  int slot = find_lower(inner, key);
2202 
2203  BTREE_PRINT("btree::insert_descend into " << inner->childid[slot]);
2204 
2205  std::pair<iterator, bool> r = insert_descend(inner->childid[slot],
2206  key, value, &newkey, &newchild);
2207 
2208  if (newchild)
2209  {
2210  BTREE_PRINT("btree::insert_descend newchild with key " << newkey << " node " << newchild << " at slot " << slot);
2211 
2212  if (inner->isfull())
2213  {
2214  split_inner_node(inner, splitkey, splitnode, slot);
2215 
2216  BTREE_PRINT("btree::insert_descend done split_inner: putslot: " << slot << " putkey: " << newkey << " upkey: " << *splitkey);
2217 
2218 #ifdef BTREE_DEBUG
2219  if (debug)
2220  {
2221  print_node(std::cout, inner);
2222  print_node(std::cout, *splitnode);
2223  }
2224 #endif
2225 
2226  // check if insert slot is in the split sibling node
2227  BTREE_PRINT("btree::insert_descend switch: " << slot << " > " << inner->slotuse+1);
2228 
2229  if (slot == inner->slotuse+1 && inner->slotuse < (*splitnode)->slotuse)
2230  {
2231  // special case when the insert slot matches the split
2232  // place between the two nodes, then the insert key
2233  // becomes the split key.
2234 
2235  BTREE_ASSERT(inner->slotuse + 1 < innerslotmax);
2236 
2237  inner_node *splitinner = static_cast<inner_node*>(*splitnode);
2238 
2239  // move the split key and it's datum into the left node
2240  inner->slotkey[inner->slotuse] = *splitkey;
2241  inner->childid[inner->slotuse+1] = splitinner->childid[0];
2242  inner->slotuse++;
2243 
2244  // set new split key and move corresponding datum into right node
2245  splitinner->childid[0] = newchild;
2246  *splitkey = newkey;
2247 
2248  return r;
2249  }
2250  else if (slot >= inner->slotuse+1)
2251  {
2252  // in case the insert slot is in the newly create split
2253  // node, we reuse the code below.
2254 
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);
2258  }
2259  }
2260 
2261  // move items and put pointer to child node into correct slot
2262  BTREE_ASSERT(slot >= 0 && slot <= inner->slotuse);
2263 
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);
2268 
2269  inner->slotkey[slot] = newkey;
2270  inner->childid[slot + 1] = newchild;
2271  inner->slotuse++;
2272  }
2273 
2274  return r;
2275  }
2276  else // n->isleafnode() == true
2277  {
2278  leaf_node *leaf = static_cast<leaf_node*>(n);
2279 
2280  int slot = find_lower(leaf, key);
2281 
2282  if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) {
2283  return std::pair<iterator, bool>(iterator(leaf, slot), false);
2284  }
2285 
2286  if (leaf->isfull())
2287  {
2288  split_leaf_node(leaf, splitkey, splitnode);
2289 
2290  // check if insert slot is in the split sibling node
2291  if (slot >= leaf->slotuse)
2292  {
2293  slot -= leaf->slotuse;
2294  leaf = static_cast<leaf_node*>(*splitnode);
2295  }
2296  }
2297 
2298  // move items and put data item into correct data slot
2299  BTREE_ASSERT(slot >= 0 && slot <= leaf->slotuse);
2300 
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);
2305 
2306  leaf->slotkey[slot] = key;
2307  if (!used_as_set) leaf->slotdata[slot] = value;
2308  leaf->slotuse++;
2309 
2310  if (splitnode && leaf != *splitnode && slot == leaf->slotuse-1)
2311  {
2312  // special case: the node was split, and the insert is at the
2313  // last slot of the old node. then the splitkey must be
2314  // updated.
2315  *splitkey = key;
2316  }
2317 
2318  return std::pair<iterator, bool>(iterator(leaf, slot), true);
2319  }
2320  }
2321 
2322  /// Split up a leaf node into two equally-filled sibling leaves. Returns
2323  /// the new nodes and it's insertion key in the two parameters.
2324  void split_leaf_node(leaf_node* leaf, key_type* _newkey, node** _newleaf)
2325  {
2326  BTREE_ASSERT(leaf->isfull());
2327 
2328  unsigned int mid = (leaf->slotuse >> 1);
2329 
2330  BTREE_PRINT("btree::split_leaf_node on " << leaf);
2331 
2332  leaf_node *newleaf = allocate_leaf();
2333 
2334  newleaf->slotuse = leaf->slotuse - mid;
2335 
2336  newleaf->nextleaf = leaf->nextleaf;
2337  if (newleaf->nextleaf == NULL) {
2338  BTREE_ASSERT(leaf == m_tailleaf);
2339  m_tailleaf = newleaf;
2340  }
2341  else {
2342  newleaf->nextleaf->prevleaf = newleaf;
2343  }
2344 
2345  std::copy(leaf->slotkey + mid, leaf->slotkey + leaf->slotuse,
2346  newleaf->slotkey);
2347  data_copy(leaf->slotdata + mid, leaf->slotdata + leaf->slotuse,
2348  newleaf->slotdata);
2349 
2350  leaf->slotuse = mid;
2351  leaf->nextleaf = newleaf;
2352  newleaf->prevleaf = leaf;
2353 
2354  *_newkey = leaf->slotkey[leaf->slotuse-1];
2355  *_newleaf = newleaf;
2356  }
2357 
2358  /// Split up an inner node into two equally-filled sibling nodes. Returns
2359  /// the new nodes and it's insertion key in the two parameters. Requires
2360  /// the slot of the item will be inserted, so the nodes will be the same
2361  /// size after the insert.
2362  void split_inner_node(inner_node* inner, key_type* _newkey, node** _newinner, unsigned int addslot)
2363  {
2364  BTREE_ASSERT(inner->isfull());
2365 
2366  unsigned int mid = (inner->slotuse >> 1);
2367 
2368  BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot);
2369 
2370  // if the split is uneven and the overflowing item will be put into the
2371  // larger node, then the smaller split node may underflow
2372  if (addslot <= mid && mid > inner->slotuse - (mid + 1))
2373  mid--;
2374 
2375  BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot);
2376 
2377  BTREE_PRINT("btree::split_inner_node on " << inner << " into two nodes " << mid << " and " << inner->slotuse - (mid + 1) << " sized");
2378 
2379  inner_node *newinner = allocate_inner(inner->level);
2380 
2381  newinner->slotuse = inner->slotuse - (mid + 1);
2382 
2383  std::copy(inner->slotkey + mid+1, inner->slotkey + inner->slotuse,
2384  newinner->slotkey);
2385  std::copy(inner->childid + mid+1, inner->childid + inner->slotuse+1,
2386  newinner->childid);
2387 
2388  inner->slotuse = mid;
2389 
2390  *_newkey = inner->slotkey[mid];
2391  *_newinner = newinner;
2392  }
2393 
2394 public:
2395 
2396  // *** Bulk Loader - Construct Tree from Sorted Sequence
2397 
2398  /// Bulk load a sorted range. Loads items into leaves and constructs a
2399  /// B-tree above them. The tree must be empty when calling this function.
2400  template <typename Iterator>
2401  void bulk_load(Iterator ibegin, Iterator iend)
2402  {
2403  BTREE_ASSERT(empty());
2404 
2405  m_stats.itemcount = iend - ibegin;
2406 
2407  // calculate number of leaves needed, round up.
2408  size_t num_items = iend - ibegin;
2409  size_t num_leaves = (num_items + leafslotmax-1) / leafslotmax;
2410 
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.");
2412 
2413  Iterator it = ibegin;
2414  for (size_t i = 0; i < num_leaves; ++i)
2415  {
2416  // allocate new leaf node
2417  leaf_node* leaf = allocate_leaf();
2418 
2419  // copy keys or (key,value) pairs into leaf nodes, uses template
2420  // switch leaf->set_slot().
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);
2424 
2425  if (m_tailleaf != NULL) {
2426  m_tailleaf->nextleaf = leaf;
2427  leaf->prevleaf = m_tailleaf;
2428  }
2429  else {
2430  m_headleaf = leaf;
2431  }
2432  m_tailleaf = leaf;
2433 
2434  num_items -= leaf->slotuse;
2435  }
2436 
2437  BTREE_ASSERT( it == iend && num_items == 0 );
2438 
2439  // if the btree is so small to fit into one leaf, then we're done.
2440  if (m_headleaf == m_tailleaf) {
2441  m_root = m_headleaf;
2442  return;
2443  }
2444 
2445  BTREE_ASSERT( m_stats.leaves == num_leaves );
2446 
2447  // create first level of inner nodes, pointing to the leaves.
2448  size_t num_parents = (num_leaves + (innerslotmax+1)-1) / (innerslotmax+1);
2449 
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.");
2451 
2452  // save inner nodes and maxkey for next level.
2453  typedef std::pair<inner_node*, const key_type*> nextlevel_type;
2454  nextlevel_type* nextlevel = new nextlevel_type[num_parents];
2455 
2456  leaf_node* leaf = m_headleaf;
2457  for (size_t i = 0; i < num_parents; ++i)
2458  {
2459  // allocate new inner node at level 1
2460  inner_node* n = allocate_inner(1);
2461 
2462  n->slotuse = static_cast<int>(num_leaves / (num_parents-i));
2463  BTREE_ASSERT(n->slotuse > 0);
2464  --n->slotuse; // this counts keys, but an inner node has keys+1 children.
2465 
2466  // copy last key from each leaf and set child
2467  for (unsigned short s = 0; s < n->slotuse; ++s)
2468  {
2469  n->slotkey[s] = leaf->slotkey[leaf->slotuse-1];
2470  n->childid[s] = leaf;
2471  leaf = leaf->nextleaf;
2472  }
2473  n->childid[n->slotuse] = leaf;
2474 
2475  // track max key of any descendant.
2476  nextlevel[i].first = n;
2477  nextlevel[i].second = &leaf->slotkey[leaf->slotuse-1];
2478 
2479  leaf = leaf->nextleaf;
2480  num_leaves -= n->slotuse+1;
2481  }
2482 
2483  BTREE_ASSERT( leaf == NULL && num_leaves == 0 );
2484 
2485  // recursively build inner nodes pointing to inner nodes.
2486  for (int level = 2; num_parents != 1; ++level)
2487  {
2488  size_t num_children = num_parents;
2489  num_parents = (num_children + (innerslotmax+1)-1) / (innerslotmax+1);
2490 
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.");
2492 
2493  size_t inner_index = 0;
2494  for (size_t i = 0; i < num_parents; ++i)
2495  {
2496  // allocate new inner node at level
2497  inner_node* n = allocate_inner(level);
2498 
2499  n->slotuse = static_cast<int>(num_children / (num_parents-i));
2500  BTREE_ASSERT(n->slotuse > 0);
2501  --n->slotuse; // this counts keys, but an inner node has keys+1 children.
2502 
2503  // copy children and maxkeys from nextlevel
2504  for (unsigned short s = 0; s < n->slotuse; ++s)
2505  {
2506  n->slotkey[s] = *nextlevel[inner_index].second;
2507  n->childid[s] = nextlevel[inner_index].first;
2508  ++inner_index;
2509  }
2510  n->childid[n->slotuse] = nextlevel[inner_index].first;
2511 
2512  // reuse nextlevel array for parents, because we can overwrite
2513  // slots we've already consumed.
2514  nextlevel[i].first = n;
2515  nextlevel[i].second = nextlevel[inner_index].second;
2516 
2517  ++inner_index;
2518  num_children -= n->slotuse+1;
2519  }
2520 
2521  BTREE_ASSERT( num_children == 0 );
2522  }
2523 
2524  m_root = nextlevel[0].first;
2525  delete [] nextlevel;
2526 
2527  if (selfverify) verify();
2528  }
2529 
2530 private:
2531  // *** Support Class Encapsulating Deletion Results
2532 
2533  /// Result flags of recursive deletion.
2535  {
2536  /// Deletion successful and no fix-ups necessary.
2537  btree_ok = 0,
2538 
2539  /// Deletion not successful because key was not found.
2540  btree_not_found = 1,
2541 
2542  /// Deletion successful, the last key was updated so parent slotkeys
2543  /// need updates.
2544  btree_update_lastkey = 2,
2545 
2546  /// Deletion successful, children nodes were merged and the parent
2547  /// needs to remove the empty node.
2548  btree_fixmerge = 4
2549  };
2550 
2551  /// B+ tree recursive deletion has much information which is needs to be
2552  /// passed upward.
2553  struct result_t
2554  {
2555  /// Merged result flags
2557 
2558  /// The key to be updated at the parent's slot
2559  key_type lastkey;
2560 
2561  /// Constructor of a result with a specific flag, this can also be used
2562  /// as for implicit conversion.
2563  inline result_t(result_flags_t f = btree_ok)
2564  : flags(f), lastkey()
2565  { }
2566 
2567  /// Constructor with a lastkey value.
2568  inline result_t(result_flags_t f, const key_type &k)
2569  : flags(f), lastkey(k)
2570  { }
2571 
2572  /// Test if this result object has a given flag set.
2573  inline bool has(result_flags_t f) const
2574  {
2575  return (flags & f) != 0;
2576  }
2577 
2578  /// Merge two results OR-ing the result flags and overwriting lastkeys.
2579  inline result_t& operator|= (const result_t &other)
2580  {
2581  flags = result_flags_t(flags | other.flags);
2582 
2583  // we overwrite existing lastkeys on purpose
2584  if (other.has(btree_update_lastkey))
2585  lastkey = other.lastkey;
2586 
2587  return *this;
2588  }
2589  };
2590 
2591 public:
2592  // *** Public Erase Functions
2593 
2594  /// Erases one (the first) of the key/data pairs associated with the given
2595  /// key.
2596  bool erase_one(const key_type &key)
2597  {
2598  BTREE_PRINT("btree::erase_one(" << key << ") on btree size " << size());
2599 
2600  if (selfverify) verify();
2601 
2602  if (!m_root) return false;
2603 
2604  result_t result = erase_one_descend(key, m_root, NULL, NULL, NULL, NULL, NULL, 0);
2605 
2606  if (!result.has(btree_not_found))
2607  --m_stats.itemcount;
2608 
2609 #ifdef BTREE_DEBUG
2610  if (debug) print(std::cout);
2611 #endif
2612  if (selfverify) verify();
2613 
2614  return !result.has(btree_not_found);
2615  }
2616 
2617  /// Erases all the key/data pairs associated with the given key. This is
2618  /// implemented using erase_one().
2619  size_type erase(const key_type &key)
2620  {
2621  size_type c = 0;
2622 
2623  while( erase_one(key) )
2624  {
2625  ++c;
2626  if (!allow_duplicates) break;
2627  }
2628 
2629  return c;
2630  }
2631 
2632  /// Erase the key/data pair referenced by the iterator.
2633  void erase(iterator iter)
2634  {
2635  BTREE_PRINT("btree::erase_iter(" << iter.currnode << "," << iter.currslot << ") on btree size " << size());
2636 
2637  if (selfverify) verify();
2638 
2639  if (!m_root) return;
2640 
2641  result_t result = erase_iter_descend(iter, m_root, NULL, NULL, NULL, NULL, NULL, 0);
2642 
2643  if (!result.has(btree_not_found))
2644  --m_stats.itemcount;
2645 
2646 #ifdef BTREE_DEBUG
2647  if (debug) print(std::cout);
2648 #endif
2649  if (selfverify) verify();
2650  }
2651 
2652 #ifdef BTREE_TODO
2653  /// Erase all key/data pairs in the range [first,last). This function is
2654  /// currently not implemented by the B+ Tree.
2655  void erase(iterator /* first */, iterator /* last */)
2656  {
2657  abort();
2658  }
2659 #endif
2660 
2661 private:
2662  // *** Private Erase Functions
2663 
2664  /** @brief Erase one (the first) key/data pair in the B+ tree matching key.
2665  *
2666  * Descends down the tree in search of key. During the descent the parent,
2667  * left and right siblings and their parents are computed and passed
2668  * down. Once the key/data pair is found, it is removed from the leaf. If
2669  * the leaf underflows 6 different cases are handled. These cases resolve
2670  * the underflow by shifting key/data pairs from adjacent sibling nodes,
2671  * merging two sibling nodes or trimming the tree.
2672  */
2673  result_t erase_one_descend(const key_type& key,
2674  node *curr,
2675  node *left, node *right,
2676  inner_node *leftparent, inner_node *rightparent,
2677  inner_node *parent, unsigned int parentslot)
2678  {
2679  if (curr->isleafnode())
2680  {
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);
2684 
2685  int slot = find_lower(leaf, key);
2686 
2687  if (slot >= leaf->slotuse || !key_equal(key, leaf->slotkey[slot]))
2688  {
2689  BTREE_PRINT("Could not find key " << key << " to erase.");
2690 
2691  return btree_not_found;
2692  }
2693 
2694  BTREE_PRINT("Found key in leaf " << curr << " at slot " << slot);
2695 
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);
2700 
2701  leaf->slotuse--;
2702 
2703  result_t myres = btree_ok;
2704 
2705  // if the last key of the leaf was changed, the parent is notified
2706  // and updates the key of this leaf
2707  if (slot == leaf->slotuse)
2708  {
2709  if (parent && parentslot < parent->slotuse)
2710  {
2711  BTREE_ASSERT(parent->childid[parentslot] == curr);
2712  parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
2713  }
2714  else
2715  {
2716  if (leaf->slotuse >= 1)
2717  {
2718  BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1]);
2719  myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
2720  }
2721  else
2722  {
2723  BTREE_ASSERT(leaf == m_root);
2724  }
2725  }
2726  }
2727 
2728  if (leaf->isunderflow() && !(leaf == m_root && leaf->slotuse >= 1))
2729  {
2730  // determine what to do about the underflow
2731 
2732  // case : if this empty leaf is the root, then delete all nodes
2733  // and set root to NULL.
2734  if (leftleaf == NULL && rightleaf == NULL)
2735  {
2736  BTREE_ASSERT(leaf == m_root);
2737  BTREE_ASSERT(leaf->slotuse == 0);
2738 
2739  free_node(m_root);
2740 
2741  m_root = leaf = NULL;
2742  m_headleaf = m_tailleaf = NULL;
2743 
2744  // will be decremented soon by insert_start()
2745  BTREE_ASSERT(m_stats.itemcount == 1);
2746  BTREE_ASSERT(m_stats.leaves == 0);
2747  BTREE_ASSERT(m_stats.innernodes == 0);
2748 
2749  return btree_ok;
2750  }
2751  // case : if both left and right leaves would underflow in case of
2752  // a shift, then merging is necessary. choose the more local merger
2753  // with our parent
2754  else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
2755  {
2756  if (leftparent == parent)
2757  myres |= merge_leaves(leftleaf, leaf, leftparent);
2758  else
2759  myres |= merge_leaves(leaf, rightleaf, rightparent);
2760  }
2761  // case : the right leaf has extra data, so balance right with current
2762  else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
2763  {
2764  if (rightparent == parent)
2765  myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2766  else
2767  myres |= merge_leaves(leftleaf, leaf, leftparent);
2768  }
2769  // case : the left leaf has extra data, so balance left with current
2770  else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
2771  {
2772  if (leftparent == parent)
2773  shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2774  else
2775  myres |= merge_leaves(leaf, rightleaf, rightparent);
2776  }
2777  // case : both the leaf and right leaves have extra data and our
2778  // parent, choose the leaf with more data
2779  else if (leftparent == rightparent)
2780  {
2781  if (leftleaf->slotuse <= rightleaf->slotuse)
2782  myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2783  else
2784  shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2785  }
2786  else
2787  {
2788  if (leftparent == parent)
2789  shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2790  else
2791  myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2792  }
2793  }
2794 
2795  return myres;
2796  }
2797  else // !curr->isleafnode()
2798  {
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);
2802 
2803  node *myleft, *myright;
2804  inner_node *myleftparent, *myrightparent;
2805 
2806  int slot = find_lower(inner, key);
2807 
2808  if (slot == 0) {
2809  myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
2810  myleftparent = leftparent;
2811  }
2812  else {
2813  myleft = inner->childid[slot - 1];
2814  myleftparent = inner;
2815  }
2816 
2817  if (slot == inner->slotuse) {
2818  myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
2819  myrightparent = rightparent;
2820  }
2821  else {
2822  myright = inner->childid[slot + 1];
2823  myrightparent = inner;
2824  }
2825 
2826  BTREE_PRINT("erase_one_descend into " << inner->childid[slot]);
2827 
2828  result_t result = erase_one_descend(key,
2829  inner->childid[slot],
2830  myleft, myright,
2831  myleftparent, myrightparent,
2832  inner, slot);
2833 
2834  result_t myres = btree_ok;
2835 
2836  if (result.has(btree_not_found))
2837  {
2838  return result;
2839  }
2840 
2841  if (result.has(btree_update_lastkey))
2842  {
2843  if (parent && parentslot < parent->slotuse)
2844  {
2845  BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot);
2846 
2847  BTREE_ASSERT(parent->childid[parentslot] == curr);
2848  parent->slotkey[parentslot] = result.lastkey;
2849  }
2850  else
2851  {
2852  BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey);
2853  myres |= result_t(btree_update_lastkey, result.lastkey);
2854  }
2855  }
2856 
2857  if (result.has(btree_fixmerge))
2858  {
2859  // either the current node or the next is empty and should be removed
2860  if (inner->childid[slot]->slotuse != 0)
2861  slot++;
2862 
2863  // this is the child slot invalidated by the merge
2864  BTREE_ASSERT(inner->childid[slot]->slotuse == 0);
2865 
2866  free_node(inner->childid[slot]);
2867 
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);
2872 
2873  inner->slotuse--;
2874 
2875  if (inner->level == 1)
2876  {
2877  // fix split key for children leaves
2878  slot--;
2879  leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]);
2880  inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
2881  }
2882  }
2883 
2884  if (inner->isunderflow() && !(inner == m_root && inner->slotuse >= 1))
2885  {
2886  // case: the inner node is the root and has just one child. that child becomes the new root
2887  if (leftinner == NULL && rightinner == NULL)
2888  {
2889  BTREE_ASSERT(inner == m_root);
2890  BTREE_ASSERT(inner->slotuse == 0);
2891 
2892  m_root = inner->childid[0];
2893 
2894  inner->slotuse = 0;
2895  free_node(inner);
2896 
2897  return btree_ok;
2898  }
2899  // case : if both left and right leaves would underflow in case of
2900  // a shift, then merging is necessary. choose the more local merger
2901  // with our parent
2902  else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
2903  {
2904  if (leftparent == parent)
2905  myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
2906  else
2907  myres |= merge_inner(inner, rightinner, rightparent, parentslot);
2908  }
2909  // case : the right leaf has extra data, so balance right with current
2910  else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
2911  {
2912  if (rightparent == parent)
2913  shift_left_inner(inner, rightinner, rightparent, parentslot);
2914  else
2915  myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
2916  }
2917  // case : the left leaf has extra data, so balance left with current
2918  else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
2919  {
2920  if (leftparent == parent)
2921  shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2922  else
2923  myres |= merge_inner(inner, rightinner, rightparent, parentslot);
2924  }
2925  // case : both the leaf and right leaves have extra data and our
2926  // parent, choose the leaf with more data
2927  else if (leftparent == rightparent)
2928  {
2929  if (leftinner->slotuse <= rightinner->slotuse)
2930  shift_left_inner(inner, rightinner, rightparent, parentslot);
2931  else
2932  shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2933  }
2934  else
2935  {
2936  if (leftparent == parent)
2937  shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2938  else
2939  shift_left_inner(inner, rightinner, rightparent, parentslot);
2940  }
2941  }
2942 
2943  return myres;
2944  }
2945  }
2946 
2947  /** @brief Erase one key/data pair referenced by an iterator in the B+
2948  * tree.
2949  *
2950  * Descends down the tree in search of an iterator. During the descent the
2951  * parent, left and right siblings and their parents are computed and
2952  * passed down. The difficulty is that the iterator contains only a pointer
2953  * to a leaf_node, which means that this function must do a recursive depth
2954  * first search for that leaf node in the subtree containing all pairs of
2955  * the same key. This subtree can be very large, even the whole tree,
2956  * though in practice it would not make sense to have so many duplicate
2957  * keys.
2958  *
2959  * Once the referenced key/data pair is found, it is removed from the leaf
2960  * and the same underflow cases are handled as in erase_one_descend.
2961  */
2962  result_t erase_iter_descend(const iterator& iter,
2963  node *curr,
2964  node *left, node *right,
2965  inner_node *leftparent, inner_node *rightparent,
2966  inner_node *parent, unsigned int parentslot)
2967  {
2968  if (curr->isleafnode())
2969  {
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);
2973 
2974  // if this is not the correct leaf, get next step in recursive
2975  // search
2976  if (leaf != iter.currnode)
2977  {
2978  return btree_not_found;
2979  }
2980 
2981  if (iter.currslot >= leaf->slotuse)
2982  {
2983  BTREE_PRINT("Could not find iterator (" << iter.currnode << "," << iter.currslot << ") to erase. Invalid leaf node?");
2984 
2985  return btree_not_found;
2986  }
2987 
2988  int slot = iter.currslot;
2989 
2990  BTREE_PRINT("Found iterator in leaf " << curr << " at slot " << slot);
2991 
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);
2996 
2997  leaf->slotuse--;
2998 
2999  result_t myres = btree_ok;
3000 
3001  // if the last key of the leaf was changed, the parent is notified
3002  // and updates the key of this leaf
3003  if (slot == leaf->slotuse)
3004  {
3005  if (parent && parentslot < parent->slotuse)
3006  {
3007  BTREE_ASSERT(parent->childid[parentslot] == curr);
3008  parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
3009  }
3010  else
3011  {
3012  if (leaf->slotuse >= 1)
3013  {
3014  BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1]);
3015  myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
3016  }
3017  else
3018  {
3019  BTREE_ASSERT(leaf == m_root);
3020  }
3021  }
3022  }
3023 
3024  if (leaf->isunderflow() && !(leaf == m_root && leaf->slotuse >= 1))
3025  {
3026  // determine what to do about the underflow
3027 
3028  // case : if this empty leaf is the root, then delete all nodes
3029  // and set root to NULL.
3030  if (leftleaf == NULL && rightleaf == NULL)
3031  {
3032  BTREE_ASSERT(leaf == m_root);
3033  BTREE_ASSERT(leaf->slotuse == 0);
3034 
3035  free_node(m_root);
3036 
3037  m_root = leaf = NULL;
3038  m_headleaf = m_tailleaf = NULL;
3039 
3040  // will be decremented soon by insert_start()
3041  BTREE_ASSERT(m_stats.itemcount == 1);
3042  BTREE_ASSERT(m_stats.leaves == 0);
3043  BTREE_ASSERT(m_stats.innernodes == 0);
3044 
3045  return btree_ok;
3046  }
3047  // case : if both left and right leaves would underflow in case of
3048  // a shift, then merging is necessary. choose the more local merger
3049  // with our parent
3050  else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
3051  {
3052  if (leftparent == parent)
3053  myres |= merge_leaves(leftleaf, leaf, leftparent);
3054  else
3055  myres |= merge_leaves(leaf, rightleaf, rightparent);
3056  }
3057  // case : the right leaf has extra data, so balance right with current
3058  else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
3059  {
3060  if (rightparent == parent)
3061  myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
3062  else
3063  myres |= merge_leaves(leftleaf, leaf, leftparent);
3064  }
3065  // case : the left leaf has extra data, so balance left with current
3066  else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
3067  {
3068  if (leftparent == parent)
3069  shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
3070  else
3071  myres |= merge_leaves(leaf, rightleaf, rightparent);
3072  }
3073  // case : both the leaf and right leaves have extra data and our
3074  // parent, choose the leaf with more data
3075  else if (leftparent == rightparent)
3076  {
3077  if (leftleaf->slotuse <= rightleaf->slotuse)
3078  myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
3079  else
3080  shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
3081  }
3082  else
3083  {
3084  if (leftparent == parent)
3085  shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
3086  else
3087  myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
3088  }
3089  }
3090 
3091  return myres;
3092  }
3093  else // !curr->isleafnode()
3094  {
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);
3098 
3099  // find first slot below which the searched iterator might be
3100  // located.
3101 
3102  result_t result;
3103  int slot = find_lower(inner, iter.key());
3104 
3105  while (slot <= inner->slotuse)
3106  {
3107  node *myleft, *myright;
3108  inner_node *myleftparent, *myrightparent;
3109 
3110  if (slot == 0) {
3111  myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
3112  myleftparent = leftparent;
3113  }
3114  else {
3115  myleft = inner->childid[slot - 1];
3116  myleftparent = inner;
3117  }
3118 
3119  if (slot == inner->slotuse) {
3120  myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
3121  myrightparent = rightparent;
3122  }
3123  else {
3124  myright = inner->childid[slot + 1];
3125  myrightparent = inner;
3126  }
3127 
3128  BTREE_PRINT("erase_iter_descend into " << inner->childid[slot]);
3129 
3130  result = erase_iter_descend(iter,
3131  inner->childid[slot],
3132  myleft, myright,
3133  myleftparent, myrightparent,
3134  inner, slot);
3135 
3136  if (!result.has(btree_not_found))
3137  break;
3138 
3139  // continue recursive search for leaf on next slot
3140 
3141  if (slot < inner->slotuse && key_less(inner->slotkey[slot],iter.key()))
3142  return btree_not_found;
3143 
3144  ++slot;
3145  }
3146 
3147  if (slot > inner->slotuse)
3148  return btree_not_found;
3149 
3150  result_t myres = btree_ok;
3151 
3152  if (result.has(btree_update_lastkey))
3153  {
3154  if (parent && parentslot < parent->slotuse)
3155  {
3156  BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot);
3157 
3158  BTREE_ASSERT(parent->childid[parentslot] == curr);
3159  parent->slotkey[parentslot] = result.lastkey;
3160  }
3161  else
3162  {
3163  BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey);
3164  myres |= result_t(btree_update_lastkey, result.lastkey);
3165  }
3166  }
3167 
3168  if (result.has(btree_fixmerge))
3169  {
3170  // either the current node or the next is empty and should be removed
3171  if (inner->childid[slot]->slotuse != 0)
3172  slot++;
3173 
3174  // this is the child slot invalidated by the merge
3175  BTREE_ASSERT(inner->childid[slot]->slotuse == 0);
3176 
3177  free_node(inner->childid[slot]);
3178 
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);
3183 
3184  inner->slotuse--;
3185 
3186  if (inner->level == 1)
3187  {
3188  // fix split key for children leaves
3189  slot--;
3190  leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]);
3191  inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
3192  }
3193  }
3194 
3195  if (inner->isunderflow() && !(inner == m_root && inner->slotuse >= 1))
3196  {
3197  // case: the inner node is the root and has just one
3198  // child. that child becomes the new root
3199  if (leftinner == NULL && rightinner == NULL)
3200  {
3201  BTREE_ASSERT(inner == m_root);
3202  BTREE_ASSERT(inner->slotuse == 0);
3203 
3204  m_root = inner->childid[0];
3205 
3206  inner->slotuse = 0;
3207  free_node(inner);
3208 
3209  return btree_ok;
3210  }
3211  // case : if both left and right leaves would underflow in case of
3212  // a shift, then merging is necessary. choose the more local merger
3213  // with our parent
3214  else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
3215  {
3216  if (leftparent == parent)
3217  myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
3218  else
3219  myres |= merge_inner(inner, rightinner, rightparent, parentslot);
3220  }
3221  // case : the right leaf has extra data, so balance right with current
3222  else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
3223  {
3224  if (rightparent == parent)
3225  shift_left_inner(inner, rightinner, rightparent, parentslot);
3226  else
3227  myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
3228  }
3229  // case : the left leaf has extra data, so balance left with current
3230  else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
3231  {
3232  if (leftparent == parent)
3233  shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
3234  else
3235  myres |= merge_inner(inner, rightinner, rightparent, parentslot);
3236  }
3237  // case : both the leaf and right leaves have extra data and our
3238  // parent, choose the leaf with more data
3239  else if (leftparent == rightparent)
3240  {
3241  if (leftinner->slotuse <= rightinner->slotuse)
3242  shift_left_inner(inner, rightinner, rightparent, parentslot);
3243  else
3244  shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
3245  }
3246  else
3247  {
3248  if (leftparent == parent)
3249  shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
3250  else
3251  shift_left_inner(inner, rightinner, rightparent, parentslot);
3252  }
3253  }
3254 
3255  return myres;
3256  }
3257  }
3258 
3259  /// Merge two leaf nodes. The function moves all key/data pairs from right
3260  /// to left and sets right's slotuse to zero. The right slot is then
3261  /// removed by the calling parent node.
3262  result_t merge_leaves(leaf_node* left, leaf_node* right, inner_node* parent)
3263  {
3264  BTREE_PRINT("Merge leaf nodes " << left << " and " << right << " with common parent " << parent << ".");
3265  (void)parent;
3266 
3267  BTREE_ASSERT(left->isleafnode() && right->isleafnode());
3268  BTREE_ASSERT(parent->level == 1);
3269 
3270  BTREE_ASSERT(left->slotuse + right->slotuse < leafslotmax);
3271 
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);
3276 
3277  left->slotuse += right->slotuse;
3278 
3279  left->nextleaf = right->nextleaf;
3280  if (left->nextleaf)
3281  left->nextleaf->prevleaf = left;
3282  else
3283  m_tailleaf = left;
3284 
3285  right->slotuse = 0;
3286 
3287  return btree_fixmerge;
3288  }
3289 
3290  /// Merge two inner nodes. The function moves all key/childid pairs from
3291  /// right to left and sets right's slotuse to zero. The right slot is then
3292  /// removed by the calling parent node.
3293  static result_t merge_inner(inner_node* left, inner_node* right, inner_node* parent, unsigned int parentslot)
3294  {
3295  BTREE_PRINT("Merge inner nodes " << left << " and " << right << " with common parent " << parent << ".");
3296 
3297  BTREE_ASSERT(left->level == right->level);
3298  BTREE_ASSERT(parent->level == left->level + 1);
3299 
3300  BTREE_ASSERT(parent->childid[parentslot] == left);
3301 
3302  BTREE_ASSERT(left->slotuse + right->slotuse < innerslotmax);
3303 
3304  if (selfverify)
3305  {
3306  // find the left node's slot in the parent's children
3307  unsigned int leftslot = 0;
3308  while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3309  ++leftslot;
3310 
3311  BTREE_ASSERT(leftslot < parent->slotuse);
3312  BTREE_ASSERT(parent->childid[leftslot] == left);
3313  BTREE_ASSERT(parent->childid[leftslot+1] == right);
3314 
3315  BTREE_ASSERT(parentslot == leftslot);
3316  }
3317 
3318  // retrieve the decision key from parent
3319  left->slotkey[left->slotuse] = parent->slotkey[parentslot];
3320  left->slotuse++;
3321 
3322  // copy over keys and children from right
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);
3327 
3328  left->slotuse += right->slotuse;
3329  right->slotuse = 0;
3330 
3331  return btree_fixmerge;
3332  }
3333 
3334  /// Balance two leaf nodes. The function moves key/data pairs from right to
3335  /// left so that both nodes are equally filled. The parent node is updated
3336  /// if possible.
3337  static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
3338  {
3339  BTREE_ASSERT(left->isleafnode() && right->isleafnode());
3340  BTREE_ASSERT(parent->level == 1);
3341 
3342  BTREE_ASSERT(left->nextleaf == right);
3343  BTREE_ASSERT(left == right->prevleaf);
3344 
3345  BTREE_ASSERT(left->slotuse < right->slotuse);
3346  BTREE_ASSERT(parent->childid[parentslot] == left);
3347 
3348  unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1;
3349 
3350  BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << ".");
3351 
3352  BTREE_ASSERT(left->slotuse + shiftnum < leafslotmax);
3353 
3354  // copy the first items from the right node to the last slot in the left node.
3355 
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);
3360 
3361  left->slotuse += shiftnum;
3362 
3363  // shift all slots in the right node to the left
3364 
3365  std::copy(right->slotkey + shiftnum, right->slotkey + right->slotuse,
3366  right->slotkey);
3367  data_copy(right->slotdata + shiftnum, right->slotdata + right->slotuse,
3368  right->slotdata);
3369 
3370  right->slotuse -= shiftnum;
3371 
3372  // fixup parent
3373  if (parentslot < parent->slotuse) {
3374  parent->slotkey[parentslot] = left->slotkey[left->slotuse - 1];
3375  return btree_ok;
3376  }
3377  else { // the update is further up the tree
3378  return result_t(btree_update_lastkey, left->slotkey[left->slotuse - 1]);
3379  }
3380  }
3381 
3382  /// Balance two inner nodes. The function moves key/data pairs from right
3383  /// to left so that both nodes are equally filled. The parent node is
3384  /// updated if possible.
3385  static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
3386  {
3387  BTREE_ASSERT(left->level == right->level);
3388  BTREE_ASSERT(parent->level == left->level + 1);
3389 
3390  BTREE_ASSERT(left->slotuse < right->slotuse);
3391  BTREE_ASSERT(parent->childid[parentslot] == left);
3392 
3393  unsigned int shiftnum = (right->slotuse - left->slotuse) >> 1;
3394 
3395  BTREE_PRINT("Shifting (inner) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << ".");
3396 
3397  BTREE_ASSERT(left->slotuse + shiftnum < innerslotmax);
3398 
3399  if (selfverify)
3400  {
3401  // find the left node's slot in the parent's children and compare to parentslot
3402 
3403  unsigned int leftslot = 0;
3404  while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3405  ++leftslot;
3406 
3407  BTREE_ASSERT(leftslot < parent->slotuse);
3408  BTREE_ASSERT(parent->childid[leftslot] == left);
3409  BTREE_ASSERT(parent->childid[leftslot+1] == right);
3410 
3411  BTREE_ASSERT(leftslot == parentslot);
3412  }
3413 
3414  // copy the parent's decision slotkey and childid to the first new key on the left
3415  left->slotkey[left->slotuse] = parent->slotkey[parentslot];
3416  left->slotuse++;
3417 
3418  // copy the other items from the right node to the last slots in the left node.
3419 
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);
3424 
3425  left->slotuse += shiftnum - 1;
3426 
3427  // fixup parent
3428  parent->slotkey[parentslot] = right->slotkey[shiftnum - 1];
3429 
3430  // shift all slots in the right node
3431 
3432  std::copy(right->slotkey + shiftnum, right->slotkey + right->slotuse,
3433  right->slotkey);
3434  std::copy(right->childid + shiftnum, right->childid + right->slotuse+1,
3435  right->childid);
3436 
3437  right->slotuse -= shiftnum;
3438  }
3439 
3440  /// Balance two leaf nodes. The function moves key/data pairs from left to
3441  /// right so that both nodes are equally filled. The parent node is updated
3442  /// if possible.
3443  static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
3444  {
3445  BTREE_ASSERT(left->isleafnode() && right->isleafnode());
3446  BTREE_ASSERT(parent->level == 1);
3447 
3448  BTREE_ASSERT(left->nextleaf == right);
3449  BTREE_ASSERT(left == right->prevleaf);
3450  BTREE_ASSERT(parent->childid[parentslot] == left);
3451 
3452  BTREE_ASSERT(left->slotuse > right->slotuse);
3453 
3454  unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1;
3455 
3456  BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << ".");
3457 
3458  if (selfverify)
3459  {
3460  // find the left node's slot in the parent's children
3461  unsigned int leftslot = 0;
3462  while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3463  ++leftslot;
3464 
3465  BTREE_ASSERT(leftslot < parent->slotuse);
3466  BTREE_ASSERT(parent->childid[leftslot] == left);
3467  BTREE_ASSERT(parent->childid[leftslot+1] == right);
3468 
3469  BTREE_ASSERT(leftslot == parentslot);
3470  }
3471 
3472  // shift all slots in the right node
3473 
3474  BTREE_ASSERT(right->slotuse + shiftnum < leafslotmax);
3475 
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);
3480 
3481  right->slotuse += shiftnum;
3482 
3483  // copy the last items from the left node to the first slot in the right node.
3484  std::copy(left->slotkey + left->slotuse - shiftnum, left->slotkey + left->slotuse,
3485  right->slotkey);
3486  data_copy(left->slotdata + left->slotuse - shiftnum, left->slotdata + left->slotuse,
3487  right->slotdata);
3488 
3489  left->slotuse -= shiftnum;
3490 
3491  parent->slotkey[parentslot] = left->slotkey[left->slotuse-1];
3492  }
3493 
3494  /// Balance two inner nodes. The function moves key/data pairs from left to
3495  /// right so that both nodes are equally filled. The parent node is updated
3496  /// if possible.
3497  static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
3498  {
3499  BTREE_ASSERT(left->level == right->level);
3500  BTREE_ASSERT(parent->level == left->level + 1);
3501 
3502  BTREE_ASSERT(left->slotuse > right->slotuse);
3503  BTREE_ASSERT(parent->childid[parentslot] == left);
3504 
3505  unsigned int shiftnum = (left->slotuse - right->slotuse) >> 1;
3506 
3507  BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << ".");
3508 
3509  if (selfverify)
3510  {
3511  // find the left node's slot in the parent's children
3512  unsigned int leftslot = 0;
3513  while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
3514  ++leftslot;
3515 
3516  BTREE_ASSERT(leftslot < parent->slotuse);
3517  BTREE_ASSERT(parent->childid[leftslot] == left);
3518  BTREE_ASSERT(parent->childid[leftslot+1] == right);
3519 
3520  BTREE_ASSERT(leftslot == parentslot);
3521  }
3522 
3523  // shift all slots in the right node
3524 
3525  BTREE_ASSERT(right->slotuse + shiftnum < innerslotmax);
3526 
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);
3531 
3532  right->slotuse += shiftnum;
3533 
3534  // copy the parent's decision slotkey and childid to the last new key on the right
3535  right->slotkey[shiftnum - 1] = parent->slotkey[parentslot];
3536 
3537  // copy the remaining last items from the left node to the first slot in the right node.
3538  std::copy(left->slotkey + left->slotuse - shiftnum+1, left->slotkey + left->slotuse,
3539  right->slotkey);
3540  std::copy(left->childid + left->slotuse - shiftnum+1, left->childid + left->slotuse+1,
3541  right->childid);
3542 
3543  // copy the first to-be-removed key from the left node to the parent's decision slot
3544  parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum];
3545 
3546  left->slotuse -= shiftnum;
3547  }
3548 
3549 #ifdef BTREE_DEBUG
3550 public:
3551  // *** Debug Printing
3552 
3553  /// Print out the B+ tree structure with keys onto the given ostream. This
3554  /// function requires that the header is compiled with BTREE_DEBUG and that
3555  /// key_type is printable via std::ostream.
3556  void print(std::ostream &os) const
3557  {
3558  if (m_root) {
3559  print_node(os, m_root, 0, true);
3560  }
3561  }
3562 
3563  /// Print out only the leaves via the double linked list.
3564  void print_leaves(std::ostream &os) const
3565  {
3566  os << "leaves:" << std::endl;
3567 
3568  const leaf_node *n = m_headleaf;
3569 
3570  while(n)
3571  {
3572  os << " " << n << std::endl;
3573 
3574  n = n->nextleaf;
3575  }
3576  }
3577 
3578 private:
3579 
3580  /// Recursively descend down the tree and print out nodes.
3581  static void print_node(std::ostream &os, const node* node, unsigned int depth=0, bool recursive=false)
3582  {
3583  for(unsigned int i = 0; i < depth; i++) os << " ";
3584 
3585  os << "node " << node << " level " << node->level << " slotuse " << node->slotuse << std::endl;
3586 
3587  if (node->isleafnode())
3588  {
3589  const leaf_node *leafnode = static_cast<const leaf_node*>(node);
3590 
3591  for(unsigned int i = 0; i < depth; i++) os << " ";
3592  os << " leaf prev " << leafnode->prevleaf << " next " << leafnode->nextleaf << std::endl;
3593 
3594  for(unsigned int i = 0; i < depth; i++) os << " ";
3595 
3596  for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
3597  {
3598  os << leafnode->slotkey[slot] << " "; // << "(data: " << leafnode->slotdata[slot] << ") ";
3599  }
3600  os << std::endl;
3601  }
3602  else
3603  {
3604  const inner_node *innernode = static_cast<const inner_node*>(node);
3605 
3606  for(unsigned int i = 0; i < depth; i++) os << " ";
3607 
3608  for (unsigned short slot = 0; slot < innernode->slotuse; ++slot)
3609  {
3610  os << "(" << innernode->childid[slot] << ") " << innernode->slotkey[slot] << " ";
3611  }
3612  os << "(" << innernode->childid[innernode->slotuse] << ")" << std::endl;
3613 
3614  if (recursive)
3615  {
3616  for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
3617  {
3618  print_node(os, innernode->childid[slot], depth + 1, recursive);
3619  }
3620  }
3621  }
3622  }
3623 #endif
3624 
3625 public:
3626  // *** Verification of B+ Tree Invariants
3627 
3628  /// Run a thorough verification of all B+ tree invariants. The program
3629  /// aborts via assert() if something is wrong.
3630  void verify() const
3631  {
3632  key_type minkey, maxkey;
3633  tree_stats vstats;
3634 
3635  if (m_root)
3636  {
3637  verify_node(m_root, &minkey, &maxkey, vstats);
3638 
3639  assert( vstats.itemcount == m_stats.itemcount );
3640  assert( vstats.leaves == m_stats.leaves );
3641  assert( vstats.innernodes == m_stats.innernodes );
3642 
3643  verify_leaflinks();
3644  }
3645  }
3646 
3647 private:
3648 
3649  /// Recursively descend down the tree and verify each node
3650  void verify_node(const node* n, key_type* minkey, key_type* maxkey, tree_stats &vstats) const
3651  {
3652  BTREE_PRINT("verifynode " << n);
3653 
3654  if (n->isleafnode())
3655  {
3656  const leaf_node *leaf = static_cast<const leaf_node*>(n);
3657 
3658  assert( leaf == m_root || !leaf->isunderflow() );
3659  assert( leaf->slotuse > 0 );
3660 
3661  for(unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot)
3662  {
3663  assert(key_lessequal(leaf->slotkey[slot], leaf->slotkey[slot + 1]));
3664  }
3665 
3666  *minkey = leaf->slotkey[0];
3667  *maxkey = leaf->slotkey[leaf->slotuse - 1];
3668 
3669  vstats.leaves++;
3670  vstats.itemcount += leaf->slotuse;
3671  }
3672  else // !n->isleafnode()
3673  {
3674  const inner_node *inner = static_cast<const inner_node*>(n);
3675  vstats.innernodes++;
3676 
3677  assert( inner == m_root || !inner->isunderflow() );
3678  assert( inner->slotuse > 0 );
3679 
3680  for(unsigned short slot = 0; slot < inner->slotuse - 1; ++slot)
3681  {
3682  assert(key_lessequal(inner->slotkey[slot], inner->slotkey[slot + 1]));
3683  }
3684 
3685  for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
3686  {
3687  const node *subnode = inner->childid[slot];
3688  key_type subminkey = key_type();
3689  key_type submaxkey = key_type();
3690 
3691  assert(subnode->level + 1 == inner->level);
3692  verify_node(subnode, &subminkey, &submaxkey, vstats);
3693 
3694  BTREE_PRINT("verify subnode " << subnode << ": " << subminkey << " - " << submaxkey);
3695 
3696  if (slot == 0)
3697  *minkey = subminkey;
3698  else
3699  assert(key_greaterequal(subminkey, inner->slotkey[slot-1]));
3700 
3701  if (slot == inner->slotuse)
3702  *maxkey = submaxkey;
3703  else
3704  assert(key_equal(inner->slotkey[slot], submaxkey));
3705 
3706  if (inner->level == 1 && slot < inner->slotuse)
3707  {
3708  // children are leaves and must be linked together in the
3709  // correct order
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]);
3712 
3713  assert(leafa->nextleaf == leafb);
3714  assert(leafa == leafb->prevleaf);
3715  (void)leafa; (void)leafb;
3716  }
3717  if (inner->level == 2 && slot < inner->slotuse)
3718  {
3719  // verify leaf links between the adjacent inner nodes
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]);
3722 
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]);
3725 
3726  assert(leafa->nextleaf == leafb);
3727  assert(leafa == leafb->prevleaf);
3728  (void)leafa; (void)leafb;
3729  }
3730  }
3731  }
3732  }
3733 
3734  /// Verify the double linked list of leaves.
3735  void verify_leaflinks() const
3736  {
3737  const leaf_node *n = m_headleaf;
3738 
3739  assert(n->level == 0);
3740  assert(!n || n->prevleaf == NULL);
3741 
3742  unsigned int testcount = 0;
3743 
3744  while(n)
3745  {
3746  assert(n->level == 0);
3747  assert(n->slotuse > 0);
3748 
3749  for(unsigned short slot = 0; slot < n->slotuse - 1; ++slot)
3750  {
3751  assert(key_lessequal(n->slotkey[slot], n->slotkey[slot + 1]));
3752  }
3753 
3754  testcount += n->slotuse;
3755 
3756  if (n->nextleaf)
3757  {
3758  assert(key_lessequal(n->slotkey[n->slotuse-1], n->nextleaf->slotkey[0]));
3759 
3760  assert(n == n->nextleaf->prevleaf);
3761  }
3762  else
3763  {
3764  assert(m_tailleaf == n);
3765  }
3766 
3767  n = n->nextleaf;
3768  }
3769 
3770  assert(testcount == size());
3771  }
3772 
3773 private:
3774  // *** Dump and Restore of B+ Trees
3775 
3776  /// A header for the binary image containing the base properties of the B+
3777  /// tree. These properties have to match the current template
3778  /// instantiation.
3780  {
3781  /// "stx-btree", just to stop the restore() function from loading garbage
3782  char signature[12];
3783 
3784  /// Currently 0
3785  unsigned short version;
3786 
3787  /// sizeof(key_type)
3788  unsigned short key_type_size;
3789 
3790  /// sizeof(data_type)
3791  unsigned short data_type_size;
3792 
3793  /// Number of slots in the leaves
3794  unsigned short leafslots;
3795 
3796  /// Number of slots in the inner nodes
3797  unsigned short innerslots;
3798 
3799  /// Allow duplicates
3801 
3802  /// The item count of the tree
3803  size_type itemcount;
3804 
3805  /// Fill the struct with the current B+ tree's properties, itemcount is
3806  /// not filled.
3807  inline void fill()
3808  {
3809  // don't want to include string.h just for this signature
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;
3813 
3814  version = 0;
3815  key_type_size = sizeof(typename btree_self::key_type);
3816  data_type_size = sizeof(typename btree_self::data_type);
3817  leafslots = btree_self::leafslotmax;
3818  innerslots = btree_self::innerslotmax;
3819  allow_duplicates = btree_self::allow_duplicates;
3820  }
3821 
3822  /// Returns true if the headers have the same vital properties
3823  inline bool same(const struct dump_header &o) const
3824  {
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)
3828  && (version == o.version)
3829  && (key_type_size == o.key_type_size)
3830  && (data_type_size == o.data_type_size)
3831  && (leafslots == o.leafslots)
3832  && (innerslots == o.innerslots)
3833  && (allow_duplicates == o.allow_duplicates);
3834  }
3835  };
3836 
3837 public:
3838 
3839  /// Dump the contents of the B+ tree out onto an ostream as a binary
3840  /// image. The image contains memory pointers which will be fixed when the
3841  /// image is restored. For this to work your key_type and data_type must be
3842  /// integral types and contain no pointers or references.
3843  void dump(std::ostream &os) const
3844  {
3845  struct dump_header header;
3846  header.fill();
3847  header.itemcount = size();
3848 
3849  os.write(reinterpret_cast<char*>(&header), sizeof(header));
3850 
3851  if (m_root) {
3852  dump_node(os, m_root);
3853  }
3854  }
3855 
3856  /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
3857  /// pointers are fixed using the dump order. For dump and restore to work
3858  /// your key_type and data_type must be integral types and contain no
3859  /// pointers or references. Returns true if the restore was successful.
3860  bool restore(std::istream &is)
3861  {
3862  struct dump_header fileheader;
3863  is.read(reinterpret_cast<char*>(&fileheader), sizeof(fileheader));
3864  if (!is.good()) return false;
3865 
3866  struct dump_header myheader;
3867  myheader.fill();
3868  myheader.itemcount = fileheader.itemcount;
3869 
3870  if (!myheader.same(fileheader))
3871  {
3872  BTREE_PRINT("btree::restore: file header does not match instantiation signature.");
3873  return false;
3874  }
3875 
3876  clear();
3877 
3878  if (fileheader.itemcount > 0)
3879  {
3880  m_root = restore_node(is);
3881  if (m_root == NULL) return false;
3882 
3883  m_stats.itemcount = fileheader.itemcount;
3884  }
3885 
3886 #ifdef BTREE_DEBUG
3887  if (debug) print(std::cout);
3888 #endif
3889  if (selfverify) verify();
3890 
3891  return true;
3892  }
3893 
3894 private:
3895 
3896  /// Recursively descend down the tree and dump each node in a precise order
3897  void dump_node(std::ostream &os, const node* n) const
3898  {
3899  BTREE_PRINT("dump_node " << n << std::endl);
3900 
3901  if (n->isleafnode())
3902  {
3903  const leaf_node *leaf = static_cast<const leaf_node*>(n);
3904 
3905  os.write(reinterpret_cast<const char*>(leaf), sizeof(*leaf));
3906  }
3907  else // !n->isleafnode()
3908  {
3909  const inner_node *inner = static_cast<const inner_node*>(n);
3910 
3911  os.write(reinterpret_cast<const char*>(inner), sizeof(*inner));
3912 
3913  for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
3914  {
3915  const node *subnode = inner->childid[slot];
3916 
3917  dump_node(os, subnode);
3918  }
3919  }
3920  }
3921 
3922  /// Read the dump image and construct a tree from the node order in the
3923  /// serialization.
3924  node* restore_node(std::istream &is)
3925  {
3926  union {
3927  node top;
3928  leaf_node leaf;
3929  inner_node inner;
3930  } nu;
3931 
3932  // first read only the top of the node
3933  is.read(reinterpret_cast<char*>(&nu.top), sizeof(nu.top));
3934  if (!is.good()) return NULL;
3935 
3936  if (nu.top.isleafnode())
3937  {
3938  // read remaining data of leaf node
3939  is.read(reinterpret_cast<char*>(&nu.leaf) + sizeof(nu.top), sizeof(nu.leaf) - sizeof(nu.top));
3940  if (!is.good()) return NULL;
3941 
3942  leaf_node *newleaf = allocate_leaf();
3943 
3944  // copy over all data, the leaf nodes contain only their double linked list pointers
3945  *newleaf = nu.leaf;
3946 
3947  // reconstruct the linked list from the order in the file
3948  if (m_headleaf == NULL) {
3949  BTREE_ASSERT(newleaf->prevleaf == NULL);
3950  m_headleaf = m_tailleaf = newleaf;
3951  }
3952  else {
3953  newleaf->prevleaf = m_tailleaf;
3954  m_tailleaf->nextleaf = newleaf;
3955  m_tailleaf = newleaf;
3956  }
3957 
3958  return newleaf;
3959  }
3960  else
3961  {
3962  // read remaining data of inner node
3963  is.read(reinterpret_cast<char*>(&nu.inner) + sizeof(nu.top), sizeof(nu.inner) - sizeof(nu.top));
3964  if (!is.good()) return NULL;
3965 
3966  inner_node *newinner = allocate_inner(0);
3967 
3968  // copy over all data, the inner nodes contain only pointers to their children
3969  *newinner = nu.inner;
3970 
3971  for(unsigned short slot = 0; slot <= newinner->slotuse; ++slot)
3972  {
3973  newinner->childid[slot] = restore_node(is);
3974  }
3975 
3976  return newinner;
3977  }
3978  }
3979 };
3980 
3981 } // namespace stx
3982 
3983 #endif // _STX_BTREE_H_
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition: btree.h:1063
self operator--(int)
Postfix– backstep the iterator to the last slot.
Definition: btree.h:598
For sets the second pair_type is an empty struct, so the value_type should only be the first...
Definition: btree.h:387
btree::value_type value_type
The value type of the btree. Returned by operator*().
Definition: btree.h:1051
struct node * copy_recursive(const node *n)
Recursively copy nodes from another B+ tree object.
Definition: btree.h:2040
unsigned short currslot
Current key/data slot referenced.
Definition: btree.h:671
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
Definition: btree.h:1573
static OutputIterator data_copy(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
Definition: btree.h:1506
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
Definition: btree.h:1615
btree::value_type value_type
The value type of the btree. Returned by operator*().
Definition: btree.h:644
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
Definition: btree.h:3843
bool isunderflow() const
True if node has too few entries.
Definition: btree.h:310
leaf_node::alloc_type leaf_node_allocator()
Return an allocator for leaf_node objects.
Definition: btree.h:1454
btree::data_type data_type
The data type of the btree. Returned by data().
Definition: btree.h:641
self & operator--()
Prefix– backstep the iterator to the last slot.
Definition: btree.h:783
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
Definition: btree.h:1423
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.
Definition: btree.h:2144
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...
Definition: btree.h:1920
node * restore_node(std::istream &is)
Read the dump image and construct a tree from the node order in the serialization.
Definition: btree.h:3924
data_type & data() const
Writable reference to the current data object.
Definition: btree.h:942
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree.h:1580
const_iterator()
Default-Constructor of a const iterator.
Definition: btree.h:690
bool isfew() const
True if few used entries, less than half full.
Definition: btree.h:304
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...
Definition: btree.h:1898
B+ tree recursive deletion has much information which is needs to be passed upward.
Definition: btree.h:2553
leaf_node * m_tailleaf
Pointer to last leaf in the double linked leaf chain.
Definition: btree.h:1296
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.h:1757
pointer operator->() const
Dereference the iterator.
Definition: btree.h:726
#define BTREE_MAX(a, b)
The maximum of a and b. Used in some compile-time formulas.
Definition: btree.h:71
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.h:1747
leaf_node * m_headleaf
Pointer to first leaf in the double linked leaf chain.
Definition: btree.h:1293
bool operator>(const btree_self &other) const
Greater relation. Based on operator<.
Definition: btree.h:1976
Basic class implementing a base B+ tree data structure in memory.
Definition: btree.h:163
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...
Definition: btree.h:110
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.h:1734
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...
Definition: btree.h:2563
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
Definition: btree.h:1594
STL-like read-only reverse iterator object for B+ tree items.
Definition: btree.h:1039
result_flags_t flags
Merged result flags.
Definition: btree.h:2556
const value_type & reference
Reference to the value_type. STL required.
Definition: btree.h:1057
btree(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
Definition: btree.h:1313
_Key key_type
First template parameter: The key type of the B+ tree.
Definition: btree.h:170
STL-like iterator object for B+ tree items.
Definition: btree.h:427
const_reverse_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
Definition: btree.h:1117
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.
Definition: btree.h:3581
Extended structure of a leaf node in memory.
Definition: btree.h:319
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree.h:3860
bool operator!=(const self &x) const
Inequality of iterators.
Definition: btree.h:624
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
Definition: btree.h:1112
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
Definition: btree.h:1097
static result_t merge_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Merge two inner nodes.
Definition: btree.h:3293
btree::key_type key_type
The key type of the btree. Returned by key().
Definition: btree.h:1045
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.h:2619
#define BTREE_PRINT(x)
Print out debug information to std::cout if BTREE_DEBUG is defined.
Definition: btree.h:55
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition: btree.h:2596
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...
Definition: btree.h:1342
unsigned short currslot
One slot past the current key/data slot referenced.
Definition: btree.h:1078
const key_type & key() const
Key of the current slot.
Definition: btree.h:733
bool isleafnode() const
True if this is a leaf node.
Definition: btree.h:272
reverse_iterator()
Default-Constructor of a reverse iterator.
Definition: btree.h:901
bool allow_duplicates
Allow duplicates.
Definition: btree.h:3800
void free_node(node *n)
Correctly free either inner or leaf node, destructs all contained key and value objects.
Definition: btree.h:1485
bool operator>=(const btree_self &other) const
Greater-equal relation. Based on operator<.
Definition: btree.h:1988
reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
Definition: btree.h:911
STX - Some Template Extensions namespace.
Definition: btree.h:81
Function class to compare value_type objects. Required by the STL.
Definition: btree.h:1371
data_type & data() const
Writable reference to the current data object.
Definition: btree.h:536
size_type innernodes
Number of inner nodes in the B+ tree.
Definition: btree.h:1258
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
Definition: btree.h:917
STL-like mutable reverse iterator object for B+ tree items.
Definition: btree.h:835
reference operator*() const
Dereference the iterator.
Definition: btree.h:1124
bool key_less(const key_type &a, const key_type b) const
True if a < b ? "constructed" from m_key_less()
Definition: btree.h:1411
int find_upper(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater than key.
Definition: btree.h:1682
key_type slotkey[leafslotmax]
Keys of children or data pointers.
Definition: btree.h:331
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
Definition: btree.h:2655
std::pair< key_type, data_type > pair_type
The pair of key_type and data_type, this may be different from value_type.
Definition: btree.h:219
_Data data_type
Second template parameter: The data type associated with each key.
Definition: btree.h:174
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.
Definition: btree.h:1635
reference operator*() const
Dereference the iterator.
Definition: btree.h:717
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.
Definition: btree.h:2190
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree.h:1940
btree_pair_to_value< value_type, pair_type > pair_to_value_type
Using template specialization select the correct converter used by the iterators. ...
Definition: btree.h:415
result_t merge_leaves(leaf_node *left, leaf_node *right, inner_node *parent)
Merge two leaf nodes.
Definition: btree.h:3262
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...
Definition: btree.h:1877
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
Definition: btree.h:487
unsigned short innerslots
Number of slots in the inner nodes.
Definition: btree.h:3797
bool operator!=(const btree_self &other) const
Inequality relation. Based on operator==.
Definition: btree.h:1963
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...
Definition: btree.h:1822
void set_slot(unsigned short slot, const key_type &key)
Set the key pair in slot.
Definition: btree.h:373
ptrdiff_t difference_type
STL-magic.
Definition: btree.h:454
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition: btree.h:451
key_type lastkey
The key to be updated at the parent&#39;s slot.
Definition: btree.h:2559
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
Definition: btree.h:705
bool operator!=(const self &x) const
Inequality of iterators.
Definition: btree.h:827
self & operator++()
Prefix++ advance the iterator to the next slot.
Definition: btree.h:949
reference operator*() const
Dereference the iterator, this is not a value_type& because key and value are not stored together...
Definition: btree.h:514
A header for the binary image containing the base properties of the B+ tree.
Definition: btree.h:3779
leaf_node * prevleaf
Double linked list pointers to traverse the leaves.
Definition: btree.h:325
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...
Definition: btree.h:1622
void initialize()
Set variables to initial values.
Definition: btree.h:337
static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
Definition: btree.h:3497
result_t(result_flags_t f, const key_type &k)
Constructor with a lastkey value.
Definition: btree.h:2568
static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
Balance two inner nodes.
Definition: btree.h:3385
bool isunderflow() const
True if node has too few entries.
Definition: btree.h:356
key_compare m_key_less
Key comparison object.
Definition: btree.h:1303
bool operator==(const self &x) const
Equality of iterators.
Definition: btree.h:618
_Alloc::template rebind< leaf_node >::other alloc_type
Define an related allocator for the leaf_node structs.
Definition: btree.h:322
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.h:2401
unsigned short currslot
Current key/data slot referenced.
Definition: btree.h:466
std::pair< iterator, bool > insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2097
bool operator==(const self &x) const
Equality of iterators.
Definition: btree.h:1025
Extended structure of a inner node in-memory.
Definition: btree.h:280
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.h:1527
reverse_iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable reverse iterator.
Definition: btree.h:906
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
Definition: btree.h:77
btree(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last).
Definition: btree.h:1331
Generates default traits for a B+ tree used as a map.
Definition: btree.h:116
leaf_node * nextleaf
Double linked list pointers to traverse the leaves.
Definition: btree.h:328
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.h:1741
ptrdiff_t difference_type
STL-magic.
Definition: btree.h:659
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
Definition: btree.h:1086
ptrdiff_t difference_type
STL-magic.
Definition: btree.h:862
bool operator==(const self &x) const
Equality of iterators.
Definition: btree.h:821
allocator_type m_allocator
Memory allocator.
Definition: btree.h:1306
static OutputIterator data_copy_backward(InputIterator first, InputIterator last, OutputIterator result)
Convenient template function for conditional copying of slotdata.
Definition: btree.h:1516
void verify_leaflinks() const
Verify the double linked list of leaves.
Definition: btree.h:3735
void dump_node(std::ostream &os, const node *n) const
Recursively descend down the tree and dump each node in a precise order.
Definition: btree.h:3897
unsigned short version
Currently 0.
Definition: btree.h:3785
btree::key_type key_type
The key type of the btree. Returned by key().
Definition: btree.h:433
bool has(result_flags_t f) const
Test if this result object has a given flag set.
Definition: btree.h:2573
iterator(typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a mutable iterator.
Definition: btree.h:503
tree_stats m_stats
Other small statistics about the B+ tree.
Definition: btree.h:1299
btree::value_type value_type
The value type of the btree. Returned by operator*().
Definition: btree.h:439
bool operator==(const self &x) const
Equality of iterators.
Definition: btree.h:1232
unsigned short leafslots
Number of slots in the leaves.
Definition: btree.h:3794
value_compare(key_compare kc)
Constructor called from btree::value_comp()
Definition: btree.h:1378
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().
Definition: btree.h:1946
std::pair< iterator, bool > insert(const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2088
_Value value_type
Third template parameter: Composition pair of key and data types, this is required by the STL standar...
Definition: btree.h:180
bool operator()(const value_type &x, const value_type &y) const
Function call "less"-operator resulting in true if x < y.
Definition: btree.h:1388
bool operator<(const btree_self &other) const
Total ordering relation of B+ trees of the same type.
Definition: btree.h:1970
size_t size_type
Size type used to count keys.
Definition: btree.h:216
ptrdiff_t difference_type
STL-magic.
Definition: btree.h:1066
The header structure of each node in-memory.
Definition: btree.h:255
btree::pair_type pair_type
The pair type of the btree.
Definition: btree.h:850
btree(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
Definition: btree.h:1320
self operator--(int)
Postfix– backstep the iterator to the next slot.
Definition: btree.h:1212
Generates default traits for a B+ tree used as a set.
Definition: btree.h:86
size_type itemcount
The item count of the tree.
Definition: btree.h:3803
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.h:1395
const_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const iterator.
Definition: btree.h:695
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition: btree.h:859
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree.h:1402
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
Definition: btree.h:700
key_compare key_comp
Key comparison function from the template parameter.
Definition: btree.h:1375
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition: btree.h:656
iterator insert2(iterator, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2120
iterator(const reverse_iterator &it)
Copy-constructor from a reverse iterator.
Definition: btree.h:508
self operator++(int)
Postfix++ advance the iterator to the next slot.
Definition: btree.h:763
iterator insert(iterator, const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2113
bool operator!=(const self &x) const
Inequality of iterators.
Definition: btree.h:1031
_Compare key_compare
Fourth template parameter: Key comparison function object.
Definition: btree.h:183
btree::data_type data_type
The data type of the btree. Returned by data().
Definition: btree.h:436
bool isfew() const
True if few used entries, less than half full.
Definition: btree.h:350
bool isfull() const
True if the node&#39;s slots are full.
Definition: btree.h:298
const_reverse_iterator(const typename btree::leaf_node *l, unsigned short s)
Initializing-Constructor of a const reverse iterator.
Definition: btree.h:1102
inner_node * allocate_inner(unsigned short level)
Allocate and initialize an inner node.
Definition: btree.h:1475
void fill()
Fill the struct with the current B+ tree&#39;s properties, itemcount is not filled.
Definition: btree.h:3807
#define BTREE_ASSERT(x)
Assertion only if BTREE_DEBUG is defined. This is not used in verify().
Definition: btree.h:58
leaf_node * allocate_leaf()
Allocate and initialize a leaf node.
Definition: btree.h:1466
self & operator++()
Prefix++ advance the iterator to the next slot.
Definition: btree.h:745
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
Definition: btree.h:668
const value_type * pointer
Pointer to the value_type. STL required.
Definition: btree.h:653
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
Definition: btree.h:3556
static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
Definition: btree.h:3443
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
Definition: btree.h:679
const key_type & key() const
Key of the current slot.
Definition: btree.h:935
unsigned short key_type_size
sizeof(key_type)
Definition: btree.h:3788
btree::key_type key_type
The key type of the btree. Returned by key().
Definition: btree.h:841
size_type nodes() const
Return the total number of nodes.
Definition: btree.h:1274
value_type temp_value
Evil! A temporary value_type to STL-correctly deliver operator* and operator->
Definition: btree.h:890
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
Definition: btree.h:2129
btree(const btree_self &other)
Copy constructor.
Definition: btree.h:2022
const key_type & key() const
Key of the current slot.
Definition: btree.h:530
size_type leaves
Number of leaves in the B+ tree.
Definition: btree.h:1255
unsigned short level
Level in the b-tree, if level == 0 -> leaf node.
Definition: btree.h:258
self & operator++()
Prefix++ advance the iterator to the previous slot.
Definition: btree.h:1156
value_type * pointer
Pointer to the value_type. STL required.
Definition: btree.h:856
value_type & reference
Reference to the value_type. STL required.
Definition: btree.h:853
btree::pair_type pair_type
The pair type of the btree.
Definition: btree.h:647
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
Definition: btree.h:1587
void set_slot(unsigned short slot, const pair_type &value)
Set the (key,data) pair in slot.
Definition: btree.h:363
double avgfill_leaves() const
Return the average fill of leaves.
Definition: btree.h:1280
const value_type * pointer
Pointer to the value_type. STL required.
Definition: btree.h:1060
const_reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
Definition: btree.h:1107
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...
Definition: btree.h:1800
static const bool selfverify
If true, the tree will self verify it&#39;s invariants after each insert() or erase().
Definition: btree.h:90
const btree::leaf_node * currnode
The currently referenced leaf node of the tree.
Definition: btree.h:1075
const value_type & reference
Reference to the value_type. STL required.
Definition: btree.h:650
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...
Definition: btree.h:1778
bool key_greaterequal(const key_type &a, const key_type b) const
True if a >= b ? constructed from key_less()
Definition: btree.h:1429
self & operator--()
Prefix– backstep the iterator to the last slot.
Definition: btree.h:987
value_type & reference
Reference to the value_type. STL required.
Definition: btree.h:445
btree::data_type data_type
The data type of the btree. Returned by data().
Definition: btree.h:1048
void initialize(const unsigned short l)
Set variables to initial values.
Definition: btree.h:292
btree::pair_type pair_type
The pair type of the btree.
Definition: btree.h:1054
const data_type & data() const
Read-only reference to the current data object.
Definition: btree.h:739
unsigned short data_type_size
sizeof(data_type)
Definition: btree.h:3791
unsigned short currslot
One slot past the current key/data slot referenced.
Definition: btree.h:874
self operator++(int)
Postfix++ advance the iterator to the next slot.
Definition: btree.h:967
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
Definition: btree.h:3564
btree::leaf_node * currnode
The currently referenced leaf node of the tree.
Definition: btree.h:871
const_iterator(const const_reverse_iterator &it)
Copy-constructor from a const reverse iterator.
Definition: btree.h:710
btree::data_type data_type
The data type of the btree. Returned by data().
Definition: btree.h:844
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.h:1728
btree::value_type value_type
The value type of the btree. Returned by operator*().
Definition: btree.h:847
bool operator==(const btree_self &other) const
Equality relation of B+ trees of the same type.
Definition: btree.h:1957
btree::leaf_node * currnode
The currently referenced leaf node of the tree.
Definition: btree.h:463
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.
Definition: btree.h:2362
_Traits traits
Fifth template parameter: Traits object used to define more parameters of the B+ tree.
Definition: btree.h:187
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree.h:1601
A small struct containing basic statistics about the B+ tree.
Definition: btree.h:1249
value_type operator()(const pair_type &p) const
Convert a fake pair type to just the first component.
Definition: btree.h:394
btree::pair_type pair_type
The pair type of the btree.
Definition: btree.h:442
bool operator<=(const btree_self &other) const
Less-equal relation. Based on operator<.
Definition: btree.h:1982
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.
Definition: btree.h:3650
btree::key_type key_type
The key type of the btree. Returned by key().
Definition: btree.h:638
bool key_lessequal(const key_type &a, const key_type b) const
True if a <= b ? constructed from key_less()
Definition: btree.h:1417
bool isfull() const
True if the node&#39;s slots are full.
Definition: btree.h:344
~btree()
Frees up all used B+ tree memory pages.
Definition: btree.h:1351
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.h:3630
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2106
self operator++(int)
Postfix++ advance the iterator to the previous slot.
Definition: btree.h:1174
_Alloc allocator_type
Seventh template parameter: STL allocator for tree nodes.
Definition: btree.h:194
tree_stats()
Zero initialized.
Definition: btree.h:1267
self & operator--()
Prefix– backstep the iterator to the last slot.
Definition: btree.h:580
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.h:1445
btree< key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set > btree_self
Typedef of our own type.
Definition: btree.h:213
pointer operator->() const
Dereference the iterator.
Definition: btree.h:523
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ? constructed from key_less().
Definition: btree.h:1436
static const int innerslots
Number of slots in each inner node of the tree.
Definition: btree.h:104
inner_node::alloc_type inner_node_allocator()
Return an allocator for inner_node objects.
Definition: btree.h:1460
const data_type & data() const
Read-only reference to the current data object.
Definition: btree.h:1149
value_type operator()(const pair_type &p) const
Identity "convert" a real pair type to just the first component.
Definition: btree.h:408
void swap(btree_self &from)
Fast swapping of two identical B+ tree objects.
Definition: btree.h:1357
value_type * pointer
Pointer to the value_type. STL required.
Definition: btree.h:448
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree.h:1608
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
Definition: btree.h:96
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.
Definition: btree.h:2673
data_type slotdata[used_as_set ? 1 :leafslotmax]
Array of data.
Definition: btree.h:334
void clear_recursive(node *n)
Recursively free up nodes.
Definition: btree.h:1545
void split_leaf_node(leaf_node *leaf, key_type *_newkey, node **_newleaf)
Split up a leaf node into two equally-filled sibling leaves.
Definition: btree.h:2324
node * m_root
Pointer to the B+ tree&#39;s root node, either leaf or inner node.
Definition: btree.h:1290
_Alloc::template rebind< inner_node >::other alloc_type
Define an related allocator for the inner_node structs.
Definition: btree.h:283
unsigned short slotuse
Number of key slotuse use, so number of valid children or data pointers.
Definition: btree.h:262
self & operator--()
Prefix– backstep the iterator to the next slot.
Definition: btree.h:1194
self & operator++()
Prefix++ advance the iterator to the next slot.
Definition: btree.h:542
iterator()
Default-Constructor of a mutable iterator.
Definition: btree.h:498
static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
Balance two leaf nodes.
Definition: btree.h:3337
void initialize(const unsigned short l)
Delayed initialisation of constructed node.
Definition: btree.h:265
self operator++(int)
Postfix++ advance the iterator to the next slot.
Definition: btree.h:560
pointer operator->() const
Dereference the iterator.
Definition: btree.h:927
self operator--(int)
Postfix– backstep the iterator to the last slot.
Definition: btree.h:1005
size_type itemcount
Number of items in the B+ tree.
Definition: btree.h:1252
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.
Definition: btree.h:2962
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
Definition: btree.h:2633
static const int leafslots
Number of slots in each leaf of the tree.
Definition: btree.h:100
STL-like read-only iterator object for B+ tree items.
Definition: btree.h:632
value_type operator()(pair_type &p) const
Convert a fake pair type to just the first component.
Definition: btree.h:390
bool operator!=(const self &x) const
Inequality of iterators.
Definition: btree.h:1238
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...
Definition: btree.h:1855
pointer operator->() const
Dereference the iterator.
Definition: btree.h:1134
bool same(const struct dump_header &o) const
Returns true if the headers have the same vital properties.
Definition: btree.h:3823
const key_type & key() const
Key of the current slot.
Definition: btree.h:1142
value_type operator()(pair_type &p) const
Identity "convert" a real pair type to just the first component.
Definition: btree.h:404
self operator--(int)
Postfix– backstep the iterator to the last slot.
Definition: btree.h:801