LTP GCOV extension - code coverage report
Current view: directory - include/stx - btree_multimap.h
Test: STX B+ Tree Testsuite
Date: 2007-05-08 Instrumented lines: 103
Code covered: 26.2 % Executed lines: 27

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

Generated by: LTP GCOV extension version 1.4