Stxxl
1.3.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/vector.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002-2008 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2007-2009 Johannes Singler <singler@ira.uka.de> 00008 * Copyright (C) 2008-2010 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00009 * 00010 * Distributed under the Boost Software License, Version 1.0. 00011 * (See accompanying file LICENSE_1_0.txt or copy at 00012 * http://www.boost.org/LICENSE_1_0.txt) 00013 **************************************************************************/ 00014 00015 #ifndef STXXL_VECTOR_HEADER 00016 #define STXXL_VECTOR_HEADER 00017 00018 #include <vector> 00019 #include <queue> 00020 #include <algorithm> 00021 00022 #include <stxxl/bits/deprecated.h> 00023 #include <stxxl/bits/io/request_operations.h> 00024 #include <stxxl/bits/mng/mng.h> 00025 #include <stxxl/bits/mng/typed_block.h> 00026 #include <stxxl/bits/common/tmeta.h> 00027 #include <stxxl/bits/containers/pager.h> 00028 #include <stxxl/bits/common/is_sorted.h> 00029 00030 00031 __STXXL_BEGIN_NAMESPACE 00032 00036 00037 00041 00042 template <typename size_type, size_type modulo2, size_type modulo1> 00043 class double_blocked_index 00044 { 00045 static const size_type modulo12 = modulo1 * modulo2; 00046 00047 size_type pos, block1, block2, offset; 00048 00050 00051 void set(size_type pos) 00052 { 00053 this->pos = pos; 00054 block2 = pos / modulo12; 00055 pos -= block2 * modulo12; 00056 block1 = pos / modulo1; 00057 offset = (pos - block1 * modulo1); 00058 00059 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00060 assert(/* 0 <= block1 && */ block1 < modulo2); 00061 assert(/* 0 <= offset && */ offset < modulo1); 00062 } 00063 00064 public: 00065 double_blocked_index() 00066 { 00067 set(0); 00068 } 00069 00070 double_blocked_index(size_type pos) 00071 { 00072 set(pos); 00073 } 00074 00075 double_blocked_index(size_type block2, size_type block1, size_type offset) 00076 { 00077 assert(/* 0 <= block1 && */ block1 < modulo2); 00078 assert(/* 0 <= offset && */ offset < modulo1); 00079 00080 this->block2 = block2; 00081 this->block1 = block1; 00082 this->offset = offset; 00083 pos = block2 * modulo12 + block1 * modulo1 + offset; 00084 } 00085 00086 double_blocked_index & operator = (size_type pos) 00087 { 00088 set(pos); 00089 return *this; 00090 } 00091 00092 //pre-increment operator 00093 double_blocked_index & operator ++ () 00094 { 00095 ++pos; 00096 ++offset; 00097 if (offset == modulo1) 00098 { 00099 offset = 0; 00100 ++block1; 00101 if (block1 == modulo2) 00102 { 00103 block1 = 0; 00104 ++block2; 00105 } 00106 } 00107 00108 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00109 assert(/* 0 <= block1 && */ block1 < modulo2); 00110 assert(/* 0 <= offset && */ offset < modulo1); 00111 00112 return *this; 00113 } 00114 00115 //post-increment operator 00116 double_blocked_index operator ++ (int) 00117 { 00118 double_blocked_index former(*this); 00119 operator ++ (); 00120 return former; 00121 } 00122 00123 //pre-increment operator 00124 double_blocked_index & operator -- () 00125 { 00126 --pos; 00127 if (offset == 0) 00128 { 00129 offset = modulo1; 00130 if (block1 == 0) 00131 { 00132 block1 = modulo2; 00133 --block2; 00134 } 00135 --block1; 00136 } 00137 --offset; 00138 00139 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00140 assert(/*0 <= block1 &&*/ block1 < modulo2); 00141 assert(/*0 <= offset &&*/ offset < modulo1); 00142 00143 return *this; 00144 } 00145 00146 //post-increment operator 00147 double_blocked_index operator -- (int) 00148 { 00149 double_blocked_index former(*this); 00150 operator -- (); 00151 return former; 00152 } 00153 00154 double_blocked_index operator + (size_type addend) const 00155 { 00156 return double_blocked_index(pos + addend); 00157 } 00158 00159 double_blocked_index & operator += (size_type addend) 00160 { 00161 set(pos + addend); 00162 return *this; 00163 } 00164 00165 double_blocked_index operator - (size_type addend) const 00166 { 00167 return double_blocked_index(pos - addend); 00168 } 00169 00170 size_type operator - (const double_blocked_index & dbi2) const 00171 { 00172 return pos - dbi2.pos; 00173 } 00174 00175 double_blocked_index & operator -= (size_type subtrahend) 00176 { 00177 set(pos - subtrahend); 00178 return *this; 00179 } 00180 00181 bool operator == (const double_blocked_index & dbi2) const 00182 { 00183 return pos == dbi2.pos; 00184 } 00185 00186 bool operator != (const double_blocked_index & dbi2) const 00187 { 00188 return pos != dbi2.pos; 00189 } 00190 00191 bool operator < (const double_blocked_index & dbi2) const 00192 { 00193 return pos < dbi2.pos; 00194 } 00195 00196 bool operator <= (const double_blocked_index & dbi2) const 00197 { 00198 return pos <= dbi2.pos; 00199 } 00200 00201 bool operator > (const double_blocked_index & dbi2) const 00202 { 00203 return pos > dbi2.pos; 00204 } 00205 00206 bool operator >= (const double_blocked_index & dbi2) const 00207 { 00208 return pos >= dbi2.pos; 00209 } 00210 00211 double_blocked_index & operator >>= (size_type shift) 00212 { 00213 set(pos >> shift); 00214 return *this; 00215 } 00216 00217 size_type get_pos() const 00218 { 00219 return pos; 00220 } 00221 00222 const size_type & get_block2() const 00223 { 00224 return block2; 00225 } 00226 00227 const size_type & get_block1() const 00228 { 00229 return block1; 00230 } 00231 00232 const size_type & get_offset() const 00233 { 00234 return offset; 00235 } 00236 }; 00237 00238 00239 template <unsigned BlkSize_> 00240 class bid_vector : public std::vector<BID<BlkSize_> > 00241 { 00242 public: 00243 typedef std::vector<BID<BlkSize_> > _Derived; 00244 typedef typename _Derived::size_type size_type; 00245 typedef typename _Derived::value_type bid_type; 00246 00247 bid_vector(size_type _sz) : _Derived(_sz) 00248 { } 00249 }; 00250 00251 00252 template < 00253 typename Tp_, 00254 unsigned PgSz_, 00255 typename PgTp_, 00256 unsigned BlkSize_, 00257 typename AllocStr_, 00258 typename SzTp_> 00259 class vector; 00260 00261 00262 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00263 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00264 class const_vector_iterator; 00265 00266 00268 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00269 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00270 class vector_iterator 00271 { 00272 typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _Self; 00273 typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _CIterator; 00274 00275 friend class const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>; 00276 00277 public: 00278 typedef _CIterator const_iterator; 00279 typedef _Self iterator; 00280 00281 typedef unsigned block_offset_type; 00282 typedef vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> vector_type; 00283 friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>; 00284 typedef typename vector_type::bids_container_type bids_container_type; 00285 typedef typename bids_container_type::iterator bids_container_iterator; 00286 typedef typename bids_container_type::bid_type bid_type; 00287 typedef typename vector_type::block_type block_type; 00288 typedef typename vector_type::blocked_index_type blocked_index_type; 00289 00290 typedef std::random_access_iterator_tag iterator_category; 00291 typedef typename vector_type::size_type size_type; 00292 typedef typename vector_type::difference_type difference_type; 00293 typedef typename vector_type::value_type value_type; 00294 typedef typename vector_type::reference reference; 00295 typedef typename vector_type::const_reference const_reference; 00296 typedef typename vector_type::pointer pointer; 00297 typedef typename vector_type::const_pointer const_pointer; 00298 00299 protected: 00300 blocked_index_type offset; 00301 vector_type * p_vector; 00302 00303 private: 00304 vector_iterator(vector_type * v, size_type o) : offset(o), 00305 p_vector(v) 00306 { } 00307 00308 public: 00309 vector_iterator() : offset(0), p_vector(NULL) { } 00310 vector_iterator(const _Self & a) : 00311 offset(a.offset), 00312 p_vector(a.p_vector) { } 00313 00314 block_offset_type block_offset() const 00315 { 00316 return static_cast<block_offset_type>(offset.get_offset()); 00317 } 00318 bids_container_iterator bid() const 00319 { 00320 return p_vector->bid(offset); 00321 } 00322 00323 difference_type operator - (const _Self & a) const 00324 { 00325 return offset - a.offset; 00326 } 00327 00328 difference_type operator - (const const_iterator & a) const 00329 { 00330 return offset - a.offset; 00331 } 00332 00333 _Self operator - (size_type op) const 00334 { 00335 return _Self(p_vector, offset.get_pos() - op); 00336 } 00337 00338 _Self operator + (size_type op) const 00339 { 00340 return _Self(p_vector, offset.get_pos() + op); 00341 } 00342 00343 _Self & operator -= (size_type op) 00344 { 00345 offset -= op; 00346 return *this; 00347 } 00348 00349 _Self & operator += (size_type op) 00350 { 00351 offset += op; 00352 return *this; 00353 } 00354 00355 reference operator * () 00356 { 00357 return p_vector->element(offset); 00358 } 00359 00360 pointer operator -> () 00361 { 00362 return &(p_vector->element(offset)); 00363 } 00364 00365 const_reference operator * () const 00366 { 00367 return p_vector->const_element(offset); 00368 } 00369 00370 const_pointer operator -> () const 00371 { 00372 return &(p_vector->const_element(offset)); 00373 } 00374 00375 reference operator [] (size_type op) 00376 { 00377 return p_vector->element(offset.get_pos() + op); 00378 } 00379 00380 const_reference operator [] (size_type op) const 00381 { 00382 return p_vector->const_element(offset.get_pos() + op); 00383 } 00384 00385 void block_externally_updated() 00386 { 00387 p_vector->block_externally_updated(offset); 00388 } 00389 00390 _STXXL_DEPRECATED(void touch()) 00391 { 00392 block_externally_updated(); 00393 } 00394 00395 _Self & operator ++ () 00396 { 00397 offset++; 00398 return *this; 00399 } 00400 _Self operator ++ (int) 00401 { 00402 _Self __tmp = *this; 00403 offset++; 00404 return __tmp; 00405 } 00406 _Self & operator -- () 00407 { 00408 offset--; 00409 return *this; 00410 } 00411 _Self operator -- (int) 00412 { 00413 _Self __tmp = *this; 00414 offset--; 00415 return __tmp; 00416 } 00417 bool operator == (const _Self & a) const 00418 { 00419 assert(p_vector == a.p_vector); 00420 return offset == a.offset; 00421 } 00422 bool operator != (const _Self & a) const 00423 { 00424 assert(p_vector == a.p_vector); 00425 return offset != a.offset; 00426 } 00427 bool operator < (const _Self & a) const 00428 { 00429 assert(p_vector == a.p_vector); 00430 return offset < a.offset; 00431 } 00432 bool operator <= (const _Self & a) const 00433 { 00434 assert(p_vector == a.p_vector); 00435 return offset <= a.offset; 00436 } 00437 bool operator > (const _Self & a) const 00438 { 00439 assert(p_vector == a.p_vector); 00440 return offset > a.offset; 00441 } 00442 bool operator >= (const _Self & a) const 00443 { 00444 assert(p_vector == a.p_vector); 00445 return offset >= a.offset; 00446 } 00447 00448 bool operator == (const const_iterator & a) const 00449 { 00450 assert(p_vector == a.p_vector); 00451 return offset == a.offset; 00452 } 00453 bool operator != (const const_iterator & a) const 00454 { 00455 assert(p_vector == a.p_vector); 00456 return offset != a.offset; 00457 } 00458 bool operator < (const const_iterator & a) const 00459 { 00460 assert(p_vector == a.p_vector); 00461 return offset < a.offset; 00462 } 00463 bool operator <= (const const_iterator & a) const 00464 { 00465 assert(p_vector == a.p_vector); 00466 return offset <= a.offset; 00467 } 00468 bool operator > (const const_iterator & a) const 00469 { 00470 assert(p_vector == a.p_vector); 00471 return offset > a.offset; 00472 } 00473 bool operator >= (const const_iterator & a) const 00474 { 00475 assert(p_vector == a.p_vector); 00476 return offset >= a.offset; 00477 } 00478 00479 void flush() 00480 { 00481 p_vector->flush(); 00482 } 00483 #if 0 00484 std::ostream & operator << (std::ostream & o) const 00485 { 00486 o << "vectorpointer: " << ((void *)p_vector) << " offset: " << offset; 00487 return o; 00488 } 00489 #endif 00490 }; 00491 00493 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00494 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00495 class const_vector_iterator 00496 { 00497 typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _Self; 00498 typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> _NonConstIterator; 00499 00500 friend class vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>; 00501 00502 public: 00503 typedef _Self const_iterator; 00504 typedef _NonConstIterator iterator; 00505 00506 typedef unsigned block_offset_type; 00507 typedef vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> vector_type; 00508 friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>; 00509 typedef typename vector_type::bids_container_type bids_container_type; 00510 typedef typename bids_container_type::iterator bids_container_iterator; 00511 typedef typename bids_container_type::bid_type bid_type; 00512 typedef typename vector_type::block_type block_type; 00513 typedef typename vector_type::blocked_index_type blocked_index_type; 00514 00515 typedef std::random_access_iterator_tag iterator_category; 00516 typedef typename vector_type::size_type size_type; 00517 typedef typename vector_type::difference_type difference_type; 00518 typedef typename vector_type::value_type value_type; 00519 typedef typename vector_type::const_reference reference; 00520 typedef typename vector_type::const_reference const_reference; 00521 typedef typename vector_type::const_pointer pointer; 00522 typedef typename vector_type::const_pointer const_pointer; 00523 00524 protected: 00525 blocked_index_type offset; 00526 const vector_type * p_vector; 00527 00528 private: 00529 const_vector_iterator(const vector_type * v, size_type o) : offset(o), 00530 p_vector(v) 00531 { } 00532 00533 public: 00534 const_vector_iterator() : offset(0), p_vector(NULL) 00535 { } 00536 const_vector_iterator(const _Self & a) : 00537 offset(a.offset), 00538 p_vector(a.p_vector) 00539 { } 00540 00541 const_vector_iterator(const iterator & a) : 00542 offset(a.offset), 00543 p_vector(a.p_vector) 00544 { } 00545 00546 block_offset_type block_offset() const 00547 { 00548 return static_cast<block_offset_type>(offset.get_offset()); 00549 } 00550 bids_container_iterator bid() const 00551 { 00552 return ((vector_type *)p_vector)->bid(offset); 00553 } 00554 00555 difference_type operator - (const _Self & a) const 00556 { 00557 return offset - a.offset; 00558 } 00559 00560 difference_type operator - (const iterator & a) const 00561 { 00562 return offset - a.offset; 00563 } 00564 00565 _Self operator - (size_type op) const 00566 { 00567 return _Self(p_vector, offset.get_pos() - op); 00568 } 00569 00570 _Self operator + (size_type op) const 00571 { 00572 return _Self(p_vector, offset.get_pos() + op); 00573 } 00574 00575 _Self & operator -= (size_type op) 00576 { 00577 offset -= op; 00578 return *this; 00579 } 00580 00581 _Self & operator += (size_type op) 00582 { 00583 offset += op; 00584 return *this; 00585 } 00586 00587 const_reference operator * () const 00588 { 00589 return p_vector->const_element(offset); 00590 } 00591 00592 const_pointer operator -> () const 00593 { 00594 return &(p_vector->const_element(offset)); 00595 } 00596 00597 const_reference operator [] (size_type op) const 00598 { 00599 return p_vector->const_element(offset.get_pos() + op); 00600 } 00601 00602 void block_externally_updated() 00603 { 00604 p_vector->block_externally_updated(offset); 00605 } 00606 00607 _STXXL_DEPRECATED(void touch()) 00608 { 00609 block_externally_updated(); 00610 } 00611 00612 _Self & operator ++ () 00613 { 00614 offset++; 00615 return *this; 00616 } 00617 _Self operator ++ (int) 00618 { 00619 _Self tmp_ = *this; 00620 offset++; 00621 return tmp_; 00622 } 00623 _Self & operator -- () 00624 { 00625 offset--; 00626 return *this; 00627 } 00628 _Self operator -- (int) 00629 { 00630 _Self __tmp = *this; 00631 offset--; 00632 return __tmp; 00633 } 00634 bool operator == (const _Self & a) const 00635 { 00636 assert(p_vector == a.p_vector); 00637 return offset == a.offset; // or (offset + stxxl::int64(p_vector)) 00638 } 00639 bool operator != (const _Self & a) const 00640 { 00641 assert(p_vector == a.p_vector); 00642 return offset != a.offset; 00643 } 00644 bool operator < (const _Self & a) const 00645 { 00646 assert(p_vector == a.p_vector); 00647 return offset < a.offset; 00648 } 00649 bool operator <= (const _Self & a) const 00650 { 00651 assert(p_vector == a.p_vector); 00652 return offset <= a.offset; 00653 } 00654 bool operator > (const _Self & a) const 00655 { 00656 assert(p_vector == a.p_vector); 00657 return offset > a.offset; 00658 } 00659 bool operator >= (const _Self & a) const 00660 { 00661 assert(p_vector == a.p_vector); 00662 return offset >= a.offset; 00663 } 00664 00665 bool operator == (const iterator & a) const 00666 { 00667 assert(p_vector == a.p_vector); 00668 return offset == a.offset; // or (offset + stxxl::int64(p_vector)) 00669 } 00670 bool operator != (const iterator & a) const 00671 { 00672 assert(p_vector == a.p_vector); 00673 return offset != a.offset; 00674 } 00675 bool operator < (const iterator & a) const 00676 { 00677 assert(p_vector == a.p_vector); 00678 return offset < a.offset; 00679 } 00680 bool operator <= (const iterator & a) const 00681 { 00682 assert(p_vector == a.p_vector); 00683 return offset <= a.offset; 00684 } 00685 bool operator > (const iterator & a) const 00686 { 00687 assert(p_vector == a.p_vector); 00688 return offset > a.offset; 00689 } 00690 bool operator >= (const iterator & a) const 00691 { 00692 assert(p_vector == a.p_vector); 00693 return offset >= a.offset; 00694 } 00695 00696 void flush() 00697 { 00698 p_vector->flush(); 00699 } 00700 00701 #if 0 00702 std::ostream & operator << (std::ostream & o) const 00703 { 00704 o << "vector pointer: " << ((void *)p_vector) << " offset: " << offset; 00705 return o; 00706 } 00707 #endif 00708 }; 00709 00710 00712 00725 template < 00726 typename Tp_, 00727 unsigned PgSz_ = 4, 00728 typename PgTp_ = lru_pager<8>, 00729 unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_), 00730 typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY, 00731 typename SzTp_ = stxxl::uint64 // will be deprecated soon 00732 > 00733 class vector 00734 { 00735 public: 00736 typedef Tp_ value_type; 00737 typedef value_type & reference; 00738 typedef const value_type & const_reference; 00739 typedef value_type * pointer; 00740 typedef SzTp_ size_type; 00741 typedef stxxl::int64 difference_type; 00742 typedef const value_type * const_pointer; 00743 00744 typedef PgTp_ pager_type; 00745 typedef AllocStr_ alloc_strategy_type; 00746 00747 enum constants { 00748 block_size = BlkSize_, 00749 page_size = PgSz_, 00750 n_pages = pager_type::n_pages, 00751 on_disk = -1 00752 }; 00753 00754 typedef vector_iterator<value_type, alloc_strategy_type, size_type, 00755 difference_type, block_size, pager_type, page_size> iterator; 00756 friend class vector_iterator<value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size>; 00757 typedef const_vector_iterator<value_type, alloc_strategy_type, 00758 size_type, difference_type, block_size, pager_type, page_size> const_iterator; 00759 friend class const_vector_iterator<value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size>; 00760 typedef std::reverse_iterator<iterator> reverse_iterator; 00761 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00762 00763 typedef bid_vector<block_size> bids_container_type; 00764 typedef typename bids_container_type::iterator bids_container_iterator; 00765 typedef typename bids_container_type::const_iterator const_bids_container_iterator; 00766 00767 typedef typed_block<BlkSize_, Tp_> block_type; 00768 typedef double_blocked_index<SzTp_, PgSz_, block_type::size> blocked_index_type; 00769 00770 private: 00771 alloc_strategy_type alloc_strategy; 00772 size_type _size; 00773 bids_container_type _bids; 00774 mutable pager_type pager; 00775 00776 enum { valid_on_disk = 0, uninitialized = 1, dirty = 2 }; 00777 mutable std::vector<unsigned char> _page_status; 00778 mutable std::vector<int_type> _page_to_slot; 00779 mutable simple_vector<int_type> _slot_to_page; 00780 mutable std::queue<int_type> _free_slots; 00781 mutable simple_vector<block_type> * _cache; 00782 file * _from; 00783 block_manager * bm; 00784 config * cfg; 00785 bool exported; 00786 00787 size_type size_from_file_length(stxxl::uint64 file_length) const 00788 { 00789 stxxl::uint64 blocks_fit = file_length / stxxl::uint64(block_type::raw_size); 00790 size_type cur_size = blocks_fit * stxxl::uint64(block_type::size); 00791 stxxl::uint64 rest = file_length - blocks_fit * stxxl::uint64(block_type::raw_size); 00792 return (cur_size + rest / stxxl::uint64(sizeof(value_type))); 00793 } 00794 00795 stxxl::uint64 file_length() const 00796 { 00797 typedef stxxl::uint64 file_size_type; 00798 size_type cur_size = size(); 00799 size_type num_full_blocks = cur_size / block_type::size; 00800 if (cur_size % block_type::size != 0) 00801 { 00802 size_type rest = cur_size - num_full_blocks * block_type::size; 00803 return file_size_type(num_full_blocks) * block_type::raw_size + rest * sizeof(value_type); 00804 } 00805 return file_size_type(num_full_blocks) * block_type::raw_size; 00806 } 00807 00808 public: 00809 vector(size_type n = 0) : 00810 _size(n), 00811 _bids(div_ceil(n, block_type::size)), 00812 _page_status(div_ceil(_bids.size(), page_size)), 00813 _page_to_slot(div_ceil(_bids.size(), page_size)), 00814 _slot_to_page(n_pages), 00815 _cache(NULL), 00816 _from(NULL), 00817 exported(false) 00818 { 00819 bm = block_manager::get_instance(); 00820 cfg = config::get_instance(); 00821 00822 allocate_page_cache(); 00823 int_type all_pages = div_ceil(_bids.size(), page_size); 00824 int_type i = 0; 00825 for ( ; i < all_pages; ++i) 00826 { 00827 _page_status[i] = uninitialized; 00828 _page_to_slot[i] = on_disk; 00829 } 00830 00831 for (i = 0; i < n_pages; ++i) 00832 _free_slots.push(i); 00833 00834 bm->new_blocks(alloc_strategy, _bids.begin(), _bids.end(), 0); 00835 } 00836 00837 void swap(vector & obj) 00838 { 00839 std::swap(alloc_strategy, obj.alloc_strategy); 00840 std::swap(_size, obj._size); 00841 std::swap(_bids, obj._bids); 00842 std::swap(pager, obj.pager); 00843 std::swap(_page_status, obj._page_status); 00844 std::swap(_page_to_slot, obj._page_to_slot); 00845 std::swap(_slot_to_page, obj._slot_to_page); 00846 std::swap(_free_slots, obj._free_slots); 00847 std::swap(_cache, obj._cache); 00848 std::swap(_from, obj._from); 00849 std::swap(exported, obj.exported); 00850 } 00851 00852 void allocate_page_cache() const 00853 { 00854 if (!_cache) 00855 _cache = new simple_vector<block_type>(n_pages * page_size); 00856 } 00857 00858 // allows to free the cache, but you may not access any element until call allocate_pacge_cache() again 00859 void deallocate_page_cache() const 00860 { 00861 flush(); 00862 delete _cache; 00863 _cache = NULL; 00864 } 00865 00866 size_type capacity() const 00867 { 00868 return size_type(_bids.size()) * block_type::size; 00869 } 00871 size_type raw_capacity() const 00872 { 00873 return size_type(_bids.size()) * block_type::raw_size; 00874 } 00875 00876 void reserve(size_type n) 00877 { 00878 if (n <= capacity()) 00879 return; 00880 00881 unsigned_type old_bids_size = _bids.size(); 00882 unsigned_type new_bids_size = div_ceil(n, block_type::size); 00883 unsigned_type new_pages = div_ceil(new_bids_size, page_size); 00884 _page_status.resize(new_pages, uninitialized); 00885 _page_to_slot.resize(new_pages, on_disk); 00886 00887 _bids.resize(new_bids_size); 00888 if (_from == NULL) 00889 { 00890 bm->new_blocks(alloc_strategy, _bids.begin() + old_bids_size, _bids.end(), old_bids_size); 00891 } 00892 else 00893 { 00894 size_type offset = size_type(old_bids_size) * size_type(block_type::raw_size); 00895 bids_container_iterator it = _bids.begin() + old_bids_size; 00896 for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size)) 00897 { 00898 (*it).storage = _from; 00899 (*it).offset = offset; 00900 } 00901 STXXL_VERBOSE1("vector::reserve(): Changing size of file " << ((void *)_from) << " to " 00902 << offset); 00903 _from->set_size(offset); 00904 } 00905 } 00906 00907 void resize(size_type n) 00908 { 00909 _resize(n); 00910 } 00911 00912 void resize(size_type n, bool shrink_capacity) 00913 { 00914 if (shrink_capacity) 00915 _resize_shrink_capacity(n); 00916 else 00917 _resize(n); 00918 } 00919 00920 private: 00921 void _resize(size_type n) 00922 { 00923 reserve(n); 00924 if (n < _size) { 00925 // mark excess pages as uninitialized and evict them from cache 00926 unsigned_type first_page_to_evict = div_ceil(n, block_type::size * page_size); 00927 for (unsigned_type i = first_page_to_evict; i < _page_status.size(); ++i) { 00928 if (_page_to_slot[i] != on_disk) { 00929 _free_slots.push(_page_to_slot[i]); 00930 _page_to_slot[i] = on_disk; 00931 } 00932 _page_status[i] = uninitialized; 00933 } 00934 } 00935 _size = n; 00936 } 00937 00938 void _resize_shrink_capacity(size_type n) 00939 { 00940 unsigned_type old_bids_size = _bids.size(); 00941 unsigned_type new_bids_size = div_ceil(n, block_type::size); 00942 00943 if (new_bids_size > old_bids_size) 00944 { 00945 reserve(n); 00946 } 00947 else if (new_bids_size < old_bids_size) 00948 { 00949 if (_from != NULL) 00950 _from->set_size(new_bids_size * block_type::raw_size); 00951 else 00952 bm->delete_blocks(_bids.begin() + old_bids_size, _bids.end()); 00953 00954 _bids.resize(new_bids_size); 00955 unsigned_type new_pages = div_ceil(new_bids_size, page_size); 00956 _page_status.resize(new_pages); 00957 00958 unsigned_type first_page_to_evict = div_ceil(new_bids_size, page_size); 00959 // clear dirty flag, so these pages will be never written 00960 std::fill(_page_status.begin() + first_page_to_evict, 00961 _page_status.end(), (unsigned char)valid_on_disk); 00962 } 00963 00964 _size = n; 00965 } 00966 00967 public: 00968 void clear() 00969 { 00970 _size = 0; 00971 if (_from == NULL) 00972 bm->delete_blocks(_bids.begin(), _bids.end()); 00973 00974 _bids.clear(); 00975 _page_status.clear(); 00976 _page_to_slot.clear(); 00977 while (!_free_slots.empty()) 00978 _free_slots.pop(); 00979 00980 00981 for (int_type i = 0; i < n_pages; ++i) 00982 _free_slots.push(i); 00983 } 00984 00985 void push_back(const_reference obj) 00986 { 00987 size_type old_size = _size; 00988 resize(old_size + 1); 00989 element(old_size) = obj; 00990 } 00991 void pop_back() 00992 { 00993 resize(_size - 1); 00994 } 00995 00996 reference back() 00997 { 00998 return element(_size - 1); 00999 } 01000 reference front() 01001 { 01002 return element(0); 01003 } 01004 const_reference back() const 01005 { 01006 return const_element(_size - 1); 01007 } 01008 const_reference front() const 01009 { 01010 return const_element(0); 01011 } 01012 01018 vector(file * from, size_type size = size_type(-1)) : 01019 _size((size == size_type(-1)) ? size_from_file_length(from->size()) : size), 01020 _bids(div_ceil(_size, size_type(block_type::size))), 01021 _page_status(div_ceil(_bids.size(), page_size)), 01022 _page_to_slot(div_ceil(_bids.size(), page_size)), 01023 _slot_to_page(n_pages), 01024 _cache(NULL), 01025 _from(from), 01026 exported(false) 01027 { 01028 // initialize from file 01029 if (!block_type::has_only_data) 01030 { 01031 std::ostringstream str_; 01032 str_ << "The block size for a vector that is mapped to a file must be a multiple of the element size (" << 01033 sizeof(value_type) << ") and the page size (4096)."; 01034 throw std::runtime_error(str_.str()); 01035 } 01036 01037 bm = block_manager::get_instance(); 01038 cfg = config::get_instance(); 01039 01040 allocate_page_cache(); 01041 int_type all_pages = div_ceil(_bids.size(), page_size); 01042 int_type i = 0; 01043 for ( ; i < all_pages; ++i) 01044 { 01045 _page_status[i] = valid_on_disk; 01046 _page_to_slot[i] = on_disk; 01047 } 01048 01049 for (i = 0; i < n_pages; ++i) 01050 _free_slots.push(i); 01051 01052 01053 //allocate blocks equidistantly and in-order 01054 size_type offset = 0; 01055 bids_container_iterator it = _bids.begin(); 01056 for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size)) 01057 { 01058 (*it).storage = from; 01059 (*it).offset = offset; 01060 } 01061 from->set_size(offset); 01062 } 01063 01064 vector(const vector & obj) : 01065 _size(obj.size()), 01066 _bids(div_ceil(obj.size(), block_type::size)), 01067 _page_status(div_ceil(_bids.size(), page_size)), 01068 _page_to_slot(div_ceil(_bids.size(), page_size)), 01069 _slot_to_page(n_pages), 01070 _cache(NULL), 01071 _from(NULL), 01072 exported(false) 01073 { 01074 assert(!obj.exported); 01075 bm = block_manager::get_instance(); 01076 cfg = config::get_instance(); 01077 01078 allocate_page_cache(); 01079 int_type all_pages = div_ceil(_bids.size(), page_size); 01080 int_type i = 0; 01081 for ( ; i < all_pages; ++i) 01082 { 01083 _page_status[i] = uninitialized; 01084 _page_to_slot[i] = on_disk; 01085 } 01086 01087 for (i = 0; i < n_pages; ++i) 01088 _free_slots.push(i); 01089 01090 bm->new_blocks(alloc_strategy, _bids.begin(), _bids.end(), 0); 01091 01092 const_iterator inbegin = obj.begin(); 01093 const_iterator inend = obj.end(); 01094 std::copy(inbegin, inend, begin()); 01095 } 01096 01097 vector & operator = (const vector & obj) 01098 { 01099 if (&obj != this) 01100 { 01101 vector tmp(obj); 01102 this->swap(tmp); 01103 } 01104 return *this; 01105 } 01106 01107 size_type size() const 01108 { 01109 return _size; 01110 } 01111 bool empty() const 01112 { 01113 return (!_size); 01114 } 01115 iterator begin() 01116 { 01117 return iterator(this, 0); 01118 } 01119 const_iterator begin() const 01120 { 01121 return const_iterator(this, 0); 01122 } 01123 const_iterator cbegin() const 01124 { 01125 return begin(); 01126 } 01127 iterator end() 01128 { 01129 return iterator(this, _size); 01130 } 01131 const_iterator end() const 01132 { 01133 return const_iterator(this, _size); 01134 } 01135 const_iterator cend() const 01136 { 01137 return end(); 01138 } 01139 01140 reverse_iterator rbegin() 01141 { 01142 return reverse_iterator(end()); 01143 } 01144 const_reverse_iterator rbegin() const 01145 { 01146 return const_reverse_iterator(end()); 01147 } 01148 const_reverse_iterator crbegin() const 01149 { 01150 return const_reverse_iterator(end()); 01151 } 01152 reverse_iterator rend() 01153 { 01154 return reverse_iterator(begin()); 01155 } 01156 const_reverse_iterator rend() const 01157 { 01158 return const_reverse_iterator(begin()); 01159 } 01160 const_reverse_iterator crend() const 01161 { 01162 return const_reverse_iterator(begin()); 01163 } 01164 01165 reference operator [] (size_type offset) 01166 { 01167 return element(offset); 01168 } 01169 const_reference operator [] (size_type offset) const 01170 { 01171 return const_element(offset); 01172 } 01173 01174 bool is_element_cached(size_type offset) const 01175 { 01176 return is_page_cached(blocked_index_type(offset)); 01177 } 01178 01179 void flush() const 01180 { 01181 simple_vector<bool> non_free_slots(n_pages); 01182 int_type i = 0; 01183 for ( ; i < n_pages; i++) 01184 non_free_slots[i] = true; 01185 01186 while (!_free_slots.empty()) 01187 { 01188 non_free_slots[_free_slots.front()] = false; 01189 _free_slots.pop(); 01190 } 01191 01192 for (i = 0; i < n_pages; i++) 01193 { 01194 _free_slots.push(i); 01195 int_type page_no = _slot_to_page[i]; 01196 if (non_free_slots[i]) 01197 { 01198 STXXL_VERBOSE1("vector: flushing page " << i << " at address " 01199 << (int64(page_no) * int64(block_type::size) * int64(page_size))); 01200 write_page(page_no, i); 01201 01202 _page_to_slot[page_no] = on_disk; 01203 } 01204 } 01205 } 01206 01207 ~vector() 01208 { 01209 STXXL_VERBOSE("~vector()"); 01210 try 01211 { 01212 flush(); 01213 } 01214 catch (io_error e) 01215 { 01216 STXXL_ERRMSG("io_error thrown in ~vector(): " << e.what()); 01217 } 01218 catch (...) 01219 { 01220 STXXL_ERRMSG("Exception thrown in ~vector()"); 01221 } 01222 01223 if (!exported) 01224 { 01225 if (_from == NULL) 01226 bm->delete_blocks(_bids.begin(), _bids.end()); 01227 else // file must be truncated 01228 { 01229 STXXL_VERBOSE1("~vector(): Changing size of file " << ((void *)_from) << " to " 01230 << file_length()); 01231 STXXL_VERBOSE1("~vector(): size of the vector is " << size()); 01232 try 01233 { 01234 _from->set_size(file_length()); 01235 } 01236 catch (...) 01237 { 01238 STXXL_ERRMSG("Exception thrown in ~vector()...set_size()"); 01239 } 01240 } 01241 } 01242 delete _cache; 01243 } 01244 01247 void export_files(std::string filename_prefix) 01248 { 01249 int64 no = 0; 01250 for (bids_container_iterator i = _bids.begin(); i != _bids.end(); ++i) { 01251 std::ostringstream number; 01252 number << std::setw(9) << std::setfill('0') << no; 01253 size_type current_block_size = 01254 ((i + 1) == _bids.end() && _size % block_type::size > 0) ? 01255 (_size % block_type::size) * sizeof(value_type) : 01256 block_type::size * sizeof(value_type); 01257 (*i).storage->export_files((*i).offset, current_block_size, filename_prefix + number.str()); 01258 ++no; 01259 } 01260 exported = true; 01261 } 01262 01264 file * get_file() const 01265 { 01266 return _from; 01267 } 01268 01271 template <typename ForwardIterator> 01272 void set_content(const ForwardIterator & bid_begin, const ForwardIterator & bid_end, size_type n) 01273 { 01274 unsigned_type new_bids_size = div_ceil(n, block_type::size); 01275 _bids.resize(new_bids_size); 01276 std::copy(bid_begin, bid_end, _bids.begin()); 01277 unsigned_type new_pages = div_ceil(new_bids_size, page_size); 01278 _page_status.resize(new_pages, valid_on_disk); 01279 _page_to_slot.resize(new_pages, on_disk); 01280 _size = n; 01281 } 01282 01283 private: 01284 bids_container_iterator bid(const size_type & offset) 01285 { 01286 return (_bids.begin() + 01287 static_cast<typename bids_container_type::size_type> 01288 (offset / block_type::size)); 01289 } 01290 bids_container_iterator bid(const blocked_index_type & offset) 01291 { 01292 return (_bids.begin() + 01293 static_cast<typename bids_container_type::size_type> 01294 (offset.get_block2() * PgSz_ + offset.get_block1())); 01295 } 01296 const_bids_container_iterator bid(const size_type & offset) const 01297 { 01298 return (_bids.begin() + 01299 static_cast<typename bids_container_type::size_type> 01300 (offset / block_type::size)); 01301 } 01302 const_bids_container_iterator bid(const blocked_index_type & offset) const 01303 { 01304 return (_bids.begin() + 01305 static_cast<typename bids_container_type::size_type> 01306 (offset.get_block2() * PgSz_ + offset.get_block1())); 01307 } 01308 01309 void read_page(int_type page_no, int_type cache_slot) const 01310 { 01311 if (_page_status[page_no] == uninitialized) 01312 return; 01313 STXXL_VERBOSE1("vector " << this << ": reading page_no=" << page_no << " cache_slot=" << cache_slot); 01314 request_ptr * reqs = new request_ptr[page_size]; 01315 int_type block_no = page_no * page_size; 01316 int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size())); 01317 int_type i = cache_slot * page_size, j = 0; 01318 for ( ; block_no < last_block; ++block_no, ++i, ++j) 01319 { 01320 reqs[j] = (*_cache)[i].read(_bids[block_no]); 01321 } 01322 assert(last_block - page_no * page_size > 0); 01323 wait_all(reqs, last_block - page_no * page_size); 01324 delete[] reqs; 01325 } 01326 void write_page(int_type page_no, int_type cache_slot) const 01327 { 01328 if (!(_page_status[page_no] & dirty)) 01329 return; 01330 STXXL_VERBOSE1("vector " << this << ": writing page_no=" << page_no << " cache_slot=" << cache_slot); 01331 request_ptr * reqs = new request_ptr[page_size]; 01332 int_type block_no = page_no * page_size; 01333 int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size())); 01334 int_type i = cache_slot * page_size, j = 0; 01335 for ( ; block_no < last_block; ++block_no, ++i, ++j) 01336 { 01337 reqs[j] = (*_cache)[i].write(_bids[block_no]); 01338 } 01339 _page_status[page_no] = valid_on_disk; 01340 assert(last_block - page_no * page_size > 0); 01341 wait_all(reqs, last_block - page_no * page_size); 01342 delete[] reqs; 01343 } 01344 01345 reference element(size_type offset) 01346 { 01347 #ifdef STXXL_RANGE_CHECK 01348 assert(offset < size()); 01349 #endif 01350 return element(blocked_index_type(offset)); 01351 } 01352 01353 reference element(const blocked_index_type & offset) 01354 { 01355 #ifdef STXXL_RANGE_CHECK 01356 assert(offset.get_pos() < size()); 01357 #endif 01358 int_type page_no = offset.get_block2(); 01359 assert(page_no < int_type(_page_to_slot.size())); // fails if offset is too large, out of bound access 01360 int_type cache_slot = _page_to_slot[page_no]; 01361 if (cache_slot < 0) // == on_disk 01362 { 01363 if (_free_slots.empty()) // has to kick 01364 { 01365 int_type kicked_slot = pager.kick(); 01366 pager.hit(kicked_slot); 01367 int_type old_page_no = _slot_to_page[kicked_slot]; 01368 _page_to_slot[page_no] = kicked_slot; 01369 _page_to_slot[old_page_no] = on_disk; 01370 _slot_to_page[kicked_slot] = page_no; 01371 01372 write_page(old_page_no, kicked_slot); 01373 read_page(page_no, kicked_slot); 01374 01375 _page_status[page_no] = dirty; 01376 01377 return (*_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()]; 01378 } 01379 else 01380 { 01381 int_type free_slot = _free_slots.front(); 01382 _free_slots.pop(); 01383 pager.hit(free_slot); 01384 _page_to_slot[page_no] = free_slot; 01385 _slot_to_page[free_slot] = page_no; 01386 01387 read_page(page_no, free_slot); 01388 01389 _page_status[page_no] = dirty; 01390 01391 return (*_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()]; 01392 } 01393 } 01394 else 01395 { 01396 _page_status[page_no] = dirty; 01397 pager.hit(cache_slot); 01398 return (*_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()]; 01399 } 01400 } 01401 01402 // don't forget to first flush() the vector's cache before updating pages externally 01403 void page_externally_updated(unsigned_type page_no) const 01404 { 01405 // fails if offset is too large, out of bound access 01406 assert(page_no < _page_status.size()); 01407 // "A dirty page has been marked as newly initialized. The page content will be lost." 01408 assert(!(_page_status[page_no] & dirty)); 01409 if (_page_to_slot[page_no] != on_disk) { 01410 // remove page from cache 01411 _free_slots.push(_page_to_slot[page_no]); 01412 _page_to_slot[page_no] = on_disk; 01413 } 01414 _page_status[page_no] = valid_on_disk; 01415 } 01416 01417 void block_externally_updated(size_type offset) const 01418 { 01419 page_externally_updated(offset / (block_type::size * page_size)); 01420 } 01421 01422 void block_externally_updated(const blocked_index_type & offset) const 01423 { 01424 page_externally_updated(offset.get_block2()); 01425 } 01426 01427 _STXXL_DEPRECATED(void touch(size_type offset) const) 01428 { 01429 page_externally_updated(offset / (block_type::size * page_size)); 01430 } 01431 01432 _STXXL_DEPRECATED(void touch(const blocked_index_type & offset) const) 01433 { 01434 page_externally_updated(offset.get_block2()); 01435 } 01436 01437 const_reference const_element(size_type offset) const 01438 { 01439 return const_element(blocked_index_type(offset)); 01440 } 01441 01442 const_reference const_element(const blocked_index_type & offset) const 01443 { 01444 int_type page_no = offset.get_block2(); 01445 assert(page_no < int_type(_page_to_slot.size())); // fails if offset is too large, out of bound access 01446 int_type cache_slot = _page_to_slot[page_no]; 01447 if (cache_slot < 0) // == on_disk 01448 { 01449 if (_free_slots.empty()) // has to kick 01450 { 01451 int_type kicked_slot = pager.kick(); 01452 pager.hit(kicked_slot); 01453 int_type old_page_no = _slot_to_page[kicked_slot]; 01454 _page_to_slot[page_no] = kicked_slot; 01455 _page_to_slot[old_page_no] = on_disk; 01456 _slot_to_page[kicked_slot] = page_no; 01457 01458 write_page(old_page_no, kicked_slot); 01459 read_page(page_no, kicked_slot); 01460 01461 return (*_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()]; 01462 } 01463 else 01464 { 01465 int_type free_slot = _free_slots.front(); 01466 _free_slots.pop(); 01467 pager.hit(free_slot); 01468 _page_to_slot[page_no] = free_slot; 01469 _slot_to_page[free_slot] = page_no; 01470 01471 read_page(page_no, free_slot); 01472 01473 return (*_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()]; 01474 } 01475 } 01476 else 01477 { 01478 pager.hit(cache_slot); 01479 return (*_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()]; 01480 } 01481 } 01482 01483 bool is_page_cached(const blocked_index_type & offset) const 01484 { 01485 int_type page_no = offset.get_block2(); 01486 assert(page_no < int_type(_page_to_slot.size())); // fails if offset is too large, out of bound access 01487 int_type cache_slot = _page_to_slot[page_no]; 01488 return (cache_slot >= 0); // on_disk == -1 01489 } 01490 }; 01491 01492 template < 01493 typename Tp_, 01494 unsigned PgSz_, 01495 typename PgTp_, 01496 unsigned BlkSize_, 01497 typename AllocStr_, 01498 typename SzTp_> 01499 inline bool operator == (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01500 AllocStr_, SzTp_> & a, 01501 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01502 AllocStr_, SzTp_> & b) 01503 { 01504 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); 01505 } 01506 01507 template < 01508 typename Tp_, 01509 unsigned PgSz_, 01510 typename PgTp_, 01511 unsigned BlkSize_, 01512 typename AllocStr_, 01513 typename SzTp_> 01514 inline bool operator != (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01515 AllocStr_, SzTp_> & a, 01516 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01517 AllocStr_, SzTp_> & b) 01518 { 01519 return !(a == b); 01520 } 01521 01522 template < 01523 typename Tp_, 01524 unsigned PgSz_, 01525 typename PgTp_, 01526 unsigned BlkSize_, 01527 typename AllocStr_, 01528 typename SzTp_> 01529 inline bool operator < (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01530 AllocStr_, SzTp_> & a, 01531 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01532 AllocStr_, SzTp_> & b) 01533 { 01534 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); 01535 } 01536 01537 template < 01538 typename Tp_, 01539 unsigned PgSz_, 01540 typename PgTp_, 01541 unsigned BlkSize_, 01542 typename AllocStr_, 01543 typename SzTp_> 01544 inline bool operator > (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01545 AllocStr_, SzTp_> & a, 01546 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01547 AllocStr_, SzTp_> & b) 01548 { 01549 return b < a; 01550 } 01551 01552 template < 01553 typename Tp_, 01554 unsigned PgSz_, 01555 typename PgTp_, 01556 unsigned BlkSize_, 01557 typename AllocStr_, 01558 typename SzTp_> 01559 inline bool operator <= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01560 AllocStr_, SzTp_> & a, 01561 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01562 AllocStr_, SzTp_> & b) 01563 { 01564 return !(b < a); 01565 } 01566 01567 template < 01568 typename Tp_, 01569 unsigned PgSz_, 01570 typename PgTp_, 01571 unsigned BlkSize_, 01572 typename AllocStr_, 01573 typename SzTp_> 01574 inline bool operator >= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01575 AllocStr_, SzTp_> & a, 01576 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01577 AllocStr_, SzTp_> & b) 01578 { 01579 return !(a < b); 01580 } 01581 01583 01585 01586 // specialization for stxxl::vector, to use only const_iterators 01587 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 01588 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 01589 bool is_sorted( 01590 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first, 01591 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last) 01592 { 01593 return is_sorted_helper( 01594 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first), 01595 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last)); 01596 } 01597 01598 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 01599 unsigned BlkSize_, typename PgTp_, unsigned PgSz_, typename _StrictWeakOrdering> 01600 bool is_sorted( 01601 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first, 01602 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last, 01603 _StrictWeakOrdering __comp) 01604 { 01605 return is_sorted_helper( 01606 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first), 01607 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last), 01608 __comp); 01609 } 01610 01612 01615 01617 01639 template < 01640 typename Tp_, 01641 unsigned PgSz_ = 4, 01642 unsigned Pages_ = 8, 01643 unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_), 01644 typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY, 01645 pager_type Pager_ = lru 01646 > 01647 struct VECTOR_GENERATOR 01648 { 01649 typedef typename IF<Pager_ == lru, 01650 lru_pager<Pages_>, random_pager<Pages_> >::result PagerType; 01651 01652 typedef vector<Tp_, PgSz_, PagerType, BlkSize_, AllocStr_> result; 01653 }; 01654 01655 01657 01658 __STXXL_END_NAMESPACE 01659 01660 01661 namespace std 01662 { 01663 template < 01664 typename Tp_, 01665 unsigned PgSz_, 01666 typename PgTp_, 01667 unsigned BlkSize_, 01668 typename AllocStr_, 01669 typename SzTp_> 01670 void swap(stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & a, 01671 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & b) 01672 { 01673 a.swap(b); 01674 } 01675 } 01676 01677 #endif // !STXXL_VECTOR_HEADER 01678 // vim: et:ts=4:sw=4