Stxxl  1.2.1
vector.h
1 /***************************************************************************
2  * include/stxxl/bits/containers/vector.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2007 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7  * Copyright (C) 2007, 2008 Johannes Singler <singler@ira.uka.de>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_VECTOR_HEADER
15 #define STXXL_VECTOR_HEADER
16 
17 #include <vector>
18 #include <algorithm>
19 
20 #include <stxxl/bits/mng/mng.h>
21 #include <stxxl/bits/common/tmeta.h>
22 #include <stxxl/bits/containers/pager.h>
23 #include <stxxl/bits/common/is_sorted.h>
24 
25 
26 __STXXL_BEGIN_NAMESPACE
27 
31 
32 
36 
37 template <unsigned_type modulo2, unsigned_type modulo1>
38 class double_blocked_index
39 {
40  static const unsigned_type modulo12 = modulo1 * modulo2;
41 
42  unsigned_type pos;
43  unsigned_type block1, block2;
44  unsigned_type offset;
45 
47 
48  void set(unsigned_type pos)
49  {
50  this->pos = pos;
51  block2 = pos / modulo12;
52  pos -= block2 * modulo12;
53  block1 = pos / modulo1;
54  offset = (pos - block1 * modulo1);
55 
56  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
57  assert(/* 0 <= block1 && */ block1 < modulo2);
58  assert(/* 0 <= offset && */ offset < modulo1);
59  }
60 
61 public:
62  double_blocked_index()
63  {
64  set(0);
65  }
66 
67  double_blocked_index(unsigned_type pos)
68  {
69  set(pos);
70  }
71 
72  double_blocked_index(unsigned_type block2, unsigned_type block1, unsigned_type)
73  {
74  this->block2 = block2;
75  this->block1 = block1;
76  this->offset = offset;
77  pos = block2 * modulo12 + block1 * modulo1 + offset;
78 
79  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
80  assert(/* 0 <= block1 && */ block1 < modulo2);
81  assert(/* 0 <= offset && */ offset < modulo1);
82  }
83 
84  double_blocked_index & operator = (unsigned_type pos)
85  {
86  set(pos);
87  return *this;
88  }
89 
90  //pre-increment operator
91  double_blocked_index & operator ++ ()
92  {
93  ++pos;
94  ++offset;
95  if (offset == modulo1)
96  {
97  offset = 0;
98  ++block1;
99  if (block1 == modulo2)
100  {
101  block1 = 0;
102  ++block2;
103  }
104  }
105 
106  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
107  assert(/* 0 <= block1 && */ block1 < modulo2);
108  assert(/* 0 <= offset && */ offset < modulo1);
109 
110  return *this;
111  }
112 
113  //post-increment operator
114  double_blocked_index operator ++ (int)
115  {
116  double_blocked_index former(*this);
117  operator ++ ();
118  return former;
119  }
120 
121  //pre-increment operator
122  double_blocked_index & operator -- ()
123  {
124  --pos;
125  if (offset == 0)
126  {
127  offset = modulo1;
128  if (block1 == 0)
129  {
130  block1 = modulo2;
131  --block2;
132  }
133  --block1;
134  }
135  --offset;
136 
137  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
138  assert(/*0 <= block1 &&*/ block1 < modulo2);
139  assert(/*0 <= offset &&*/ offset < modulo1);
140 
141  return *this;
142  }
143 
144  //post-increment operator
145  double_blocked_index operator -- (int)
146  {
147  double_blocked_index former(*this);
148  operator -- ();
149  return former;
150  }
151 
152  double_blocked_index operator + (unsigned_type addend) const
153  {
154  return double_blocked_index(pos + addend);
155  }
156 
157  double_blocked_index & operator += (unsigned_type addend)
158  {
159  set(pos + addend);
160  return *this;
161  }
162 
163  double_blocked_index operator - (unsigned_type addend) const
164  {
165  return double_blocked_index(pos - addend);
166  }
167 
168  unsigned_type operator - (const double_blocked_index & dbi2) const
169  {
170  return pos - dbi2.pos;
171  }
172 
173  double_blocked_index & operator -= (unsigned_type subtrahend)
174  {
175  set(pos - subtrahend);
176  return *this;
177  }
178 
179  bool operator == (const double_blocked_index & dbi2) const
180  {
181  return pos == dbi2.pos;
182  }
183 
184  bool operator != (const double_blocked_index & dbi2) const
185  {
186  return pos != dbi2.pos;
187  }
188 
189  bool operator < (const double_blocked_index & dbi2) const
190  {
191  return pos < dbi2.pos;
192  }
193 
194  bool operator <= (const double_blocked_index & dbi2) const
195  {
196  return pos <= dbi2.pos;
197  }
198 
199  bool operator > (const double_blocked_index & dbi2) const
200  {
201  return pos > dbi2.pos;
202  }
203 
204  bool operator >= (const double_blocked_index & dbi2) const
205  {
206  return pos >= dbi2.pos;
207  }
208 
209  double_blocked_index & operator >>= (unsigned_type shift)
210  {
211  set(pos >> shift);
212  return *this;
213  }
214 
215  unsigned_type get_pos() const
216  {
217  return pos;
218  }
219 
220  const unsigned_type & get_block2() const
221  {
222  return block2;
223  }
224 
225  const unsigned_type & get_block1() const
226  {
227  return block1;
228  }
229 
230  const unsigned_type & get_offset() const
231  {
232  return offset;
233  }
234 };
235 
236 
237 template <unsigned BlkSize_>
238 class bid_vector : public std::vector<BID<BlkSize_> >
239 {
240 public:
241  enum
242  { block_size = BlkSize_ };
243  typedef bid_vector<block_size> _Self;
244  typedef std::vector<BID<BlkSize_> > _Derived;
245  typedef unsigned size_type;
246 
247  bid_vector(size_type _sz) : _Derived(_sz)
248  { }
249 };
250 
251 
252 template <
253  typename Tp_,
254  unsigned PgSz_,
255  typename PgTp_,
256  unsigned BlkSize_,
257  typename AllocStr_,
258  typename SzTp_>
259 class vector;
260 
261 
262 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
263  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
265 
266 
268 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
269  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
271 {
272  typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_,
273  BlkSize_, PgTp_, PgSz_> _Self;
274  typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_,
275  BlkSize_, PgTp_, PgSz_> _CIterator;
276 
277  friend class const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>;
278 
279 public:
280  typedef _CIterator const_iterator;
281  typedef _Self iterator;
282 
283  typedef SzTp_ size_type;
284  typedef DiffTp_ difference_type;
285  typedef unsigned block_offset_type;
287  friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>;
288  typedef bid_vector<BlkSize_> bids_container_type;
289  typedef typename bids_container_type::iterator bids_container_iterator;
291  typedef BID<BlkSize_> bid_type;
292 
293  typedef std::random_access_iterator_tag iterator_category;
294  typedef typename vector_type::value_type value_type;
295  typedef typename vector_type::reference reference;
296  typedef typename vector_type::const_reference const_reference;
297  typedef typename vector_type::pointer pointer;
298  typedef typename vector_type::const_pointer const_pointer;
299 
300  enum { block_size = BlkSize_ };
301 
302 protected:
303  double_blocked_index<PgSz_, block_type::size> offset;
304  vector_type * p_vector;
305 
306 private:
307  vector_iterator(vector_type * v, size_type o) : offset(o),
308  p_vector(v)
309  { }
310 
311 public:
312  vector_iterator() : offset(0), p_vector(NULL) { }
313  vector_iterator(const _Self & a) :
314  offset(a.offset),
315  p_vector(a.p_vector) { }
316 
317  block_offset_type block_offset() const
318  {
319  return static_cast<block_offset_type>(offset.get_offset());
320  }
321  bids_container_iterator bid() const
322  {
323  return p_vector->bid(offset);
324  }
325 
326  difference_type operator - (const _Self & a) const
327  {
328  return offset - a.offset;
329  }
330 
331  difference_type operator - (const const_iterator & a) const
332  {
333  return offset - a.offset;
334  }
335 
336  _Self operator - (size_type op) const
337  {
338  return _Self(p_vector, offset.get_pos() - op);
339  }
340 
341  _Self operator + (size_type op) const
342  {
343  return _Self(p_vector, offset.get_pos() + op);
344  }
345 
346  _Self & operator -= (size_type op)
347  {
348  offset -= op;
349  return *this;
350  }
351 
352  _Self & operator += (size_type op)
353  {
354  offset += op;
355  return *this;
356  }
357 
358  reference operator * ()
359  {
360  return p_vector->element(offset);
361  }
362 
363  pointer operator -> ()
364  {
365  return &(p_vector->element(offset));
366  }
367 
368  const_reference operator * () const
369  {
370  return p_vector->const_element(offset);
371  }
372 
373  const_pointer operator -> () const
374  {
375  return &(p_vector->const_element(offset));
376  }
377 
378  reference operator [] (size_type op)
379  {
380  return p_vector->element(offset.get_pos() + op);
381  }
382 
383  const_reference operator [] (size_type op) const
384  {
385  return p_vector->const_element(offset.get_pos() + op);
386  }
387 
388  void touch()
389  {
390  p_vector->touch(offset);
391  }
392 
393  _Self & operator ++ ()
394  {
395  offset++;
396  return *this;
397  }
398  _Self operator ++ (int)
399  {
400  _Self __tmp = *this;
401  offset++;
402  return __tmp;
403  }
404  _Self & operator -- ()
405  {
406  offset--;
407  return *this;
408  }
409  _Self operator -- (int)
410  {
411  _Self __tmp = *this;
412  offset--;
413  return __tmp;
414  }
415  bool operator == (const _Self & a) const
416  {
417  assert(p_vector == a.p_vector);
418  return offset == a.offset;
419  }
420  bool operator != (const _Self & a) const
421  {
422  assert(p_vector == a.p_vector);
423  return offset != a.offset;
424  }
425  bool operator < (const _Self & a) const
426  {
427  assert(p_vector == a.p_vector);
428  return offset < a.offset;
429  }
430  bool operator <= (const _Self & a) const
431  {
432  assert(p_vector == a.p_vector);
433  return offset <= a.offset;
434  }
435  bool operator > (const _Self & a) const
436  {
437  assert(p_vector == a.p_vector);
438  return a > *this;
439  }
440  bool operator >= (const _Self & a) const
441  {
442  assert(p_vector == a.p_vector);
443  return a >= *this;
444  }
445 
446  bool operator == (const const_iterator & a) const
447  {
448  assert(p_vector == a.p_vector);
449  return offset == a.offset;
450  }
451  bool operator != (const const_iterator & a) const
452  {
453  assert(p_vector == a.p_vector);
454  return offset != a.offset;
455  }
456  bool operator < (const const_iterator & a) const
457  {
458  assert(p_vector == a.p_vector);
459  return offset < a.offset;
460  }
461  bool operator <= (const const_iterator & a) const
462  {
463  assert(p_vector == a.p_vector);
464  return offset <= a.offset;
465  }
466  bool operator > (const const_iterator & a) const
467  {
468  assert(p_vector == a.p_vector);
469  return a > *this;
470  }
471  bool operator >= (const const_iterator & a) const
472  {
473  assert(p_vector == a.p_vector);
474  return a >= *this;
475  }
476 
477  void flush()
478  {
479  p_vector->flush();
480  }
481  /*
482  std::ostream & operator<< (std::ostream & o) const
483  {
484  o << "vectorpointer: " << ((void*)p_vector) <<" offset: "<<offset;
485  return o;
486  }*/
487 };
488 
490 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
491  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
493 {
494  typedef const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_,
495  BlkSize_, PgTp_, PgSz_> _Self;
496  typedef vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_,
497  BlkSize_, PgTp_, PgSz_> _NonConstIterator;
498 
499  friend class vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>;
500 
501 public:
502  typedef _Self const_iterator;
503  typedef _NonConstIterator iterator;
504 
505  typedef SzTp_ size_type;
506  typedef DiffTp_ difference_type;
507  typedef unsigned block_offset_type;
509  friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>;
510  typedef bid_vector<BlkSize_> bids_container_type;
511  typedef typename bids_container_type::iterator bids_container_iterator;
513  typedef BID<BlkSize_> bid_type;
514 
515  typedef std::random_access_iterator_tag iterator_category;
516  typedef typename vector_type::value_type value_type;
517  typedef typename vector_type::reference reference;
518  typedef typename vector_type::const_reference const_reference;
519  typedef typename vector_type::pointer pointer;
520  typedef typename vector_type::const_pointer const_pointer;
521 
522  enum { block_size = BlkSize_ };
523 
524 protected:
525  double_blocked_index<PgSz_, block_type::size> offset;
526  const vector_type * p_vector;
527 
528 private:
529  const_vector_iterator(const vector_type * v, size_type o) : offset(o),
530  p_vector(v)
531  { }
532 
533 public:
534  const_vector_iterator() : offset(0), p_vector(NULL)
535  { }
536  const_vector_iterator(const _Self & a) :
537  offset(a.offset),
538  p_vector(a.p_vector)
539  { }
540 
541  const_vector_iterator(const iterator & a) :
542  offset(a.offset),
543  p_vector(a.p_vector)
544  { }
545 
546  block_offset_type block_offset() const
547  {
548  return static_cast<block_offset_type>(offset.get_offset());
549  }
550  bids_container_iterator bid() const
551  {
552  return ((vector_type *)p_vector)->bid(offset);
553  }
554 
555  difference_type operator - (const _Self & a) const
556  {
557  return offset - a.offset;
558  }
559 
560  difference_type operator - (const iterator & a) const
561  {
562  return offset - a.offset;
563  }
564 
565  _Self operator - (size_type op) const
566  {
567  return _Self(p_vector, offset.get_pos() - op);
568  }
569 
570  _Self operator + (size_type op) const
571  {
572  return _Self(p_vector, offset.get_pos() + op);
573  }
574 
575  _Self & operator -= (size_type op)
576  {
577  offset -= op;
578  return *this;
579  }
580 
581  _Self & operator += (size_type op)
582  {
583  offset += op;
584  return *this;
585  }
586 
587  const_reference operator * () const
588  {
589  return p_vector->const_element(offset);
590  }
591 
592  const_pointer operator -> () const
593  {
594  return &(p_vector->const_element(offset));
595  }
596 
597  const_reference operator [] (size_type op) const
598  {
599  return p_vector->const_element(offset.get_pos() + op);
600  }
601 
602  void touch()
603  {
604  p_vector->touch(offset);
605  }
606 
607  _Self & operator ++ ()
608  {
609  offset++;
610  return *this;
611  }
612  _Self operator ++ (int)
613  {
614  _Self tmp_ = *this;
615  offset++;
616  return tmp_;
617  }
618  _Self & operator -- ()
619  {
620  offset--;
621  return *this;
622  }
623  _Self operator -- (int)
624  {
625  _Self __tmp = *this;
626  offset--;
627  return __tmp;
628  }
629  bool operator == (const _Self & a) const
630  {
631  assert(p_vector == a.p_vector);
632  return offset == a.offset; // or (offset + stxxl::int64(p_vector))
633  }
634  bool operator != (const _Self & a) const
635  {
636  assert(p_vector == a.p_vector);
637  return offset != a.offset;
638  }
639  bool operator < (const _Self & a) const
640  {
641  assert(p_vector == a.p_vector);
642  return offset < a.offset;
643  }
644  bool operator <= (const _Self & a) const
645  {
646  assert(p_vector == a.p_vector);
647  return offset <= a.offset;
648  }
649  bool operator > (const _Self & a) const
650  {
651  assert(p_vector == a.p_vector);
652  return offset > a.offset;
653  }
654  bool operator >= (const _Self & a) const
655  {
656  assert(p_vector == a.p_vector);
657  return offset >= a.offset;
658  }
659 
660  bool operator == (const iterator & a) const
661  {
662  assert(p_vector == a.p_vector);
663  return offset == a.offset; // or (offset + stxxl::int64(p_vector))
664  }
665  bool operator != (const iterator & a) const
666  {
667  assert(p_vector == a.p_vector);
668  return offset != a.offset;
669  }
670  bool operator < (const iterator & a) const
671  {
672  assert(p_vector == a.p_vector);
673  return offset < a.offset;
674  }
675  bool operator <= (const iterator & a) const
676  {
677  assert(p_vector == a.p_vector);
678  return offset <= a.offset;
679  }
680  bool operator > (const iterator & a) const
681  {
682  assert(p_vector == a.p_vector);
683  return offset > a.offset;
684  }
685  bool operator >= (const iterator & a) const
686  {
687  assert(p_vector == a.p_vector);
688  return offset >= a.offset;
689  }
690 
691  void flush()
692  {
693  p_vector->flush();
694  }
695 
696  std::ostream & operator << (std::ostream & o) const
697  {
698  o << "vectorpointer: " << ((void *)p_vector) << " offset: " << offset;
699  return o;
700  }
701 };
702 
703 
705 
718 template <
719  typename Tp_,
720  unsigned PgSz_ = 4,
721  typename PgTp_ = lru_pager<8>,
722  unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_),
723  typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY,
724  typename SzTp_ = stxxl::uint64 // will be deprecated soon
725  >
726 class vector
727 {
728 public:
729  typedef Tp_ value_type;
730  typedef value_type & reference;
731  typedef const value_type & const_reference;
732  typedef value_type * pointer;
733  typedef SzTp_ size_type;
734  typedef stxxl::int64 difference_type;
735  typedef const value_type * const_pointer;
736 
737  typedef PgTp_ pager_type;
738  typedef AllocStr_ alloc_strategy;
739 
740  enum {
741  block_size = BlkSize_,
742  page_size = PgSz_,
743  n_pages = pager_type::n_pages,
744  on_disk = -1
745  };
746 
747  typedef vector_iterator<value_type, alloc_strategy, size_type,
748  difference_type, block_size, pager_type, page_size> iterator;
749  friend class vector_iterator<value_type, alloc_strategy, size_type, difference_type, block_size, pager_type, page_size>;
750  typedef const_vector_iterator<value_type, alloc_strategy,
751  size_type, difference_type, block_size, pager_type, page_size> const_iterator;
752  friend class const_vector_iterator<value_type, alloc_strategy, size_type, difference_type, block_size, pager_type, page_size>;
753 
754  typedef bid_vector<block_size> bids_container_type;
755  typedef typename bids_container_type::
756  iterator bids_container_iterator;
757  typedef typename bids_container_type::
758  const_iterator const_bids_container_iterator;
759 
761 
762 private:
763  alloc_strategy _alloc_strategy;
764  size_type _size;
765  bids_container_type _bids;
766  //bids_container_iterator _bids_finish;
767  mutable pager_type pager;
768 
769  enum { uninitialized = 1, dirty = 2 };
770  mutable std::vector<unsigned char> _page_status;
771  mutable std::vector<int_type> _last_page;
772  mutable simple_vector<int_type> _page_no;
773  mutable std::queue<int_type> _free_pages;
774  mutable simple_vector<block_type> _cache;
775  file * _from;
776  block_manager * bm;
777  config * cfg;
778 
779  size_type size_from_file_length(stxxl::uint64 file_length)
780  {
781  stxxl::uint64 blocks_fit = file_length / stxxl::uint64(block_type::raw_size);
782  size_type cur_size = blocks_fit * stxxl::uint64(block_type::size);
783  stxxl::uint64 rest = file_length - blocks_fit * stxxl::uint64(block_type::raw_size);
784  return (cur_size + rest / stxxl::uint64(sizeof(value_type)));
785  }
786  stxxl::uint64 file_length()
787  {
788  size_type cur_size = size();
789  if (cur_size % size_type(block_type::size))
790  {
791  stxxl::uint64 full_blocks_length = size_type(_bids.size() - 1) * size_type(block_type::raw_size);
792  size_type rest = cur_size - size_type(_bids.size() - 1) * size_type(block_type::size);
793  return full_blocks_length + rest * size_type(sizeof(value_type));
794  }
795  return size_type(_bids.size()) * size_type(block_type::raw_size);
796  }
797 
798 public:
799  vector(size_type n = 0) :
800  _size(n),
801  _bids(div_and_round_up(n, block_type::size)),
802  _page_status(div_and_round_up(_bids.size(), page_size)),
803  _last_page(div_and_round_up(_bids.size(), page_size)),
804  _page_no(n_pages),
805  _cache(n_pages * page_size),
806  _from(NULL)
807  {
808  bm = block_manager::get_instance();
809  cfg = config::get_instance();
810 
811  int_type all_pages = div_and_round_up(_bids.size(), page_size);
812  int_type i = 0;
813  for ( ; i < all_pages; ++i)
814  {
815  _page_status[i] = uninitialized;
816  _last_page[i] = on_disk;
817  }
818 
819  for (i = 0; i < n_pages; ++i)
820  _free_pages.push(i);
821 
822 
823  bm->new_blocks(_alloc_strategy, _bids.begin(),
824  _bids.end());
825  }
826 
827  void swap(vector & obj)
828  {
829  std::swap(_alloc_strategy, obj._alloc_strategy);
830  std::swap(_size, obj._size);
831  std::swap(_bids, obj._bids);
832  std::swap(pager, obj.pager);
833  std::swap(_page_status, obj._page_status);
834  std::swap(_last_page, obj._last_page);
835  std::swap(_page_no, obj._page_no);
836  std::swap(_free_pages, obj._free_pages);
837  std::swap(_cache, obj._cache);
838  std::swap(_from, obj._from);
839  }
840  size_type capacity() const
841  {
842  return size_type(_bids.size()) * block_type::size;
843  }
844  void reserve(size_type n)
845  {
846  if (n <= capacity())
847  return;
848 
849 
850  unsigned_type old_bids_size = _bids.size();
851  unsigned_type new_bids_size = div_and_round_up(n, block_type::size);
852  unsigned_type new_pages = div_and_round_up(new_bids_size, page_size);
853  _page_status.resize(new_pages, uninitialized);
854  _last_page.resize(new_pages, on_disk);
855 
856  _bids.resize(new_bids_size);
857  if (_from == NULL)
858  bm->new_blocks(offset_allocator<alloc_strategy>(old_bids_size, _alloc_strategy),
859  _bids.begin() + old_bids_size, _bids.end());
860 
861  else
862  {
863  size_type offset = size_type(old_bids_size) * size_type(block_type::raw_size);
864  bids_container_iterator it = _bids.begin() + old_bids_size;
865  for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size))
866  {
867  (*it).storage = _from;
868  (*it).offset = offset;
869  }
870  STXXL_VERBOSE1("vector::reserve(): Changing size of file " << ((void *)_from) << " to "
871  << offset);
872  _from->set_size(offset);
873  }
874  }
875  void resize(size_type n)
876  {
877 #ifndef STXXL_FREE_EXTMEMORY_ON_VECTOR_RESIZE
878  reserve(n);
879 #else
880  unsigned_type old_bids_size = _bids.size();
881  unsigned_type new_bids_size = div_and_round_up(n, block_type::size);
882 
883 
884  if (new_bids_size > old_bids_size)
885  {
886  reserve(n);
887  }
888  else if (new_bids_size < old_bids_size)
889  {
890  bm->delete_blocks(_bids.begin() + new_bids_size, _bids.end());
891  _bids.resize(new_bids_size);
892 
893  unsigned_type first_page_to_evict = div_and_round_up(new_bids_size, page_size);
894  std::fill(_page_status.begin() + first_page_to_evict,
895  _page_status.end(), 0); // clear dirty flag, so this pages
896  // will be never written
897  }
898 #endif
899 
900  _size = n;
901  }
902  void clear()
903  {
904  _size = 0;
905  bm->delete_blocks(_bids.begin(), _bids.end());
906 
907  _bids.clear();
908  _page_status.clear();
909  _last_page.clear();
910  while (!_free_pages.empty())
911  _free_pages.pop();
912 
913 
914  for (int_type i = 0; i < n_pages; ++i)
915  _free_pages.push(i);
916  }
917  void push_back(const_reference obj)
918  {
919  size_type old_size = _size;
920  resize(old_size + 1);
921  element(old_size) = obj;
922  }
923  void pop_back()
924  {
925  resize(_size - 1);
926  }
927  reference back()
928  {
929  return element(_size - 1);
930  }
931  reference front()
932  {
933  return element(0);
934  }
935  const_reference back() const
936  {
937  return const_element(_size - 1);
938  }
939  const_reference front() const
940  {
941  return const_element(0);
942  }
949  vector(file * from) :
950  _size(size_from_file_length(from->size())),
951  _bids(div_and_round_up(_size, size_type(block_type::size))),
952  _page_status(div_and_round_up(_bids.size(), page_size)),
953  _last_page(div_and_round_up(_bids.size(), page_size)),
954  _page_no(n_pages),
955  _cache(n_pages * page_size),
956  _from(from)
957  {
958  // initialize from file
959  assert(from->get_id() == -1);
960 
961  if (block_type::has_filler)
962  {
963  std::ostringstream str_;
964  str_ << "The block size for the vector, mapped to a file must me a multiple of the element size (" <<
965  sizeof(value_type) << ") and the page size (4096).";
966  throw std::runtime_error(str_.str());
967  }
968 
969  bm = block_manager::get_instance();
970  cfg = config::get_instance();
971 
972  int_type all_pages = div_and_round_up(_bids.size(), page_size);
973  int_type i = 0;
974  for ( ; i < all_pages; ++i)
975  {
976  _page_status[i] = 0;
977  _last_page[i] = on_disk;
978  }
979 
980  for (i = 0; i < n_pages; ++i)
981  _free_pages.push(i);
982 
983 
984  size_type offset = 0;
985  bids_container_iterator it = _bids.begin();
986  for ( ; it != _bids.end(); ++it, offset += size_type(block_type::raw_size))
987  {
988  (*it).storage = from;
989  (*it).offset = offset;
990  }
991  from->set_size(offset);
992  }
993 
994  vector(const vector & obj) :
995  _size(obj.size()),
996  _bids(div_and_round_up(obj.size(), block_type::size)),
997  _page_status(div_and_round_up(_bids.size(), page_size)),
998  _last_page(div_and_round_up(_bids.size(), page_size)),
999  _page_no(n_pages),
1000  _cache(n_pages * page_size),
1001  _from(NULL)
1002  {
1003  bm = block_manager::get_instance();
1004  cfg = config::get_instance();
1005 
1006  int_type all_pages = div_and_round_up(_bids.size(), page_size);
1007  int_type i = 0;
1008  for ( ; i < all_pages; ++i)
1009  {
1010  _page_status[i] = uninitialized;
1011  _last_page[i] = on_disk;
1012  }
1013 
1014  for (i = 0; i < n_pages; ++i)
1015  _free_pages.push(i);
1016 
1017 
1018  bm->new_blocks(_alloc_strategy, _bids.begin(),
1019  _bids.end());
1020 
1021  const_iterator inbegin = obj.begin();
1022  const_iterator inend = obj.end();
1023  std::copy(inbegin, inend, begin());
1024  }
1025 
1026  vector & operator = (const vector & obj)
1027  {
1028  if (&obj != this)
1029  {
1030  vector tmp(obj);
1031  this->swap(tmp);
1032  }
1033  return *this;
1034  }
1035 
1036  size_type size() const
1037  {
1038  return _size;
1039  }
1040  bool empty() const
1041  {
1042  return (!_size);
1043  }
1044  iterator begin()
1045  {
1046  return iterator(this, 0);
1047  }
1048  const_iterator begin() const
1049  {
1050  return const_iterator(this, 0);
1051  }
1052  const_iterator cbegin() const
1053  {
1054  return begin();
1055  }
1056  iterator end()
1057  {
1058  return iterator(this, _size);
1059  }
1060  const_iterator end() const
1061  {
1062  return const_iterator(this, _size);
1063  }
1064  const_iterator cend() const
1065  {
1066  return end();
1067  }
1068  reference operator [] (size_type offset)
1069  {
1070  return element(offset);
1071  }
1072  const_reference operator [] (size_type offset) const
1073  {
1074  return const_element(offset);
1075  }
1076 
1077  void flush() const
1078  {
1079  simple_vector<bool> non_free_pages(n_pages);
1080  int_type i = 0;
1081  for ( ; i < n_pages; i++)
1082  non_free_pages[i] = true;
1083 
1084 
1085  while (!_free_pages.empty())
1086  {
1087  non_free_pages[_free_pages.front()] = false;
1088  _free_pages.pop();
1089  }
1090 
1091  for (i = 0; i < n_pages; i++)
1092  {
1093  _free_pages.push(i);
1094  int_type page_no = _page_no[i];
1095  if (non_free_pages[i])
1096  {
1097  STXXL_VERBOSE1("vector: flushing page " << i << " address: " << (int64(page_no) *
1098  int64(block_type::size) * int64(page_size)));
1099  if (_page_status[page_no] & dirty)
1100  write_page(page_no, i);
1101 
1102 
1103  _last_page[page_no] = on_disk;
1104  _page_status[page_no] = 0;
1105  }
1106  }
1107  }
1108  ~vector()
1109  {
1110  try
1111  {
1112  flush();
1113  }
1114  catch (...)
1115  {
1116  STXXL_VERBOSE("An exception in the ~vector()");
1117  }
1118 
1119  bm->delete_blocks(_bids.begin(), _bids.end());
1120 
1121  if (_from) // file must be truncated
1122  {
1123  STXXL_VERBOSE1("~vector(): Changing size of file " << ((void *)_from) << " to "
1124  << file_length());
1125  STXXL_VERBOSE1("~vector(): size of the vector is " << size());
1126  _from->set_size(file_length());
1127  }
1128  }
1129 
1130 private:
1131  bids_container_iterator bid(const size_type & offset)
1132  {
1133  return (_bids.begin() +
1134  static_cast<typename bids_container_type::size_type>
1135  (offset / block_type::size));
1136  }
1137  bids_container_iterator bid(const double_blocked_index<PgSz_, block_type::size> & offset)
1138  {
1139  return (_bids.begin() +
1140  static_cast<typename bids_container_type::size_type>
1141  (offset.get_block2() * PgSz_ + offset.get_block1()));
1142  }
1143  const_bids_container_iterator bid(const size_type & offset) const
1144  {
1145  return (_bids.begin() +
1146  static_cast<typename bids_container_type::size_type>
1147  (offset / block_type::size));
1148  }
1149  const_bids_container_iterator bid(const double_blocked_index<PgSz_, block_type::size> & offset) const
1150  {
1151  return (_bids.begin() +
1152  static_cast<typename bids_container_type::size_type>
1153  (offset.get_block2() * PgSz_ + offset.get_block1()));
1154  }
1155  void read_page(int_type page_no, int_type cache_page) const
1156  {
1157  STXXL_VERBOSE1("vector " << this << ": reading page_no=" << page_no << " cache_page=" << cache_page);
1158  request_ptr * reqs = new request_ptr[page_size];
1159  int_type block_no = page_no * page_size;
1160  int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size()));
1161  int_type i = cache_page * page_size, j = 0;
1162  for ( ; block_no < last_block; ++block_no, ++i, ++j)
1163  {
1164  reqs[j] = _cache[i].read(_bids[block_no]);
1165  }
1166  assert(last_block - page_no * page_size > 0);
1167  wait_all(reqs, last_block - page_no * page_size);
1168  delete[] reqs;
1169  }
1170  void write_page(int_type page_no, int_type cache_page) const
1171  {
1172  STXXL_VERBOSE1("vector " << this << ": writing page_no=" << page_no << " cache_page=" << cache_page);
1173  request_ptr * reqs = new request_ptr[page_size];
1174  int_type block_no = page_no * page_size;
1175  int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size()));
1176  int_type i = cache_page * page_size, j = 0;
1177  for ( ; block_no < last_block; ++block_no, ++i, ++j)
1178  {
1179  reqs[j] = _cache[i].write(_bids[block_no]);
1180  }
1181  assert(last_block - page_no * page_size > 0);
1182  wait_all(reqs, last_block - page_no * page_size);
1183  delete[] reqs;
1184  }
1185  reference element(size_type offset)
1186  {
1187  return element(double_blocked_index<PgSz_, block_type::size>(offset));
1188  }
1189 
1190  reference element(const double_blocked_index<PgSz_, block_type::size> & offset)
1191  {
1192  int_type page_no = offset.get_block2();
1193  assert(page_no < int_type(_last_page.size())); // fails if offset is too large, out of bound access
1194  int_type last_page = _last_page[page_no];
1195  if (last_page < 0) // == on_disk
1196  {
1197  if (_free_pages.empty()) // has to kick
1198  {
1199  int_type kicked_page = pager.kick();
1200  pager.hit(kicked_page);
1201  int_type old_page_no = _page_no[kicked_page];
1202  _last_page[page_no] = kicked_page;
1203  _last_page[old_page_no] = on_disk;
1204  _page_no[kicked_page] = page_no;
1205 
1206  // what to do with the old page ?
1207  if (_page_status[old_page_no] & dirty)
1208  {
1209  // has to store changes
1210  write_page(old_page_no, kicked_page);
1211  }
1212 
1213  if (_page_status[page_no] != uninitialized)
1214  {
1215  read_page(page_no, kicked_page);
1216  }
1217 
1218  _page_status[page_no] = dirty;
1219 
1220  return _cache[kicked_page * page_size + offset.get_block1()][offset.get_offset()];
1221  }
1222  else
1223  {
1224  int_type free_page = _free_pages.front();
1225  _free_pages.pop();
1226  pager.hit(free_page);
1227  _last_page[page_no] = free_page;
1228  _page_no[free_page] = page_no;
1229 
1230  if (_page_status[page_no] != uninitialized)
1231  {
1232  read_page(page_no, free_page);
1233  }
1234 
1235  _page_status[page_no] = dirty;
1236 
1237  return _cache[free_page * page_size + offset.get_block1()][offset.get_offset()];
1238  }
1239  }
1240  else
1241  {
1242  _page_status[page_no] = dirty;
1243  pager.hit(last_page);
1244  return _cache[last_page * page_size + offset.get_block1()][offset.get_offset()];
1245  }
1246  }
1247  void touch(size_type offset) const
1248  {
1249  // fails if offset is too large, out of bound access
1250  assert(offset / (block_type::size * page_size)< _page_status.size());
1251  _page_status[offset / (block_type::size * page_size)] = 0;
1252  }
1253 
1254  void touch(const double_blocked_index<PgSz_, block_type::size> & offset) const
1255  {
1256  // fails if offset is too large, out of bound access
1257  assert(offset.get_block2() < _page_status.size());
1258  _page_status[offset.get_block2()] = 0;
1259  }
1260 
1261  const_reference const_element(size_type offset) const
1262  {
1263  return const_element(double_blocked_index<PgSz_, block_type::size>(offset));
1264  }
1265 
1266  const_reference const_element(const double_blocked_index<PgSz_, block_type::size> & offset) const
1267  {
1268  int_type page_no = offset.get_block2();
1269  assert(page_no < int_type(_last_page.size())); // fails if offset is too large, out of bound access
1270  int_type last_page = _last_page[page_no];
1271  if (last_page < 0) // == on_disk
1272  {
1273  if (_free_pages.empty()) // has to kick
1274  {
1275  int_type kicked_page = pager.kick();
1276  pager.hit(kicked_page);
1277  int_type old_page_no = _page_no[kicked_page];
1278  _last_page[page_no] = kicked_page;
1279  _last_page[old_page_no] = on_disk;
1280  _page_no[kicked_page] = page_no;
1281 
1282  // what to do with the old page ?
1283  if (_page_status[old_page_no] & dirty)
1284  {
1285  // has to store changes
1286  write_page(old_page_no, kicked_page);
1287  }
1288 
1289  if (_page_status[page_no] != uninitialized)
1290  {
1291  read_page(page_no, kicked_page);
1292  }
1293 
1294  _page_status[page_no] = 0;
1295 
1296  return _cache[kicked_page * page_size + offset.get_block1()][offset.get_offset()];
1297  }
1298  else
1299  {
1300  int_type free_page = _free_pages.front();
1301  _free_pages.pop();
1302  pager.hit(free_page);
1303  _last_page[page_no] = free_page;
1304  _page_no[free_page] = page_no;
1305 
1306  if (_page_status[page_no] != uninitialized)
1307  {
1308  read_page(page_no, free_page);
1309  }
1310 
1311  _page_status[page_no] = 0;
1312 
1313  return _cache[free_page * page_size + offset.get_block1()][offset.get_offset()];
1314  }
1315  }
1316  else
1317  {
1318  pager.hit(last_page);
1319  return _cache[last_page * page_size + offset.get_block1()][offset.get_offset()];
1320  }
1321  }
1322 };
1323 
1324 template <
1325  typename Tp_,
1326  unsigned PgSz_,
1327  typename PgTp_,
1328  unsigned BlkSize_,
1329  typename AllocStr_,
1330  typename SzTp_>
1331 inline bool operator == (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1332  AllocStr_, SzTp_> & a,
1333  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1334  AllocStr_, SzTp_> & b)
1335 {
1336  return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1337 }
1338 
1339 template <
1340  typename Tp_,
1341  unsigned PgSz_,
1342  typename PgTp_,
1343  unsigned BlkSize_,
1344  typename AllocStr_,
1345  typename SzTp_>
1346 inline bool operator != (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1347  AllocStr_, SzTp_> & a,
1348  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1349  AllocStr_, SzTp_> & b)
1350 {
1351  return !(a == b);
1352 }
1353 
1354 template <
1355  typename Tp_,
1356  unsigned PgSz_,
1357  typename PgTp_,
1358  unsigned BlkSize_,
1359  typename AllocStr_,
1360  typename SzTp_>
1361 inline bool operator < (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1362  AllocStr_, SzTp_> & a,
1363  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1364  AllocStr_, SzTp_> & b)
1365 {
1366  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
1367 }
1368 
1369 template <
1370  typename Tp_,
1371  unsigned PgSz_,
1372  typename PgTp_,
1373  unsigned BlkSize_,
1374  typename AllocStr_,
1375  typename SzTp_>
1376 inline bool operator > (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1377  AllocStr_, SzTp_> & a,
1378  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1379  AllocStr_, SzTp_> & b)
1380 {
1381  return b < a;
1382 }
1383 
1384 template <
1385  typename Tp_,
1386  unsigned PgSz_,
1387  typename PgTp_,
1388  unsigned BlkSize_,
1389  typename AllocStr_,
1390  typename SzTp_>
1391 inline bool operator <= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1392  AllocStr_, SzTp_> & a,
1393  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1394  AllocStr_, SzTp_> & b)
1395 {
1396  return !(b < a);
1397 }
1398 
1399 template <
1400  typename Tp_,
1401  unsigned PgSz_,
1402  typename PgTp_,
1403  unsigned BlkSize_,
1404  typename AllocStr_,
1405  typename SzTp_>
1406 inline bool operator >= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1407  AllocStr_, SzTp_> & a,
1408  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1409  AllocStr_, SzTp_> & b)
1410 {
1411  return !(a < b);
1412 }
1413 
1415 
1417 
1418 // specialization for stxxl::vector, to use only const_iterators
1419 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
1420  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
1421 bool is_sorted(
1422  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first,
1423  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last)
1424 {
1425  return is_sorted_helper(
1426  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first),
1427  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last));
1428 }
1429 
1430 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
1431  unsigned BlkSize_, typename PgTp_, unsigned PgSz_, typename _StrictWeakOrdering>
1432 bool is_sorted(
1433  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first,
1434  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last,
1435  _StrictWeakOrdering __comp)
1436 {
1437  return is_sorted_helper(
1438  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first),
1439  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last),
1440  __comp);
1441 }
1442 
1444 
1447 
1449 
1472 template <
1473  typename Tp_,
1474  unsigned PgSz_ = 4,
1475  unsigned Pages_ = 8,
1476  unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_),
1477  typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY,
1478  pager_type Pager_ = lru
1479  >
1481 {
1482  typedef typename IF<Pager_ == lru,
1484 
1486 };
1487 
1488 
1490 
1491 __STXXL_END_NAMESPACE
1492 
1493 
1494 namespace std
1495 {
1496  template <
1497  typename Tp_,
1498  unsigned PgSz_,
1499  typename PgTp_,
1500  unsigned BlkSize_,
1501  typename AllocStr_,
1502  typename SzTp_>
1503  void swap(stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & a,
1504  stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & b)
1505  {
1506  a.swap(b);
1507  }
1508 }
1509 
1510 #endif // !STXXL_VECTOR_HEADER