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>
20 #include <stxxl/bits/common/error_handling.h>
23 __STXXL_BEGIN_NAMESPACE
27 template <
class BTreeType>
28 class iterator_map :
private noncopyable
31 typedef BTreeType btree_type;
32 typedef typename btree_type::leaf_bid_type bid_type;
33 typedef btree_iterator_base<btree_type> iterator_base;
41 Key(
const bid_type & b,
unsigned p) : bid(b), pos(p) { }
46 bool operator () (
const bid_type & a,
const bid_type & b)
const
48 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
54 bool operator () (
const Key & a,
const Key & b)
const
56 return BIDComp(a.bid, b.bid) || (a.bid == b.bid && a.pos < b.pos);
60 typedef std::multimap<Key, iterator_base *, KeyCmp> multimap_type;
62 multimap_type It2Addr_;
65 typedef typename multimap_type::value_type pair_type;
66 typedef typename multimap_type::iterator mmiterator_type;
67 typedef typename multimap_type::const_iterator mmconst_iterator_type;
71 void change_btree_pointers(btree_type * b)
73 mmconst_iterator_type it = It2Addr_.begin();
74 for ( ; it != It2Addr_.end(); ++it)
76 (it->second)->btree_ = b;
81 iterator_map(btree_type * b) : btree_(b)
84 void register_iterator(iterator_base & it)
86 STXXL_VERBOSE2(
"btree::iterator_map register_iterator addr=" << &it <<
87 " BID: " << it.bid <<
" POS: " << it.pos);
88 It2Addr_.insert(pair_type(Key(it.bid, it.pos), &it));
90 void unregister_iterator(iterator_base & it)
92 STXXL_VERBOSE2(
"btree::iterator_map unregister_iterator addr=" << &it <<
93 " BID: " << it.bid <<
" POS: " << it.pos);
94 assert(!It2Addr_.empty());
95 Key key(it.bid, it.pos);
96 std::pair<mmiterator_type, mmiterator_type> range =
97 It2Addr_.equal_range(key);
99 assert(range.first != range.second);
101 mmiterator_type i = range.first;
102 for ( ; i != range.second; ++i)
104 assert(it.bid == (*i).first.bid);
105 assert(it.pos == (*i).first.pos);
107 if ((*i).second == &it)
115 STXXL_THROW(std::runtime_error,
"unregister_iterator",
"Panic in btree::iterator_map, can not find and unregister iterator");
117 template <
class OutputContainer>
118 void find(
const bid_type & bid,
121 OutputContainer & out
124 Key firstkey(bid, first_pos);
125 Key lastkey(bid, last_pos);
126 mmconst_iterator_type begin = It2Addr_.lower_bound(firstkey);
127 mmconst_iterator_type end = It2Addr_.upper_bound(lastkey);
129 mmconst_iterator_type i = begin;
130 for ( ; i != end; ++i)
132 assert(bid == (*i).first.bid);
133 out.push_back((*i).second);
137 virtual ~iterator_map()
139 mmconst_iterator_type it = It2Addr_.begin();
140 for ( ; it != It2Addr_.end(); ++it)
141 (it->second)->make_invalid();
144 void swap(iterator_map & obj)
146 std::swap(It2Addr_, obj.It2Addr_);
147 change_btree_pointers(btree_);
148 obj.change_btree_pointers(obj.btree_);
153 __STXXL_END_NAMESPACE
158 template <
class BTreeType>
159 void swap(stxxl::btree::iterator_map<BTreeType> & a,
160 stxxl::btree::iterator_map<BTreeType> & b)
_ExtIterator find(_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable &_value, int_type nbuffers)
External equivalent of std::find.
Definition: scan.h:215