1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2009 Oracle. All rights reserved. 5 * 6 * $Id$ 7 */ 8 9#ifndef _DB_STL_DB_BASE_ITERATOR_H 10#define _DB_STL_DB_BASE_ITERATOR_H 11 12#include "dbstl_common.h" 13 14START_NS(dbstl) 15 16template <Typename ddt> 17class ElementRef; 18template <Typename ddt> 19class ElementHolder; 20 21/** \defgroup dbstl_iterators dbstl iterator classes 22Common information for all dbstl iterators: 23 241. Each instance of a dbstl iterator uniquely owns a Berkeley DB cursor, 25so that the key/data pair it currently sits on is always valid before it moves 26elsewhere. It also caches the current key/data pair values in order for member 27functions like operator* /operator-> to work properly, but caching is not 28compatible with standard C++ Stl behavior --- the C++ standard requires the 29iterator refer to a shared piece of memory where the data is stored, 30thus two iterators of the same container sitting on the same element should 31point to the same memory location, which is false for dbstl iterators. 32 332. There are some functions common to each child class of this class which have 34identical behaviors, so we will document them here. 35 36@{ 37This class is the base class for all dbstl iterators, there is no much to say 38about this class itself, and users are not supposed to directly use this class 39at all. So we will talk about some common functions of dbstl iterators in 40this section. 41 42\sa db_vector_base_iterator db_vector_iterator db_map_base_iterator 43db_map_iterator db_set_base_iterator db_set_iterator 44*/ 45template <Typename ddt> 46class db_base_iterator 47{ 48protected: 49 typedef db_base_iterator<ddt> self; 50 friend class ElementHolder<ddt>; 51 friend class ElementRef<ddt>; 52 53 // The container from which this iterator is created. 54 mutable db_container *owner_; 55 56 bool dead_; // Internally used to prevent recursive destruction calls. 57 58 // Whether or not to always get current key/data pair directly from db; 59 // If true, always poll db, slower but safe for concurrent use; 60 // otherwise faster, but when multiple iterators point to the same 61 // key/data pair (they definitely have same locker id) and use some 62 // iterators to update current key/data pair, then other iterators' 63 // key/data pairs are obsolete, need to call iterator::refresh(). 64 // 65 bool directdb_get_; 66 67 // Whether to do bulk retrieval for a read only iterator. If non-zero, 68 // do bulk retrieval and use this member as the bulk buffer size, 69 // otherwise, do not use bulk retrieval. While doing bulk retrieval, 70 // no longer read from database even if directdb_get is true. 71 u_int32_t bulk_retrieval_; 72 73 // Whether to use DB_RMW flag in Dbc::get. Users can set this flag in 74 // db_container::begin(). The flag may be ignored when there is no 75 // locking subsystem initialized. 76 bool rmw_csr_; 77 78 // Whether this iterator is a db_set/db_multiset iterator. 79 bool is_set_; 80 81 // Whether this iterator is read only. Default value is false. 82 // The const version of begin(), or passing an explicit "readonly" 83 // parameter to non-const begin() will will create a read only 84 // iterator; 85 // 86 bool read_only_; 87 88 // Iteration status. If in valid range, it is 0, otherwise it is 89 // INVALID_ITERATOR_POSITION. 90 mutable int itr_status_; 91 92 // Distinguish the invalid iterator of end() and rend(). If an 93 // iterator was invalidated in operator++, inval_pos_type_ is 94 // IPT_AFTER_LAST, else if in operator-- it is IPT_BEFORE_FIRST. 95 // For random iterator, inval_pos_type_ is also updated in random 96 // movement functions. This member is only valid when itr_status_ is 97 // set to INVALID_ITERATOR_POSITION. 98 mutable char inval_pos_type_; 99 // Values to denote the invalid positions. 100 const static char IPT_BEFORE_FIRST = -1; 101 const static char IPT_AFTER_LAST = 1; 102 const static char IPT_UNSET = 0; 103 104 virtual void delete_me() const { delete this;} 105 106 virtual db_base_iterator* dup_itr() const 107 { 108 THROW(InvalidFunctionCall, ( 109 "\ndb_base_iterator<>::dup_itr can't be called.\n")); 110 111 } 112 113 inline bool is_set_iterator() const 114 { 115 return is_set_; 116 } 117 118 // The following two functions can't be abstract virtual for 119 // compiler errors. 120 virtual int replace_current(const ddt&) 121 { 122 THROW(InvalidFunctionCall, ( 123 "\ndb_base_iterator<>::replace_current can't be called\n")); 124 } 125 126 virtual int replace_current_key(const ddt&) 127 { 128 THROW(InvalidFunctionCall, ( 129 "\ndb_base_iterator<>::replace_current_key can't be called\n")); 130 } 131 132public: 133#if NEVER_DEFINE_THIS_MACRO_IT_IS_FOR_DOXYGEN_ONLY 134 /// Read data from underlying database via its cursor, and update 135 /// its cached value. 136 /// \param from_db Whether retrieve data from database rather than 137 /// using the cached data in this iterator. 138 /// \return 0 if succeeded. Otherwise an DbstlException exception 139 /// will be thrown. 140 int refresh(bool from_db = true); 141 142 /** Close its cursor. If you are sure the iterator is no longer 143 used, call this function so that its underlying cursor is closed 144 before this iterator is destructed, potentially increase performance 145 and concurrency. Note that the cursor is definitely 146 closed at iterator destruction if you don't close it explicitly. 147 */ 148 void close_cursor() const; 149 150 /** Call this function to modify bulk buffer size. Bulk retrieval is 151 enabled when creating an iterator, so users later can only modify 152 the bulk buffer size to another value, but can't enable/disable 153 bulk read while an iterator is already alive. 154 \param sz The new buffer size in bytes. 155 \return true if succeeded, false otherwise. 156 */ 157 bool set_bulk_buffer(u_int32_t sz); 158 159 /// Return current bulk buffer size. Returns 0 if bulk retrieval is 160 /// not enabled. 161 u_int32_t get_bulk_bufsize(); 162#endif // NEVER_DEFINE_THIS_MACRO_IT_IS_FOR_DOXYGEN_ONLY 163 164 //////////////////////////////////////////////////////////////////// 165 // 166 // Begin public constructors and destructor. 167 // 168 /// Default constructor. 169 db_base_iterator() 170 { 171 owner_ = NULL; 172 directdb_get_ = true; 173 dead_ = false; 174 itr_status_ = INVALID_ITERATOR_POSITION; 175 read_only_ = false; 176 is_set_ = false; 177 bulk_retrieval_ = 0; 178 rmw_csr_ = false; 179 inval_pos_type_ = IPT_UNSET; 180 } 181 182 /// Constructor. 183 db_base_iterator(db_container *powner, bool directdbget, 184 bool b_read_only, u_int32_t bulk, bool rmw) 185 { 186 owner_ = powner; 187 directdb_get_ = directdbget; 188 dead_ = false; 189 itr_status_ = INVALID_ITERATOR_POSITION; 190 read_only_ = b_read_only; 191 is_set_ = false; 192 bulk_retrieval_ = bulk; 193 rmw_csr_ = rmw; 194 inval_pos_type_ = IPT_UNSET; 195 } 196 197 /// Copy constructor. Copy all members of this class. 198 db_base_iterator(const db_base_iterator &bi) 199 { 200 owner_ = bi.owner_; 201 directdb_get_ = bi.directdb_get_; 202 dead_ = false; 203 itr_status_ = bi.itr_status_; 204 read_only_ = bi.read_only_; 205 is_set_ = bi.is_set_; 206 bulk_retrieval_ = bi.bulk_retrieval_; 207 rmw_csr_ = bi.rmw_csr_; 208 inval_pos_type_ = bi.inval_pos_type_; 209 } 210 211 /** 212 Iterator assignment operator. 213 Iterator assignment will cause the underlying cursor of the right iterator 214 to be duplicated to the left iterator after its previous cursor is closed, 215 to make sure each iterator owns one unique cursor. The key/data cached 216 in the right iterator is copied to the left iterator. Consequently, 217 the left iterator points to the same key/data pair in the database 218 as the the right value after the assignment, and have identical cached 219 key/data pair. 220 \param bi The other iterator to assign with. 221 \return The iterator bi's reference. 222 */ 223 inline const self& operator=(const self& bi) 224 { 225 ASSIGNMENT_PREDCOND(bi) 226 owner_ = bi.owner_; 227 directdb_get_ = bi.directdb_get_; 228 dead_ = false; 229 itr_status_ = bi.itr_status_; 230 read_only_ = bi.read_only_; 231 is_set_ = bi.is_set_; 232 bulk_retrieval_ = bi.bulk_retrieval_; 233 rmw_csr_ = bi.rmw_csr_; 234 inval_pos_type_ = bi.inval_pos_type_; 235 return bi; 236 } 237 238 /// Destructor. 239 virtual ~db_base_iterator() {} 240 241 //////////////////////////////////////////////////////////////////// 242 243 /// \brief Get bulk buffer size. 244 /// 245 /// Return bulk buffer size. If the size is 0, bulk retrieval is not 246 /// enabled. 247 u_int32_t get_bulk_retrieval() const { return bulk_retrieval_; } 248 249 /// \brief Get DB_RMW setting. 250 /// 251 /// Return true if the iterator's cursor has DB_RMW flag set, false 252 /// otherwise. DB_RMW flag causes 253 /// a write lock to be acquired when reading a key/data pair, so 254 /// that the transaction won't block later when writing back the 255 /// updated value in a read-modify-write operation cycle. 256 bool is_rmw() const { return rmw_csr_; } 257 258 /// \brief Get direct database get setting. 259 /// 260 /// Return true if every operation to retrieve the key/data pair the 261 /// iterator points to will read from database rather than using 262 /// the cached value, false otherwise. 263 bool is_directdb_get() const {return directdb_get_; } 264}; // db_base_iterator 265 266//////////////////////////////////////////////////////////////////////// 267//////////////////////////////////////////////////////////////////////// 268// 269// db_reverse_iterator class template definition. 270// 271// db_reverse_iterator is the reverse iterator adapter for all iterator 272// classes of dbstl. It makes an original iterator its reverse iterator. 273// We don't want to use std::reverse_iterator<> adapter because it is more 274// more expensive. Here we move the original iterator one position back to 275// avoid unnecessary movement. 276// 277/// This class is the reverse class adaptor for all dbstl iterator classes. 278/// It inherits from real iterator classes like db_vector_iterator, 279/// db_map_iterator or db_set_iterator. When you call container::rbegin(), 280/// you will get an instance of this class. 281/// \sa db_vector_base_iterator db_vector_iterator db_map_base_iterator 282/// db_map_iterator db_set_base_iterator db_set_iterator 283template <Typename iterator, Typename twin_itr_t> 284class _exported db_reverse_iterator : public iterator 285{ 286public: 287 // typedefs are not inherited, so re-define them here. 288 // 289 typedef db_reverse_iterator<iterator, twin_itr_t> self; 290 typedef typename iterator::value_type T; 291 typedef iterator iterator_type; 292 typedef typename iterator::value_type value_type; 293 typedef typename iterator::reference reference; 294 typedef typename iterator::pointer pointer; 295 typedef typename iterator::iterator_category iterator_category; 296 typedef typename iterator::key_type key_type; 297 typedef typename iterator::data_type data_type; 298 typedef typename iterator::difference_type difference_type; 299 typedef typename iterator::value_type_wrap value_type_wrap; 300 // Construct a reverse iterator from iterator vi. We don't duplicate 301 // itrerator vi here because vi is not supposed to be used again. 302 // This function is supposed to be used by dbstl users, internally 303 // self::set_iterator method is used. 304 /// Constructor. Construct from an iterator of wrapped type. 305 db_reverse_iterator(const iterator& vi) : iterator(vi) 306 { 307 iterator::operator--(); 308 } 309 310 /// Copy constructor. 311 db_reverse_iterator(const self& ritr) 312 : iterator(ritr) 313 { 314 } 315 316 /// Copy constructor. 317 db_reverse_iterator(const 318 db_reverse_iterator<twin_itr_t, iterator>& ritr) 319 : iterator(ritr) 320 { 321 } 322 323 /// Default constructor. 324 db_reverse_iterator() : iterator() 325 { 326 } 327 328 // Do not throw exceptions here because it is normal to iterate to 329 // "end()". 330 // 331 /// \name Reverse iterator movement functions 332 /// When we talk about reverse iterator movement, we think the 333 /// container is a uni-directional range, represented by [begin, end), 334 /// and this is true no matter we are using iterators or reverse 335 /// iterators. When an iterator is moved closer to "begin", we say it 336 /// is moved forward, otherwise we say it is moved backward. 337 //@{ 338 /// Move this iterator forward by one element. 339 /// \return The moved iterator at new position. 340 self& operator++() 341 { 342 iterator::operator--(); 343 return *this; 344 } 345 346 /// Move this iterator forward by one element. 347 /// \return The original iterator at old position. 348 self operator++(int) 349 { 350 // XXX!!! This conversion relies on this class or 351 // db_set_iterator<> having no data members at all, which 352 // is currently the case. 353 return (self)iterator::operator--(1); 354 } 355 356 /// Move this iterator backward by one element. 357 /// \return The moved iterator at new position. 358 self& operator--() 359 { 360 iterator::operator++(); 361 return *this; 362 } 363 364 /// Move this iterator backward by one element. 365 /// \return The original iterator at old position. 366 self operator--(int) 367 { 368 // XXX!!! This conversion relies on this class or 369 // db_set_iterator<> having no data members at all, which 370 // is currently the case. 371 return (self)iterator::operator++(1); 372 } 373 //@} // Movement operators. 374 375 /// Assignment operator. 376 /// \param ri The iterator to assign with. 377 /// \return The iterator ri. 378 /// \sa db_base_iterator::operator=(const self&) 379 const self& operator=(const self& ri) 380 { 381 ASSIGNMENT_PREDCOND(ri) 382 iterator::operator=(ri); 383 return ri; 384 } 385 386 ////////////// Methods below only applies to random iterators. ///// 387 /// \name Operators for random reverse iterators 388 /// Return a new iterator by moving this iterator backward or forward 389 /// by n elements. 390 //@{ 391 /// Iterator shuffle operator. 392 /// Return a new iterator by moving this iterator forward 393 /// by n elements. 394 /// \param n The amount and direction of movement. If negative, 395 /// will move towards reverse direction. 396 /// \return A new iterator at new position. 397 self operator+(difference_type n) const 398 { 399 self ritr(*this); 400 ritr.iterator::operator-=(n); 401 return ritr; 402 } 403 404 /// Iterator shuffle operator. 405 /// Return a new iterator by moving this iterator backward 406 /// by n elements. 407 /// \param n The amount and direction of movement. If negative, 408 /// will move towards reverse direction. 409 /// \return A new iterator at new position. 410 self operator-(difference_type n) const 411 { 412 self ritr(*this); 413 ritr.iterator::operator+=(n); 414 return ritr; 415 } 416 //@} 417 /// \name Operators for random reverse iterators 418 /// Move this iterator backward or forward by n elements and then 419 /// return it. 420 //@{ 421 /// Iterator shuffle operator. 422 /// Move this iterator forward by n elements and then 423 /// return it. 424 /// \param n The amount and direction of movement. If negative, 425 /// will move towards reverse direction. 426 /// \return This iterator at new position. 427 const self& operator+=(difference_type n) 428 { 429 iterator::operator-=(n); 430 return *this; 431 } 432 433 /// Iterator shuffle operator. 434 /// Move this iterator backward by n elements and then 435 /// return it. 436 /// \param n The amount and direction of movement. If negative, 437 /// will move towards reverse direction. 438 /// \return This iterator at new position. 439 const self& operator-=(difference_type n) 440 { 441 iterator::operator+=(n); 442 return *this; 443 } 444 //@} 445 /// \name Operators for random reverse iterators 446 /// Reverse iterator comparison against reverse iterator itr, the one 447 /// sitting on elements with less index is returned to be greater. 448 //@{ 449 /// Less compare operator. 450 bool operator<(const self& itr) const 451 { 452 return (iterator::operator>(itr)); 453 } 454 455 /// Greater compare operator. 456 bool operator>(const self& itr) const 457 { 458 return (iterator::operator<(itr)); 459 } 460 461 /// Less equal compare operator. 462 bool operator<=(const self& itr) const 463 { 464 return (iterator::operator>=(itr)); 465 } 466 467 /// Greater equal compare operator. 468 bool operator>=(const self& itr) const 469 { 470 return (iterator::operator<=(itr)); 471 } 472 //@} 473 // Because v.rend() - v.rbegin() < 0, we should negate base version. 474 /// Return the negative value of the difference of indices of elements 475 /// this iterator and itr are sitting on. 476 /// \return itr.index - this->index. 477 /// \param itr The other reverse iterator. 478 difference_type operator-(const self&itr) const 479 { 480 difference_type d = iterator::operator-(itr); 481 return -d; 482 } 483 484 /// Return the reference of the element which can be reached by moving 485 /// this reverse iterator by Off times backward. If Off is negative, 486 /// the movement will be forward. 487 inline value_type_wrap operator[](difference_type Off) const 488 { 489 self ritr(*this); 490 value_type_wrap res = ritr.iterator::operator[](-Off); 491 return res; 492 } 493 494}; // reverse_iterator 495//@} // dbstl_iterators 496END_NS 497 498#endif // !_DB_STL_DB_BASE_ITERATOR_H 499