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
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
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
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