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