stx/btree.h

Go to the documentation of this file.
00001 // $Id: btree.h 72 2008-01-25 12:47:26Z tb $
00006 /*
00007  * STX B+ Tree Template Classes v0.8.1
00008  * Copyright (C) 2008 Timo Bingmann
00009  *
00010  * This library is free software; you can redistribute it and/or modify it
00011  * under the terms of the GNU Lesser General Public License as published by the
00012  * Free Software Foundation; either version 2.1 of the License, or (at your
00013  * option) any later version.
00014  *
00015  * This library is distributed in the hope that it will be useful, but WITHOUT
00016  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00017  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
00018  * for more details.
00019  *
00020  * You should have received a copy of the GNU Lesser General Public License
00021  * along with this library; if not, write to the Free Software Foundation,
00022  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00023  */
00024 
00025 #ifndef _STX_BTREE_H_
00026 #define _STX_BTREE_H_
00027 
00028 // *** Required Headers from the STL
00029 
00030 #include <algorithm>
00031 #include <functional>
00032 #include <istream>
00033 #include <ostream>
00034 #include <assert.h>
00035 
00036 // *** Debugging Macros
00037 
00038 #ifdef BTREE_DEBUG
00039 
00040 #include <iostream>
00041 
00043 #define BTREE_PRINT(x)          do { if (debug) (std::cout << x); } while(0)
00044 
00046 #define BTREE_ASSERT(x)         do { assert(x); } while(0)
00047 
00048 #else
00049 
00051 #define BTREE_PRINT(x)          do { } while(0)
00052 
00054 #define BTREE_ASSERT(x)         do { } while(0)
00055 
00056 #endif
00057 
00059 #define BTREE_MAX(a,b)          ((a) < (b) ? (b) : (a))
00060 
00061 #ifndef BTREE_FRIENDS
00065 #define BTREE_FRIENDS           friend class btree_friend;
00066 #endif
00067 
00069 namespace stx {
00070 
00073 template <typename _Key>
00074 struct btree_default_set_traits
00075 {
00078     static const bool   selfverify = false;
00079 
00084     static const bool   debug = false;
00085 
00088     static const int    leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );
00089 
00092     static const int    innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
00093 };
00094 
00097 template <typename _Key, typename _Data>
00098 struct btree_default_map_traits
00099 {
00102     static const bool   selfverify = false;
00103 
00108     static const bool   debug = false;
00109 
00112     static const int    leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );
00113 
00116     static const int    innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
00117 };
00118 
00132 template <typename _Key, typename _Data,
00133           typename _Value = std::pair<_Key, _Data>,
00134           typename _Compare = std::less<_Key>,
00135           typename _Traits = btree_default_map_traits<_Key, _Data>,
00136           bool _Duplicates = false>
00137 class btree
00138 {
00139 public:
00140     // *** Template Parameter Types
00141 
00144     typedef _Key                        key_type;
00145 
00148     typedef _Data                       data_type;
00149 
00154     typedef _Value                      value_type;
00155 
00157     typedef _Compare                    key_compare;
00158 
00161     typedef _Traits                     traits;
00162 
00165     static const bool                   allow_duplicates = _Duplicates;
00166 
00167     // The macro BTREE_FRIENDS can be used by outside class to access the B+
00168     // tree internals. This was added for wxBTreeDemo to be able to draw the
00169     // tree.
00170     BTREE_FRIENDS
00171 
00172 public:
00173     // *** Constructed Types
00174 
00176     typedef btree<key_type, data_type, value_type,
00177                   key_compare, traits, allow_duplicates>        btree_self;
00178 
00180     typedef size_t                              size_type;
00181 
00183     typedef std::pair<key_type, data_type>      pair_type;
00184 
00185 public:
00186     // *** Static Constant Options and Values of the B+ Tree
00187 
00189     static const unsigned short         leafslotmax =  traits::leafslots;
00190 
00193     static const unsigned short         innerslotmax =  traits::innerslots;
00194 
00198     static const unsigned short minleafslots = (leafslotmax / 2);
00199 
00203     static const unsigned short mininnerslots = (innerslotmax / 2);
00204 
00207     static const bool                   selfverify = traits::selfverify;
00208 
00212     static const bool                   debug = traits::debug;
00213 
00214 private:
00215     // *** Node Classes for In-Memory Nodes
00216 
00219     struct node
00220     {
00222         unsigned short  level;
00223 
00226         unsigned short  slotuse;
00227 
00229         inline void initialize(const unsigned short l)
00230         {
00231             level = l;
00232             slotuse = 0;
00233         }
00234 
00236         inline bool isleafnode() const
00237         {
00238             return (level == 0);
00239         }
00240     };
00241 
00244     struct inner_node : public node
00245     {
00247         key_type        slotkey[innerslotmax];
00248 
00250         node*           childid[innerslotmax+1];
00251 
00253         inline void initialize(const unsigned short l)
00254         {
00255             node::initialize(l);
00256         }
00257 
00259         inline bool isfull() const
00260         {
00261             return (node::slotuse == innerslotmax);
00262         }
00263 
00265         inline bool isfew() const
00266         {
00267             return (node::slotuse <= mininnerslots);
00268         }
00269 
00271         inline bool isunderflow() const
00272         {
00273             return (node::slotuse < mininnerslots);
00274         }
00275     };
00276 
00280     struct leaf_node : public node
00281     {
00283         leaf_node       *prevleaf;
00284 
00286         leaf_node       *nextleaf;
00287 
00289         key_type        slotkey[leafslotmax];
00290 
00292         data_type       slotdata[leafslotmax];
00293 
00295         inline void initialize()
00296         {
00297             node::initialize(0);
00298             prevleaf = nextleaf = NULL;
00299         }
00300 
00302         inline bool isfull() const
00303         {
00304             return (node::slotuse == leafslotmax);
00305         }
00306 
00308         inline bool isfew() const
00309         {
00310             return (node::slotuse <= minleafslots);
00311         }
00312 
00314         inline bool isunderflow() const
00315         {
00316             return (node::slotuse < minleafslots);
00317         }
00318     };
00319 
00320 private:
00321     // *** Template Magic to Convert a pair or key/data types to a value_type
00322 
00325     template <typename value_type, typename pair_type>
00326     struct btree_pair_to_value
00327     {
00329         inline value_type operator()(pair_type& p) const {
00330             return p.first;
00331         }
00333         inline value_type operator()(const pair_type& p) const {
00334             return p.first;
00335         }
00336     };
00337 
00339     template <typename value_type>
00340     struct btree_pair_to_value<value_type, value_type>
00341     {
00343         inline value_type operator()(pair_type& p) const {
00344             return p;
00345         }
00347         inline value_type operator()(const pair_type& p) const {
00348             return p;
00349         }
00350     };
00351 
00354     typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;
00355 
00356 public:
00357     // *** Iterators and Reverse Iterators
00358 
00359     class iterator;
00360     class const_iterator;
00361 
00364     class iterator
00365     {
00366     public:
00367         // *** Types
00368 
00370         typedef typename btree::key_type                key_type;
00371 
00373         typedef typename btree::data_type               data_type;
00374 
00376         typedef typename btree::value_type              value_type;
00377 
00379         typedef typename btree::pair_type               pair_type;
00380 
00382         typedef value_type&             reference;
00383 
00385         typedef value_type*             pointer;
00386 
00388         typedef std::bidirectional_iterator_tag iterator_category;
00389 
00391         typedef ptrdiff_t               difference_type;
00392 
00394         typedef iterator                self;
00395 
00396     private:
00397         // *** Members
00398 
00400         typename btree::leaf_node*      currnode;
00401 
00403         unsigned short  currslot;
00404 
00406         friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>::const_iterator;
00407 
00410         mutable value_type              temp_value;
00411 
00412         // The macro BTREE_FRIENDS can be used by outside class to access the B+
00413         // tree internals. This was added for wxBTreeDemo to be able to draw the
00414         // tree.
00415         BTREE_FRIENDS
00416 
00417     public:
00418         // *** Methods
00419 
00421         inline iterator(typename btree::leaf_node *l, unsigned short s)
00422             : currnode(l), currslot(s)
00423         { }
00424 
00427         inline reference operator*() const
00428         {
00429             temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
00430                                                          currnode->slotdata[currslot]) );
00431             return temp_value;
00432         }
00433 
00437         inline pointer operator->() const
00438         {
00439             temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
00440                                                          currnode->slotdata[currslot]) );
00441             return &temp_value;
00442         }
00443 
00445         inline const key_type& key() const
00446         {
00447             return currnode->slotkey[currslot];
00448         }
00449 
00451         inline data_type& data() const
00452         {
00453             return currnode->slotdata[currslot];
00454         }
00455 
00457         inline self& operator++()
00458         {
00459             if (currslot + 1 < currnode->slotuse) {
00460                 ++currslot;
00461             }
00462             else if (currnode->nextleaf != NULL) {
00463                 currnode = currnode->nextleaf;
00464                 currslot = 0;
00465             }
00466             else {
00467                 // this is end()
00468                 currslot = currnode->slotuse;
00469             }
00470 
00471             return *this;
00472         }
00473 
00475         inline self operator++(int)
00476         {
00477             self tmp = *this;   // copy ourselves
00478 
00479             if (currslot + 1 < currnode->slotuse) {
00480                 ++currslot;
00481             }
00482             else if (currnode->nextleaf != NULL) {
00483                 currnode = currnode->nextleaf;
00484                 currslot = 0;
00485             }
00486             else {
00487                 // this is end()
00488                 currslot = currnode->slotuse;
00489             }
00490 
00491             return tmp;
00492         }
00493 
00495         inline self& operator--()
00496         {
00497             if (currslot > 0) {
00498                 --currslot;
00499             }
00500             else if (currnode->prevleaf != NULL) {
00501                 currnode = currnode->prevleaf;
00502                 currslot = currnode->slotuse - 1;
00503             }
00504             else {
00505                 // this is begin()
00506                 currslot = 0;
00507             }
00508 
00509             return *this;
00510         }
00511 
00513         inline self operator--(int)
00514         {
00515             self tmp = *this;   // copy ourselves
00516 
00517             if (currslot > 0) {
00518                 --currslot;
00519             }
00520             else if (currnode->prevleaf != NULL) {
00521                 currnode = currnode->prevleaf;
00522                 currslot = currnode->slotuse - 1;
00523             }
00524             else {
00525                 // this is begin()
00526                 currslot = 0;
00527             }
00528 
00529             return tmp;
00530         }
00531 
00533         inline bool operator==(const self& x) const
00534         {
00535             return (x.currnode == currnode) && (x.currslot == currslot);
00536         }
00537 
00539         inline bool operator!=(const self& x) const
00540         {
00541             return (x.currnode != currnode) || (x.currslot != currslot);
00542         }
00543     };
00544 
00547     class const_iterator
00548     {
00549     public:
00550         // *** Types
00551 
00553         typedef typename btree::key_type                key_type;
00554 
00556         typedef typename btree::data_type               data_type;
00557 
00559         typedef typename btree::value_type              value_type;
00560 
00562         typedef typename btree::pair_type               pair_type;
00563 
00565         typedef const value_type&       reference;
00566 
00568         typedef const value_type*       pointer;
00569 
00571         typedef std::bidirectional_iterator_tag iterator_category;
00572 
00574         typedef ptrdiff_t       difference_type;
00575 
00577         typedef const_iterator          self;
00578 
00579     private:
00580         // *** Members
00581 
00583         const typename btree::leaf_node*        currnode;
00584 
00586         unsigned short  currslot;
00587 
00590         mutable value_type              temp_value;
00591 
00592         // The macro BTREE_FRIENDS can be used by outside class to access the B+
00593         // tree internals. This was added for wxBTreeDemo to be able to draw the
00594         // tree.
00595         BTREE_FRIENDS
00596 
00597     public:
00598         // *** Methods
00599 
00601         inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
00602             : currnode(l), currslot(s)
00603         { }
00604 
00606         inline const_iterator(const iterator &it)
00607             : currnode(it.currnode), currslot(it.currslot)
00608         { }
00609 
00613         inline reference operator*() const
00614         {
00615             temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
00616                                                          currnode->slotdata[currslot]) );
00617             return temp_value;
00618         }
00619 
00623         inline pointer operator->() const
00624         {
00625             temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
00626                                                          currnode->slotdata[currslot]) );
00627             return &temp_value;
00628         }
00629 
00631         inline const key_type& key() const
00632         {
00633             return currnode->slotkey[currslot];
00634         }
00635 
00637         inline const data_type& data() const
00638         {
00639             return currnode->slotdata[currslot];
00640         }
00641 
00643         inline self& operator++()
00644         {
00645             if (currslot + 1 < currnode->slotuse) {
00646                 ++currslot;
00647             }
00648             else if (currnode->nextleaf != NULL) {
00649                 currnode = currnode->nextleaf;
00650                 currslot = 0;
00651             }
00652             else {
00653                 // this is end()
00654                 currslot = currnode->slotuse;
00655             }
00656 
00657             return *this;
00658         }
00659 
00661         inline self operator++(int)
00662         {
00663             self tmp = *this;   // copy ourselves
00664 
00665             if (currslot + 1 < currnode->slotuse) {
00666                 ++currslot;
00667             }
00668             else if (currnode->nextleaf != NULL) {
00669                 currnode = currnode->nextleaf;
00670                 currslot = 0;
00671             }
00672             else {
00673                 // this is end()
00674                 currslot = currnode->slotuse;
00675             }
00676 
00677             return tmp;
00678         }
00679 
00681         inline self& operator--()
00682         {
00683             if (currslot > 0) {
00684                 --currslot;
00685             }
00686             else if (currnode->prevleaf != NULL) {
00687                 currnode = currnode->prevleaf;
00688                 currslot = currnode->slotuse - 1;
00689             }
00690             else {
00691                 // this is begin()
00692                 currslot = 0;
00693             }
00694 
00695             return *this;
00696         }
00697 
00699         inline self operator--(int)
00700         {
00701             self tmp = *this;   // copy ourselves
00702 
00703             if (currslot > 0) {
00704                 --currslot;
00705             }
00706             else if (currnode->prevleaf != NULL) {
00707                 currnode = currnode->prevleaf;
00708                 currslot = currnode->slotuse - 1;
00709             }
00710             else {
00711                 // this is begin()
00712                 currslot = 0;
00713             }
00714 
00715             return tmp;
00716         }
00717 
00719         inline bool operator==(const self& x) const
00720         {
00721             return (x.currnode == currnode) && (x.currslot == currslot);
00722         }
00723 
00725         inline bool operator!=(const self& x) const
00726         {
00727             return (x.currnode != currnode) || (x.currslot != currslot);
00728         }
00729     };
00730 
00732     typedef std::reverse_iterator<iterator>       reverse_iterator;
00733 
00735     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00736 
00737 public:
00738     // *** Small Statistics Structure
00739 
00742     struct tree_stats
00743     {
00745         size_type       itemcount;
00746 
00748         size_type       leaves;
00749 
00751         size_type       innernodes;
00752 
00754         static const unsigned short     leafslots = btree_self::leafslotmax;
00755 
00757         static const unsigned short     innerslots = btree_self::innerslotmax;
00758 
00760         inline tree_stats()
00761             : itemcount(0),
00762               leaves(0), innernodes(0)
00763         {
00764         }
00765 
00767         inline size_type nodes() const
00768         {
00769             return innernodes + leaves;
00770         }
00771 
00773         inline double avgfill_leaves() const
00774         {
00775             return static_cast<double>(itemcount) / (leaves * leafslots);
00776         }
00777     };
00778 
00779 private:
00780     // *** Tree Object Data Members
00781 
00783     node*       root;
00784 
00786     leaf_node   *headleaf;
00787 
00789     leaf_node   *tailleaf;
00790 
00792     tree_stats  stats;
00793 
00796     key_compare key_less;
00797 
00798 public:
00799     // *** Constructors and Destructor
00800 
00803     inline btree()
00804         : root(NULL), headleaf(NULL), tailleaf(NULL)
00805     {
00806     }
00807 
00810     inline btree(const key_compare &kcf)
00811         : root(NULL), headleaf(NULL), tailleaf(NULL),
00812           key_less(kcf)
00813     {
00814     }
00815 
00817     template <class InputIterator>
00818     inline btree(InputIterator first, InputIterator last)
00819         : root(NULL), headleaf(NULL), tailleaf(NULL)
00820     {
00821         insert(first, last);
00822     }
00823 
00826     template <class InputIterator>
00827     inline btree(InputIterator first, InputIterator last, const key_compare &kcf)
00828         : root(NULL), headleaf(NULL), tailleaf(NULL),
00829           key_less(kcf)
00830     {
00831         insert(first, last);
00832     }
00833 
00835     inline ~btree()
00836     {
00837         clear();
00838     }
00839 
00841     void swap(btree_self& from)
00842     {
00843         std::swap(root, from.root);
00844         std::swap(headleaf, from.headleaf);
00845         std::swap(tailleaf, from.tailleaf);
00846         std::swap(stats, from.stats);
00847         std::swap(key_less, from.key_less);
00848     }
00849 
00850 public:
00851     // *** Key and Value Comparison Function Objects
00852 
00854     class value_compare
00855     {
00856     protected:
00858         key_compare     key_comp;
00859 
00861         inline value_compare(key_compare kc)
00862             : key_comp(kc)
00863         { }
00864 
00866         friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>;
00867 
00868     public:
00870         inline bool operator()(const value_type& x, const value_type& y) const
00871         {
00872             return key_comp(x.first, y.first);
00873         }
00874     };
00875 
00877     inline key_compare key_comp() const
00878     {
00879         return key_less;
00880     }
00881 
00884     inline value_compare value_comp() const
00885     {
00886         return value_compare(key_less);
00887     }
00888 
00889 private:
00890     // *** Convenient Key Comparison Functions Generated From key_less
00891 
00893     inline bool key_lessequal(const key_type &a, const key_type b) const
00894     {
00895         return !key_less(b, a);
00896     }
00897 
00899     inline bool key_greater(const key_type &a, const key_type &b) const
00900     {
00901         return key_less(b, a);
00902     }
00903 
00905     inline bool key_greaterequal(const key_type &a, const key_type b) const
00906     {
00907         return !key_less(a, b);
00908     }
00909 
00912     inline bool key_equal(const key_type &a, const key_type &b) const
00913     {
00914         return !key_less(a, b) && !key_less(b, a);
00915     }
00916 
00917 private:
00918     // *** Node Object Allocation and Deallocation Functions
00919 
00921     inline leaf_node* allocate_leaf()
00922     {
00923         leaf_node* n = new leaf_node;
00924         n->initialize();
00925         stats.leaves++;
00926         return n;
00927     }
00928 
00930     inline inner_node* allocate_inner(unsigned short l)
00931     {
00932         inner_node* n = new inner_node;
00933         n->initialize(l);
00934         stats.innernodes++;
00935         return n;
00936     }
00937 
00940     inline void free_node(node *n)
00941     {
00942         if (n->isleafnode()) {
00943             delete static_cast<leaf_node*>(n);
00944             stats.leaves--;
00945         }
00946         else {
00947             delete static_cast<inner_node*>(n);
00948             stats.innernodes--;
00949         }
00950     }
00951 
00952 public:
00953     // *** Fast Destruction of the B+ Tree
00954 
00956     void clear()
00957     {
00958         if (root)
00959         {
00960             clear_recursive(root);
00961             free_node(root);
00962 
00963             root = NULL;
00964             headleaf = tailleaf = NULL;
00965 
00966             stats = tree_stats();
00967         }
00968 
00969         BTREE_ASSERT(stats.itemcount == 0);
00970     }
00971 
00972 private:
00974     void clear_recursive(node *n)
00975     {
00976         if (n->isleafnode())
00977         {
00978             leaf_node *leafnode = static_cast<leaf_node*>(n);
00979 
00980             for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
00981             {
00982                 // data objects are deleted by leaf_node's destructor
00983             }
00984         }
00985         else
00986         {
00987             inner_node *innernode = static_cast<inner_node*>(n);
00988 
00989             for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
00990             {
00991                 clear_recursive(innernode->childid[slot]);
00992                 free_node(innernode->childid[slot]);
00993             }
00994         }
00995     }
00996 
00997 public:
00998     // *** STL Iterator Construction Functions
00999 
01002     inline iterator begin()
01003     {
01004         return iterator(headleaf, 0);
01005     }
01006 
01009     inline iterator end()
01010     {
01011         return iterator(tailleaf, tailleaf ? tailleaf->slotuse : 0);
01012     }
01013 
01016     inline const_iterator begin() const
01017     {
01018         return const_iterator(headleaf, 0);
01019     }
01020 
01023     inline const_iterator end() const
01024     {
01025         return const_iterator(tailleaf, tailleaf ? tailleaf->slotuse : 0);
01026     }
01027 
01030     inline reverse_iterator rbegin()
01031     {
01032         return reverse_iterator(end());
01033     }
01034 
01037     inline reverse_iterator rend()
01038     {
01039         return reverse_iterator(begin());
01040     }
01041 
01044     inline const_reverse_iterator rbegin() const
01045     {
01046         return const_reverse_iterator(end());
01047     }
01048 
01051     inline const_reverse_iterator rend() const
01052     {
01053         return const_reverse_iterator(begin());
01054     }
01055 
01056 private:
01057     // *** B+ Tree Node Binary Search Functions
01058 
01063     template <typename node_type>
01064     inline int find_lower(const node_type *n, const key_type& key) const
01065     {
01066         if (n->slotuse == 0) return 0;
01067 
01068         int lo = 0,
01069             hi = n->slotuse - 1;
01070 
01071         while(lo < hi)
01072         {
01073             int mid = (lo + hi) / 2;
01074 
01075             if (key_lessequal(key, n->slotkey[mid])) {
01076                 hi = mid - 1;
01077             }
01078             else {
01079                 lo = mid + 1;
01080             }
01081         }
01082 
01083         if (hi < 0 || key_less(n->slotkey[hi], key))
01084             hi++;
01085 
01086         BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
01087 
01088         // verify result using simple linear search
01089         if (selfverify)
01090         {
01091             int i = n->slotuse - 1;
01092             while(i >= 0 && key_lessequal(key, n->slotkey[i]))
01093                 i--;
01094             i++;
01095 
01096             BTREE_PRINT("testfind: " << i << std::endl);
01097             BTREE_ASSERT(i == hi);
01098         }
01099         else {
01100             BTREE_PRINT(std::endl);
01101         }
01102 
01103         return hi;
01104     }
01105 
01110     template <typename node_type>
01111     inline int find_upper(const node_type *n, const key_type& key) const
01112     {
01113         if (n->slotuse == 0) return 0;
01114 
01115         int lo = 0,
01116             hi = n->slotuse - 1;
01117 
01118         while(lo < hi)
01119         {
01120             int mid = (lo + hi) / 2;
01121 
01122             if (key_less(key, n->slotkey[mid])) {
01123                 hi = mid - 1;
01124             }
01125             else {
01126                 lo = mid + 1;
01127             }
01128         }
01129 
01130         if (hi < 0 || key_lessequal(n->slotkey[hi], key))
01131             hi++;
01132 
01133         BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");
01134 
01135         // verify result using simple linear search
01136         if (selfverify)
01137         {
01138             int i = n->slotuse - 1;
01139             while(i >= 0 && key_less(key, n->slotkey[i]))
01140                 i--;
01141             i++;
01142 
01143             BTREE_PRINT("btree::find_upper testfind: " << i << std::endl);
01144             BTREE_ASSERT(i == hi);
01145         }
01146         else {
01147             BTREE_PRINT(std::endl);
01148         }
01149 
01150         return hi;
01151     }
01152 
01153 public:
01154     // *** Access Functions to the Item Count
01155 
01157     inline size_type size() const
01158     {
01159         return stats.itemcount;
01160     }
01161 
01163     inline bool empty() const
01164     {
01165         return (size() == size_type(0));
01166     }
01167 
01170     inline size_type max_size() const
01171     {
01172         return size_type(-1);
01173     }
01174 
01176     inline const struct tree_stats& get_stats() const
01177     {
01178         return stats;
01179     }
01180 
01181 public:
01182     // *** Standard Access Functions Querying the Tree by Descending to a Leaf
01183 
01186     bool exists(const key_type &key) const
01187     {
01188         const node *n = root;
01189 
01190         if (!n) return false;
01191 
01192         while(!n->isleafnode())
01193         {
01194             const inner_node *inner = static_cast<const inner_node*>(n);
01195             int slot = find_lower(inner, key);
01196 
01197             n = inner->childid[slot];
01198         }
01199 
01200         const leaf_node *leaf = static_cast<const leaf_node*>(n);
01201 
01202         int slot = find_lower(leaf, key);
01203         return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]));
01204     }
01205 
01208     iterator find(const key_type &key)
01209     {
01210         node *n = root;
01211         if (!n) return end();
01212 
01213         while(!n->isleafnode())
01214         {
01215             const inner_node *inner = static_cast<const inner_node*>(n);
01216             int slot = find_lower(inner, key);
01217 
01218             n = inner->childid[slot];
01219         }
01220 
01221         leaf_node *leaf = static_cast<leaf_node*>(n);
01222 
01223         int slot = find_lower(leaf, key);
01224         return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
01225             ? iterator(leaf, slot) : end();
01226     }
01227 
01230     const_iterator find(const key_type &key) const
01231     {
01232         const node *n = root;
01233         if (!n) return end();
01234 
01235         while(!n->isleafnode())
01236         {
01237             const inner_node *inner = static_cast<const inner_node*>(n);
01238             int slot = find_lower(inner, key);
01239 
01240             n = inner->childid[slot];
01241         }
01242 
01243         const leaf_node *leaf = static_cast<const leaf_node*>(n);
01244 
01245         int slot = find_lower(leaf, key);
01246         return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
01247             ? const_iterator(leaf, slot) : end();
01248     }
01249 
01252     size_type count(const key_type &key) const
01253     {
01254         const node *n = root;
01255         if (!n) return 0;
01256 
01257         while(!n->isleafnode())
01258         {
01259             const inner_node *inner = static_cast<const inner_node*>(n);
01260             int slot = find_lower(inner, key);
01261 
01262             n = inner->childid[slot];
01263         }
01264 
01265         const leaf_node *leaf = static_cast<const leaf_node*>(n);
01266 
01267         int slot = find_lower(leaf, key);
01268         size_type num = 0;
01269 
01270         while (leaf && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot]))
01271         {
01272             ++num;
01273             if (++slot >= leaf->slotuse)
01274             {
01275                 leaf = leaf->nextleaf;
01276                 slot = 0;
01277             }
01278         }
01279 
01280         return num;
01281     }
01282 
01285     iterator lower_bound(const key_type& key)
01286     {
01287         node *n = root;
01288         if (!n) return end();
01289 
01290         while(!n->isleafnode())
01291         {
01292             const inner_node *inner = static_cast<const inner_node*>(n);
01293             int slot = find_lower(inner, key);
01294 
01295             n = inner->childid[slot];
01296         }
01297 
01298         leaf_node *leaf = static_cast<leaf_node*>(n);
01299 
01300         int slot = find_lower(leaf, key);
01301         return iterator(leaf, slot);
01302     }
01303 
01306     const_iterator lower_bound(const key_type& key) const
01307     {
01308         const node *n = root;
01309         if (!n) return end();
01310 
01311         while(!n->isleafnode())
01312         {
01313             const inner_node *inner = static_cast<const inner_node*>(n);
01314             int slot = find_lower(inner, key);
01315 
01316             n = inner->childid[slot];
01317         }
01318 
01319         const leaf_node *leaf = static_cast<const leaf_node*>(n);
01320 
01321         int slot = find_lower(leaf, key);
01322         return const_iterator(leaf, slot);
01323     }
01324 
01327     iterator upper_bound(const key_type& key)
01328     {
01329         node *n = root;
01330         if (!n) return end();
01331 
01332         while(!n->isleafnode())
01333         {
01334             const inner_node *inner = static_cast<const inner_node*>(n);
01335             int slot = find_upper(inner, key);
01336 
01337             n = inner->childid[slot];
01338         }
01339 
01340         leaf_node *leaf = static_cast<leaf_node*>(n);
01341 
01342         int slot = find_upper(leaf, key);
01343         return iterator(leaf, slot);
01344     }
01345 
01348     const_iterator upper_bound(const key_type& key) const
01349     {
01350         const node *n = root;
01351         if (!n) return end();
01352 
01353         while(!n->isleafnode())
01354         {
01355             const inner_node *inner = static_cast<const inner_node*>(n);
01356             int slot = find_upper(inner, key);
01357 
01358             n = inner->childid[slot];
01359         }
01360 
01361         const leaf_node *leaf = static_cast<const leaf_node*>(n);
01362 
01363         int slot = find_upper(leaf, key);
01364         return const_iterator(leaf, slot);
01365     }
01366 
01368     inline std::pair<iterator, iterator> equal_range(const key_type& key)
01369     {
01370         return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
01371     }
01372 
01374     inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
01375     {
01376         return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
01377     }
01378 
01379 public:
01380     // *** B+ Tree Object Comparison Functions
01381 
01385     inline bool operator==(const btree_self &other) const
01386     {
01387         return (size() == other.size()) && std::equal(begin(), end(), other.begin());
01388     }
01389 
01391     inline bool operator!=(const btree_self &other) const
01392     {
01393         return !(*this == other);
01394     }
01395 
01398     inline bool operator<(const btree_self &other) const
01399     {
01400         return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
01401     }
01402 
01404     inline bool operator>(const btree_self &other) const
01405     {
01406         return other < *this;
01407     }
01408 
01410     inline bool operator<=(const btree_self &other) const
01411     {
01412         return !(other < *this);
01413     }
01414 
01416     inline bool operator>=(const btree_self &other) const
01417     {
01418         return !(*this < other);
01419     }
01420 
01421 public:
01423 
01425     inline btree_self& operator= (const btree_self &other)
01426     {
01427         if (this != &other)
01428         {
01429             clear();
01430 
01431             key_less = other.key_comp();
01432             if (other.size() != 0)
01433             {
01434                 stats.leaves = stats.innernodes = 0;
01435                 root = copy_recursive(other.root);
01436                 stats = other.stats;
01437             }
01438 
01439             if (selfverify) verify();
01440         }
01441         return *this;
01442     }
01443 
01446     inline btree(const btree_self &other)
01447         : root(NULL), headleaf(NULL), tailleaf(NULL),
01448           stats( other.stats ),
01449           key_less( other.key_comp() )
01450     {
01451         if (size() > 0)
01452         {
01453             stats.leaves = stats.innernodes = 0;
01454             root = copy_recursive(other.root);
01455             if (selfverify) verify();
01456         }
01457     }
01458 
01459 private:
01461     struct node* copy_recursive(const node *n)
01462     {
01463         if (n->isleafnode())
01464         {
01465             const leaf_node *leaf = static_cast<const leaf_node*>(n);
01466             leaf_node *newleaf = allocate_leaf();
01467 
01468             newleaf->slotuse = leaf->slotuse;
01469             std::copy(leaf->slotkey, leaf->slotkey + leaf->slotuse, newleaf->slotkey);
01470             std::copy(leaf->slotdata, leaf->slotdata + leaf->slotuse, newleaf->slotdata);
01471 
01472             if (headleaf == NULL)
01473             {
01474                 headleaf = tailleaf = newleaf;
01475                 newleaf->prevleaf = newleaf->nextleaf = NULL;
01476             }
01477             else
01478             {
01479                 newleaf->prevleaf = tailleaf;
01480                 tailleaf->nextleaf = newleaf;
01481                 tailleaf = newleaf;
01482             }
01483 
01484             return newleaf;
01485         }
01486         else
01487         {
01488             const inner_node *inner = static_cast<const inner_node*>(n);
01489             inner_node *newinner = allocate_inner(inner->level);
01490 
01491             newinner->slotuse = inner->slotuse;
01492             std::copy(inner->slotkey, inner->slotkey + inner->slotuse, newinner->slotkey);
01493 
01494             for (unsigned short slot = 0; slot <= inner->slotuse; ++slot)
01495             {
01496                 newinner->childid[slot] = copy_recursive(inner->childid[slot]);
01497             }
01498 
01499             return newinner;
01500         }
01501     }
01502 
01503 public:
01504     // *** Public Insertion Functions
01505 
01509     inline std::pair<iterator, bool> insert(const pair_type& x)
01510     {
01511         return insert_start(x.first, x.second);
01512     }
01513 
01518     inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
01519     {
01520         return insert_start(key, data);
01521     }
01522 
01527     inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
01528     {
01529         return insert_start(key, data);
01530     }
01531 
01534     inline iterator insert(iterator /* hint */, const pair_type &x)
01535     {
01536         return insert_start(x.first, x.second).first;
01537     }
01538 
01541     inline iterator insert2(iterator /* hint */, const key_type& key, const data_type& data)
01542     {
01543         return insert_start(key, data).first;
01544     }
01545 
01548     template <typename InputIterator>
01549     inline void insert(InputIterator first, InputIterator last)
01550     {
01551         InputIterator iter = first;
01552         while(iter != last)
01553         {
01554             insert(*iter);
01555             ++iter;
01556         }
01557     }
01558 
01559 private:
01560     // *** Private Insertion Functions
01561 
01564     std::pair<iterator, bool> insert_start(const key_type& key, const data_type& value)
01565     {
01566         node *newchild = NULL;
01567         key_type newkey = key_type();
01568 
01569         if (!root)
01570         {
01571             root = headleaf = tailleaf = allocate_leaf();
01572         }
01573 
01574         std::pair<iterator, bool> r = insert_descend(root, key, value, &newkey, &newchild);
01575 
01576         if (newchild)
01577         {
01578             inner_node *newroot = allocate_inner(root->level + 1);
01579             newroot->slotkey[0] = newkey;
01580 
01581             newroot->childid[0] = root;
01582             newroot->childid[1] = newchild;
01583 
01584             newroot->slotuse = 1;
01585 
01586             root = newroot;
01587         }
01588 
01589         // increment itemcount if the item was inserted
01590         if (r.second) ++stats.itemcount;
01591 
01592 #ifdef BTREE_DEBUG
01593         if (debug) print(std::cout);
01594 #endif
01595 
01596         if (selfverify) {
01597             verify();
01598             BTREE_ASSERT(exists(key));
01599         }
01600 
01601         return r;
01602     }
01603 
01611     std::pair<iterator, bool> insert_descend(node* n,
01612                                              const key_type& key, const data_type& value,
01613                                              key_type* splitkey, node** splitnode)
01614     {
01615         if (!n->isleafnode())
01616         {
01617             inner_node *inner = static_cast<inner_node*>(n);
01618 
01619             key_type newkey = key_type();
01620             node *newchild = NULL;
01621 
01622             int slot = find_lower(inner, key);
01623 
01624             BTREE_PRINT("btree::insert_descend into " << inner->childid[slot] << std::endl);
01625 
01626             std::pair<iterator, bool> r = insert_descend(inner->childid[slot],
01627                                                          key, value, &newkey, &newchild);
01628 
01629             if (newchild)
01630             {
01631                 BTREE_PRINT("btree::insert_descend newchild with key " << newkey << " node " << newchild << " at slot " << slot << std::endl);
01632 
01633                 if (inner->isfull())
01634                 {
01635                     split_inner_node(inner, splitkey, splitnode, slot);
01636 
01637                     BTREE_PRINT("btree::insert_descend done split_inner: putslot: " << slot << " putkey: " << newkey << " upkey: " << *splitkey << std::endl);
01638 
01639 #ifdef BTREE_DEBUG
01640                     if (debug)
01641                     {
01642                         print_node(std::cout, inner);
01643                         print_node(std::cout, *splitnode);
01644                     }
01645 #endif
01646 
01647                     // check if insert slot is in the split sibling node
01648                     BTREE_PRINT("btree::insert_descend switch: " << slot << " > " << inner->slotuse+1 << std::endl);
01649 
01650                     if (slot == inner->slotuse+1 && inner->slotuse < (*splitnode)->slotuse)
01651                     {
01652                         // special case when the insert slot matches the split
01653                         // place between the two nodes, then the insert key
01654                         // becomes the split key.
01655 
01656                         BTREE_ASSERT(inner->slotuse + 1 < innerslotmax);
01657 
01658                         inner_node *splitinner = static_cast<inner_node*>(*splitnode);
01659 
01660                         // move the split key and it's datum into the left node
01661                         inner->slotkey[inner->slotuse] = *splitkey;
01662                         inner->childid[inner->slotuse+1] = splitinner->childid[0];
01663                         inner->slotuse++;
01664 
01665                         // set new split key and move corresponding datum into right node
01666                         splitinner->childid[0] = newchild;
01667                         *splitkey = newkey;
01668 
01669                         return r;
01670                     }
01671                     else if (slot >= inner->slotuse+1)
01672                     {
01673                         // in case the insert slot is in the newly create split
01674                         // node, we reuse the code below.
01675 
01676                         slot -= inner->slotuse+1;
01677                         inner = static_cast<inner_node*>(*splitnode);
01678                         BTREE_PRINT("btree::insert_descend switching to splitted node " << inner << " slot " << slot <<std::endl);
01679                     }
01680                 }
01681 
01682                 // put pointer to child node into correct slot
01683                 BTREE_ASSERT(slot >= 0 && slot <= inner->slotuse);
01684 
01685                 int i = inner->slotuse;
01686 
01687                 while(i > slot) {
01688                     inner->slotkey[i] = inner->slotkey[i - 1];
01689                     inner->childid[i + 1] = inner->childid[i];
01690                     i--;
01691                 }
01692 
01693                 inner->slotkey[slot] = newkey;
01694                 inner->childid[slot + 1] = newchild;
01695                 inner->slotuse++;
01696             }
01697 
01698             return r;
01699         }
01700         else // n->isleafnode() == true
01701         {
01702             leaf_node *leaf = static_cast<leaf_node*>(n);
01703 
01704             int slot = find_lower(leaf, key);
01705 
01706             if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) {
01707                 return std::pair<iterator, bool>(iterator(leaf, slot), false);
01708             }
01709 
01710             if (leaf->isfull())
01711             {
01712                 split_leaf_node(leaf, splitkey, splitnode);
01713 
01714                 // check if insert slot is in the split sibling node
01715                 if (slot >= leaf->slotuse)
01716                 {
01717                     slot -= leaf->slotuse;
01718                     leaf = static_cast<leaf_node*>(*splitnode);
01719                 }
01720             }
01721 
01722             // put data item into correct data slot
01723 
01724             int i = leaf->slotuse - 1;
01725             BTREE_ASSERT(i + 1 < leafslotmax);
01726 
01727             while(i >= 0 && key_less(key, leaf->slotkey[i])) {
01728                 leaf->slotkey[i + 1] = leaf->slotkey[i];
01729                 leaf->slotdata[i + 1] = leaf->slotdata[i];
01730                 i--;
01731             }
01732 
01733             leaf->slotkey[i + 1] = key;
01734             leaf->slotdata[i + 1] = value;
01735             leaf->slotuse++;
01736 
01737             if (splitnode && leaf != *splitnode && slot == leaf->slotuse-1)
01738             {
01739                 // special case: the node was split, and the insert is at the
01740                 // last slot of the old node. then the splitkey must be
01741                 // updated.
01742                 *splitkey = key;
01743             }
01744 
01745             return std::pair<iterator, bool>(iterator(leaf, i + 1), true);
01746         }
01747     }
01748 
01751     void split_leaf_node(leaf_node* leaf, key_type* _newkey, node** _newleaf)
01752     {
01753         BTREE_ASSERT(leaf->isfull());
01754 
01755         unsigned int mid = leaf->slotuse / 2;
01756 
01757         BTREE_PRINT("btree::split_leaf_node on " << leaf << std::endl);
01758 
01759         leaf_node *newleaf = allocate_leaf();
01760 
01761         newleaf->slotuse = leaf->slotuse - mid;
01762 
01763         newleaf->nextleaf = leaf->nextleaf;
01764         if (newleaf->nextleaf == NULL) {
01765             BTREE_ASSERT(leaf == tailleaf);
01766             tailleaf = newleaf;
01767         }
01768         else {
01769             newleaf->nextleaf->prevleaf = newleaf;
01770         }
01771 
01772         for(unsigned int slot = mid; slot < leaf->slotuse; ++slot)
01773         {
01774             unsigned int ni = slot - mid;
01775             newleaf->slotkey[ni] = leaf->slotkey[slot];
01776             newleaf->slotdata[ni] = leaf->slotdata[slot];
01777         }
01778 
01779         leaf->slotuse = mid;
01780         leaf->nextleaf = newleaf;
01781         newleaf->prevleaf = leaf;
01782 
01783         *_newkey = leaf->slotkey[leaf->slotuse-1];
01784         *_newleaf = newleaf;
01785     }
01786 
01791     void split_inner_node(inner_node* inner, key_type* _newkey, node** _newinner, unsigned int addslot)
01792     {
01793         BTREE_ASSERT(inner->isfull());
01794 
01795         unsigned int mid = inner->slotuse / 2;
01796 
01797         BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot << std::endl);
01798 
01799         // if the split is uneven and the overflowing item will be put into the
01800         // larger node, then the smaller split node may underflow
01801         if (addslot <= mid && mid > inner->slotuse - (mid + 1))
01802             mid--;
01803 
01804         BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot << std::endl);
01805 
01806         BTREE_PRINT("btree::split_inner_node on " << inner << " into two nodes " << mid << " and " << inner->slotuse - (mid + 1) << " sized" << std::endl);
01807 
01808         inner_node *newinner = allocate_inner(inner->level);
01809 
01810         newinner->slotuse = inner->slotuse - (mid + 1);
01811 
01812         for(unsigned int slot = mid + 1; slot < inner->slotuse; ++slot)
01813         {
01814             unsigned int ni = slot - (mid + 1);
01815             newinner->slotkey[ni] = inner->slotkey[slot];
01816             newinner->childid[ni] = inner->childid[slot];
01817         }
01818         newinner->childid[newinner->slotuse] = inner->childid[inner->slotuse];
01819 
01820         inner->slotuse = mid;
01821 
01822         *_newkey = inner->slotkey[mid];
01823         *_newinner = newinner;
01824     }
01825 
01826 private:
01827     // *** Support Class Encapsulating Deletion Results
01828 
01830     enum result_flags_t
01831     {
01833         btree_ok = 0,
01834 
01836         btree_not_found = 1,
01837 
01840         btree_update_lastkey = 2,
01841 
01844         btree_fixmerge = 4
01845     };
01846 
01849     struct result_t
01850     {
01852         result_flags_t  flags;
01853 
01855         key_type        lastkey;
01856 
01859         inline result_t(result_flags_t f = btree_ok)
01860             : flags(f), lastkey()
01861         { }
01862 
01864         inline result_t(result_flags_t f, const key_type &k)
01865             : flags(f), lastkey(k)
01866         { }
01867 
01869         inline bool has(result_flags_t f) const
01870         {
01871             return (flags & f) != 0;
01872         }
01873 
01875         inline result_t& operator|= (const result_t &other)
01876         {
01877             flags = result_flags_t(flags | other.flags);
01878 
01879             // we overwrite existing lastkeys on purpose
01880             if (other.has(btree_update_lastkey))
01881                 lastkey = other.lastkey;
01882 
01883             return *this;
01884         }
01885     };
01886 
01887 public:
01888     // *** Public Erase Functions
01889 
01892     bool erase_one(const key_type &key)
01893     {
01894         BTREE_PRINT("btree::erase_one(" << key << ") on btree size " << size() << std::endl);
01895 
01896         if (selfverify) verify();
01897 
01898         result_t result = erase_one_descend(key, root, NULL, NULL, NULL, NULL, NULL, 0);
01899 
01900         if (!result.has(btree_not_found))
01901             --stats.itemcount;
01902 
01903 #ifdef BTREE_DEBUG
01904         if (debug) print(std::cout);
01905 #endif
01906         if (selfverify) verify();
01907 
01908         return !result.has(btree_not_found);
01909     }
01910 
01913     size_type erase(const key_type &key)
01914     {
01915         size_type c = 0;
01916 
01917         while( erase_one(key) )
01918         {
01919             ++c;
01920             if (!allow_duplicates) break;
01921         }
01922 
01923         return c;
01924     }
01925 
01926 #ifdef BTREE_TODO
01928     void erase(iterator iter)
01929     {
01930 
01931     }
01932 #endif
01933 
01934 #ifdef BTREE_TODO
01937     void erase(iterator /* first */, iterator /* last */)
01938     {
01939         abort();
01940     }
01941 #endif
01942 
01943 private:
01944     // *** Private Erase Functions
01945 
01955     result_t erase_one_descend(const key_type& key,
01956                                node *curr,
01957                                node *left, node *right,
01958                                inner_node *leftparent, inner_node *rightparent,
01959                                inner_node *parent, unsigned int parentslot)
01960     {
01961         if (curr->isleafnode())
01962         {
01963             leaf_node *leaf = static_cast<leaf_node*>(curr);
01964             leaf_node *leftleaf = static_cast<leaf_node*>(left);
01965             leaf_node *rightleaf = static_cast<leaf_node*>(right);
01966 
01967             int slot = find_lower(leaf, key);
01968 
01969             if (slot >= leaf->slotuse || !key_equal(key, leaf->slotkey[slot]))
01970             {
01971                 BTREE_PRINT("Could not find key " << key << " to erase." << std::endl);
01972 
01973                 return btree_not_found;
01974             }
01975 
01976             BTREE_PRINT("Found key in leaf " << curr << " at slot " << slot << std::endl);
01977 
01978             for (int i = slot; i < leaf->slotuse - 1; i++)
01979             {
01980                 leaf->slotkey[i] = leaf->slotkey[i + 1];
01981                 leaf->slotdata[i] = leaf->slotdata[i + 1];
01982             }
01983             leaf->slotuse--;
01984 
01985             result_t myres = btree_ok;
01986 
01987             // if the last key of the leaf was changed, the parent is notified
01988             // and updates the key of this leaf
01989             if (slot == leaf->slotuse)
01990             {
01991                 if (parent && parentslot < parent->slotuse)
01992                 {
01993                     BTREE_ASSERT(parent->childid[parentslot] == curr);
01994                     parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
01995                 }
01996                 else
01997                 {
01998                     BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1] << std::endl);
01999                     myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
02000                 }
02001             }
02002 
02003             if (leaf->isunderflow() && !(leaf == root && leaf->slotuse >= 1))
02004             {
02005                 // determine what to do about the underflow
02006 
02007                 // case : if this empty leaf is the root, there is no way to
02008                 // correct underflow
02009                 if (leftleaf == NULL && rightleaf == NULL)
02010                 {
02011                     return btree_ok;
02012                 }
02013                 // case : if both left and right leaves would underflow in case of
02014                 // a shift, then merging is necessary. choose the more local merger
02015                 // with our parent
02016                 else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
02017                 {
02018                     if (leftparent == parent)
02019                         myres |= merge_leaves(leftleaf, leaf, leftparent);
02020                     else
02021                         myres |= merge_leaves(leaf, rightleaf, rightparent);
02022                 }
02023                 // case : the right leaf has extra data, so balance right with current
02024                 else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
02025                 {
02026                     if (rightparent == parent)
02027                         myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
02028                     else
02029                         myres |= merge_leaves(leftleaf, leaf, leftparent);
02030                 }
02031                 // case : the left leaf has extra data, so balance left with current
02032                 else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
02033                 {
02034                     if (leftparent == parent)
02035                         shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
02036                     else
02037                         myres |= merge_leaves(leaf, rightleaf, rightparent);
02038                 }
02039                 // case : both the leaf and right leaves have extra data and our
02040                 // parent, choose the leaf with more data
02041                 else if (leftparent == rightparent)
02042                 {
02043                     if (leftleaf->slotuse <= rightleaf->slotuse)
02044                         myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
02045                     else
02046                         shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
02047                 }
02048                 else
02049                 {
02050                     if (leftparent == parent)
02051                         shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
02052                     else
02053                         myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
02054                 }
02055             }
02056 
02057             return myres;
02058         }
02059         else // !curr->isleafnode()
02060         {
02061             inner_node *inner = static_cast<inner_node*>(curr);
02062             inner_node *leftinner = static_cast<inner_node*>(left);
02063             inner_node *rightinner = static_cast<inner_node*>(right);
02064 
02065             node *myleft, *myright;
02066             inner_node *myleftparent, *myrightparent;
02067 
02068             int slot = find_lower(inner, key);
02069 
02070             if (slot == 0) {
02071                 myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
02072                 myleftparent = leftparent;
02073             }
02074             else {
02075                 myleft = inner->childid[slot - 1];
02076                 myleftparent = inner;
02077             }
02078 
02079             if (slot == inner->slotuse) {
02080                 myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
02081                 myrightparent = rightparent;
02082             }
02083             else {
02084                 myright = inner->childid[slot + 1];
02085                 myrightparent = inner;
02086             }
02087 
02088             BTREE_PRINT("erase_one_descend into " << inner->childid[slot] << std::endl);
02089 
02090             result_t result = erase_one_descend(key,
02091                                                 inner->childid[slot],
02092                                                 myleft, myright,
02093                                                 myleftparent, myrightparent,
02094                                                 inner, slot);
02095 
02096             result_t myres = btree_ok;
02097 
02098             if (result.has(btree_not_found))
02099             {
02100                 return result;
02101             }
02102 
02103             if (result.has(btree_update_lastkey))
02104             {
02105                 if (parent && parentslot < parent->slotuse)
02106                 {
02107                     BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot << std::endl);
02108 
02109                     BTREE_ASSERT(parent->childid[parentslot] == curr);
02110                     parent->slotkey[parentslot] = result.lastkey;
02111                 }
02112                 else
02113                 {
02114                     BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey << std::endl);
02115                     myres |= result_t(btree_update_lastkey, result.lastkey);
02116                 }
02117             }
02118 
02119             if (result.has(btree_fixmerge))
02120             {
02121                 // either the current node or the next is empty and should be removed
02122                 if (inner->childid[slot]->slotuse != 0)
02123                     slot++;
02124 
02125                 // this is the child slot invalidated by the merge
02126                 BTREE_ASSERT(inner->childid[slot]->slotuse == 0);
02127 
02128                 free_node(inner->childid[slot]);
02129 
02130                 for(int i = slot; i < inner->slotuse; i++)
02131                 {
02132                     inner->slotkey[i - 1] = inner->slotkey[i];
02133                     inner->childid[i] = inner->childid[i + 1];
02134                 }
02135                 inner->slotuse--;
02136 
02137                 if (inner->level == 1)
02138                 {
02139                     // fix split key for children leaves
02140                     slot--;
02141                     leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]);
02142                     inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
02143                 }
02144             }
02145 
02146             if (inner->isunderflow() && !(inner == root && inner->slotuse >= 1))
02147             {
02148                 // case: the inner node is the root and has just one child. that child becomes the new root
02149                 if (leftinner == NULL && rightinner == NULL)
02150                 {
02151                     BTREE_ASSERT(inner == root);
02152                     BTREE_ASSERT(inner->slotuse == 0);
02153 
02154                     root = inner->childid[0];
02155 
02156                     inner->slotuse = 0;
02157                     free_node(inner);
02158 
02159                     return btree_ok;
02160                 }
02161                 // case : if both left and right leaves would underflow in case of
02162                 // a shift, then merging is necessary. choose the more local merger
02163                 // with our parent
02164                 else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
02165                 {
02166                     if (leftparent == parent)
02167                         myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
02168                     else
02169                         myres |= merge_inner(inner, rightinner, rightparent, parentslot);
02170                 }
02171                 // case : the right leaf has extra data, so balance right with current
02172                 else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
02173                 {
02174                     if (rightparent == parent)
02175                         shift_left_inner(inner, rightinner, rightparent, parentslot);
02176                     else
02177                         myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
02178                 }
02179                 // case : the left leaf has extra data, so balance left with current
02180                 else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
02181                 {
02182                     if (leftparent == parent)
02183                         shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
02184                     else
02185                         myres |= merge_inner(inner, rightinner, rightparent, parentslot);
02186                 }
02187                 // case : both the leaf and right leaves have extra data and our
02188                 // parent, choose the leaf with more data
02189                 else if (leftparent == rightparent)
02190                 {
02191                     if (leftinner->slotuse <= rightinner->slotuse)
02192                         shift_left_inner(inner, rightinner, rightparent, parentslot);
02193                     else
02194                         shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
02195                 }
02196                 else
02197                 {
02198                     if (leftparent == parent)
02199                         shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
02200                     else
02201                         shift_left_inner(inner, rightinner, rightparent, parentslot);
02202                 }
02203             }
02204 
02205             return myres;
02206         }
02207     }
02208 
02212     result_t merge_leaves(leaf_node* left, leaf_node* right, inner_node* parent)
02213     {
02214         BTREE_PRINT("Merge leaf nodes " << left << " and " << right << " with common parent " << parent << "." << std::endl);
02215         (void)parent;
02216 
02217         BTREE_ASSERT(left->isleafnode() && right->isleafnode());
02218         BTREE_ASSERT(parent->level == 1);
02219 
02220         BTREE_ASSERT(left->slotuse + right->slotuse < leafslotmax);
02221 
02222         for (unsigned int i = 0; i < right->slotuse; i++)
02223         {
02224             left->slotkey[left->slotuse + i] = right->slotkey[i];
02225             left->slotdata[left->slotuse + i] = right->slotdata[i];
02226         }
02227         left->slotuse += right->slotuse;
02228 
02229         left->nextleaf = right->nextleaf;
02230         if (left->nextleaf)
02231             left->nextleaf->prevleaf = left;
02232         else
02233             tailleaf = left;
02234 
02235         right->slotuse = 0;
02236 
02237         return btree_fixmerge;
02238     }
02239 
02243     static result_t merge_inner(inner_node* left, inner_node* right, inner_node* parent, unsigned int parentslot)
02244     {
02245         BTREE_PRINT("Merge inner nodes " << left << " and " << right << " with common parent " << parent << "." << std::endl);
02246 
02247         BTREE_ASSERT(left->level == right->level);
02248         BTREE_ASSERT(parent->level == left->level + 1);
02249 
02250         BTREE_ASSERT(parent->childid[parentslot] == left);
02251 
02252         BTREE_ASSERT(left->slotuse + right->slotuse < innerslotmax);
02253 
02254         if (selfverify)
02255         {
02256             // find the left node's slot in the parent's children
02257             unsigned int leftslot = 0;
02258             while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
02259                 ++leftslot;
02260 
02261             BTREE_ASSERT(leftslot < parent->slotuse);
02262             BTREE_ASSERT(parent->childid[leftslot] == left);
02263             BTREE_ASSERT(parent->childid[leftslot+1] == right);
02264 
02265             BTREE_ASSERT(parentslot == leftslot);
02266         }
02267 
02268         // retrieve the decision key from parent
02269         left->slotkey[left->slotuse] = parent->slotkey[parentslot];
02270         left->slotuse++;
02271 
02272         // copy over keys and children from right
02273         for (unsigned int i = 0; i < right->slotuse; i++)
02274         {
02275             left->slotkey[left->slotuse + i] = right->slotkey[i];
02276             left->childid[left->slotuse + i] = right->childid[i];
02277         }
02278         left->slotuse += right->slotuse;
02279 
02280         left->childid[left->slotuse] = right->childid[right->slotuse];
02281 
02282         right->slotuse = 0;
02283 
02284         return btree_fixmerge;
02285     }
02286 
02290     static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
02291     {
02292         BTREE_ASSERT(left->isleafnode() && right->isleafnode());
02293         BTREE_ASSERT(parent->level == 1);
02294 
02295         BTREE_ASSERT(left->nextleaf == right);
02296         BTREE_ASSERT(left == right->prevleaf);
02297 
02298         BTREE_ASSERT(left->slotuse < right->slotuse);
02299         BTREE_ASSERT(parent->childid[parentslot] == left);
02300 
02301         unsigned int shiftnum = (right->slotuse - left->slotuse) / 2;
02302 
02303         BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "." << std::endl);
02304 
02305         BTREE_ASSERT(left->slotuse + shiftnum < leafslotmax);
02306 
02307         // copy the first items from the right node to the last slot in the left node.
02308         for(unsigned int i = 0; i < shiftnum; i++)
02309         {
02310             left->slotkey[left->slotuse + i] = right->slotkey[i];
02311             left->slotdata[left->slotuse + i] = right->slotdata[i];
02312         }
02313         left->slotuse += shiftnum;
02314 
02315         // shift all slots in the right node to the left
02316 
02317         right->slotuse -= shiftnum;
02318         for(int i = 0; i < right->slotuse; i++)
02319         {
02320             right->slotkey[i] = right->slotkey[i + shiftnum];
02321             right->slotdata[i] = right->slotdata[i + shiftnum];
02322         }
02323 
02324         // fixup parent
02325         if (parentslot < parent->slotuse) {
02326             parent->slotkey[parentslot] = left->slotkey[left->slotuse - 1];
02327             return btree_ok;
02328         }
02329         else { // the update is further up the tree
02330             return result_t(btree_update_lastkey, left->slotkey[left->slotuse - 1]);
02331         }
02332     }
02333 
02337     static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
02338     {
02339         BTREE_ASSERT(left->level == right->level);
02340         BTREE_ASSERT(parent->level == left->level + 1);
02341 
02342         BTREE_ASSERT(left->slotuse < right->slotuse);
02343         BTREE_ASSERT(parent->childid[parentslot] == left);
02344 
02345         unsigned int shiftnum = (right->slotuse - left->slotuse) / 2;
02346 
02347         BTREE_PRINT("Shifting (inner) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "." << std::endl);
02348 
02349         BTREE_ASSERT(left->slotuse + shiftnum < innerslotmax);
02350 
02351         if (selfverify)
02352         {
02353             // find the left node's slot in the parent's children and compare to parentslot
02354 
02355             unsigned int leftslot = 0;
02356             while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
02357                 ++leftslot;
02358 
02359             BTREE_ASSERT(leftslot < parent->slotuse);
02360             BTREE_ASSERT(parent->childid[leftslot] == left);
02361             BTREE_ASSERT(parent->childid[leftslot+1] == right);
02362 
02363             BTREE_ASSERT(leftslot == parentslot);
02364         }
02365 
02366         // copy the parent's decision slotkey and childid to the first new key on the left
02367         left->slotkey[left->slotuse] = parent->slotkey[parentslot];
02368         left->slotuse++;
02369 
02370         // copy the other items from the right node to the last slots in the left node.
02371         for(unsigned int i = 0; i < shiftnum - 1; i++)
02372         {
02373             left->slotkey[left->slotuse + i] = right->slotkey[i];
02374             left->childid[left->slotuse + i] = right->childid[i];
02375         }
02376         left->slotuse += shiftnum - 1;
02377 
02378         // fixup parent
02379         parent->slotkey[parentslot] = right->slotkey[shiftnum - 1];
02380         // last pointer in left
02381         left->childid[left->slotuse] = right->childid[shiftnum - 1];
02382 
02383         // shift all slots in the right node
02384 
02385         right->slotuse -= shiftnum;
02386         for(int i = 0; i < right->slotuse; i++)
02387         {
02388             right->slotkey[i] = right->slotkey[i + shiftnum];
02389             right->childid[i] = right->childid[i + shiftnum];
02390         }
02391         right->childid[right->slotuse] = right->childid[right->slotuse + shiftnum];
02392     }
02393 
02397     static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
02398     {
02399         BTREE_ASSERT(left->isleafnode() && right->isleafnode());
02400         BTREE_ASSERT(parent->level == 1);
02401 
02402         BTREE_ASSERT(left->nextleaf == right);
02403         BTREE_ASSERT(left == right->prevleaf);
02404         BTREE_ASSERT(parent->childid[parentslot] == left);
02405 
02406         BTREE_ASSERT(left->slotuse > right->slotuse);
02407 
02408         unsigned int shiftnum = (left->slotuse - right->slotuse) / 2;
02409 
02410         BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "." << std::endl);
02411 
02412         if (selfverify)
02413         {
02414             // find the left node's slot in the parent's children
02415             unsigned int leftslot = 0;
02416             while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
02417                 ++leftslot;
02418 
02419             BTREE_ASSERT(leftslot < parent->slotuse);
02420             BTREE_ASSERT(parent->childid[leftslot] == left);
02421             BTREE_ASSERT(parent->childid[leftslot+1] == right);
02422 
02423             BTREE_ASSERT(leftslot == parentslot);
02424         }
02425 
02426         // shift all slots in the right node
02427 
02428         BTREE_ASSERT(right->slotuse + shiftnum < leafslotmax);
02429 
02430         for(int i = right->slotuse; i >= 0; i--)
02431         {
02432             right->slotkey[i + shiftnum] = right->slotkey[i];
02433             right->slotdata[i + shiftnum] = right->slotdata[i];
02434         }
02435         right->slotuse += shiftnum;
02436 
02437         // copy the last items from the left node to the first slot in the right node.
02438         for(unsigned int i = 0; i < shiftnum; i++)
02439         {
02440             right->slotkey[i] = left->slotkey[left->slotuse - shiftnum + i];
02441             right->slotdata[i] = left->slotdata[left->slotuse - shiftnum + i];
02442         }
02443         left->slotuse -= shiftnum;
02444 
02445         parent->slotkey[parentslot] = left->slotkey[left->slotuse-1];
02446     }
02447 
02451     static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
02452     {
02453         BTREE_ASSERT(left->level == right->level);
02454         BTREE_ASSERT(parent->level == left->level + 1);
02455 
02456         BTREE_ASSERT(left->slotuse > right->slotuse);
02457         BTREE_ASSERT(parent->childid[parentslot] == left);
02458 
02459         unsigned int shiftnum = (left->slotuse - right->slotuse) / 2;
02460 
02461         BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "." << std::endl);
02462 
02463         if (selfverify)
02464         {
02465             // find the left node's slot in the parent's children
02466             unsigned int leftslot = 0;
02467             while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
02468                 ++leftslot;
02469 
02470             BTREE_ASSERT(leftslot < parent->slotuse);
02471             BTREE_ASSERT(parent->childid[leftslot] == left);
02472             BTREE_ASSERT(parent->childid[leftslot+1] == right);
02473 
02474             BTREE_ASSERT(leftslot == parentslot);
02475         }
02476 
02477         // shift all slots in the right node
02478 
02479         BTREE_ASSERT(right->slotuse + shiftnum < innerslotmax);
02480 
02481         right->childid[right->slotuse + shiftnum] = right->childid[right->slotuse];
02482         for(int i = right->slotuse-1; i >= 0; i--)
02483         {
02484             right->slotkey[i + shiftnum] = right->slotkey[i];
02485             right->childid[i + shiftnum] = right->childid[i];
02486         }
02487 
02488         right->slotuse += shiftnum;
02489 
02490         // copy the parent's decision slotkey and childid to the last new key on the right
02491         right->slotkey[shiftnum - 1] = parent->slotkey[parentslot];
02492         right->childid[shiftnum - 1] = left->childid[left->slotuse];
02493 
02494         // copy the remaining last items from the left node to the first slot in the right node.
02495         for(unsigned int i = 0; i < shiftnum - 1; i++)
02496         {
02497             right->slotkey[i] = left->slotkey[left->slotuse - shiftnum + i + 1];
02498             right->childid[i] = left->childid[left->slotuse - shiftnum + i + 1];
02499         }
02500 
02501         // copy the first to-be-removed key from the left node to the parent's decision slot
02502         parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum];
02503 
02504         left->slotuse -= shiftnum;
02505     }
02506 
02507 #ifdef BTREE_DEBUG
02508 public:
02509     // *** Debug Printing
02510 
02514     void print(std::ostream &os) const
02515     {
02516         if (root) {
02517             print_node(os, root, 0, true);
02518         }
02519     }
02520 
02522     void print_leaves(std::ostream &os) const
02523     {
02524         os << "leaves:" << std::endl;
02525 
02526         const leaf_node *n = headleaf;
02527 
02528         while(n)
02529         {
02530             os << "  " << n << std::endl;
02531 
02532             n = n->nextleaf;
02533         }
02534     }
02535 
02536 private:
02537 
02539     static void print_node(std::ostream &os, const node* node, unsigned int depth=0, bool recursive=false)
02540     {
02541         for(unsigned int i = 0; i < depth; i++) os << "  ";
02542 
02543         os << "node " << node << " level " << node->level << " slotuse " << node->slotuse << std::endl;
02544 
02545         if (node->isleafnode())
02546         {
02547             const leaf_node *leafnode = static_cast<const leaf_node*>(node);
02548 
02549             for(unsigned int i = 0; i < depth; i++) os << "  ";
02550             os << "  leaf prev " << leafnode->prevleaf << " next " << leafnode->nextleaf << std::endl;
02551 
02552             for(unsigned int i = 0; i < depth; i++) os << "  ";
02553 
02554             for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
02555             {
02556                 os << leafnode->slotkey[slot] << "  "; // << "(data: " << leafnode->slotdata[slot] << ") ";
02557             }
02558             os << std::endl;
02559         }
02560         else
02561         {
02562             const inner_node *innernode = static_cast<const inner_node*>(node);
02563 
02564             for(unsigned int i = 0; i < depth; i++) os << "  ";
02565 
02566             for (unsigned short slot = 0; slot < innernode->slotuse; ++slot)
02567             {
02568                 os << "(" << innernode->childid[slot] << ") " << innernode->slotkey[slot] << " ";
02569             }
02570             os << "(" << innernode->childid[innernode->slotuse] << ")" << std::endl;
02571 
02572             if (recursive)
02573             {
02574                 for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
02575                 {
02576                     print_node(os, innernode->childid[slot], depth + 1, recursive);
02577                 }
02578             }
02579         }
02580     }
02581 #endif
02582 
02583 public:
02584     // *** Verification of B+ Tree Invariants
02585 
02588     void verify() const
02589     {
02590         key_type minkey, maxkey;
02591         tree_stats vstats;
02592 
02593         if (root)
02594         {
02595             verify_node(root, &minkey, &maxkey, vstats);
02596 
02597             assert( vstats.itemcount == stats.itemcount );
02598             assert( vstats.leaves == stats.leaves );
02599             assert( vstats.innernodes == stats.innernodes );
02600         }
02601 
02602         verify_leaflinks();
02603     }
02604 
02605 private:
02606 
02608     void verify_node(const node* n, key_type* minkey, key_type* maxkey, tree_stats &vstats) const
02609     {
02610         BTREE_PRINT("verifynode " << n << std::endl);
02611 
02612         if (n->isleafnode())
02613         {
02614             const leaf_node *leaf = static_cast<const leaf_node*>(n);
02615 
02616             assert(leaf == root || !leaf->isunderflow());
02617 
02618             for(unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot)
02619             {
02620                 assert(key_lessequal(leaf->slotkey[slot], leaf->slotkey[slot + 1]));
02621             }
02622 
02623             *minkey = leaf->slotkey[0];
02624             *maxkey = leaf->slotkey[leaf->slotuse - 1];
02625 
02626             vstats.leaves++;
02627             vstats.itemcount += leaf->slotuse;
02628         }
02629         else // !n->isleafnode()
02630         {
02631             const inner_node *inner = static_cast<const inner_node*>(n);
02632             vstats.innernodes++;
02633 
02634             assert(inner == root || !inner->isunderflow());
02635 
02636             for(unsigned short slot = 0; slot < inner->slotuse - 1; ++slot)
02637             {
02638                 assert(key_lessequal(inner->slotkey[slot], inner->slotkey[slot + 1]));
02639             }
02640 
02641             for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
02642             {
02643                 const node *subnode = inner->childid[slot];
02644                 key_type subminkey = key_type();
02645                 key_type submaxkey = key_type();
02646 
02647                 assert(subnode->level + 1 == inner->level);
02648                 verify_node(subnode, &subminkey, &submaxkey, vstats);
02649 
02650                 BTREE_PRINT("verify subnode " << subnode << ": " << subminkey << " - " << submaxkey << std::endl);
02651 
02652                 if (slot == 0)
02653                     *minkey = subminkey;
02654                 else
02655                     assert(key_greaterequal(subminkey, inner->slotkey[slot-1]));
02656 
02657                 if (slot == inner->slotuse)
02658                     *maxkey = submaxkey;
02659                 else
02660                     assert(key_equal(inner->slotkey[slot], submaxkey));
02661 
02662                 if (inner->level == 1 && slot < inner->slotuse)
02663                 {
02664                     // children are leaves and must be linked together in the
02665                     // correct order
02666                     const leaf_node *leafa = static_cast<const leaf_node*>(inner->childid[slot]);
02667                     const leaf_node *leafb = static_cast<const leaf_node*>(inner->childid[slot + 1]);
02668 
02669                     assert(leafa->nextleaf == leafb);
02670                     assert(leafa == leafb->prevleaf);
02671                     (void)leafa; (void)leafb;
02672                 }
02673                 if (inner->level == 2 && slot < inner->slotuse)
02674                 {
02675                     // verify leaf links between the adjacent inner nodes
02676                     const inner_node *parenta = static_cast<const inner_node*>(inner->childid[slot]);
02677                     const inner_node *parentb = static_cast<const inner_node*>(inner->childid[slot+1]);
02678 
02679                     const leaf_node *leafa = static_cast<const leaf_node*>(parenta->childid[parenta->slotuse]);
02680                     const leaf_node *leafb = static_cast<const leaf_node*>(parentb->childid[0]);
02681 
02682                     assert(leafa->nextleaf == leafb);
02683                     assert(leafa == leafb->prevleaf);
02684                     (void)leafa; (void)leafb;
02685                 }
02686             }
02687         }
02688     }
02689 
02691     void verify_leaflinks() const
02692     {
02693         const leaf_node *n = headleaf;
02694 
02695         assert(n->level == 0);
02696         assert(!n || n->prevleaf == NULL);
02697 
02698         unsigned int testcount = 0;
02699 
02700         while(n)
02701         {
02702             assert(n->level == 0);
02703 
02704             for(unsigned short slot = 0; slot < n->slotuse - 1; ++slot)
02705             {
02706                 assert(key_lessequal(n->slotkey[slot], n->slotkey[slot + 1]));
02707             }
02708 
02709             testcount += n->slotuse;
02710 
02711             if (n->nextleaf)
02712             {
02713                 assert(key_lessequal(n->slotkey[n->slotuse-1], n->nextleaf->slotkey[0]));
02714 
02715                 assert(n == n->nextleaf->prevleaf);
02716             }
02717             else
02718             {
02719                 assert(tailleaf == n);
02720             }
02721 
02722             n = n->nextleaf;
02723         }
02724 
02725         assert(testcount == size());
02726     }
02727 
02728 private:
02729     // *** Dump and Restore of B+ Trees
02730 
02734     struct dump_header
02735     {
02737         char            signature[12];
02738 
02740         unsigned short  version;
02741 
02743         unsigned short  key_type_size;
02744 
02746         unsigned short  data_type_size;
02747 
02749         unsigned short  leafslots;
02750 
02752         unsigned short  innerslots;
02753 
02755         bool            allow_duplicates;
02756 
02758         size_type       itemcount;
02759 
02762         inline void fill()
02763         {
02764             // don't want to include string.h just for this signature
02765             *reinterpret_cast<unsigned int*>(signature+0) = 0x2d787473;
02766             *reinterpret_cast<unsigned int*>(signature+4) = 0x65727462;
02767             *reinterpret_cast<unsigned int*>(signature+8) = 0x00000065;
02768 
02769             version = 0;
02770             key_type_size = sizeof(typename btree_self::key_type);
02771             data_type_size = sizeof(typename btree_self::data_type);
02772             leafslots = btree_self::leafslotmax;
02773             innerslots = btree_self::innerslotmax;
02774             allow_duplicates = btree_self::allow_duplicates;
02775         }
02776 
02778         inline bool same(const struct dump_header &o) const
02779         {
02780             return (*reinterpret_cast<const unsigned int*>(signature+0) ==
02781                     *reinterpret_cast<const unsigned int*>(o.signature+0))
02782                 && (*reinterpret_cast<const unsigned int*>(signature+4) ==
02783                     *reinterpret_cast<const unsigned int*>(o.signature+4))
02784                 && (*reinterpret_cast<const unsigned int*>(signature+8) ==
02785                     *reinterpret_cast<const unsigned int*>(o.signature+8))
02786 
02787                 && (version == o.version)
02788                 && (key_type_size == o.key_type_size)
02789                 && (data_type_size == o.data_type_size)
02790                 && (leafslots == o.leafslots)
02791                 && (innerslots == o.innerslots)
02792                 && (allow_duplicates == o.allow_duplicates);
02793         }
02794     };
02795 
02796 public:
02797 
02802     void dump(std::ostream &os) const
02803     {
02804         struct dump_header header;
02805         header.fill();
02806         header.itemcount = size();
02807 
02808         os.write(reinterpret_cast<char*>(&header), sizeof(header));
02809 
02810         if (root)
02811             dump_node(os, root);
02812     }
02813 
02818     bool restore(std::istream &is)
02819     {
02820         struct dump_header fileheader;
02821         is.read(reinterpret_cast<char*>(&fileheader), sizeof(fileheader));
02822         if (!is.good()) return false;
02823 
02824         struct dump_header myheader;
02825         myheader.fill();
02826         myheader.itemcount = fileheader.itemcount;
02827 
02828         if (!myheader.same(fileheader))
02829         {
02830             BTREE_PRINT("btree::restore: file header does not match instantiation signature." << std::endl);
02831             return false;
02832         }
02833 
02834         clear();
02835 
02836         if (fileheader.itemcount > 0)
02837         {
02838             root = restore_node(is);
02839             if (root == NULL) return false;
02840 
02841             stats.itemcount = fileheader.itemcount;
02842         }
02843 
02844 #ifdef BTREE_DEBUG
02845         if (debug) print(std::cout);
02846 #endif
02847         if (selfverify) verify();
02848 
02849         return true;
02850     }
02851 
02852 private:
02853 
02855     void dump_node(std::ostream &os, const node* n) const
02856     {
02857         BTREE_PRINT("dump_node " << n << std::endl);
02858 
02859         if (n->isleafnode())
02860         {
02861             const leaf_node *leaf = static_cast<const leaf_node*>(n);
02862 
02863             os.write(reinterpret_cast<const char*>(leaf), sizeof(*leaf));
02864         }
02865         else // !n->isleafnode()
02866         {
02867             const inner_node *inner = static_cast<const inner_node*>(n);
02868 
02869             os.write(reinterpret_cast<const char*>(inner), sizeof(*inner));
02870 
02871             for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
02872             {
02873                 const node *subnode = inner->childid[slot];
02874 
02875                 dump_node(os, subnode);
02876             }
02877         }
02878     }
02879 
02882     node* restore_node(std::istream &is)
02883     {
02884         union {
02885             node        top;
02886             leaf_node   leaf;
02887             inner_node  inner;
02888         } nu;
02889 
02890         // first read only the top of the node
02891         is.read(reinterpret_cast<char*>(&nu.top), sizeof(nu.top));
02892         if (!is.good()) return NULL;
02893 
02894         if (nu.top.isleafnode())
02895         {
02896             // read remaining data of leaf node
02897             is.read(reinterpret_cast<char*>(&nu.leaf) + sizeof(nu.top), sizeof(nu.leaf) - sizeof(nu.top));
02898             if (!is.good()) return NULL;
02899 
02900             leaf_node *newleaf = allocate_leaf();
02901 
02902             // copy over all data, the leaf nodes contain only their double linked list pointers
02903             *newleaf = nu.leaf;
02904 
02905             // reconstruct the linked list from the order in the file
02906             if (headleaf == NULL) {
02907                 BTREE_ASSERT(newleaf->prevleaf == NULL);
02908                 headleaf = tailleaf = newleaf;
02909             }
02910             else {
02911                 newleaf->prevleaf = tailleaf;
02912                 tailleaf->nextleaf = newleaf;
02913                 tailleaf = newleaf;
02914             }
02915 
02916             return newleaf;
02917         }
02918         else
02919         {
02920             // read remaining data of inner node
02921             is.read(reinterpret_cast<char*>(&nu.inner) + sizeof(nu.top), sizeof(nu.inner) - sizeof(nu.top));
02922             if (!is.good()) return NULL;
02923 
02924             inner_node *newinner = allocate_inner(0);
02925 
02926             // copy over all data, the inner nodes contain only pointers to their children
02927             *newinner = nu.inner;
02928 
02929             for(unsigned short slot = 0; slot <= newinner->slotuse; ++slot)
02930             {
02931                 newinner->childid[slot] = restore_node(is);
02932             }
02933 
02934             return newinner;
02935         }
02936     }
02937 };
02938 
02939 } // namespace stx
02940 
02941 #endif // _STX_BTREE_H_

Generated on Fri Jan 25 13:53:43 2008 for STX B+ Tree Template Classes by  doxygen 1.5.4