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