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