1 : // $Id: btree.h 37 2007-04-27 12:13:27Z tb $
2 : /** \file btree.h
3 : * Contains the main B+ tree implementation template class btree.
4 : */
5 :
6 : /*
7 : * STX B+ Tree Template Classes v0.7
8 : * Copyright (C) 2007 Timo Bingmann
9 : *
10 : * This library is free software; you can redistribute it and/or modify it
11 : * under the terms of the GNU Lesser General Public License as published by the
12 : * Free Software Foundation; either version 2.1 of the License, or (at your
13 : * option) any later version.
14 : *
15 : * This library is distributed in the hope that it will be useful, but WITHOUT
16 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
18 : * for more details.
19 : *
20 : * You should have received a copy of the GNU Lesser General Public License
21 : * along with this library; if not, write to the Free Software Foundation,
22 : * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 : */
24 :
25 : #ifndef _STX_BTREE_H_
26 : #define _STX_BTREE_H_
27 :
28 : // *** Required Headers from the STL
29 :
30 : #include <functional>
31 : #include <algorithm>
32 : #include <istream>
33 : #include <ostream>
34 : #include <assert.h>
35 :
36 : // *** Debugging Macros
37 :
38 : #ifdef BTREE_DEBUG
39 :
40 : #include <iostream>
41 :
42 : /// Print out debug information to std::cout if BTREE_DEBUG is defined.
43 : #define BTREE_PRINT(x) do { if (debug) (std::cout << x); } while(0)
44 :
45 : /// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
46 : #define BTREE_ASSERT(x) do { assert(x); } while(0)
47 :
48 : #else
49 :
50 : /// Print out debug information to std::cout if BTREE_DEBUG is defined.
51 : #define BTREE_PRINT(x) do { } while(0)
52 :
53 : /// Assertion only if BTREE_DEBUG is defined. This is not used in verify().
54 : #define BTREE_ASSERT(x) do { } while(0)
55 :
56 : #endif
57 :
58 : /// The maximum of a and b. Used in some compile-time formulas.
59 : #define BTREE_MAX(a,b) ((a) < (b) ? (b) : (a))
60 :
61 : /// STX - Some Template Extensions namespace
62 : namespace stx {
63 :
64 : /** Generates default traits for a B+ tree used as a set. It estimates leaf and
65 : * inner node sizes by assuming a cache line size of 256 bytes. */
66 : template <typename _Key>
67 : struct btree_default_set_traits
68 : {
69 : /// If true, the tree will self verify it's invariants after each insert()
70 : /// or erase(). The header must have been compiled with BTREE_DEBUG defined.
71 : static const bool selfverify = false;
72 :
73 : /// If true, the tree will print out debug information and a tree dump
74 : /// during insert() or erase() operation. The header must have been
75 : /// compiled with BTREE_DEBUG defined and key_type must be std::ostream
76 : /// printable.
77 : static const bool debug = false;
78 :
79 : /// Number of slots in each leaf of the tree. Estimated so that each node
80 : /// has a size of about 256 bytes.
81 : static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );
82 :
83 : /// Number of slots in each inner node of the tree. Estimated so that each node
84 : /// has a size of about 256 bytes.
85 : static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
86 : };
87 :
88 : /** Generates default traits for a B+ tree used as a map. It estimates leaf and
89 : * inner node sizes by assuming a cache line size of 256 bytes. */
90 : template <typename _Key, typename _Data>
91 : struct btree_default_map_traits
92 : {
93 : /// If true, the tree will self verify it's invariants after each insert()
94 : /// or erase(). The header must have been compiled with BTREE_DEBUG defined.
95 : static const bool selfverify = false;
96 :
97 : /// If true, the tree will print out debug information and a tree dump
98 : /// during insert() or erase() operation. The header must have been
99 : /// compiled with BTREE_DEBUG defined and key_type must be std::ostream
100 : /// printable.
101 : static const bool debug = false;
102 :
103 : /// Number of slots in each leaf of the tree. Estimated so that each node
104 : /// has a size of about 256 bytes.
105 : static const int leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );
106 :
107 : /// Number of slots in each inner node of the tree. Estimated so that each node
108 : /// has a size of about 256 bytes.
109 : static const int innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
110 : };
111 :
112 : /** @brief Basic class implementing a base B+ tree data structure in memory.
113 : *
114 : * The base implementation of a memory B+ tree. It is based on the
115 : * implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper
116 : * and other algorithm resources. Almost all STL-required function calls are
117 : * implemented. The asymptotic time requirements of the STL are not always
118 : * fulfilled in theory, however in practice this B+ tree performs better than a
119 : * red-black tree by using more memory. The insertion function splits the nodes
120 : * on the recursion unroll. Erase is largely based on Jannink's ideas.
121 : *
122 : * This class is specialized into btree_set, btree_multiset, btree_map and
123 : * btree_multimap using default template parameters and facade functions.
124 : */
125 : template <typename _Key, typename _Data,
126 : typename _Value = std::pair<_Key, _Data>,
127 : typename _Compare = std::less<_Key>,
128 : typename _Traits = btree_default_map_traits<_Key, _Data>,
129 : bool _Duplicates = false>
130 : class btree
131 : {
132 : public:
133 : // *** Template Parameter Types
134 :
135 : /// First template parameter: The key type of the B+ tree. This is stored
136 : /// in inner nodes and leaves
137 : typedef _Key key_type;
138 :
139 : /// Second template parameter: The data type associated with each
140 : /// key. Stored in the B+ tree's leaves
141 : typedef _Data data_type;
142 :
143 : /// Third template parameter: Composition pair of key and data types, this
144 : /// is required by the STL standard. The B+ tree does not store key and
145 : /// data together. If value_type == key_type then the B+ tree implements a
146 : /// set.
147 : typedef _Value value_type;
148 :
149 : /// Fourth template parameter: Key comparison function object
150 : typedef _Compare key_compare;
151 :
152 : /// Fifth template parameter: Traits object used to define more parameters
153 : /// of the B+ tree
154 : typedef _Traits traits;
155 :
156 : /// Sixth template parameter: Allow duplicate keys in the B+ tree. Used to
157 : /// implement multiset and multimap.
158 : static const bool allow_duplicates = _Duplicates;
159 :
160 : public:
161 : // *** Constructed Types
162 :
163 : /// Typedef of our own type
164 : typedef btree<key_type, data_type, value_type,
165 : key_compare, traits, allow_duplicates> btree_self;
166 :
167 : /// Size type used to count keys
168 : typedef size_t size_type;
169 :
170 : /// The pair of key_type and data_type, this may be different from value_type.
171 : typedef std::pair<key_type, data_type> pair_type;
172 :
173 : public:
174 : // *** Static Constant Options and Values of the B+ Tree
175 :
176 : /// Base B+ tree parameter: The number of key/data slots in each leaf
177 : static const unsigned short leafslotmax = traits::leafslots;
178 :
179 : /// Base B+ tree parameter: The number of key slots in each inner node,
180 : /// this can differ from slots in each leaf.
181 : static const unsigned short innerslotmax = traits::innerslots;
182 :
183 : /// Computed B+ tree parameter: The minimum number of key/data slots used
184 : /// in a leaf. If fewer slots are used, the leaf will be merged or slots
185 : /// shifted from it's siblings.
186 : static const unsigned short minleafslots = (leafslotmax / 2);
187 :
188 : /// Computed B+ tree parameter: The minimum number of key slots used
189 : /// in an inner node. If fewer slots are used, the inner node will be
190 : /// merged or slots shifted from it's siblings.
191 : static const unsigned short mininnerslots = (innerslotmax / 2);
192 :
193 : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
194 : /// invariants after each insert/erase operation.
195 : static const bool selfverify = traits::selfverify;
196 :
197 : /// Debug parameter: Prints out lots of debug information about how the
198 : /// algorithms change the tree. Requires the header file to be compiled
199 : /// with BTREE_PRINT and the key type must be std::ostream printable.
200 : static const bool debug = traits::debug;
201 :
202 : private:
203 : // *** Node Classes for In-Memory Nodes
204 :
205 : /// The header structure of each node in-memory. This structure is extended
206 : /// by inner_node or leaf_node.
207 : struct node
208 65 : {
209 : /// Level in the b-tree, if level == 0 -> leaf node
210 : unsigned short level;
211 :
212 : /// Number of key slotuse use, so number of valid children or data
213 : /// pointers
214 : unsigned short slotuse;
215 :
216 : /// Delayed initialisation of constructed node
217 8693 : inline void initialize(const unsigned short l)
218 : {
219 8693 : level = l;
220 8693 : slotuse = 0;
221 : }
222 :
223 : /// True if this is a leaf node
224 61849855 : inline bool isleafnode() const
225 : {
226 61849855 : return (level == 0);
227 : }
228 : };
229 :
230 : /// Extended structure of a inner node in-memory. Contains only keys and no
231 : /// data items.
232 : struct inner_node : public node
233 9 : {
234 : /// Keys of children or data pointers
235 : key_type slotkey[innerslotmax];
236 :
237 : /// Pointers to children
238 : node* childid[innerslotmax+1];
239 :
240 : /// Set variables to initial values
241 1537 : inline void initialize(const unsigned short l)
242 : {
243 1537 : node::initialize(l);
244 : }
245 :
246 : /// True if the node's slots are full
247 8191 : inline bool isfull() const
248 : {
249 8191 : return (node::slotuse == innerslotmax);
250 : }
251 :
252 : /// True if few used entries, less than half full
253 3488 : inline bool isfew() const
254 : {
255 3488 : return (node::slotuse <= mininnerslots);
256 : }
257 :
258 : /// True if node has too few entries
259 11803777 : inline bool isunderflow() const
260 : {
261 11803777 : return (node::slotuse < mininnerslots);
262 : }
263 : };
264 :
265 : /// Extended structure of a leaf node in memory. Contains pairs of keys and
266 : /// data items. Key and data slots are kept in separate arrays, because the
267 : /// key array is traversed very often compared to accessing the data items.
268 : struct leaf_node : public node
269 56 : {
270 : /// Double linked list pointers to traverse the leaves
271 : leaf_node *prevleaf;
272 :
273 : /// Double linked list pointers to traverse the leaves
274 : leaf_node *nextleaf;
275 :
276 : /// Keys of children or data pointers
277 : key_type slotkey[leafslotmax];
278 :
279 : /// Array of data
280 : data_type slotdata[leafslotmax];
281 :
282 : /// Set variables to initial values
283 7156 : inline void initialize()
284 : {
285 7156 : node::initialize(0);
286 7156 : prevleaf = nextleaf = NULL;
287 : }
288 :
289 : /// True if the node's slots are full
290 30514 : inline bool isfull() const
291 : {
292 30514 : return (node::slotuse == leafslotmax);
293 : }
294 :
295 : /// True if few used entries, less than half full
296 13759 : inline bool isfew() const
297 : {
298 13759 : return (node::slotuse <= minleafslots);
299 : }
300 :
301 : /// True if node has too few entries
302 49332010 : inline bool isunderflow() const
303 : {
304 49332010 : return (node::slotuse < minleafslots);
305 : }
306 : };
307 :
308 : private:
309 : // *** Template Magic to Convert a pair or key/data types to a value_type
310 :
311 : /// \internal For sets the second pair_type is an empty struct, so the
312 : /// value_type should only be the first.
313 : template <typename value_type, typename pair_type>
314 : struct btree_pair_to_value
315 : {
316 : /// Convert a fake pair type to just the first component
317 : inline value_type operator()(pair_type& p) const {
318 : return p.first;
319 : }
320 : /// Convert a fake pair type to just the first component
321 16316 : inline value_type operator()(const pair_type& p) const {
322 16316 : return p.first;
323 : }
324 : };
325 :
326 : /// \internal For maps value_type is the same as the pair_type
327 : template <typename value_type>
328 : struct btree_pair_to_value<value_type, value_type>
329 : {
330 : /// Identity "convert" a real pair type to just the first component
331 : inline value_type operator()(pair_type& p) const {
332 : return p;
333 : }
334 : /// Identity "convert" a real pair type to just the first component
335 0 : inline value_type operator()(const pair_type& p) const {
336 0 : return p;
337 : }
338 : };
339 :
340 : /// Using template specialization select the correct converter used by the
341 : /// iterators
342 : typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;
343 :
344 : public:
345 : // *** Iterators and Reverse Iterators
346 :
347 : class iterator;
348 : class const_iterator;
349 :
350 : /// STL-like iterator object for B+ tree items. The iterator points to a
351 : /// specific slot number in a leaf.
352 : class iterator
353 : {
354 : public:
355 : // *** Types
356 :
357 : /// The key type of the btree. Returned by key().
358 : typedef typename btree::key_type key_type;
359 :
360 : /// The data type of the btree. Returned by data().
361 : typedef typename btree::data_type data_type;
362 :
363 : /// The value type of the btree. Returned by operator*().
364 : typedef typename btree::value_type value_type;
365 :
366 : /// The pair type of the btree.
367 : typedef typename btree::pair_type pair_type;
368 :
369 : /// Reference to the value_type. Required by the reverse_iterator.
370 : typedef value_type& reference;
371 :
372 : /// Pointer to the value_type. Required by the reverse_iterator.
373 : typedef value_type* pointer;
374 :
375 : /// STL-magic iterator category
376 : typedef std::bidirectional_iterator_tag iterator_category;
377 :
378 : /// STL-magic
379 : typedef ptrdiff_t difference_type;
380 :
381 : /// Our own type
382 : typedef iterator self;
383 :
384 : private:
385 : // *** Members
386 :
387 : /// The currently referenced leaf node of the tree
388 : typename btree::leaf_node* currnode;
389 :
390 : /// Current key/data slot referenced
391 : unsigned short currslot;
392 :
393 : /// Friendly to the const_iterator, so it may access the two data items directly
394 : friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>::const_iterator;
395 :
396 : /// Evil! A temporary value_type to STL-correctly deliver operator* and
397 : /// operator->
398 : mutable value_type temp_value;
399 :
400 : public:
401 : // *** Methods
402 :
403 : /// Constructor of a mutable iterator
404 51852 : inline iterator(typename btree::leaf_node *l, unsigned short s)
405 51852 : : currnode(l), currslot(s)
406 51852 : { }
407 :
408 : /// Dereference the iterator, this is not a value_type& because key and
409 : /// value are not stored together
410 9600 : inline reference operator*() const
411 : {
412 9600 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
413 : currnode->slotdata[currslot]) );
414 9600 : return temp_value;
415 : }
416 :
417 : /// Dereference the iterator. Do not use this if possible, use key()
418 : /// and data() instead. The B+ tree does not stored key and data
419 : /// together.
420 : inline pointer operator->() const
421 : {
422 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
423 : currnode->slotdata[currslot]) );
424 : return &temp_value;
425 : }
426 :
427 : /// Key of the current slot
428 17360 : inline const key_type& key() const
429 : {
430 17360 : return currnode->slotkey[currslot];
431 : }
432 :
433 : /// Writable reference to the current data object
434 0 : inline data_type& data() const
435 : {
436 0 : return currnode->slotdata[currslot];
437 : }
438 :
439 : /// Prefix++ advance the iterator to the next slot
440 23760 : inline self& operator++()
441 : {
442 23760 : if (currslot + 1 < currnode->slotuse) {
443 18365 : ++currslot;
444 : }
445 5395 : else if (currnode->nextleaf != NULL) {
446 5387 : currnode = currnode->nextleaf;
447 5387 : currslot = 0;
448 : }
449 : else {
450 : // this is end()
451 8 : currslot = currnode->slotuse;
452 : }
453 :
454 23760 : return *this;
455 : }
456 :
457 : /// Postfix++ advance the iterator to the next slot
458 : inline self operator++(int)
459 : {
460 : self tmp = *this; // copy ourselves
461 :
462 : if (currslot + 1 < currnode->slotuse) {
463 : ++currslot;
464 : }
465 : else if (currnode->nextleaf != NULL) {
466 : currnode = currnode->nextleaf;
467 : currslot = 0;
468 : }
469 : else {
470 : // this is end()
471 : currslot = currnode->slotuse;
472 : }
473 :
474 : return tmp;
475 : }
476 :
477 : /// Prefix-- backstep the iterator to the last slot
478 16000 : inline self& operator--()
479 : {
480 16000 : if (currslot > 0) {
481 13150 : --currslot;
482 : }
483 2850 : else if (currnode->prevleaf != NULL) {
484 2850 : currnode = currnode->prevleaf;
485 2850 : currslot = currnode->slotuse - 1;
486 : }
487 : else {
488 : // this is begin()
489 0 : currslot = 0;
490 : }
491 :
492 16000 : return *this;
493 : }
494 :
495 : /// Postfix-- backstep the iterator to the last slot
496 : inline self operator--(int)
497 : {
498 : self tmp = *this; // copy ourselves
499 :
500 : if (currslot > 0) {
501 : --currslot;
502 : }
503 : else if (currnode->prevleaf != NULL) {
504 : currnode = currnode->prevleaf;
505 : currslot = currnode->slotuse - 1;
506 : }
507 : else {
508 : // this is begin()
509 : currslot = 0;
510 : }
511 :
512 : return tmp;
513 : }
514 :
515 : /// Equality of iterators
516 6410 : inline bool operator==(const self& x) const
517 : {
518 6410 : return (x.currnode == currnode) && (x.currslot == currslot);
519 : }
520 :
521 : /// Inequality of iterators
522 23768 : inline bool operator!=(const self& x) const
523 : {
524 23768 : return (x.currnode != currnode) || (x.currslot != currslot);
525 : }
526 : };
527 :
528 : /// STL-like read-only iterator object for B+ tree items. The iterator
529 : /// points to a specific slot number in a leaf.
530 : class const_iterator
531 : {
532 : public:
533 : // *** Types
534 :
535 : /// The key type of the btree. Returned by key().
536 : typedef typename btree::key_type key_type;
537 :
538 : /// The data type of the btree. Returned by data().
539 : typedef typename btree::data_type data_type;
540 :
541 : /// The value type of the btree. Returned by operator*().
542 : typedef typename btree::value_type value_type;
543 :
544 : /// The pair type of the btree.
545 : typedef typename btree::pair_type pair_type;
546 :
547 : /// Reference to the value_type. Required by the reverse_iterator.
548 : typedef const value_type& reference;
549 :
550 : /// Pointer to the value_type. Required by the reverse_iterator.
551 : typedef const value_type* pointer;
552 :
553 : /// STL-magic iterator category
554 : typedef std::bidirectional_iterator_tag iterator_category;
555 :
556 : /// STL-magic
557 : typedef ptrdiff_t difference_type;
558 :
559 : /// Our own type
560 : typedef const_iterator self;
561 :
562 : private:
563 : // *** Members
564 :
565 : /// The currently referenced leaf node of the tree
566 : const typename btree::leaf_node* currnode;
567 :
568 : /// Current key/data slot referenced
569 : unsigned short currslot;
570 :
571 : /// Evil! A temporary value_type to STL-correctly deliver operator* and
572 : /// operator->
573 : mutable value_type temp_value;
574 :
575 : public:
576 : // *** Methods
577 :
578 : /// Constructor of a const iterator
579 31 : inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
580 31 : : currnode(l), currslot(s)
581 31 : { }
582 :
583 : /// Copy-constructor from a mutable const iterator
584 9680 : inline const_iterator(const iterator &it)
585 9680 : : currnode(it.currnode), currslot(it.currslot)
586 9680 : { }
587 :
588 : /// Dereference the iterator. Do not use this if possible, use key()
589 : /// and data() instead. The B+ tree does not stored key and data
590 : /// together.
591 6716 : inline reference operator*() const
592 : {
593 6716 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
594 : currnode->slotdata[currslot]) );
595 6716 : return temp_value;
596 : }
597 :
598 : /// Dereference the iterator. Do not use this if possible, use key()
599 : /// and data() instead. The B+ tree does not stored key and data
600 : /// together.
601 : inline pointer operator->() const
602 : {
603 : temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
604 : currnode->slotdata[currslot]) );
605 : return &temp_value;
606 : }
607 :
608 : /// Key of the current slot
609 4024 : inline const key_type& key() const
610 : {
611 4024 : return currnode->slotkey[currslot];
612 : }
613 :
614 : /// Read-only reference to the current data object
615 : inline const data_type& data() const
616 : {
617 : return currnode->slotdata[currslot];
618 : }
619 :
620 : /// Prefix++ advance the iterator to the next slot
621 4796 : inline self& operator++()
622 : {
623 4796 : if (currslot + 1 < currnode->slotuse) {
624 3962 : ++currslot;
625 : }
626 834 : else if (currnode->nextleaf != NULL) {
627 822 : currnode = currnode->nextleaf;
628 822 : currslot = 0;
629 : }
630 : else {
631 : // this is end()
632 12 : currslot = currnode->slotuse;
633 : }
634 :
635 4796 : return *this;
636 : }
637 :
638 : /// Postfix++ advance the iterator to the next slot
639 : inline self operator++(int)
640 : {
641 : self tmp = *this; // copy ourselves
642 :
643 : if (currslot + 1 < currnode->slotuse) {
644 : ++currslot;
645 : }
646 : else if (currnode->nextleaf != NULL) {
647 : currnode = currnode->nextleaf;
648 : currslot = 0;
649 : }
650 : else {
651 : // this is end()
652 : currslot = currnode->slotuse;
653 : }
654 :
655 : return tmp;
656 : }
657 :
658 : /// Prefix-- backstep the iterator to the last slot
659 : inline self& operator--()
660 : {
661 : if (currslot > 0) {
662 : --currslot;
663 : }
664 : else if (currnode->prevleaf != NULL) {
665 : currnode = currnode->prevleaf;
666 : currslot = currnode->slotuse - 1;
667 : }
668 : else {
669 : // this is begin()
670 : currslot = 0;
671 : }
672 :
673 : return *this;
674 : }
675 :
676 : /// Postfix-- backstep the iterator to the last slot
677 : inline self operator--(int)
678 : {
679 : self tmp = *this; // copy ourselves
680 :
681 : if (currslot > 0) {
682 : --currslot;
683 : }
684 : else if (currnode->prevleaf != NULL) {
685 : currnode = currnode->prevleaf;
686 : currslot = currnode->slotuse - 1;
687 : }
688 : else {
689 : // this is begin()
690 : currslot = 0;
691 : }
692 :
693 : return tmp;
694 : }
695 :
696 : /// Equality of iterators
697 4842 : inline bool operator==(const self& x) const
698 : {
699 4842 : return (x.currnode == currnode) && (x.currslot == currslot);
700 : }
701 :
702 : /// Inequality of iterators
703 3367 : inline bool operator!=(const self& x) const
704 : {
705 3367 : return (x.currnode != currnode) || (x.currslot != currslot);
706 : }
707 : };
708 :
709 : /// create mutable reverse iterator by using STL magic
710 : typedef std::reverse_iterator<iterator> reverse_iterator;
711 :
712 : /// create constant reverse iterator by using STL magic
713 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
714 :
715 : public:
716 : // *** Small Statistics Structure
717 :
718 : /** A small struct containing basic statistics about the B+ tree. It can be
719 : * fetched using get_stats(). */
720 : struct tree_stats
721 : {
722 : /// Number of items in the B+ tree
723 : size_type itemcount;
724 :
725 : /// Number of leaves in the B+ tree
726 : size_type leaves;
727 :
728 : /// Number of inner nodes in the B+ tree
729 : size_type innernodes;
730 :
731 : /// Base B+ tree parameter: The number of key/data slots in each leaf
732 : static const unsigned short leafslots = btree_self::leafslotmax;
733 :
734 : /// Base B+ tree parameter: The number of key slots in each inner node.
735 : static const unsigned short innerslots = btree_self::innerslotmax;
736 :
737 : /// Zero initialized
738 66713 : inline tree_stats()
739 : : itemcount(0),
740 66713 : leaves(0), innernodes(0)
741 66713 : {
742 : }
743 :
744 : /// Return the total number of nodes
745 : inline size_type nodes() const
746 : {
747 : return innernodes + leaves;
748 : }
749 :
750 : /// Return the average fill of leaves
751 : inline double avgfill_leaves() const
752 : {
753 : return static_cast<double>(itemcount) / (leaves * leafslots);
754 : }
755 : };
756 :
757 : private:
758 : // *** Tree Object Data Members
759 :
760 : /// Pointer to the B+ tree's root node, either leaf or inner node
761 : node* root;
762 :
763 : /// Pointer to first leaf in the double linked leaf chain
764 : leaf_node *headleaf;
765 :
766 : /// Pointer to last leaf in the double linked leaf chain
767 : leaf_node *tailleaf;
768 :
769 : /// Other small statistics about the B+ tree
770 : tree_stats stats;
771 :
772 : /// Key comparison object. More comparison functions are generated from
773 : /// this < relation.
774 : key_compare key_less;
775 :
776 : public:
777 : // *** Constructors and Destructor
778 :
779 : /// Default constructor initializing an empty B+ tree with the standard key
780 : /// comparison function
781 15 : inline btree()
782 15 : : root(NULL), headleaf(NULL), tailleaf(NULL)
783 15 : {
784 : }
785 :
786 : /// Constructor initializing an empty B+ tree with a special key
787 : /// comparison object
788 1 : inline btree(const key_compare &kcf)
789 : : root(NULL), headleaf(NULL), tailleaf(NULL),
790 1 : key_less(kcf)
791 1 : {
792 : }
793 :
794 : /// Constructor initializing a B+ tree with the range [first,last)
795 : template <class InputIterator>
796 : inline btree(InputIterator first, InputIterator last)
797 : : root(NULL), headleaf(NULL), tailleaf(NULL)
798 : {
799 : insert(first, last);
800 : }
801 :
802 : /// Constructor initializing a B+ tree with the range [first,last) and a
803 : /// special key comparison object
804 : template <class InputIterator>
805 : inline btree(InputIterator first, InputIterator last, const key_compare &kcf)
806 : : root(NULL), headleaf(NULL), tailleaf(NULL),
807 : key_less(kcf)
808 : {
809 : insert(first, last);
810 : }
811 :
812 : /// Frees up all used B+ tree memory pages
813 18 : inline ~btree()
814 : {
815 18 : clear();
816 : }
817 :
818 : /// Fast swapping of two identical B+ tree objects.
819 : void swap(btree_self& from)
820 : {
821 : std::swap(root, from.root);
822 : std::swap(headleaf, from.headleaf);
823 : std::swap(tailleaf, from.tailleaf);
824 : std::swap(stats, from.stats);
825 : std::swap(key_less, from.key_less);
826 : }
827 :
828 : public:
829 : // *** Key and Value Comparison Function Objects
830 :
831 : /// Function class to compare value_type objects. Required by the STL
832 : class value_compare
833 : {
834 : protected:
835 : /// Key comparison function from the template parameter
836 : key_compare key_comp;
837 :
838 : /// Constructor called from btree::value_comp()
839 0 : inline value_compare(key_compare kc)
840 0 : : key_comp(kc)
841 0 : { }
842 :
843 : /// Friendly to the btree class so it may call the constructor
844 : friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>;
845 :
846 : public:
847 : /// Function call "less"-operator resulting in true if x < y.
848 : inline bool operator()(const value_type& x, const value_type& y) const
849 : {
850 : return key_comp(x.first, y.first);
851 : }
852 : };
853 :
854 : /// Constant access to the key comparison object sorting the B+ tree
855 3 : inline key_compare key_comp() const
856 : {
857 3 : return key_less;
858 : }
859 :
860 : /// Constant access to a constructed value_type comparison object. Required
861 : /// by the STL
862 0 : inline value_compare value_comp() const
863 : {
864 0 : return value_compare(key_less);
865 : }
866 :
867 : private:
868 : // *** Convenient Key Comparison Functions Generated From key_less
869 :
870 : /// True if a <= b ? constructed from key_less()
871 395638602 : inline bool key_lessequal(const key_type &a, const key_type b) const
872 : {
873 395638602 : return !key_less(b, a);
874 : }
875 :
876 : /// True if a > b ? constructed from key_less()
877 : inline bool key_greater(const key_type &a, const key_type &b) const
878 : {
879 : return key_less(b, a);
880 : }
881 :
882 : /// True if a >= b ? constructed from key_less()
883 49244640 : inline bool key_greaterequal(const key_type &a, const key_type b) const
884 : {
885 49244640 : return !key_less(a, b);
886 : }
887 :
888 : /// True if a == b ? constructed from key_less(). This requires the <
889 : /// relation to be a total order, otherwise the B+ tree cannot be sorted.
890 52455581 : inline bool key_equal(const key_type &a, const key_type &b) const
891 : {
892 52455581 : return !key_less(a, b) && !key_less(b, a);
893 : }
894 :
895 : private:
896 : // *** Node Object Allocation and Deallocation Functions
897 :
898 : /// Allocate and initialize a leaf node
899 7156 : inline leaf_node* allocate_leaf()
900 : {
901 7156 : leaf_node* n = new leaf_node;
902 7156 : n->initialize();
903 7156 : stats.leaves++;
904 7156 : return n;
905 : }
906 :
907 : /// Allocate and initialize an inner node
908 1537 : inline inner_node* allocate_inner(unsigned short l)
909 : {
910 1537 : inner_node* n = new inner_node;
911 1537 : n->initialize(l);
912 1537 : stats.innernodes++;
913 1537 : return n;
914 : }
915 :
916 : /// Correctly free either inner or leaf node, destructs all contained key
917 : /// and value objects
918 8693 : inline void free_node(node *n)
919 : {
920 8693 : if (n->isleafnode()) {
921 7156 : delete static_cast<leaf_node*>(n);
922 7156 : stats.leaves--;
923 : }
924 : else {
925 1537 : delete static_cast<inner_node*>(n);
926 1537 : stats.innernodes--;
927 : }
928 : }
929 :
930 : public:
931 : // *** Fast Destruction of the B+ Tree
932 :
933 : /// Frees all key/data pairs and all nodes of the tree
934 20 : void clear()
935 : {
936 20 : if (root)
937 : {
938 17 : clear_recursive(root);
939 17 : free_node(root);
940 :
941 17 : root = NULL;
942 17 : headleaf = tailleaf = NULL;
943 :
944 17 : stats = tree_stats();
945 : }
946 :
947 20 : BTREE_ASSERT(stats.itemcount == 0);
948 : }
949 :
950 : private:
951 : /// Recursively free up nodes
952 2676 : void clear_recursive(node *n)
953 : {
954 2676 : if (n->isleafnode())
955 : {
956 2273 : leaf_node *leafnode = static_cast<leaf_node*>(n);
957 :
958 2273 : for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
959 : {
960 : // data objects are deleted by leaf_node's destructor
961 : }
962 : }
963 : else
964 : {
965 403 : inner_node *innernode = static_cast<inner_node*>(n);
966 :
967 3062 : for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
968 : {
969 2659 : clear_recursive(innernode->childid[slot]);
970 5335 : free_node(innernode->childid[slot]);
971 : }
972 : }
973 : }
974 :
975 : public:
976 : // *** STL Iterator Construction Functions
977 :
978 : /// Constructs a read/data-write iterator that points to the first slot in
979 : /// the first leaf of the B+ tree.
980 9 : inline iterator begin()
981 : {
982 9 : return iterator(headleaf, 0);
983 : }
984 :
985 : /// Constructs a read/data-write iterator that points to the first invalid
986 : /// slot in the last leaf of the B+ tree.
987 22215 : inline iterator end()
988 : {
989 22215 : return iterator(tailleaf, tailleaf->slotuse);
990 : }
991 :
992 : /// Constructs a read-only constant iterator that points to the first slot
993 : /// in the first leaf of the B+ tree.
994 18 : inline const_iterator begin() const
995 : {
996 18 : return const_iterator(headleaf, 0);
997 : }
998 :
999 : /// Constructs a read-only constant iterator that points to the first
1000 : /// invalid slot in the last leaf of the B+ tree.
1001 13 : inline const_iterator end() const
1002 : {
1003 13 : return const_iterator(tailleaf, tailleaf->slotuse);
1004 : }
1005 :
1006 : /// Constructs a read/data-write reverse iterator that points to the first
1007 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
1008 2 : inline reverse_iterator rbegin()
1009 : {
1010 2 : return reverse_iterator(end());
1011 : }
1012 :
1013 : /// Constructs a read/data-write reverse iterator that points to the first
1014 : /// slot in the first leaf of the B+ tree. Uses STL magic.
1015 2 : inline reverse_iterator rend()
1016 : {
1017 2 : return reverse_iterator(begin());
1018 : }
1019 :
1020 : /// Constructs a read-only reverse iterator that points to the first
1021 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
1022 0 : inline const_reverse_iterator rbegin() const
1023 : {
1024 0 : return const_reverse_iterator(end());
1025 : }
1026 :
1027 : /// Constructs a read-only reverse iterator that points to the first slot
1028 : /// in the first leaf of the B+ tree. Uses STL magic.
1029 0 : inline const_reverse_iterator rend() const
1030 : {
1031 0 : return const_reverse_iterator(begin());
1032 : }
1033 :
1034 : private:
1035 : // *** B+ Tree Node Binary Search Functions
1036 :
1037 : /// Searches for the first key in the node n less or equal to key. Uses
1038 : /// binary search with an optional linear self-verification. This is a
1039 : /// template function, because the slotkey array is located at different
1040 : /// places in leaf_node and inner_node.
1041 : template <typename node_type>
1042 712539 : inline int find_lower(const node_type *n, const key_type& key) const
1043 : {
1044 712539 : if (n->slotuse == 0) return 0;
1045 :
1046 712526 : int lo = 0,
1047 712526 : hi = n->slotuse - 1;
1048 :
1049 2655710 : while(lo < hi)
1050 : {
1051 1230658 : int mid = (lo + hi) / 2;
1052 :
1053 1230658 : if (key_lessequal(key, n->slotkey[mid])) {
1054 573768 : hi = mid - 1;
1055 : }
1056 : else {
1057 656890 : lo = mid + 1;
1058 : }
1059 : }
1060 :
1061 712526 : if (hi < 0 || key_less(n->slotkey[hi], key))
1062 422444 : hi++;
1063 :
1064 : BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
1065 :
1066 : // verify result using simple linear search
1067 : if (selfverify)
1068 : {
1069 712526 : int i = n->slotuse - 1;
1070 3399314 : while(i >= 0 && key_lessequal(key, n->slotkey[i]))
1071 1974262 : i--;
1072 712526 : i++;
1073 :
1074 : BTREE_PRINT("testfind: " << i << std::endl);
1075 712526 : BTREE_ASSERT(i == hi);
1076 : }
1077 : else {
1078 : BTREE_PRINT(std::endl);
1079 : }
1080 :
1081 712526 : return hi;
1082 : }
1083 :
1084 : /// Searches for the first key in the node n greater than key. Uses binary
1085 : /// search with an optional linear self-verification. This is a template
1086 : /// function, because the slotkey array is located at different places in
1087 : /// leaf_node and inner_node.
1088 : template <typename node_type>
1089 7700 : inline int find_upper(const node_type *n, const key_type& key) const
1090 : {
1091 7700 : if (n->slotuse == 0) return 0;
1092 :
1093 7700 : int lo = 0,
1094 7700 : hi = n->slotuse - 1;
1095 :
1096 30732 : while(lo < hi)
1097 : {
1098 15332 : int mid = (lo + hi) / 2;
1099 :
1100 15332 : if (key_less(key, n->slotkey[mid])) {
1101 6026 : hi = mid - 1;
1102 : }
1103 : else {
1104 9306 : lo = mid + 1;
1105 : }
1106 : }
1107 :
1108 7700 : if (hi < 0 || key_lessequal(n->slotkey[hi], key))
1109 4748 : hi++;
1110 :
1111 : BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
1112 :
1113 : // verify result using simple linear search
1114 : if (selfverify)
1115 : {
1116 7700 : int i = n->slotuse - 1;
1117 36122 : while(i >= 0 && key_less(key, n->slotkey[i]))
1118 20722 : i--;
1119 7700 : i++;
1120 :
1121 : BTREE_PRINT("btree::find_upper testfind: " << i << std::endl);
1122 7700 : BTREE_ASSERT(i == hi);
1123 : }
1124 : else {
1125 : BTREE_PRINT(std::endl);
1126 : }
1127 :
1128 7700 : return hi;
1129 : }
1130 :
1131 : public:
1132 : // *** Access Functions to the Item Count
1133 :
1134 : /// Return the number of key/data pairs in the B+ tree
1135 144086 : inline size_type size() const
1136 : {
1137 144086 : return stats.itemcount;
1138 : }
1139 :
1140 : /// Returns true if there is at least one key/data pair in the B+ tree
1141 7 : inline bool empty() const
1142 : {
1143 7 : return (size() == size_type(0));
1144 : }
1145 :
1146 : /// Returns the largest possible size of the B+ Tree. This is just a
1147 : /// function required by the STL standard, the B+ Tree can hold more items.
1148 0 : inline size_type max_size() const
1149 : {
1150 0 : return size_type(-1);
1151 : }
1152 :
1153 : /// Return a const reference to the current statistics.
1154 0 : inline const struct tree_stats& get_stats() const
1155 : {
1156 0 : return stats;
1157 : }
1158 :
1159 : public:
1160 : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
1161 :
1162 : /// Non-STL function checking whether a key is in the B+ tree. The same as
1163 : /// (find(k) != end()) or (count() != 0).
1164 62708 : bool exists(const key_type &key) const
1165 : {
1166 62708 : const node *n = root;
1167 :
1168 62708 : if (!n) return false;
1169 :
1170 373026 : while(!n->isleafnode())
1171 : {
1172 247610 : const inner_node *inner = static_cast<const inner_node*>(n);
1173 247610 : int slot = find_lower(inner, key);
1174 :
1175 247610 : n = inner->childid[slot];
1176 : }
1177 :
1178 62708 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1179 :
1180 62708 : int slot = find_lower(leaf, key);
1181 62708 : return key_equal(key, leaf->slotkey[slot]);
1182 : }
1183 :
1184 : /// Tries to locate a key in the B+ tree and returns an iterator to the
1185 : /// key/data slot if found. If unsuccessful it returns end().
1186 0 : iterator find(const key_type &key)
1187 : {
1188 0 : node *n = root;
1189 0 : if (!n) return end();
1190 :
1191 0 : while(!n->isleafnode())
1192 : {
1193 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1194 0 : int slot = find_lower(inner, key);
1195 :
1196 0 : n = inner->childid[slot];
1197 : }
1198 :
1199 0 : leaf_node *leaf = static_cast<leaf_node*>(n);
1200 :
1201 0 : int slot = find_lower(leaf, key);
1202 0 : return key_equal(key, leaf->slotkey[slot]) ? iterator(leaf, slot) : end();
1203 : }
1204 :
1205 : /// Tries to locate a key in the B+ tree and returns an constant iterator
1206 : /// to the key/data slot if found. If unsuccessful it returns end().
1207 0 : const_iterator find(const key_type &key) const
1208 : {
1209 0 : const node *n = root;
1210 0 : if (!n) return end();
1211 :
1212 0 : while(!n->isleafnode())
1213 : {
1214 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1215 0 : int slot = find_lower(inner, key);
1216 :
1217 0 : n = inner->childid[slot];
1218 : }
1219 :
1220 0 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1221 :
1222 0 : int slot = find_lower(leaf, key);
1223 0 : return key_equal(key, leaf->slotkey[slot]) ? const_iterator(leaf, slot) : end();
1224 : }
1225 :
1226 : /// Tries to locate a key in the B+ tree and returns the number of
1227 : /// identical key entries found.
1228 34720 : size_type count(const key_type &key) const
1229 : {
1230 34720 : const node *n = root;
1231 34720 : if (!n) return 0;
1232 :
1233 214767 : while(!n->isleafnode())
1234 : {
1235 145327 : const inner_node *inner = static_cast<const inner_node*>(n);
1236 145327 : int slot = find_lower(inner, key);
1237 :
1238 145327 : n = inner->childid[slot];
1239 : }
1240 :
1241 34720 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1242 :
1243 34720 : int slot = find_lower(leaf, key);
1244 34720 : size_type num = 0;
1245 :
1246 3173397 : while (leaf && key_equal(key, leaf->slotkey[slot]))
1247 : {
1248 3103957 : ++num;
1249 3103957 : if (++slot >= leaf->slotuse)
1250 : {
1251 775421 : leaf = leaf->nextleaf;
1252 775421 : slot = 0;
1253 : }
1254 : }
1255 :
1256 34720 : return num;
1257 : }
1258 :
1259 : /// Searches the B+ tree and returns an iterator to the first key less or
1260 : /// equal to the parameter. If unsuccessful it returns end().
1261 2420 : iterator lower_bound(const key_type& key)
1262 : {
1263 2420 : node *n = root;
1264 2420 : if (!n) return end();
1265 :
1266 10120 : while(!n->isleafnode())
1267 : {
1268 5280 : const inner_node *inner = static_cast<const inner_node*>(n);
1269 5280 : int slot = find_lower(inner, key);
1270 :
1271 5280 : n = inner->childid[slot];
1272 : }
1273 :
1274 2420 : leaf_node *leaf = static_cast<leaf_node*>(n);
1275 :
1276 2420 : int slot = find_lower(leaf, key);
1277 2420 : return iterator(leaf, slot);
1278 : }
1279 :
1280 : /// Searches the B+ tree and returns an constant iterator to the first key less or
1281 : /// equal to the parameter. If unsuccessful it returns end().
1282 0 : const_iterator lower_bound(const key_type& key) const
1283 : {
1284 0 : const node *n = root;
1285 0 : if (!n) return end();
1286 :
1287 0 : while(!n->isleafnode())
1288 : {
1289 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1290 0 : int slot = find_lower(inner, key);
1291 :
1292 0 : n = inner->childid[slot];
1293 : }
1294 :
1295 0 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1296 :
1297 0 : int slot = find_lower(leaf, key);
1298 0 : return const_iterator(leaf, slot);
1299 : }
1300 :
1301 : /// Searches the B+ tree and returns an iterator to the first key greater
1302 : /// than the parameter. If unsuccessful it returns end().
1303 2420 : iterator upper_bound(const key_type& key)
1304 : {
1305 2420 : node *n = root;
1306 2420 : if (!n) return end();
1307 :
1308 10120 : while(!n->isleafnode())
1309 : {
1310 5280 : const inner_node *inner = static_cast<const inner_node*>(n);
1311 5280 : int slot = find_upper(inner, key);
1312 :
1313 5280 : n = inner->childid[slot];
1314 : }
1315 :
1316 2420 : leaf_node *leaf = static_cast<leaf_node*>(n);
1317 :
1318 2420 : int slot = find_upper(leaf, key);
1319 2420 : return iterator(leaf, slot);
1320 : }
1321 :
1322 : /// Searches the B+ tree and returns an constant iterator to the first key
1323 : /// greater than the parameter. If unsuccessful it returns end().
1324 0 : const_iterator upper_bound(const key_type& key) const
1325 : {
1326 0 : const node *n = root;
1327 0 : if (!n) return end();
1328 :
1329 0 : while(!n->isleafnode())
1330 : {
1331 0 : const inner_node *inner = static_cast<const inner_node*>(n);
1332 0 : int slot = find_upper(inner, key);
1333 :
1334 0 : n = inner->childid[slot];
1335 : }
1336 :
1337 0 : const leaf_node *leaf = static_cast<const leaf_node*>(n);
1338 :
1339 0 : int slot = find_upper(leaf, key);
1340 0 : return const_iterator(leaf, slot);
1341 : }
1342 :
1343 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
1344 1210 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
1345 : {
1346 1210 : return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
1347 : }
1348 :
1349 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
1350 0 : inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1351 : {
1352 0 : return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
1353 : }
1354 :
1355 : public:
1356 : // *** B+ Tree Object Comparison Functions
1357 :
1358 : /// Equality relation of B+ trees of the same type. B+ trees of the same
1359 : /// size and equal elements (both key and data) are considered
1360 : /// equal. Beware of the random ordering of duplicate keys.
1361 5 : inline bool operator==(const btree_self &other) const
1362 : {
1363 |
