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