13 #ifndef STXXL_CONTAINERS_BTREE__ITERATOR_MAP_H
14 #define STXXL_CONTAINERS_BTREE__ITERATOR_MAP_H
18 #include <stxxl/bits/noncopyable.h>
19 #include <stxxl/bits/containers/btree/iterator.h>
22 __STXXL_BEGIN_NAMESPACE
26 template <
class BTreeType>
27 class iterator_map :
private noncopyable
30 typedef BTreeType btree_type;
31 typedef typename btree_type::leaf_bid_type bid_type;
32 typedef btree_iterator_base<btree_type> iterator_base;
40 Key(
const bid_type & b,
unsigned p) : bid(b), pos(p) { }
45 bool operator () (
const bid_type & a,
const bid_type & b)
const
47 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
53 bool operator () (
const Key & a,
const Key & b)
const
55 return BIDComp(a.bid, b.bid) || (a.bid == b.bid && a.pos < b.pos);
59 typedef std::multimap<Key, iterator_base *, KeyCmp> multimap_type;
61 multimap_type It2Addr_;
64 typedef typename multimap_type::value_type pair_type;
65 typedef typename multimap_type::iterator mmiterator_type;
66 typedef typename multimap_type::const_iterator mmconst_iterator_type;
70 void change_btree_pointers(btree_type * b)
72 mmconst_iterator_type it = It2Addr_.begin();
73 for ( ; it != It2Addr_.end(); ++it)
75 (it->second)->btree_ = b;
80 iterator_map(btree_type * b) : btree_(b)
83 void register_iterator(iterator_base & it)
85 STXXL_VERBOSE2(
"btree::iterator_map register_iterator addr=" << &it <<
86 " BID: " << it.bid <<
" POS: " << it.pos);
87 It2Addr_.insert(pair_type(Key(it.bid, it.pos), &it));
89 void unregister_iterator(iterator_base & it)
91 STXXL_VERBOSE2(
"btree::iterator_map unregister_iterator addr=" << &it <<
92 " BID: " << it.bid <<
" POS: " << it.pos);
93 assert(!It2Addr_.empty());
94 Key key(it.bid, it.pos);
95 std::pair<mmiterator_type, mmiterator_type> range =
96 It2Addr_.equal_range(key);
98 assert(range.first != range.second);
100 mmiterator_type i = range.first;
101 for ( ; i != range.second; ++i)
103 assert(it.bid == (*i).first.bid);
104 assert(it.pos == (*i).first.pos);
106 if ((*i).second == &it)
114 STXXL_THROW(std::runtime_error,
"unregister_iterator",
"Panic in btree::iterator_map, can not find and unregister iterator");
116 template <
class OutputContainer>
117 void find(
const bid_type & bid,
120 OutputContainer & out
123 Key firstkey(bid, first_pos);
124 Key lastkey(bid, last_pos);
125 mmconst_iterator_type begin = It2Addr_.lower_bound(firstkey);
126 mmconst_iterator_type end = It2Addr_.upper_bound(lastkey);
128 mmconst_iterator_type i = begin;
129 for ( ; i != end; ++i)
131 assert(bid == (*i).first.bid);
132 out.push_back((*i).second);
136 virtual ~iterator_map()
138 mmconst_iterator_type it = It2Addr_.begin();
139 for ( ; it != It2Addr_.end(); ++it)
140 (it->second)->make_invalid();
143 void swap(iterator_map & obj)
145 std::swap(It2Addr_, obj.It2Addr_);
146 change_btree_pointers(btree_);
147 obj.change_btree_pointers(obj.btree_);
152 __STXXL_END_NAMESPACE
157 template <
class BTreeType>
158 void swap(stxxl::btree::iterator_map<BTreeType> & a,
159 stxxl::btree::iterator_map<BTreeType> & b)