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