Stxxl  1.3.2
iterator.h
1 /***************************************************************************
2  * include/stxxl/bits/containers/btree/iterator.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <[email protected]>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_CONTAINERS_BTREE__ITERATOR_H
14 #define STXXL_CONTAINERS_BTREE__ITERATOR_H
15 
16 #include <iterator>
17 #include <cassert>
18 #include <stxxl/bits/verbose.h>
19 
20 
21 __STXXL_BEGIN_NAMESPACE
22 
23 
24 namespace btree
25 {
26  template <class BTreeType>
27  class iterator_map;
28  template <class BTreeType>
29  class btree_iterator;
30  template <class BTreeType>
31  class btree_const_iterator;
32  template <class KeyType_, class DataType_, class KeyCmp_, unsigned LogNElem_, class BTreeType>
33  class normal_leaf;
34 
35  template <class BTreeType>
36  class btree_iterator_base
37  {
38  public:
39  typedef BTreeType btree_type;
40  typedef typename btree_type::leaf_bid_type bid_type;
41  typedef typename btree_type::value_type value_type;
42  typedef typename btree_type::reference reference;
43  typedef typename btree_type::const_reference const_reference;
44  typedef std::bidirectional_iterator_tag iterator_category;
45  typedef typename btree_type::difference_type difference_type;
46 
47  friend class iterator_map<btree_type>;
48  template <class KeyType_, class DataType_,
49  class KeyCmp_, unsigned LogNElem_, class BTreeType__>
50  friend class normal_leaf;
51 
52  template <class BTreeType_>
53  friend bool operator == (const btree_iterator<BTreeType_> & a,
54  const btree_const_iterator<BTreeType_> & b);
55  template <class BTreeType_>
56  friend bool operator != (const btree_iterator<BTreeType_> & a,
57  const btree_const_iterator<BTreeType_> & b);
58 
59  protected:
60  btree_type * btree_;
61  bid_type bid;
62  unsigned pos;
63 
64  btree_iterator_base()
65  {
66  STXXL_VERBOSE3("btree_iterator_base def construct addr=" << this);
67  make_invalid();
68  }
69 
70  btree_iterator_base(
71  btree_type * btree__,
72  const bid_type & b,
73  unsigned p
74  ) : btree_(btree__), bid(b), pos(p)
75  {
76  STXXL_VERBOSE3("btree_iterator_base parameter construct addr=" << this);
77  btree_->iterator_map_.register_iterator(*this);
78  }
79 
80  void make_invalid()
81  {
82  btree_ = NULL;
83  }
84 
85  btree_iterator_base(const btree_iterator_base & obj)
86  {
87  STXXL_VERBOSE3("btree_iterator_base constr from" << (&obj) << " to " << this);
88  btree_ = obj.btree_;
89  bid = obj.bid;
90  pos = obj.pos;
91  if (btree_)
92  btree_->iterator_map_.register_iterator(*this);
93  }
94 
95  btree_iterator_base & operator = (const btree_iterator_base & obj)
96  {
97  STXXL_VERBOSE3("btree_iterator_base copy from" << (&obj) << " to " << this);
98  if (&obj != this)
99  {
100  if (btree_)
101  btree_->iterator_map_.unregister_iterator(*this);
102 
103  btree_ = obj.btree_;
104  bid = obj.bid;
105  pos = obj.pos;
106  if (btree_)
107  btree_->iterator_map_.register_iterator(*this);
108  }
109  return *this;
110  }
111 
112  reference non_const_access()
113  {
114  assert(btree_);
115  typename btree_type::leaf_type * Leaf = btree_->leaf_cache_.get_node(bid);
116  assert(Leaf);
117  return (reference)((*Leaf)[pos]);
118  }
119 
120  const_reference const_access() const
121  {
122  assert(btree_);
123  typename btree_type::leaf_type const * Leaf = btree_->leaf_cache_.get_const_node(bid);
124  assert(Leaf);
125  return (reference)((*Leaf)[pos]);
126  }
127 
128  bool operator == (const btree_iterator_base & obj) const
129  {
130  return bid == obj.bid && pos == obj.pos && btree_ == obj.btree_;
131  }
132 
133  bool operator != (const btree_iterator_base & obj) const
134  {
135  return bid != obj.bid || pos != obj.pos || btree_ != obj.btree_;
136  }
137 
138  btree_iterator_base & increment()
139  {
140  assert(btree_);
141  bid_type cur_bid = bid;
142  typename btree_type::leaf_type const * Leaf = btree_->leaf_cache_.get_const_node(bid, true);
143  assert(Leaf);
144  Leaf->increment_iterator(*this);
145  btree_->leaf_cache_.unfix_node(cur_bid);
146  return *this;
147  }
148 
149  btree_iterator_base & decrement()
150  {
151  assert(btree_);
152  bid_type cur_bid = bid;
153  typename btree_type::leaf_type const * Leaf = btree_->leaf_cache_.get_const_node(bid, true);
154  assert(Leaf);
155  Leaf->decrement_iterator(*this);
156  btree_->leaf_cache_.unfix_node(cur_bid);
157  return *this;
158  }
159 
160  public:
161  virtual ~btree_iterator_base()
162  {
163  STXXL_VERBOSE3("btree_iterator_base deconst " << this);
164  if (btree_)
165  btree_->iterator_map_.unregister_iterator(*this);
166  }
167  };
168 
169  template <class BTreeType>
170  class btree_iterator : public btree_iterator_base<BTreeType>
171  {
172  public:
173  typedef BTreeType btree_type;
174  typedef typename btree_type::leaf_bid_type bid_type;
175  typedef typename btree_type::value_type value_type;
176  typedef typename btree_type::reference reference;
177  typedef typename btree_type::const_reference const_reference;
178  typedef typename btree_type::pointer pointer;
179 
180  template <class KeyType_, class DataType_,
181  class KeyCmp_, unsigned LogNElem_, class BTreeType__>
182  friend class normal_leaf;
183 
184  using btree_iterator_base<btree_type>::non_const_access;
185 
186  btree_iterator() : btree_iterator_base<btree_type>()
187  { }
188 
189  btree_iterator(const btree_iterator & obj) :
190  btree_iterator_base<btree_type>(obj)
191  { }
192 
193  btree_iterator & operator = (const btree_iterator & obj)
194  {
195  btree_iterator_base<btree_type>::operator = (obj);
196  return *this;
197  }
198 
199  reference operator * ()
200  {
201  return non_const_access();
202  }
203 
204  pointer operator -> ()
205  {
206  return &(non_const_access());
207  }
208 
209  bool operator == (const btree_iterator & obj) const
210  {
211  return btree_iterator_base<btree_type>::operator == (obj);
212  }
213 
214  bool operator != (const btree_iterator & obj) const
215  {
216  return btree_iterator_base<btree_type>::operator != (obj);
217  }
218 
219  btree_iterator & operator ++ ()
220  {
221  assert(*this != btree_iterator_base<btree_type>::btree_->end());
222  btree_iterator_base<btree_type>::increment();
223  return *this;
224  }
225 
226  btree_iterator & operator -- ()
227  {
228  btree_iterator_base<btree_type>::decrement();
229  return *this;
230  }
231 
232  btree_iterator operator ++ (int)
233  {
234  assert(*this != btree_iterator_base<btree_type>::btree_->end());
235  btree_iterator result(*this);
236  btree_iterator_base<btree_type>::increment();
237  return result;
238  }
239 
240  btree_iterator operator -- (int)
241  {
242  btree_iterator result(*this);
243  btree_iterator_base<btree_type>::decrement();
244  return result;
245  }
246 
247  private:
248  btree_iterator(
249  btree_type * btree__,
250  const bid_type & b,
251  unsigned p
252  ) : btree_iterator_base<btree_type>(btree__, b, p)
253  { }
254  };
255 
256  template <class BTreeType>
257  class btree_const_iterator : public btree_iterator_base<BTreeType>
258  {
259  public:
260  typedef btree_iterator<BTreeType> iterator;
261 
262  typedef BTreeType btree_type;
263  typedef typename btree_type::leaf_bid_type bid_type;
264  typedef typename btree_type::value_type value_type;
265  typedef typename btree_type::const_reference reference;
266  typedef typename btree_type::const_pointer pointer;
267 
268  template <class KeyType_, class DataType_,
269  class KeyCmp_, unsigned LogNElem_, class BTreeType__>
270  friend class normal_leaf;
271 
272  using btree_iterator_base<btree_type>::const_access;
273 
274  btree_const_iterator() : btree_iterator_base<btree_type>()
275  { }
276 
277  btree_const_iterator(const btree_const_iterator & obj) :
278  btree_iterator_base<btree_type>(obj)
279  { }
280 
281  btree_const_iterator(const iterator & obj) :
282  btree_iterator_base<btree_type>(obj)
283  { }
284 
285  btree_const_iterator & operator = (const btree_const_iterator & obj)
286  {
287  btree_iterator_base<btree_type>::operator = (obj);
288  return *this;
289  }
290 
291  reference operator * ()
292  {
293  return const_access();
294  }
295 
296  pointer operator -> ()
297  {
298  return &(const_access());
299  }
300 
301 
302  bool operator == (const iterator & obj) const
303  {
304  return btree_iterator_base<btree_type>::operator == (obj);
305  }
306 
307  bool operator != (const iterator & obj) const
308  {
309  return btree_iterator_base<btree_type>::operator != (obj);
310  }
311 
312  bool operator == (const btree_const_iterator & obj) const
313  {
314  return btree_iterator_base<btree_type>::operator == (obj);
315  }
316 
317  bool operator != (const btree_const_iterator & obj) const
318  {
319  return btree_iterator_base<btree_type>::operator != (obj);
320  }
321 
322  btree_const_iterator & operator ++ ()
323  {
324  assert(*this != btree_iterator_base<btree_type>::btree_->end());
325  btree_iterator_base<btree_type>::increment();
326  return *this;
327  }
328 
329  btree_const_iterator & operator -- ()
330  {
331  btree_iterator_base<btree_type>::decrement();
332  return *this;
333  }
334 
335  btree_const_iterator operator ++ (int)
336  {
337  assert(*this != btree_iterator_base<btree_type>::btree_->end());
338  btree_const_iterator result(*this);
339  btree_iterator_base<btree_type>::increment();
340  return result;
341  }
342 
343  btree_const_iterator operator -- (int)
344  {
345  btree_const_iterator result(*this);
346  btree_iterator_base<btree_type>::decrement();
347  return result;
348  }
349 
350  private:
351  btree_const_iterator(
352  btree_type * btree__,
353  const bid_type & b,
354  unsigned p
355  ) : btree_iterator_base<btree_type>(btree__, b, p)
356  { }
357  };
358 
359  template <class BTreeType>
360  inline bool operator == (const btree_iterator<BTreeType> & a,
361  const btree_const_iterator<BTreeType> & b)
362  {
363  return a.btree_iterator_base<BTreeType>::operator == (b);
364  }
365 
366  template <class BTreeType>
367  inline bool operator != (const btree_iterator<BTreeType> & a,
368  const btree_const_iterator<BTreeType> & b)
369  {
370  return a.btree_iterator_base<BTreeType>::operator != (b);
371  }
372 }
373 
374 __STXXL_END_NAMESPACE
375 
376 #endif /* STXXL_CONTAINERS_BTREE__ITERATOR_H */