Branch data Line data Source code
1 : : // $Id: btree_map.h 128 2011-05-18 07:23:35Z tb $
2 : : /** \file btree_map.h
3 : : * Contains the specialized B+ tree template class btree_map
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_MAP_H_
26 : : #define _STX_BTREE_MAP_H_
27 : :
28 : : #include <stx/btree.h>
29 : :
30 : : namespace stx {
31 : :
32 : : /** @brief Specialized B+ tree template class implementing STL's map container.
33 : : *
34 : : * Implements the STL map using a B+ tree. It can be used as a drop-in
35 : : * replacement for std::map. Not all asymptotic time requirements are met in
36 : : * theory. The class has a traits class defining B+ tree properties like slots
37 : : * and self-verification. Furthermore an allocator can be specified for tree
38 : : * nodes.
39 : : *
40 : : * Most noteworthy difference to the default red-black implementation of
41 : : * std::map is that the B+ tree does not hold key and data pair together in
42 : : * memory. Instead each B+ tree node has two arrays of keys and data
43 : : * values. This design directly generates many problems in implementing the
44 : : * iterator's operator's which return value_type composition pairs.
45 : : */
46 : : template <typename _Key, typename _Data,
47 : : typename _Compare = std::less<_Key>,
48 : : typename _Traits = btree_default_map_traits<_Key, _Data>,
49 : : typename _Alloc = std::allocator<std::pair<_Key, _Data> > >
50 : : class btree_map
51 : : {
52 : : public:
53 : : // *** Template Parameter Types
54 : :
55 : : /// First template parameter: The key type of the btree. This is stored in
56 : : /// inner nodes and leaves
57 : : typedef _Key key_type;
58 : :
59 : : /// Second template parameter: The data type associated with each
60 : : /// key. Stored in the B+ tree's leaves
61 : : typedef _Data data_type;
62 : :
63 : : /// Third template parameter: Key comparison function object
64 : : typedef _Compare key_compare;
65 : :
66 : : /// Fourth template parameter: Traits object used to define more parameters
67 : : /// of the B+ tree
68 : : typedef _Traits traits;
69 : :
70 : : /// Fifth template parameter: STL allocator
71 : : typedef _Alloc allocator_type;
72 : :
73 : : // The macro BTREE_FRIENDS can be used by outside class to access the B+
74 : : // tree internals. This was added for wxBTreeDemo to be able to draw the
75 : : // tree.
76 : : BTREE_FRIENDS
77 : :
78 : : public:
79 : : // *** Constructed Types
80 : :
81 : : /// Typedef of our own type
82 : : typedef btree_map<key_type, data_type, key_compare, traits, allocator_type> self;
83 : :
84 : : /// Construct the STL-required value_type as a composition pair of key and
85 : : /// data types
86 : : typedef std::pair<key_type, data_type> value_type;
87 : :
88 : : /// Implementation type of the btree_base
89 : : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false, allocator_type> btree_impl;
90 : :
91 : : /// Function class comparing two value_type pairs.
92 : : typedef typename btree_impl::value_compare value_compare;
93 : :
94 : : /// Size type used to count keys
95 : : typedef typename btree_impl::size_type size_type;
96 : :
97 : : /// Small structure containing statistics about the tree
98 : : typedef typename btree_impl::tree_stats tree_stats;
99 : :
100 : : public:
101 : : // *** Static Constant Options and Values of the B+ Tree
102 : :
103 : : /// Base B+ tree parameter: The number of key/data slots in each leaf
104 : : static const unsigned short leafslotmax = btree_impl::leafslotmax;
105 : :
106 : : /// Base B+ tree parameter: The number of key slots in each inner node,
107 : : /// this can differ from slots in each leaf.
108 : : static const unsigned short innerslotmax = btree_impl::innerslotmax;
109 : :
110 : : /// Computed B+ tree parameter: The minimum number of key/data slots used
111 : : /// in a leaf. If fewer slots are used, the leaf will be merged or slots
112 : : /// shifted from it's siblings.
113 : : static const unsigned short minleafslots = btree_impl::minleafslots;
114 : :
115 : : /// Computed B+ tree parameter: The minimum number of key slots used
116 : : /// in an inner node. If fewer slots are used, the inner node will be
117 : : /// merged or slots shifted from it's siblings.
118 : : static const unsigned short mininnerslots = btree_impl::mininnerslots;
119 : :
120 : : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
121 : : /// invariants after each insert/erase operation.
122 : : static const bool selfverify = btree_impl::selfverify;
123 : :
124 : : /// Debug parameter: Prints out lots of debug information about how the
125 : : /// algorithms change the tree. Requires the header file to be compiled
126 : : /// with BTREE_DEBUG and the key type must be std::ostream printable.
127 : : static const bool debug = btree_impl::debug;
128 : :
129 : : /// Operational parameter: Allow duplicate keys in the btree.
130 : : static const bool allow_duplicates = btree_impl::allow_duplicates;
131 : :
132 : : public:
133 : : // *** Iterators and Reverse Iterators
134 : :
135 : : /// STL-like iterator object for B+ tree items. The iterator points to a
136 : : /// specific slot number in a leaf.
137 : : typedef typename btree_impl::iterator iterator;
138 : :
139 : : /// STL-like iterator object for B+ tree items. The iterator points to a
140 : : /// specific slot number in a leaf.
141 : : typedef typename btree_impl::const_iterator const_iterator;
142 : :
143 : : /// create mutable reverse iterator by using STL magic
144 : : typedef typename btree_impl::reverse_iterator reverse_iterator;
145 : :
146 : : /// create constant reverse iterator by using STL magic
147 : : typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
148 : :
149 : : private:
150 : : // *** Tree Implementation Object
151 : :
152 : : /// The contained implementation object
153 : : btree_impl tree;
154 : :
155 : : public:
156 : : // *** Constructors and Destructor
157 : :
158 : : /// Default constructor initializing an empty B+ tree with the standard key
159 : : /// comparison function
160 : 2 : explicit inline btree_map(const allocator_type &alloc = allocator_type())
161 : 2 : : tree(alloc)
162 : : {
163 : 2 : }
164 : :
165 : : /// Constructor initializing an empty B+ tree with a special key
166 : : /// comparison object
167 : 0 : explicit inline btree_map(const key_compare &kcf,
168 : : const allocator_type &alloc = allocator_type())
169 : 0 : : tree(kcf, alloc)
170 : : {
171 : 0 : }
172 : :
173 : : /// Constructor initializing a B+ tree with the range [first,last)
174 : : template <class InputIterator>
175 : : inline btree_map(InputIterator first, InputIterator last,
176 : : const allocator_type &alloc = allocator_type())
177 : : : tree(first, last, alloc)
178 : : {
179 : : }
180 : :
181 : : /// Constructor initializing a B+ tree with the range [first,last) and a
182 : : /// special key comparison object
183 : : template <class InputIterator>
184 : : inline btree_map(InputIterator first, InputIterator last, const key_compare &kcf,
185 : : const allocator_type &alloc = allocator_type())
186 : : : tree(first, last, kcf, alloc)
187 : : {
188 : : }
189 : :
190 : : /// Frees up all used B+ tree memory pages
191 : 2 : inline ~btree_map()
192 : 2 : {
193 : 2 : }
194 : :
195 : : /// Fast swapping of two identical B+ tree objects.
196 : 0 : void swap(self& from)
197 : : {
198 : 0 : std::swap(tree, from.tree);
199 : 0 : }
200 : :
201 : : public:
202 : : // *** Key and Value Comparison Function Objects
203 : :
204 : : /// Constant access to the key comparison object sorting the B+ tree
205 : 0 : inline key_compare key_comp() const
206 : : {
207 : 0 : return tree.key_comp();
208 : : }
209 : :
210 : : /// Constant access to a constructed value_type comparison object. required
211 : : /// by the STL
212 : 0 : inline value_compare value_comp() const
213 : : {
214 : 0 : return tree.value_comp();
215 : : }
216 : :
217 : : public:
218 : : // *** Allocators
219 : :
220 : : /// Return the base node allocator provided during construction.
221 : 0 : allocator_type get_allocator() const
222 : : {
223 : 0 : return tree.get_allocator();
224 : : }
225 : :
226 : : public:
227 : : // *** Fast Destruction of the B+ Tree
228 : :
229 : : /// Frees all key/data pairs and all nodes of the tree
230 : 0 : void clear()
231 : : {
232 : 0 : tree.clear();
233 : 0 : }
234 : :
235 : : public:
236 : : // *** STL Iterator Construction Functions
237 : :
238 : : /// Constructs a read/data-write iterator that points to the first slot in
239 : : /// the first leaf of the B+ tree.
240 : 4004 : inline iterator begin()
241 : : {
242 : 4004 : return tree.begin();
243 : : }
244 : :
245 : : /// Constructs a read/data-write iterator that points to the first invalid
246 : : /// slot in the last leaf of the B+ tree.
247 : 103998 : inline iterator end()
248 : : {
249 : 103998 : return tree.end();
250 : : }
251 : :
252 : : /// Constructs a read-only constant iterator that points to the first slot
253 : : /// in the first leaf of the B+ tree.
254 : 0 : inline const_iterator begin() const
255 : : {
256 : 0 : return tree.begin();
257 : : }
258 : :
259 : : /// Constructs a read-only constant iterator that points to the first
260 : : /// invalid slot in the last leaf of the B+ tree.
261 : 0 : inline const_iterator end() const
262 : : {
263 : 0 : return tree.end();
264 : : }
265 : :
266 : : /// Constructs a read/data-write reverse iterator that points to the first
267 : : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
268 : 4004 : inline reverse_iterator rbegin()
269 : : {
270 : 4004 : return tree.rbegin();
271 : : }
272 : :
273 : : /// Constructs a read/data-write reverse iterator that points to the first
274 : : /// slot in the first leaf of the B+ tree. Uses STL magic.
275 : 4008 : inline reverse_iterator rend()
276 : : {
277 : 4008 : return tree.rend();
278 : : }
279 : :
280 : : /// Constructs a read-only reverse iterator that points to the first
281 : : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
282 : 0 : inline const_reverse_iterator rbegin() const
283 : : {
284 : 0 : return tree.rbegin();
285 : : }
286 : :
287 : : /// Constructs a read-only reverse iterator that points to the first slot
288 : : /// in the first leaf of the B+ tree. Uses STL magic.
289 : 0 : inline const_reverse_iterator rend() const
290 : : {
291 : 0 : return tree.rend();
292 : : }
293 : :
294 : : public:
295 : : // *** Access Functions to the Item Count
296 : :
297 : : /// Return the number of key/data pairs in the B+ tree
298 : 1 : inline size_type size() const
299 : : {
300 : 1 : return tree.size();
301 : : }
302 : :
303 : : /// Returns true if there is at least one key/data pair in the B+ tree
304 : 0 : inline bool empty() const
305 : : {
306 : 0 : return tree.empty();
307 : : }
308 : :
309 : : /// Returns the largest possible size of the B+ Tree. This is just a
310 : : /// function required by the STL standard, the B+ Tree can hold more items.
311 : 0 : inline size_type max_size() const
312 : : {
313 : 0 : return tree.max_size();
314 : : }
315 : :
316 : : /// Return a const reference to the current statistics.
317 : 0 : inline const tree_stats& get_stats() const
318 : : {
319 : 0 : return tree.get_stats();
320 : : }
321 : :
322 : : public:
323 : : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
324 : :
325 : : /// Non-STL function checking whether a key is in the B+ tree. The same as
326 : : /// (find(k) != end()) or (count() != 0).
327 : 0 : bool exists(const key_type &key) const
328 : : {
329 : 0 : return tree.exists(key);
330 : : }
331 : :
332 : : /// Tries to locate a key in the B+ tree and returns an iterator to the
333 : : /// key/data slot if found. If unsuccessful it returns end().
334 : 99990 : iterator find(const key_type &key)
335 : : {
336 : 99990 : return tree.find(key);
337 : : }
338 : :
339 : : /// Tries to locate a key in the B+ tree and returns an constant iterator
340 : : /// to the key/data slot if found. If unsuccessful it returns end().
341 : 0 : const_iterator find(const key_type &key) const
342 : : {
343 : 0 : return tree.find(key);
344 : : }
345 : :
346 : : /// Tries to locate a key in the B+ tree and returns the number of
347 : : /// identical key entries found. Since this is a unique map, count()
348 : : /// returns either 0 or 1.
349 : 0 : size_type count(const key_type &key) const
350 : : {
351 : 0 : return tree.count(key);
352 : : }
353 : :
354 : : /// Searches the B+ tree and returns an iterator to the first pair
355 : : /// equal to or greater than key, or end() if all keys are smaller.
356 : 0 : iterator lower_bound(const key_type& key)
357 : : {
358 : 0 : return tree.lower_bound(key);
359 : : }
360 : :
361 : : /// Searches the B+ tree and returns a constant iterator to the
362 : : /// first pair equal to or greater than key, or end() if all keys
363 : : /// are smaller.
364 : 0 : const_iterator lower_bound(const key_type& key) const
365 : : {
366 : 0 : return tree.lower_bound(key);
367 : : }
368 : :
369 : : /// Searches the B+ tree and returns an iterator to the first pair
370 : : /// greater than key, or end() if all keys are smaller or equal.
371 : 0 : iterator upper_bound(const key_type& key)
372 : : {
373 : 0 : return tree.upper_bound(key);
374 : : }
375 : :
376 : : /// Searches the B+ tree and returns a constant iterator to the
377 : : /// first pair greater than key, or end() if all keys are smaller
378 : : /// or equal.
379 : 0 : const_iterator upper_bound(const key_type& key) const
380 : : {
381 : 0 : return tree.upper_bound(key);
382 : : }
383 : :
384 : : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
385 : 0 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
386 : : {
387 : 0 : return tree.equal_range(key);
388 : : }
389 : :
390 : : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
391 : 0 : inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
392 : : {
393 : 0 : return tree.equal_range(key);
394 : : }
395 : :
396 : : public:
397 : : // *** B+ Tree Object Comparison Functions
398 : :
399 : : /// Equality relation of B+ trees of the same type. B+ trees of the same
400 : : /// size and equal elements (both key and data) are considered
401 : : /// equal.
402 : 0 : inline bool operator==(const self &other) const
403 : : {
404 : 0 : return (tree == other.tree);
405 : : }
406 : :
407 : : /// Inequality relation. Based on operator==.
408 : 0 : inline bool operator!=(const self &other) const
409 : : {
410 : 0 : return (tree != other.tree);
411 : : }
412 : :
413 : : /// Total ordering relation of B+ trees of the same type. It uses
414 : : /// std::lexicographical_compare() for the actual comparison of elements.
415 : 0 : inline bool operator<(const self &other) const
416 : : {
417 : 0 : return (tree < other.tree);
418 : : }
419 : :
420 : : /// Greater relation. Based on operator<.
421 : 0 : inline bool operator>(const self &other) const
422 : : {
423 : 0 : return (tree > other.tree);
424 : : }
425 : :
426 : : /// Less-equal relation. Based on operator<.
427 : 0 : inline bool operator<=(const self &other) const
428 : : {
429 : 0 : return (tree <= other.tree);
430 : : }
431 : :
432 : : /// Greater-equal relation. Based on operator<.
433 : 0 : inline bool operator>=(const self &other) const
434 : : {
435 : 0 : return (tree >= other.tree);
436 : : }
437 : :
438 : : public:
439 : : /// *** Fast Copy: Assign Operator and Copy Constructors
440 : :
441 : : /// Assignment operator. All the key/data pairs are copied
442 : 0 : inline self& operator= (const self &other)
443 : : {
444 [ # # ]: 0 : if (this != &other)
445 : : {
446 : 0 : tree = other.tree;
447 : : }
448 : 0 : return *this;
449 : : }
450 : :
451 : : /// Copy constructor. The newly initialized B+ tree object will contain a
452 : : /// copy of all key/data pairs.
453 : 0 : inline btree_map(const self &other)
454 : 0 : : tree(other.tree)
455 : : {
456 : 0 : }
457 : :
458 : : public:
459 : : // *** Public Insertion Functions
460 : :
461 : : /// Attempt to insert a key/data pair into the B+ tree. Fails if the pair
462 : : /// is already present.
463 : 2000 : inline std::pair<iterator, bool> insert(const value_type& x)
464 : : {
465 : 2000 : return tree.insert2(x.first, x.second);
466 : : }
467 : :
468 : : /// Attempt to insert a key/data pair into the B+ tree. Beware that if
469 : : /// key_type == data_type, then the template iterator insert() is called
470 : : /// instead. Fails if the inserted pair is already present.
471 : 0 : inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
472 : : {
473 : 0 : return tree.insert2(key, data);
474 : : }
475 : :
476 : : /// Attempt to insert a key/data pair into the B+ tree. This function is the
477 : : /// same as the other insert, however if key_type == data_type then the
478 : : /// non-template function cannot be called. Fails if the inserted pair is
479 : : /// already present.
480 : 0 : inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
481 : : {
482 : 0 : return tree.insert2(key, data);
483 : : }
484 : :
485 : : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
486 : : /// is currently ignored by the B+ tree insertion routine.
487 : 0 : inline iterator insert(iterator hint, const value_type &x)
488 : : {
489 : 0 : return tree.insert2(hint, x.first, x.second);
490 : : }
491 : :
492 : : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
493 : : /// currently ignored by the B+ tree insertion routine.
494 : 0 : inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
495 : : {
496 : 0 : return tree.insert2(hint, key, data);
497 : : }
498 : :
499 : : /// Returns a reference to the object that is associated with a particular
500 : : /// key. If the map does not already contain such an object, operator[]
501 : : /// inserts the default object data_type().
502 : 0 : inline data_type& operator[](const key_type& key)
503 : : {
504 : 0 : iterator i = insert( value_type(key, data_type()) ).first;
505 : 0 : return i.data();
506 : : }
507 : :
508 : : /// Attempt to insert the range [first,last) of value_type pairs into the B+
509 : : /// tree. Each key/data pair is inserted individually.
510 : : template <typename InputIterator>
511 : : inline void insert(InputIterator first, InputIterator last)
512 : : {
513 : : return tree.insert(first, last);
514 : : }
515 : :
516 : : public:
517 : : // *** Public Erase Functions
518 : :
519 : : /// Erases the key/data pairs associated with the given key. For this
520 : : /// unique-associative map there is no difference to erase().
521 : 0 : bool erase_one(const key_type &key)
522 : : {
523 : 0 : return tree.erase_one(key);
524 : : }
525 : :
526 : : /// Erases all the key/data pairs associated with the given key. This is
527 : : /// implemented using erase_one().
528 : 0 : size_type erase(const key_type &key)
529 : : {
530 : 0 : return tree.erase(key);
531 : : }
532 : :
533 : : /// Erase the key/data pair referenced by the iterator.
534 : 0 : void erase(iterator iter)
535 : : {
536 : 0 : return tree.erase(iter);
537 : : }
538 : :
539 : : #ifdef BTREE_TODO
540 : : /// Erase all key/data pairs in the range [first,last). This function is
541 : : /// currently not implemented by the B+ Tree.
542 : : void erase(iterator /* first */, iterator /* last */)
543 : : {
544 : : abort();
545 : : }
546 : : #endif
547 : :
548 : : #ifdef BTREE_DEBUG
549 : : public:
550 : : // *** Debug Printing
551 : :
552 : : /// Print out the B+ tree structure with keys onto the given ostream. This function
553 : : /// requires that the header is compiled with BTREE_DEBUG and that key_type
554 : : /// is printable via std::ostream.
555 : 0 : void print(std::ostream &os) const
556 : : {
557 : 0 : tree.print(os);
558 : 0 : }
559 : :
560 : : /// Print out only the leaves via the double linked list.
561 : 0 : void print_leaves(std::ostream &os) const
562 : : {
563 : 0 : tree.print_leaves(os);
564 : 0 : }
565 : : #endif
566 : :
567 : : public:
568 : : // *** Verification of B+ Tree Invariants
569 : :
570 : : /// Run a thorough verification of all B+ tree invariants. The program
571 : : /// aborts via BTREE_ASSERT() if something is wrong.
572 : 0 : void verify() const
573 : : {
574 : 0 : tree.verify();
575 : 0 : }
576 : :
577 : : public:
578 : :
579 : : /// Dump the contents of the B+ tree out onto an ostream as a binary
580 : : /// image. The image contains memory pointers which will be fixed when the
581 : : /// image is restored. For this to work your key_type and data_type must be
582 : : /// integral types and contain no pointers or references.
583 : 0 : void dump(std::ostream &os) const
584 : : {
585 : 0 : tree.dump(os);
586 : 0 : }
587 : :
588 : : /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
589 : : /// pointers are fixed using the dump order. For dump and restore to work
590 : : /// your key_type and data_type must be integral types and contain no
591 : : /// pointers or references. Returns true if the restore was successful.
592 : 0 : bool restore(std::istream &is)
593 : : {
594 : 0 : return tree.restore(is);
595 : : }
596 : : };
597 : :
598 : : } // namespace stx
599 : :
600 : : #endif // _STX_BTREE_MAP_H_
|
