1 // Debugging vector implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 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 38 namespace std _GLIBCXX_VISIBILITY(default) 39 { 40 namespace __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_C::vector<_Tp, _Allocator>, 47 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > 48 { 49 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base; 50 51 typedef typename _Base::iterator _Base_iterator; 52 typedef typename _Base::const_iterator _Base_const_iterator; 53 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 54 55 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 56 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits; 57 #endif 58 59 public: 60 typedef typename _Base::reference reference; 61 typedef typename _Base::const_reference const_reference; 62 63 typedef __gnu_debug::_Safe_iterator<_Base_iterator,vector> 64 iterator; 65 typedef __gnu_debug::_Safe_iterator<_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 80 vector(const _Allocator& __a = _Allocator()) 81 : _Base(__a), _M_guaranteed_capacity(0) { } 82 83 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 84 explicit 85 vector(size_type __n) 86 : _Base(__n), _M_guaranteed_capacity(__n) { } 87 88 vector(size_type __n, const _Tp& __value, 89 const _Allocator& __a = _Allocator()) 90 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 91 #else 92 explicit 93 vector(size_type __n, const _Tp& __value = _Tp(), 94 const _Allocator& __a = _Allocator()) 95 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 96 #endif 97 98 template<class _InputIterator> 99 vector(_InputIterator __first, _InputIterator __last, 100 const _Allocator& __a = _Allocator()) 101 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 102 __last)), 103 __gnu_debug::__base(__last), __a), 104 _M_guaranteed_capacity(0) 105 { _M_update_guaranteed_capacity(); } 106 107 vector(const vector& __x) 108 : _Base(__x), _M_guaranteed_capacity(__x.size()) { } 109 110 /// Construction from a release-mode vector 111 vector(const _Base& __x) 112 : _Base(__x), _M_guaranteed_capacity(__x.size()) { } 113 114 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 115 vector(vector&& __x) noexcept 116 : _Base(std::move(__x)), 117 _M_guaranteed_capacity(this->size()) 118 { 119 this->_M_swap(__x); 120 __x._M_guaranteed_capacity = 0; 121 } 122 123 vector(const vector& __x, const allocator_type& __a) 124 : _Base(__x, __a), _M_guaranteed_capacity(__x.size()) { } 125 126 vector(vector&& __x, const allocator_type& __a) 127 : _Base(std::move(__x), __a), 128 _M_guaranteed_capacity(this->size()) 129 { 130 __x._M_invalidate_all(); 131 __x._M_guaranteed_capacity = 0; 132 } 133 134 vector(initializer_list<value_type> __l, 135 const allocator_type& __a = allocator_type()) 136 : _Base(__l, __a), 137 _M_guaranteed_capacity(__l.size()) { } 138 #endif 139 140 ~vector() _GLIBCXX_NOEXCEPT { } 141 142 vector& 143 operator=(const vector& __x) 144 { 145 static_cast<_Base&>(*this) = __x; 146 this->_M_invalidate_all(); 147 _M_update_guaranteed_capacity(); 148 return *this; 149 } 150 151 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 152 vector& 153 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 154 { 155 _Base::operator=(std::move(__x)); 156 this->_M_invalidate_all(); 157 _M_update_guaranteed_capacity(); 158 __x._M_invalidate_all(); 159 __x._M_guaranteed_capacity = 0; 160 return *this; 161 } 162 163 vector& 164 operator=(initializer_list<value_type> __l) 165 { 166 static_cast<_Base&>(*this) = __l; 167 this->_M_invalidate_all(); 168 _M_update_guaranteed_capacity(); 169 return *this; 170 } 171 #endif 172 173 template<typename _InputIterator> 174 void 175 assign(_InputIterator __first, _InputIterator __last) 176 { 177 __glibcxx_check_valid_range(__first, __last); 178 _Base::assign(__gnu_debug::__base(__first), 179 __gnu_debug::__base(__last)); 180 this->_M_invalidate_all(); 181 _M_update_guaranteed_capacity(); 182 } 183 184 void 185 assign(size_type __n, const _Tp& __u) 186 { 187 _Base::assign(__n, __u); 188 this->_M_invalidate_all(); 189 _M_update_guaranteed_capacity(); 190 } 191 192 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 193 void 194 assign(initializer_list<value_type> __l) 195 { 196 _Base::assign(__l); 197 this->_M_invalidate_all(); 198 _M_update_guaranteed_capacity(); 199 } 200 #endif 201 202 using _Base::get_allocator; 203 204 // iterators: 205 iterator 206 begin() _GLIBCXX_NOEXCEPT 207 { return iterator(_Base::begin(), this); } 208 209 const_iterator 210 begin() const _GLIBCXX_NOEXCEPT 211 { return const_iterator(_Base::begin(), this); } 212 213 iterator 214 end() _GLIBCXX_NOEXCEPT 215 { return iterator(_Base::end(), this); } 216 217 const_iterator 218 end() const _GLIBCXX_NOEXCEPT 219 { return const_iterator(_Base::end(), this); } 220 221 reverse_iterator 222 rbegin() _GLIBCXX_NOEXCEPT 223 { return reverse_iterator(end()); } 224 225 const_reverse_iterator 226 rbegin() const _GLIBCXX_NOEXCEPT 227 { return const_reverse_iterator(end()); } 228 229 reverse_iterator 230 rend() _GLIBCXX_NOEXCEPT 231 { return reverse_iterator(begin()); } 232 233 const_reverse_iterator 234 rend() const _GLIBCXX_NOEXCEPT 235 { return const_reverse_iterator(begin()); } 236 237 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 238 const_iterator 239 cbegin() const noexcept 240 { return const_iterator(_Base::begin(), this); } 241 242 const_iterator 243 cend() const noexcept 244 { return const_iterator(_Base::end(), this); } 245 246 const_reverse_iterator 247 crbegin() const noexcept 248 { return const_reverse_iterator(end()); } 249 250 const_reverse_iterator 251 crend() const noexcept 252 { return const_reverse_iterator(begin()); } 253 #endif 254 255 // 23.2.4.2 capacity: 256 using _Base::size; 257 using _Base::max_size; 258 259 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 260 void 261 resize(size_type __sz) 262 { 263 bool __realloc = _M_requires_reallocation(__sz); 264 if (__sz < this->size()) 265 this->_M_invalidate_after_nth(__sz); 266 _Base::resize(__sz); 267 if (__realloc) 268 this->_M_invalidate_all(); 269 _M_update_guaranteed_capacity(); 270 } 271 272 void 273 resize(size_type __sz, const _Tp& __c) 274 { 275 bool __realloc = _M_requires_reallocation(__sz); 276 if (__sz < this->size()) 277 this->_M_invalidate_after_nth(__sz); 278 _Base::resize(__sz, __c); 279 if (__realloc) 280 this->_M_invalidate_all(); 281 _M_update_guaranteed_capacity(); 282 } 283 #else 284 void 285 resize(size_type __sz, _Tp __c = _Tp()) 286 { 287 bool __realloc = _M_requires_reallocation(__sz); 288 if (__sz < this->size()) 289 this->_M_invalidate_after_nth(__sz); 290 _Base::resize(__sz, __c); 291 if (__realloc) 292 this->_M_invalidate_all(); 293 _M_update_guaranteed_capacity(); 294 } 295 #endif 296 297 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 298 void 299 shrink_to_fit() 300 { 301 if (_Base::_M_shrink_to_fit()) 302 { 303 _M_guaranteed_capacity = _Base::capacity(); 304 this->_M_invalidate_all(); 305 } 306 } 307 #endif 308 309 size_type 310 capacity() const _GLIBCXX_NOEXCEPT 311 { 312 #ifdef _GLIBCXX_DEBUG_PEDANTIC 313 return _M_guaranteed_capacity; 314 #else 315 return _Base::capacity(); 316 #endif 317 } 318 319 using _Base::empty; 320 321 void 322 reserve(size_type __n) 323 { 324 bool __realloc = _M_requires_reallocation(__n); 325 _Base::reserve(__n); 326 if (__n > _M_guaranteed_capacity) 327 _M_guaranteed_capacity = __n; 328 if (__realloc) 329 this->_M_invalidate_all(); 330 } 331 332 // element access: 333 reference 334 operator[](size_type __n) 335 { 336 __glibcxx_check_subscript(__n); 337 return _M_base()[__n]; 338 } 339 340 const_reference 341 operator[](size_type __n) const 342 { 343 __glibcxx_check_subscript(__n); 344 return _M_base()[__n]; 345 } 346 347 using _Base::at; 348 349 reference 350 front() 351 { 352 __glibcxx_check_nonempty(); 353 return _Base::front(); 354 } 355 356 const_reference 357 front() const 358 { 359 __glibcxx_check_nonempty(); 360 return _Base::front(); 361 } 362 363 reference 364 back() 365 { 366 __glibcxx_check_nonempty(); 367 return _Base::back(); 368 } 369 370 const_reference 371 back() const 372 { 373 __glibcxx_check_nonempty(); 374 return _Base::back(); 375 } 376 377 // _GLIBCXX_RESOLVE_LIB_DEFECTS 378 // DR 464. Suggestion for new member functions in standard containers. 379 using _Base::data; 380 381 // 23.2.4.3 modifiers: 382 void 383 push_back(const _Tp& __x) 384 { 385 bool __realloc = _M_requires_reallocation(this->size() + 1); 386 _Base::push_back(__x); 387 if (__realloc) 388 this->_M_invalidate_all(); 389 _M_update_guaranteed_capacity(); 390 } 391 392 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 393 template<typename _Up = _Tp> 394 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 395 void>::__type 396 push_back(_Tp&& __x) 397 { emplace_back(std::move(__x)); } 398 399 template<typename... _Args> 400 void 401 emplace_back(_Args&&... __args) 402 { 403 bool __realloc = _M_requires_reallocation(this->size() + 1); 404 _Base::emplace_back(std::forward<_Args>(__args)...); 405 if (__realloc) 406 this->_M_invalidate_all(); 407 _M_update_guaranteed_capacity(); 408 } 409 #endif 410 411 void 412 pop_back() 413 { 414 __glibcxx_check_nonempty(); 415 this->_M_invalidate_if(_Equal(--_Base::end())); 416 _Base::pop_back(); 417 } 418 419 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 420 template<typename... _Args> 421 iterator 422 emplace(iterator __position, _Args&&... __args) 423 { 424 __glibcxx_check_insert(__position); 425 bool __realloc = _M_requires_reallocation(this->size() + 1); 426 difference_type __offset = __position.base() - _Base::begin(); 427 _Base_iterator __res = _Base::emplace(__position.base(), 428 std::forward<_Args>(__args)...); 429 if (__realloc) 430 this->_M_invalidate_all(); 431 else 432 this->_M_invalidate_after_nth(__offset); 433 _M_update_guaranteed_capacity(); 434 return iterator(__res, this); 435 } 436 #endif 437 438 iterator 439 insert(iterator __position, const _Tp& __x) 440 { 441 __glibcxx_check_insert(__position); 442 bool __realloc = _M_requires_reallocation(this->size() + 1); 443 difference_type __offset = __position.base() - _Base::begin(); 444 _Base_iterator __res = _Base::insert(__position.base(), __x); 445 if (__realloc) 446 this->_M_invalidate_all(); 447 else 448 this->_M_invalidate_after_nth(__offset); 449 _M_update_guaranteed_capacity(); 450 return iterator(__res, this); 451 } 452 453 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 454 template<typename _Up = _Tp> 455 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 456 iterator>::__type 457 insert(iterator __position, _Tp&& __x) 458 { return emplace(__position, std::move(__x)); } 459 460 void 461 insert(iterator __position, initializer_list<value_type> __l) 462 { this->insert(__position, __l.begin(), __l.end()); } 463 #endif 464 465 void 466 insert(iterator __position, size_type __n, const _Tp& __x) 467 { 468 __glibcxx_check_insert(__position); 469 bool __realloc = _M_requires_reallocation(this->size() + __n); 470 difference_type __offset = __position.base() - _Base::begin(); 471 _Base::insert(__position.base(), __n, __x); 472 if (__realloc) 473 this->_M_invalidate_all(); 474 else 475 this->_M_invalidate_after_nth(__offset); 476 _M_update_guaranteed_capacity(); 477 } 478 479 template<class _InputIterator> 480 void 481 insert(iterator __position, 482 _InputIterator __first, _InputIterator __last) 483 { 484 __glibcxx_check_insert_range(__position, __first, __last); 485 486 /* Hard to guess if invalidation will occur, because __last 487 - __first can't be calculated in all cases, so we just 488 punt here by checking if it did occur. */ 489 _Base_iterator __old_begin = _M_base().begin(); 490 difference_type __offset = __position.base() - _Base::begin(); 491 _Base::insert(__position.base(), __gnu_debug::__base(__first), 492 __gnu_debug::__base(__last)); 493 494 if (_M_base().begin() != __old_begin) 495 this->_M_invalidate_all(); 496 else 497 this->_M_invalidate_after_nth(__offset); 498 _M_update_guaranteed_capacity(); 499 } 500 501 iterator 502 erase(iterator __position) 503 { 504 __glibcxx_check_erase(__position); 505 difference_type __offset = __position.base() - _Base::begin(); 506 _Base_iterator __res = _Base::erase(__position.base()); 507 this->_M_invalidate_after_nth(__offset); 508 return iterator(__res, this); 509 } 510 511 iterator 512 erase(iterator __first, iterator __last) 513 { 514 // _GLIBCXX_RESOLVE_LIB_DEFECTS 515 // 151. can't currently clear() empty container 516 __glibcxx_check_erase_range(__first, __last); 517 518 if (__first.base() != __last.base()) 519 { 520 difference_type __offset = __first.base() - _Base::begin(); 521 _Base_iterator __res = _Base::erase(__first.base(), 522 __last.base()); 523 this->_M_invalidate_after_nth(__offset); 524 return iterator(__res, this); 525 } 526 else 527 return __first; 528 } 529 530 void 531 swap(vector& __x) 532 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 533 noexcept(_Alloc_traits::_S_nothrow_swap()) 534 #endif 535 { 536 _Base::swap(__x); 537 this->_M_swap(__x); 538 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity); 539 } 540 541 void 542 clear() _GLIBCXX_NOEXCEPT 543 { 544 _Base::clear(); 545 this->_M_invalidate_all(); 546 _M_guaranteed_capacity = 0; 547 } 548 549 _Base& 550 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 551 552 const _Base& 553 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 554 555 private: 556 size_type _M_guaranteed_capacity; 557 558 bool 559 _M_requires_reallocation(size_type __elements) 560 { return __elements > this->capacity(); } 561 562 void 563 _M_update_guaranteed_capacity() 564 { 565 if (this->size() > _M_guaranteed_capacity) 566 _M_guaranteed_capacity = this->size(); 567 } 568 569 void 570 _M_invalidate_after_nth(difference_type __n) 571 { 572 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 573 this->_M_invalidate_if(_After_nth(__n, _Base::begin())); 574 } 575 }; 576 577 template<typename _Tp, typename _Alloc> 578 inline bool 579 operator==(const vector<_Tp, _Alloc>& __lhs, 580 const vector<_Tp, _Alloc>& __rhs) 581 { return __lhs._M_base() == __rhs._M_base(); } 582 583 template<typename _Tp, typename _Alloc> 584 inline bool 585 operator!=(const vector<_Tp, _Alloc>& __lhs, 586 const vector<_Tp, _Alloc>& __rhs) 587 { return __lhs._M_base() != __rhs._M_base(); } 588 589 template<typename _Tp, typename _Alloc> 590 inline bool 591 operator<(const vector<_Tp, _Alloc>& __lhs, 592 const vector<_Tp, _Alloc>& __rhs) 593 { return __lhs._M_base() < __rhs._M_base(); } 594 595 template<typename _Tp, typename _Alloc> 596 inline bool 597 operator<=(const vector<_Tp, _Alloc>& __lhs, 598 const vector<_Tp, _Alloc>& __rhs) 599 { return __lhs._M_base() <= __rhs._M_base(); } 600 601 template<typename _Tp, typename _Alloc> 602 inline bool 603 operator>=(const vector<_Tp, _Alloc>& __lhs, 604 const vector<_Tp, _Alloc>& __rhs) 605 { return __lhs._M_base() >= __rhs._M_base(); } 606 607 template<typename _Tp, typename _Alloc> 608 inline bool 609 operator>(const vector<_Tp, _Alloc>& __lhs, 610 const vector<_Tp, _Alloc>& __rhs) 611 { return __lhs._M_base() > __rhs._M_base(); } 612 613 template<typename _Tp, typename _Alloc> 614 inline void 615 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 616 { __lhs.swap(__rhs); } 617 618 } // namespace __debug 619 620 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 621 // DR 1182. 622 /// std::hash specialization for vector<bool>. 623 template<typename _Alloc> 624 struct hash<__debug::vector<bool, _Alloc>> 625 : public __hash_base<size_t, __debug::vector<bool, _Alloc>> 626 { 627 size_t 628 operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept 629 { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>() 630 (__b._M_base()); } 631 }; 632 #endif 633 634 } // namespace std 635 636 #endif 637
