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