1// Debugging vector implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 3, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file debug/vector
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_VECTOR
31#define _GLIBCXX_DEBUG_VECTOR 1
32
33#include <vector>
34#include <utility>
35#include <debug/safe_sequence.h>
36#include <debug/safe_iterator.h>
37
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40namespace __debug
41{
42  /// Class std::vector with safety/checking/debug instrumentation.
43  template<typename _Tp,
44	   typename _Allocator = std::allocator<_Tp> >
45    class vector
46    : public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
47      public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
48    {
49      typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
50
51      typedef typename _Base::iterator _Base_iterator;
52      typedef typename _Base::const_iterator _Base_const_iterator;
53      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
54
55#ifdef __GXX_EXPERIMENTAL_CXX0X__
56      typedef __gnu_cxx::__alloc_traits<_Allocator>  _Alloc_traits;
57#endif
58
59    public:
60      typedef typename _Base::reference             reference;
61      typedef typename _Base::const_reference       const_reference;
62
63      typedef __gnu_debug::_Safe_iterator<_Base_iterator,vector>
64      iterator;
65      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,vector>
66      const_iterator;
67
68      typedef typename _Base::size_type             size_type;
69      typedef typename _Base::difference_type       difference_type;
70
71      typedef _Tp				    value_type;
72      typedef _Allocator			    allocator_type;
73      typedef typename _Base::pointer               pointer;
74      typedef typename _Base::const_pointer         const_pointer;
75      typedef std::reverse_iterator<iterator>       reverse_iterator;
76      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
77
78      // 23.2.4.1 construct/copy/destroy:
79      explicit
80      vector(const _Allocator& __a = _Allocator())
81      : _Base(__a), _M_guaranteed_capacity(0) { }
82
83#ifdef __GXX_EXPERIMENTAL_CXX0X__
84      explicit
85      vector(size_type __n)
86      : _Base(__n), _M_guaranteed_capacity(__n) { }
87
88      vector(size_type __n, const _Tp& __value,
89	     const _Allocator& __a = _Allocator())
90      : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
91#else
92      explicit
93      vector(size_type __n, const _Tp& __value = _Tp(),
94	     const _Allocator& __a = _Allocator())
95      : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
96#endif
97
98      template<class _InputIterator>
99        vector(_InputIterator __first, _InputIterator __last,
100	       const _Allocator& __a = _Allocator())
101        : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
102								     __last)),
103		__gnu_debug::__base(__last), __a),
104	  _M_guaranteed_capacity(0)
105        { _M_update_guaranteed_capacity(); }
106
107      vector(const vector& __x)
108      : _Base(__x), _M_guaranteed_capacity(__x.size()) { }
109
110      /// Construction from a release-mode vector
111      vector(const _Base& __x)
112      : _Base(__x), _M_guaranteed_capacity(__x.size()) { }
113
114#ifdef __GXX_EXPERIMENTAL_CXX0X__
115      vector(vector&& __x) noexcept
116      : _Base(std::move(__x)),
117	_M_guaranteed_capacity(this->size())
118      {
119	this->_M_swap(__x);
120	__x._M_guaranteed_capacity = 0;
121      }
122
123      vector(const vector& __x, const allocator_type& __a)
124      : _Base(__x, __a), _M_guaranteed_capacity(__x.size()) { }
125
126      vector(vector&& __x, const allocator_type& __a)
127      : _Base(std::move(__x), __a),
128        _M_guaranteed_capacity(this->size())
129      {
130	__x._M_invalidate_all();
131	__x._M_guaranteed_capacity = 0;
132      }
133
134      vector(initializer_list<value_type> __l,
135	     const allocator_type& __a = allocator_type())
136      : _Base(__l, __a),
137	_M_guaranteed_capacity(__l.size()) { }
138#endif
139
140      ~vector() _GLIBCXX_NOEXCEPT { }
141
142      vector&
143      operator=(const vector& __x)
144      {
145	static_cast<_Base&>(*this) = __x;
146	this->_M_invalidate_all();
147	_M_update_guaranteed_capacity();
148	return *this;
149      }
150
151#ifdef __GXX_EXPERIMENTAL_CXX0X__
152      vector&
153      operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
154      {
155	_Base::operator=(std::move(__x));
156	this->_M_invalidate_all();
157	_M_update_guaranteed_capacity();
158	__x._M_invalidate_all();
159	__x._M_guaranteed_capacity = 0;
160	return *this;
161      }
162
163      vector&
164      operator=(initializer_list<value_type> __l)
165      {
166	static_cast<_Base&>(*this) = __l;
167	this->_M_invalidate_all();
168	_M_update_guaranteed_capacity();
169	return *this;
170      }
171#endif
172
173      template<typename _InputIterator>
174        void
175        assign(_InputIterator __first, _InputIterator __last)
176        {
177	  __glibcxx_check_valid_range(__first, __last);
178	  _Base::assign(__gnu_debug::__base(__first),
179			__gnu_debug::__base(__last));
180	  this->_M_invalidate_all();
181	  _M_update_guaranteed_capacity();
182	}
183
184      void
185      assign(size_type __n, const _Tp& __u)
186      {
187	_Base::assign(__n, __u);
188	this->_M_invalidate_all();
189	_M_update_guaranteed_capacity();
190      }
191
192#ifdef __GXX_EXPERIMENTAL_CXX0X__
193      void
194      assign(initializer_list<value_type> __l)
195      {
196	_Base::assign(__l);
197	this->_M_invalidate_all();
198	_M_update_guaranteed_capacity();
199      }
200#endif
201
202      using _Base::get_allocator;
203
204      // iterators:
205      iterator
206      begin() _GLIBCXX_NOEXCEPT
207      { return iterator(_Base::begin(), this); }
208
209      const_iterator
210      begin() const _GLIBCXX_NOEXCEPT
211      { return const_iterator(_Base::begin(), this); }
212
213      iterator
214      end() _GLIBCXX_NOEXCEPT
215      { return iterator(_Base::end(), this); }
216
217      const_iterator
218      end() const _GLIBCXX_NOEXCEPT
219      { return const_iterator(_Base::end(), this); }
220
221      reverse_iterator
222      rbegin() _GLIBCXX_NOEXCEPT
223      { return reverse_iterator(end()); }
224
225      const_reverse_iterator
226      rbegin() const _GLIBCXX_NOEXCEPT
227      { return const_reverse_iterator(end()); }
228
229      reverse_iterator
230      rend() _GLIBCXX_NOEXCEPT
231      { return reverse_iterator(begin()); }
232
233      const_reverse_iterator
234      rend() const _GLIBCXX_NOEXCEPT
235      { return const_reverse_iterator(begin()); }
236
237#ifdef __GXX_EXPERIMENTAL_CXX0X__
238      const_iterator
239      cbegin() const noexcept
240      { return const_iterator(_Base::begin(), this); }
241
242      const_iterator
243      cend() const noexcept
244      { return const_iterator(_Base::end(), this); }
245
246      const_reverse_iterator
247      crbegin() const noexcept
248      { return const_reverse_iterator(end()); }
249
250      const_reverse_iterator
251      crend() const noexcept
252      { return const_reverse_iterator(begin()); }
253#endif
254
255      // 23.2.4.2 capacity:
256      using _Base::size;
257      using _Base::max_size;
258
259#ifdef __GXX_EXPERIMENTAL_CXX0X__
260      void
261      resize(size_type __sz)
262      {
263	bool __realloc = _M_requires_reallocation(__sz);
264	if (__sz < this->size())
265	  this->_M_invalidate_after_nth(__sz);
266	_Base::resize(__sz);
267	if (__realloc)
268	  this->_M_invalidate_all();
269	_M_update_guaranteed_capacity();
270      }
271
272      void
273      resize(size_type __sz, const _Tp& __c)
274      {
275	bool __realloc = _M_requires_reallocation(__sz);
276	if (__sz < this->size())
277	  this->_M_invalidate_after_nth(__sz);
278	_Base::resize(__sz, __c);
279	if (__realloc)
280	  this->_M_invalidate_all();
281	_M_update_guaranteed_capacity();
282      }
283#else
284      void
285      resize(size_type __sz, _Tp __c = _Tp())
286      {
287	bool __realloc = _M_requires_reallocation(__sz);
288	if (__sz < this->size())
289	  this->_M_invalidate_after_nth(__sz);
290	_Base::resize(__sz, __c);
291	if (__realloc)
292	  this->_M_invalidate_all();
293	_M_update_guaranteed_capacity();
294      }
295#endif
296
297#ifdef __GXX_EXPERIMENTAL_CXX0X__
298      void
299      shrink_to_fit()
300      {
301	if (_Base::_M_shrink_to_fit())
302	  {
303	    _M_guaranteed_capacity = _Base::capacity();
304	    this->_M_invalidate_all();
305	  }
306      }
307#endif
308
309      size_type
310      capacity() const _GLIBCXX_NOEXCEPT
311      {
312#ifdef _GLIBCXX_DEBUG_PEDANTIC
313	return _M_guaranteed_capacity;
314#else
315	return _Base::capacity();
316#endif
317      }
318
319      using _Base::empty;
320
321      void
322      reserve(size_type __n)
323      {
324	bool __realloc = _M_requires_reallocation(__n);
325	_Base::reserve(__n);
326	if (__n > _M_guaranteed_capacity)
327	  _M_guaranteed_capacity = __n;
328	if (__realloc)
329	  this->_M_invalidate_all();
330      }
331
332      // element access:
333      reference
334      operator[](size_type __n)
335      {
336	__glibcxx_check_subscript(__n);
337	return _M_base()[__n];
338      }
339
340      const_reference
341      operator[](size_type __n) const
342      {
343	__glibcxx_check_subscript(__n);
344	return _M_base()[__n];
345      }
346
347      using _Base::at;
348
349      reference
350      front()
351      {
352	__glibcxx_check_nonempty();
353	return _Base::front();
354      }
355
356      const_reference
357      front() const
358      {
359	__glibcxx_check_nonempty();
360	return _Base::front();
361      }
362
363      reference
364      back()
365      {
366	__glibcxx_check_nonempty();
367	return _Base::back();
368      }
369
370      const_reference
371      back() const
372      {
373	__glibcxx_check_nonempty();
374	return _Base::back();
375      }
376
377      // _GLIBCXX_RESOLVE_LIB_DEFECTS
378      // DR 464. Suggestion for new member functions in standard containers.
379      using _Base::data;
380
381      // 23.2.4.3 modifiers:
382      void
383      push_back(const _Tp& __x)
384      {
385	bool __realloc = _M_requires_reallocation(this->size() + 1);
386	_Base::push_back(__x);
387	if (__realloc)
388	  this->_M_invalidate_all();
389	_M_update_guaranteed_capacity();
390      }
391
392#ifdef __GXX_EXPERIMENTAL_CXX0X__
393      template<typename _Up = _Tp>
394        typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
395					void>::__type
396        push_back(_Tp&& __x)
397	{ emplace_back(std::move(__x)); }
398
399      template<typename... _Args>
400        void
401        emplace_back(_Args&&... __args)
402	{
403	  bool __realloc = _M_requires_reallocation(this->size() + 1);
404	  _Base::emplace_back(std::forward<_Args>(__args)...);
405	  if (__realloc)
406	    this->_M_invalidate_all();
407	  _M_update_guaranteed_capacity();
408	}
409#endif
410
411      void
412      pop_back()
413      {
414	__glibcxx_check_nonempty();
415	this->_M_invalidate_if(_Equal(--_Base::end()));
416	_Base::pop_back();
417      }
418
419#ifdef __GXX_EXPERIMENTAL_CXX0X__
420      template<typename... _Args>
421        iterator
422        emplace(iterator __position, _Args&&... __args)
423	{
424	  __glibcxx_check_insert(__position);
425	  bool __realloc = _M_requires_reallocation(this->size() + 1);
426	  difference_type __offset = __position.base() - _Base::begin();
427	  _Base_iterator __res = _Base::emplace(__position.base(),
428						std::forward<_Args>(__args)...);
429	  if (__realloc)
430	    this->_M_invalidate_all();
431	  else
432	    this->_M_invalidate_after_nth(__offset);
433	  _M_update_guaranteed_capacity();
434	  return iterator(__res, this);
435	}
436#endif
437
438      iterator
439      insert(iterator __position, const _Tp& __x)
440      {
441	__glibcxx_check_insert(__position);
442	bool __realloc = _M_requires_reallocation(this->size() + 1);
443	difference_type __offset = __position.base() - _Base::begin();
444	_Base_iterator __res = _Base::insert(__position.base(), __x);
445	if (__realloc)
446	  this->_M_invalidate_all();
447	else
448	  this->_M_invalidate_after_nth(__offset);
449	_M_update_guaranteed_capacity();
450	return iterator(__res, this);
451      }
452
453#ifdef __GXX_EXPERIMENTAL_CXX0X__
454      template<typename _Up = _Tp>
455        typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
456					iterator>::__type
457        insert(iterator __position, _Tp&& __x)
458        { return emplace(__position, std::move(__x)); }
459
460      void
461      insert(iterator __position, initializer_list<value_type> __l)
462      { this->insert(__position, __l.begin(), __l.end()); }
463#endif
464
465      void
466      insert(iterator __position, size_type __n, const _Tp& __x)
467      {
468	__glibcxx_check_insert(__position);
469	bool __realloc = _M_requires_reallocation(this->size() + __n);
470	difference_type __offset = __position.base() - _Base::begin();
471	_Base::insert(__position.base(), __n, __x);
472	if (__realloc)
473	  this->_M_invalidate_all();
474	else
475	  this->_M_invalidate_after_nth(__offset);
476	_M_update_guaranteed_capacity();
477      }
478
479      template<class _InputIterator>
480        void
481        insert(iterator __position,
482	       _InputIterator __first, _InputIterator __last)
483        {
484	  __glibcxx_check_insert_range(__position, __first, __last);
485
486	  /* Hard to guess if invalidation will occur, because __last
487	     - __first can't be calculated in all cases, so we just
488	     punt here by checking if it did occur. */
489	  _Base_iterator __old_begin = _M_base().begin();
490	  difference_type __offset = __position.base() - _Base::begin();
491	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
492					   __gnu_debug::__base(__last));
493
494	  if (_M_base().begin() != __old_begin)
495	    this->_M_invalidate_all();
496	  else
497	    this->_M_invalidate_after_nth(__offset);
498	  _M_update_guaranteed_capacity();
499	}
500
501      iterator
502      erase(iterator __position)
503      {
504	__glibcxx_check_erase(__position);
505	difference_type __offset = __position.base() - _Base::begin();
506	_Base_iterator __res = _Base::erase(__position.base());
507	this->_M_invalidate_after_nth(__offset);
508	return iterator(__res, this);
509      }
510
511      iterator
512      erase(iterator __first, iterator __last)
513      {
514	// _GLIBCXX_RESOLVE_LIB_DEFECTS
515	// 151. can't currently clear() empty container
516	__glibcxx_check_erase_range(__first, __last);
517
518	if (__first.base() != __last.base())
519	  {
520	    difference_type __offset = __first.base() - _Base::begin();
521	    _Base_iterator __res = _Base::erase(__first.base(),
522						__last.base());
523	    this->_M_invalidate_after_nth(__offset);
524	    return iterator(__res, this);
525	  }
526	else
527	  return __first;
528      }
529
530      void
531      swap(vector& __x)
532#ifdef __GXX_EXPERIMENTAL_CXX0X__
533			noexcept(_Alloc_traits::_S_nothrow_swap())
534#endif
535      {
536	_Base::swap(__x);
537	this->_M_swap(__x);
538        std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
539      }
540
541      void
542      clear() _GLIBCXX_NOEXCEPT
543      {
544	_Base::clear();
545	this->_M_invalidate_all();
546        _M_guaranteed_capacity = 0;
547      }
548
549      _Base&
550      _M_base() _GLIBCXX_NOEXCEPT { return *this; }
551
552      const _Base&
553      _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
554
555    private:
556      size_type _M_guaranteed_capacity;
557
558      bool
559      _M_requires_reallocation(size_type __elements)
560      { return __elements > this->capacity(); }
561
562      void
563      _M_update_guaranteed_capacity()
564      {
565	if (this->size() > _M_guaranteed_capacity)
566	  _M_guaranteed_capacity = this->size();
567      }
568
569      void
570      _M_invalidate_after_nth(difference_type __n)
571      {
572	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
573	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
574      }
575    };
576
577  template<typename _Tp, typename _Alloc>
578    inline bool
579    operator==(const vector<_Tp, _Alloc>& __lhs,
580	       const vector<_Tp, _Alloc>& __rhs)
581    { return __lhs._M_base() == __rhs._M_base(); }
582
583  template<typename _Tp, typename _Alloc>
584    inline bool
585    operator!=(const vector<_Tp, _Alloc>& __lhs,
586	       const vector<_Tp, _Alloc>& __rhs)
587    { return __lhs._M_base() != __rhs._M_base(); }
588
589  template<typename _Tp, typename _Alloc>
590    inline bool
591    operator<(const vector<_Tp, _Alloc>& __lhs,
592	      const vector<_Tp, _Alloc>& __rhs)
593    { return __lhs._M_base() < __rhs._M_base(); }
594
595  template<typename _Tp, typename _Alloc>
596    inline bool
597    operator<=(const vector<_Tp, _Alloc>& __lhs,
598	       const vector<_Tp, _Alloc>& __rhs)
599    { return __lhs._M_base() <= __rhs._M_base(); }
600
601  template<typename _Tp, typename _Alloc>
602    inline bool
603    operator>=(const vector<_Tp, _Alloc>& __lhs,
604	       const vector<_Tp, _Alloc>& __rhs)
605    { return __lhs._M_base() >= __rhs._M_base(); }
606
607  template<typename _Tp, typename _Alloc>
608    inline bool
609    operator>(const vector<_Tp, _Alloc>& __lhs,
610	      const vector<_Tp, _Alloc>& __rhs)
611    { return __lhs._M_base() > __rhs._M_base(); }
612
613  template<typename _Tp, typename _Alloc>
614    inline void
615    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
616    { __lhs.swap(__rhs); }
617
618} // namespace __debug
619
620#ifdef __GXX_EXPERIMENTAL_CXX0X__
621  // DR 1182.
622  /// std::hash specialization for vector<bool>.
623  template<typename _Alloc>
624    struct hash<__debug::vector<bool, _Alloc>>
625    : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
626    {
627      size_t
628      operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
629      { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()
630	  (__b._M_base()); }
631    };
632#endif
633
634} // namespace std
635
636#endif
637