1 : // $Id: btree.h 37 2007-04-27 12:13:27Z tb $
2 : /** \file btree.h
3 : * Contains the main B+ tree implementation template class btree.
4 : */
5 :
6 : /*
7 : * STX B+ Tree Template Classes v0.7
8 : * Copyright (C) 2007 Timo Bingmann
9 : *
10 : * This library is free software; you can redistribute it and/or modify it
11 : * under the terms of the GNU Lesser General Public License as published by the
12 : * Free Software Foundation; either version 2.1 of the License, or (at your
13 : * option) any later version.
14 : *
15 : * This library is distributed in the hope that it will be useful, but WITHOUT
16 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
18 : * for more details.
19 : *
20 : * You should have received a copy of the GNU Lesser General Public License
21 : * along with this library; if not, write to the Free Software Foundation,
22 : * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 : */
24 :
25 : #ifndef _STX_BTREE_H_
26 : #define _STX_BTREE_H_
27 :
28 : // *** Required Headers from the STL
29 :
30 : #include <functional>
31 : #include <algorithm>
32 : #include <istream>
33 : #include <ostream>
34 : #include <assert.h>
35 :
36 : // *** Debugging Macros
37 :
38 : #ifdef BTREE_DEBUG
39 :
40 : #include <iostream>
41 :
42 : /// Print out debug information to std::cout if BTREE_DEBUG is defined.
43 : #define BTREE_PRINT(x) do { if (debug) (std::cout << x); } while(0)
44 :
45 : /// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
46 : #define BTREE_ASSERT(x) do { assert(x); } while(0)
47 :
48 : #else
49 :
50 : /// Print out debug information to std::cout if BTREE_DEBUG is defined.
51 : #define BTREE_PRINT(x) do { } while(0)
52 :
53 : /// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
54 : #define BTREE_ASSERT(x) do { } while(0)
55 :
56 : #endif
57 :
58 : /// The maximum of a and b. Used in some compile-time formulas.
59 : #define BTREE_MAX(a,b) ((a) < (b) ? (b) : (a))
60 :
61 : /// STX - Some Template Extensions namespace
62 : namespace stx {
63 :
64 : /** Generates default traits for a B+ tree used as a set. It estimates leaf and
65 : * inner node sizes by assuming a cache line size of 256 bytes. */
66 : template <typename _Key>
67 : struct btree_default_set_traits
68 : {
69 : /// If true, the tree will self verify it's invariants after each insert()
70 : /// or erase(). The header must have been compiled with BTREE_DEBUG defined.
71 : static const bool selfverify = false;
72 :
73 : /// If true, the tree will print out debug information and a tree dump
74 : /// during insert() or erase() operation. The header must have been
75 : /// compiled with BTREE_DEBUG defined and key_type must be std::ostream
76 : /// printable.
77 : static const bool debug = false;
78 :
79 : /// Number of slots in each leaf of the tree. Estimated so that each node
80 : /// has a size of about 256 bytes.
81 : static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );
82 :
83 : /// Number of slots in each inner node of the tree. Estimated so that each node
84 : /// has a size of about 256 bytes.
85 : static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
86 : };
87 :
88 : /** Generates default traits for a B+ tree used as a map. It estimates leaf and
89 : * inner node sizes by assuming a cache line size of 256 bytes. */
90 : template <typename _Key, typename _Data>
91 : struct btree_default_map_traits
92 : {
93 : /// If true, the tree will self verify it's invariants after each insert()
94 : /// or erase(). The header must have been compiled with BTREE_DEBUG defined.
95 : static const bool selfverify = false;
96 :
97 : /// If true, the tree will print out debug information and a tree dump
98 : /// during insert() or erase() operation. The header must have been
99 : /// compiled with BTREE_DEBUG defined and key_type must be std::ostream
100 : /// printable.
101 : static const bool debug = false;
102 :
103 : /// Number of slots in each leaf of the tree. Estimated so that each node
104 : /// has a size of about 256 bytes.
105 : static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );
106 :
107 : /// Number of slots in each inner node of the tree. Estimated so that each node
108 : /// has a size of about 256 bytes.
109 : static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
110 : };
111 :
112 : /** @brief Basic class implementing a base B+ tree data structure in memory.
113 : *
114 : * The base implementation of a memory B+ tree. It is based on the
115 : * implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper
116 : * and other algorithm resources. Almost all STL-required function calls are
117 : * implemented. The asymptotic time requirements of the STL are not always
118 : * fulfilled in theory, however in practice this B+ tree performs better than a
119 : * red-black tree by using more memory. The insertion function splits the nodes
120 : * on the recursion unroll. Erase is largely based on Jannink's ideas.
121 : *
122 : * This class is specialized into btree_set, btree_multiset, btree_map and
123 : * btree_multimap using default template parameters and facade functions.
124 : */
125 : template <typename _Key, typename _Data,
126 : typename _Value = std::pair<_Key, _Data>,
127 : typename _Compare = std::less<_Key>,
128 : typename _Traits = btree_default_map_traits<_Key, _Data>,
129 : bool _Duplicates = false>
130 : class btree
131 : {
132 : public:
133 : // *** Template Parameter Types
134 :
135 : /// First template parameter: The key type of the B+ tree. This is stored
136 : /// in inner nodes and leaves
137 : typedef _Key key_type;
138 :
139 : /// Second template parameter: The data type associated with each
140 : /// key. Stored in the B+ tree's leaves
141 : typedef _Data data_type;
142 :
143 : /// Third template parameter: Composition pair of key and data types, this
144 : /// is required by the STL standard. The B+ tree does not store key and
145 : /// data together. If value_type == key_type then the B+ tree implements a
146 : /// set.
147 : typedef _Value value_type;
148 :
149 : /// Fourth template parameter: Key comparison function object
150 : typedef _Compare key_compare;
151 :
152 : /// Fifth template parameter: Traits object used to define more parameters
153 : /// of the B+ tree
154 : typedef _Traits traits;
155 :
156 : /// Sixth template parameter: Allow duplicate keys in the B+ tree. Used to
157 : /// implement multiset and multimap.
158 : static const bool allow_duplicates = _Duplicates;
159 :
160 : public:
161 : // *** Constructed Types
162 :
163 : /// Typedef of our own type
164 : typedef btree<key_type, data_type, value_type,
165 : key_compare, traits, allow_duplicates> btree_self;
166 :
167 : /// Size type used to count keys
168 : typedef size_t size_type;
169 :
170 : /// The pair of key_type and data_type, this may be different from value_type.
171 : typedef std::pair<key_type, data_type> pair_type;
172 :
173 : public:
174 : // *** Static Constant Options and Values of the B+ Tree
175 :
176 : /// Base B+ tree parameter: The number of key/data slots in each leaf
177 : static const unsigned short leafslotmax = traits::leafslots;
178 :
179 : /// Base B+ tree parameter: The number of key slots in each inner node,
180 : /// this can differ from slots in each leaf.
181 : static const unsigned short innerslotmax = traits::innerslots;
182 :
183 : /// Computed B+ tree parameter: The minimum number of key/data slots used
184 : /// in a leaf. If fewer slots are used, the leaf will be merged or slots
185 : /// shifted from it's siblings.
186 : static const unsigned short minleafslots = (leafslotmax / 2);
187 :
188 : /// Computed B+ tree parameter: The minimum number of key slots used
189 : /// in an inner node. If fewer slots are used, the inner node will be
190 : /// merged or slots shifted from it's siblings.
191 : static const unsigned short mininnerslots = (innerslotmax / 2);
192 :
193 : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
194 : /// invariants after each insert/erase operation.
195 : static const bool selfverify = traits::selfverify;
196 :
197 : /// Debug parameter: Prints out lots of debug information about how the
198 : /// algorithms change the tree. Requires the header file to be compiled
199 : /// with BTREE_PRINT and the key type must be std::ostream printable.
200 : static const bool debug = traits::debug;
201 :
202 : private:
203 : // *** Node Classes for In-Memory Nodes
204 :
205 : /// The header structure of each node in-memory. This structure is extended
206 : /// by inner_node or leaf_node.
207 : struct node
208 65 : {
209 : /// Level in the b-tree, if level == 0 -> leaf node
210 : unsigned short level;
211 :
212 : /// Number of key slotuse use, so number of valid children or data
213 : /// pointers
214 : unsigned short slotuse;
215 :
216 : /// Delayed initialisation of constructed node
217 8693 : inline void initialize(const unsigned short l)
218 : {
219 8693 : level = l;
220 8693 : slotuse = 0;
221 : }
222 :
223 : /// True if this is a leaf node
224 61849855 : inline bool isleafnode() const
225 : {
226 61849855 : return (level == 0);
227 : }
228 : };
229 :
230 : /// Extended structure of a inner node in-memory. Contains only keys and no
231 : /// data items.
232 : struct inner_node : public node
233 9 : {
234 : /// Keys of children or data pointers
235 : key_type slotkey[innerslotmax];
236 :
237 : /// Pointers to children
238 : node* childid[innerslotmax+1];
239 :
240 : /// Set variables to initial values
241 1537 : inline void initialize(const unsigned short l)
242 : {
243 1537 : node::initialize(l);
244 : }
245 :
246 : /// True if the node's slots are full
247 8191 : inline bool isfull() const
248 : {
249 8191 : return (node::slotuse == innerslotmax);
250 : }
251 :
252 : /// True if few used entries, less than half full
253 3488 : inline bool isfew() const
254 : {
255 3488 : return (node::slotuse <= mininnerslots);
256 : }
257 :
258 : /// True if node has too few entries
259 11803777 : inline bool isunderflow() const
260 : {
261 11803777 : return (node::slotuse < mininnerslots);
262 : }
263 : };
264 :
265 : /// Extended structure of a leaf node in memory. Contains pairs of keys and
266 : /// data items. Key and data slots are kept in separate arrays, because the
267 : /// key array is traversed very often compared to accessing the data items.
268 : struct leaf_node : public node
269 56 : {
270 : /// Double linked list pointers to traverse the leaves
271 : leaf_node *prevleaf;
272 :
273 : /// Double linked list pointers to traverse the leaves
274 : leaf_node *nextleaf;
275 :
276 : /// Keys of children or data pointers
277 : key_type slotkey[leafslotmax];
278 :
279 : /// Array of data
280 : data_type slotdata[leafslotmax];
281 :
282 : /// Set variables to initial values
283 7156 : inline void initialize()
284 : {
285 7156 : node::initialize(0);
286 7156 : prevleaf = nextleaf = NULL;
287 : }
288 :
289 : /// True if the node's slots are full
290 30514 : inline bool isfull() const
291 : {
292 30514 : return (node::slotuse == leafslotmax);
293 : }
294 :
295 : /// True if few used entries, less than half full
296 13759 : inline bool isfew() const
297 : {
298 13759 : return (node::slotuse <= minleafslots);
299 : }
300 :
301 : /// True if node has too few entries
302 49332010 : inline bool isunderflow() const
303 : {
304 49332010 : return (node::slotuse < minleafslots);
305 : }
306 : };
307 :
308 : private:
309 : // *** Template Magic to Convert a pair or key/data types to a value_type
310 :
311 : /// \internal For sets the second pair_type is an empty struct, so the
312 : /// value_type should only be the first.
313 : template <typename value_type, typename pair_type>
314 : struct btree_pair_to_value
315 : {
316 : /// Convert a fake pair type to just the first component
317 : inline value_type operator()(pair_type& p) const {
318 : return p.first;
319 : }
320 : /// Convert a fake pair type to just the first component
321 16316 : inline value_type operator()(const pair_type& p) const {
322 16316 : return p.first;
323 : }
324 : };
325 :
326 : /// \internal For maps value_type is the same as the pair_type
327 : template <typename value_type>
328 : struct btree_pair_to_value<value_type, value_type>
329 : {
330 : /// Identity "convert" a real pair type to just the first component
331 : inline value_type operator()(pair_type& p) const {
332 : return p;
333 : }
334 : /// Identity "convert" a real pair type to just the first component
335 0 : inline value_type operator()(const pair_type& p) const {
336 0 : return p;
337 : }
338 : };
339 :
340 : /// Using template specialization select the correct converter used by the
341 : /// iterators
342 : typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;
343 :
344 : public:
345 : // *** Iterators and Reverse Iterators
346 :
347 : class iterator;
348 : class const_iterator;
349 :
350 : /// STL-like iterator object for B+ tree items. The iterator points to a
351 : /// specific slot number in a leaf.
352 : class iterator
353 : {
354 : public:
355 : // *** Types
356 :
357 : /// The key type of the btree. Returned by key().
358 : typedef typename btree::key_type key_type;
359 :
360 : /// The data type of the btree. Returned by data().
361 : typedef typename btree::data_type data_type;
362 :
363 : /// The value type of the btree. Returned by operator*().
364 : typedef typename btree::value_type value_type;
365 :
366 : /// The pair type of the btree.
367 : typedef typename btree::pair_type pair_type;
368 :
369 : /// Reference to the value_type. Required by the reverse_iterator.
370 : typedef value_type& reference;
371 :
372 : /// Pointer to the value_type. Required by the reverse_iterator.
373 : typedef value_type* pointer;
374 :
375 : /// STL-magic iterator category
376 : typedef std::bidirectional_iterator_tag iterator_category;
377 :
378 : /// STL-magic
379 : typedef ptrdiff_t difference_type;
380 :
381 : /// Our own type
382 : typedef iterator self;
383 :
384 : private:
385 : // *** Members
386 :
387 : /// The currently referenced leaf node of the tree
388 : typename btree::leaf_node* currnode;
389 :
390 : /// Current key/data slot referenced
391 : unsigned short currslot;
392 :
393 : /// Friendly to the const_iterator, so it may access the two data items directly
394 : friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>::const_iterator;
395 :
396 : /// Evil! A temporary value_type to STL-correctly deliver operator* and
397 : /// operator->
398 : mutable value_type temp_value;
399 :
400 : public:
401 : // *** Methods
402 :
403 : /// Constructor of a mutable iterator
404 51852 : inline iterator(typename btree::leaf_node *l, unsigned short s)
405 51852 : : currnode(l), currslot(s)
406 51852 : { }
407 :
408 : /// Dereference the iterator, this is not a value_type& because key and
409 : /// value are not stored together
410 9600 : inline reference operator*() const
411 : {
412 9600 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
413 : currnode->slotdata[currslot]) );
414 9600 : return temp_value;
415 : }
416 :
417 : /// Dereference the iterator. Do not use this if possible, use key()
418 : /// and data() instead. The B+ tree does not stored key and data
419 : /// together.
420 : inline pointer operator->() const
421 : {
422 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
423 : currnode->slotdata[currslot]) );
424 : return &temp_value;
425 : }
426 :
427 : /// Key of the current slot
428 17360 : inline const key_type& key() const
429 : {
430 17360 : return currnode->slotkey[currslot];
431 : }
432 :
433 : /// Writable reference to the current data object
434 0 : inline data_type& data() const
435 : {
436 0 : return currnode->slotdata[currslot];
437 : }
438 :
439 : /// Prefix++ advance the iterator to the next slot
440 23760 : inline self& operator++()
441 : {
442 23760 : if (currslot + 1 < currnode->slotuse) {
443 18365 : ++currslot;
444 : }
445 5395 : else if (currnode->nextleaf != NULL) {
446 5387 : currnode = currnode->nextleaf;
447 5387 : currslot = 0;
448 : }
449 : else {
450 : // this is end()
451 8 : currslot = currnode->slotuse;
452 : }
453 :
454 23760 : return *this;
455 : }
456 :
457 : /// Postfix++ advance the iterator to the next slot
458 : inline self operator++(int)
459 : {
460 : self tmp = *this; // copy ourselves
461 :
462 : if (currslot + 1 < currnode->slotuse) {
463 : ++currslot;
464 : }
465 : else if (currnode->nextleaf != NULL) {
466 : currnode = currnode->nextleaf;
467 : currslot = 0;
468 : }
469 : else {
470 : // this is end()
471 : currslot = currnode->slotuse;
472 : }
473 :
474 : return tmp;
475 : }
476 :
477 : /// Prefix-- backstep the iterator to the last slot
478 16000 : inline self& operator--()
479 : {
480 16000 : if (currslot > 0) {
481 13150 : --currslot;
482 : }
483 2850 : else if (currnode->prevleaf != NULL) {
484 2850 : currnode = currnode->prevleaf;
485 2850 : currslot = currnode->slotuse - 1;
486 : }
487 : else {
488 : // this is begin()
489 0 : currslot = 0;
490 : }
491 :
492 16000 : return *this;
493 : }
494 :
495 : /// Postfix-- backstep the iterator to the last slot
496 : inline self operator--(int)
497 : {
498 : self tmp = *this; // copy ourselves
499 :
500 : if (currslot > 0) {
501 : --currslot;
502 : }
503 : else if (currnode->prevleaf != NULL) {
504 : currnode = currnode->prevleaf;
505 : currslot = currnode->slotuse - 1;
506 : }
507 : else {
508 : // this is begin()
509 : currslot = 0;
510 : }
511 :
512 : return tmp;
513 : }
514 :
515 : /// Equality of iterators
516 6410 : inline bool operator==(const self& x) const
517 : {
518 6410 : return (x.currnode == currnode) && (x.currslot == currslot);
519 : }
520 :
521 : /// Inequality of iterators
522 23768 : inline bool operator!=(const self& x) const
523 : {
524 23768 : return (x.currnode != currnode) || (x.currslot != currslot);
525 : }
526 : };
527 :
528 : /// STL-like read-only iterator object for B+ tree items. The iterator
529 : /// points to a specific slot number in a leaf.
530 : class const_iterator
531 : {
532 : public:
533 : // *** Types
534 :
535 : /// The key type of the btree. Returned by key().
536 : typedef typename btree::key_type key_type;
537 :
538 : /// The data type of the btree. Returned by data().
539 : typedef typename btree::data_type data_type;
540 :
541 : /// The value type of the btree. Returned by operator*().
542 : typedef typename btree::value_type value_type;
543 :
544 : /// The pair type of the btree.
545 : typedef typename btree::pair_type pair_type;
546 :
547 : /// Reference to the value_type. Required by the reverse_iterator.
548 : typedef const value_type& reference;
549 :
550 : /// Pointer to the value_type. Required by the reverse_iterator.
551 : typedef const value_type* pointer;
552 :
553 : /// STL-magic iterator category
554 : typedef std::bidirectional_iterator_tag iterator_category;
555 :
556 : /// STL-magic
557 : typedef ptrdiff_t difference_type;
558 :
559 : /// Our own type
560 : typedef const_iterator self;
561 :
562 : private:
563 : // *** Members
564 :
565 : /// The currently referenced leaf node of the tree
566 : const typename btree::leaf_node* currnode;
567 :
568 : /// Current key/data slot referenced
569 : unsigned short currslot;
570 :
571 : /// Evil! A temporary value_type to STL-correctly deliver operator* and
572 : /// operator->
573 : mutable value_type temp_value;
574 :
575 : public:
576 : // *** Methods
577 :
578 : /// Constructor of a const iterator
579 31 : inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
580 31 : : currnode(l), currslot(s)
581 31 : { }
582 :
583 : /// Copy-constructor from a mutable const iterator
584 9680 : inline const_iterator(const iterator &it)
585 9680 : : currnode(it.currnode), currslot(it.currslot)
586 9680 : { }
587 :
588 : /// Dereference the iterator. Do not use this if possible, use key()
589 : /// and data() instead. The B+ tree does not stored key and data
590 : /// together.
591 6716 : inline reference operator*() const
592 : {
593 6716 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
594 : currnode->slotdata[currslot]) );
595 6716 : return temp_value;
596 : }
597 :
598 : /// Dereference the iterator. Do not use this if possible, use key()
599 : /// and data() instead. The B+ tree does not stored key and data
600 : /// together.
601 : inline pointer operator->() const
602 : {
603 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
604 : currnode->slotdata[currslot]) );
605 : return &temp_value;
606 : }
607 :
608 : /// Key of the current slot
609 4024 : inline const key_type& key() const
610 : {
611 4024 : return currnode->slotkey[currslot];
612 : }
613 :
614 : /// Read-only reference to the current data object
615 : inline const data_type& data() const
616 : {
617 : return currnode->slotdata[currslot];
618 : }
619 :
620 : /// Prefix++ advance the iterator to the next slot
621 4796 : inline self& operator++()
622 : {
623 4796 : if (currslot + 1 < currnode->slotuse) {
624 3962 : ++currslot;
625 : }
626 834 : else if (currnode->nextleaf != NULL) {
627 822 : currnode = currnode->nextleaf;
628 822 : currslot = 0;
629 : }
630 : else {
631 : // this is end()
632 12 : currslot = currnode->slotuse;
633 : }
634 :
635 4796 : return *this;
636 : }
637 :
638 : /// Postfix++ advance the iterator to the next slot
639 : inline self operator++(int)
640 : {
641 : self tmp = *this; // copy ourselves
642 :
643 : if (currslot + 1 < currnode->slotuse) {
644 : ++currslot;
645 : }
646 : else if (currnode->nextleaf != NULL) {
647 : currnode = currnode->nextleaf;
648 : currslot = 0;
649 : }
650 : else {
651 : // this is end()
652 : currslot = currnode->slotuse;
653 : }
654 :
655 : return tmp;
656 : }
657 :
658 : /// Prefix-- backstep the iterator to the last slot
659 : inline self& operator--()
660 : {
661 : if (currslot > 0) {
662 : --currslot;
663 : }
664 : else if (currnode->prevleaf != NULL) {
665 : currnode = currnode->prevleaf;
666 : currslot = currnode->slotuse - 1;
667 : }
668 : else {
669 : // this is begin()
670 : currslot = 0;
671 : }
672 :
673 : return *this;
674 : }
675 :
676 : /// Postfix-- backstep the iterator to the last slot
677 : inline self operator--(int)
678 : {
679 : self tmp = *this; // copy ourselves
680 :
681 : if (currslot > 0) {
682 : --currslot;
683 : }
684 : else if (currnode->prevleaf != NULL) {
685 : currnode = currnode->prevleaf;
686 : currslot = currnode->slotuse - 1;
687 : }
688 : else {
689 : // this is begin()
690 : currslot = 0;
691 : }
692 :
693 : return tmp;
694 : }
695 :
696 : /// Equality of iterators
697 4842 : inline bool operator==(const self& x) const
698 : {
699 4842 : return (x.currnode == currnode) && (x.currslot == currslot);
700 : }
701 :
702 : /// Inequality of iterators
703 3367 : inline bool operator!=(const self& x) const
704 : {
705 3367 : return (x.currnode != currnode) || (x.currslot != currslot);
706 : }
707 : };
708 :
709 : /// create mutable reverse iterator by using STL magic
710 : typedef std::reverse_iterator<iterator> reverse_iterator;
711 :
712 : /// create constant reverse iterator by using STL magic
713 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
714 :
715 : public:
716 : // *** Small Statistics Structure
717 :
718 : /** A small struct containing basic statistics about the B+ tree. It can be
719 : * fetched using get_stats(). */
720 : struct tree_stats
721 : {
722 : /// Number of items in the B+ tree
723 : size_type itemcount;
724 :
725 : /// Number of leaves in the B+ tree
726 : size_type leaves;
727 :
728 : /// Number of inner nodes in the B+ tree
729 : size_type innernodes;
730 :
731 : /// Base B+ tree parameter: The number of key/data slots in each leaf
732 : static const unsigned short leafslots = btree_self::leafslotmax;
733 :
734 : /// Base B+ tree parameter: The number of key slots in each inner node.
735 : static const unsigned short innerslots = btree_self::innerslotmax;
736 :
737 : /// Zero initialized
738 66713 : inline tree_stats()
739 : : itemcount(0),
740 66713 : leaves(0), innernodes(0)
741 66713 : {
742 : }
743 :
744 : /// Return the total number of nodes
745 : inline size_type nodes() const
746 : {
747 : return innernodes + leaves;
748 : }
749 :
750 : /// Return the average fill of leaves
751 : inline double avgfill_leaves() const
752 : {
753 : return static_cast<double>(itemcount) / (leaves * leafslots);
754 : }
755 : };
756 :
757 : private:
758 : // *** Tree Object Data Members
759 :
760 : /// Pointer to the B+ tree's root node, either leaf or inner node
761 : node* root;
762 :
763 : /// Pointer to first leaf in the double linked leaf chain
764 : leaf_node *headleaf;
765 :
766 : /// Pointer to last leaf in the double linked leaf chain
767 : leaf_node *tailleaf;
768 :
769 : /// Other small statistics about the B+ tree
770 : tree_stats stats;
771 :
772 : /// Key comparison object. More comparison functions are generated from
773 : /// this < relation.
774 : key_compare key_less;
775 :
776 : public:
777 : // *** Constructors and Destructor
778 :
779 : /// Default constructor initializing an empty B+ tree with the standard key
780 : /// comparison function
781 15 : inline btree()
782 15 : : root(NULL), headleaf(NULL), tailleaf(NULL)
783 15 : {
784 : }
785 :
786 : /// Constructor initializing an empty B+ tree with a special key
787 : /// comparison object
788 1 : inline btree(const key_compare &kcf)
789 : : root(NULL), headleaf(NULL), tailleaf(NULL),
790 1 : key_less(kcf)
791 1 : {
792 : }
793 :
794 : /// Constructor initializing a B+ tree with the range [first,last)
795 : template <class InputIterator>
796 : inline btree(InputIterator first, InputIterator last)
797 : : root(NULL), headleaf(NULL), tailleaf(NULL)
798 : {
799 : insert(first, last);
800 : }
801 :
802 : /// Constructor initializing a B+ tree with the range [first,last) and a
803 : /// special key comparison object
804 : template <class InputIterator>
805 : inline btree(InputIterator first, InputIterator last, const key_compare &kcf)
806 : : root(NULL), headleaf(NULL), tailleaf(NULL),
807 : key_less(kcf)
808 : {
809 : insert(first, last);
810 : }
811 :
812 : /// Frees up all used B+ tree memory pages
813 18 : inline ~btree()
814 : {
815 18 : clear();
816 : }
817 :
818 : /// Fast swapping of two identical B+ tree objects.
819 : void swap(btree_self& from)
820 : {
821 : std::swap(root, from.root);
822 : std::swap(headleaf, from.headleaf);
823 : std::swap(tailleaf, from.tailleaf);
824 : std::swap(stats, from.stats);
825 : std::swap(key_less, from.key_less);
826 : }
827 :
828 : public:
829 : // *** Key and Value Comparison Function Objects
830 :
831 : /// Function class to compare value_type objects. Required by the STL
832 : class value_compare
833 : {
834 : protected:
835 : /// Key comparison function from the template parameter
836 : key_compare key_comp;
837 :
838 : /// Constructor called from btree::value_comp()
839 0 : inline value_compare(key_compare kc)
840 0 : : key_comp(kc)
841 0 : { }
842 :
843 : /// Friendly to the btree class so it may call the constructor
844 : friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>;
845 :
846 : public:
847 : /// Function call "less"-operator resulting in true if x < y.
848 : inline bool operator()(const value_type& x, const value_type& y) const
849 : {
850 : return key_comp(x.first, y.first);
851 : }
852 : };
853 :
854 : /// Constant access to the key comparison object sorting the B+ tree
855 3 : inline key_compare key_comp() const
856 : {
857 3 : return key_less;
858 : }
859 :
860 : /// Constant access to a constructed value_type comparison object. Required
861 : /// by the STL
862 0 : inline value_compare value_comp() const
863 : {
864 0 : return value_compare(key_less);
865 : }
866 :
867 : private:
868 : // *** Convenient Key Comparison Functions Generated From key_less
869 :
870 : /// True if a <= b ? constructed from key_less()
871 395638602 : inline bool key_lessequal(const key_type &a, const key_type b) const
872 : {
873 395638602 : return !key_less(b, a);
874 : }
875 :
876 : /// True if a > b ? constructed from key_less()
877 : inline bool key_greater(const key_type &a, const key_type &b) const
878 : {
879 : return key_less(b, a);
880 : }
881 :
882 : /// True if a >= b ? constructed from key_less()
883 49244640 : inline bool key_greaterequal(const key_type &a, const key_type b) const
884 : {
885 49244640 : return !key_less(a, b);
886 : }
887 :
888 : /// True if a == b ? constructed from key_less(). This requires the <
889 : /// relation to be a total order, otherwise the B+ tree cannot be sorted.
890 52455581 : inline bool key_equal(const key_type &a, const key_type &b) const
891 : {
892 52455581 : return !key_less(a, b) && !key_less(b, a);
893 : }
894 :
895 : private:
896 : // *** Node Object Allocation and Deallocation Functions
897 :
898 : /// Allocate and initialize a leaf node
899 7156 : inline leaf_node* allocate_leaf()
900 : {
901 7156 : leaf_node* n = new leaf_node;
902 7156 : n->initialize();
903 7156 : stats.leaves++;
904 7156 : return n;
905 : }
906 :
907 : /// Allocate and initialize an inner node
908 1537 : inline inner_node* allocate_inner(unsigned short l)
909 : {
910 1537 : inner_node* n = new inner_node;
911 1537 : n->initialize(l);
912 1537 : stats.innernodes++;
913 1537 : return n;
914 : }
915 :
916 : /// Correctly free either inner or leaf node, destructs all contained key
917 : /// and value objects
918 8693 : inline void free_node(node *n)
919 : {
920 8693 : if (n->isleafnode()) {
921 7156 : delete static_cast<leaf_node*>(n);
922 7156 : stats.leaves--;
923 : }
924 : else {
925 1537 : delete static_cast<inner_node*>(n);
926 1537 : stats.innernodes--;
927 : }
928 : }
929 :
930 : public:
931 : // *** Fast Destruction of the B+ Tree
932 :
933 : /// Frees all key/data pairs and all nodes of the tree
934 20 : void clear()
935 : {
936 20 : if (root)
937 : {
938 17 : clear_recursive(root);
939 17 : free_node(root);
940 :
941 17 : root = NULL;
942 17 : headleaf = tailleaf = NULL;
943 :
944 17 : stats = tree_stats();
945 : }
946 :
947 20 : BTREE_ASSERT(stats.itemcount == 0);
948 : }
949 :
950 : private:
951 : /// Recursively free up nodes
952 2676 : void clear_recursive(node *n)
953 : {
954 2676 : if (n->isleafnode())
955 : {
956 2273 : leaf_node *leafnode = static_cast<leaf_node*>(n);
957 :
958 2273 : for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
959 : {
960 : // data objects are deleted by leaf_node's destructor
961 : }
962 : }
963 : else
964 : {
965 403 : inner_node *innernode = static_cast<inner_node*>(n);
966 :
967 3062 : for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
968 : {
969 2659 : clear_recursive(innernode->childid[slot]);
970 5335 : free_node(innernode->childid[slot]);
971 : }
972 : }
973 : }
974 :
975 : public:
976 : // *** STL Iterator Construction Functions
977 :
978 : /// Constructs a read/data-write iterator that points to the first slot in
979 : /// the first leaf of the B+ tree.
980 9 : inline iterator begin()
981 : {
982 9 : return iterator(headleaf, 0);
983 : }
984 :
985 : /// Constructs a read/data-write iterator that points to the first invalid
986 : /// slot in the last leaf of the B+ tree.
987 22215 : inline iterator end()
988 : {
989 22215 : return iterator(tailleaf, tailleaf->slotuse);
990 : }
991 :
992 : /// Constructs a read-only constant iterator that points to the first slot
993 : /// in the first leaf of the B+ tree.
994 18 : inline const_iterator begin() const
995 : {
996 18 : return const_iterator(headleaf, 0);
997 : }
998 :
999 : /// Constructs a read-only constant iterator that points to the first
1000 : /// invalid slot in the last leaf of the B+ tree.
1001 13 : inline const_iterator end() const
1002 : {
1003 13 : return const_iterator(tailleaf, tailleaf->slotuse);
1004 : }
1005 :
1006 : /// Constructs a read/data-write reverse iterator that points to the first
1007 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
1008 2 : inline reverse_iterator rbegin()
1009 : {
1010 2 : return reverse_iterator(end());
1011 : }
1012 :
1013 : /// Constructs a read/data-write reverse iterator that points to the first
1014 : /// slot in the first leaf of the B+ tree. Uses STL magic.
1015 2 : inline reverse_iterator rend()
1016 : {
1017 2 : return reverse_iterator(begin());
1018 : }
1019 :
1020 : /// Constructs a read-only reverse iterator that points to the first
1021 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
1022 0 : inline const_reverse_iterator rbegin() const
1023 : {
1024 0 : return const_reverse_iterator(end());
1025 : }
1026 :
1027 : /// Constructs a read-only reverse iterator that points to the first slot
1028 : /// in the first leaf of the B+ tree. Uses STL magic.
1029 0 : inline const_reverse_iterator rend() const
1030 : {
1031 0 : return const_reverse_iterator(begin());
1032 : }
1033 :
1034 : private:
1035 : // *** B+ Tree Node Binary Search Functions
1036 :
1037 : /// Searches for the first key in the node n less or equal to key. Uses
1038 : /// binary search with an optional linear self-verification. This is a
1039 : /// template function, because the slotkey array is located at different
1040 : /// places in leaf_node and inner_node.
1041 : template <typename node_type>
1042 712539 : inline int find_lower(const node_type *n, const key_type& key) const
1043 : {
1044 712539 : if (n->slotuse == 0) return 0;
1045 :
1046 712526 : int lo = 0,
1047 712526 : hi = n->slotuse - 1;
1048 :
1049 2655710 : while(lo < hi)
1050 : {
1051 1230658 : int mid = (lo + hi) / 2;
1052 :
1053 1230658 : if (key_lessequal(key, n->slotkey[mid])) {
1054 573768 : hi = mid - 1;
1055 : }
1056 : else {
1057 656890 : lo = mid + 1;
1058 : }
1059 : }
1060 :
1061 712526 : if (hi < 0 || key_less(n->slotkey[hi], key))
1062 422444 : hi++;
1063 :
1064 : BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
1065 :
1066 : // verify result using simple linear search
1067 : if (selfverify)
1068 : {
1069 712526 : int i = n->slotuse - 1;
1070 3399314 : while(i >= 0 && key_lessequal(key, n->slotkey[i]))
1071 1974262 : i--;
1072 712526 : i++;
1073 :
1074 : BTREE_PRINT("testfind: " << i << std::endl);
1075 712526 : BTREE_ASSERT(i == hi);
1076 : }
1077 : else {
1078 : BTREE_PRINT(std::endl);
1079 : }
1080 :
1081 712526 : return hi;
1082 : }
1083 :
1084 : /// Searches for the first key in the node n greater than key. Uses binary
1085 : /// search with an optional linear self-verification. This is a template
1086 : /// function, because the slotkey array is located at different places in
1087 : /// leaf_node and inner_node.
1088 : template <typename node_type>
1089 7700 : inline int find_upper(const node_type *n, const key_type& key) const
1090 : {
1091 7700 : if (n->slotuse == 0) return 0;
1092 :
1093 7700 : int lo = 0,
1094 7700 : hi = n->slotuse - 1;
1095 :
1096 30732 : while(lo < hi)
1097 : {
1098 15332 : int mid = (lo + hi) / 2;
1099 :
1100 15332 : if (key_less(key, n->slotkey[mid])) {
1101 6026 : hi = mid - 1;
1102 : }
1103 : else {
1104 9306 : lo = mid + 1;
1105 : }
1106 : }
1107 :
1108 7700 : if (hi < 0 || key_lessequal(n->slotkey[hi], key))
1109 4748 : hi++;
1110 :
1111 : BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
1112 :
1113 : // verify result using simple linear search
1114 : if (selfverify)
1115 : {
1116 7700 : int i = n->slotuse - 1;
1117 36122 : while(i >= 0 && key_less(key, n->slotkey[i]))
1118 20722 : i--;
1119 7700 : i++;
1120 :
1121 : BTREE_PRINT("btree::find_upper testfind: " << i << std::endl);
1122 7700 : BTREE_ASSERT(i == hi);
1123 : }
1124 : else {
1125 : BTREE_PRINT(std::endl);
1126 : }
1127 :
1128 7700 : return hi;
1129 : }
1130 :
1131 : public:
1132 : // *** Access Functions to the Item Count
1133 :
1134 : /// Return the number of key/data pairs in the B+ tree
1135 144086 : inline size_type size() const
1136 : {
1137 144086 : return stats.itemcount;
1138 : }
1139 :
1140 : /// Returns true if there is at least one key/data pair in the B+ tree
1141 7 : inline bool empty() const
1142 : {
1143 7 : return (size() == size_type(0));
1144 : }
1145 :
1146 : /// Returns the largest possible size of the B+ Tree. This is just a
1147 : /// function required by the STL standard, the B+ Tree can hold more items.
1148 0 : inline size_type max_size() const
1149 : {
1150 0 : return size_type(-1);
1151 : }
1152 :
1153 : /// Return a const reference to the current statistics.
1154 0 : inline const struct tree_stats& get_stats() const
1155 : {
1156 0 : return stats;
1157 : }
1158 :
1159 : public:
1160 : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
1161 :
1162 : /// Non-STL function checking whether a key is in the B+ tree. The same as
1163 : /// (find(k) != end()) or (count() != 0).
1164 62708 : bool exists(const key_type &key) const
1165 : {
1166 62708 : const node *n = root;
1167 :
1168 62708 : if (!n) return false;
1169 :
1170 373026 : while(!n->isleafnode())
1171 : {
1172 247610 : const inner_node *inner = static_cast<const inner_node*>(n);
1173 247610 : int slot = find_lower(inner, key);
1174 :
1175 247610 : n = inner->childid[slot];
1176 : }
1177 :
1178 62708 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1179 :
1180 62708 : int slot = find_lower(leaf, key);
1181 62708 : return key_equal(key, leaf->slotkey[slot]);
1182 : }
1183 :
1184 : /// Tries to locate a key in the B+ tree and returns an iterator to the
1185 : /// key/data slot if found. If unsuccessful it returns end().
1186 0 : iterator find(const key_type &key)
1187 : {
1188 0 : node *n = root;
1189 0 : if (!n) return end();
1190 :
1191 0 : while(!n->isleafnode())
1192 : {
1193 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1194 0 : int slot = find_lower(inner, key);
1195 :
1196 0 : n = inner->childid[slot];
1197 : }
1198 :
1199 0 : leaf_node *leaf = static_cast<leaf_node*>(n);
1200 :
1201 0 : int slot = find_lower(leaf, key);
1202 0 : return key_equal(key, leaf->slotkey[slot]) ? iterator(leaf, slot) : end();
1203 : }
1204 :
1205 : /// Tries to locate a key in the B+ tree and returns an constant iterator
1206 : /// to the key/data slot if found. If unsuccessful it returns end().
1207 0 : const_iterator find(const key_type &key) const
1208 : {
1209 0 : const node *n = root;
1210 0 : if (!n) return end();
1211 :
1212 0 : while(!n->isleafnode())
1213 : {
1214 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1215 0 : int slot = find_lower(inner, key);
1216 :
1217 0 : n = inner->childid[slot];
1218 : }
1219 :
1220 0 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1221 :
1222 0 : int slot = find_lower(leaf, key);
1223 0 : return key_equal(key, leaf->slotkey[slot]) ? const_iterator(leaf, slot) : end();
1224 : }
1225 :
1226 : /// Tries to locate a key in the B+ tree and returns the number of
1227 : /// identical key entries found.
1228 34720 : size_type count(const key_type &key) const
1229 : {
1230 34720 : const node *n = root;
1231 34720 : if (!n) return 0;
1232 :
1233 214767 : while(!n->isleafnode())
1234 : {
1235 145327 : const inner_node *inner = static_cast<const inner_node*>(n);
1236 145327 : int slot = find_lower(inner, key);
1237 :
1238 145327 : n = inner->childid[slot];
1239 : }
1240 :
1241 34720 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1242 :
1243 34720 : int slot = find_lower(leaf, key);
1244 34720 : size_type num = 0;
1245 :
1246 3173397 : while (leaf && key_equal(key, leaf->slotkey[slot]))
1247 : {
1248 3103957 : ++num;
1249 3103957 : if (++slot >= leaf->slotuse)
1250 : {
1251 775421 : leaf = leaf->nextleaf;
1252 775421 : slot = 0;
1253 : }
1254 : }
1255 :
1256 34720 : return num;
1257 : }
1258 :
1259 : /// Searches the B+ tree and returns an iterator to the first key less or
1260 : /// equal to the parameter. If unsuccessful it returns end().
1261 2420 : iterator lower_bound(const key_type& key)
1262 : {
1263 2420 : node *n = root;
1264 2420 : if (!n) return end();
1265 :
1266 10120 : while(!n->isleafnode())
1267 : {
1268 5280 : const inner_node *inner = static_cast<const inner_node*>(n);
1269 5280 : int slot = find_lower(inner, key);
1270 :
1271 5280 : n = inner->childid[slot];
1272 : }
1273 :
1274 2420 : leaf_node *leaf = static_cast<leaf_node*>(n);
1275 :
1276 2420 : int slot = find_lower(leaf, key);
1277 2420 : return iterator(leaf, slot);
1278 : }
1279 :
1280 : /// Searches the B+ tree and returns an constant iterator to the first key less or
1281 : /// equal to the parameter. If unsuccessful it returns end().
1282 0 : const_iterator lower_bound(const key_type& key) const
1283 : {
1284 0 : const node *n = root;
1285 0 : if (!n) return end();
1286 :
1287 0 : while(!n->isleafnode())
1288 : {
1289 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1290 0 : int slot = find_lower(inner, key);
1291 :
1292 0 : n = inner->childid[slot];
1293 : }
1294 :
1295 0 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1296 :
1297 0 : int slot = find_lower(leaf, key);
1298 0 : return const_iterator(leaf, slot);
1299 : }
1300 :
1301 : /// Searches the B+ tree and returns an iterator to the first key greater
1302 : /// than the parameter. If unsuccessful it returns end().
1303 2420 : iterator upper_bound(const key_type& key)
1304 : {
1305 2420 : node *n = root;
1306 2420 : if (!n) return end();
1307 :
1308 10120 : while(!n->isleafnode())
1309 : {
1310 5280 : const inner_node *inner = static_cast<const inner_node*>(n);
1311 5280 : int slot = find_upper(inner, key);
1312 :
1313 5280 : n = inner->childid[slot];
1314 : }
1315 :
1316 2420 : leaf_node *leaf = static_cast<leaf_node*>(n);
1317 :
1318 2420 : int slot = find_upper(leaf, key);
1319 2420 : return iterator(leaf, slot);
1320 : }
1321 :
1322 : /// Searches the B+ tree and returns an constant iterator to the first key
1323 : /// greater than the parameter. If unsuccessful it returns end().
1324 0 : const_iterator upper_bound(const key_type& key) const
1325 : {
1326 0 : const node *n = root;
1327 0 : if (!n) return end();
1328 :
1329 0 : while(!n->isleafnode())
1330 : {
1331 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1332 0 : int slot = find_upper(inner, key);
1333 :
1334 0 : n = inner->childid[slot];
1335 : }
1336 :
1337 0 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1338 :
1339 0 : int slot = find_upper(leaf, key);
1340 0 : return const_iterator(leaf, slot);
1341 : }
1342 :
1343 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
1344 1210 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
1345 : {
1346 1210 : return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
1347 : }
1348 :
1349 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
1350 0 : inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1351 : {
1352 0 : return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
1353 : }
1354 :
1355 : public:
1356 : // *** B+ Tree Object Comparison Functions
1357 :
1358 : /// Equality relation of B+ trees of the same type. B+ trees of the same
1359 : /// size and equal elements (both key and data) are considered
1360 : /// equal. Beware of the random ordering of duplicate keys.
1361 5 : inline bool operator==(const btree_self &other) const
1362 : {
1363 5 : return (size() == other.size()) && std::equal(begin(), end(), other.begin());
1364 : }
1365 :
1366 : /// Inequality relation. Based on operator==.
1367 1 : inline bool operator!=(const btree_self &other) const
1368 : {
1369 1 : return !(*this == other);
1370 : }
1371 :
1372 : /// Total ordering relation of B+ trees of the same type. It uses
1373 : /// std::lexicographical_compare() for the actual comparison of elements.
1374 4 : inline bool operator<(const btree_self &other) const
1375 : {
1376 4 : return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
1377 : }
1378 :
1379 : /// Greater relation. Based on operator<.
1380 1 : inline bool operator>(const btree_self &other) const
1381 : {
1382 1 : return other < *this;
1383 : }
1384 :
1385 : /// Less-equal relation. Based on operator<.
1386 1 : inline bool operator<=(const btree_self &other) const
1387 : {
1388 1 : return !(other < *this);
1389 : }
1390 :
1391 : /// Greater-equal relation. Based on operator<.
1392 1 : inline bool operator>=(const btree_self &other) const
1393 : {
1394 1 : return !(*this < other);
1395 : }
1396 :
1397 : public:
1398 : /// *** Fast Copy: Assign Operator and Copy Constructors
1399 :
1400 : /// Assignment operator. All the key/data pairs are copied
1401 1 : inline btree_self& operator= (const btree_self &other)
1402 : {
1403 1 : if (this != &other)
1404 : {
1405 1 : clear();
1406 :
1407 1 : key_less = other.key_comp();
1408 1 : if (other.size() != 0)
1409 : {
1410 1 : stats.leaves = stats.innernodes = 0;
1411 1 : root = copy_recursive(other.root);
1412 1 : stats = other.stats;
1413 : }
1414 :
1415 1 : if (selfverify) verify();
1416 : }
1417 1 : return *this;
1418 : }
1419 :
1420 : /// Copy constructor. The newly initialized B+ tree object will contain a
1421 : /// copy of all key/data pairs.
1422 2 : inline btree(const btree_self &other)
1423 : : root(NULL), headleaf(NULL), tailleaf(NULL),
1424 : stats( other.stats ),
1425 2 : key_less( other.key_comp() )
1426 : {
1427 2 : if (size() > 0)
1428 : {
1429 2 : stats.leaves = stats.innernodes = 0;
1430 2 : root = copy_recursive(other.root);
1431 2 : if (selfverify) verify();
1432 : }
1433 : }
1434 :
1435 : private:
1436 : /// Recursively copy nodes from another B+ tree object
1437 802 : class node* copy_recursive(const node *n)
1438 : {
1439 802 : if (n->isleafnode())
1440 : {
1441 683 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1442 683 : leaf_node *newleaf = allocate_leaf();
1443 :
1444 683 : newleaf->slotuse = leaf->slotuse;
1445 683 : std::copy(leaf->slotkey, leaf->slotkey + leaf->slotuse, newleaf->slotkey);
1446 683 : std::copy(leaf->slotdata, leaf->slotdata + leaf->slotuse, newleaf->slotdata);
1447 :
1448 683 : if (headleaf == NULL)
1449 : {
1450 3 : headleaf = tailleaf = newleaf;
1451 3 : newleaf->prevleaf = newleaf->nextleaf = NULL;
1452 : }
1453 : else
1454 : {
1455 680 : newleaf->prevleaf = tailleaf;
1456 680 : tailleaf->nextleaf = newleaf;
1457 680 : tailleaf = newleaf;
1458 : }
1459 :
1460 683 : return newleaf;
1461 : }
1462 : else
1463 : {
1464 119 : const inner_node *inner = static_cast<const inner_node*>(n);
1465 119 : inner_node *newinner = allocate_inner(inner->level);
1466 :
1467 119 : newinner->slotuse = inner->slotuse;
1468 119 : std::copy(inner->slotkey, inner->slotkey + inner->slotuse, newinner->slotkey);
1469 :
1470 918 : for (unsigned short slot = 0; slot <= inner->slotuse; ++slot)
1471 : {
1472 799 : newinner->childid[slot] = copy_recursive(inner->childid[slot]);
1473 : }
1474 :
1475 119 : return newinner;
1476 : }
1477 : }
1478 :
1479 : public:
1480 : // *** Public Insertion Functions
1481 :
1482 : /// Attempt to insert a key/data pair into the B+ tree. If the tree does not
1483 : /// allow duplicate keys, then the insert may fail if it is already
1484 : /// present.
1485 : inline std::pair<iterator, bool> insert(const pair_type& x)
1486 : {
1487 : return insert_start(x.first, x.second);
1488 : }
1489 :
1490 : /// Attempt to insert a key/data pair into the B+ tree. Beware that if
1491 : /// key_type == data_type, then the template iterator insert() is called
1492 : /// instead. If the tree does not allow duplicate keys, then the insert may
1493 : /// fail if it is already present.
1494 : inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
1495 : {
1496 : return insert_start(key, data);
1497 : }
1498 :
1499 : /// Attempt to insert a key/data pair into the B+ tree. This function is the
1500 : /// same as the other insert, however if key_type == data_type then the
1501 : /// non-template function cannot be called. If the tree does not allow
1502 : /// duplicate keys, then the insert may fail if it is already present.
1503 24788 : inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
1504 : {
1505 24788 : return insert_start(key, data);
1506 : }
1507 :
1508 : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
1509 : /// is currently ignored by the B+ tree insertion routine.
1510 : inline iterator insert(iterator /* hint */, const pair_type &x)
1511 : {
1512 : return insert_start(x.first, x.second).first;
1513 : }
1514 :
1515 : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
1516 : /// currently ignored by the B+ tree insertion routine.
1517 0 : inline iterator insert2(iterator /* hint */, const key_type& key, const data_type& data)
1518 : {
1519 0 : return insert_start(key, data).first;
1520 : }
1521 :
1522 : /// Attempt to insert the range [first,last) of value_type pairs into the B+
1523 : /// tree. Each key/data pair is inserted individually.
1524 : template <typename InputIterator>
1525 : inline void insert(InputIterator first, InputIterator last)
1526 : {
1527 : InputIterator iter = first;
1528 : while(iter != last)
1529 : {
1530 : insert(*iter);
1531 : ++iter;
1532 : }
1533 : }
1534 :
1535 : private:
1536 : // *** Private Insertion Functions
1537 :
1538 : /// Start the insertion descent at the current root and handle root
1539 : /// splits. Returns true if the item was inserted
1540 24788 : std::pair<iterator, bool> insert_start(const key_type& key, const data_type& value)
1541 : {
1542 24788 : node *newchild = NULL;
1543 24788 : key_type newkey = key_type();
1544 :
1545 24788 : if (!root)
1546 : {
1547 13 : root = headleaf = tailleaf = allocate_leaf();
1548 : }
1549 :
1550 24788 : std::pair<iterator, bool> r = insert_descend(root, key, value, &newkey, &newchild);
1551 :
1552 24788 : if (newchild)
1553 : {
1554 35 : inner_node *newroot = allocate_inner(root->level + 1);
1555 35 : newroot->slotkey[0] = newkey;
1556 :
1557 35 : newroot->childid[0] = root;
1558 35 : newroot->childid[1] = newchild;
1559 :
1560 35 : newroot->slotuse = 1;
1561 :
1562 35 : root = newroot;
1563 : }
1564 :
1565 : // increment itemcount if the item was inserted
1566 24788 : if (r.second) ++stats.itemcount;
1567 :
1568 : if (debug)
1569 : print();
1570 :
1571 : if (selfverify) {
1572 24788 : verify();
1573 24788 : BTREE_ASSERT(exists(key));
1574 : }
1575 :
1576 : return r;
1577 : }
1578 :
1579 : /**
1580 : * @brief Insert an item into the B+ tree.
1581 : *
1582 : * Descend down the nodes to a leaf, insert the key/data pair in a free
1583 : * slot. If the node overflows, then it must be split and the new split
1584 : * node inserted into the parent. Unroll / this splitting up to the root.
1585 : */
1586 : std::pair<iterator, bool> insert_descend(node* n,
1587 : const key_type& key, const data_type& value,
1588 114702 : key_type* splitkey, node** splitnode)
1589 : {
1590 114702 : if (!n->isleafnode())
1591 : {
1592 89914 : inner_node *inner = static_cast<inner_node*>(n);
1593 :
1594 89914 : key_type newkey = key_type();
1595 89914 : node *newchild = NULL;
1596 :
1597 89914 : int slot = find_lower(inner, key);
1598 :
1599 : BTREE_PRINT("btree::insert_descend into " << inner->childid[slot] << std::endl);
1600 :
1601 : std::pair<iterator, bool> r = insert_descend(inner->childid[slot],
1602 89914 : key, value, &newkey, &newchild);
1603 :
1604 89914 : if (newchild)
1605 : {
1606 : BTREE_PRINT("btree::insert_descend newchild with key " << newkey << " node " << newchild << " at slot " << slot << std::endl);
1607 :
1608 6941 : if (inner->isfull())
1609 : {
1610 1250 : split_inner_node(inner, splitkey, splitnode, slot);
1611 :
1612 : BTREE_PRINT("btree::insert_descend done split_inner: putslot: " << slot << " putkey: " << newkey << " upkey: " << *splitkey << std::endl);
1613 :
1614 : if (debug)
1615 : {
1616 : print_node(inner);
1617 : print_node(*splitnode);
1618 : }
1619 :
1620 : // check if insert slot is in the split sibling node
1621 : BTREE_PRINT("btree::insert_descend switch: " << slot << " > " << inner->slotuse+1 << std::endl);
1622 :
1623 1250 : if (slot == inner->slotuse+1 && inner->slotuse < (*splitnode)->slotuse)
1624 : {
1625 : // special case when the insert slot matches the split
1626 : // place between the two nodes, then the insert key
1627 : // becomes the split key.
1628 :
1629 36 : BTREE_ASSERT(inner->slotuse + 1 < innerslotmax);
1630 :
1631 36 : inner_node *splitinner = static_cast<inner_node*>(*splitnode);
1632 :
1633 : // move the split key and it's datum into the left node
1634 36 : inner->slotkey[inner->slotuse] = *splitkey;
1635 36 : inner->childid[inner->slotuse+1] = splitinner->childid[0];
1636 36 : inner->slotuse++;
1637 :
1638 : // set new split key and move corresponding datum into right node
1639 36 : splitinner->childid[0] = newchild;
1640 36 : *splitkey = newkey;
1641 :
1642 36 : return r;
1643 : }
1644 1214 : else if (slot >= inner->slotuse+1)
1645 : {
1646 : // in case the insert slot is in the newly create split
1647 : // node, we reuse the code below.
1648 :
1649 753 : slot -= inner->slotuse+1;
1650 753 : inner = static_cast<inner_node*>(*splitnode);
1651 : BTREE_PRINT("btree::insert_descend switching to splitted node " << inner << " slot " << slot <<std::endl);
1652 : }
1653 : }
1654 :
1655 : // put pointer to child node into correct slot
1656 6905 : BTREE_ASSERT(slot >= 0 && slot <= inner->slotuse);
1657 :
1658 6905 : int i = inner->slotuse;
1659 :
1660 26025 : while(i > slot) {
1661 12215 : inner->slotkey[i] = inner->slotkey[i - 1];
1662 12215 : inner->childid[i + 1] = inner->childid[i];
1663 12215 : i--;
1664 : }
1665 :
1666 6905 : inner->slotkey[slot] = newkey;
1667 6905 : inner->childid[slot + 1] = newchild;
1668 6905 : inner->slotuse++;
1669 : }
1670 :
1671 89878 : return r;
1672 : }
1673 : else // n->isleafnode() == true
1674 : {
1675 24788 : leaf_node *leaf = static_cast<leaf_node*>(n);
1676 :
1677 24788 : int slot = find_lower(leaf, key);
1678 :
1679 0 : if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) {
1680 0 : return std::pair<iterator, bool>(iterator(leaf, slot), false);
1681 : }
1682 :
1683 24788 : if (leaf->isfull())
1684 : {
1685 5726 : split_leaf_node(leaf, splitkey, splitnode);
1686 :
1687 : // check if insert slot is in the split sibling node
1688 5726 : if (slot >= leaf->slotuse)
1689 : {
1690 2950 : slot -= leaf->slotuse;
1691 2950 : leaf = static_cast<leaf_node*>(*splitnode);
1692 : }
1693 : }
1694 :
1695 : // put data item into correct data slot
1696 :
1697 24788 : int i = leaf->slotuse - 1;
1698 24788 : BTREE_ASSERT(i + 1 < leafslotmax);
1699 :
1700 62826 : while(i >= 0 && key_less(key, leaf->slotkey[i])) {
1701 13250 : leaf->slotkey[i + 1] = leaf->slotkey[i];
1702 13250 : leaf->slotdata[i + 1] = leaf->slotdata[i];
1703 13250 : i--;
1704 : }
1705 :
1706 24788 : leaf->slotkey[i + 1] = key;
1707 24788 : leaf->slotdata[i + 1] = value;
1708 24788 : leaf->slotuse++;
1709 :
1710 24788 : if (splitnode && leaf != *splitnode && slot == leaf->slotuse-1)
1711 : {
1712 : // special case: the node was split, and the insert is at the
1713 : // last slot of the old node. then the splitkey must be
1714 : // updated.
1715 7559 : *splitkey = key;
1716 : }
1717 :
1718 24788 : return std::pair<iterator, bool>(iterator(leaf, i + 1), true);
1719 : }
1720 : }
1721 :
1722 : /// Split up a leaf node into two equally-filled sibling leaves. Returns
1723 : /// the new nodes and it's insertion key in the two parameters.
1724 5726 : void split_leaf_node(leaf_node* leaf, key_type* _newkey, node** _newleaf)
1725 : {
1726 5726 : BTREE_ASSERT(leaf->isfull());
1727 :
1728 5726 : unsigned int mid = leaf->slotuse / 2;
1729 :
1730 : BTREE_PRINT("btree::split_leaf_node on " << leaf << std::endl);
1731 :
1732 5726 : leaf_node *newleaf = allocate_leaf();
1733 :
1734 5726 : newleaf->slotuse = leaf->slotuse - mid;
1735 :
1736 5726 : newleaf->nextleaf = leaf->nextleaf;
1737 5726 : if (newleaf->nextleaf == NULL) {
1738 2567 : BTREE_ASSERT(leaf == tailleaf);
1739 2567 : tailleaf = newleaf;
1740 : }
1741 : else {
1742 3159 : newleaf->nextleaf->prevleaf = newleaf;
1743 : }
1744 :
1745 28630 : for(unsigned int slot = mid; slot < leaf->slotuse; ++slot)
1746 : {
1747 22904 : unsigned int ni = slot - mid;
1748 22904 : newleaf->slotkey[ni] = leaf->slotkey[slot];
1749 22904 : newleaf->slotdata[ni] = leaf->slotdata[slot];
1750 : }
1751 :
1752 5726 : leaf->slotuse = mid;
1753 5726 : leaf->nextleaf = newleaf;
1754 5726 : newleaf->prevleaf = leaf;
1755 :
1756 5726 : *_newkey = leaf->slotkey[leaf->slotuse-1];
1757 5726 : *_newleaf = newleaf;
1758 : }
1759 :
1760 : /// Split up an inner node into two equally-filled sibling nodes. Returns
1761 : /// the new nodes and it's insertion key in the two parameters. Requires
1762 : /// the slot of the item will be inserted, so the nodes will be the same
1763 : /// size after the insert.
1764 1250 : void split_inner_node(inner_node* inner, key_type* _newkey, node** _newinner, unsigned int addslot)
1765 : {
1766 1250 : BTREE_ASSERT(inner->isfull());
1767 :
1768 1250 : unsigned int mid = inner->slotuse / 2;
1769 :
1770 : BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot << std::endl);
1771 :
1772 : // if the split is uneven and the overflowing item will be put into the
1773 : // larger node, then the smaller split node may underflow
1774 1250 : if (addslot <= mid && mid > inner->slotuse - (mid + 1))
1775 497 : mid--;
1776 :
1777 : BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot << std::endl);
1778 :
1779 : BTREE_PRINT("btree::split_inner_node on " << inner << " into two nodes " << mid << " and " << inner->slotuse - (mid + 1) << " sized" << std::endl);
1780 :
1781 1250 : inner_node *newinner = allocate_inner(inner->level);
1782 :
1783 1250 : newinner->slotuse = inner->slotuse - (mid + 1);
1784 :
1785 5497 : for(unsigned int slot = mid + 1; slot < inner->slotuse; ++slot)
1786 : {
1787 4247 : unsigned int ni = slot - (mid + 1);
1788 4247 : newinner->slotkey[ni] = inner->slotkey[slot];
1789 4247 : newinner->childid[ni] = inner->childid[slot];
1790 : }
1791 1250 : newinner->childid[newinner->slotuse] = inner->childid[inner->slotuse];
1792 :
1793 1250 : inner->slotuse = mid;
1794 :
1795 1250 : *_newkey = inner->slotkey[mid];
1796 1250 : *_newinner = newinner;
1797 : }
1798 :
1799 : private:
1800 : // *** Support Class Encapsulating Deletion Results
1801 :
1802 : /// Result flags of recursive deletion.
1803 : enum result_flags_t
1804 : {
1805 : /// Deletion successful and no fix-ups necessary.
1806 : btree_ok = 0,
1807 :
1808 : /// Deletion not successful because key was not found.
1809 : btree_not_found = 1,
1810 :
1811 : /// Deletion successful, the last key was updated so parent slotkeys
1812 : /// need updates.
1813 : btree_update_lastkey = 2,
1814 :
1815 : /// Deletion successful, children nodes were merged and the parent
1816 : /// needs to remove the empty node.
1817 : btree_fixmerge = 4
1818 : };
1819 :
1820 : /// \internal B+ tree recursive deletion has much information which is
1821 : /// needs to be passed upward.
1822 : struct result_t
1823 : {
1824 : /// Merged result flags
1825 : result_flags_t flags;
1826 :
1827 : /// The key to be updated at the parent's slot
1828 : key_type lastkey;
1829 :
1830 : /// Constructor of a result with a specific flag, this can also be used
1831 : /// as for implicit conversion.
1832 106381 : inline result_t(result_flags_t f = btree_ok)
1833 106381 : : flags(f), lastkey()
1834 106381 : { }
1835 :
1836 : /// Constructor with a lastkey value.
1837 373 : inline result_t(result_flags_t f, const key_type &k)
1838 373 : : flags(f), lastkey(k)
1839 373 : { }
1840 :
1841 : /// Test if this result object has a given flag set.
1842 285317 : inline bool has(result_flags_t f) const
1843 : {
1844 285317 : return (flags & f);
1845 : }
1846 :
1847 : /// Merge two results OR-ing the result flags and overwriting lastkeys.
1848 6945 : inline result_t& operator|= (const result_t &other)
1849 : {
1850 6945 : flags = result_flags_t(flags | other.flags);
1851 :
1852 : // we overwrite existing lastkeys on purpose
1853 6945 : if (other.has(btree_update_lastkey))
1854 373 : lastkey = other.lastkey;
1855 :
1856 6945 : return *this;
1857 : }
1858 : };
1859 :
1860 : public:
1861 : // *** Public Erase Functions
1862 :
1863 : /// Erases one (the first) of the key/data pairs associated with the given
1864 : /// key.
1865 20944 : bool erase_one(const key_type &key)
1866 : {
1867 : BTREE_PRINT("btree::erase_one(" << key << ") on btree size " << size() << std::endl);
1868 :
1869 20944 : if (selfverify) verify();
1870 :
1871 20944 : result_t result = erase_one_descend(key, root, NULL, NULL, NULL, NULL, NULL, 0);
1872 :
1873 20944 : if (!result.has(btree_not_found))
1874 20944 : --stats.itemcount;
1875 :
1876 : if (debug) print();
1877 20944 : if (selfverify) verify();
1878 :
1879 20944 : return !result.has(btree_not_found);
1880 : }
1881 :
1882 : /// Erases all the key/data pairs associated with the given key. This is
1883 : /// implemented using erase_one().
1884 0 : size_type erase(const key_type &key)
1885 : {
1886 0 : size_type c = 0;
1887 :
1888 0 : while( erase_one(key) )
1889 : {
1890 0 : ++c;
1891 0 : if (!allow_duplicates) break;
1892 : }
1893 :
1894 0 : return c;
1895 : }
1896 :
1897 : #ifdef BTREE_TODO
1898 : /// Erase the key/data pair referenced by the iterator.
1899 : void erase(iterator iter)
1900 : {
1901 :
1902 : }
1903 : #endif
1904 :
1905 : #ifdef BTREE_TODO
1906 : /// Erase all key/data pairs in the range [first,last). This function is
1907 : /// currently not implemented by the B+ Tree.
1908 : void erase(iterator /* first */, iterator /* last */)
1909 : {
1910 : abort();
1911 : }
1912 : #endif
1913 :
1914 : private:
1915 : // *** Private Erase Functions
1916 :
1917 : /** @brief Erase one (the first) key/data pair in the B+ tree matching key.
1918 : *
1919 : * Descends down the tree in search of key. During the descent the parent,
1920 : * left and right siblings and their parents are computed and passed
1921 : * down. Once the key/data pair is found, it is removed from the leaf. If
1922 : * the leaf underflows 6 different cases are handled. These cases resolve
1923 : * the underflow by shifting key/data pairs from adjacent sibling nodes,
1924 : * merging two sibling nodes or trimming the tree.
1925 : */
1926 : result_t erase_one_descend(const key_type& key,
1927 : node *curr,
1928 : node *left, node *right,
1929 : inner_node *leftparent, inner_node *rightparent,
1930 99772 : inner_node *parent, unsigned int parentslot)
1931 : {
1932 99772 : if (curr->isleafnode())
1933 : {
1934 20944 : leaf_node *leaf = static_cast<leaf_node*>(curr);
1935 20944 : leaf_node *leftleaf = static_cast<leaf_node*>(left);
1936 20944 : leaf_node *rightleaf = static_cast<leaf_node*>(right);
1937 :
1938 20944 : int slot = find_lower(leaf, key);
1939 :
1940 20944 : if (!key_equal(key, leaf->slotkey[slot]))
1941 : {
1942 : BTREE_PRINT("Could not find key " << key << " to erase." << std::endl);
1943 :
1944 0 : return btree_not_found;
1945 : }
1946 :
1947 : BTREE_PRINT("Found key in leaf " << curr << " at slot " << slot << std::endl);
1948 :
1949 95590 : for (int i = slot; i < leaf->slotuse - 1; i++)
1950 : {
1951 74646 : leaf->slotkey[i] = leaf->slotkey[i + 1];
1952 74646 : leaf->slotdata[i] = leaf->slotdata[i + 1];
1953 : }
1954 20944 : leaf->slotuse--;
1955 :
1956 20944 : result_t myres = btree_ok;
1957 :
1958 : // if the last key of the leaf was changed, the parent is notified
1959 : // and updates the key of this leaf
1960 20944 : if (slot == leaf->slotuse)
1961 : {
1962 2846 : if (parent && parentslot < parent->slotuse)
1963 : {
1964 1269 : BTREE_ASSERT(parent->childid[parentslot] == curr);
1965 1269 : parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
1966 : }
1967 : else
1968 : {
1969 : BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1] << std::endl);
1970 308 : myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
1971 : }
1972 : }
1973 :
1974 20944 : if (leaf->isunderflow() && !(leaf == root && leaf->slotuse >= 1))
1975 : {
1976 : // determine what to do about the underflow
1977 :
1978 : // case : if this empty leaf is the root, there is no way to
1979 : // correct underflow
1980 6518 : if (leftleaf == NULL && rightleaf == NULL)
1981 : {
1982 10 : return btree_ok;
1983 : }
1984 : // case : if both left and right leaves would underflow in case of
1985 : // a shift, then merging is necessary. choose the more local merger
1986 : // with our parent
1987 6508 : else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
1988 : {
1989 4736 : if (leftparent == parent)
1990 1285 : myres |= merge_leaves(leftleaf, leaf, leftparent);
1991 : else
1992 3451 : myres |= merge_leaves(leaf, rightleaf, rightparent);
1993 : }
1994 : // case : the right leaf has extra data, so balance right with current
1995 1772 : else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
1996 : {
1997 421 : if (rightparent == parent)
1998 339 : myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
1999 : else
2000 82 : myres |= merge_leaves(leftleaf, leaf, leftparent);
2001 : }
2002 : // case : the left leaf has extra data, so balance left with current
2003 1351 : else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
2004 : {
2005 923 : if (leftparent == parent)
2006 858 : shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2007 : else
2008 65 : myres |= merge_leaves(leaf, rightleaf, rightparent);
2009 : }
2010 : // case : both the leaf and right leaves have extra data and our
2011 : // parent, choose the leaf with more data
2012 428 : else if (leftparent == rightparent)
2013 : {
2014 274 : if (leftleaf->slotuse <= rightleaf->slotuse)
2015 177 : myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2016 : else
2017 97 : shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2018 : }
2019 : else
2020 : {
2021 154 : if (leftparent == parent)
2022 88 : shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
2023 : else
2024 66 : myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
2025 : }
2026 : }
2027 :
2028 20934 : return myres;
2029 : }
2030 : else // !curr->isleafnode()
2031 : {
2032 78828 : inner_node *inner = static_cast<inner_node*>(curr);
2033 78828 : inner_node *leftinner = static_cast<inner_node*>(left);
2034 78828 : inner_node *rightinner = static_cast<inner_node*>(right);
2035 :
2036 : node *myleft, *myright;
2037 : inner_node *myleftparent, *myrightparent;
2038 :
2039 78828 : int slot = find_lower(inner, key);
2040 :
2041 78828 : if (slot == 0) {
2042 54740 : myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
2043 54740 : myleftparent = leftparent;
2044 : }
2045 : else {
2046 24088 : myleft = inner->childid[slot - 1];
2047 24088 : myleftparent = inner;
2048 : }
2049 :
2050 78828 : if (slot == inner->slotuse) {
2051 5870 : myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
2052 5870 : myrightparent = rightparent;
2053 : }
2054 : else {
2055 72958 : myright = inner->childid[slot + 1];
2056 72958 : myrightparent = inner;
2057 : }
2058 :
2059 : BTREE_PRINT("erase_one_descend into " << inner->childid[slot] << std::endl);
2060 :
2061 : result_t result = erase_one_descend(key,
2062 : inner->childid[slot],
2063 : myleft, myright,
2064 : myleftparent, myrightparent,
2065 78828 : inner, slot);
2066 :
2067 78828 : result_t myres = btree_ok;
2068 :
2069 78828 : if (result.has(btree_not_found))
2070 : {
2071 0 : return result;
2072 : }
2073 :
2074 78828 : if (result.has(btree_update_lastkey))
2075 : {
2076 617 : if (parent && parentslot < parent->slotuse)
2077 : {
2078 : BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot << std::endl);
2079 :
2080 276 : BTREE_ASSERT(parent->childid[parentslot] == curr);
2081 276 : parent->slotkey[parentslot] = result.lastkey;
2082 : }
2083 : else
2084 : {
2085 : BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey << std::endl);
2086 65 : myres |= result_t(btree_update_lastkey, result.lastkey);
2087 : }
2088 : }
2089 :
2090 78828 : if (result.has(btree_fixmerge))
2091 : {
2092 : // either the current node or the next is empty and should be removed
2093 5990 : if (inner->childid[slot]->slotuse != 0)
2094 4314 : slot++;
2095 :
2096 : // this is the child slot invalidated by the merge
2097 5990 : BTREE_ASSERT(inner->childid[slot]->slotuse == 0);
2098 :
2099 5990 : free_node(inner->childid[slot]);
2100 :
2101 29620 : for(int i = slot; i < inner->slotuse; i++)
2102 : {
2103 23630 : inner->slotkey[i - 1] = inner->slotkey[i];
2104 23630 : inner->childid[i] = inner->childid[i + 1];
2105 : }
2106 5990 : inner->slotuse--;
2107 :
2108 5990 : if (inner->level == 1)
2109 : {
2110 : // fix split key for children leaves
2111 4883 : slot--;
2112 4883 : leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]);
2113 4883 : inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
2114 : }
2115 : }
2116 :
2117 78828 : if (inner->isunderflow() && !(inner == root && inner->slotuse >= 1))
2118 : {
2119 : // case: the inner node is the root and has just one child. that child becomes the new root
2120 1661 : if (leftinner == NULL && rightinner == NULL)
2121 : {
2122 27 : BTREE_ASSERT(inner == root);
2123 27 : BTREE_ASSERT(inner->slotuse == 0);
2124 :
2125 27 : root = inner->childid[0];
2126 :
2127 27 : inner->slotuse = 0;
2128 27 : free_node(inner);
2129 :
2130 27 : return btree_ok;
2131 : }
2132 : // case : if both left and right leaves would underflow in case of
2133 : // a shift, then merging is necessary. choose the more local merger
2134 : // with our parent
2135 1634 : else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
2136 : {
2137 1095 : if (leftparent == parent)
2138 303 : myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
2139 : else
2140 792 : myres |= merge_inner(inner, rightinner, rightparent, parentslot);
2141 : }
2142 : // case : the right leaf has extra data, so balance right with current
2143 539 : else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
2144 : {
2145 96 : if (rightparent == parent)
2146 90 : shift_left_inner(inner, rightinner, rightparent, parentslot);
2147 : else
2148 6 : myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
2149 : }
2150 : // case : the left leaf has extra data, so balance left with current
2151 443 : else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
2152 : {
2153 283 : if (leftparent == parent)
2154 277 : shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2155 : else
2156 6 : myres |= merge_inner(inner, rightinner, rightparent, parentslot);
2157 : }
2158 : // case : both the leaf and right leaves have extra data and our
2159 : // parent, choose the leaf with more data
2160 160 : else if (leftparent == rightparent)
2161 : {
2162 75 : if (leftinner->slotuse <= rightinner->slotuse)
2163 44 : shift_left_inner(inner, rightinner, rightparent, parentslot);
2164 : else
2165 31 : shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2166 : }
2167 : else
2168 : {
2169 85 : if (leftparent == parent)
2170 42 : shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
2171 : else
2172 43 : shift_left_inner(inner, rightinner, rightparent, parentslot);
2173 : }
2174 : }
2175 :
2176 78801 : return myres;
2177 : }
2178 : }
2179 :
2180 : /// Merge two leaf nodes. The function moves all key/data pairs from right
2181 : /// to left and sets right's slotuse to zero. The right slot is then
2182 : /// removed by the calling parent node.
2183 4883 : result_t merge_leaves(leaf_node* left, leaf_node* right, inner_node* parent)
2184 : {
2185 : BTREE_PRINT("Merge leaf nodes " << left << " and " << right << " with common parent " << parent << "." << std::endl);
2186 : (void)parent;
2187 :
2188 4883 : BTREE_ASSERT(left->isleafnode() && right->isleafnode());
2189 4883 : BTREE_ASSERT(parent->level == 1);
2190 :
2191 4883 : BTREE_ASSERT(left->slotuse + right->slotuse < leafslotmax);
2192 :
2193 23048 : for (unsigned int i = 0; i < right->slotuse; i++)
2194 : {
2195 18165 : left->slotkey[left->slotuse + i] = right->slotkey[i];
2196 18165 : left->slotdata[left->slotuse + i] = right->slotdata[i];
2197 : }
2198 4883 : left->slotuse += right->slotuse;
2199 :
2200 4883 : left->nextleaf = right->nextleaf;
2201 4883 : if (left->nextleaf)
2202 4848 : left->nextleaf->prevleaf = left;
2203 : else
2204 35 : tailleaf = left;
2205 :
2206 4883 : right->slotuse = 0;
2207 :
2208 4883 : return btree_fixmerge;
2209 : }
2210 :
2211 : /// Merge two inner nodes. The function moves all key/childid pairs from
2212 : /// right to left and sets right's slotuse to zero. The right slot is then
2213 : /// removed by the calling parent node.
2214 1107 : static result_t merge_inner(inner_node* left, inner_node* right, inner_node* parent, unsigned int parentslot)
2215 : {
2216 : BTREE_PRINT("Merge inner nodes " << left << " and " << right << " with common parent " << parent << "." << std::endl);
2217 :
2218 1107 : BTREE_ASSERT(left->level == right->level);
2219 1107 : BTREE_ASSERT(parent->level == left->level + 1);
2220 :
2221 1107 : BTREE_ASSERT(parent->childid[parentslot] == left);
2222 :
2223 1107 : BTREE_ASSERT(left->slotuse + right->slotuse < innerslotmax);
2224 :
2225 : if (selfverify)
2226 : {
2227 : // find the left node's slot in the parent's children
2228 1107 : unsigned int leftslot = 0;
2229 2894 : while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
2230 680 : ++leftslot;
2231 :
2232 1107 : BTREE_ASSERT(leftslot < parent->slotuse);
2233 1107 : BTREE_ASSERT(parent->childid[leftslot] == left);
2234 1107 : BTREE_ASSERT(parent->childid[leftslot+1] == right);
2235 :
2236 1107 : BTREE_ASSERT(parentslot == leftslot);
2237 : }
2238 :
2239 : // retrieve the decision key from parent
2240 1107 : left->slotkey[left->slotuse] = parent->slotkey[parentslot];
2241 1107 : left->slotuse++;
2242 :
2243 : // copy over keys and children from right
2244 5226 : for (unsigned int i = 0; i < right->slotuse; i++)
2245 : {
2246 4119 : left->slotkey[left->slotuse + i] = right->slotkey[i];
2247 4119 : left->childid[left->slotuse + i] = right->childid[i];
2248 : }
2249 1107 : left->slotuse += right->slotuse;
2250 :
2251 1107 : left->childid[left->slotuse] = right->childid[right->slotuse];
2252 :
2253 1107 : right->slotuse = 0;
2254 :
2255 1107 : return btree_fixmerge;
2256 : }
2257 :
2258 : /// Balance two leaf nodes. The function moves key/data pairs from right to
2259 : /// left so that both nodes are equally filled. The parent node is updated
2260 : /// if possible.
2261 582 : static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
2262 : {
2263 582 : BTREE_ASSERT(left->isleafnode() && right->isleafnode());
2264 582 : BTREE_ASSERT(parent->level == 1);
2265 :
2266 582 : BTREE_ASSERT(left->nextleaf == right);
2267 582 : BTREE_ASSERT(left == right->prevleaf);
2268 :
2269 582 : BTREE_ASSERT(left->slotuse < right->slotuse);
2270 582 : BTREE_ASSERT(parent->childid[parentslot] == left);
2271 :
2272 582 : unsigned int shiftnum = (right->slotuse - left->slotuse) / 2;
2273 :
2274 : BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "." << std::endl);
2275 :
2276 582 : BTREE_ASSERT(left->slotuse + shiftnum < leafslotmax);
2277 :
2278 : // copy the first items from the right node to the last slot in the left node.
2279 1333 : for(unsigned int i = 0; i < shiftnum; i++)
2280 : {
2281 751 : left->slotkey[left->slotuse + i] = right->slotkey[i];
2282 751 : left->slotdata[left->slotuse + i] = right->slotdata[i];
2283 : }
2284 582 : left->slotuse += shiftnum;
2285 :
2286 : // shift all slots in the right node to the left
2287 :
2288 582 : right->slotuse -= shiftnum;
2289 3206 : for(int i = 0; i < right->slotuse; i++)
2290 : {
2291 2624 : right->slotkey[i] = right->slotkey[i + shiftnum];
2292 2624 : right->slotdata[i] = right->slotdata[i + shiftnum];
2293 : }
2294 :
2295 : // fixup parent
2296 582 : if (parentslot < parent->slotuse) {
2297 582 : parent->slotkey[parentslot] = left->slotkey[left->slotuse - 1];
2298 582 : return btree_ok;
2299 : }
2300 : else { // the update is further up the tree
2301 0 : return result_t(btree_update_lastkey, left->slotkey[left->slotuse - 1]);
2302 : }
2303 : }
2304 :
2305 : /// Balance two inner nodes. The function moves key/data pairs from right
2306 : /// to left so that both nodes are equally filled. The parent node is
2307 : /// updated if possible.
2308 177 : static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
2309 : {
2310 177 : BTREE_ASSERT(left->level == right->level);
2311 177 : BTREE_ASSERT(parent->level == left->level + 1);
2312 :
2313 177 : BTREE_ASSERT(left->slotuse < right->slotuse);
2314 177 : BTREE_ASSERT(parent->childid[parentslot] == left);
2315 :
2316 177 : unsigned int shiftnum = (right->slotuse - left->slotuse) / 2;
2317 :
2318 : BTREE_PRINT("Shifting (inner) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "." << std::endl);
2319 :
2320 177 : BTREE_ASSERT(left->slotuse + shiftnum < innerslotmax);
2321 :
2322 : if (selfverify)
2323 : {
2324 : // find the left node's slot in the parent's children and compare to parentslot
2325 :
2326 177 : unsigned int leftslot = 0;
2327 671 : while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
2328 317 : ++leftslot;
2329 :
2330 177 : BTREE_ASSERT(leftslot < parent->slotuse);
2331 177 : BTREE_ASSERT(parent->childid[leftslot] == left);
2332 177 : BTREE_ASSERT(parent->childid[leftslot+1] == right);
2333 :
2334 177 : BTREE_ASSERT(leftslot == parentslot);
2335 : }
2336 :
2337 : // copy the parent's decision slotkey and childid to the first new key on the left
2338 177 : left->slotkey[left->slotuse] = parent->slotkey[parentslot];
2339 177 : left->slotuse++;
2340 :
2341 : // copy the other items from the right node to the last slots in the left node.
2342 256 : for(unsigned int i = 0; i < shiftnum - 1; i++)
2343 : {
2344 79 : left->slotkey[left->slotuse + i] = right->slotkey[i];
2345 79 : left->childid[left->slotuse + i] = right->childid[i];
2346 : }
2347 177 : left->slotuse += shiftnum - 1;
2348 :
2349 : // fixup parent
2350 177 : parent->slotkey[parentslot] = right->slotkey[shiftnum - 1];
2351 : // last pointer in left
2352 177 : left->childid[left->slotuse] = right->childid[shiftnum - 1];
2353 :
2354 : // shift all slots in the right node
2355 :
2356 177 : right->slotuse -= shiftnum;
2357 1044 : for(int i = 0; i < right->slotuse; i++)
2358 : {
2359 867 : right->slotkey[i] = right->slotkey[i + shiftnum];
2360 867 : right->childid[i] = right->childid[i + shiftnum];
2361 : }
2362 177 : right->childid[right->slotuse] = right->childid[right->slotuse + shiftnum];
2363 : }
2364 :
2365 : /// Balance two leaf nodes. The function moves key/data pairs from left to
2366 : /// right so that both nodes are equally filled. The parent node is updated
2367 : /// if possible.
2368 1043 : static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
2369 : {
2370 1043 : BTREE_ASSERT(left->isleafnode() && right->isleafnode());
2371 1043 : BTREE_ASSERT(parent->level == 1);
2372 :
2373 1043 : BTREE_ASSERT(left->nextleaf == right);
2374 1043 : BTREE_ASSERT(left == right->prevleaf);
2375 1043 : BTREE_ASSERT(parent->childid[parentslot] == left);
2376 :
2377 1043 : BTREE_ASSERT(left->slotuse > right->slotuse);
2378 :
2379 1043 : unsigned int shiftnum = (left->slotuse - right->slotuse) / 2;
2380 :
2381 : BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "." << std::endl);
2382 :
2383 : if (selfverify)
2384 : {
2385 : // find the left node's slot in the parent's children
2386 1043 : unsigned int leftslot = 0;
2387 4835 : while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
2388 2749 : ++leftslot;
2389 :
2390 1043 : BTREE_ASSERT(leftslot < parent->slotuse);
2391 1043 : BTREE_ASSERT(parent->childid[leftslot] == left);
2392 1043 : BTREE_ASSERT(parent->childid[leftslot+1] == right);
2393 :
2394 1043 : BTREE_ASSERT(leftslot == parentslot);
2395 : }
2396 :
2397 : // shift all slots in the right node
2398 :
2399 1043 : BTREE_ASSERT(right->slotuse + shiftnum < leafslotmax);
2400 :
2401 5215 : for(int i = right->slotuse; i >= 0; i--)
2402 : {
2403 4172 : right->slotkey[i + shiftnum] = right->slotkey[i];
2404 4172 : right->slotdata[i + shiftnum] = right->slotdata[i];
2405 : }
2406 1043 : right->slotuse += shiftnum;
2407 :
2408 : // copy the last items from the left node to the first slot in the right node.
2409 2269 : for(unsigned int i = 0; i < shiftnum; i++)
2410 : {
2411 1226 : right->slotkey[i] = left->slotkey[left->slotuse - shiftnum + i];
2412 1226 : right->slotdata[i] = left->slotdata[left->slotuse - shiftnum + i];
2413 : }
2414 1043 : left->slotuse -= shiftnum;
2415 :
2416 1043 : parent->slotkey[parentslot] = left->slotkey[left->slotuse-1];
2417 : }
2418 :
2419 : /// Balance two inner nodes. The function moves key/data pairs from left to
2420 : /// right so that both nodes are equally filled. The parent node is updated
2421 : /// if possible.
2422 350 : static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
2423 : {
2424 350 : BTREE_ASSERT(left->level == right->level);
2425 350 : BTREE_ASSERT(parent->level == left->level + 1);
2426 :
2427 350 : BTREE_ASSERT(left->slotuse > right->slotuse);
2428 350 : BTREE_ASSERT(parent->childid[parentslot] == left);
2429 :
2430 350 : unsigned int shiftnum = (left->slotuse - right->slotuse) / 2;
2431 :
2432 : BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "." << std::endl);
2433 :
2434 : if (selfverify)
2435 : {
2436 : // find the left node's slot in the parent's children
2437 350 : unsigned int leftslot = 0;
2438 1465 : while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
2439 765 : ++leftslot;
2440 :
2441 350 : BTREE_ASSERT(leftslot < parent->slotuse);
2442 350 : BTREE_ASSERT(parent->childid[leftslot] == left);
2443 350 : BTREE_ASSERT(parent->childid[leftslot+1] == right);
2444 :
2445 350 : BTREE_ASSERT(leftslot == parentslot);
2446 : }
2447 :
2448 : // shift all slots in the right node
2449 :
2450 350 : BTREE_ASSERT(right->slotuse + shiftnum < innerslotmax);
2451 :
2452 350 : right->childid[right->slotuse + shiftnum] = right->childid[right->slotuse];
2453 1400 : for(int i = right->slotuse-1; i >= 0; i--)
2454 : {
2455 1050 : right->slotkey[i + shiftnum] = right->slotkey[i];
2456 1050 : right->childid[i + shiftnum] = right->childid[i];
2457 : }
2458 :
2459 350 : right->slotuse += shiftnum;
2460 :
2461 : // copy the parent's decision slotkey and childid to the last new key on the right
2462 350 : right->slotkey[shiftnum - 1] = parent->slotkey[parentslot];
2463 350 : right->childid[shiftnum - 1] = left->childid[left->slotuse];
2464 :
2465 : // copy the remaining last items from the left node to the first slot in the right node.
2466 458 : for(unsigned int i = 0; i < shiftnum - 1; i++)
2467 : {
2468 108 : right->slotkey[i] = left->slotkey[left->slotuse - shiftnum + i + 1];
2469 108 : right->childid[i] = left->childid[left->slotuse - shiftnum + i + 1];
2470 : }
2471 :
2472 : // copy the first to-be-removed key from the left node to the parent's decision slot
2473 350 : parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum];
2474 :
2475 350 : left->slotuse -= shiftnum;
2476 : }
2477 :
2478 : public:
2479 : // *** Debug Printing
2480 :
2481 : /// Print out the B+ tree structure with keys onto std::cout. This function
2482 : /// requires that the header is compiled with BTREE_PRINT and that key_type
2483 : /// is printable via std::ostream.
2484 0 : void print() const
2485 : {
2486 0 : print_node(root, 0, true);
2487 : }
2488 :
2489 : /// Print out only the leaves via the double linked list.
2490 0 : void print_leaves() const
2491 : {
2492 : BTREE_PRINT("leaves:" << std::endl);
2493 :
2494 0 : const leaf_node *n = headleaf;
2495 :
2496 0 : while(n)
2497 : {
2498 : BTREE_PRINT(" " << n << std::endl);
2499 :
2500 0 : n = n->nextleaf;
2501 : }
2502 : }
2503 :
2504 : private:
2505 :
2506 : /// Recursively descend down the tree and print out nodes.
2507 0 : static void print_node(const node* node, unsigned int depth=0, bool recursive=false)
2508 : {
2509 0 : for(unsigned int i = 0; i < depth; i++) BTREE_PRINT(" ");
2510 :
2511 : BTREE_PRINT("node " << node << " level " << node->level << " slotuse " << node->slotuse << std::endl);
2512 :
2513 0 : if (node->isleafnode())
2514 : {
2515 0 : const leaf_node *leafnode = static_cast<const leaf_node*>(node);
2516 :
2517 0 : for(unsigned int i = 0; i < depth; i++) BTREE_PRINT(" ");
2518 : BTREE_PRINT(" leaf prev " << leafnode->prevleaf << " next " << leafnode->nextleaf << std::endl);
2519 :
2520 0 : for(unsigned int i = 0; i < depth; i++) BTREE_PRINT(" ");
2521 :
2522 0 : for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
2523 : {
2524 : BTREE_PRINT(leafnode->slotkey[slot] << " "); // << "(data: " << leafnode->slotdata[slot] << ") ";
2525 : }
2526 : BTREE_PRINT(std::endl);
2527 : }
2528 : else
2529 : {
2530 0 : const inner_node *innernode = static_cast<const inner_node*>(node);
2531 :
2532 0 : for(unsigned int i = 0; i < depth; i++) BTREE_PRINT(" ");
2533 :
2534 0 : for (unsigned short slot = 0; slot < innernode->slotuse; ++slot)
2535 : {
2536 : BTREE_PRINT("(" << innernode->childid[slot] << ") " << innernode->slotkey[slot] << " ");
2537 : }
2538 : BTREE_PRINT("(" << innernode->childid[innernode->slotuse] << ")");
2539 : BTREE_PRINT(std::endl);
2540 :
2541 0 : if (recursive)
2542 : {
2543 0 : for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
2544 : {
2545 0 : print_node(innernode->childid[slot], depth + 1, recursive);
2546 : }
2547 : }
2548 : }
2549 : }
2550 :
2551 : public:
2552 : // *** Verification of B+ Tree Invariants
2553 :
2554 : /// Run a thorough verification of all B+ tree invariants. The program
2555 : /// aborts via assert() if something is wrong.
2556 66680 : void verify() const
2557 : {
2558 960 : key_type minkey, maxkey;
2559 66680 : tree_stats vstats;
2560 :
2561 66680 : if (root)
2562 : {
2563 66680 : verify_node(root, &minkey, &maxkey, vstats);
2564 :
2565 66680 : assert( vstats.itemcount == stats.itemcount );
2566 66680 : assert( vstats.leaves == stats.leaves );
2567 66680 : assert( vstats.innernodes == stats.innernodes );
2568 : }
2569 :
2570 66680 : verify_leaflinks();
2571 : }
2572 :
2573 : private:
2574 :
2575 : /// Recursively descend down the tree and verify each node
2576 61102695 : void verify_node(const node* n, key_type* minkey, key_type* maxkey, tree_stats &vstats) const
2577 : {
2578 : BTREE_PRINT("verifynode " << n << std::endl);
2579 :
2580 61102695 : if (n->isleafnode())
2581 : {
2582 49311320 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
2583 :
2584 49311320 : assert(leaf == root || !leaf->isunderflow());
2585 :
2586 201940604 : for(unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot)
2587 : {
2588 152629284 : assert(key_lessequal(leaf->slotkey[slot], leaf->slotkey[slot + 1]));
2589 : }
2590 :
2591 49311320 : *minkey = leaf->slotkey[0];
2592 49311320 : *maxkey = leaf->slotkey[leaf->slotuse - 1];
2593 :
2594 49311320 : vstats.leaves++;
2595 49311320 : vstats.itemcount += leaf->slotuse;
2596 : }
2597 : else // !n->isleafnode()
2598 : {
2599 11791375 : const inner_node *inner = static_cast<const inner_node*>(n);
2600 11791375 : vstats.innernodes++;
2601 :
2602 11791375 : assert(inner == root || !inner->isunderflow());
2603 :
2604 49244640 : for(unsigned short slot = 0; slot < inner->slotuse - 1; ++slot)
2605 : {
2606 37453265 : assert(key_lessequal(inner->slotkey[slot], inner->slotkey[slot + 1]));
2607 : }
2608 :
2609 72827390 : for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
2610 : {
2611 61036015 : const node *subnode = inner->childid[slot];
2612 61036015 : key_type subminkey = key_type();
2613 61036015 : key_type submaxkey = key_type();
2614 :
2615 61036015 : assert(subnode->level + 1 == inner->level);
2616 61036015 : verify_node(subnode, &subminkey, &submaxkey, vstats);
2617 :
2618 : BTREE_PRINT("verify subnode " << subnode << ": " << subminkey << " - " << submaxkey << std::endl);
2619 :
2620 61036015 : if (slot == 0)
2621 11791375 : *minkey = subminkey;
2622 : else
2623 49244640 : assert(key_greaterequal(subminkey, inner->slotkey[slot-1]));
2624 :
2625 61036015 : if (slot == inner->slotuse)
2626 11791375 : *maxkey = submaxkey;
2627 : else
2628 49244640 : assert(key_equal(inner->slotkey[slot], submaxkey));
2629 :
2630 61036015 : if (inner->level == 1 && slot < inner->slotuse)
2631 : {
2632 : // children are leaves and must be linked together in the
2633 : // correct order
2634 39733265 : const leaf_node *leafa = static_cast<const leaf_node*>(inner->childid[slot]);
2635 39733265 : const leaf_node *leafb = static_cast<const leaf_node*>(inner->childid[slot + 1]);
2636 :
2637 39733265 : assert(leafa->nextleaf == leafb);
2638 39733265 : assert(leafa == leafb->prevleaf);
2639 : (void)leafa; (void)leafb;
2640 : }
2641 61036015 : if (inner->level == 2 && slot < inner->slotuse)
2642 : {
2643 : // verify leaf links between the adjacent inner nodes
2644 7763973 : const inner_node *parenta = static_cast<const inner_node*>(inner->childid[slot]);
2645 7763973 : const inner_node *parentb = static_cast<const inner_node*>(inner->childid[slot+1]);
2646 :
2647 7763973 : const leaf_node *leafa = static_cast<const leaf_node*>(parenta->childid[parenta->slotuse]);
2648 7763973 : const leaf_node *leafb = static_cast<const leaf_node*>(parentb->childid[0]);
2649 :
2650 7763973 : assert(leafa->nextleaf == leafb);
2651 7763973 : assert(leafa == leafb->prevleaf);
2652 61102695 : (void)leafa; (void)leafb;
2653 : }
2654 : }
2655 : }
2656 : }
2657 :
2658 : /// Verify the double linked list of leaves.
2659 66680 : void verify_leaflinks() const
2660 : {
2661 66680 : const leaf_node *n = headleaf;
2662 :
2663 66680 : assert(n->level == 0);
2664 66680 : assert(!n || n->prevleaf == NULL);
2665 :
2666 66680 : unsigned int testcount = 0;
2667 :
2668 49444680 : while(n)
2669 : {
2670 49311320 : assert(n->level == 0);
2671 :
2672 201940604 : for(unsigned short slot = 0; slot < n->slotuse - 1; ++slot)
2673 : {
2674 152629284 : assert(key_lessequal(n->slotkey[slot], n->slotkey[slot + 1]));
2675 : }
2676 :
2677 49311320 : testcount += n->slotuse;
2678 :
2679 49311320 : if (n->nextleaf)
2680 : {
2681 49244640 : assert(key_lessequal(n->slotkey[n->slotuse-1], n->nextleaf->slotkey[0]));
2682 :
2683 49244640 : assert(n == n->nextleaf->prevleaf);
2684 : }
2685 : else
2686 : {
2687 66680 : assert(tailleaf == n);
2688 : }
2689 :
2690 49311320 : n = n->nextleaf;
2691 : }
2692 :
2693 66680 : assert(testcount == size());
2694 : }
2695 :
2696 : private:
2697 : // *** Dump and Restore of B+ Trees
2698 :
2699 : /// \internal A header for the binary image containing the base properties
2700 : /// of the B+ tree. These properties have to match the current template
2701 : /// instantiation.
2702 : struct dump_header
2703 : {
2704 : /// "stx-btree", just to stop the restore() function from loading garbage
2705 : char signature[12];
2706 :
2707 : /// Currently 0
2708 : unsigned short version;
2709 :
2710 : /// sizeof(key_type)
2711 : unsigned short key_type_size;
2712 :
2713 : /// sizeof(data_type)
2714 : unsigned short data_type_size;
2715 :
2716 : /// Number of slots in the leaves
2717 : unsigned short leafslots;
2718 :
2719 : /// Number of slots in the inner nodes
2720 : unsigned short innerslots;
2721 :
2722 : /// Allow duplicates
2723 : bool allow_duplicates;
2724 :
2725 : /// The item count of the tree
2726 : size_type itemcount;
2727 :
2728 : /// Fill the struct with the current B+ tree's properties, itemcount is
2729 : /// not filled.
2730 3 : inline void fill()
2731 : {
2732 : // don't want to include string.h just for this signature
2733 3 : *reinterpret_cast<unsigned int*>(signature+0) = 0x2d787473;
2734 3 : *reinterpret_cast<unsigned int*>(signature+4) = 0x65727462;
2735 3 : *reinterpret_cast<unsigned int*>(signature+8) = 0x00000065;
2736 :
2737 3 : version = 0;
2738 3 : key_type_size = sizeof(typename btree_self::key_type);
2739 3 : data_type_size = sizeof(typename btree_self::data_type);
2740 3 : leafslots = btree_self::leafslotmax;
2741 3 : innerslots = btree_self::innerslotmax;
2742 3 : allow_duplicates = btree_self::allow_duplicates;
2743 : }
2744 :
2745 : /// Returns true if the headers have the same vital properties
2746 2 : inline bool same(const struct dump_header &o) const
2747 : {
2748 : return (*reinterpret_cast<const unsigned int*>(signature+0) ==
2749 : *reinterpret_cast<const unsigned int*>(o.signature+0))
2750 : && (*reinterpret_cast<const unsigned int*>(signature+4) ==
2751 : *reinterpret_cast<const unsigned int*>(o.signature+4))
2752 : && (*reinterpret_cast<const unsigned int*>(signature+8) ==
2753 : *reinterpret_cast<const unsigned int*>(o.signature+8))
2754 :
2755 : && (version == o.version)
2756 : && (key_type_size == o.key_type_size)
2757 : && (data_type_size == o.data_type_size)
2758 : && (leafslots == o.leafslots)
2759 : && (innerslots == o.innerslots)
2760 2 : && (allow_duplicates == o.allow_duplicates);
2761 : }
2762 : };
2763 :
2764 : public:
2765 :
2766 : /// Dump the contents of the B+ tree out onto an ostream as a binary
2767 : /// image. The image contains memory pointers which will be fixed when the
2768 : /// image is restored. For this to work your key_type and data_type must be
2769 : /// integral types and contain no pointers or references.
2770 1 : void dump(std::ostream &os) const
2771 : {
2772 : struct dump_header header;
2773 1 : header.fill();
2774 1 : header.itemcount = size();
2775 :
2776 1 : os.write(reinterpret_cast<char*>(&header), sizeof(header));
2777 :
2778 1 : if (root)
2779 1 : dump_node(os, root);
2780 : }
2781 :
2782 : /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
2783 : /// pointers are fixed using the dump order. For dump and restore to work
2784 : /// your key_type and data_type must be integral types and contain no
2785 : /// pointers or references. Returns true if the restore was successful.
2786 2 : bool restore(std::istream &is)
2787 : {
2788 : struct dump_header fileheader;
2789 2 : is.read(reinterpret_cast<char*>(&fileheader), sizeof(fileheader));
2790 2 : if (!is.good()) return false;
2791 :
2792 : struct dump_header myheader;
2793 2 : myheader.fill();
2794 2 : myheader.itemcount = fileheader.itemcount;
2795 :
2796 2 : if (!myheader.same(fileheader))
2797 : {
2798 : BTREE_PRINT("btree::restore: file header does not match instantiation signature." << std::endl);
2799 1 : return false;
2800 : }
2801 :
2802 1 : clear();
2803 :
2804 1 : if (fileheader.itemcount > 0)
2805 : {
2806 1 : root = restore_node(is);
2807 1 : if (root == NULL) return false;
2808 :
2809 1 : stats.itemcount = fileheader.itemcount;
2810 : }
2811 :
2812 : if (debug) print();
2813 1 : if (selfverify) verify();
2814 :
2815 1 : return true;
2816 : }
2817 :
2818 : private:
2819 :
2820 : /// Recursively descend down the tree and dump each node in a precise order
2821 867 : void dump_node(std::ostream &os, const node* n) const
2822 : {
2823 : BTREE_PRINT("dump_node " << n << std::endl);
2824 :
2825 867 : if (n->isleafnode())
2826 : {
2827 734 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
2828 :
2829 734 : os.write(reinterpret_cast<const char*>(leaf), sizeof(*leaf));
2830 : }
2831 : else // !n->isleafnode()
2832 : {
2833 133 : const inner_node *inner = static_cast<const inner_node*>(n);
2834 :
2835 133 : os.write(reinterpret_cast<const char*>(inner), sizeof(*inner));
2836 :
2837 999 : for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
2838 : {
2839 866 : const node *subnode = inner->childid[slot];
2840 :
2841 1733 : dump_node(os, subnode);
2842 : }
2843 : }
2844 : }
2845 :
2846 : /// Read the dump image and construct a tree from the node order in the
2847 : /// serialization.
2848 867 : node* restore_node(std::istream &is)
2849 : {
2850 : union {
2851 : node top;
2852 : leaf_node leaf;
2853 : inner_node inner;
2854 : } nu;
2855 :
2856 : // first read only the top of the node
2857 867 : is.read(reinterpret_cast<char*>(&nu.top), sizeof(nu.top));
2858 867 : if (!is.good()) return NULL;
2859 :
2860 867 : if (nu.top.isleafnode())
2861 : {
2862 : // read remaining data of leaf node
2863 734 : is.read(reinterpret_cast<char*>(&nu.leaf) + sizeof(nu.top), sizeof(nu.leaf) - sizeof(nu.top));
2864 734 : if (!is.good()) return NULL;
2865 :
2866 734 : leaf_node *newleaf = allocate_leaf();
2867 :
2868 : // copy over all data, the leaf nodes contain only their double linked list pointers
2869 734 : *newleaf = nu.leaf;
2870 :
2871 : // reconstruct the linked list from the order in the file
2872 734 : if (headleaf == NULL) {
2873 1 : BTREE_ASSERT(newleaf->prevleaf == NULL);
2874 1 : headleaf = tailleaf = newleaf;
2875 : }
2876 : else {
2877 733 : newleaf->prevleaf = tailleaf;
2878 733 : tailleaf->nextleaf = newleaf;
2879 733 : tailleaf = newleaf;
2880 : }
2881 :
2882 734 : return newleaf;
2883 : }
2884 : else
2885 : {
2886 : // read remaining data of inner node
2887 133 : is.read(reinterpret_cast<char*>(&nu.inner) + sizeof(nu.top), sizeof(nu.inner) - sizeof(nu.top));
2888 133 : if (!is.good()) return NULL;
2889 :
2890 133 : inner_node *newinner = allocate_inner(0);
2891 :
2892 : // copy over all data, the inner nodes contain only pointers to their children
2893 133 : *newinner = nu.inner;
2894 :
2895 999 : for(unsigned short slot = 0; slot <= newinner->slotuse; ++slot)
2896 : {
2897 866 : newinner->childid[slot] = restore_node(is);
2898 : }
2899 :
2900 133 : return newinner;
2901 : }
2902 : }
2903 : };
2904 :
2905 : } // namespace stx
2906 :
2907 : #endif // _STX_BTREE_H_
|
