00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_CONTAINERS_BTREE__ITERATOR_H
00014 #define STXXL_CONTAINERS_BTREE__ITERATOR_H
00015
00016 #include <stxxl/bits/common/utils.h>
00017
00018
00019 __STXXL_BEGIN_NAMESPACE
00020
00021
00022 namespace btree
00023 {
00024 template <class BTreeType>
00025 class iterator_map;
00026 template <class BTreeType>
00027 class btree_iterator;
00028 template <class BTreeType>
00029 class btree_const_iterator;
00030 template <class KeyType_, class DataType_, class KeyCmp_, unsigned LogNElem_, class BTreeType>
00031 class normal_leaf;
00032
00033 template <class BTreeType>
00034 class btree_iterator_base
00035 {
00036 public:
00037 typedef BTreeType btree_type;
00038 typedef typename btree_type::leaf_bid_type bid_type;
00039 typedef typename btree_type::value_type value_type;
00040 typedef typename btree_type::reference reference;
00041 typedef typename btree_type::const_reference const_reference;
00042 typedef std::bidirectional_iterator_tag iterator_category;
00043 typedef typename btree_type::difference_type difference_type;
00044
00045 friend class iterator_map<btree_type>;
00046 template <class KeyType_, class DataType_,
00047 class KeyCmp_, unsigned LogNElem_, class BTreeType__>
00048 friend class normal_leaf;
00049
00050 template <class BTreeType_>
00051 friend bool operator == (const btree_iterator<BTreeType_> & a,
00052 const btree_const_iterator<BTreeType_> & b);
00053 template <class BTreeType_>
00054 friend bool operator != (const btree_iterator<BTreeType_> & a,
00055 const btree_const_iterator<BTreeType_> & b);
00056
00057 protected:
00058 btree_type * btree_;
00059 bid_type bid;
00060 unsigned pos;
00061
00062 btree_iterator_base()
00063 {
00064 STXXL_VERBOSE3("btree_iterator_base def construct addr=" << this);
00065 make_invalid();
00066 }
00067
00068 btree_iterator_base(
00069 btree_type * btree__,
00070 const bid_type & b,
00071 unsigned p
00072 ) : btree_(btree__), bid(b), pos(p)
00073 {
00074 STXXL_VERBOSE3("btree_iterator_base parameter construct addr=" << this);
00075 btree_->iterator_map_.register_iterator(*this);
00076 }
00077
00078 void make_invalid()
00079 {
00080 btree_ = NULL;
00081 }
00082
00083 btree_iterator_base(const btree_iterator_base & obj)
00084 {
00085 STXXL_VERBOSE3("btree_iterator_base constr from" << (&obj) << " to " << this);
00086 btree_ = obj.btree_;
00087 bid = obj.bid;
00088 pos = obj.pos;
00089 if (btree_)
00090 btree_->iterator_map_.register_iterator(*this);
00091 }
00092
00093 btree_iterator_base & operator = (const btree_iterator_base & obj)
00094 {
00095 STXXL_VERBOSE3("btree_iterator_base copy from" << (&obj) << " to " << this);
00096 if (&obj != this)
00097 {
00098 if (btree_)
00099 btree_->iterator_map_.unregister_iterator(*this);
00100
00101 btree_ = obj.btree_;
00102 bid = obj.bid;
00103 pos = obj.pos;
00104 if (btree_)
00105 btree_->iterator_map_.register_iterator(*this);
00106 }
00107 return *this;
00108 }
00109
00110 reference non_const_access()
00111 {
00112 assert(btree_);
00113 typename btree_type::leaf_type * Leaf = btree_->leaf_cache_.get_node(bid);
00114 assert(Leaf);
00115 return (reference)((*Leaf)[pos]);
00116 }
00117
00118 const_reference const_access() const
00119 {
00120 assert(btree_);
00121 typename btree_type::leaf_type const * Leaf = btree_->leaf_cache_.get_const_node(bid);
00122 assert(Leaf);
00123 return (reference)((*Leaf)[pos]);
00124 }
00125
00126 bool operator == (const btree_iterator_base & obj) const
00127 {
00128 return bid == obj.bid && pos == obj.pos && btree_ == obj.btree_;
00129 }
00130
00131 bool operator != (const btree_iterator_base & obj) const
00132 {
00133 return bid != obj.bid || pos != obj.pos || btree_ != obj.btree_;
00134 }
00135
00136 btree_iterator_base & increment()
00137 {
00138 assert(btree_);
00139 bid_type cur_bid = bid;
00140 typename btree_type::leaf_type const * Leaf = btree_->leaf_cache_.get_const_node(bid, true);
00141 assert(Leaf);
00142 Leaf->increment_iterator(*this);
00143 btree_->leaf_cache_.unfix_node(cur_bid);
00144 return *this;
00145 }
00146
00147 btree_iterator_base & decrement()
00148 {
00149 assert(btree_);
00150 bid_type cur_bid = bid;
00151 typename btree_type::leaf_type const * Leaf = btree_->leaf_cache_.get_const_node(bid, true);
00152 assert(Leaf);
00153 Leaf->decrement_iterator(*this);
00154 btree_->leaf_cache_.unfix_node(cur_bid);
00155 return *this;
00156 }
00157
00158 public:
00159 virtual ~btree_iterator_base()
00160 {
00161 STXXL_VERBOSE3("btree_iterator_base deconst " << this);
00162 if (btree_)
00163 btree_->iterator_map_.unregister_iterator(*this);
00164 }
00165 };
00166
00167 template <class BTreeType>
00168 class btree_iterator : public btree_iterator_base<BTreeType>
00169 {
00170 public:
00171 typedef BTreeType btree_type;
00172 typedef typename btree_type::leaf_bid_type bid_type;
00173 typedef typename btree_type::value_type value_type;
00174 typedef typename btree_type::reference reference;
00175 typedef typename btree_type::const_reference const_reference;
00176 typedef typename btree_type::pointer pointer;
00177
00178 template <class KeyType_, class DataType_,
00179 class KeyCmp_, unsigned LogNElem_, class BTreeType__>
00180 friend class normal_leaf;
00181
00182 using btree_iterator_base<btree_type>::non_const_access;
00183
00184 btree_iterator() : btree_iterator_base<btree_type>()
00185 { }
00186
00187 btree_iterator(const btree_iterator & obj) :
00188 btree_iterator_base<btree_type>(obj)
00189 { }
00190
00191 btree_iterator & operator = (const btree_iterator & obj)
00192 {
00193 btree_iterator_base<btree_type>::operator = (obj);
00194 return *this;
00195 }
00196
00197 reference operator * ()
00198 {
00199 return non_const_access();
00200 }
00201
00202 pointer operator -> ()
00203 {
00204 return &(non_const_access());
00205 }
00206
00207 bool operator == (const btree_iterator & obj) const
00208 {
00209 return btree_iterator_base<btree_type>::operator == (obj);
00210 }
00211
00212 bool operator != (const btree_iterator & obj) const
00213 {
00214 return btree_iterator_base<btree_type>::operator != (obj);
00215 }
00216
00217 btree_iterator & operator ++ ()
00218 {
00219 assert(*this != btree_iterator_base<btree_type>::btree_->end());
00220 btree_iterator_base<btree_type>::increment();
00221 return *this;
00222 }
00223
00224 btree_iterator & operator -- ()
00225 {
00226 btree_iterator_base<btree_type>::decrement();
00227 return *this;
00228 }
00229
00230 btree_iterator operator ++ (int)
00231 {
00232 assert(*this != btree_iterator_base<btree_type>::btree_->end());
00233 btree_iterator result(*this);
00234 btree_iterator_base<btree_type>::increment();
00235 return result;
00236 }
00237
00238 btree_iterator operator -- (int)
00239 {
00240 btree_iterator result(*this);
00241 btree_iterator_base<btree_type>::decrement();
00242 return result;
00243 }
00244
00245 private:
00246 btree_iterator(
00247 btree_type * btree__,
00248 const bid_type & b,
00249 unsigned p
00250 ) : btree_iterator_base<btree_type>(btree__, b, p)
00251 { }
00252 };
00253
00254 template <class BTreeType>
00255 class btree_const_iterator : public btree_iterator_base<BTreeType>
00256 {
00257 public:
00258 typedef btree_iterator<BTreeType> iterator;
00259
00260 typedef BTreeType btree_type;
00261 typedef typename btree_type::leaf_bid_type bid_type;
00262 typedef typename btree_type::value_type value_type;
00263 typedef typename btree_type::const_reference reference;
00264 typedef typename btree_type::const_pointer pointer;
00265
00266 template <class KeyType_, class DataType_,
00267 class KeyCmp_, unsigned LogNElem_, class BTreeType__>
00268 friend class normal_leaf;
00269
00270 using btree_iterator_base<btree_type>::const_access;
00271
00272 btree_const_iterator() : btree_iterator_base<btree_type>()
00273 { }
00274
00275 btree_const_iterator(const btree_const_iterator & obj) :
00276 btree_iterator_base<btree_type>(obj)
00277 { }
00278
00279 btree_const_iterator(const iterator & obj) :
00280 btree_iterator_base<btree_type>(obj)
00281 { }
00282
00283 btree_const_iterator & operator = (const btree_const_iterator & obj)
00284 {
00285 btree_iterator_base<btree_type>::operator = (obj);
00286 return *this;
00287 }
00288
00289 reference operator * ()
00290 {
00291 return const_access();
00292 }
00293
00294 pointer operator -> ()
00295 {
00296 return &(const_access());
00297 }
00298
00299
00300 bool operator == (const iterator & obj) const
00301 {
00302 return btree_iterator_base<btree_type>::operator == (obj);
00303 }
00304
00305 bool operator != (const iterator & obj) const
00306 {
00307 return btree_iterator_base<btree_type>::operator != (obj);
00308 }
00309
00310 bool operator == (const btree_const_iterator & obj) const
00311 {
00312 return btree_iterator_base<btree_type>::operator == (obj);
00313 }
00314
00315 bool operator != (const btree_const_iterator & obj) const
00316 {
00317 return btree_iterator_base<btree_type>::operator != (obj);
00318 }
00319
00320 btree_const_iterator & operator ++ ()
00321 {
00322 assert(*this != btree_iterator_base<btree_type>::btree_->end());
00323 btree_iterator_base<btree_type>::increment();
00324 return *this;
00325 }
00326
00327 btree_const_iterator & operator -- ()
00328 {
00329 btree_iterator_base<btree_type>::decrement();
00330 return *this;
00331 }
00332
00333 btree_const_iterator operator ++ (int)
00334 {
00335 assert(*this != btree_iterator_base<btree_type>::btree_->end());
00336 btree_const_iterator result(*this);
00337 btree_iterator_base<btree_type>::increment();
00338 return result;
00339 }
00340
00341 btree_const_iterator operator -- (int)
00342 {
00343 btree_const_iterator result(*this);
00344 btree_iterator_base<btree_type>::decrement();
00345 return result;
00346 }
00347
00348 private:
00349 btree_const_iterator(
00350 btree_type * btree__,
00351 const bid_type & b,
00352 unsigned p
00353 ) : btree_iterator_base<btree_type>(btree__, b, p)
00354 { }
00355 };
00356
00357 template <class BTreeType>
00358 inline bool operator == (const btree_iterator<BTreeType> & a,
00359 const btree_const_iterator<BTreeType> & b)
00360 {
00361 return a.btree_iterator_base<BTreeType>::operator == (b);
00362 }
00363
00364 template <class BTreeType>
00365 inline bool operator != (const btree_iterator<BTreeType> & a,
00366 const btree_const_iterator<BTreeType> & b)
00367 {
00368 return a.btree_iterator_base<BTreeType>::operator != (b);
00369 }
00370 }
00371
00372 __STXXL_END_NAMESPACE
00373
00374 #endif