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