Stxxl
1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/btree/iterator.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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 /* STXXL_CONTAINERS_BTREE__ITERATOR_H */