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#ifndef _GLIBCXX_DEBUG_VECTOR
32#define _GLIBCXX_DEBUG_VECTOR 1
33
34#include <vector>
35#include <utility>
36#include <debug/safe_sequence.h>
37#include <debug/safe_iterator.h>
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 _Base::pointer               pointer;
68      typedef typename _Base::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      // _GLIBCXX_RESOLVE_LIB_DEFECTS
234      // DR 464. Suggestion for new member functions in standard containers.
235      using _Base::data;
236
237      // 23.2.4.3 modifiers:
238      void
239      push_back(const _Tp& __x)
240      {
241	bool __realloc = _M_requires_reallocation(this->size() + 1);
242	_Base::push_back(__x);
243	if (__realloc)
244	  this->_M_invalidate_all();
245	_M_update_guaranteed_capacity();
246      }
247
248      void
249      pop_back()
250      {
251	__glibcxx_check_nonempty();
252	iterator __victim = end() - 1;
253	__victim._M_invalidate();
254	_Base::pop_back();
255      }
256
257      iterator
258      insert(iterator __position, const _Tp& __x)
259      {
260	__glibcxx_check_insert(__position);
261	bool __realloc = _M_requires_reallocation(this->size() + 1);
262	difference_type __offset = __position - begin();
263	typename _Base::iterator __res = _Base::insert(__position.base(),__x);
264	if (__realloc)
265	  this->_M_invalidate_all();
266	else
267	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
268	_M_update_guaranteed_capacity();
269	return iterator(__res, this);
270      }
271
272      void
273      insert(iterator __position, size_type __n, const _Tp& __x)
274      {
275	__glibcxx_check_insert(__position);
276	bool __realloc = _M_requires_reallocation(this->size() + __n);
277	difference_type __offset = __position - begin();
278	_Base::insert(__position.base(), __n, __x);
279	if (__realloc)
280	  this->_M_invalidate_all();
281	else
282	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
283	_M_update_guaranteed_capacity();
284      }
285
286      template<class _InputIterator>
287        void
288        insert(iterator __position,
289	       _InputIterator __first, _InputIterator __last)
290        {
291	  __glibcxx_check_insert_range(__position, __first, __last);
292
293	  /* Hard to guess if invalidation will occur, because __last
294	     - __first can't be calculated in all cases, so we just
295	     punt here by checking if it did occur. */
296	  typename _Base::iterator __old_begin = _M_base().begin();
297	  difference_type __offset = __position - begin();
298	  _Base::insert(__position.base(), __first, __last);
299
300	  if (_M_base().begin() != __old_begin)
301	    this->_M_invalidate_all();
302	  else
303	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
304	  _M_update_guaranteed_capacity();
305	}
306
307      iterator
308      erase(iterator __position)
309      {
310	__glibcxx_check_erase(__position);
311	difference_type __offset = __position - begin();
312	typename _Base::iterator __res = _Base::erase(__position.base());
313	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
314	return iterator(__res, this);
315      }
316
317      iterator
318      erase(iterator __first, iterator __last)
319      {
320	// _GLIBCXX_RESOLVE_LIB_DEFECTS
321	// 151. can't currently clear() empty container
322	__glibcxx_check_erase_range(__first, __last);
323
324	difference_type __offset = __first - begin();
325	typename _Base::iterator __res = _Base::erase(__first.base(),
326							 __last.base());
327	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
328	return iterator(__res, this);
329      }
330
331      void
332      swap(vector<_Tp,_Allocator>& __x)
333      {
334	_Base::swap(__x);
335	this->_M_swap(__x);
336        std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
337      }
338
339      void
340      clear()
341      {
342	_Base::clear();
343	this->_M_invalidate_all();
344        _M_guaranteed_capacity = 0;
345      }
346
347      _Base&
348      _M_base() { return *this; }
349
350      const _Base&
351      _M_base() const { return *this; }
352
353    private:
354      size_type _M_guaranteed_capacity;
355
356      bool
357      _M_requires_reallocation(size_type __elements)
358      {
359#ifdef _GLIBCXX_DEBUG_PEDANTIC
360	return __elements > this->capacity();
361#else
362	return __elements > _M_guaranteed_capacity;
363#endif
364      }
365
366      void
367      _M_update_guaranteed_capacity()
368      {
369	if (this->size() > _M_guaranteed_capacity)
370	  _M_guaranteed_capacity = this->size();
371      }
372    };
373
374  template<typename _Tp, typename _Alloc>
375    inline bool
376    operator==(const vector<_Tp, _Alloc>& __lhs,
377	       const vector<_Tp, _Alloc>& __rhs)
378    { return __lhs._M_base() == __rhs._M_base(); }
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 void
412    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
413    { __lhs.swap(__rhs); }
414} // namespace __gnu_debug_def
415
416#endif
417