Stxxl 1.2.1
|
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 */