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