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