13 #ifndef STXXL_CONTAINERS_BTREE__ITERATOR_H
14 #define STXXL_CONTAINERS_BTREE__ITERATOR_H
16 #include <stxxl/bits/common/utils.h>
19 __STXXL_BEGIN_NAMESPACE
24 template <
class BTreeType>
26 template <
class BTreeType>
28 template <
class BTreeType>
29 class btree_const_iterator;
30 template <
class KeyType_,
class DataType_,
class KeyCmp_,
unsigned LogNElem_,
class BTreeType>
33 template <
class BTreeType>
34 class btree_iterator_base
37 typedef BTreeType btree_type;
38 typedef typename btree_type::leaf_bid_type bid_type;
39 typedef typename btree_type::value_type value_type;
40 typedef typename btree_type::reference reference;
41 typedef typename btree_type::const_reference const_reference;
42 typedef std::bidirectional_iterator_tag iterator_category;
43 typedef typename btree_type::difference_type difference_type;
45 friend class iterator_map<btree_type>;
46 template <
class KeyType_,
class DataType_,
47 class KeyCmp_,
unsigned LogNElem_,
class BTreeType__>
48 friend class normal_leaf;
50 template <
class BTreeType_>
51 friend bool operator == (
const btree_iterator<BTreeType_> & a,
52 const btree_const_iterator<BTreeType_> & b);
53 template <
class BTreeType_>
54 friend bool operator != (
const btree_iterator<BTreeType_> & a,
55 const btree_const_iterator<BTreeType_> & b);
64 STXXL_VERBOSE3(
"btree_iterator_base def construct addr=" <<
this);
72 ) : btree_(btree__), bid(b), pos(p)
74 STXXL_VERBOSE3(
"btree_iterator_base parameter construct addr=" <<
this);
75 btree_->iterator_map_.register_iterator(*
this);
83 btree_iterator_base(
const btree_iterator_base & obj)
85 STXXL_VERBOSE3(
"btree_iterator_base constr from" << (&obj) <<
" to " <<
this);
90 btree_->iterator_map_.register_iterator(*
this);
93 btree_iterator_base & operator = (
const btree_iterator_base & obj)
95 STXXL_VERBOSE3(
"btree_iterator_base copy from" << (&obj) <<
" to " <<
this);
99 btree_->iterator_map_.unregister_iterator(*
this);
105 btree_->iterator_map_.register_iterator(*
this);
110 reference non_const_access()
113 typename btree_type::leaf_type * Leaf = btree_->leaf_cache_.get_node(bid);
115 return (reference)((*Leaf)[pos]);
118 const_reference const_access()
const
121 typename btree_type::leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node(bid);
123 return (reference)((*Leaf)[pos]);
126 bool operator == (
const btree_iterator_base & obj)
const
128 return bid == obj.bid && pos == obj.pos && btree_ == obj.btree_;
131 bool operator != (
const btree_iterator_base & obj)
const
133 return bid != obj.bid || pos != obj.pos || btree_ != obj.btree_;
136 btree_iterator_base & increment()
139 bid_type cur_bid = bid;
140 typename btree_type::leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node(bid,
true);
142 Leaf->increment_iterator(*
this);
143 btree_->leaf_cache_.unfix_node(cur_bid);
147 btree_iterator_base & decrement()
150 bid_type cur_bid = bid;
151 typename btree_type::leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node(bid,
true);
153 Leaf->decrement_iterator(*
this);
154 btree_->leaf_cache_.unfix_node(cur_bid);
159 virtual ~btree_iterator_base()
161 STXXL_VERBOSE3(
"btree_iterator_base deconst " <<
this);
163 btree_->iterator_map_.unregister_iterator(*
this);
167 template <
class BTreeType>
168 class btree_iterator :
public btree_iterator_base<BTreeType>
171 typedef BTreeType btree_type;
172 typedef typename btree_type::leaf_bid_type bid_type;
173 typedef typename btree_type::value_type value_type;
174 typedef typename btree_type::reference reference;
175 typedef typename btree_type::const_reference const_reference;
176 typedef typename btree_type::pointer pointer;
178 template <
class KeyType_,
class DataType_,
179 class KeyCmp_,
unsigned LogNElem_,
class BTreeType__>
180 friend class normal_leaf;
182 using btree_iterator_base<btree_type>::non_const_access;
184 btree_iterator() : btree_iterator_base<btree_type>()
187 btree_iterator(
const btree_iterator & obj) :
188 btree_iterator_base<btree_type>(obj)
191 btree_iterator & operator = (
const btree_iterator & obj)
193 btree_iterator_base<btree_type>::operator = (obj);
197 reference operator * ()
199 return non_const_access();
202 pointer operator -> ()
204 return &(non_const_access());
207 bool operator == (
const btree_iterator & obj)
const
209 return btree_iterator_base<btree_type>::operator == (obj);
212 bool operator != (
const btree_iterator & obj)
const
214 return btree_iterator_base<btree_type>::operator != (obj);
217 btree_iterator & operator ++ ()
219 assert(*
this != btree_iterator_base<btree_type>::btree_->end());
220 btree_iterator_base<btree_type>::increment();
224 btree_iterator & operator -- ()
226 btree_iterator_base<btree_type>::decrement();
230 btree_iterator operator ++ (
int)
232 assert(*
this != btree_iterator_base<btree_type>::btree_->end());
233 btree_iterator result(*
this);
234 btree_iterator_base<btree_type>::increment();
238 btree_iterator operator -- (
int)
240 btree_iterator result(*
this);
241 btree_iterator_base<btree_type>::decrement();
247 btree_type * btree__,
250 ) : btree_iterator_base<btree_type>(btree__, b, p)
254 template <
class BTreeType>
255 class btree_const_iterator :
public btree_iterator_base<BTreeType>
258 typedef btree_iterator<BTreeType> iterator;
260 typedef BTreeType btree_type;
261 typedef typename btree_type::leaf_bid_type bid_type;
262 typedef typename btree_type::value_type value_type;
263 typedef typename btree_type::const_reference reference;
264 typedef typename btree_type::const_pointer pointer;
266 template <
class KeyType_,
class DataType_,
267 class KeyCmp_,
unsigned LogNElem_,
class BTreeType__>
268 friend class normal_leaf;
270 using btree_iterator_base<btree_type>::const_access;
272 btree_const_iterator() : btree_iterator_base<btree_type>()
275 btree_const_iterator(
const btree_const_iterator & obj) :
276 btree_iterator_base<btree_type>(obj)
279 btree_const_iterator(
const iterator & obj) :
280 btree_iterator_base<btree_type>(obj)
283 btree_const_iterator & operator = (
const btree_const_iterator & obj)
285 btree_iterator_base<btree_type>::operator = (obj);
289 reference operator * ()
291 return const_access();
294 pointer operator -> ()
296 return &(const_access());
300 bool operator == (
const iterator & obj)
const
302 return btree_iterator_base<btree_type>::operator == (obj);
305 bool operator != (
const iterator & obj)
const
307 return btree_iterator_base<btree_type>::operator != (obj);
310 bool operator == (
const btree_const_iterator & obj)
const
312 return btree_iterator_base<btree_type>::operator == (obj);
315 bool operator != (
const btree_const_iterator & obj)
const
317 return btree_iterator_base<btree_type>::operator != (obj);
320 btree_const_iterator & operator ++ ()
322 assert(*
this != btree_iterator_base<btree_type>::btree_->end());
323 btree_iterator_base<btree_type>::increment();
327 btree_const_iterator & operator -- ()
329 btree_iterator_base<btree_type>::decrement();
333 btree_const_iterator operator ++ (
int)
335 assert(*
this != btree_iterator_base<btree_type>::btree_->end());
336 btree_const_iterator result(*
this);
337 btree_iterator_base<btree_type>::increment();
341 btree_const_iterator operator -- (
int)
343 btree_const_iterator result(*
this);
344 btree_iterator_base<btree_type>::decrement();
349 btree_const_iterator(
350 btree_type * btree__,
353 ) : btree_iterator_base<btree_type>(btree__, b, p)
357 template <
class BTreeType>
358 inline bool operator == (
const btree_iterator<BTreeType> & a,
359 const btree_const_iterator<BTreeType> & b)
361 return a.btree_iterator_base<BTreeType>::operator == (b);
364 template <
class BTreeType>
365 inline bool operator != (
const btree_iterator<BTreeType> & a,
366 const btree_const_iterator<BTreeType> & b)
368 return a.btree_iterator_base<BTreeType>::operator != (b);
372 __STXXL_END_NAMESPACE