iterator_map.h

00001 /***************************************************************************
00002  *  include/stxxl/bits/containers/btree/iterator_map.h
00003  *
00004  *  Part of the STXXL. See http://stxxl.sourceforge.net
00005  *
00006  *  Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de>
00007  *
00008  *  Distributed under the Boost Software License, Version 1.0.
00009  *  (See accompanying file LICENSE_1_0.txt or copy at
00010  *  http://www.boost.org/LICENSE_1_0.txt)
00011  **************************************************************************/
00012 
00013 #ifndef STXXL_CONTAINERS_BTREE__ITERATOR_MAP_H
00014 #define STXXL_CONTAINERS_BTREE__ITERATOR_MAP_H
00015 
00016 #include <map>
00017 
00018 #include <stxxl/bits/noncopyable.h>
00019 #include <stxxl/bits/containers/btree/iterator.h>
00020 
00021 
00022 __STXXL_BEGIN_NAMESPACE
00023 
00024 namespace btree
00025 {
00026     template <class BTreeType>
00027     class iterator_map : private noncopyable
00028     {
00029     public:
00030         typedef BTreeType btree_type;
00031         typedef typename btree_type::leaf_bid_type bid_type;
00032         typedef btree_iterator_base<btree_type> iterator_base;
00033 
00034     private:
00035         struct Key
00036         {
00037             bid_type bid;
00038             unsigned pos;
00039             Key() { }
00040             Key(const bid_type & b, unsigned p) : bid(b), pos(p) { }
00041         };
00042 
00043         struct bid_comp
00044         {
00045             bool operator () (const bid_type & a, const bid_type & b) const
00046             {
00047                 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
00048             }
00049         };
00050         struct KeyCmp
00051         {
00052             bid_comp BIDComp;
00053             bool operator () (const Key & a, const Key & b) const
00054             {
00055                 return BIDComp(a.bid, b.bid) || (a.bid == b.bid && a.pos < b.pos);
00056             }
00057         };
00058 
00059         typedef std::multimap<Key, iterator_base *, KeyCmp> multimap_type;
00060 
00061         multimap_type It2Addr_;
00062         btree_type * btree_;
00063 
00064         typedef typename multimap_type::value_type pair_type;
00065         typedef typename multimap_type::iterator mmiterator_type;
00066         typedef typename multimap_type::const_iterator mmconst_iterator_type;
00067 
00068 
00069         // changes btree pointer in all contained iterators
00070         void change_btree_pointers(btree_type * b)
00071         {
00072             mmconst_iterator_type it = It2Addr_.begin();
00073             for ( ; it != It2Addr_.end(); ++it)
00074             {
00075                 (it->second)->btree_ = b;
00076             }
00077         }
00078 
00079     public:
00080         iterator_map(btree_type * b) : btree_(b)
00081         { }
00082 
00083         void register_iterator(iterator_base & it)
00084         {
00085             STXXL_VERBOSE2("btree::iterator_map register_iterator addr=" << &it <<
00086                            " BID: " << it.bid << " POS: " << it.pos);
00087             It2Addr_.insert(pair_type(Key(it.bid, it.pos), &it));
00088         }
00089         void unregister_iterator(iterator_base & it)
00090         {
00091             STXXL_VERBOSE2("btree::iterator_map unregister_iterator addr=" << &it <<
00092                            " BID: " << it.bid << " POS: " << it.pos);
00093             assert(!It2Addr_.empty());
00094             Key key(it.bid, it.pos);
00095             std::pair<mmiterator_type, mmiterator_type> range =
00096                 It2Addr_.equal_range(key);
00097 
00098             assert(range.first != range.second);
00099 
00100             mmiterator_type i = range.first;
00101             for ( ; i != range.second; ++i)
00102             {
00103                 assert(it.bid == (*i).first.bid);
00104                 assert(it.pos == (*i).first.pos);
00105 
00106                 if ((*i).second == &it)
00107                 {
00108                     // found it
00109                     It2Addr_.erase(i);
00110                     return;
00111                 }
00112             }
00113 
00114             STXXL_THROW(std::runtime_error, "unregister_iterator", "Panic in btree::iterator_map, can not find and unregister iterator");
00115         }
00116         template <class OutputContainer>
00117         void find(const bid_type & bid,
00118                   unsigned first_pos,
00119                   unsigned last_pos,
00120                   OutputContainer & out
00121                   )
00122         {
00123             Key firstkey(bid, first_pos);
00124             Key lastkey(bid, last_pos);
00125             mmconst_iterator_type begin = It2Addr_.lower_bound(firstkey);
00126             mmconst_iterator_type end = It2Addr_.upper_bound(lastkey);
00127 
00128             mmconst_iterator_type i = begin;
00129             for ( ; i != end; ++i)
00130             {
00131                 assert(bid == (*i).first.bid);
00132                 out.push_back((*i).second);
00133             }
00134         }
00135 
00136         virtual ~iterator_map()
00137         {
00138             mmconst_iterator_type it = It2Addr_.begin();
00139             for ( ; it != It2Addr_.end(); ++it)
00140                 (it->second)->make_invalid();
00141         }
00142 
00143         void swap(iterator_map & obj)
00144         {
00145             std::swap(It2Addr_, obj.It2Addr_);
00146             change_btree_pointers(btree_);
00147             obj.change_btree_pointers(obj.btree_);
00148         }
00149     };
00150 }
00151 
00152 __STXXL_END_NAMESPACE
00153 
00154 
00155 namespace std
00156 {
00157     template <class BTreeType>
00158     void swap(stxxl::btree::iterator_map<BTreeType> & a,
00159               stxxl::btree::iterator_map<BTreeType> & b)
00160     {
00161         a.swap(b);
00162     }
00163 }
00164 
00165 #endif /* STXXL_CONTAINERS_BTREE__ITERATOR_MAP_H */

Generated on Thu Jun 4 10:21:45 2009 for Stxxl by  doxygen 1.4.7