1// Debugging vector implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005
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 2, 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// You should have received a copy of the GNU General Public License along
18// with this library; see the file COPYING.  If not, write to the Free
19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20// USA.
21
22// As a special exception, you may use this file as part of a free software
23// library without restriction.  Specifically, if other files instantiate
24// templates or use macros or inline functions from this file, or you compile
25// this file and link it with other files to produce an executable, this
26// file does not by itself cause the resulting executable to be covered by
27// the GNU General Public License.  This exception does not however
28// invalidate any other reasons why the executable file might be covered by
29// the GNU General Public License.
30
31/** @file debug/vector
32 *  This file is a GNU debug extension to the Standard C++ Library.
33 */
34
35#ifndef _GLIBCXX_DEBUG_VECTOR
36#define _GLIBCXX_DEBUG_VECTOR 1
37
38#include <vector>
39#include <utility>
40#include <debug/safe_sequence.h>
41#include <debug/safe_iterator.h>
42
43namespace std
44{
45namespace __debug
46{
47  template<typename _Tp,
48	   typename _Allocator = std::allocator<_Tp> >
49    class vector
50    : public _GLIBCXX_STD::vector<_Tp, _Allocator>,
51      public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
52    {
53      typedef _GLIBCXX_STD::vector<_Tp, _Allocator> _Base;
54      typedef __gnu_debug::_Safe_sequence<vector>              _Safe_base;
55
56      typedef typename _Base::const_iterator _Base_const_iterator;
57      typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
58
59    public:
60      typedef typename _Base::reference             reference;
61      typedef typename _Base::const_reference       const_reference;
62
63      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector>
64      iterator;
65      typedef __gnu_debug::_Safe_iterator<typename _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 vector(const _Allocator& __a = _Allocator())
80      : _Base(__a), _M_guaranteed_capacity(0) { }
81
82      explicit vector(size_type __n, const _Tp& __value = _Tp(),
83		      const _Allocator& __a = _Allocator())
84      : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
85
86      template<class _InputIterator>
87        vector(_InputIterator __first, _InputIterator __last,
88	       const _Allocator& __a = _Allocator())
89	: _Base(__gnu_debug::__check_valid_range(__first, __last),
90		__last, __a),
91	  _M_guaranteed_capacity(0)
92        { _M_update_guaranteed_capacity(); }
93
94      vector(const vector<_Tp,_Allocator>& __x)
95      : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
96
97      /// Construction from a release-mode vector
98      vector(const _Base& __x)
99      : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
100
101      ~vector() { }
102
103      vector<_Tp,_Allocator>&
104      operator=(const vector<_Tp,_Allocator>& __x)
105      {
106	static_cast<_Base&>(*this) = __x;
107	this->_M_invalidate_all();
108	_M_update_guaranteed_capacity();
109	return *this;
110      }
111
112      template<typename _InputIterator>
113        void
114        assign(_InputIterator __first, _InputIterator __last)
115        {
116	  __glibcxx_check_valid_range(__first, __last);
117	  _Base::assign(__first, __last);
118	  this->_M_invalidate_all();
119	  _M_update_guaranteed_capacity();
120	}
121
122      void
123      assign(size_type __n, const _Tp& __u)
124      {
125	_Base::assign(__n, __u);
126	this->_M_invalidate_all();
127	_M_update_guaranteed_capacity();
128      }
129
130      using _Base::get_allocator;
131
132      // iterators:
133      iterator
134      begin()
135      { return iterator(_Base::begin(), this); }
136
137      const_iterator
138      begin() const
139      { return const_iterator(_Base::begin(), this); }
140
141      iterator
142      end()
143      { return iterator(_Base::end(), this); }
144
145      const_iterator
146      end() const
147      { return const_iterator(_Base::end(), this); }
148
149      reverse_iterator
150      rbegin()
151      { return reverse_iterator(end()); }
152
153      const_reverse_iterator
154      rbegin() const
155      { return const_reverse_iterator(end()); }
156
157      reverse_iterator
158      rend()
159      { return reverse_iterator(begin()); }
160
161      const_reverse_iterator
162      rend() const
163      { return const_reverse_iterator(begin()); }
164
165      // 23.2.4.2 capacity:
166      using _Base::size;
167      using _Base::max_size;
168
169      void
170      resize(size_type __sz, _Tp __c = _Tp())
171      {
172	bool __realloc = _M_requires_reallocation(__sz);
173	if (__sz < this->size())
174	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
175	_Base::resize(__sz, __c);
176	if (__realloc)
177	  this->_M_invalidate_all();
178      }
179
180      using _Base::capacity;
181      using _Base::empty;
182
183      void
184      reserve(size_type __n)
185      {
186	bool __realloc = _M_requires_reallocation(__n);
187	_Base::reserve(__n);
188	if (__n > _M_guaranteed_capacity)
189	  _M_guaranteed_capacity = __n;
190	if (__realloc)
191	  this->_M_invalidate_all();
192      }
193
194      // element access:
195      reference
196      operator[](size_type __n)
197      {
198	__glibcxx_check_subscript(__n);
199	return _M_base()[__n];
200      }
201
202      const_reference
203      operator[](size_type __n) const
204      {
205	__glibcxx_check_subscript(__n);
206	return _M_base()[__n];
207      }
208
209      using _Base::at;
210
211      reference
212      front()
213      {
214	__glibcxx_check_nonempty();
215	return _Base::front();
216      }
217
218      const_reference
219      front() const
220      {
221	__glibcxx_check_nonempty();
222	return _Base::front();
223      }
224
225      reference
226      back()
227      {
228	__glibcxx_check_nonempty();
229	return _Base::back();
230      }
231
232      const_reference
233      back() const
234      {
235	__glibcxx_check_nonempty();
236	return _Base::back();
237      }
238
239      // _GLIBCXX_RESOLVE_LIB_DEFECTS
240      // DR 464. Suggestion for new member functions in standard containers.
241      using _Base::data;
242
243      // 23.2.4.3 modifiers:
244      void
245      push_back(const _Tp& __x)
246      {
247	bool __realloc = _M_requires_reallocation(this->size() + 1);
248	_Base::push_back(__x);
249	if (__realloc)
250	  this->_M_invalidate_all();
251	_M_update_guaranteed_capacity();
252      }
253
254      void
255      pop_back()
256      {
257	__glibcxx_check_nonempty();
258	iterator __victim = end() - 1;
259	__victim._M_invalidate();
260	_Base::pop_back();
261      }
262
263      iterator
264      insert(iterator __position, const _Tp& __x)
265      {
266	__glibcxx_check_insert(__position);
267	bool __realloc = _M_requires_reallocation(this->size() + 1);
268	difference_type __offset = __position - begin();
269	typename _Base::iterator __res = _Base::insert(__position.base(),__x);
270	if (__realloc)
271	  this->_M_invalidate_all();
272	else
273	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
274	_M_update_guaranteed_capacity();
275	return iterator(__res, this);
276      }
277
278      void
279      insert(iterator __position, size_type __n, const _Tp& __x)
280      {
281	__glibcxx_check_insert(__position);
282	bool __realloc = _M_requires_reallocation(this->size() + __n);
283	difference_type __offset = __position - begin();
284	_Base::insert(__position.base(), __n, __x);
285	if (__realloc)
286	  this->_M_invalidate_all();
287	else
288	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
289	_M_update_guaranteed_capacity();
290      }
291
292      template<class _InputIterator>
293        void
294        insert(iterator __position,
295	       _InputIterator __first, _InputIterator __last)
296        {
297	  __glibcxx_check_insert_range(__position, __first, __last);
298
299	  /* Hard to guess if invalidation will occur, because __last
300	     - __first can't be calculated in all cases, so we just
301	     punt here by checking if it did occur. */
302	  typename _Base::iterator __old_begin = _M_base().begin();
303	  difference_type __offset = __position - begin();
304	  _Base::insert(__position.base(), __first, __last);
305
306	  if (_M_base().begin() != __old_begin)
307	    this->_M_invalidate_all();
308	  else
309	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
310	  _M_update_guaranteed_capacity();
311	}
312
313      iterator
314      erase(iterator __position)
315      {
316	__glibcxx_check_erase(__position);
317	difference_type __offset = __position - begin();
318	typename _Base::iterator __res = _Base::erase(__position.base());
319	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
320	return iterator(__res, this);
321      }
322
323      iterator
324      erase(iterator __first, iterator __last)
325      {
326	// _GLIBCXX_RESOLVE_LIB_DEFECTS
327	// 151. can't currently clear() empty container
328	__glibcxx_check_erase_range(__first, __last);
329
330	difference_type __offset = __first - begin();
331	typename _Base::iterator __res = _Base::erase(__first.base(),
332							 __last.base());
333	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
334	return iterator(__res, this);
335      }
336
337      void
338      swap(vector<_Tp,_Allocator>& __x)
339      {
340	_Base::swap(__x);
341	this->_M_swap(__x);
342        std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
343      }
344
345      void
346      clear()
347      {
348	_Base::clear();
349	this->_M_invalidate_all();
350        _M_guaranteed_capacity = 0;
351      }
352
353      _Base&
354      _M_base() { return *this; }
355
356      const _Base&
357      _M_base() const { return *this; }
358
359    private:
360      size_type _M_guaranteed_capacity;
361
362      bool
363      _M_requires_reallocation(size_type __elements)
364      {
365#ifdef _GLIBCXX_DEBUG_PEDANTIC
366	return __elements > this->capacity();
367#else
368	return __elements > _M_guaranteed_capacity;
369#endif
370      }
371
372      void
373      _M_update_guaranteed_capacity()
374      {
375	if (this->size() > _M_guaranteed_capacity)
376	  _M_guaranteed_capacity = this->size();
377      }
378    };
379
380  template<typename _Tp, typename _Alloc>
381    inline bool
382    operator==(const vector<_Tp, _Alloc>& __lhs,
383	       const vector<_Tp, _Alloc>& __rhs)
384    { return __lhs._M_base() == __rhs._M_base(); }
385
386  template<typename _Tp, typename _Alloc>
387    inline bool
388    operator!=(const vector<_Tp, _Alloc>& __lhs,
389	       const vector<_Tp, _Alloc>& __rhs)
390    { return __lhs._M_base() != __rhs._M_base(); }
391
392  template<typename _Tp, typename _Alloc>
393    inline bool
394    operator<(const vector<_Tp, _Alloc>& __lhs,
395	      const vector<_Tp, _Alloc>& __rhs)
396    { return __lhs._M_base() < __rhs._M_base(); }
397
398  template<typename _Tp, typename _Alloc>
399    inline bool
400    operator<=(const vector<_Tp, _Alloc>& __lhs,
401	       const vector<_Tp, _Alloc>& __rhs)
402    { return __lhs._M_base() <= __rhs._M_base(); }
403
404  template<typename _Tp, typename _Alloc>
405    inline bool
406    operator>=(const vector<_Tp, _Alloc>& __lhs,
407	       const vector<_Tp, _Alloc>& __rhs)
408    { return __lhs._M_base() >= __rhs._M_base(); }
409
410  template<typename _Tp, typename _Alloc>
411    inline bool
412    operator>(const vector<_Tp, _Alloc>& __lhs,
413	      const vector<_Tp, _Alloc>& __rhs)
414    { return __lhs._M_base() > __rhs._M_base(); }
415
416  template<typename _Tp, typename _Alloc>
417    inline void
418    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
419    { __lhs.swap(__rhs); }
420} // namespace __debug
421} // namespace std
422
423#endif
424