1// Debugging vector implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
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
39{
40namespace __debug
41{
42  template<typename _Tp,
43	   typename _Allocator = std::allocator<_Tp> >
44    class vector
45    : public _GLIBCXX_STD_D::vector<_Tp, _Allocator>,
46      public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
47    {
48      typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base;
49      typedef __gnu_debug::_Safe_sequence<vector>              _Safe_base;
50
51      typedef typename _Base::const_iterator _Base_const_iterator;
52      typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
53
54    public:
55      typedef typename _Base::reference             reference;
56      typedef typename _Base::const_reference       const_reference;
57
58      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector>
59      iterator;
60      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector>
61      const_iterator;
62
63      typedef typename _Base::size_type             size_type;
64      typedef typename _Base::difference_type       difference_type;
65
66      typedef _Tp				    value_type;
67      typedef _Allocator			    allocator_type;
68      typedef typename _Base::pointer               pointer;
69      typedef typename _Base::const_pointer         const_pointer;
70      typedef std::reverse_iterator<iterator>       reverse_iterator;
71      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
72
73      // 23.2.4.1 construct/copy/destroy:
74      explicit vector(const _Allocator& __a = _Allocator())
75      : _Base(__a), _M_guaranteed_capacity(0) { }
76
77      explicit vector(size_type __n, const _Tp& __value = _Tp(),
78		      const _Allocator& __a = _Allocator())
79      : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
80
81      template<class _InputIterator>
82        vector(_InputIterator __first, _InputIterator __last,
83	       const _Allocator& __a = _Allocator())
84	: _Base(__gnu_debug::__check_valid_range(__first, __last),
85		__last, __a),
86	  _M_guaranteed_capacity(0)
87        { _M_update_guaranteed_capacity(); }
88
89      vector(const vector& __x)
90      : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
91
92      /// Construction from a release-mode vector
93      vector(const _Base& __x)
94      : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
95
96#ifdef __GXX_EXPERIMENTAL_CXX0X__
97      vector(vector&& __x)
98      : _Base(std::forward<vector>(__x)), _Safe_base(),
99	_M_guaranteed_capacity(this->size())
100      {
101	this->_M_swap(__x);
102	__x._M_guaranteed_capacity = 0;
103      }
104
105      vector(initializer_list<value_type> __l,
106	     const allocator_type& __a = allocator_type())
107      : _Base(__l, __a), _Safe_base(),
108	_M_guaranteed_capacity(__l.size()) { }
109#endif
110
111      ~vector() { }
112
113      vector&
114      operator=(const vector& __x)
115      {
116	static_cast<_Base&>(*this) = __x;
117	this->_M_invalidate_all();
118	_M_update_guaranteed_capacity();
119	return *this;
120      }
121
122#ifdef __GXX_EXPERIMENTAL_CXX0X__
123      vector&
124      operator=(vector&& __x)
125      {
126        // NB: DR 675.
127	clear();
128	swap(__x);
129	return *this;
130      }
131
132      vector&
133      operator=(initializer_list<value_type> __l)
134      {
135	static_cast<_Base&>(*this) = __l;
136	this->_M_invalidate_all();
137	_M_update_guaranteed_capacity();
138	return *this;
139      }
140#endif
141
142      template<typename _InputIterator>
143        void
144        assign(_InputIterator __first, _InputIterator __last)
145        {
146	  __glibcxx_check_valid_range(__first, __last);
147	  _Base::assign(__first, __last);
148	  this->_M_invalidate_all();
149	  _M_update_guaranteed_capacity();
150	}
151
152      void
153      assign(size_type __n, const _Tp& __u)
154      {
155	_Base::assign(__n, __u);
156	this->_M_invalidate_all();
157	_M_update_guaranteed_capacity();
158      }
159
160#ifdef __GXX_EXPERIMENTAL_CXX0X__
161      void
162      assign(initializer_list<value_type> __l)
163      {
164	_Base::assign(__l);
165	this->_M_invalidate_all();
166	_M_update_guaranteed_capacity();
167      }
168#endif
169
170      using _Base::get_allocator;
171
172      // iterators:
173      iterator
174      begin()
175      { return iterator(_Base::begin(), this); }
176
177      const_iterator
178      begin() const
179      { return const_iterator(_Base::begin(), this); }
180
181      iterator
182      end()
183      { return iterator(_Base::end(), this); }
184
185      const_iterator
186      end() const
187      { return const_iterator(_Base::end(), this); }
188
189      reverse_iterator
190      rbegin()
191      { return reverse_iterator(end()); }
192
193      const_reverse_iterator
194      rbegin() const
195      { return const_reverse_iterator(end()); }
196
197      reverse_iterator
198      rend()
199      { return reverse_iterator(begin()); }
200
201      const_reverse_iterator
202      rend() const
203      { return const_reverse_iterator(begin()); }
204
205#ifdef __GXX_EXPERIMENTAL_CXX0X__
206      const_iterator
207      cbegin() const
208      { return const_iterator(_Base::begin(), this); }
209
210      const_iterator
211      cend() const
212      { return const_iterator(_Base::end(), this); }
213
214      const_reverse_iterator
215      crbegin() const
216      { return const_reverse_iterator(end()); }
217
218      const_reverse_iterator
219      crend() const
220      { return const_reverse_iterator(begin()); }
221#endif
222
223      // 23.2.4.2 capacity:
224      using _Base::size;
225      using _Base::max_size;
226
227      void
228      resize(size_type __sz, _Tp __c = _Tp())
229      {
230	bool __realloc = _M_requires_reallocation(__sz);
231	if (__sz < this->size())
232	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
233	_Base::resize(__sz, __c);
234	if (__realloc)
235	  this->_M_invalidate_all();
236      }
237
238      size_type
239      capacity() const
240      {
241#ifdef _GLIBCXX_DEBUG_PEDANTIC
242	return _M_guaranteed_capacity;
243#else
244	return _Base::capacity();
245#endif
246      }
247
248      using _Base::empty;
249
250      void
251      reserve(size_type __n)
252      {
253	bool __realloc = _M_requires_reallocation(__n);
254	_Base::reserve(__n);
255	if (__n > _M_guaranteed_capacity)
256	  _M_guaranteed_capacity = __n;
257	if (__realloc)
258	  this->_M_invalidate_all();
259      }
260
261      // element access:
262      reference
263      operator[](size_type __n)
264      {
265	__glibcxx_check_subscript(__n);
266	return _M_base()[__n];
267      }
268
269      const_reference
270      operator[](size_type __n) const
271      {
272	__glibcxx_check_subscript(__n);
273	return _M_base()[__n];
274      }
275
276      using _Base::at;
277
278      reference
279      front()
280      {
281	__glibcxx_check_nonempty();
282	return _Base::front();
283      }
284
285      const_reference
286      front() const
287      {
288	__glibcxx_check_nonempty();
289	return _Base::front();
290      }
291
292      reference
293      back()
294      {
295	__glibcxx_check_nonempty();
296	return _Base::back();
297      }
298
299      const_reference
300      back() const
301      {
302	__glibcxx_check_nonempty();
303	return _Base::back();
304      }
305
306      // _GLIBCXX_RESOLVE_LIB_DEFECTS
307      // DR 464. Suggestion for new member functions in standard containers.
308      using _Base::data;
309
310      // 23.2.4.3 modifiers:
311      void
312      push_back(const _Tp& __x)
313      {
314	bool __realloc = _M_requires_reallocation(this->size() + 1);
315	_Base::push_back(__x);
316	if (__realloc)
317	  this->_M_invalidate_all();
318	_M_update_guaranteed_capacity();
319      }
320
321#ifdef __GXX_EXPERIMENTAL_CXX0X__
322      template<typename _Up = _Tp>
323        typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
324					void>::__type
325        push_back(_Tp&& __x)
326	{ emplace_back(std::move(__x)); }
327
328      template<typename... _Args>
329        void
330        emplace_back(_Args&&... __args)
331	{
332	  bool __realloc = _M_requires_reallocation(this->size() + 1);
333	  _Base::emplace_back(std::forward<_Args>(__args)...);
334	  if (__realloc)
335	    this->_M_invalidate_all();
336	  _M_update_guaranteed_capacity();
337	}
338#endif
339
340      void
341      pop_back()
342      {
343	__glibcxx_check_nonempty();
344	iterator __victim = end() - 1;
345	__victim._M_invalidate();
346	_Base::pop_back();
347      }
348
349#ifdef __GXX_EXPERIMENTAL_CXX0X__
350      template<typename... _Args>
351        iterator
352        emplace(iterator __position, _Args&&... __args)
353	{
354	  __glibcxx_check_insert(__position);
355	  bool __realloc = _M_requires_reallocation(this->size() + 1);
356	  difference_type __offset = __position - begin();
357	  typename _Base::iterator __res = _Base::emplace(__position.base(),
358					    std::forward<_Args>(__args)...);
359	  if (__realloc)
360	    this->_M_invalidate_all();
361	  else
362	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
363	  _M_update_guaranteed_capacity();
364	  return iterator(__res, this);
365	}
366#endif
367
368      iterator
369      insert(iterator __position, const _Tp& __x)
370      {
371	__glibcxx_check_insert(__position);
372	bool __realloc = _M_requires_reallocation(this->size() + 1);
373	difference_type __offset = __position - begin();
374	typename _Base::iterator __res = _Base::insert(__position.base(),__x);
375	if (__realloc)
376	  this->_M_invalidate_all();
377	else
378	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
379	_M_update_guaranteed_capacity();
380	return iterator(__res, this);
381      }
382
383#ifdef __GXX_EXPERIMENTAL_CXX0X__
384      template<typename _Up = _Tp>
385        typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
386					iterator>::__type
387        insert(iterator __position, _Tp&& __x)
388        { return emplace(__position, std::move(__x)); }
389
390      void
391      insert(iterator __position, initializer_list<value_type> __l)
392      { this->insert(__position, __l.begin(), __l.end()); }
393#endif
394
395      void
396      insert(iterator __position, size_type __n, const _Tp& __x)
397      {
398	__glibcxx_check_insert(__position);
399	bool __realloc = _M_requires_reallocation(this->size() + __n);
400	difference_type __offset = __position - begin();
401	_Base::insert(__position.base(), __n, __x);
402	if (__realloc)
403	  this->_M_invalidate_all();
404	else
405	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
406	_M_update_guaranteed_capacity();
407      }
408
409      template<class _InputIterator>
410        void
411        insert(iterator __position,
412	       _InputIterator __first, _InputIterator __last)
413        {
414	  __glibcxx_check_insert_range(__position, __first, __last);
415
416	  /* Hard to guess if invalidation will occur, because __last
417	     - __first can't be calculated in all cases, so we just
418	     punt here by checking if it did occur. */
419	  typename _Base::iterator __old_begin = _M_base().begin();
420	  difference_type __offset = __position - begin();
421	  _Base::insert(__position.base(), __first, __last);
422
423	  if (_M_base().begin() != __old_begin)
424	    this->_M_invalidate_all();
425	  else
426	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
427	  _M_update_guaranteed_capacity();
428	}
429
430      iterator
431      erase(iterator __position)
432      {
433	__glibcxx_check_erase(__position);
434	difference_type __offset = __position - begin();
435	typename _Base::iterator __res = _Base::erase(__position.base());
436	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
437	return iterator(__res, this);
438      }
439
440      iterator
441      erase(iterator __first, iterator __last)
442      {
443	// _GLIBCXX_RESOLVE_LIB_DEFECTS
444	// 151. can't currently clear() empty container
445	__glibcxx_check_erase_range(__first, __last);
446
447	difference_type __offset = __first - begin();
448	typename _Base::iterator __res = _Base::erase(__first.base(),
449							 __last.base());
450	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
451	return iterator(__res, this);
452      }
453
454      void
455#ifdef __GXX_EXPERIMENTAL_CXX0X__
456      swap(vector&& __x)
457#else
458      swap(vector& __x)
459#endif
460      {
461	_Base::swap(__x);
462	this->_M_swap(__x);
463        std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
464      }
465
466      void
467      clear()
468      {
469	_Base::clear();
470	this->_M_invalidate_all();
471        _M_guaranteed_capacity = 0;
472      }
473
474      _Base&
475      _M_base() { return *this; }
476
477      const _Base&
478      _M_base() const { return *this; }
479
480    private:
481      size_type _M_guaranteed_capacity;
482
483      bool
484      _M_requires_reallocation(size_type __elements)
485      { return __elements > this->capacity(); }
486
487      void
488      _M_update_guaranteed_capacity()
489      {
490	if (this->size() > _M_guaranteed_capacity)
491	  _M_guaranteed_capacity = this->size();
492      }
493    };
494
495  template<typename _Tp, typename _Alloc>
496    inline bool
497    operator==(const vector<_Tp, _Alloc>& __lhs,
498	       const vector<_Tp, _Alloc>& __rhs)
499    { return __lhs._M_base() == __rhs._M_base(); }
500
501  template<typename _Tp, typename _Alloc>
502    inline bool
503    operator!=(const vector<_Tp, _Alloc>& __lhs,
504	       const vector<_Tp, _Alloc>& __rhs)
505    { return __lhs._M_base() != __rhs._M_base(); }
506
507  template<typename _Tp, typename _Alloc>
508    inline bool
509    operator<(const vector<_Tp, _Alloc>& __lhs,
510	      const vector<_Tp, _Alloc>& __rhs)
511    { return __lhs._M_base() < __rhs._M_base(); }
512
513  template<typename _Tp, typename _Alloc>
514    inline bool
515    operator<=(const vector<_Tp, _Alloc>& __lhs,
516	       const vector<_Tp, _Alloc>& __rhs)
517    { return __lhs._M_base() <= __rhs._M_base(); }
518
519  template<typename _Tp, typename _Alloc>
520    inline bool
521    operator>=(const vector<_Tp, _Alloc>& __lhs,
522	       const vector<_Tp, _Alloc>& __rhs)
523    { return __lhs._M_base() >= __rhs._M_base(); }
524
525  template<typename _Tp, typename _Alloc>
526    inline bool
527    operator>(const vector<_Tp, _Alloc>& __lhs,
528	      const vector<_Tp, _Alloc>& __rhs)
529    { return __lhs._M_base() > __rhs._M_base(); }
530
531  template<typename _Tp, typename _Alloc>
532    inline void
533    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
534    { __lhs.swap(__rhs); }
535
536#ifdef __GXX_EXPERIMENTAL_CXX0X__
537  template<typename _Tp, typename _Alloc>
538    inline void
539    swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
540    { __lhs.swap(__rhs); }
541
542  template<typename _Tp, typename _Alloc>
543    inline void
544    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
545    { __lhs.swap(__rhs); }
546#endif
547
548} // namespace __debug
549} // namespace std
550
551#endif
552