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