1// Debugging vector implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 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 3, 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// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/** @file debug/vector 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30#ifndef _GLIBCXX_DEBUG_VECTOR 31#define _GLIBCXX_DEBUG_VECTOR 1 32 33#include <vector> 34#include <utility> 35#include <debug/safe_sequence.h> 36#include <debug/safe_iterator.h> 37 38namespace std 39{ 40namespace __debug 41{ 42 /// Class std::vector with safety/checking/debug instrumentation. 43 template<typename _Tp, 44 typename _Allocator = std::allocator<_Tp> > 45 class vector 46 : public _GLIBCXX_STD_D::vector<_Tp, _Allocator>, 47 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > 48 { 49 typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base; 50 typedef __gnu_debug::_Safe_sequence<vector> _Safe_base; 51 52 typedef typename _Base::const_iterator _Base_const_iterator; 53 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 54 55 public: 56 typedef typename _Base::reference reference; 57 typedef typename _Base::const_reference const_reference; 58 59 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector> 60 iterator; 61 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector> 62 const_iterator; 63 64 typedef typename _Base::size_type size_type; 65 typedef typename _Base::difference_type difference_type; 66 67 typedef _Tp value_type; 68 typedef _Allocator allocator_type; 69 typedef typename _Base::pointer pointer; 70 typedef typename _Base::const_pointer const_pointer; 71 typedef std::reverse_iterator<iterator> reverse_iterator; 72 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 73 74 // 23.2.4.1 construct/copy/destroy: 75 explicit vector(const _Allocator& __a = _Allocator()) 76 : _Base(__a), _M_guaranteed_capacity(0) { } 77 78 explicit vector(size_type __n, const _Tp& __value = _Tp(), 79 const _Allocator& __a = _Allocator()) 80 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 81 82 template<class _InputIterator> 83 vector(_InputIterator __first, _InputIterator __last, 84 const _Allocator& __a = _Allocator()) 85 : _Base(__gnu_debug::__check_valid_range(__first, __last), 86 __last, __a), 87 _M_guaranteed_capacity(0) 88 { _M_update_guaranteed_capacity(); } 89 90 vector(const vector& __x) 91 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 92 93 /// Construction from a release-mode vector 94 vector(const _Base& __x) 95 : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { } 96 97#ifdef __GXX_EXPERIMENTAL_CXX0X__ 98 vector(vector&& __x) 99 : _Base(std::forward<vector>(__x)), _Safe_base(), 100 _M_guaranteed_capacity(this->size()) 101 { 102 this->_M_swap(__x); 103 __x._M_guaranteed_capacity = 0; 104 } 105 106 vector(initializer_list<value_type> __l, 107 const allocator_type& __a = allocator_type()) 108 : _Base(__l, __a), _Safe_base(), 109 _M_guaranteed_capacity(__l.size()) { } 110#endif 111 112 ~vector() { } 113 114 vector& 115 operator=(const vector& __x) 116 { 117 static_cast<_Base&>(*this) = __x; 118 this->_M_invalidate_all(); 119 _M_update_guaranteed_capacity(); 120 return *this; 121 } 122 123#ifdef __GXX_EXPERIMENTAL_CXX0X__ 124 vector& 125 operator=(vector&& __x) 126 { 127 // NB: DR 1204. 128 // NB: DR 675. 129 clear(); 130 swap(__x); 131 return *this; 132 } 133 134 vector& 135 operator=(initializer_list<value_type> __l) 136 { 137 static_cast<_Base&>(*this) = __l; 138 this->_M_invalidate_all(); 139 _M_update_guaranteed_capacity(); 140 return *this; 141 } 142#endif 143 144 template<typename _InputIterator> 145 void 146 assign(_InputIterator __first, _InputIterator __last) 147 { 148 __glibcxx_check_valid_range(__first, __last); 149 _Base::assign(__first, __last); 150 this->_M_invalidate_all(); 151 _M_update_guaranteed_capacity(); 152 } 153 154 void 155 assign(size_type __n, const _Tp& __u) 156 { 157 _Base::assign(__n, __u); 158 this->_M_invalidate_all(); 159 _M_update_guaranteed_capacity(); 160 } 161 162#ifdef __GXX_EXPERIMENTAL_CXX0X__ 163 void 164 assign(initializer_list<value_type> __l) 165 { 166 _Base::assign(__l); 167 this->_M_invalidate_all(); 168 _M_update_guaranteed_capacity(); 169 } 170#endif 171 172 using _Base::get_allocator; 173 174 // iterators: 175 iterator 176 begin() 177 { return iterator(_Base::begin(), this); } 178 179 const_iterator 180 begin() const 181 { return const_iterator(_Base::begin(), this); } 182 183 iterator 184 end() 185 { return iterator(_Base::end(), this); } 186 187 const_iterator 188 end() const 189 { return const_iterator(_Base::end(), this); } 190 191 reverse_iterator 192 rbegin() 193 { return reverse_iterator(end()); } 194 195 const_reverse_iterator 196 rbegin() const 197 { return const_reverse_iterator(end()); } 198 199 reverse_iterator 200 rend() 201 { return reverse_iterator(begin()); } 202 203 const_reverse_iterator 204 rend() const 205 { return const_reverse_iterator(begin()); } 206 207#ifdef __GXX_EXPERIMENTAL_CXX0X__ 208 const_iterator 209 cbegin() const 210 { return const_iterator(_Base::begin(), this); } 211 212 const_iterator 213 cend() const 214 { return const_iterator(_Base::end(), this); } 215 216 const_reverse_iterator 217 crbegin() const 218 { return const_reverse_iterator(end()); } 219 220 const_reverse_iterator 221 crend() const 222 { return const_reverse_iterator(begin()); } 223#endif 224 225 // 23.2.4.2 capacity: 226 using _Base::size; 227 using _Base::max_size; 228 229 void 230 resize(size_type __sz, _Tp __c = _Tp()) 231 { 232 bool __realloc = _M_requires_reallocation(__sz); 233 if (__sz < this->size()) 234 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin())); 235 _Base::resize(__sz, __c); 236 if (__realloc) 237 this->_M_invalidate_all(); 238 _M_update_guaranteed_capacity(); 239 } 240 241#ifdef __GXX_EXPERIMENTAL_CXX0X__ 242 using _Base::shrink_to_fit; 243#endif 244 245 size_type 246 capacity() const 247 { 248#ifdef _GLIBCXX_DEBUG_PEDANTIC 249 return _M_guaranteed_capacity; 250#else 251 return _Base::capacity(); 252#endif 253 } 254 255 using _Base::empty; 256 257 void 258 reserve(size_type __n) 259 { 260 bool __realloc = _M_requires_reallocation(__n); 261 _Base::reserve(__n); 262 if (__n > _M_guaranteed_capacity) 263 _M_guaranteed_capacity = __n; 264 if (__realloc) 265 this->_M_invalidate_all(); 266 } 267 268 // element access: 269 reference 270 operator[](size_type __n) 271 { 272 __glibcxx_check_subscript(__n); 273 return _M_base()[__n]; 274 } 275 276 const_reference 277 operator[](size_type __n) const 278 { 279 __glibcxx_check_subscript(__n); 280 return _M_base()[__n]; 281 } 282 283 using _Base::at; 284 285 reference 286 front() 287 { 288 __glibcxx_check_nonempty(); 289 return _Base::front(); 290 } 291 292 const_reference 293 front() const 294 { 295 __glibcxx_check_nonempty(); 296 return _Base::front(); 297 } 298 299 reference 300 back() 301 { 302 __glibcxx_check_nonempty(); 303 return _Base::back(); 304 } 305 306 const_reference 307 back() const 308 { 309 __glibcxx_check_nonempty(); 310 return _Base::back(); 311 } 312 313 // _GLIBCXX_RESOLVE_LIB_DEFECTS 314 // DR 464. Suggestion for new member functions in standard containers. 315 using _Base::data; 316 317 // 23.2.4.3 modifiers: 318 void 319 push_back(const _Tp& __x) 320 { 321 bool __realloc = _M_requires_reallocation(this->size() + 1); 322 _Base::push_back(__x); 323 if (__realloc) 324 this->_M_invalidate_all(); 325 _M_update_guaranteed_capacity(); 326 } 327 328#ifdef __GXX_EXPERIMENTAL_CXX0X__ 329 template<typename _Up = _Tp> 330 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 331 void>::__type 332 push_back(_Tp&& __x) 333 { emplace_back(std::move(__x)); } 334 335 template<typename... _Args> 336 void 337 emplace_back(_Args&&... __args) 338 { 339 bool __realloc = _M_requires_reallocation(this->size() + 1); 340 _Base::emplace_back(std::forward<_Args>(__args)...); 341 if (__realloc) 342 this->_M_invalidate_all(); 343 _M_update_guaranteed_capacity(); 344 } 345#endif 346 347 void 348 pop_back() 349 { 350 __glibcxx_check_nonempty(); 351 iterator __victim = end() - 1; 352 __victim._M_invalidate(); 353 _Base::pop_back(); 354 } 355 356#ifdef __GXX_EXPERIMENTAL_CXX0X__ 357 template<typename... _Args> 358 iterator 359 emplace(iterator __position, _Args&&... __args) 360 { 361 __glibcxx_check_insert(__position); 362 bool __realloc = _M_requires_reallocation(this->size() + 1); 363 difference_type __offset = __position - begin(); 364 typename _Base::iterator __res = _Base::emplace(__position.base(), 365 std::forward<_Args>(__args)...); 366 if (__realloc) 367 this->_M_invalidate_all(); 368 else 369 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 370 _M_update_guaranteed_capacity(); 371 return iterator(__res, this); 372 } 373#endif 374 375 iterator 376 insert(iterator __position, const _Tp& __x) 377 { 378 __glibcxx_check_insert(__position); 379 bool __realloc = _M_requires_reallocation(this->size() + 1); 380 difference_type __offset = __position - begin(); 381 typename _Base::iterator __res = _Base::insert(__position.base(),__x); 382 if (__realloc) 383 this->_M_invalidate_all(); 384 else 385 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 386 _M_update_guaranteed_capacity(); 387 return iterator(__res, this); 388 } 389 390#ifdef __GXX_EXPERIMENTAL_CXX0X__ 391 template<typename _Up = _Tp> 392 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 393 iterator>::__type 394 insert(iterator __position, _Tp&& __x) 395 { return emplace(__position, std::move(__x)); } 396 397 void 398 insert(iterator __position, initializer_list<value_type> __l) 399 { this->insert(__position, __l.begin(), __l.end()); } 400#endif 401 402 void 403 insert(iterator __position, size_type __n, const _Tp& __x) 404 { 405 __glibcxx_check_insert(__position); 406 bool __realloc = _M_requires_reallocation(this->size() + __n); 407 difference_type __offset = __position - begin(); 408 _Base::insert(__position.base(), __n, __x); 409 if (__realloc) 410 this->_M_invalidate_all(); 411 else 412 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 413 _M_update_guaranteed_capacity(); 414 } 415 416 template<class _InputIterator> 417 void 418 insert(iterator __position, 419 _InputIterator __first, _InputIterator __last) 420 { 421 __glibcxx_check_insert_range(__position, __first, __last); 422 423 /* Hard to guess if invalidation will occur, because __last 424 - __first can't be calculated in all cases, so we just 425 punt here by checking if it did occur. */ 426 typename _Base::iterator __old_begin = _M_base().begin(); 427 difference_type __offset = __position - begin(); 428 _Base::insert(__position.base(), __first, __last); 429 430 if (_M_base().begin() != __old_begin) 431 this->_M_invalidate_all(); 432 else 433 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 434 _M_update_guaranteed_capacity(); 435 } 436 437 iterator 438 erase(iterator __position) 439 { 440 __glibcxx_check_erase(__position); 441 difference_type __offset = __position - begin(); 442 typename _Base::iterator __res = _Base::erase(__position.base()); 443 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 444 return iterator(__res, this); 445 } 446 447 iterator 448 erase(iterator __first, iterator __last) 449 { 450 // _GLIBCXX_RESOLVE_LIB_DEFECTS 451 // 151. can't currently clear() empty container 452 __glibcxx_check_erase_range(__first, __last); 453 454 difference_type __offset = __first - begin(); 455 typename _Base::iterator __res = _Base::erase(__first.base(), 456 __last.base()); 457 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin())); 458 return iterator(__res, this); 459 } 460 461 void 462 swap(vector& __x) 463 { 464 _Base::swap(__x); 465 this->_M_swap(__x); 466 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity); 467 } 468 469 void 470 clear() 471 { 472 _Base::clear(); 473 this->_M_invalidate_all(); 474 _M_guaranteed_capacity = 0; 475 } 476 477 _Base& 478 _M_base() { return *this; } 479 480 const _Base& 481 _M_base() const { return *this; } 482 483 private: 484 size_type _M_guaranteed_capacity; 485 486 bool 487 _M_requires_reallocation(size_type __elements) 488 { return __elements > this->capacity(); } 489 490 void 491 _M_update_guaranteed_capacity() 492 { 493 if (this->size() > _M_guaranteed_capacity) 494 _M_guaranteed_capacity = this->size(); 495 } 496 }; 497 498 template<typename _Tp, typename _Alloc> 499 inline bool 500 operator==(const vector<_Tp, _Alloc>& __lhs, 501 const vector<_Tp, _Alloc>& __rhs) 502 { return __lhs._M_base() == __rhs._M_base(); } 503 504 template<typename _Tp, typename _Alloc> 505 inline bool 506 operator!=(const vector<_Tp, _Alloc>& __lhs, 507 const vector<_Tp, _Alloc>& __rhs) 508 { return __lhs._M_base() != __rhs._M_base(); } 509 510 template<typename _Tp, typename _Alloc> 511 inline bool 512 operator<(const vector<_Tp, _Alloc>& __lhs, 513 const vector<_Tp, _Alloc>& __rhs) 514 { return __lhs._M_base() < __rhs._M_base(); } 515 516 template<typename _Tp, typename _Alloc> 517 inline bool 518 operator<=(const vector<_Tp, _Alloc>& __lhs, 519 const vector<_Tp, _Alloc>& __rhs) 520 { return __lhs._M_base() <= __rhs._M_base(); } 521 522 template<typename _Tp, typename _Alloc> 523 inline bool 524 operator>=(const vector<_Tp, _Alloc>& __lhs, 525 const vector<_Tp, _Alloc>& __rhs) 526 { return __lhs._M_base() >= __rhs._M_base(); } 527 528 template<typename _Tp, typename _Alloc> 529 inline bool 530 operator>(const vector<_Tp, _Alloc>& __lhs, 531 const vector<_Tp, _Alloc>& __rhs) 532 { return __lhs._M_base() > __rhs._M_base(); } 533 534 template<typename _Tp, typename _Alloc> 535 inline void 536 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 537 { __lhs.swap(__rhs); } 538 539} // namespace __debug 540 541#ifdef __GXX_EXPERIMENTAL_CXX0X__ 542 // DR 1182. 543 /// std::hash specialization for vector<bool>. 544 template<typename _Alloc> 545 struct hash<__debug::vector<bool, _Alloc>> 546 : public std::unary_function<__debug::vector<bool, _Alloc>, size_t> 547 { 548 size_t 549 operator()(const __debug::vector<bool, _Alloc>& __b) const 550 { return std::hash<_GLIBCXX_STD_D::vector<bool, _Alloc>>() 551 (__b._M_base()); } 552 }; 553#endif 554 555} // namespace std 556 557#endif 558