tlx
Loading...
Searching...
No Matches
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 <tb@panthema.net>
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
27namespace 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*/
73template <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 */
118template <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> >
124class BTree
125{
126public:
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
162public:
163 //! \name Constructed Types
164 //! \{
165
166 //! Typedef of our own type
169
170 //! Size type used to count keys
171 typedef size_t size_type;
172
173 //! \}
174
175public:
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
207private:
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 std::allocator_traits<Allocator>::template rebind_alloc<InnerNode> alloc_type;
238
239 //! Keys of children or data pointers
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) {
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 std::allocator_traits<Allocator>::template rebind_alloc<LeafNode> 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
285
286 //! Set variables to initial values
287 void initialize() {
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) {
316 slotdata[slot] = value;
317 }
318 };
319
320 //! \}
321
322public:
323 //! \name Iterators and Reverse Iterators
324 //! \{
325
326 class iterator;
327 class const_iterator;
328 class reverse_iterator;
329 class const_reverse_iterator;
330
331 //! STL-like iterator object for B+ tree items. The iterator points to a
332 //! specific slot number in a leaf.
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*().
343
344 //! Reference to the value_type. STL required.
346
347 //! Pointer to the value_type. STL required.
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.
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
406 { }
407
408 //! Dereference the iterator.
411 }
412
413 //! Dereference the iterator.
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.
425 if (curr_slot + 1u < curr_leaf->slotuse) {
426 ++curr_slot;
427 }
428 else if (curr_leaf->next_leaf != nullptr) {
430 curr_slot = 0;
431 }
432 else {
433 // this is end()
435 }
436
437 return *this;
438 }
439
440 //! Postfix++ advance the iterator to the next slot.
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) {
449 curr_slot = 0;
450 }
451 else {
452 // this is end()
454 }
455
456 return tmp;
457 }
458
459 //! Prefix-- backstep the iterator to the last slot.
461 if (curr_slot > 0) {
462 --curr_slot;
463 }
464 else if (curr_leaf->prev_leaf != nullptr) {
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.
478 iterator tmp = *this; // copy ourselves
479
480 if (curr_slot > 0) {
481 --curr_slot;
482 }
483 else if (curr_leaf->prev_leaf != nullptr) {
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*().
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
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
568 { }
569
570 //! Copy-constructor from a mutable reverse iterator
571 const_iterator(const reverse_iterator& it) // NOLINT
573 { }
574
575 //! Copy-constructor from a const reverse iterator
578 { }
579
580 //! Dereference the iterator.
583 }
584
585 //! Dereference the iterator.
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.
597 if (curr_slot + 1u < curr_leaf->slotuse) {
598 ++curr_slot;
599 }
600 else if (curr_leaf->next_leaf != nullptr) {
602 curr_slot = 0;
603 }
604 else {
605 // this is end()
607 }
608
609 return *this;
610 }
611
612 //! Postfix++ advance the iterator to the next slot.
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) {
621 curr_slot = 0;
622 }
623 else {
624 // this is end()
626 }
627
628 return tmp;
629 }
630
631 //! Prefix-- backstep the iterator to the last slot.
633 if (curr_slot > 0) {
634 --curr_slot;
635 }
636 else if (curr_leaf->prev_leaf != nullptr) {
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.
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) {
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*().
690
691 //! Reference to the value_type. STL required.
693
694 //! Pointer to the value_type. STL required.
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
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
748 { }
749
750 //! Dereference the iterator.
753 return curr_leaf->slotdata[curr_slot - 1];
754 }
755
756 //! Dereference the iterator.
759 return &curr_leaf->slotdata[curr_slot - 1];
760 }
761
762 //! Key of the current slot.
763 const key_type& key() const {
765 return curr_leaf->key(curr_slot - 1);
766 }
767
768 //! Prefix++ advance the iterator to the next slot.
770 if (curr_slot > 1) {
771 --curr_slot;
772 }
773 else if (curr_leaf->prev_leaf != nullptr) {
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.
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) {
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.
806 if (curr_slot < curr_leaf->slotuse) {
807 ++curr_slot;
808 }
809 else if (curr_leaf->next_leaf != nullptr) {
811 curr_slot = 1;
812 }
813 else {
814 // this is end() == rbegin()
816 }
817
818 return *this;
819 }
820
821 //! Postfix-- backstep the iterator to the last slot.
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) {
830 curr_slot = 1;
831 }
832 else {
833 // this is end() == rbegin()
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*().
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
914 { }
915
916 //! Copy-constructor from a const iterator.
919 { }
920
921 //! Copy-constructor from a mutable reverse iterator.
925
926 //! Dereference the iterator.
929 return curr_leaf->slotdata[curr_slot - 1];
930 }
931
932 //! Dereference the iterator.
935 return &curr_leaf->slotdata[curr_slot - 1];
936 }
937
938 //! Key of the current slot.
939 const key_type& key() const {
941 return curr_leaf->key(curr_slot - 1);
942 }
943
944 //! Prefix++ advance the iterator to the previous slot.
946 if (curr_slot > 1) {
947 --curr_slot;
948 }
949 else if (curr_leaf->prev_leaf != nullptr) {
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.
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) {
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.
982 if (curr_slot < curr_leaf->slotuse) {
983 ++curr_slot;
984 }
985 else if (curr_leaf->next_leaf != nullptr) {
987 curr_slot = 1;
988 }
989 else {
990 // this is end() == rbegin()
992 }
993
994 return *this;
995 }
996
997 //! Postfix-- backstep the iterator to the next slot.
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) {
1006 curr_slot = 1;
1007 }
1008 else {
1009 // this is end() == rbegin()
1011 }
1012
1013 return tmp;
1014 }
1015
1016 //! Equality of iterators.
1018 return (x.curr_leaf == curr_leaf) && (x.curr_slot == curr_slot);
1019 }
1020
1021 //! Inequality of iterators.
1023 return (x.curr_leaf != curr_leaf) || (x.curr_slot != curr_slot);
1024 }
1025 };
1026
1027 //! \}
1028
1029public:
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
1040
1041 //! Number of leaves in the B+ tree
1043
1044 //! Number of inner nodes in the B+ tree
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
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
1072private:
1073 //! \name Tree Object Data Members
1074 //! \{
1075
1076 //! Pointer to the B+ tree's root node, either leaf or inner node.
1078
1079 //! Pointer to first leaf in the double linked leaf chain.
1081
1082 //! Pointer to last leaf in the double linked leaf chain.
1084
1085 //! Other small statistics about the B+ tree.
1087
1088 //! Key comparison object. More comparison functions are generated from
1089 //! this < relation.
1091
1092 //! Memory allocator.
1094
1095 //! \}
1096
1097public:
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
1155public:
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
1165
1166 //! Constructor called from BTree::value_comp()
1168 : key_comp(kc)
1169 { }
1170
1171 //! Friendly to the btree class so it may call the constructor
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.
1184 return key_less_;
1185 }
1186
1187 //! Constant access to a constructed value_type comparison object. Required
1188 //! by the STL.
1190 return value_compare(key_less_);
1191 }
1192
1193 //! \}
1194
1195private:
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
1227public:
1228 //! \name Allocators
1229 //! \{
1230
1231 //! Return the base node allocator provided during construction.
1233 return allocator_;
1234 }
1235
1236 //! \}
1237
1238private:
1239 //! \name Node Object Allocation and Deallocation Functions
1240 //! \{
1241
1242 //! Return an allocator for LeafNode objects.
1246
1247 //! Return an allocator for InnerNode objects.
1251
1252 //! Allocate and initialize a leaf node
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);
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);
1274 std::allocator_traits<typename LeafNode::alloc_type>::destroy(a, ln);
1275 std::allocator_traits<typename LeafNode::alloc_type>::deallocate(a, ln, 1);
1276 stats_.leaves--;
1277 }
1278 else {
1279 InnerNode* in = static_cast<InnerNode*>(n);
1281 std::allocator_traits<typename InnerNode::alloc_type>::destroy(a, in);
1282 std::allocator_traits<typename InnerNode::alloc_type>::deallocate(a, in, 1);
1284 }
1285 }
1286
1287 //! \}
1288
1289public:
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 {
1299
1300 root_ = nullptr;
1301 head_leaf_ = tail_leaf_ = nullptr;
1302
1303 stats_ = tree_stats();
1304 }
1305
1307 }
1308
1309private:
1310 //! Recursively free up nodes.
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
1335public:
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.
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.
1349 }
1350
1351 //! Constructs a read-only constant iterator that points to the first slot
1352 //! in the first leaf of the B+ tree.
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.
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.
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.
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.
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.
1386
1387 //! \}
1388
1389private:
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
1489public:
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.
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
1516public:
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.
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.
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.
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.
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
1709public:
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
1750public:
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 {
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 {
1787 if (other.root_) {
1788 root_ = copy_recursive(other.root_);
1789 }
1790 if (self_verify) verify();
1791 }
1792 }
1793
1794private:
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
1840public:
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
1871private:
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) {
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();
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
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.
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) {
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
2148public:
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) {
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
2302private:
2303 //! \name Support Class Encapsulating Deletion Results
2304 //! \{
2305
2306 //! Result flags of recursive deletion.
2308 //! Deletion successful and no fix-ups necessary.
2310
2311 //! Deletion not successful because key was not found.
2313
2314 //! Deletion successful, the last key was updated so parent slotkeys
2315 //! need updates.
2317
2318 //! Deletion successful, children nodes were merged and the parent needs
2319 //! to remove the empty node.
2320 btree_fixmerge = 4
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
2331
2332 //! Constructor of a result with a specific flag, this can also be used
2333 //! as for implicit conversion.
2335 : flags(f), lastkey()
2336 { }
2337
2338 //! Constructor with a lastkey value.
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.
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
2362public:
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().
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
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
2435private:
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 */
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
2516
2517 root_ = leaf = nullptr;
2518 head_leaf_ = tail_leaf_ = nullptr;
2519
2520 // will be decremented soon by insert_start()
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)
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
2569 left_leaf, leaf, left_parent, parentslot - 1);
2570 }
2571 else
2572 {
2573 if (left_parent == parent)
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)
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)
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)
2745 inner, right_inner, right_parent, parentslot);
2746 else
2748 left_inner, inner, left_parent, parentslot - 1);
2749 }
2750 else
2751 {
2752 if (left_parent == parent)
2754 left_inner, inner, left_parent, parentslot - 1);
2755 else
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 */
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
2855
2856 root_ = leaf = nullptr;
2857 head_leaf_ = tail_leaf_ = nullptr;
2858
2859 // will be decremented soon by insert_start()
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) {
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 {
2913 left_leaf, leaf, left_parent, parentslot - 1);
2914 }
2915 }
2916 else
2917 {
2918 if (left_parent == parent) {
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) {
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) {
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) {
3112 inner, right_inner, right_parent, parentslot);
3113 }
3114 else {
3116 left_inner, inner, left_parent, parentslot - 1);
3117 }
3118 }
3119 else
3120 {
3121 if (left_parent == parent) {
3123 left_inner, inner, left_parent, parentslot - 1);
3124 }
3125 else {
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.
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.
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
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.
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
3452public:
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
3479private:
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
3535public:
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);
3552
3554 }
3555 }
3556
3557private:
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 {
3676 n->next_leaf->key(0)));
3677
3679 }
3680 else
3681 {
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/******************************************************************************/
STL-like read-only iterator object for B+ tree items.
Definition btree.hpp:509
const_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
Definition btree.hpp:571
BTree::key_type key_type
The key type of the btree. Returned by key().
Definition btree.hpp:514
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition btree.hpp:526
const BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
Definition btree.hpp:538
const_iterator self
Our own type.
Definition btree.hpp:532
const_iterator & operator++()
Prefix++ advance the iterator to the next slot.
Definition btree.hpp:596
const value_type & reference
Reference to the value_type. STL required.
Definition btree.hpp:520
reference operator*() const
Dereference the iterator.
Definition btree.hpp:581
bool operator!=(const const_iterator &x) const
Inequality of iterators.
Definition btree.hpp:673
const_iterator()
Default-Constructor of a const iterator.
Definition btree.hpp:556
bool operator==(const const_iterator &x) const
Equality of iterators.
Definition btree.hpp:668
const_iterator(const const_reverse_iterator &it)
Copy-constructor from a const reverse iterator.
Definition btree.hpp:576
const value_type * pointer
Pointer to the value_type. STL required.
Definition btree.hpp:523
const_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
Definition btree.hpp:566
ptrdiff_t difference_type
STL-magic.
Definition btree.hpp:529
const key_type & key() const
Key of the current slot.
Definition btree.hpp:591
unsigned short curr_slot
Current key/data slot referenced.
Definition btree.hpp:541
BTree::value_type value_type
The value type of the btree. Returned by operator*().
Definition btree.hpp:517
pointer operator->() const
Dereference the iterator.
Definition btree.hpp:586
const_iterator & operator--()
Prefix– backstep the iterator to the last slot.
Definition btree.hpp:632
const_iterator(const typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a const iterator.
Definition btree.hpp:561
STL-like read-only reverse iterator object for B+ tree items.
Definition btree.hpp:854
BTree::key_type key_type
The key type of the btree. Returned by key().
Definition btree.hpp:859
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition btree.hpp:871
const BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
Definition btree.hpp:883
const_reverse_iterator self
Our own type.
Definition btree.hpp:877
const_reverse_iterator & operator--()
Prefix– backstep the iterator to the next slot.
Definition btree.hpp:981
const_reverse_iterator & operator++()
Prefix++ advance the iterator to the previous slot.
Definition btree.hpp:945
const_reverse_iterator(const reverse_iterator &it)
Copy-constructor from a mutable reverse iterator.
Definition btree.hpp:922
const_reverse_iterator(const typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a const reverse iterator.
Definition btree.hpp:906
const_reverse_iterator(const const_iterator &it)
Copy-constructor from a const iterator.
Definition btree.hpp:917
const value_type & reference
Reference to the value_type. STL required.
Definition btree.hpp:865
bool operator==(const const_reverse_iterator &x) const
Equality of iterators.
Definition btree.hpp:1017
reference operator*() const
Dereference the iterator.
Definition btree.hpp:927
const_reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
Definition btree.hpp:912
const_reverse_iterator()
Default-Constructor of a const reverse iterator.
Definition btree.hpp:901
const value_type * pointer
Pointer to the value_type. STL required.
Definition btree.hpp:868
ptrdiff_t difference_type
STL-magic.
Definition btree.hpp:874
const key_type & key() const
Key of the current slot.
Definition btree.hpp:939
unsigned short curr_slot
One slot past the current key/data slot referenced.
Definition btree.hpp:886
BTree::value_type value_type
The value type of the btree. Returned by operator*().
Definition btree.hpp:862
pointer operator->() const
Dereference the iterator.
Definition btree.hpp:933
bool operator!=(const const_reverse_iterator &x) const
Inequality of iterators.
Definition btree.hpp:1022
STL-like iterator object for B+ tree items.
Definition btree.hpp:334
iterator(const reverse_iterator &it)
Copy-constructor from a reverse iterator.
Definition btree.hpp:404
BTree::key_type key_type
The key type of the btree. Returned by key().
Definition btree.hpp:339
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition btree.hpp:351
bool operator==(const iterator &x) const
Equality of iterators.
Definition btree.hpp:496
iterator self
Our own type.
Definition btree.hpp:357
bool operator!=(const iterator &x) const
Inequality of iterators.
Definition btree.hpp:501
iterator()
Default-Constructor of a mutable iterator.
Definition btree.hpp:394
iterator & operator--()
Prefix– backstep the iterator to the last slot.
Definition btree.hpp:460
reference operator*() const
Dereference the iterator.
Definition btree.hpp:409
value_type & reference
Reference to the value_type. STL required.
Definition btree.hpp:345
iterator & operator++()
Prefix++ advance the iterator to the next slot.
Definition btree.hpp:424
ptrdiff_t difference_type
STL-magic.
Definition btree.hpp:354
BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
Definition btree.hpp:363
value_type * pointer
Pointer to the value_type. STL required.
Definition btree.hpp:348
const key_type & key() const
Key of the current slot.
Definition btree.hpp:419
unsigned short curr_slot
Current key/data slot referenced.
Definition btree.hpp:366
BTree::value_type value_type
The value type of the btree. Returned by operator*().
Definition btree.hpp:342
pointer operator->() const
Dereference the iterator.
Definition btree.hpp:414
iterator(typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a mutable iterator.
Definition btree.hpp:399
STL-like mutable reverse iterator object for B+ tree items.
Definition btree.hpp:681
BTree::key_type key_type
The key type of the btree. Returned by key().
Definition btree.hpp:686
std::bidirectional_iterator_tag iterator_category
STL-magic iterator category.
Definition btree.hpp:698
bool operator!=(const reverse_iterator &x) const
Inequality of iterators.
Definition btree.hpp:846
reverse_iterator(const iterator &it)
Copy-constructor from a mutable iterator.
Definition btree.hpp:746
reverse_iterator self
Our own type.
Definition btree.hpp:704
reverse_iterator & operator++()
Prefix++ advance the iterator to the next slot.
Definition btree.hpp:769
bool operator==(const reverse_iterator &x) const
Equality of iterators.
Definition btree.hpp:841
reverse_iterator(typename BTree::LeafNode *l, unsigned short s)
Initializing-Constructor of a mutable reverse iterator.
Definition btree.hpp:741
reverse_iterator()
Default-Constructor of a reverse iterator.
Definition btree.hpp:736
reference operator*() const
Dereference the iterator.
Definition btree.hpp:751
value_type & reference
Reference to the value_type. STL required.
Definition btree.hpp:692
ptrdiff_t difference_type
STL-magic.
Definition btree.hpp:701
BTree::LeafNode * curr_leaf
The currently referenced leaf node of the tree.
Definition btree.hpp:710
value_type * pointer
Pointer to the value_type. STL required.
Definition btree.hpp:695
reverse_iterator & operator--()
Prefix– backstep the iterator to the last slot.
Definition btree.hpp:805
const key_type & key() const
Key of the current slot.
Definition btree.hpp:763
unsigned short curr_slot
One slot past the current key/data slot referenced.
Definition btree.hpp:713
BTree::value_type value_type
The value type of the btree. Returned by operator*().
Definition btree.hpp:689
pointer operator->() const
Dereference the iterator.
Definition btree.hpp:757
Function class to compare value_type objects. Required by the STL.
Definition btree.hpp:1161
bool operator()(const value_type &x, const value_type &y) const
Function call "less"-operator resulting in true if x < y.
Definition btree.hpp:1177
key_compare key_comp
Key comparison function from the template parameter.
Definition btree.hpp:1164
Basic class implementing a B+ tree data structure in memory.
Definition btree.hpp:125
static const unsigned short inner_slotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
Definition btree.hpp:184
void clear_recursive(node *n)
Recursively free up nodes.
Definition btree.hpp:1311
Value value_type
Second template parameter: Composition pair of key and data types, or just the key for set containers...
Definition btree.hpp:136
void verify_leaflinks() const
Verify the double linked list of leaves.
Definition btree.hpp:3653
static result_t merge_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Merge two inner nodes.
Definition btree.hpp:3169
const_reverse_iterator rend() const
Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tre...
Definition btree.hpp:1383
void swap(BTree &from)
Fast swapping of two identical B+ tree objects.
Definition btree.hpp:1144
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
void split_leaf_node(LeafNode *leaf, key_type *out_newkey, node **out_newleaf)
Split up a leaf node into two equally-filled sibling leaves.
Definition btree.hpp:2074
void free_node(node *n)
Correctly free either inner or leaf node, destructs all contained key and value objects.
Definition btree.hpp:1270
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition btree.hpp:1846
bool operator>=(const BTree &other) const
Greater-equal relation. Based on operator<.
Definition btree.hpp:1744
BTree & operator=(const BTree &other)
Assignment operator. All the key/data pairs are copied.
Definition btree.hpp:1755
bool operator==(const BTree &other) const
Equality relation of B+ trees of the same type.
Definition btree.hpp:1716
bool key_less(const key_type &a, const key_type &b) const
True if a < b ? "constructed" from key_less_()
Definition btree.hpp:1200
KeyOfValue key_of_value
Third template: key extractor class to pull key_type from value_type.
Definition btree.hpp:139
static void shift_left_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Balance two inner nodes.
Definition btree.hpp:3264
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
Definition btree.hpp:1353
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
LeafNode::alloc_type leaf_node_allocator()
Return an allocator for LeafNode objects.
Definition btree.hpp:1243
iterator lower_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair equal to or greater than key,...
Definition btree.hpp:1616
Key key_type
First template parameter: The key type of the B+ tree.
Definition btree.hpp:132
TLX_BTREE_FRIENDS
Definition btree.hpp:160
result_flags_t
Result flags of recursive deletion.
Definition btree.hpp:2307
@ btree_fixmerge
Deletion successful, children nodes were merged and the parent needs to remove the empty node.
Definition btree.hpp:2320
@ btree_not_found
Deletion not successful because key was not found.
Definition btree.hpp:2312
@ btree_update_lastkey
Deletion successful, the last key was updated so parent slotkeys need updates.
Definition btree.hpp:2316
@ btree_ok
Deletion successful and no fix-ups necessary.
Definition btree.hpp:2309
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition btree.hpp:2368
struct node * copy_recursive(const node *n)
Recursively copy nodes from another B+ tree object.
Definition btree.hpp:1796
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition btree.hpp:2155
static void shift_right_inner(InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot)
Balance two inner nodes.
Definition btree.hpp:3385
iterator insert(iterator, const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition btree.hpp:1852
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition btree.hpp:194
const_iterator lower_bound(const key_type &key) const
Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key,...
Definition btree.hpp:1636
iterator upper_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...
Definition btree.hpp:1656
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
size_t size_type
Size type used to count keys.
Definition btree.hpp:171
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition btree.hpp:150
LeafNode * allocate_leaf()
Allocate and initialize a leaf node.
Definition btree.hpp:1253
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition btree.hpp:180
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
key_compare key_less_
Key comparison object.
Definition btree.hpp:1090
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition btree.hpp:1494
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Definition btree.hpp:203
BTree(const BTree &other)
Copy constructor.
Definition btree.hpp:1779
size_type count(const key_type &key) const
Tries to locate a key in the B+ tree and returns the number of identical key entries found.
Definition btree.hpp:1584
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition btree.hpp:1499
LeafNode * tail_leaf_
Pointer to last leaf in the double linked leaf chain.
Definition btree.hpp:1083
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition btree.hpp:1371
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(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last).
Definition btree.hpp:1120
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition btree.hpp:1232
BTree(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition btree.hpp:1103
Compare key_compare
Fourth template parameter: key_type comparison function object.
Definition btree.hpp:142
unsigned short find_lower(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater or equal to key.
Definition btree.hpp:1398
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition btree.hpp:1510
InnerNode::alloc_type inner_node_allocator()
Return an allocator for InnerNode objects.
Definition btree.hpp:1248
static void shift_right_leaf(LeafNode *left, LeafNode *right, InnerNode *parent, unsigned int parentslot)
Balance two leaf nodes.
Definition btree.hpp:3329
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition btree.hpp:198
unsigned short find_upper(const node_type *n, const key_type &key) const
Searches for the first key in the node n greater than key.
Definition btree.hpp:1445
allocator_type allocator_
Memory allocator.
Definition btree.hpp:1093
bool key_greater(const key_type &a, const key_type &b) const
True if a > b ? constructed from key_less()
Definition btree.hpp:1210
LeafNode * head_leaf_
Pointer to first leaf in the double linked leaf chain.
Definition btree.hpp:1080
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition btree.hpp:3541
BTree(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
Definition btree.hpp:1110
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition btree.hpp:1505
bool operator!=(const BTree &other) const
Inequality relation. Based on operator==.
Definition btree.hpp:1722
iterator find(const key_type &key)
Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
Definition btree.hpp:1542
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
bool operator>(const BTree &other) const
Greater relation. Based on operator<.
Definition btree.hpp:1734
Traits traits
Fifth template parameter: Traits object used to define more parameters of the B+ tree.
Definition btree.hpp:146
const_iterator upper_bound(const key_type &key) const
Searches the B+ tree and returns a constant iterator to the first pair greater than key,...
Definition btree.hpp:1676
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition btree.hpp:1522
std::pair< iterator, bool > insert_start(const key_type &key, const value_type &value)
Start the insertion descent at the current root and handle root splits.
Definition btree.hpp:1878
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition btree.hpp:189
bool key_equal(const key_type &a, const key_type &b) const
True if a == b ? constructed from key_less().
Definition btree.hpp:1221
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
Definition btree.hpp:1860
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition btree.hpp:1189
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
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition btree.hpp:1294
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition btree.hpp:1347
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
Definition btree.hpp:1359
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition btree.hpp:1365
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
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Definition btree.hpp:1341
BTree(InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
Definition btree.hpp:1131
static result_t shift_left_leaf(LeafNode *left, LeafNode *right, InnerNode *parent, unsigned int parentslot)
Balance two leaf nodes.
Definition btree.hpp:3215
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition btree.hpp:2392
bool key_lessequal(const key_type &a, const key_type &b) const
True if a <= b ? constructed from key_less()
Definition btree.hpp:1205
result_t merge_leaves(LeafNode *left, LeafNode *right, InnerNode *parent)
Merge two leaf nodes.
Definition btree.hpp:3139
InnerNode * allocate_inner(unsigned short level)
Allocate and initialize an inner node.
Definition btree.hpp:1261
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition btree.hpp:1183
node * root_
Pointer to the B+ tree's root node, either leaf or inner node.
Definition btree.hpp:1077
tree_stats stats_
Other small statistics about the B+ tree.
Definition btree.hpp:1086
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
Definition btree.hpp:1377
bool operator<=(const BTree &other) const
Less-equal relation. Based on operator<.
Definition btree.hpp:1739
const_iterator find(const key_type &key) const
Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found.
Definition btree.hpp:1563
~BTree()
Frees up all used B+ tree memory pages.
Definition btree.hpp:1139
bool operator<(const BTree &other) const
Total ordering relation of B+ trees of the same type.
Definition btree.hpp:1728
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
Definition btree.hpp:2405
void split_inner_node(InnerNode *inner, key_type *out_newkey, node **out_newinner, unsigned int addslot)
Split up an inner node into two equally-filled sibling nodes.
Definition btree.hpp:2110
Allocator allocator_type
Seventh template parameter: STL allocator for tree nodes.
Definition btree.hpp:153
#define tlx_die_unless(X)
Check condition X and die miserably if false.
Definition core.hpp:65
#define TLX_BTREE_MAX(a, b)
The maximum of a and b. Used in some compile-time formulas.
Definition btree.hpp:60
#define TLX_BTREE_PRINT(x)
Print out debug information to std::cout if TLX_BTREE_DEBUG is defined.
Definition btree.hpp:52
#define TLX_BTREE_ASSERT(x)
Assertion only if TLX_BTREE_DEBUG is defined. This is not used in verify().
Definition btree.hpp:55
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
Extended structure of a inner node in-memory.
Definition btree.hpp:235
std::allocator_traits< Allocator >::template rebind_alloc< InnerNode > alloc_type
Define an related allocator for the InnerNode structs.
Definition btree.hpp:237
node * childid[inner_slotmax+1]
Pointers to children.
Definition btree.hpp:243
void initialize(const unsigned short l)
Set variables to initial values.
Definition btree.hpp:246
const key_type & key(size_t s) const
Return key in slot s.
Definition btree.hpp:251
bool is_few() const
True if few used entries, less than half full.
Definition btree.hpp:261
key_type slotkey[inner_slotmax]
Keys of children or data pointers.
Definition btree.hpp:240
bool is_underflow() const
True if node has too few entries.
Definition btree.hpp:266
bool is_full() const
True if the node's slots are full.
Definition btree.hpp:256
Extended structure of a leaf node in memory.
Definition btree.hpp:273
value_type slotdata[leaf_slotmax]
Array of (key, data) pairs.
Definition btree.hpp:284
void initialize()
Set variables to initial values.
Definition btree.hpp:287
std::allocator_traits< Allocator >::template rebind_alloc< LeafNode > alloc_type
Define an related allocator for the LeafNode structs.
Definition btree.hpp:275
LeafNode * prev_leaf
Double linked list pointers to traverse the leaves.
Definition btree.hpp:278
LeafNode * next_leaf
Double linked list pointers to traverse the leaves.
Definition btree.hpp:281
const key_type & key(size_t s) const
Return key in slot s.
Definition btree.hpp:293
bool is_few() const
True if few used entries, less than half full.
Definition btree.hpp:303
bool is_underflow() const
True if node has too few entries.
Definition btree.hpp:308
void set_slot(unsigned short slot, const value_type &value)
Set the (key,data) pair in slot.
Definition btree.hpp:314
bool is_full() const
True if the node's slots are full.
Definition btree.hpp:298
The header structure of each node in-memory.
Definition btree.hpp:213
unsigned short level
Level in the b-tree, if level == 0 -> leaf node.
Definition btree.hpp:215
unsigned short slotuse
Number of key slotuse use, so the number of valid children or data pointers.
Definition btree.hpp:219
bool is_leafnode() const
True if this is a leaf node.
Definition btree.hpp:228
void initialize(const unsigned short l)
Delayed initialisation of constructed node.
Definition btree.hpp:222
B+ tree recursive deletion has much information which is needs to be passed upward.
Definition btree.hpp:2325
result_t(result_flags_t f=btree_ok)
Constructor of a result with a specific flag, this can also be used as for implicit conversion.
Definition btree.hpp:2334
result_flags_t flags
Merged result flags.
Definition btree.hpp:2327
key_type lastkey
The key to be updated at the parent's slot.
Definition btree.hpp:2330
result_t & operator|=(const result_t &other)
Merge two results OR-ing the result flags and overwriting lastkeys.
Definition btree.hpp:2349
bool has(result_flags_t f) const
Test if this result object has a given flag set.
Definition btree.hpp:2344
result_t(result_flags_t f, const key_type &k)
Constructor with a lastkey value.
Definition btree.hpp:2339
A small struct containing basic statistics about the B+ tree.
Definition btree.hpp:1037
double avgfill_leaves() const
Return the average fill of leaves.
Definition btree.hpp:1065
size_type inner_nodes
Number of inner nodes in the B+ tree.
Definition btree.hpp:1045
size_type leaves
Number of leaves in the B+ tree.
Definition btree.hpp:1042
size_type size
Number of items in the B+ tree.
Definition btree.hpp:1039
static const unsigned short inner_slots
Base B+ tree parameter: The number of key slots in each inner node.
Definition btree.hpp:1051
static const unsigned short leaf_slots
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition btree.hpp:1048
size_type nodes() const
Return the total number of nodes.
Definition btree.hpp:1060
tree_stats()
Zero initialized.
Definition btree.hpp:1054
Generates default traits for a B+ tree used as a set or map.
Definition btree.hpp:74
static const size_t binsearch_threshold
As of stx-btree-0.9, the code does linear search in find_lower() and find_upper() instead of binary_s...
Definition btree.hpp:100
static const int inner_slots
Number of slots in each inner node of the tree.
Definition btree.hpp:93
static const bool debug
If true, the tree will print out debug information and a tree dump during insert() or erase() operati...
Definition btree.hpp:84
static const bool self_verify
If true, the tree will self verify its invariants after each insert() or erase().
Definition btree.hpp:78
static const int leaf_slots
Number of slots in each leaf of the tree.
Definition btree.hpp:88