STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
vector.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/vector.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2008 Roman Dementiev <[email protected]>
7  * Copyright (C) 2007-2009 Johannes Singler <[email protected]>
8  * Copyright (C) 2008-2010 Andreas Beckmann <[email protected]>
9  * Copyright (C) 2013 Timo Bingmann <[email protected]>
10  *
11  * Distributed under the Boost Software License, Version 1.0.
12  * (See accompanying file LICENSE_1_0.txt or copy at
13  * http://www.boost.org/LICENSE_1_0.txt)
14  **************************************************************************/
15 
16 #ifndef STXXL_CONTAINERS_VECTOR_HEADER
17 #define STXXL_CONTAINERS_VECTOR_HEADER
18 
19 #include <vector>
20 #include <queue>
21 #include <algorithm>
22 
23 #include <stxxl/bits/deprecated.h>
33 
35 
36 #define STXXL_VERBOSE_VECTOR(msg) STXXL_VERBOSE1("vector[" << static_cast<const void*>(this) << "]::" << msg)
37 
38 //! \defgroup stlcont Containers
39 //! \ingroup stllayer
40 //! Containers with STL-compatible interface
41 
42 //! \defgroup stlcont_vector vector
43 //! \ingroup stlcont
44 //! Vector and support classes
45 //! \{
46 
47 template <typename SizeType, SizeType modulo2, SizeType modulo1>
49 {
50  typedef SizeType size_type;
51 
52  static const size_type modulo12 = modulo1 * modulo2;
53 
55  unsigned_type block1, block2, offset;
56 
57  //! \invariant block2 * modulo12 + block1 * modulo1 + offset == pos && 0 <= block1 &lt; modulo2 && 0 <= offset &lt; modulo1
58 
59  void set(size_type pos)
60  {
61  this->pos = pos;
62  block2 = (int_type)(pos / modulo12);
63  pos -= block2 * modulo12;
64  block1 = (int_type)(pos / modulo1);
65  offset = (int_type)(pos - block1 * modulo1);
66 
67  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
68  assert(/* 0 <= block1 && */ block1 < modulo2);
69  assert(/* 0 <= offset && */ offset < modulo1);
70  }
71 
72 public:
74  {
75  set(0);
76  }
77 
79  {
80  set(pos);
81  }
82 
84  {
85  assert(/* 0 <= block1 && */ block1 < modulo2);
86  assert(/* 0 <= offset && */ offset < modulo1);
87 
88  this->block2 = block2;
89  this->block1 = block1;
90  this->offset = offset;
91  pos = block2 * modulo12 + block1 * modulo1 + offset;
92  }
93 
94  double_blocked_index& operator = (size_type pos)
95  {
96  set(pos);
97  return *this;
98  }
99 
100  //pre-increment operator
102  {
103  ++pos;
104  ++offset;
105  if (offset == modulo1)
106  {
107  offset = 0;
108  ++block1;
109  if (block1 == modulo2)
110  {
111  block1 = 0;
112  ++block2;
113  }
114  }
115 
116  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
117  assert(/* 0 <= block1 && */ block1 < modulo2);
118  assert(/* 0 <= offset && */ offset < modulo1);
119 
120  return *this;
121  }
122 
123  //post-increment operator
125  {
126  double_blocked_index former(*this);
127  operator ++ ();
128  return former;
129  }
130 
131  //pre-increment operator
133  {
134  --pos;
135  if (offset == 0)
136  {
137  offset = modulo1;
138  if (block1 == 0)
139  {
140  block1 = modulo2;
141  --block2;
142  }
143  --block1;
144  }
145  --offset;
146 
147  assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
148  assert(/*0 <= block1 &&*/ block1 < modulo2);
149  assert(/*0 <= offset &&*/ offset < modulo1);
150 
151  return *this;
152  }
153 
154  //post-increment operator
156  {
157  double_blocked_index former(*this);
158  operator -- ();
159  return former;
160  }
161 
162  double_blocked_index operator + (size_type addend) const
163  {
164  return double_blocked_index(pos + addend);
165  }
166 
168  {
169  set(pos + addend);
170  return *this;
171  }
172 
173  double_blocked_index operator - (size_type addend) const
174  {
175  return double_blocked_index(pos - addend);
176  }
177 
178  size_type operator - (const double_blocked_index& dbi2) const
179  {
180  return pos - dbi2.pos;
181  }
182 
183  double_blocked_index& operator -= (size_type subtrahend)
184  {
185  set(pos - subtrahend);
186  return *this;
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  bool operator > (const double_blocked_index& dbi2) const
210  {
211  return pos > dbi2.pos;
212  }
213 
214  bool operator >= (const double_blocked_index& dbi2) const
215  {
216  return pos >= dbi2.pos;
217  }
218 
219  double_blocked_index& operator >>= (size_type shift)
220  {
221  set(pos >> shift);
222  return *this;
223  }
224 
226  {
227  return pos;
228  }
229 
230  const unsigned_type & get_block2() const
231  {
232  return block2;
233  }
234 
235  const unsigned_type & get_block1() const
236  {
237  return block1;
238  }
239 
240  const unsigned_type & get_offset() const
241  {
242  return offset;
243  }
244 };
245 
246 ////////////////////////////////////////////////////////////////////////////
247 
248 template <
249  typename ValueType,
250  unsigned PageSize,
251  typename PagerType,
252  unsigned BlockSize,
253  typename AllocStr,
254  typename SizeType>
255 class vector;
256 
257 template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
258  unsigned BlockSize, typename PagerType, unsigned PageSize>
260 
261 template <typename VectorIteratorType>
263 
264 template <typename VectorIteratorType>
266 
267 template <typename VectorIteratorType>
269 
270 ////////////////////////////////////////////////////////////////////////////
271 
272 //! External vector iterator, model of \c ext_random_access_iterator concept.
273 template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
274  unsigned BlockSize, typename PagerType, unsigned PageSize>
276 {
277  typedef vector_iterator<ValueType, AllocStr, SizeType,
278  DiffType, BlockSize, PagerType, PageSize> self_type;
279 
280  typedef const_vector_iterator<ValueType, AllocStr, SizeType,
281  DiffType, BlockSize, PagerType, PageSize> const_self_type;
282 
283  friend class const_vector_iterator<ValueType, AllocStr, SizeType,
284  DiffType, BlockSize, PagerType, PageSize>;
285 
286 public:
287  //! \name Types
288  //! \{
289 
292 
293  typedef unsigned block_offset_type;
295  friend class vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType>;
297  typedef typename bids_container_type::iterator bids_container_iterator;
301 
302  typedef std::random_access_iterator_tag iterator_category;
308  typedef typename vector_type::pointer pointer;
310 
311  //! \}
312 
313 protected:
316 
317 private:
318  //! private constructor for initializing other iterators
320  : offset(o), p_vector(v)
321  { }
322 
323 public:
324  //! constructs invalid iterator
326  : offset(0), p_vector(NULL)
327  { }
328  //! copy-constructor
330  : offset(a.offset),
331  p_vector(a.p_vector)
332  { }
333 
334  //! \name Iterator Properties
335  //! \{
336 
337  //! return pointer to vector containing iterator
339  {
340  return p_vector;
341  }
342  //! return block offset of current element
344  {
345  return static_cast<block_offset_type>(offset.get_offset());
346  }
347  //! return iterator to BID containg current element
349  {
350  return p_vector->bid(offset);
351  }
352 
353  //! \}
354 
355  //! \name Access Operators
356  //! \{
357 
358  //! return current element
359  reference operator * ()
360  {
361  return p_vector->element(offset);
362  }
363  //! return pointer to current element
364  pointer operator -> ()
365  {
366  return &(p_vector->element(offset));
367  }
368  //! return const reference to current element
369  const_reference operator * () const
370  {
371  return p_vector->const_element(offset);
372  }
373  //! return const pointer to current element
374  const_pointer operator -> () const
375  {
376  return &(p_vector->const_element(offset));
377  }
378  //! return mutable reference to element +i after the current element
379  reference operator [] (size_type i)
380  {
381  return p_vector->element(offset.get_pos() + i);
382  }
383 
384 #ifdef _LIBCPP_VERSION
385  //-tb 2013-11: libc++ defines std::reverse_iterator::operator[] in such a
386  // way that it expects vector_iterator::operator[] to return a (mutable)
387  // reference. Thus to remove confusion about the compiler error, we remove
388  // the operator[] const for libc++. The const_reference actually violates
389  // some version of the STL standard, but works well in gcc's libstdc++.
390 #else
391  //! return const reference to element +i after the current element
392  const_reference operator [] (size_type i) const
393  {
394  return p_vector->const_element(offset.get_pos() + i);
395  }
396 #endif
397  //! \}
398 
399  //! \name Relative Calculation of Iterators
400  //! \{
401 
402  //! calculate different between two iterator
403  difference_type operator - (const self_type& a) const
404  {
405  return offset - a.offset;
406  }
407  //! calculate different between two iterator
408  difference_type operator - (const const_self_type& a) const
409  {
410  return offset - a.offset;
411  }
412  //! return iterator advanced -i positions in the vector
413  self_type operator - (size_type i) const
414  {
415  return self_type(p_vector, offset.get_pos() - i);
416  }
417  //! return iterator advanced +i positions in the vector
418  self_type operator + (size_type i) const
419  {
420  return self_type(p_vector, offset.get_pos() + i);
421  }
422  //! advance this iterator -i positions in the vector
423  self_type& operator -= (size_type i)
424  {
425  offset -= i;
426  return *this;
427  }
428  //! advance this iterator +i positions in the vector
430  {
431  offset += i;
432  return *this;
433  }
434  //! advance this iterator to next position in the vector
436  {
437  offset++;
438  return *this;
439  }
440  //! advance this iterator to next position in the vector
442  {
443  self_type tmp = *this;
444  offset++;
445  return tmp;
446  }
447  //! advance this iterator to preceding position in the vector
449  {
450  offset--;
451  return *this;
452  }
453  //! advance this iterator to preceding position in the vector
455  {
456  self_type tmp = *this;
457  offset--;
458  return tmp;
459  }
460 
461  //! \}
462 
463  //! \name Comparison Operators
464  //! \{
465 
466  bool operator == (const self_type& a) const
467  {
468  assert(p_vector == a.p_vector);
469  return offset == a.offset;
470  }
471  bool operator != (const self_type& a) const
472  {
473  assert(p_vector == a.p_vector);
474  return offset != a.offset;
475  }
476  bool operator < (const self_type& a) const
477  {
478  assert(p_vector == a.p_vector);
479  return offset < a.offset;
480  }
481  bool operator <= (const self_type& a) const
482  {
483  assert(p_vector == a.p_vector);
484  return offset <= a.offset;
485  }
486  bool operator > (const self_type& a) const
487  {
488  assert(p_vector == a.p_vector);
489  return offset > a.offset;
490  }
491  bool operator >= (const self_type& a) const
492  {
493  assert(p_vector == a.p_vector);
494  return offset >= a.offset;
495  }
496 
497  bool operator == (const const_self_type& a) const
498  {
499  assert(p_vector == a.p_vector);
500  return offset == a.offset;
501  }
502  bool operator != (const const_self_type& a) const
503  {
504  assert(p_vector == a.p_vector);
505  return offset != a.offset;
506  }
507  bool operator < (const const_self_type& a) const
508  {
509  assert(p_vector == a.p_vector);
510  return offset < a.offset;
511  }
512  bool operator <= (const const_self_type& a) const
513  {
514  assert(p_vector == a.p_vector);
515  return offset <= a.offset;
516  }
517  bool operator > (const const_self_type& a) const
518  {
519  assert(p_vector == a.p_vector);
520  return offset > a.offset;
521  }
522  bool operator >= (const const_self_type& a) const
523  {
524  assert(p_vector == a.p_vector);
525  return offset >= a.offset;
526  }
527 
528  //! \}
529 
530  //! \name Flushing Operation
531  //! \{
532 
534  {
535  p_vector->block_externally_updated(offset);
536  }
537 
538  void flush()
539  {
540  p_vector->flush();
541  }
542 
543  //! \}
544 };
545 
546 ////////////////////////////////////////////////////////////////////////////
547 
548 //! Const external vector iterator, model of \c ext_random_access_iterator concept.
549 template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
550  unsigned BlockSize, typename PagerType, unsigned PageSize>
551 class const_vector_iterator
552 {
553  typedef const_vector_iterator<ValueType, AllocStr, SizeType, DiffType,
554  BlockSize, PagerType, PageSize> self_type;
555 
556  typedef vector_iterator<ValueType, AllocStr, SizeType, DiffType,
557  BlockSize, PagerType, PageSize> mutable_self_type;
558 
559  friend class vector_iterator<ValueType, AllocStr, SizeType, DiffType,
560  BlockSize, PagerType, PageSize>;
561 
562 public:
563  //! \name Types
564  //! \{
565 
568 
569  typedef unsigned block_offset_type;
571  friend class vector<ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType>;
573  typedef typename bids_container_type::iterator bids_container_iterator;
577 
578  typedef std::random_access_iterator_tag iterator_category;
586 
587  //! \}
588 
589 protected:
592 
593 private:
594  //! private constructor for initializing other iterators
596  : offset(o), p_vector(v)
597  { }
598 
599 public:
600  //! constructs invalid iterator
602  : offset(0), p_vector(NULL)
603  { }
604  //! copy-constructor
606  : offset(a.offset), p_vector(a.p_vector)
607  { }
608  //! copy-constructor from mutable iterator
610  : offset(a.offset), p_vector(a.p_vector)
611  { }
612 
613  //! \name Iterator Properties
614  //! \{
615 
616  //! return pointer to vector containing iterator
617  const vector_type * parent_vector() const
618  {
619  return p_vector;
620  }
621  //! return block offset of current element
623  {
624  return static_cast<block_offset_type>(offset.get_offset());
625  }
626  //! return iterator to BID containg current element
628  {
629  return ((vector_type*)p_vector)->bid(offset);
630  }
631 
632  //! \}
633 
634  //! \name Access Operators
635  //! \{
636 
637  //! return current element
638  const_reference operator * () const
639  {
640  return p_vector->const_element(offset);
641  }
642  //! return pointer to current element
643  const_pointer operator -> () const
644  {
645  return &(p_vector->const_element(offset));
646  }
647  //! return const reference to element +i after the current element
648  const_reference operator [] (size_type i) const
649  {
650  return p_vector->const_element(offset.get_pos() + i);
651  }
652 
653  //! \}
654 
655  //! \name Relative Calculation of Iterators
656  //! \{
657 
658  //! calculate different between two iterator
659  difference_type operator - (const self_type& a) const
660  {
661  return offset - a.offset;
662  }
663  //! calculate different between two iterator
664  difference_type operator - (const mutable_self_type& a) const
665  {
666  return offset - a.offset;
667  }
668  //! return iterator advanced -i positions in the vector
669  self_type operator - (size_type i) const
670  {
671  return self_type(p_vector, offset.get_pos() - i);
672  }
673  //! return iterator advanced +i positions in the vector
674  self_type operator + (size_type i) const
675  {
676  return self_type(p_vector, offset.get_pos() + i);
677  }
678  //! advance this iterator -i positions in the vector
679  self_type& operator -= (size_type i)
680  {
681  offset -= i;
682  return *this;
683  }
684  //! advance this iterator +i positions in the vector
686  {
687  offset += i;
688  return *this;
689  }
690  //! advance this iterator to next position in the vector
692  {
693  offset++;
694  return *this;
695  }
696  //! advance this iterator to next position in the vector
698  {
699  self_type tmp_ = *this;
700  offset++;
701  return tmp_;
702  }
703  //! advance this iterator to preceding position in the vector
705  {
706  offset--;
707  return *this;
708  }
709  //! advance this iterator to preceding position in the vector
711  {
712  self_type tmp = *this;
713  offset--;
714  return tmp;
715  }
716 
717  //! \}
718 
719  //! \name Comparison Operators
720  //! \{
721 
722  bool operator == (const self_type& a) const
723  {
724  assert(p_vector == a.p_vector);
725  return offset == a.offset;
726  }
727  bool operator != (const self_type& a) const
728  {
729  assert(p_vector == a.p_vector);
730  return offset != a.offset;
731  }
732  bool operator < (const self_type& a) const
733  {
734  assert(p_vector == a.p_vector);
735  return offset < a.offset;
736  }
737  bool operator <= (const self_type& a) const
738  {
739  assert(p_vector == a.p_vector);
740  return offset <= a.offset;
741  }
742  bool operator > (const self_type& a) const
743  {
744  assert(p_vector == a.p_vector);
745  return offset > a.offset;
746  }
747  bool operator >= (const self_type& a) const
748  {
749  assert(p_vector == a.p_vector);
750  return offset >= a.offset;
751  }
752 
753  bool operator == (const mutable_self_type& a) const
754  {
755  assert(p_vector == a.p_vector);
756  return offset == a.offset;
757  }
758  bool operator != (const mutable_self_type& a) const
759  {
760  assert(p_vector == a.p_vector);
761  return offset != a.offset;
762  }
763  bool operator < (const mutable_self_type& a) const
764  {
765  assert(p_vector == a.p_vector);
766  return offset < a.offset;
767  }
768  bool operator <= (const mutable_self_type& a) const
769  {
770  assert(p_vector == a.p_vector);
771  return offset <= a.offset;
772  }
773  bool operator > (const mutable_self_type& a) const
774  {
775  assert(p_vector == a.p_vector);
776  return offset > a.offset;
777  }
778  bool operator >= (const mutable_self_type& a) const
779  {
780  assert(p_vector == a.p_vector);
781  return offset >= a.offset;
782  }
783 
784  //! \}
785 
786  //! \name Flushing Operation
787  //! \{
788 
790  {
791  p_vector->block_externally_updated(offset);
792  }
793 
794  void flush()
795  {
796  p_vector->flush();
797  }
798 
799  //! \}
800 };
801 
802 ////////////////////////////////////////////////////////////////////////////
803 
804 //! External vector container. \n
805 //! <b>Introduction</b> to vector container: see \ref tutorial_vector tutorial. \n
806 //! <b>Design and Internals</b> of vector container: see \ref design_vector
807 //!
808 //! For semantics of the methods see documentation of the STL std::vector
809 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
810 //! \tparam PageSize number of blocks in a page
811 //! \tparam PagerType pager type, \c random_pager<x> or \c lru_pager<x>, where x is the default number of pages,
812 //! default is \c lru_pager<8>
813 //! \tparam BlockSize external block size in bytes, default is 2 MiB
814 //! \tparam AllocStr one of allocation strategies: \c striping , \c RC , \c SR , or \c FR
815 //! default is RC
816 //!
817 //! Memory consumption: BlockSize*x*PageSize bytes
818 //! \warning Do not store references to the elements of an external vector. Such references
819 //! might be invalidated during any following access to elements of the vector
820 template <
821  typename ValueType,
822  unsigned PageSize = 4,
823  typename PagerType = lru_pager<8>,
824  unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
825  typename AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
826  typename SizeType = stxxl::uint64 // will be deprecated soon
827  >
828 class vector
829 {
830 public:
831  //! \name Standard Types
832  //! \{
833 
834  //! The type of elements stored in the vector.
835  typedef ValueType value_type;
836  //! reference to value_type
838  //! constant reference to value_type
839  typedef const value_type& const_reference;
840  //! pointer to value_type
841  typedef value_type* pointer;
842  //! constant pointer to value_type
843  typedef const value_type* const_pointer;
844  //! an unsigned 64-bit integral type
845  typedef SizeType size_type;
847 
848  typedef PagerType pager_type;
849  typedef AllocStr alloc_strategy_type;
850 
851  enum constants {
852  block_size = BlockSize,
853  page_size = PageSize,
854  on_disk = -1
855  };
856 
857  //! iterator used to iterate through a vector, see \ref design_vector_notes.
858  typedef vector_iterator<value_type, alloc_strategy_type, size_type,
859  difference_type, block_size, pager_type, page_size> iterator;
861 
862  //! constant iterator used to iterate through a vector, see \ref design_vector_notes.
866  typedef std::reverse_iterator<iterator> reverse_iterator;
867  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
868 
869  //! \}
870 
871  //! \name Extra Types
872  //! \{
873 
874  //! vector_bufwriter compatible with this vector
876 
877  //! vector_bufreader compatible with this vector
879 
880  //! vector_bufreader compatible with this vector
882 
883  //! \internal
884  class bid_vector : public std::vector<BID<block_size> >
885  {
886  public:
887  typedef std::vector<BID<block_size> > super_type;
888  typedef typename super_type::size_type size_type;
889  typedef typename super_type::value_type bid_type;
890 
892  { }
893  };
894 
895  typedef bid_vector bids_container_type;
896  typedef typename bids_container_type::iterator bids_container_iterator;
897  typedef typename bids_container_type::const_iterator const_bids_container_iterator;
898 
899  //! type of the block used in disk-memory transfers
901  //! double-index type to reference individual elements in a block
903 
904  //! \}
905 
906 private:
911 
912  // enum specifying status of a page of the vector
913  enum { valid_on_disk = 0, uninitialized = 1, dirty = 2 };
914  //! status of each page (valid_on_disk, uninitialized or dirty)
915  mutable std::vector<unsigned char> m_page_status;
916  mutable std::vector<int_type> m_page_to_slot;
918  mutable std::queue<int_type> m_free_slots;
923 
925  {
926  stxxl::uint64 blocks_fit = file_length / stxxl::uint64(block_type::raw_size);
927  size_type cur_size = blocks_fit * stxxl::uint64(block_type::size);
928  stxxl::uint64 rest = file_length - blocks_fit * stxxl::uint64(block_type::raw_size);
929  return (cur_size + rest / stxxl::uint64(sizeof(value_type)));
930  }
931 
933  {
934  typedef stxxl::uint64 file_size_type;
935  size_type cur_size = size();
936  size_type num_full_blocks = cur_size / block_type::size;
937  if (cur_size % block_type::size != 0)
938  {
939  size_type rest = cur_size - num_full_blocks * block_type::size;
940  return file_size_type(num_full_blocks) * block_type::raw_size + rest * sizeof(value_type);
941  }
942  return file_size_type(num_full_blocks) * block_type::raw_size;
943  }
944 
945 public:
946  //! \name Constructors/Destructors
947  //! \{
948 
949  //! Constructs external vector with n elements.
950  //!
951  //! \param n Number of elements.
952  //! \param npages Number of cached pages.
953  vector(size_type n = 0, unsigned_type npages = pager_type().size())
954  : m_size(n),
955  m_bids((size_t)div_ceil(n, block_type::size)),
956  m_pager(npages),
957  m_page_status(div_ceil(m_bids.size(), page_size)),
958  m_page_to_slot(div_ceil(m_bids.size(), page_size)),
959  m_slot_to_page(npages),
960  m_cache(NULL),
961  m_from(NULL),
962  m_exported(false)
963  {
964  m_bm = block_manager::get_instance();
965 
966  allocate_page_cache();
967 
968  for (size_t i = 0; i < m_page_status.size(); ++i)
969  {
970  m_page_status[i] = uninitialized;
971  m_page_to_slot[i] = on_disk;
972  }
973 
974  for (unsigned_type i = 0; i < numpages(); ++i)
975  m_free_slots.push(i);
976 
977  m_bm->new_blocks(m_alloc_strategy, m_bids.begin(), m_bids.end(), 0);
978  }
979 
980  //! \}
981 
982  //! \name Modifier
983  //! \{
984 
985  //! swap content
986  void swap(vector& obj)
987  {
988  std::swap(m_alloc_strategy, obj.m_alloc_strategy);
989  std::swap(m_size, obj.m_size);
990  std::swap(m_bids, obj.m_bids);
991  std::swap(m_pager, obj.m_pager);
992  std::swap(m_page_status, obj.m_page_status);
993  std::swap(m_page_to_slot, obj.m_page_to_slot);
994  std::swap(m_slot_to_page, obj.m_slot_to_page);
995  std::swap(m_free_slots, obj.m_free_slots);
996  std::swap(m_cache, obj.m_cache);
997  std::swap(m_from, obj.m_from);
998  std::swap(m_exported, obj.m_exported);
999  }
1000 
1001  //! \}
1002 
1003  //! \name Miscellaneous
1004  //! \{
1005 
1006  //! Allocate page cache, must be called to allow access to elements.
1007  void allocate_page_cache() const
1008  {
1009  // numpages() might be zero
1010  if (!m_cache && numpages() > 0)
1011  m_cache = new simple_vector<block_type>(numpages() * page_size);
1012  }
1013 
1014  //! allows to free the cache, but you may not access any element until call
1015  //! allocate_page_cache() again
1017  {
1018  flush();
1019  delete m_cache;
1020  m_cache = NULL;
1021  }
1022 
1023  //! \name Size and Capacity
1024  //! \{
1025 
1026  //! return the size of the vector.
1027  size_type size() const
1028  {
1029  return m_size;
1030  }
1031  //! true if the vector's size is zero.
1032  bool empty() const
1033  {
1034  return (!m_size);
1035  }
1036 
1037  //! Return the number of elelemtsn for which \a external memory has been
1038  //! allocated. capacity() is always greator than or equal to size().
1040  {
1041  return size_type(m_bids.size()) * block_type::size;
1042  }
1043  //! Returns the number of bytes that the vector has allocated on disks.
1045  {
1046  return size_type(m_bids.size()) * block_type::raw_size;
1047  }
1048 
1049  /*! Reserves at least n elements in external memory.
1050  *
1051  * If n is less than or equal to capacity(), this call has no
1052  * effect. Otherwise, it is a request for allocation of additional \b
1053  * external memory. If the request is successful, then capacity() is
1054  * greater than or equal to n; otherwise capacity() is unchanged. In either
1055  * case, size() is unchanged.
1056  */
1058  {
1059  if (n <= capacity())
1060  return;
1061 
1062  unsigned_type old_bids_size = m_bids.size();
1063  unsigned_type new_bids_size = (unsigned_type)div_ceil(n, block_type::size);
1064  unsigned_type new_pages = div_ceil(new_bids_size, page_size);
1065  m_page_status.resize(new_pages, uninitialized);
1066  m_page_to_slot.resize(new_pages, on_disk);
1067 
1068  m_bids.resize(new_bids_size);
1069  if (m_from == NULL)
1070  {
1071  m_bm->new_blocks(m_alloc_strategy,
1072  m_bids.begin() + old_bids_size, m_bids.end(),
1073  old_bids_size);
1074  }
1075  else
1076  {
1077  size_type offset = size_type(old_bids_size) * size_type(block_type::raw_size);
1078  for (bids_container_iterator it = m_bids.begin() + old_bids_size;
1079  it != m_bids.end(); ++it, offset += size_type(block_type::raw_size))
1080  {
1081  (*it).storage = m_from;
1082  (*it).offset = offset;
1083  }
1084  STXXL_VERBOSE_VECTOR("reserve(): Changing size of file " <<
1085  ((void*)m_from) << " to " << offset);
1086  m_from->set_size(offset);
1087  }
1088  }
1089 
1090  //! Resize vector contents to n items.
1091  //! \warning this will not call the constructor of objects in external memory!
1093  {
1094  _resize(n);
1095  }
1096 
1097  //! Resize vector contents to n items, and allow the allocated external
1098  //! memory to shrink. Internal memory allocation remains unchanged.
1099  //! \warning this will not call the constructor of objects in external memory!
1100  void resize(size_type n, bool shrink_capacity)
1101  {
1102  if (shrink_capacity)
1103  _resize_shrink_capacity(n);
1104  else
1105  _resize(n);
1106  }
1107 
1108  //! \}
1109 
1110 private:
1111  //! Resize vector, only allow capacity growth.
1113  {
1114  reserve(n);
1115  if (n < m_size) {
1116  // mark excess pages as uninitialized and evict them from cache
1117  unsigned_type first_page_to_evict = (unsigned_type)div_ceil(n, block_type::size * page_size);
1118  for (size_t i = first_page_to_evict; i < m_page_status.size(); ++i) {
1119  if (m_page_to_slot[i] != on_disk) {
1120  m_free_slots.push(m_page_to_slot[i]);
1121  m_page_to_slot[i] = on_disk;
1122  }
1123  m_page_status[i] = uninitialized;
1124  }
1125  }
1126  m_size = n;
1127  }
1128 
1129  //! Resize vector, also allow reduction of external memory capacity.
1131  {
1132  unsigned_type old_bids_size = m_bids.size();
1133  unsigned_type new_bids_size = (unsigned_type)div_ceil(n, block_type::size);
1134 
1135  if (new_bids_size > old_bids_size)
1136  {
1137  reserve(n);
1138  }
1139  else if (new_bids_size < old_bids_size)
1140  {
1141  unsigned_type new_pages_size = div_ceil(new_bids_size, page_size);
1142 
1143  STXXL_VERBOSE_VECTOR("shrinking from " << old_bids_size << " to " <<
1144  new_bids_size << " blocks = from " <<
1145  m_page_status.size() << " to " <<
1146  new_pages_size << " pages");
1147 
1148  // release blocks
1149  if (m_from != NULL)
1150  m_from->set_size(new_bids_size * block_type::raw_size);
1151  else
1152  m_bm->delete_blocks(m_bids.begin() + old_bids_size, m_bids.end());
1153 
1154  m_bids.resize(new_bids_size);
1155 
1156  // don't resize m_page_to_slot or m_page_status, because it is
1157  // still needed to check page status and match the mapping
1158  // m_slot_to_page
1159 
1160  // clear dirty flag, so these pages will be never written
1161  std::fill(m_page_status.begin() + new_pages_size,
1162  m_page_status.end(), (unsigned char)valid_on_disk);
1163  }
1164 
1165  m_size = n;
1166  }
1167 
1168 public:
1169  //! \name Modifiers
1170  //! \{
1171 
1172  //! Erases all of the elements and deallocates all external memory that is
1173  //! occupied.
1174  void clear()
1175  {
1176  m_size = 0;
1177  if (m_from == NULL)
1178  m_bm->delete_blocks(m_bids.begin(), m_bids.end());
1179 
1180  m_bids.clear();
1181  m_page_status.clear();
1182  m_page_to_slot.clear();
1183  while (!m_free_slots.empty())
1184  m_free_slots.pop();
1185 
1186  for (unsigned_type i = 0; i < numpages(); ++i)
1187  m_free_slots.push(i);
1188  }
1189 
1190  //! \name Front and Back Access
1191  //! \{
1192 
1193  //! Append a new element at the end.
1195  {
1196  size_type old_size = m_size;
1197  resize(old_size + 1);
1198  element(old_size) = obj;
1199  }
1200  //! Removes the last element (without returning it, see back()).
1201  void pop_back()
1202  {
1203  resize(m_size - 1);
1204  }
1205 
1206  //! \}
1207 
1208  //! \name Operators
1209  //! \{
1210 
1211  //! Returns a reference to the last element, see \ref design_vector_notes.
1213  {
1214  return element(m_size - 1);
1215  }
1216  //! Returns a reference to the first element, see \ref design_vector_notes.
1218  {
1219  return element(0);
1220  }
1221  //! Returns a constant reference to the last element, see \ref design_vector_notes.
1223  {
1224  return const_element(m_size - 1);
1225  }
1226  //! Returns a constant reference to the first element, see \ref design_vector_notes.
1228  {
1229  return const_element(0);
1230  }
1231 
1232  //! \}
1233 
1234  //! \name Constructors/Destructors
1235  //! \{
1236 
1237  //! Construct vector from a file.
1238  //! \param from file to be constructed from
1239  //! \param size Number of elements.
1240  //! \param npages Number of cached pages.
1241  //! \warning Only one \c vector can be assigned to a particular (physical) file.
1242  //! The block size of the vector must be a multiple of the element size
1243  //! \c sizeof(ValueType) and the page size (4096).
1244  vector(file* from, size_type size = size_type(-1), unsigned_type npages = pager_type().size())
1245  : m_size((size == size_type(-1)) ? size_from_file_length(from->size()) : size),
1246  m_bids((size_t)div_ceil(m_size, size_type(block_type::size))),
1247  m_pager(npages),
1248  m_page_status(div_ceil(m_bids.size(), page_size)),
1249  m_page_to_slot(div_ceil(m_bids.size(), page_size)),
1250  m_slot_to_page(npages),
1251  m_cache(NULL),
1252  m_from(from),
1253  m_exported(false)
1254  {
1255  // initialize from file
1256  if (!block_type::has_only_data)
1257  {
1258  std::ostringstream str;
1259  str << "The block size for a vector that is mapped to a file must be a multiple of the element size (" <<
1260  sizeof(value_type) << ") and the page size (4096).";
1261  throw std::runtime_error(str.str());
1262  }
1263 
1264  m_bm = block_manager::get_instance();
1265 
1266  allocate_page_cache();
1267 
1268  for (size_t i = 0; i < m_page_status.size(); ++i)
1269  {
1270  m_page_status[i] = valid_on_disk;
1271  m_page_to_slot[i] = on_disk;
1272  }
1273 
1274  for (unsigned_type i = 0; i < numpages(); ++i)
1275  m_free_slots.push(i);
1276 
1277  // allocate blocks equidistantly and in-order
1278  size_type offset = 0;
1279  for (bids_container_iterator it = m_bids.begin();
1280  it != m_bids.end(); ++it, offset += size_type(block_type::raw_size))
1281  {
1282  (*it).storage = from;
1283  (*it).offset = offset;
1284  }
1285  from->set_size(offset);
1286  }
1287 
1288  //! copy-constructor
1289  vector(const vector& obj)
1290  : m_size(obj.size()),
1291  m_bids((size_t)div_ceil(obj.size(), block_type::size)),
1292  m_pager(obj.numpages()),
1293  m_page_status(div_ceil(m_bids.size(), page_size)),
1294  m_page_to_slot(div_ceil(m_bids.size(), page_size)),
1295  m_slot_to_page(obj.numpages()),
1296  m_cache(NULL),
1297  m_from(NULL),
1298  m_exported(false)
1299  {
1300  assert(!obj.m_exported);
1301  m_bm = block_manager::get_instance();
1302 
1303  allocate_page_cache();
1304 
1305  for (size_t i = 0; i < m_page_status.size(); ++i)
1306  {
1307  m_page_status[i] = uninitialized;
1308  m_page_to_slot[i] = on_disk;
1309  }
1310 
1311  for (unsigned_type i = 0; i < numpages(); ++i)
1312  m_free_slots.push(i);
1313 
1314  m_bm->new_blocks(m_alloc_strategy, m_bids.begin(), m_bids.end(), 0);
1315 
1316  const_iterator inbegin = obj.begin();
1317  const_iterator inend = obj.end();
1318  std::copy(inbegin, inend, begin());
1319  }
1320 
1321  //! \}
1322 
1323  //! \name Operators
1324  //! \{
1325 
1326  //! assignment operator
1327  vector& operator = (const vector& obj)
1328  {
1329  if (&obj != this)
1330  {
1331  vector tmp(obj);
1332  this->swap(tmp);
1333  }
1334  return *this;
1335  }
1336 
1337  //! \}
1338 
1339  //! \name Iterator Construction
1340  //! \{
1341 
1342  //! returns an iterator pointing to the beginning of the vector, see \ref design_vector_notes.
1344  {
1345  return iterator(this, 0);
1346  }
1347  //! returns a const_iterator pointing to the beginning of the vector, see \ref design_vector_notes.
1349  {
1350  return const_iterator(this, 0);
1351  }
1352  //! returns a const_iterator pointing to the beginning of the vector, see \ref design_vector_notes.
1354  {
1355  return begin();
1356  }
1357  //! returns an iterator pointing beyond the end of the vector, see \ref design_vector_notes.
1359  {
1360  return iterator(this, m_size);
1361  }
1362  //! returns a const_iterator pointing beyond the end of the vector, see \ref design_vector_notes.
1364  {
1365  return const_iterator(this, m_size);
1366  }
1367  //! returns a const_iterator pointing beyond the end of the vector, see \ref design_vector_notes.
1369  {
1370  return end();
1371  }
1372 
1373  //! returns a reverse_iterator pointing to the end of the vector.
1375  {
1376  return reverse_iterator(end());
1377  }
1378  //! returns a reverse_iterator pointing to the end of the vector.
1380  {
1381  return const_reverse_iterator(end());
1382  }
1383  //! returns a reverse_iterator pointing to the end of the vector.
1385  {
1386  return const_reverse_iterator(end());
1387  }
1388  //! returns a reverse_iterator pointing beyond the beginning of the vector.
1390  {
1391  return reverse_iterator(begin());
1392  }
1393  //! returns a reverse_iterator pointing beyond the beginning of the vector.
1395  {
1396  return const_reverse_iterator(begin());
1397  }
1398  //! returns a reverse_iterator pointing beyond the beginning of the vector.
1400  {
1401  return const_reverse_iterator(begin());
1402  }
1403 
1404  //! \}
1405 
1406  //! \name Direct Element Access
1407  //! \{
1408 
1409  //! access the element at the given vector's offset
1410  reference operator [] (size_type offset)
1411  {
1412  return element(offset);
1413  }
1414  //! access the element at the given vector's offset
1415  const_reference operator [] (size_type offset) const
1416  {
1417  return const_element(offset);
1418  }
1419 
1420  //! access the element at the given vector's offset
1422  {
1423  assert(offset < (size_type)size());
1424  return element(offset);
1425  }
1426  //! access the element at the given vector's offset
1428  {
1429  assert(offset < (size_type)size());
1430  return const_element(offset);
1431  }
1432 
1433  //! return true if the given vector offset is in cache
1434  bool is_element_cached(size_type offset) const
1435  {
1436  return is_page_cached(blocked_index_type(offset));
1437  }
1438 
1439  //! \}
1440 
1441  //! \name Modifiers
1442  //! \{
1443 
1444  //! Flushes the cache pages to the external memory.
1445  void flush() const
1446  {
1447  simple_vector<bool> non_free_slots(numpages());
1448 
1449  for (unsigned_type i = 0; i < numpages(); i++)
1450  non_free_slots[i] = true;
1451 
1452  while (!m_free_slots.empty())
1453  {
1454  non_free_slots[m_free_slots.front()] = false;
1455  m_free_slots.pop();
1456  }
1457 
1458  for (unsigned_type i = 0; i < numpages(); i++)
1459  {
1460  m_free_slots.push(i);
1461  int_type page_no = m_slot_to_page[i];
1462  if (non_free_slots[i])
1463  {
1464  STXXL_VERBOSE_VECTOR("flush(): flushing page " << i << " at address " <<
1465  (int64(page_no) * int64(block_type::size) * int64(page_size)));
1466  write_page(page_no, i);
1467 
1468  m_page_to_slot[page_no] = on_disk;
1469  }
1470  }
1471  }
1472 
1473  //! \}
1474 
1475  //! \name Constructors/Destructors
1476  //! \{
1477 
1479  {
1480  STXXL_VERBOSE_VECTOR("~vector()");
1481  try
1482  {
1483  flush();
1484  }
1485  catch (io_error e)
1486  {
1487  STXXL_ERRMSG("io_error thrown in ~vector(): " << e.what());
1488  }
1489  catch (...)
1490  {
1491  STXXL_ERRMSG("Exception thrown in ~vector()");
1492  }
1493 
1494  if (!m_exported)
1495  {
1496  if (m_from == NULL) {
1497  m_bm->delete_blocks(m_bids.begin(), m_bids.end());
1498  }
1499  else // file must be truncated
1500  {
1501  STXXL_VERBOSE_VECTOR("~vector(): Changing size of file " <<
1502  ((void*)m_from) << " to " << file_length());
1503  STXXL_VERBOSE_VECTOR("~vector(): size of the vector is " << size());
1504  try
1505  {
1506  m_from->set_size(file_length());
1507  }
1508  catch (...)
1509  {
1510  STXXL_ERRMSG("Exception thrown in ~vector()...set_size()");
1511  }
1512  }
1513  }
1514  delete m_cache;
1515  }
1516 
1517  //! \}
1518 
1519  //! \name Miscellaneous
1520  //! \{
1521 
1522  //! Export data such that it is persistent on the file system. Resulting
1523  //! files will be numbered ascending.
1524  void export_files(std::string filename_prefix)
1525  {
1526  int64 no = 0;
1527  for (bids_container_iterator i = m_bids.begin(); i != m_bids.end(); ++i) {
1528  std::ostringstream number;
1529  number << std::setw(9) << std::setfill('0') << no;
1530  size_type current_block_size =
1531  ((i + 1) == m_bids.end() && m_size % block_type::size > 0) ?
1532  (m_size % block_type::size) * sizeof(value_type) :
1533  block_type::size * sizeof(value_type);
1534  (*i).storage->export_files((*i).offset, current_block_size, filename_prefix + number.str());
1535  ++no;
1536  }
1537  m_exported = true;
1538  }
1539 
1540  //! Get the file associated with this vector, or NULL.
1541  file * get_file() const
1542  {
1543  return m_from;
1544  }
1545 
1546  //! \}
1547 
1548  //! \name Capacity
1549  //! \{
1550 
1551  //! Set the blocks and the size of this container explicitly.
1552  //! The vector must be completely empty before.
1553  template <typename ForwardIterator>
1554  void set_content(const ForwardIterator& bid_begin, const ForwardIterator& bid_end, size_type n)
1555  {
1556  unsigned_type new_bids_size = div_ceil(n, block_type::size);
1557  m_bids.resize(new_bids_size);
1558  std::copy(bid_begin, bid_end, m_bids.begin());
1559  unsigned_type new_pages = div_ceil(new_bids_size, page_size);
1560  m_page_status.resize(new_pages, valid_on_disk);
1561  m_page_to_slot.resize(new_pages, on_disk);
1562  m_size = n;
1563  }
1564 
1565  //! Number of pages used by the pager.
1566  inline unsigned_type numpages() const
1567  {
1568  return m_pager.size();
1569  }
1570 
1571  //! \}
1572 
1573 private:
1575  {
1576  return (m_bids.begin() +
1577  static_cast<typename bids_container_type::size_type>
1578  (offset / block_type::size));
1579  }
1581  {
1582  return (m_bids.begin() +
1583  static_cast<typename bids_container_type::size_type>
1584  (offset.get_block2() * PageSize + offset.get_block1()));
1585  }
1587  {
1588  return (m_bids.begin() +
1589  static_cast<typename bids_container_type::size_type>
1590  (offset / block_type::size));
1591  }
1593  {
1594  return (m_bids.begin() +
1595  static_cast<typename bids_container_type::size_type>
1596  (offset.get_block2() * PageSize + offset.get_block1()));
1597  }
1598 
1599  void read_page(int_type page_no, int_type cache_slot) const
1600  {
1601  assert(page_no < (int_type)m_page_status.size());
1602  if (m_page_status[page_no] == uninitialized)
1603  return;
1604  STXXL_VERBOSE_VECTOR("read_page(): page_no=" << page_no << " cache_slot=" << cache_slot);
1605  request_ptr* reqs = new request_ptr[page_size];
1606  int_type block_no = page_no * page_size;
1607  int_type last_block = STXXL_MIN(block_no + page_size, int_type(m_bids.size()));
1608  int_type i = cache_slot * page_size, j = 0;
1609  for ( ; block_no < last_block; ++block_no, ++i, ++j)
1610  {
1611  reqs[j] = (*m_cache)[i].read(m_bids[block_no]);
1612  }
1613  assert(last_block - page_no * page_size > 0);
1614  wait_all(reqs, last_block - page_no * page_size);
1615  delete[] reqs;
1616  }
1617  void write_page(int_type page_no, int_type cache_slot) const
1618  {
1619  assert(page_no < (int_type)m_page_status.size());
1620  if (!(m_page_status[page_no] & dirty))
1621  return;
1622  STXXL_VERBOSE_VECTOR("write_page(): page_no=" << page_no << " cache_slot=" << cache_slot);
1623  request_ptr* reqs = new request_ptr[page_size];
1624  int_type block_no = page_no * page_size;
1625  int_type last_block = STXXL_MIN(block_no + page_size, int_type(m_bids.size()));
1626  assert(block_no < last_block);
1627  int_type i = cache_slot * page_size, j = 0;
1628  for ( ; block_no < last_block; ++block_no, ++i, ++j)
1629  {
1630  reqs[j] = (*m_cache)[i].write(m_bids[block_no]);
1631  }
1632  m_page_status[page_no] = valid_on_disk;
1633  assert(last_block - page_no * page_size > 0);
1634  wait_all(reqs, last_block - page_no * page_size);
1635  delete[] reqs;
1636  }
1637 
1639  {
1640 #ifdef STXXL_RANGE_CHECK
1641  assert(offset < (size_type)size());
1642 #endif
1643  return element(blocked_index_type(offset));
1644  }
1645 
1647  {
1648 #ifdef STXXL_RANGE_CHECK
1649  assert(offset.get_pos() < size());
1650 #endif
1651  unsigned_type page_no = offset.get_block2();
1652  assert(page_no < m_page_to_slot.size()); // fails if offset is too large, out of bound access
1653  int_type cache_slot = m_page_to_slot[page_no];
1654  if (cache_slot < 0) // == on_disk
1655  {
1656  if (m_free_slots.empty()) // has to kick
1657  {
1658  int_type kicked_slot = m_pager.kick();
1659  m_pager.hit(kicked_slot);
1660  int_type old_page_no = m_slot_to_page[kicked_slot];
1661  m_page_to_slot[page_no] = kicked_slot;
1662  m_page_to_slot[old_page_no] = on_disk;
1663  m_slot_to_page[kicked_slot] = page_no;
1664 
1665  write_page(old_page_no, kicked_slot);
1666  read_page(page_no, kicked_slot);
1667 
1668  m_page_status[page_no] = dirty;
1669 
1670  return (*m_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()];
1671  }
1672  else
1673  {
1674  int_type free_slot = m_free_slots.front();
1675  m_free_slots.pop();
1676  m_pager.hit(free_slot);
1677  m_page_to_slot[page_no] = free_slot;
1678  m_slot_to_page[free_slot] = page_no;
1679 
1680  read_page(page_no, free_slot);
1681 
1682  m_page_status[page_no] = dirty;
1683 
1684  return (*m_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()];
1685  }
1686  }
1687  else
1688  {
1689  m_page_status[page_no] = dirty;
1690  m_pager.hit(cache_slot);
1691  return (*m_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()];
1692  }
1693  }
1694 
1695  // don't forget to first flush() the vector's cache before updating pages externally
1697  {
1698  // fails if offset is too large, out of bound access
1699  assert(page_no < m_page_status.size());
1700  // "A dirty page has been marked as newly initialized. The page content will be lost."
1701  assert(!(m_page_status[page_no] & dirty));
1702  if (m_page_to_slot[page_no] != on_disk) {
1703  // remove page from cache
1704  m_free_slots.push(m_page_to_slot[page_no]);
1705  m_page_to_slot[page_no] = on_disk;
1706  STXXL_VERBOSE_VECTOR("page_externally_updated(): page_no=" << page_no << " flushed from cache.");
1707  }
1708  else {
1709  STXXL_VERBOSE_VECTOR("page_externally_updated(): page_no=" << page_no << " no need to flush.");
1710  }
1711  m_page_status[page_no] = valid_on_disk;
1712  }
1713 
1715  {
1716  page_externally_updated(
1717  (unsigned_type)(offset / (block_type::size * page_size))
1718  );
1719  }
1720 
1722  {
1723  page_externally_updated(offset.get_block2());
1724  }
1725 
1727  {
1728  return const_element(blocked_index_type(offset));
1729  }
1730 
1732  {
1733  unsigned_type page_no = offset.get_block2();
1734  assert(page_no < m_page_to_slot.size()); // fails if offset is too large, out of bound access
1735  int_type cache_slot = m_page_to_slot[page_no];
1736  if (cache_slot < 0) // == on_disk
1737  {
1738  if (m_free_slots.empty()) // has to kick
1739  {
1740  int_type kicked_slot = m_pager.kick();
1741  m_pager.hit(kicked_slot);
1742  int_type old_page_no = m_slot_to_page[kicked_slot];
1743  m_page_to_slot[page_no] = kicked_slot;
1744  m_page_to_slot[old_page_no] = on_disk;
1745  m_slot_to_page[kicked_slot] = page_no;
1746 
1747  write_page(old_page_no, kicked_slot);
1748  read_page(page_no, kicked_slot);
1749 
1750  return (*m_cache)[kicked_slot * page_size + offset.get_block1()][offset.get_offset()];
1751  }
1752  else
1753  {
1754  int_type free_slot = m_free_slots.front();
1755  m_free_slots.pop();
1756  m_pager.hit(free_slot);
1757  m_page_to_slot[page_no] = free_slot;
1758  m_slot_to_page[free_slot] = page_no;
1759 
1760  read_page(page_no, free_slot);
1761 
1762  return (*m_cache)[free_slot * page_size + offset.get_block1()][offset.get_offset()];
1763  }
1764  }
1765  else
1766  {
1767  m_pager.hit(cache_slot);
1768  return (*m_cache)[cache_slot * page_size + offset.get_block1()][offset.get_offset()];
1769  }
1770  }
1771 
1772  bool is_page_cached(const blocked_index_type& offset) const
1773  {
1774  unsigned_type page_no = offset.get_block2();
1775  assert(page_no < m_page_to_slot.size()); // fails if offset is too large, out of bound access
1776  int_type cache_slot = m_page_to_slot[page_no];
1777  return (cache_slot >= 0); // on_disk == -1
1778  }
1779 };
1780 
1781 template <
1782  typename ValueType,
1783  unsigned PageSize,
1784  typename PagerType,
1785  unsigned BlockSize,
1786  typename AllocStr,
1787  typename SizeType>
1788 inline bool operator == (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1789  AllocStr, SizeType>& a,
1790  stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1791  AllocStr, SizeType>& b)
1792 {
1793  return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1794 }
1795 
1796 template <
1797  typename ValueType,
1798  unsigned PageSize,
1799  typename PagerType,
1800  unsigned BlockSize,
1801  typename AllocStr,
1802  typename SizeType>
1803 inline bool operator != (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1804  AllocStr, SizeType>& a,
1805  stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1806  AllocStr, SizeType>& b)
1807 {
1808  return !(a == b);
1809 }
1810 
1811 template <
1812  typename ValueType,
1813  unsigned PageSize,
1814  typename PagerType,
1815  unsigned BlockSize,
1816  typename AllocStr,
1817  typename SizeType>
1818 inline bool operator < (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1819  AllocStr, SizeType>& a,
1820  stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1821  AllocStr, SizeType>& b)
1822 {
1823  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
1824 }
1825 
1826 template <
1827  typename ValueType,
1828  unsigned PageSize,
1829  typename PagerType,
1830  unsigned BlockSize,
1831  typename AllocStr,
1832  typename SizeType>
1833 inline bool operator > (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1834  AllocStr, SizeType>& a,
1835  stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1836  AllocStr, SizeType>& b)
1837 {
1838  return b < a;
1839 }
1840 
1841 template <
1842  typename ValueType,
1843  unsigned PageSize,
1844  typename PagerType,
1845  unsigned BlockSize,
1846  typename AllocStr,
1847  typename SizeType>
1848 inline bool operator <= (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1849  AllocStr, SizeType>& a,
1850  stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1851  AllocStr, SizeType>& b)
1852 {
1853  return !(b < a);
1854 }
1855 
1856 template <
1857  typename ValueType,
1858  unsigned PageSize,
1859  typename PagerType,
1860  unsigned BlockSize,
1861  typename AllocStr,
1862  typename SizeType>
1863 inline bool operator >= (stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1864  AllocStr, SizeType>& a,
1865  stxxl::vector<ValueType, PageSize, PagerType, BlockSize,
1866  AllocStr, SizeType>& b)
1867 {
1868  return !(a < b);
1869 }
1870 
1871 ////////////////////////////////////////////////////////////////////////////
1872 
1873 // specialization for stxxl::vector, to use only const_iterators
1874 template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
1875  unsigned BlockSize, typename PagerType, unsigned PageSize>
1879 {
1880  return stxxl::is_sorted(
1883 }
1884 
1885 template <typename ValueType, typename AllocStr, typename SizeType, typename DiffType,
1886  unsigned BlockSize, typename PagerType, unsigned PageSize, typename StrictWeakOrdering>
1890  StrictWeakOrdering comp)
1891 {
1892  return stxxl::is_sorted(
1895  comp);
1896 }
1897 
1898 ////////////////////////////////////////////////////////////////////////////
1899 
1900 template <typename VectorBufReaderType>
1902 
1903 /*!
1904  * Buffered sequential reader from a vector using overlapped I/O.
1905  *
1906  * This buffered reader can be used to read a large sequential region of a
1907  * vector using overlapped I/O. The object is created from an iterator range,
1908  * which can then be read to using operator<<(), or with operator*() and
1909  * operator++().
1910  *
1911  * The interface also fulfills all requirements of a stream. Actually most of
1912  * the code is identical to stream::vector_iterator2stream.
1913  *
1914  * Note that this buffered reader is inefficient for reading small ranges. This
1915  * is intentional, as one can just use operator[] on the vector for that.
1916  *
1917  * See \ref tutorial_vector_buf
1918  */
1919 template <typename VectorIterator>
1920 class vector_bufreader : public noncopyable
1921 {
1922 public:
1923  //! template parameter: the vector iterator type
1924  typedef VectorIterator vector_iterator;
1925 
1926  //! value type of the output vector
1928 
1929  //! block type used in the vector
1931 
1932  //! type of the input vector
1934 
1935  //! block identifier iterator of the vector
1937 
1938  //! construct output buffered stream used for overlapped reading
1940 
1941  //! construct an iterator for vector_bufreader (for C++11 range-based for loop)
1943 
1944  //! size of remaining data
1946 
1947 protected:
1948  //! iterator to the beginning of the range.
1950 
1951  //! internal "current" iterator into the vector.
1953 
1954  //! iterator to the end of the range.
1956 
1957  //! buffered input stream used to overlapped I/O.
1959 
1960  //! number of blocks to use as buffers.
1962 
1963  //! allow vector_bufreader_iterator to check m_iter against its current value
1965 
1966 public:
1967  //! Create overlapped reader for the given iterator range.
1968  //! \param begin iterator to position were to start reading in vector
1969  //! \param end iterator to position were to end reading in vector
1970  //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
1972  unsigned_type nbuffers = 0)
1973  : m_begin(begin), m_end(end),
1974  m_bufin(NULL),
1975  m_nbuffers(nbuffers)
1976  {
1977  m_begin.flush(); // flush container
1978 
1979  if (m_nbuffers == 0)
1980  m_nbuffers = 2 * config::get_instance()->disks_number();
1981 
1982  rewind();
1983  }
1984 
1985  //! Create overlapped reader for the whole vector's content.
1986  //! \param vec vector to read
1987  //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
1988  vector_bufreader(const vector_type& vec, unsigned_type nbuffers = 0)
1989  : m_begin(vec.begin()), m_end(vec.end()),
1990  m_bufin(NULL),
1991  m_nbuffers(nbuffers)
1992  {
1993  m_begin.flush(); // flush container
1994 
1995  if (m_nbuffers == 0)
1996  m_nbuffers = 2 * config::get_instance()->disks_number();
1997 
1998  rewind();
1999  }
2000 
2001  //! Rewind stream back to begin. Note that this recreates the buffered
2002  //! reader and is thus not cheap.
2003  void rewind()
2004  {
2005  m_iter = m_begin;
2006  if (empty()) return;
2007 
2008  if (m_bufin) delete m_bufin;
2009 
2010  // find last bid to read
2011  bids_container_iterator end_bid = m_end.bid() + (m_end.block_offset() ? 1 : 0);
2012 
2013  // construct buffered istream for range
2014  m_bufin = new buf_istream_type(m_begin.bid(), end_bid, m_nbuffers);
2015 
2016  // skip the beginning of the block, up to real beginning
2017  vector_iterator curr = m_begin - m_begin.block_offset();
2018 
2019  for ( ; curr != m_begin; ++curr)
2020  ++(*m_bufin);
2021  }
2022 
2023  //! Finish reading and free buffered reader.
2025  {
2026  if (m_bufin) delete m_bufin;
2027  }
2028 
2029  //! Return constant reference to current item
2030  const value_type& operator * () const
2031  {
2032  return *(*m_bufin);
2033  }
2034 
2035  //! Return constant pointer to current item
2036  const value_type* operator -> () const
2037  {
2038  return &(*(*m_bufin));
2039  }
2040 
2041  //! Advance to next item (asserts if !empty()).
2043  {
2044  assert(!empty());
2045  ++m_iter;
2046  ++(*m_bufin);
2047 
2048  if (UNLIKELY(empty())) {
2049  delete m_bufin;
2050  m_bufin = NULL;
2051  }
2052 
2053  return *this;
2054  }
2055 
2056  //! Read current item into variable and advance to next one.
2057  vector_bufreader& operator >> (value_type& v)
2058  {
2059  v = operator * ();
2060  operator ++ ();
2061 
2062  return *this;
2063  }
2064 
2065  //! Return remaining size.
2066  size_type size() const
2067  {
2068  assert(m_begin <= m_iter && m_iter <= m_end);
2069  return (size_type)(m_end - m_iter);
2070  }
2071 
2072  //! Returns true once the whole range has been read.
2073  bool empty() const
2074  {
2075  return (m_iter == m_end);
2076  }
2077 
2078  //! Return vector_bufreader_iterator for C++11 range-based for loop
2080  {
2081  return bufreader_iterator(*this, m_begin);
2082  }
2083 
2084  //! Return vector_bufreader_iterator for C++11 range-based for loop
2086  {
2087  return bufreader_iterator(*this, m_end);
2088  }
2089 };
2090 
2091 ////////////////////////////////////////////////////////////////////////////
2092 
2093 /*!
2094  * Adapter for vector_bufreader to match iterator requirements of C++11
2095  * range-based loop construct.
2096  *
2097  * Since vector_bufreader itself points to only one specific item, this
2098  * iterator is merely a counter facade. The functions operator*() and
2099  * operator++() must only be called when it is in _sync_ with the bufreader
2100  * object. This is generally only the case for an iterator constructed with
2101  * begin() and then advanced with operator++(). The class checks this using
2102  * asserts(), the operators will fail if used wrong.
2103  *
2104  * See \ref tutorial_vector_buf
2105  */
2106 template <typename VectorBufReaderType>
2107 class vector_bufreader_iterator
2108 {
2109 public:
2110  //! The underlying buffered reader type
2111  typedef VectorBufReaderType vector_bufreader_type;
2112 
2113  //! Value type of vector
2114  typedef typename vector_bufreader_type::value_type value_type;
2115 
2116  //! Use vector_iterator to reference a point in the vector.
2117  typedef typename vector_bufreader_type::vector_iterator vector_iterator;
2118 
2119 protected:
2120  //! Buffered reader used to access elements in vector
2122 
2123  //! Use vector_iterator to reference a point in the vector.
2125 
2126 public:
2127  //! Construct iterator using vector_iterator
2129  : m_bufreader(bufreader), m_iter(iter)
2130  { }
2131 
2132  //! Return constant reference to current item
2133  const value_type& operator * () const
2134  {
2135  assert(m_bufreader.m_iter == m_iter);
2136  return m_bufreader.operator * ();
2137  }
2138 
2139  //! Return constant pointer to current item
2140  const value_type* operator -> () const
2141  {
2142  assert(m_bufreader.m_iter == m_iter);
2143  return m_bufreader.operator -> ();
2144  }
2145 
2146  //! Make bufreader advance to next item (asserts if !empty() or if iterator
2147  //! does not point to current).
2149  {
2150  assert(m_bufreader.m_iter == m_iter);
2151  m_bufreader.operator ++ ();
2152  m_iter++;
2153  return *this;
2154  }
2155 
2156  //! Equality comparison operator
2158  {
2159  assert(&m_bufreader == &vbi.m_bufreader);
2160  return (m_iter == vbi.m_iter);
2161  }
2162 
2163  //! Inequality comparison operator
2165  {
2166  assert(&m_bufreader == &vbi.m_bufreader);
2167  return (m_iter != vbi.m_iter);
2168  }
2169 };
2170 
2171 ////////////////////////////////////////////////////////////////////////////
2172 
2173 /*!
2174  * Buffered sequential reverse reader from a vector using overlapped I/O.
2175  *
2176  * This buffered reader can be used to read a large sequential region of a
2177  * vector _in_reverse_ using overlapped I/O. The object is created from an
2178  * iterator range, which can then be read to using operator<<(), or with
2179  * operator*() and operator++(), where ++ actually goes to the preceding
2180  * element.
2181  *
2182  * The interface also fulfills all requirements of a stream. Actually most of
2183  * the code is identical to stream::vector_iterator2stream.
2184  *
2185  * Note that this buffered reader is inefficient for reading small ranges. This
2186  * is intentional, as one can just use operator[] on the vector for that.
2187  *
2188  * See \ref tutorial_vector_buf
2189  */
2190 template <typename VectorIterator>
2191 class vector_bufreader_reverse : public noncopyable
2192 {
2193 public:
2194  //! template parameter: the vector iterator type
2195  typedef VectorIterator vector_iterator;
2196 
2197  //! value type of the output vector
2199 
2200  //! block type used in the vector
2202 
2203  //! type of the input vector
2205 
2206  //! block identifier iterator of the vector
2208 
2209  //! construct output buffered stream used for overlapped reading
2211 
2212  //! size of remaining data
2214 
2215 protected:
2216  //! iterator to the beginning of the range.
2218 
2219  //! internal "current" iterator into the vector.
2221 
2222  //! iterator to the end of the range.
2224 
2225  //! buffered input stream used to overlapped I/O.
2227 
2228  //! number of blocks to use as buffers.
2230 
2231 public:
2232  //! Create overlapped reader for the given iterator range.
2233  //! \param begin iterator to position were to start reading in vector
2234  //! \param end iterator to position were to end reading in vector
2235  //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
2237  unsigned_type nbuffers = 0)
2238  : m_begin(begin), m_end(end),
2239  m_bufin(NULL),
2240  m_nbuffers(nbuffers)
2241  {
2242  m_begin.flush(); // flush container
2243 
2244  if (m_nbuffers == 0)
2245  m_nbuffers = 2 * config::get_instance()->disks_number();
2246 
2247  rewind();
2248  }
2249 
2250  //! Create overlapped reader for the whole vector's content.
2251  //! \param vec vector to read
2252  //! \param nbuffers number of buffers used for overlapped I/O (>= 2*D recommended)
2254  : m_begin(vec.begin()), m_end(vec.end()),
2255  m_bufin(NULL),
2256  m_nbuffers(nbuffers)
2257  {
2258  m_begin.flush(); // flush container
2259 
2260  if (m_nbuffers == 0)
2261  m_nbuffers = 2 * config::get_instance()->disks_number();
2262 
2263  rewind();
2264  }
2265 
2266  //! Rewind stream back to begin. Note that this recreates the buffered
2267  //! reader and is thus not cheap.
2268  void rewind()
2269  {
2270  m_iter = m_end;
2271  if (empty()) return;
2272 
2273  if (m_bufin) delete m_bufin;
2274 
2275  // find last bid to read
2276  bids_container_iterator end_bid = m_end.bid() + (m_end.block_offset() ? 1 : 0);
2277 
2278  // construct buffered istream_reverse for range
2279  m_bufin = new buf_istream_type(m_begin.bid(), end_bid, m_nbuffers);
2280 
2281  // skip to beginning of reverse sequence.
2282  stxxl::int_type endoff = m_end.block_offset();
2283  if (endoff == 0) {
2284  // nothing to skip
2285  }
2286  else {
2287  // else, let ifstream_reverse skip last elements at end of block,
2288  // up to real end
2289  for ( ; endoff != block_type::size; endoff++)
2290  ++(*m_bufin);
2291  }
2292  }
2293 
2294  //! Finish reading and free buffered reader.
2296  {
2297  if (m_bufin) delete m_bufin;
2298  }
2299 
2300  //! Return constant reference to current item
2301  const value_type& operator * () const
2302  {
2303  return *(*m_bufin);
2304  }
2305 
2306  //! Return constant pointer to current item
2307  const value_type* operator -> () const
2308  {
2309  return &(*(*m_bufin));
2310  }
2311 
2312  //! Advance to next item (asserts if !empty()).
2314  {
2315  assert(!empty());
2316  --m_iter;
2317  ++(*m_bufin);
2318 
2319  if (UNLIKELY(empty())) {
2320  delete m_bufin;
2321  m_bufin = NULL;
2322  }
2323 
2324  return *this;
2325  }
2326 
2327  //! Read current item into variable and advance to next one.
2329  {
2330  v = operator * ();
2331  operator ++ ();
2332 
2333  return *this;
2334  }
2335 
2336  //! Return remaining size.
2337  size_type size() const
2338  {
2339  assert(m_begin <= m_iter && m_iter <= m_end);
2340  return (size_type)(m_iter - m_begin);
2341  }
2342 
2343  //! Returns true once the whole range has been read.
2344  bool empty() const
2345  {
2346  return (m_iter == m_begin);
2347  }
2348 };
2349 
2350 ////////////////////////////////////////////////////////////////////////////
2351 
2352 /*!
2353  * Buffered sequential writer to a vector using overlapped I/O.
2354  *
2355  * This buffered writer can be used to write a large sequential region of a
2356  * vector using overlapped I/O. The object is created from an iterator range,
2357  * which can then be written to using operator << (), or with operator * () and
2358  * operator ++ ().
2359  *
2360  * The buffered writer is given one iterator in the constructor. When writing,
2361  * this iterator advances in the vector and will \b enlarge the vector once it
2362  * reaches the end(). The vector size is doubled each time; nevertheless, it is
2363  * better to preinitialize the vector's size using stxxl::vector::resize().
2364  *
2365  * See \ref tutorial_vector_buf
2366  */
2367 template <typename VectorIterator>
2368 class vector_bufwriter : public noncopyable
2369 {
2370 public:
2371  //! template parameter: the vector iterator type
2372  typedef VectorIterator iterator;
2373 
2374  //! type of the output vector
2375  typedef typename iterator::vector_type vector_type;
2376 
2377  //! value type of the output vector
2378  typedef typename iterator::value_type value_type;
2379 
2380  //! block type used in the vector
2381  typedef typename iterator::block_type block_type;
2382 
2383  //! block identifier iterator of the vector
2384  typedef typename iterator::bids_container_iterator bids_container_iterator;
2385 
2386  //! iterator type of vector
2387  typedef typename iterator::iterator vector_iterator;
2388  typedef typename iterator::const_iterator vector_const_iterator;
2389 
2390  //! construct output buffered stream used for overlapped writing
2392 
2393 protected:
2394  //! internal iterator into the vector.
2396 
2397  //! iterator to the current end of the vector.
2399 
2400  //! boolean whether the vector was grown, will shorten at finish().
2401  bool m_grown;
2402 
2403  //! iterator into vector of the last block accessed (used to issue updates
2404  //! when the block is switched).
2406 
2407  //! buffered output stream used to overlapped I/O.
2409 
2410  //! number of blocks to use as buffers.
2412 
2413 public:
2414  //! Create overlapped writer beginning at the given iterator.
2415  //! \param begin iterator to position were to start writing in vector
2416  //! \param nbuffers number of buffers used for overlapped I/O (>= 2D recommended)
2418  unsigned_type nbuffers = 0)
2419  : m_iter(begin),
2420  m_end(m_iter.parent_vector()->end()),
2421  m_grown(false),
2422  m_bufout(NULL),
2423  m_nbuffers(nbuffers)
2424  {
2425  if (m_nbuffers == 0)
2426  m_nbuffers = 2 * config::get_instance()->disks_number();
2427 
2428  assert(m_iter <= m_end);
2429  }
2430 
2431  //! Create overlapped writer for the vector's beginning
2432  //! \param vec vector to write
2433  //! \param nbuffers number of buffers used for overlapped I/O (>= 2D recommended)
2435  unsigned_type nbuffers = 0)
2436  : m_iter(vec.begin()),
2437  m_end(m_iter.parent_vector()->end()),
2438  m_grown(false),
2439  m_bufout(NULL),
2440  m_nbuffers(nbuffers)
2441  {
2442  if (m_nbuffers == 0)
2443  m_nbuffers = 2 * config::get_instance()->disks_number();
2444 
2445  assert(m_iter <= m_end);
2446  }
2447 
2448  //! Finish writing and flush output back to vector.
2450  {
2451  finish();
2452  }
2453 
2454  //! Return mutable reference to item at the position of the internal
2455  //! iterator.
2456  value_type& operator * ()
2457  {
2458  if (UNLIKELY(m_iter == m_end))
2459  {
2460  // iterator points to end of vector -> double vector's size
2461 
2462  if (m_bufout) {
2463  // fixes issue with buf_ostream writing invalid blocks: when
2464  // buf_ostream::current_elem advances to next block, flush()
2465  // will write to block beyond bid().end.
2466  if (m_iter.block_offset() != 0)
2467  m_bufout->flush(); // flushes overlap buffers
2468 
2469  delete m_bufout;
2470  m_bufout = NULL;
2471 
2472  if (m_iter.block_offset() != 0)
2473  m_iter.block_externally_updated();
2474  }
2475 
2476  vector_type& v = *m_iter.parent_vector();
2477  if (v.size() < 2 * block_type::size) {
2478  v.resize(2 * block_type::size);
2479  }
2480  else {
2481  v.resize(2 * v.size());
2482  }
2483  m_end = v.end();
2484  m_grown = true;
2485  }
2486 
2487  assert(m_iter < m_end);
2488 
2489  if (UNLIKELY(m_bufout == NULL))
2490  {
2491  if (m_iter.block_offset() != 0)
2492  {
2493  // output position is not at the start of the block, we
2494  // continue to use the iterator initially passed to the
2495  // constructor.
2496  return *m_iter;
2497  }
2498  else
2499  {
2500  // output position is start of block: create buffered writer
2501 
2502  m_iter.flush(); // flush container
2503 
2504  // create buffered write stream for blocks
2505  m_bufout = new buf_ostream_type(m_iter.bid(), m_nbuffers);
2506  m_prevblk = m_iter;
2507 
2508  // drop through to normal output into buffered writer
2509  }
2510  }
2511 
2512  // if the pointer has finished a block, then we inform the vector that
2513  // this block has been updated.
2514  if (UNLIKELY(m_iter.block_offset() == 0)) {
2515  if (m_prevblk != m_iter) {
2516  m_prevblk.block_externally_updated();
2517  m_prevblk = m_iter;
2518  }
2519  }
2520 
2521  return m_bufout->operator * ();
2522  }
2523 
2524  //! Advance internal iterator.
2526  {
2527  // always advance internal iterator
2528  ++m_iter;
2529 
2530  // if buf_ostream active, advance that too
2531  if (LIKELY(m_bufout != NULL)) m_bufout->operator ++ ();
2532 
2533  return *this;
2534  }
2535 
2536  //! Write value to the current position and advance the internal iterator.
2538  {
2539  operator * () = v;
2540  operator ++ ();
2541 
2542  return *this;
2543  }
2544 
2545  //! Finish writing and flush output back to vector.
2546  void finish()
2547  {
2548  if (m_bufout)
2549  {
2550  // must finish the block started in the buffered writer: fill it with
2551  // the data in the vector
2552  vector_const_iterator const_out = m_iter;
2553 
2554  while (const_out.block_offset() != 0)
2555  {
2556  m_bufout->operator * () = *const_out;
2557  m_bufout->operator ++ ();
2558  ++const_out;
2559  }
2560 
2561  // inform the vector that the block has been updated.
2562  if (m_prevblk != m_iter) {
2563  m_prevblk.block_externally_updated();
2564  m_prevblk = m_iter;
2565  }
2566 
2567  delete m_bufout;
2568  m_bufout = NULL;
2569  }
2570 
2571  if (m_grown)
2572  {
2573  vector_type& v = *m_iter.parent_vector();
2574  v.resize(m_iter - v.begin());
2575 
2576  m_grown = false;
2577  }
2578  }
2579 };
2580 
2581 ////////////////////////////////////////////////////////////////////////////
2582 
2583 //! External vector type generator.
2584 //!
2585 //! \tparam ValueType element type of contained objects (POD with no references to internal memory)
2586 //! \tparam PageSize number of blocks in a page, default: \b 4 (recommended >= D)
2587 //! \tparam CachePages number of pages in cache, default: \b 8 (recommended >= 2)
2588 //! \tparam BlockSize external block size \a B in bytes, default: <b>2 MiB</b>
2589 //! \tparam AllocStr parallel disk allocation strategies: \c striping, RC, SR, or FR. default: \b RC.
2590 //! \tparam Pager pager type: \c random or \c lru, default: \b lru.
2591 //!
2592 //! \warning Do not store references to the elements of an external vector. Such references
2593 //! might be invalidated during any following access to elements of the vector
2594 template <
2595  typename ValueType,
2596  unsigned PageSize = 4,
2597  unsigned CachePages = 8,
2598  unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
2599  typename AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY,
2600  pager_type Pager = lru
2601  >
2603 {
2604  typedef typename IF<Pager == lru,
2606 
2608 };
2609 
2610 //! \}
2611 
2613 
2614 namespace std {
2615 
2616 template <
2617  typename ValueType,
2618  unsigned PageSize,
2619  typename PagerType,
2620  unsigned BlockSize,
2621  typename AllocStr,
2622  typename SizeType>
2625 {
2626  a.swap(b);
2627 }
2628 
2629 } // namespace std
2630 
2631 #endif // !STXXL_CONTAINERS_VECTOR_HEADER
2632 // vim: et:ts=4:sw=4
vector_bufreader< const_iterator > bufreader_type
vector_bufreader compatible with this vector
Definition: vector.h:878
vector_type::reference reference
Definition: vector.h:306
vector_iterator m_end
iterator to the end of the range.
Definition: vector.h:1955
vector_bufreader_reverse(vector_iterator begin, vector_iterator end, unsigned_type nbuffers=0)
Create overlapped reader for the given iterator range.
Definition: vector.h:2236
const_reverse_iterator crbegin() const
returns a reverse_iterator pointing to the end of the vector.
Definition: vector.h:1384
block_manager * m_bm
Definition: vector.h:921
bids_container_type::bid_type bid_type
Definition: vector.h:298
Const external vector iterator, model of ext_random_access_iterator concept.
Definition: vector.h:259
vector_iterator()
constructs invalid iterator
Definition: vector.h:325
size_type size() const
Return remaining size.
Definition: vector.h:2066
void _resize(size_type n)
Resize vector, only allow capacity growth.
Definition: vector.h:1112
void read_page(int_type page_no, int_type cache_slot) const
Definition: vector.h:1599
size_type capacity() const
Return the number of elelemtsn for which external memory has been allocated. capacity() is always gre...
Definition: vector.h:1039
compat::remove_const< Integral >::type div_ceil(Integral n, Integral2 d)
Definition: utils.h:199
#define STXXL_DEFAULT_BLOCK_SIZE(type)
virtual void set_size(offset_type newsize)=0
Changes the size of the file.
std::random_access_iterator_tag iterator_category
Definition: vector.h:302
bids_container_iterator bid(const size_type &offset)
Definition: vector.h:1574
value_type & reference
reference to value_type
Definition: vector.h:837
bool empty() const
true if the vector&#39;s size is zero.
Definition: vector.h:1032
~vector_bufreader_reverse()
Finish reading and free buffered reader.
Definition: vector.h:2295
#define LIKELY(c)
Definition: utils.h:219
friend std::ostream & operator<<(std::ostream &os, const uint_pair &a)
make a uint_pair outputtable via iostreams, using unsigned long long.
Definition: uint_types.h:228
iterator::vector_type vector_type
type of the output vector
Definition: vector.h:2375
vector< ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType > vector_type
Definition: vector.h:294
vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > mutable_self_type
Definition: vector.h:557
std::vector< unsigned char > m_page_status
status of each page (valid_on_disk, uninitialized or dirty)
Definition: vector.h:915
std::vector< BID< block_size > > super_type
Definition: vector.h:887
Buffered sequential reverse reader from a vector using overlapped I/O.
Definition: vector.h:265
const Type & STXXL_MIN(const Type &a, const Type &b)
Definition: utils.h:146
~vector_bufwriter()
Finish writing and flush output back to vector.
Definition: vector.h:2449
vector_iterator::bids_container_iterator bids_container_iterator
block identifier iterator of the vector
Definition: vector.h:1936
vector_iterator::value_type value_type
value type of the output vector
Definition: vector.h:2198
Block manager class.
Definition: block_manager.h:61
iterator end()
returns an iterator pointing beyond the end of the vector, see More Notes.
Definition: vector.h:1358
const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > self_type
Definition: vector.h:554
void export_files(std::string filename_prefix)
Export data such that it is persistent on the file system. Resulting files will be numbered ascending...
Definition: vector.h:1524
file * get_file() const
Get the file associated with this vector, or NULL.
Definition: vector.h:1541
long long int int64
Definition: types.h:38
vector_iterator::block_type block_type
block type used in the vector
Definition: vector.h:2201
super_type::size_type size_type
Definition: vector.h:888
vector_iterator m_begin
iterator to the beginning of the range.
Definition: vector.h:1949
#define STXXL_VERBOSE_VECTOR(msg)
Definition: vector.h:36
void clear()
Erases all of the elements and deallocates all external memory that is occupied.
Definition: vector.h:1174
block_offset_type block_offset() const
return block offset of current element
Definition: vector.h:622
unsigned long long int uint64
Definition: types.h:39
vector_type::blocked_index_type blocked_index_type
Definition: vector.h:300
iterator::iterator vector_iterator
iterator type of vector
Definition: vector.h:2387
ValueType value_type
The type of elements stored in the vector.
Definition: vector.h:835
const value_type & const_reference
constant reference to value_type
Definition: vector.h:839
vector_bufreader(vector_iterator begin, vector_iterator end, unsigned_type nbuffers=0)
Create overlapped reader for the given iterator range.
Definition: vector.h:1971
void rewind()
Rewind stream back to begin. Note that this recreates the buffered reader and is thus not cheap...
Definition: vector.h:2268
const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > const_self_type
Definition: vector.h:281
vector_iterator::vector_type vector_type
type of the input vector
Definition: vector.h:2204
const vector_type * p_vector
Definition: vector.h:591
vector_iterator m_iter
Use vector_iterator to reference a point in the vector.
Definition: vector.h:2124
vector_bufreader_reverse(const vector_type &vec, unsigned_type nbuffers=0)
Create overlapped reader for the whole vector&#39;s content.
Definition: vector.h:2253
reverse_iterator rend()
returns a reverse_iterator pointing beyond the beginning of the vector.
Definition: vector.h:1389
vector(file *from, size_type size=size_type(-1), unsigned_type npages=pager_type().size())
Construct vector from a file.
Definition: vector.h:1244
const_iterator end() const
returns a const_iterator pointing beyond the end of the vector, see More Notes.
Definition: vector.h:1363
Buffered sequential writer to a vector using overlapped I/O.
Definition: vector.h:268
bids_container_type m_bids
Definition: vector.h:909
const_reference at(size_type offset) const
access the element at the given vector&#39;s offset
Definition: vector.h:1427
file * m_from
Definition: vector.h:920
#define STXXL_DEFAULT_ALLOC_STRATEGY
Definition: block_alloc.h:258
iterator::block_type block_type
block type used in the vector
Definition: vector.h:2381
Adapter for vector_bufreader to match iterator requirements of C++11 range-based loop construct...
Definition: vector.h:1901
vector_iterator m_iter
internal &quot;current&quot; iterator into the vector.
Definition: vector.h:2220
vector_type::size_type size_type
size of remaining data
Definition: vector.h:2213
const unsigned_type & get_block1() const
Definition: vector.h:235
size_type size() const
return the size of the vector.
Definition: vector.h:1027
vector_type::size_type size_type
Definition: vector.h:579
Buffered sequential reader from a vector using overlapped I/O.
Definition: vector.h:262
vector_bufreader(const vector_type &vec, unsigned_type nbuffers=0)
Create overlapped reader for the whole vector&#39;s content.
Definition: vector.h:1988
const_iterator cend() const
returns a const_iterator pointing beyond the end of the vector, see More Notes.
Definition: vector.h:1368
External vector container. Introduction to vector container: see STXXL Vector tutorial. Design and Internals of vector container: see Vector.
Definition: vector.h:255
std::reverse_iterator< iterator > reverse_iterator
Definition: vector.h:866
vector(size_type n=0, unsigned_type npages=pager_type().size())
Constructs external vector with n elements.
Definition: vector.h:953
Buffered output stream.
Definition: buf_ostream.h:29
unsigned_type m_nbuffers
number of blocks to use as buffers.
Definition: vector.h:2411
Pager with random replacement strategy.
Definition: pager.h:37
bool is_page_cached(const blocked_index_type &offset) const
Definition: vector.h:1772
bool empty() const
Returns true once the whole range has been read.
Definition: vector.h:2073
vector_iterator::vector_type vector_type
type of the input vector
Definition: vector.h:1933
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
bids_container_type::const_iterator const_bids_container_iterator
Definition: vector.h:897
vector< ValueType, PageSize, PagerType, BlockSize, AllocStr, SizeType > vector_type
Definition: vector.h:570
const unsigned_type & get_offset() const
Definition: vector.h:240
std::random_access_iterator_tag iterator_category
Definition: vector.h:578
void reserve(size_type n)
Reserves at least n elements in external memory.
Definition: vector.h:1057
size_type get_pos() const
Definition: vector.h:225
iterator::value_type value_type
value type of the output vector
Definition: vector.h:2378
vector_bufwriter< iterator > bufwriter_type
vector_bufwriter compatible with this vector
Definition: vector.h:875
vector_type * parent_vector() const
return pointer to vector containing iterator
Definition: vector.h:338
std::vector< int_type > m_page_to_slot
Definition: vector.h:916
const_reference const_element(const blocked_index_type &offset) const
Definition: vector.h:1731
vector_iterator< value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size > iterator
iterator used to iterate through a vector, see More Notes.
Definition: vector.h:859
void resize(size_type n)
Resize vector contents to n items.
Definition: vector.h:1092
static long long curr
vector_type::size_type size_type
size of remaining data
Definition: vector.h:1945
void page_externally_updated(unsigned_type page_no) const
Definition: vector.h:1696
vector_type::blocked_index_type blocked_index_type
Definition: vector.h:576
void pop_back()
Removes the last element (without returning it, see back()).
Definition: vector.h:1201
vector_type::const_pointer pointer
Definition: vector.h:584
bids_container_type::bid_type bid_type
Definition: vector.h:574
vector_const_iterator m_end
iterator to the current end of the vector.
Definition: vector.h:2398
void resize(size_type n, bool shrink_capacity)
Resize vector contents to n items, and allow the allocated external memory to shrink. Internal memory allocation remains unchanged.
Definition: vector.h:1100
vector_type::const_reference const_reference
Definition: vector.h:307
bids_container_type::iterator bids_container_iterator
Definition: vector.h:573
vector(const vector &obj)
copy-constructor
Definition: vector.h:1289
void allocate_page_cache() const
Allocate page cache, must be called to allow access to elements.
Definition: vector.h:1007
const_vector_iterator()
constructs invalid iterator
Definition: vector.h:601
void block_externally_updated(const blocked_index_type &offset) const
Definition: vector.h:1721
const_bids_container_iterator bid(const blocked_index_type &offset) const
Definition: vector.h:1592
const vector_type * parent_vector() const
return pointer to vector containing iterator
Definition: vector.h:617
uint_pair & operator+=(const uint_pair &b)
addition operator (uses 64-bit arithmetic)
Definition: uint_types.h:183
vector_iterator(vector_type *v, size_type o)
private constructor for initializing other iterators
Definition: vector.h:319
iterator begin()
returns an iterator pointing to the beginning of the vector, see More Notes.
Definition: vector.h:1343
typed_block< BlockSize, ValueType > block_type
type of the block used in disk-memory transfers
Definition: vector.h:900
const_reverse_iterator rbegin() const
returns a reverse_iterator pointing to the end of the vector.
Definition: vector.h:1379
double_blocked_index< SizeType, PageSize, block_type::size > blocked_index_type
double-index type to reference individual elements in a block
Definition: vector.h:902
Block containing elements of fixed length.
Definition: typed_block.h:237
reverse_iterator rbegin()
returns a reverse_iterator pointing to the end of the vector.
Definition: vector.h:1374
unsigned block_offset_type
Definition: vector.h:293
size_type m_size
Definition: vector.h:908
VectorIterator iterator
template parameter: the vector iterator type
Definition: vector.h:2372
~vector_bufreader()
Finish reading and free buffered reader.
Definition: vector.h:2024
Defines interface of file.
Definition: file.h:56
pager_type m_pager
Definition: vector.h:910
void deallocate_page_cache() const
allows to free the cache, but you may not access any element until call allocate_page_cache() again ...
Definition: vector.h:1016
bufreader_iterator end()
Return vector_bufreader_iterator for C++11 range-based for loop.
Definition: vector.h:2085
vector_type::pointer pointer
Definition: vector.h:308
vector_iterator m_iter
internal &quot;current&quot; iterator into the vector.
Definition: vector.h:1952
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.h:198
bid_vector(size_type sz)
Definition: vector.h:891
bool operator<=(const uint_pair &b) const
less-or-equal comparison operator
Definition: uint_types.h:210
vector_type::size_type size_type
Definition: vector.h:303
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
bool operator>(const uint_pair &b) const
greater comparison operator
Definition: uint_types.h:216
vector_type::block_type block_type
Definition: vector.h:575
iterator::const_iterator vector_const_iterator
Definition: vector.h:2388
const value_type * const_pointer
constant pointer to value_type
Definition: vector.h:843
size_type raw_capacity() const
Returns the number of bytes that the vector has allocated on disks.
Definition: vector.h:1044
blocked_index_type offset
Definition: vector.h:314
super_type::value_type bid_type
Definition: vector.h:889
Buffered input stream, reading the items in the blocks in reverse order.
vector_type::bids_container_type bids_container_type
Definition: vector.h:572
#define UNLIKELY(c)
Definition: utils.h:225
vector_type::bids_container_type bids_container_type
Definition: vector.h:296
alloc_strategy_type m_alloc_strategy
Definition: vector.h:907
unsigned_type numpages() const
Number of pages used by the pager.
Definition: vector.h:1566
vector_type * p_vector
Definition: vector.h:315
bool operator>=(const uint_pair &b) const
greater-or-equal comparison operator
Definition: uint_types.h:222
pager_type
Definition: pager.h:29
const_reverse_iterator crend() const
returns a reverse_iterator pointing beyond the beginning of the vector.
Definition: vector.h:1399
void rewind()
Rewind stream back to begin. Note that this recreates the buffered reader and is thus not cheap...
Definition: vector.h:2003
vector_type::value_type value_type
Definition: vector.h:581
bool operator<(const uint_pair &b) const
less-than comparison operator
Definition: uint_types.h:204
vector_type::difference_type difference_type
Definition: vector.h:580
buf_ostream_type * m_bufout
buffered output stream used to overlapped I/O.
Definition: vector.h:2408
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
vector_iterator::bids_container_iterator bids_container_iterator
block identifier iterator of the vector
Definition: vector.h:2207
bids_container_type::iterator bids_container_iterator
Definition: vector.h:297
mutable_self_type iterator
Definition: vector.h:567
vector_bufwriter(vector_iterator begin, unsigned_type nbuffers=0)
Create overlapped writer beginning at the given iterator.
Definition: vector.h:2417
const_vector_iterator(const mutable_self_type &a)
copy-constructor from mutable iterator
Definition: vector.h:609
uint_pair & operator--()
prefix decrement operator (directly manipulates the integer parts)
Definition: uint_types.h:173
bids_container_type::iterator bids_container_iterator
Definition: vector.h:896
Buffered input stream.
Definition: buf_istream.h:34
vector_type::difference_type difference_type
Definition: vector.h:304
bids_container_iterator bid() const
return iterator to BID containg current element
Definition: vector.h:627
vector_bufreader_reverse< const_iterator > bufreader_reverse_type
vector_bufreader compatible with this vector
Definition: vector.h:881
vector_iterator::value_type value_type
value type of the output vector
Definition: vector.h:1927
AllocStr alloc_strategy_type
Definition: vector.h:849
reference element(size_type offset)
Definition: vector.h:1638
void push_back(const_reference obj)
Append a new element at the end.
Definition: vector.h:1194
bufreader_iterator begin()
Return vector_bufreader_iterator for C++11 range-based for loop.
Definition: vector.h:2079
double_blocked_index(size_type pos)
Definition: vector.h:78
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)
Definition: is_sorted.h:24
vector_type::const_reference reference
Definition: vector.h:582
External vector iterator, model of ext_random_access_iterator concept.
Definition: vector.h:275
vector_iterator m_begin
iterator to the beginning of the range.
Definition: vector.h:2217
value_type * pointer
pointer to value_type
Definition: vector.h:841
vector_bufreader_type & m_bufreader
Buffered reader used to access elements in vector.
Definition: vector.h:2121
buf_istream< block_type, bids_container_iterator > buf_istream_type
construct output buffered stream used for overlapped reading
Definition: vector.h:1939
buf_istream_type * m_bufin
buffered input stream used to overlapped I/O.
Definition: vector.h:2226
vector_iterator(const self_type &a)
copy-constructor
Definition: vector.h:329
stxxl::int64 difference_type
Definition: vector.h:846
void set(size_type pos)
Definition: vector.h:59
unsigned_type m_nbuffers
number of blocks to use as buffers.
Definition: vector.h:1961
buf_ostream< block_type, bids_container_iterator > buf_ostream_type
construct output buffered stream used for overlapped writing
Definition: vector.h:2391
VectorBufReaderType vector_bufreader_type
The underlying buffered reader type.
Definition: vector.h:2111
PagerType pager_type
Definition: vector.h:848
vector_iterator m_end
iterator to the end of the range.
Definition: vector.h:2223
blocked_index_type offset
Definition: vector.h:590
bids_container_iterator bid() const
return iterator to BID containg current element
Definition: vector.h:348
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
vector_bufreader_iterator(vector_bufreader_type &bufreader, const vector_iterator &iter)
Construct iterator using vector_iterator.
Definition: vector.h:2128
const_vector_iterator< value_type, alloc_strategy_type, size_type, difference_type, block_size, pager_type, page_size > const_iterator
constant iterator used to iterate through a vector, see More Notes.
Definition: vector.h:864
double_blocked_index(unsigned_type block2, unsigned_type block1, unsigned_type offset)
Definition: vector.h:83
vector_type::const_reference const_reference
Definition: vector.h:583
bids_container_iterator bid(const blocked_index_type &offset)
Definition: vector.h:1580
Pager with LRU replacement strategy.
Definition: pager.h:66
iterator::bids_container_iterator bids_container_iterator
block identifier iterator of the vector
Definition: vector.h:2384
void write_page(int_type page_no, int_type cache_slot) const
Definition: vector.h:1617
void wait_all(RequestIterator reqs_begin, RequestIterator reqs_end)
Collection of functions to track statuses of a number of requests.
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
block_offset_type block_offset() const
return block offset of current element
Definition: vector.h:343
self_type iterator
Definition: vector.h:290
bool m_exported
Definition: vector.h:922
unsigned_type offset
Definition: vector.h:55
bool empty() const
Returns true once the whole range has been read.
Definition: vector.h:2344
const_reference back() const
Returns a constant reference to the last element, see More Notes.
Definition: vector.h:1222
reference at(size_type offset)
access the element at the given vector&#39;s offset
Definition: vector.h:1421
IF< Pager==lru, lru_pager< CachePages >, random_pager< CachePages > >::result PagerType
Definition: vector.h:2605
void _resize_shrink_capacity(size_type n)
Resize vector, also allow reduction of external memory capacity.
Definition: vector.h:1130
vector_iterator::block_type block_type
block type used in the vector
Definition: vector.h:1930
SizeType size_type
an unsigned 64-bit integral type
Definition: vector.h:845
void finish()
Finish writing and flush output back to vector.
Definition: vector.h:2546
vector_type::block_type block_type
Definition: vector.h:299
vector_bufreader_type::value_type value_type
Value type of vector.
Definition: vector.h:2114
vector< ValueType, PageSize, PagerType, BlockSize, AllocStr > result
Definition: vector.h:2607
size_type size() const
Return remaining size.
Definition: vector.h:2337
const_reference const_element(size_type offset) const
Definition: vector.h:1726
const_reverse_iterator rend() const
returns a reverse_iterator pointing beyond the beginning of the vector.
Definition: vector.h:1394
IF template metaprogramming statement.
Definition: tmeta.h:30
const_iterator cbegin() const
returns a const_iterator pointing to the beginning of the vector, see More Notes. ...
Definition: vector.h:1353
void block_externally_updated()
Definition: vector.h:533
const_self_type const_iterator
Definition: vector.h:291
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: vector.h:867
VectorIterator vector_iterator
template parameter: the vector iterator type
Definition: vector.h:2195
vector_type::const_pointer const_pointer
Definition: vector.h:309
bid_vector bids_container_type
Definition: vector.h:895
const_vector_iterator(const self_type &a)
copy-constructor
Definition: vector.h:605
vector_bufwriter(vector_type &vec, unsigned_type nbuffers=0)
Create overlapped writer for the vector&#39;s beginning.
Definition: vector.h:2434
VectorIterator vector_iterator
template parameter: the vector iterator type
Definition: vector.h:1924
stxxl::uint64 file_length() const
Definition: vector.h:932
void set_content(const ForwardIterator &bid_begin, const ForwardIterator &bid_end, size_type n)
Set the blocks and the size of this container explicitly. The vector must be completely empty before...
Definition: vector.h:1554
std::queue< int_type > m_free_slots
Definition: vector.h:918
bool is_element_cached(size_type offset) const
return true if the given vector offset is in cache
Definition: vector.h:1434
buf_istream_reverse< block_type, bids_container_iterator > buf_istream_type
construct output buffered stream used for overlapped reading
Definition: vector.h:2210
vector_bufreader_iterator< vector_bufreader > bufreader_iterator
construct an iterator for vector_bufreader (for C++11 range-based for loop)
Definition: vector.h:1942
unsigned_type m_nbuffers
number of blocks to use as buffers.
Definition: vector.h:2229
void block_externally_updated(size_type offset) const
Definition: vector.h:1714
const_vector_iterator(const vector_type *v, size_type o)
private constructor for initializing other iterators
Definition: vector.h:595
vector_type::value_type value_type
Definition: vector.h:305
size_type size_from_file_length(stxxl::uint64 file_length) const
Definition: vector.h:924
reference element(const blocked_index_type &offset)
Definition: vector.h:1646
vector_iterator m_iter
internal iterator into the vector.
Definition: vector.h:2395
External vector type generator.
Definition: vector.h:2602
simple_vector< int_type > m_slot_to_page
Definition: vector.h:917
const_bids_container_iterator bid(const size_type &offset) const
Definition: vector.h:1586
reference back()
Returns a reference to the last element, see More Notes.
Definition: vector.h:1212
bool m_grown
boolean whether the vector was grown, will shorten at finish().
Definition: vector.h:2401
void flush() const
Flushes the cache pages to the external memory.
Definition: vector.h:1445
vector_type::const_pointer const_pointer
Definition: vector.h:585
const unsigned_type & get_block2() const
Definition: vector.h:230
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.h:192
vector_const_iterator m_prevblk
iterator into vector of the last block accessed (used to issue updates when the block is switched)...
Definition: vector.h:2405
reference front()
Returns a reference to the first element, see More Notes.
Definition: vector.h:1217
const_reference front() const
Returns a constant reference to the first element, see More Notes.
Definition: vector.h:1227
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
simple_vector< block_type > * m_cache
Definition: vector.h:919
const_iterator begin() const
returns a const_iterator pointing to the beginning of the vector, see More Notes. ...
Definition: vector.h:1348
vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > self_type
Definition: vector.h:278
vector_bufreader_type::vector_iterator vector_iterator
Use vector_iterator to reference a point in the vector.
Definition: vector.h:2117
buf_istream_type * m_bufin
buffered input stream used to overlapped I/O.
Definition: vector.h:1958
void swap(vector &obj)
swap content
Definition: vector.h:986