00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
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( block1 < modulo2);
00058 assert( 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( block1 < modulo2);
00081 assert( offset < modulo1);
00082 }
00083
00084 double_blocked_index & operator = (unsigned_type pos)
00085 {
00086 set(pos);
00087 return *this;
00088 }
00089
00090
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( block1 < modulo2);
00108 assert( offset < modulo1);
00109
00110 return *this;
00111 }
00112
00113
00114 double_blocked_index operator ++ (int)
00115 {
00116 double_blocked_index former(*this);
00117 operator ++ ();
00118 return former;
00119 }
00120
00121
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( block1 < modulo2);
00139 assert( offset < modulo1);
00140
00141 return *this;
00142 }
00143
00144
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
00483
00484
00485
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;
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;
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
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
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);
00896
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
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)
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()));
01194 int_type last_page = _last_page[page_no];
01195 if (last_page < 0)
01196 {
01197 if (_free_pages.empty())
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
01207 if (_page_status[old_page_no] & dirty)
01208 {
01209
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
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
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()));
01270 int_type last_page = _last_page[page_no];
01271 if (last_page < 0)
01272 {
01273 if (_free_pages.empty())
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
01283 if (_page_status[old_page_no] & dirty)
01284 {
01285
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
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