Stxxl 1.2.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-2007 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2007, 2008 Johannes Singler <singler@ira.uka.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 00012 **************************************************************************/ 00013 00014 #ifndef STXXL_VECTOR_HEADER 00015 #define STXXL_VECTOR_HEADER 00016 00017 #include <vector> 00018 #include <algorithm> 00019 00020 #include <stxxl/bits/mng/mng.h> 00021 #include <stxxl/bits/common/tmeta.h> 00022 #include <stxxl/bits/containers/pager.h> 00023 #include <stxxl/bits/common/is_sorted.h> 00024 00025 00026 __STXXL_BEGIN_NAMESPACE 00027 00031 00032 00036 00037 template <unsigned_type modulo2, unsigned_type modulo1> 00038 class double_blocked_index 00039 { 00040 static const unsigned_type modulo12 = modulo1 * modulo2; 00041 00042 unsigned_type pos; 00043 unsigned_type block1, block2; 00044 unsigned_type offset; 00045 00047 00048 void set(unsigned_type pos) 00049 { 00050 this->pos = pos; 00051 block2 = pos / modulo12; 00052 pos -= block2 * modulo12; 00053 block1 = pos / modulo1; 00054 offset = (pos - block1 * modulo1); 00055 00056 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00057 assert(/* 0 <= block1 && */ block1 < modulo2); 00058 assert(/* 0 <= offset && */ offset < modulo1); 00059 } 00060 00061 public: 00062 double_blocked_index() 00063 { 00064 set(0); 00065 } 00066 00067 double_blocked_index(unsigned_type pos) 00068 { 00069 set(pos); 00070 } 00071 00072 double_blocked_index(unsigned_type block2, unsigned_type block1, unsigned_type) 00073 { 00074 this->block2 = block2; 00075 this->block1 = block1; 00076 this->offset = offset; 00077 pos = block2 * modulo12 + block1 * modulo1 + offset; 00078 00079 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00080 assert(/* 0 <= block1 && */ block1 < modulo2); 00081 assert(/* 0 <= offset && */ offset < modulo1); 00082 } 00083 00084 double_blocked_index & operator = (unsigned_type pos) 00085 { 00086 set(pos); 00087 return *this; 00088 } 00089 00090 //pre-increment operator 00091 double_blocked_index & operator ++ () 00092 { 00093 ++pos; 00094 ++offset; 00095 if (offset == modulo1) 00096 { 00097 offset = 0; 00098 ++block1; 00099 if (block1 == modulo2) 00100 { 00101 block1 = 0; 00102 ++block2; 00103 } 00104 } 00105 00106 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00107 assert(/* 0 <= block1 && */ block1 < modulo2); 00108 assert(/* 0 <= offset && */ offset < modulo1); 00109 00110 return *this; 00111 } 00112 00113 //post-increment operator 00114 double_blocked_index operator ++ (int) 00115 { 00116 double_blocked_index former(*this); 00117 operator ++ (); 00118 return former; 00119 } 00120 00121 //pre-increment operator 00122 double_blocked_index & operator -- () 00123 { 00124 --pos; 00125 if (offset == 0) 00126 { 00127 offset = modulo1; 00128 if (block1 == 0) 00129 { 00130 block1 = modulo2; 00131 --block2; 00132 } 00133 --block1; 00134 } 00135 --offset; 00136 00137 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos); 00138 assert(/*0 <= block1 &&*/ block1 < modulo2); 00139 assert(/*0 <= offset &&*/ offset < modulo1); 00140 00141 return *this; 00142 } 00143 00144 //post-increment operator 00145 double_blocked_index operator -- (int) 00146 { 00147 double_blocked_index former(*this); 00148 operator -- (); 00149 return former; 00150 } 00151 00152 double_blocked_index operator + (unsigned_type addend) const 00153 { 00154 return double_blocked_index(pos + addend); 00155 } 00156 00157 double_blocked_index & operator += (unsigned_type addend) 00158 { 00159 set(pos + addend); 00160 return *this; 00161 } 00162 00163 double_blocked_index operator - (unsigned_type addend) const 00164 { 00165 return double_blocked_index(pos - addend); 00166 } 00167 00168 unsigned_type operator - (const double_blocked_index & dbi2) const 00169 { 00170 return pos - dbi2.pos; 00171 } 00172 00173 double_blocked_index & operator -= (unsigned_type subtrahend) 00174 { 00175 set(pos - subtrahend); 00176 return *this; 00177 } 00178 00179 bool operator == (const double_blocked_index & dbi2) const 00180 { 00181 return pos == dbi2.pos; 00182 } 00183 00184 bool operator != (const double_blocked_index & dbi2) const 00185 { 00186 return pos != dbi2.pos; 00187 } 00188 00189 bool operator < (const double_blocked_index & dbi2) const 00190 { 00191 return pos < dbi2.pos; 00192 } 00193 00194 bool operator <= (const double_blocked_index & dbi2) const 00195 { 00196 return pos <= dbi2.pos; 00197 } 00198 00199 bool operator > (const double_blocked_index & dbi2) const 00200 { 00201 return pos > dbi2.pos; 00202 } 00203 00204 bool operator >= (const double_blocked_index & dbi2) const 00205 { 00206 return pos >= dbi2.pos; 00207 } 00208 00209 double_blocked_index & operator >>= (unsigned_type shift) 00210 { 00211 set(pos >> shift); 00212 return *this; 00213 } 00214 00215 unsigned_type get_pos() const 00216 { 00217 return pos; 00218 } 00219 00220 const unsigned_type & get_block2() const 00221 { 00222 return block2; 00223 } 00224 00225 const unsigned_type & get_block1() const 00226 { 00227 return block1; 00228 } 00229 00230 const unsigned_type & get_offset() const 00231 { 00232 return offset; 00233 } 00234 }; 00235 00236 00237 template <unsigned BlkSize_> 00238 class bid_vector : public std::vector<BID<BlkSize_> > 00239 { 00240 public: 00241 enum 00242 { block_size = BlkSize_ }; 00243 typedef bid_vector<block_size> _Self; 00244 typedef std::vector<BID<BlkSize_> > _Derived; 00245 typedef unsigned size_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_, 00273 BlkSize_, PgTp_, PgSz_> _Self; 00274 typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, 00275 BlkSize_, PgTp_, PgSz_> _CIterator; 00276 00277 friend class const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>; 00278 00279 public: 00280 typedef _CIterator const_iterator; 00281 typedef _Self iterator; 00282 00283 typedef SzTp_ size_type; 00284 typedef DiffTp_ difference_type; 00285 typedef unsigned block_offset_type; 00286 typedef vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> vector_type; 00287 friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>; 00288 typedef bid_vector<BlkSize_> bids_container_type; 00289 typedef typename bids_container_type::iterator bids_container_iterator; 00290 typedef typed_block<BlkSize_, Tp_> block_type; 00291 typedef BID<BlkSize_> bid_type; 00292 00293 typedef std::random_access_iterator_tag iterator_category; 00294 typedef typename vector_type::value_type value_type; 00295 typedef typename vector_type::reference reference; 00296 typedef typename vector_type::const_reference const_reference; 00297 typedef typename vector_type::pointer pointer; 00298 typedef typename vector_type::const_pointer const_pointer; 00299 00300 enum { block_size = BlkSize_ }; 00301 00302 protected: 00303 double_blocked_index<PgSz_, block_type::size> offset; 00304 vector_type * p_vector; 00305 00306 private: 00307 vector_iterator(vector_type * v, size_type o) : offset(o), 00308 p_vector(v) 00309 { } 00310 00311 public: 00312 vector_iterator() : offset(0), p_vector(NULL) { } 00313 vector_iterator(const _Self & a) : 00314 offset(a.offset), 00315 p_vector(a.p_vector) { } 00316 00317 block_offset_type block_offset() const 00318 { 00319 return static_cast<block_offset_type>(offset.get_offset()); 00320 } 00321 bids_container_iterator bid() const 00322 { 00323 return p_vector->bid(offset); 00324 } 00325 00326 difference_type operator - (const _Self & a) const 00327 { 00328 return offset - a.offset; 00329 } 00330 00331 difference_type operator - (const const_iterator & a) const 00332 { 00333 return offset - a.offset; 00334 } 00335 00336 _Self operator - (size_type op) const 00337 { 00338 return _Self(p_vector, offset.get_pos() - op); 00339 } 00340 00341 _Self operator + (size_type op) const 00342 { 00343 return _Self(p_vector, offset.get_pos() + op); 00344 } 00345 00346 _Self & operator -= (size_type op) 00347 { 00348 offset -= op; 00349 return *this; 00350 } 00351 00352 _Self & operator += (size_type op) 00353 { 00354 offset += op; 00355 return *this; 00356 } 00357 00358 reference operator * () 00359 { 00360 return p_vector->element(offset); 00361 } 00362 00363 pointer operator -> () 00364 { 00365 return &(p_vector->element(offset)); 00366 } 00367 00368 const_reference operator * () const 00369 { 00370 return p_vector->const_element(offset); 00371 } 00372 00373 const_pointer operator -> () const 00374 { 00375 return &(p_vector->const_element(offset)); 00376 } 00377 00378 reference operator [] (size_type op) 00379 { 00380 return p_vector->element(offset.get_pos() + op); 00381 } 00382 00383 const_reference operator [] (size_type op) const 00384 { 00385 return p_vector->const_element(offset.get_pos() + op); 00386 } 00387 00388 void touch() 00389 { 00390 p_vector->touch(offset); 00391 } 00392 00393 _Self & operator ++ () 00394 { 00395 offset++; 00396 return *this; 00397 } 00398 _Self operator ++ (int) 00399 { 00400 _Self __tmp = *this; 00401 offset++; 00402 return __tmp; 00403 } 00404 _Self & operator -- () 00405 { 00406 offset--; 00407 return *this; 00408 } 00409 _Self operator -- (int) 00410 { 00411 _Self __tmp = *this; 00412 offset--; 00413 return __tmp; 00414 } 00415 bool operator == (const _Self & a) const 00416 { 00417 assert(p_vector == a.p_vector); 00418 return offset == a.offset; 00419 } 00420 bool operator != (const _Self & a) const 00421 { 00422 assert(p_vector == a.p_vector); 00423 return offset != a.offset; 00424 } 00425 bool operator < (const _Self & a) const 00426 { 00427 assert(p_vector == a.p_vector); 00428 return offset < a.offset; 00429 } 00430 bool operator <= (const _Self & a) const 00431 { 00432 assert(p_vector == a.p_vector); 00433 return offset <= a.offset; 00434 } 00435 bool operator > (const _Self & a) const 00436 { 00437 assert(p_vector == a.p_vector); 00438 return a > *this; 00439 } 00440 bool operator >= (const _Self & a) const 00441 { 00442 assert(p_vector == a.p_vector); 00443 return a >= *this; 00444 } 00445 00446 bool operator == (const const_iterator & a) const 00447 { 00448 assert(p_vector == a.p_vector); 00449 return offset == a.offset; 00450 } 00451 bool operator != (const const_iterator & a) const 00452 { 00453 assert(p_vector == a.p_vector); 00454 return offset != a.offset; 00455 } 00456 bool operator < (const const_iterator & a) const 00457 { 00458 assert(p_vector == a.p_vector); 00459 return offset < a.offset; 00460 } 00461 bool operator <= (const const_iterator & a) const 00462 { 00463 assert(p_vector == a.p_vector); 00464 return offset <= a.offset; 00465 } 00466 bool operator > (const const_iterator & a) const 00467 { 00468 assert(p_vector == a.p_vector); 00469 return a > *this; 00470 } 00471 bool operator >= (const const_iterator & a) const 00472 { 00473 assert(p_vector == a.p_vector); 00474 return a >= *this; 00475 } 00476 00477 void flush() 00478 { 00479 p_vector->flush(); 00480 } 00481 /* 00482 std::ostream & operator<< (std::ostream & o) const 00483 { 00484 o << "vectorpointer: " << ((void*)p_vector) <<" offset: "<<offset; 00485 return o; 00486 }*/ 00487 }; 00488 00490 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00491 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00492 class const_vector_iterator 00493 { 00494 typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, 00495 BlkSize_, PgTp_, PgSz_> _Self; 00496 typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, 00497 BlkSize_, PgTp_, PgSz_> _NonConstIterator; 00498 00499 friend class vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>; 00500 00501 public: 00502 typedef _Self const_iterator; 00503 typedef _NonConstIterator iterator; 00504 00505 typedef SzTp_ size_type; 00506 typedef DiffTp_ difference_type; 00507 typedef unsigned block_offset_type; 00508 typedef vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> vector_type; 00509 friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>; 00510 typedef bid_vector<BlkSize_> bids_container_type; 00511 typedef typename bids_container_type::iterator bids_container_iterator; 00512 typedef typed_block<BlkSize_, Tp_> block_type; 00513 typedef BID<BlkSize_> bid_type; 00514 00515 typedef std::random_access_iterator_tag iterator_category; 00516 typedef typename vector_type::value_type value_type; 00517 typedef typename vector_type::reference reference; 00518 typedef typename vector_type::const_reference const_reference; 00519 typedef typename vector_type::pointer pointer; 00520 typedef typename vector_type::const_pointer const_pointer; 00521 00522 enum { block_size = BlkSize_ }; 00523 00524 protected: 00525 double_blocked_index<PgSz_, block_type::size> 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 touch() 00603 { 00604 p_vector->touch(offset); 00605 } 00606 00607 _Self & operator ++ () 00608 { 00609 offset++; 00610 return *this; 00611 } 00612 _Self operator ++ (int) 00613 { 00614 _Self tmp_ = *this; 00615 offset++; 00616 return tmp_; 00617 } 00618 _Self & operator -- () 00619 { 00620 offset--; 00621 return *this; 00622 } 00623 _Self operator -- (int) 00624 { 00625 _Self __tmp = *this; 00626 offset--; 00627 return __tmp; 00628 } 00629 bool operator == (const _Self & a) const 00630 { 00631 assert(p_vector == a.p_vector); 00632 return offset == a.offset; // or (offset + stxxl::int64(p_vector)) 00633 } 00634 bool operator != (const _Self & a) const 00635 { 00636 assert(p_vector == a.p_vector); 00637 return offset != a.offset; 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 00660 bool operator == (const iterator & a) const 00661 { 00662 assert(p_vector == a.p_vector); 00663 return offset == a.offset; // or (offset + stxxl::int64(p_vector)) 00664 } 00665 bool operator != (const iterator & a) const 00666 { 00667 assert(p_vector == a.p_vector); 00668 return offset != a.offset; 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 00691 void flush() 00692 { 00693 p_vector->flush(); 00694 } 00695 00696 std::ostream & operator << (std::ostream & o) const 00697 { 00698 o << "vectorpointer: " << ((void *)p_vector) << " offset: " << offset; 00699 return o; 00700 } 00701 }; 00702 00703 00705 00718 template < 00719 typename Tp_, 00720 unsigned PgSz_ = 4, 00721 typename PgTp_ = lru_pager<8>, 00722 unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_), 00723 typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY, 00724 typename SzTp_ = stxxl::uint64 // will be deprecated soon 00725 > 00726 class vector 00727 { 00728 public: 00729 typedef Tp_ value_type; 00730 typedef value_type & reference; 00731 typedef const value_type & const_reference; 00732 typedef value_type * pointer; 00733 typedef SzTp_ size_type; 00734 typedef stxxl::int64 difference_type; 00735 typedef const value_type * const_pointer; 00736 00737 typedef PgTp_ pager_type; 00738 typedef AllocStr_ alloc_strategy; 00739 00740 enum { 00741 block_size = BlkSize_, 00742 page_size = PgSz_, 00743 n_pages = pager_type::n_pages, 00744 on_disk = -1 00745 }; 00746 00747 typedef vector_iterator<value_type, alloc_strategy, size_type, 00748 difference_type, block_size, pager_type, page_size> iterator; 00749 friend class vector_iterator<value_type, alloc_strategy, size_type, difference_type, block_size, pager_type, page_size>; 00750 typedef const_vector_iterator<value_type, alloc_strategy, 00751 size_type, difference_type, block_size, pager_type, page_size> const_iterator; 00752 friend class const_vector_iterator<value_type, alloc_strategy, size_type, difference_type, block_size, pager_type, page_size>; 00753 00754 typedef bid_vector<block_size> bids_container_type; 00755 typedef typename bids_container_type:: 00756 iterator bids_container_iterator; 00757 typedef typename bids_container_type:: 00758 const_iterator const_bids_container_iterator; 00759 00760 typedef typed_block<BlkSize_, Tp_> block_type; 00761 00762 private: 00763 alloc_strategy _alloc_strategy; 00764 size_type _size; 00765 bids_container_type _bids; 00766 //bids_container_iterator _bids_finish; 00767 mutable pager_type pager; 00768 00769 enum { uninitialized = 1, dirty = 2 }; 00770 mutable std::vector<unsigned char> _page_status; 00771 mutable std::vector<int_type> _last_page; 00772 mutable simple_vector<int_type> _page_no; 00773 mutable std::queue<int_type> _free_pages; 00774 mutable simple_vector<block_type> _cache; 00775 file * _from; 00776 block_manager * bm; 00777 config * cfg; 00778 00779 size_type size_from_file_length(stxxl::uint64 file_length) 00780 { 00781 stxxl::uint64 blocks_fit = file_length / stxxl::uint64(block_type::raw_size); 00782 size_type cur_size = blocks_fit * stxxl::uint64(block_type::size); 00783 stxxl::uint64 rest = file_length - blocks_fit * stxxl::uint64(block_type::raw_size); 00784 return (cur_size + rest / stxxl::uint64(sizeof(value_type))); 00785 } 00786 stxxl::uint64 file_length() 00787 { 00788 size_type cur_size = size(); 00789 if (cur_size % size_type(block_type::size)) 00790 { 00791 stxxl::uint64 full_blocks_length = size_type(_bids.size() - 1) * size_type(block_type::raw_size); 00792 size_type rest = cur_size - size_type(_bids.size() - 1) * size_type(block_type::size); 00793 return full_blocks_length + rest * size_type(sizeof(value_type)); 00794 } 00795 return size_type(_bids.size()) * size_type(block_type::raw_size); 00796 } 00797 00798 public: 00799 vector(size_type n = 0) : 00800 _size(n), 00801 _bids(div_and_round_up(n, block_type::size)), 00802 _page_status(div_and_round_up(_bids.size(), page_size)), 00803 _last_page(div_and_round_up(_bids.size(), page_size)), 00804 _page_no(n_pages), 00805 _cache(n_pages * page_size), 00806 _from(NULL) 00807 { 00808 bm = block_manager::get_instance(); 00809 cfg = config::get_instance(); 00810 00811 int_type all_pages = div_and_round_up(_bids.size(), page_size); 00812 int_type i = 0; 00813 for ( ; i < all_pages; ++i) 00814 { 00815 _page_status[i] = uninitialized; 00816 _last_page[i] = on_disk; 00817 } 00818 00819 for (i = 0; i < n_pages; ++i) 00820 _free_pages.push(i); 00821 00822 00823 bm->new_blocks(_alloc_strategy, _bids.begin(), 00824 _bids.end()); 00825 } 00826 00827 void swap(vector & obj) 00828 { 00829 std::swap(_alloc_strategy, obj._alloc_strategy); 00830 std::swap(_size, obj._size); 00831 std::swap(_bids, obj._bids); 00832 std::swap(pager, obj.pager); 00833 std::swap(_page_status, obj._page_status); 00834 std::swap(_last_page, obj._last_page); 00835 std::swap(_page_no, obj._page_no); 00836 std::swap(_free_pages, obj._free_pages); 00837 std::swap(_cache, obj._cache); 00838 std::swap(_from, obj._from); 00839 } 00840 size_type capacity() const 00841 { 00842 return size_type(_bids.size()) * block_type::size; 00843 } 00844 void reserve(size_type n) 00845 { 00846 if (n <= capacity()) 00847 return; 00848 00849 00850 unsigned_type old_bids_size = _bids.size(); 00851 unsigned_type new_bids_size = div_and_round_up(n, block_type::size); 00852 unsigned_type new_pages = div_and_round_up(new_bids_size, page_size); 00853 _page_status.resize(new_pages, uninitialized); 00854 _last_page.resize(new_pages, on_disk); 00855 00856 _bids.resize(new_bids_size); 00857 if (_from == NULL) 00858 bm->new_blocks(offset_allocator<alloc_strategy>(old_bids_size, _alloc_strategy), 00859 _bids.begin() + old_bids_size, _bids.end()); 00860 00861 else 00862 { 00863 size_type offset = size_type(old_bids_size) * size_type(block_type::raw_size); 00864 bids_container_iterator it = _bids.begin() + old_bids_size; 00865 for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size)) 00866 { 00867 (*it).storage = _from; 00868 (*it).offset = offset; 00869 } 00870 STXXL_VERBOSE1("vector::reserve(): Changing size of file " << ((void *)_from) << " to " 00871 << offset); 00872 _from->set_size(offset); 00873 } 00874 } 00875 void resize(size_type n) 00876 { 00877 #ifndef STXXL_FREE_EXTMEMORY_ON_VECTOR_RESIZE 00878 reserve(n); 00879 #else 00880 unsigned_type old_bids_size = _bids.size(); 00881 unsigned_type new_bids_size = div_and_round_up(n, block_type::size); 00882 00883 00884 if (new_bids_size > old_bids_size) 00885 { 00886 reserve(n); 00887 } 00888 else if (new_bids_size < old_bids_size) 00889 { 00890 bm->delete_blocks(_bids.begin() + new_bids_size, _bids.end()); 00891 _bids.resize(new_bids_size); 00892 00893 unsigned_type first_page_to_evict = div_and_round_up(new_bids_size, page_size); 00894 std::fill(_page_status.begin() + first_page_to_evict, 00895 _page_status.end(), 0); // clear dirty flag, so this pages 00896 // will be never written 00897 } 00898 #endif 00899 00900 _size = n; 00901 } 00902 void clear() 00903 { 00904 _size = 0; 00905 bm->delete_blocks(_bids.begin(), _bids.end()); 00906 00907 _bids.clear(); 00908 _page_status.clear(); 00909 _last_page.clear(); 00910 while (!_free_pages.empty()) 00911 _free_pages.pop(); 00912 00913 00914 for (int_type i = 0; i < n_pages; ++i) 00915 _free_pages.push(i); 00916 } 00917 void push_back(const_reference obj) 00918 { 00919 size_type old_size = _size; 00920 resize(old_size + 1); 00921 element(old_size) = obj; 00922 } 00923 void pop_back() 00924 { 00925 resize(_size - 1); 00926 } 00927 reference back() 00928 { 00929 return element(_size - 1); 00930 } 00931 reference front() 00932 { 00933 return element(0); 00934 } 00935 const_reference back() const 00936 { 00937 return const_element(_size - 1); 00938 } 00939 const_reference front() const 00940 { 00941 return const_element(0); 00942 } 00949 vector(file * from) : 00950 _size(size_from_file_length(from->size())), 00951 _bids(div_and_round_up(_size, size_type(block_type::size))), 00952 _page_status(div_and_round_up(_bids.size(), page_size)), 00953 _last_page(div_and_round_up(_bids.size(), page_size)), 00954 _page_no(n_pages), 00955 _cache(n_pages * page_size), 00956 _from(from) 00957 { 00958 // initialize from file 00959 assert(from->get_id() == -1); 00960 00961 if (block_type::has_filler) 00962 { 00963 std::ostringstream str_; 00964 str_ << "The block size for the vector, mapped to a file must me a multiple of the element size (" << 00965 sizeof(value_type) << ") and the page size (4096)."; 00966 throw std::runtime_error(str_.str()); 00967 } 00968 00969 bm = block_manager::get_instance(); 00970 cfg = config::get_instance(); 00971 00972 int_type all_pages = div_and_round_up(_bids.size(), page_size); 00973 int_type i = 0; 00974 for ( ; i < all_pages; ++i) 00975 { 00976 _page_status[i] = 0; 00977 _last_page[i] = on_disk; 00978 } 00979 00980 for (i = 0; i < n_pages; ++i) 00981 _free_pages.push(i); 00982 00983 00984 size_type offset = 0; 00985 bids_container_iterator it = _bids.begin(); 00986 for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size)) 00987 { 00988 (*it).storage = from; 00989 (*it).offset = offset; 00990 } 00991 from->set_size(offset); 00992 } 00993 00994 vector(const vector & obj) : 00995 _size(obj.size()), 00996 _bids(div_and_round_up(obj.size(), block_type::size)), 00997 _page_status(div_and_round_up(_bids.size(), page_size)), 00998 _last_page(div_and_round_up(_bids.size(), page_size)), 00999 _page_no(n_pages), 01000 _cache(n_pages * page_size), 01001 _from(NULL) 01002 { 01003 bm = block_manager::get_instance(); 01004 cfg = config::get_instance(); 01005 01006 int_type all_pages = div_and_round_up(_bids.size(), page_size); 01007 int_type i = 0; 01008 for ( ; i < all_pages; ++i) 01009 { 01010 _page_status[i] = uninitialized; 01011 _last_page[i] = on_disk; 01012 } 01013 01014 for (i = 0; i < n_pages; ++i) 01015 _free_pages.push(i); 01016 01017 01018 bm->new_blocks(_alloc_strategy, _bids.begin(), 01019 _bids.end()); 01020 01021 const_iterator inbegin = obj.begin(); 01022 const_iterator inend = obj.end(); 01023 std::copy(inbegin, inend, begin()); 01024 } 01025 01026 vector & operator = (const vector & obj) 01027 { 01028 if (&obj != this) 01029 { 01030 vector tmp(obj); 01031 this->swap(tmp); 01032 } 01033 return *this; 01034 } 01035 01036 size_type size() const 01037 { 01038 return _size; 01039 } 01040 bool empty() const 01041 { 01042 return (!_size); 01043 } 01044 iterator begin() 01045 { 01046 return iterator(this, 0); 01047 } 01048 const_iterator begin() const 01049 { 01050 return const_iterator(this, 0); 01051 } 01052 const_iterator cbegin() const 01053 { 01054 return begin(); 01055 } 01056 iterator end() 01057 { 01058 return iterator(this, _size); 01059 } 01060 const_iterator end() const 01061 { 01062 return const_iterator(this, _size); 01063 } 01064 const_iterator cend() const 01065 { 01066 return end(); 01067 } 01068 reference operator [] (size_type offset) 01069 { 01070 return element(offset); 01071 } 01072 const_reference operator [] (size_type offset) const 01073 { 01074 return const_element(offset); 01075 } 01076 01077 void flush() const 01078 { 01079 simple_vector<bool> non_free_pages(n_pages); 01080 int_type i = 0; 01081 for ( ; i < n_pages; i++) 01082 non_free_pages[i] = true; 01083 01084 01085 while (!_free_pages.empty()) 01086 { 01087 non_free_pages[_free_pages.front()] = false; 01088 _free_pages.pop(); 01089 } 01090 01091 for (i = 0; i < n_pages; i++) 01092 { 01093 _free_pages.push(i); 01094 int_type page_no = _page_no[i]; 01095 if (non_free_pages[i]) 01096 { 01097 STXXL_VERBOSE1("vector: flushing page " << i << " address: " << (int64(page_no) * 01098 int64(block_type::size) * int64(page_size))); 01099 if (_page_status[page_no] & dirty) 01100 write_page(page_no, i); 01101 01102 01103 _last_page[page_no] = on_disk; 01104 _page_status[page_no] = 0; 01105 } 01106 } 01107 } 01108 ~vector() 01109 { 01110 try 01111 { 01112 flush(); 01113 } 01114 catch (...) 01115 { 01116 STXXL_VERBOSE("An exception in the ~vector()"); 01117 } 01118 01119 bm->delete_blocks(_bids.begin(), _bids.end()); 01120 01121 if (_from) // file must be truncated 01122 { 01123 STXXL_VERBOSE1("~vector(): Changing size of file " << ((void *)_from) << " to " 01124 << file_length()); 01125 STXXL_VERBOSE1("~vector(): size of the vector is " << size()); 01126 _from->set_size(file_length()); 01127 } 01128 } 01129 01130 private: 01131 bids_container_iterator bid(const size_type & offset) 01132 { 01133 return (_bids.begin() + 01134 static_cast<typename bids_container_type::size_type> 01135 (offset / block_type::size)); 01136 } 01137 bids_container_iterator bid(const double_blocked_index<PgSz_, block_type::size> & offset) 01138 { 01139 return (_bids.begin() + 01140 static_cast<typename bids_container_type::size_type> 01141 (offset.get_block2() * PgSz_ + offset.get_block1())); 01142 } 01143 const_bids_container_iterator bid(const size_type & offset) const 01144 { 01145 return (_bids.begin() + 01146 static_cast<typename bids_container_type::size_type> 01147 (offset / block_type::size)); 01148 } 01149 const_bids_container_iterator bid(const double_blocked_index<PgSz_, block_type::size> & offset) const 01150 { 01151 return (_bids.begin() + 01152 static_cast<typename bids_container_type::size_type> 01153 (offset.get_block2() * PgSz_ + offset.get_block1())); 01154 } 01155 void read_page(int_type page_no, int_type cache_page) const 01156 { 01157 STXXL_VERBOSE1("vector " << this << ": reading page_no=" << page_no << " cache_page=" << cache_page); 01158 request_ptr * reqs = new request_ptr[page_size]; 01159 int_type block_no = page_no * page_size; 01160 int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size())); 01161 int_type i = cache_page * page_size, j = 0; 01162 for ( ; block_no < last_block; ++block_no, ++i, ++j) 01163 { 01164 reqs[j] = _cache[i].read(_bids[block_no]); 01165 } 01166 assert(last_block - page_no * page_size > 0); 01167 wait_all(reqs, last_block - page_no * page_size); 01168 delete[] reqs; 01169 } 01170 void write_page(int_type page_no, int_type cache_page) const 01171 { 01172 STXXL_VERBOSE1("vector " << this << ": writing page_no=" << page_no << " cache_page=" << cache_page); 01173 request_ptr * reqs = new request_ptr[page_size]; 01174 int_type block_no = page_no * page_size; 01175 int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size())); 01176 int_type i = cache_page * page_size, j = 0; 01177 for ( ; block_no < last_block; ++block_no, ++i, ++j) 01178 { 01179 reqs[j] = _cache[i].write(_bids[block_no]); 01180 } 01181 assert(last_block - page_no * page_size > 0); 01182 wait_all(reqs, last_block - page_no * page_size); 01183 delete[] reqs; 01184 } 01185 reference element(size_type offset) 01186 { 01187 return element(double_blocked_index<PgSz_, block_type::size>(offset)); 01188 } 01189 01190 reference element(const double_blocked_index<PgSz_, block_type::size> & offset) 01191 { 01192 int_type page_no = offset.get_block2(); 01193 assert(page_no < int_type(_last_page.size())); // fails if offset is too large, out of bound access 01194 int_type last_page = _last_page[page_no]; 01195 if (last_page < 0) // == on_disk 01196 { 01197 if (_free_pages.empty()) // has to kick 01198 { 01199 int_type kicked_page = pager.kick(); 01200 pager.hit(kicked_page); 01201 int_type old_page_no = _page_no[kicked_page]; 01202 _last_page[page_no] = kicked_page; 01203 _last_page[old_page_no] = on_disk; 01204 _page_no[kicked_page] = page_no; 01205 01206 // what to do with the old page ? 01207 if (_page_status[old_page_no] & dirty) 01208 { 01209 // has to store changes 01210 write_page(old_page_no, kicked_page); 01211 } 01212 01213 if (_page_status[page_no] != uninitialized) 01214 { 01215 read_page(page_no, kicked_page); 01216 } 01217 01218 _page_status[page_no] = dirty; 01219 01220 return _cache[kicked_page * page_size + offset.get_block1()][offset.get_offset()]; 01221 } 01222 else 01223 { 01224 int_type free_page = _free_pages.front(); 01225 _free_pages.pop(); 01226 pager.hit(free_page); 01227 _last_page[page_no] = free_page; 01228 _page_no[free_page] = page_no; 01229 01230 if (_page_status[page_no] != uninitialized) 01231 { 01232 read_page(page_no, free_page); 01233 } 01234 01235 _page_status[page_no] = dirty; 01236 01237 return _cache[free_page * page_size + offset.get_block1()][offset.get_offset()]; 01238 } 01239 } 01240 else 01241 { 01242 _page_status[page_no] = dirty; 01243 pager.hit(last_page); 01244 return _cache[last_page * page_size + offset.get_block1()][offset.get_offset()]; 01245 } 01246 } 01247 void touch(size_type offset) const 01248 { 01249 // fails if offset is too large, out of bound access 01250 assert(offset / (block_type::size * page_size)< _page_status.size()); 01251 _page_status[offset / (block_type::size * page_size)] = 0; 01252 } 01253 01254 void touch(const double_blocked_index<PgSz_, block_type::size> & offset) const 01255 { 01256 // fails if offset is too large, out of bound access 01257 assert(offset.get_block2() < _page_status.size()); 01258 _page_status[offset.get_block2()] = 0; 01259 } 01260 01261 const_reference const_element(size_type offset) const 01262 { 01263 return const_element(double_blocked_index<PgSz_, block_type::size>(offset)); 01264 } 01265 01266 const_reference const_element(const double_blocked_index<PgSz_, block_type::size> & offset) const 01267 { 01268 int_type page_no = offset.get_block2(); 01269 assert(page_no < int_type(_last_page.size())); // fails if offset is too large, out of bound access 01270 int_type last_page = _last_page[page_no]; 01271 if (last_page < 0) // == on_disk 01272 { 01273 if (_free_pages.empty()) // has to kick 01274 { 01275 int_type kicked_page = pager.kick(); 01276 pager.hit(kicked_page); 01277 int_type old_page_no = _page_no[kicked_page]; 01278 _last_page[page_no] = kicked_page; 01279 _last_page[old_page_no] = on_disk; 01280 _page_no[kicked_page] = page_no; 01281 01282 // what to do with the old page ? 01283 if (_page_status[old_page_no] & dirty) 01284 { 01285 // has to store changes 01286 write_page(old_page_no, kicked_page); 01287 } 01288 01289 if (_page_status[page_no] != uninitialized) 01290 { 01291 read_page(page_no, kicked_page); 01292 } 01293 01294 _page_status[page_no] = 0; 01295 01296 return _cache[kicked_page * page_size + offset.get_block1()][offset.get_offset()]; 01297 } 01298 else 01299 { 01300 int_type free_page = _free_pages.front(); 01301 _free_pages.pop(); 01302 pager.hit(free_page); 01303 _last_page[page_no] = free_page; 01304 _page_no[free_page] = page_no; 01305 01306 if (_page_status[page_no] != uninitialized) 01307 { 01308 read_page(page_no, free_page); 01309 } 01310 01311 _page_status[page_no] = 0; 01312 01313 return _cache[free_page * page_size + offset.get_block1()][offset.get_offset()]; 01314 } 01315 } 01316 else 01317 { 01318 pager.hit(last_page); 01319 return _cache[last_page * page_size + offset.get_block1()][offset.get_offset()]; 01320 } 01321 } 01322 }; 01323 01324 template < 01325 typename Tp_, 01326 unsigned PgSz_, 01327 typename PgTp_, 01328 unsigned BlkSize_, 01329 typename AllocStr_, 01330 typename SzTp_> 01331 inline bool operator == (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01332 AllocStr_, SzTp_> & a, 01333 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01334 AllocStr_, SzTp_> & b) 01335 { 01336 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); 01337 } 01338 01339 template < 01340 typename Tp_, 01341 unsigned PgSz_, 01342 typename PgTp_, 01343 unsigned BlkSize_, 01344 typename AllocStr_, 01345 typename SzTp_> 01346 inline bool operator != (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01347 AllocStr_, SzTp_> & a, 01348 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01349 AllocStr_, SzTp_> & b) 01350 { 01351 return !(a == b); 01352 } 01353 01354 template < 01355 typename Tp_, 01356 unsigned PgSz_, 01357 typename PgTp_, 01358 unsigned BlkSize_, 01359 typename AllocStr_, 01360 typename SzTp_> 01361 inline bool operator < (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01362 AllocStr_, SzTp_> & a, 01363 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01364 AllocStr_, SzTp_> & b) 01365 { 01366 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); 01367 } 01368 01369 template < 01370 typename Tp_, 01371 unsigned PgSz_, 01372 typename PgTp_, 01373 unsigned BlkSize_, 01374 typename AllocStr_, 01375 typename SzTp_> 01376 inline bool operator > (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01377 AllocStr_, SzTp_> & a, 01378 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01379 AllocStr_, SzTp_> & b) 01380 { 01381 return b < a; 01382 } 01383 01384 template < 01385 typename Tp_, 01386 unsigned PgSz_, 01387 typename PgTp_, 01388 unsigned BlkSize_, 01389 typename AllocStr_, 01390 typename SzTp_> 01391 inline bool operator <= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01392 AllocStr_, SzTp_> & a, 01393 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01394 AllocStr_, SzTp_> & b) 01395 { 01396 return !(b < a); 01397 } 01398 01399 template < 01400 typename Tp_, 01401 unsigned PgSz_, 01402 typename PgTp_, 01403 unsigned BlkSize_, 01404 typename AllocStr_, 01405 typename SzTp_> 01406 inline bool operator >= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01407 AllocStr_, SzTp_> & a, 01408 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, 01409 AllocStr_, SzTp_> & b) 01410 { 01411 return !(a < b); 01412 } 01413 01415 01417 01418 // specialization for stxxl::vector, to use only const_iterators 01419 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 01420 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 01421 bool is_sorted( 01422 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first, 01423 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last) 01424 { 01425 return is_sorted_helper( 01426 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first), 01427 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last)); 01428 } 01429 01430 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 01431 unsigned BlkSize_, typename PgTp_, unsigned PgSz_, typename _StrictWeakOrdering> 01432 bool is_sorted( 01433 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first, 01434 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last, 01435 _StrictWeakOrdering __comp) 01436 { 01437 return is_sorted_helper( 01438 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first), 01439 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last), 01440 __comp); 01441 } 01442 01444 01447 01449 01472 template < 01473 typename Tp_, 01474 unsigned PgSz_ = 4, 01475 unsigned Pages_ = 8, 01476 unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_), 01477 typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY, 01478 pager_type Pager_ = lru 01479 > 01480 struct VECTOR_GENERATOR 01481 { 01482 typedef typename IF<Pager_ == lru, 01483 lru_pager<Pages_>, random_pager<Pages_> >::result PagerType; 01484 01485 typedef vector<Tp_, PgSz_, PagerType, BlkSize_, AllocStr_> result; 01486 }; 01487 01488 01490 01491 __STXXL_END_NAMESPACE 01492 01493 01494 namespace std 01495 { 01496 template < 01497 typename Tp_, 01498 unsigned PgSz_, 01499 typename PgTp_, 01500 unsigned BlkSize_, 01501 typename AllocStr_, 01502 typename SzTp_> 01503 void swap(stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & a, 01504 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & b) 01505 { 01506 a.swap(b); 01507 } 01508 } 01509 01510 #endif // !STXXL_VECTOR_HEADER