1// Debugging vector implementation -*- C++ -*- 2 3// Copyright (C) 2003-2014 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file debug/vector 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29#ifndef _GLIBCXX_DEBUG_VECTOR 30#define _GLIBCXX_DEBUG_VECTOR 1 31 32#include <vector> 33#include <utility> 34#include <debug/safe_sequence.h> 35#include <debug/safe_iterator.h> 36 37namespace std _GLIBCXX_VISIBILITY(default) 38{ 39namespace __debug 40{ 41 /// Class std::vector with safety/checking/debug instrumentation. 42 template<typename _Tp, 43 typename _Allocator = std::allocator<_Tp> > 44 class vector 45 : public _GLIBCXX_STD_C::vector<_Tp, _Allocator>, 46 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base; 49 50 typedef typename _Base::iterator _Base_iterator; 51 typedef typename _Base::const_iterator _Base_const_iterator; 52 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 53 54#if __cplusplus >= 201103L 55 typedef __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> > _Safe_base; 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 80 vector() _GLIBCXX_NOEXCEPT 81 : _Base(), _M_guaranteed_capacity(0) { } 82 83 explicit 84 vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT 85 : _Base(__a), _M_guaranteed_capacity(0) { } 86 87#if __cplusplus >= 201103L 88 explicit 89 vector(size_type __n, const _Allocator& __a = _Allocator()) 90 : _Base(__n, __a), _M_guaranteed_capacity(__n) { } 91 92 vector(size_type __n, const _Tp& __value, 93 const _Allocator& __a = _Allocator()) 94 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 95#else 96 explicit 97 vector(size_type __n, const _Tp& __value = _Tp(), 98 const _Allocator& __a = _Allocator()) 99 : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { } 100#endif 101 102#if __cplusplus >= 201103L 103 template<class _InputIterator, 104 typename = std::_RequireInputIter<_InputIterator>> 105#else 106 template<class _InputIterator> 107#endif 108 vector(_InputIterator __first, _InputIterator __last, 109 const _Allocator& __a = _Allocator()) 110 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 111 __last)), 112 __gnu_debug::__base(__last), __a), 113 _M_guaranteed_capacity(0) 114 { _M_update_guaranteed_capacity(); } 115 116 vector(const vector& __x) 117 : _Base(__x), _M_guaranteed_capacity(__x.size()) { } 118 119 /// Construction from a normal-mode vector 120 vector(const _Base& __x) 121 : _Base(__x), _M_guaranteed_capacity(__x.size()) { } 122 123#if __cplusplus >= 201103L 124 vector(vector&& __x) noexcept 125 : _Base(std::move(__x)), 126 _Safe_base(std::move(__x)), 127 _M_guaranteed_capacity(this->size()) 128 { __x._M_guaranteed_capacity = 0; } 129 130 vector(const vector& __x, const allocator_type& __a) 131 : _Base(__x, __a), _M_guaranteed_capacity(__x.size()) { } 132 133 vector(vector&& __x, const allocator_type& __a) 134 : _Base(std::move(__x), __a), 135 _M_guaranteed_capacity(this->size()) 136 { 137 if (__x.get_allocator() == __a) 138 this->_M_swap(__x); 139 else 140 __x._M_invalidate_all(); 141 __x._M_guaranteed_capacity = 0; 142 } 143 144 vector(initializer_list<value_type> __l, 145 const allocator_type& __a = allocator_type()) 146 : _Base(__l, __a), 147 _M_guaranteed_capacity(__l.size()) { } 148#endif 149 150 ~vector() _GLIBCXX_NOEXCEPT { } 151 152 vector& 153 operator=(const vector& __x) 154 { 155 _M_base() = __x; 156 this->_M_invalidate_all(); 157 _M_update_guaranteed_capacity(); 158 return *this; 159 } 160 161#if __cplusplus >= 201103L 162 vector& 163 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 164 { 165 __glibcxx_check_self_move_assign(__x); 166 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 167 || __x.get_allocator() == this->get_allocator(); 168 _M_base() = std::move(__x._M_base()); 169 if (__xfer_memory) 170 this->_M_swap(__x); 171 else 172 this->_M_invalidate_all(); 173 _M_update_guaranteed_capacity(); 174 __x._M_invalidate_all(); 175 __x._M_guaranteed_capacity = 0; 176 return *this; 177 } 178 179 vector& 180 operator=(initializer_list<value_type> __l) 181 { 182 _M_base() = __l; 183 this->_M_invalidate_all(); 184 _M_update_guaranteed_capacity(); 185 return *this; 186 } 187#endif 188 189#if __cplusplus >= 201103L 190 template<typename _InputIterator, 191 typename = std::_RequireInputIter<_InputIterator>> 192#else 193 template<typename _InputIterator> 194#endif 195 void 196 assign(_InputIterator __first, _InputIterator __last) 197 { 198 __glibcxx_check_valid_range(__first, __last); 199 _Base::assign(__gnu_debug::__base(__first), 200 __gnu_debug::__base(__last)); 201 this->_M_invalidate_all(); 202 _M_update_guaranteed_capacity(); 203 } 204 205 void 206 assign(size_type __n, const _Tp& __u) 207 { 208 _Base::assign(__n, __u); 209 this->_M_invalidate_all(); 210 _M_update_guaranteed_capacity(); 211 } 212 213#if __cplusplus >= 201103L 214 void 215 assign(initializer_list<value_type> __l) 216 { 217 _Base::assign(__l); 218 this->_M_invalidate_all(); 219 _M_update_guaranteed_capacity(); 220 } 221#endif 222 223 using _Base::get_allocator; 224 225 // iterators: 226 iterator 227 begin() _GLIBCXX_NOEXCEPT 228 { return iterator(_Base::begin(), this); } 229 230 const_iterator 231 begin() const _GLIBCXX_NOEXCEPT 232 { return const_iterator(_Base::begin(), this); } 233 234 iterator 235 end() _GLIBCXX_NOEXCEPT 236 { return iterator(_Base::end(), this); } 237 238 const_iterator 239 end() const _GLIBCXX_NOEXCEPT 240 { return const_iterator(_Base::end(), this); } 241 242 reverse_iterator 243 rbegin() _GLIBCXX_NOEXCEPT 244 { return reverse_iterator(end()); } 245 246 const_reverse_iterator 247 rbegin() const _GLIBCXX_NOEXCEPT 248 { return const_reverse_iterator(end()); } 249 250 reverse_iterator 251 rend() _GLIBCXX_NOEXCEPT 252 { return reverse_iterator(begin()); } 253 254 const_reverse_iterator 255 rend() const _GLIBCXX_NOEXCEPT 256 { return const_reverse_iterator(begin()); } 257 258#if __cplusplus >= 201103L 259 const_iterator 260 cbegin() const noexcept 261 { return const_iterator(_Base::begin(), this); } 262 263 const_iterator 264 cend() const noexcept 265 { return const_iterator(_Base::end(), this); } 266 267 const_reverse_iterator 268 crbegin() const noexcept 269 { return const_reverse_iterator(end()); } 270 271 const_reverse_iterator 272 crend() const noexcept 273 { return const_reverse_iterator(begin()); } 274#endif 275 276 // 23.2.4.2 capacity: 277 using _Base::size; 278 using _Base::max_size; 279 280#if __cplusplus >= 201103L 281 void 282 resize(size_type __sz) 283 { 284 bool __realloc = _M_requires_reallocation(__sz); 285 if (__sz < this->size()) 286 this->_M_invalidate_after_nth(__sz); 287 _Base::resize(__sz); 288 if (__realloc) 289 this->_M_invalidate_all(); 290 _M_update_guaranteed_capacity(); 291 } 292 293 void 294 resize(size_type __sz, const _Tp& __c) 295 { 296 bool __realloc = _M_requires_reallocation(__sz); 297 if (__sz < this->size()) 298 this->_M_invalidate_after_nth(__sz); 299 _Base::resize(__sz, __c); 300 if (__realloc) 301 this->_M_invalidate_all(); 302 _M_update_guaranteed_capacity(); 303 } 304#else 305 void 306 resize(size_type __sz, _Tp __c = _Tp()) 307 { 308 bool __realloc = _M_requires_reallocation(__sz); 309 if (__sz < this->size()) 310 this->_M_invalidate_after_nth(__sz); 311 _Base::resize(__sz, __c); 312 if (__realloc) 313 this->_M_invalidate_all(); 314 _M_update_guaranteed_capacity(); 315 } 316#endif 317 318#if __cplusplus >= 201103L 319 void 320 shrink_to_fit() 321 { 322 if (_Base::_M_shrink_to_fit()) 323 { 324 _M_guaranteed_capacity = _Base::capacity(); 325 this->_M_invalidate_all(); 326 } 327 } 328#endif 329 330 size_type 331 capacity() const _GLIBCXX_NOEXCEPT 332 { 333#ifdef _GLIBCXX_DEBUG_PEDANTIC 334 return _M_guaranteed_capacity; 335#else 336 return _Base::capacity(); 337#endif 338 } 339 340 using _Base::empty; 341 342 void 343 reserve(size_type __n) 344 { 345 bool __realloc = _M_requires_reallocation(__n); 346 _Base::reserve(__n); 347 if (__n > _M_guaranteed_capacity) 348 _M_guaranteed_capacity = __n; 349 if (__realloc) 350 this->_M_invalidate_all(); 351 } 352 353 // element access: 354 reference 355 operator[](size_type __n) _GLIBCXX_NOEXCEPT 356 { 357 __glibcxx_check_subscript(__n); 358 return _M_base()[__n]; 359 } 360 361 const_reference 362 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 363 { 364 __glibcxx_check_subscript(__n); 365 return _M_base()[__n]; 366 } 367 368 using _Base::at; 369 370 reference 371 front() _GLIBCXX_NOEXCEPT 372 { 373 __glibcxx_check_nonempty(); 374 return _Base::front(); 375 } 376 377 const_reference 378 front() const _GLIBCXX_NOEXCEPT 379 { 380 __glibcxx_check_nonempty(); 381 return _Base::front(); 382 } 383 384 reference 385 back() _GLIBCXX_NOEXCEPT 386 { 387 __glibcxx_check_nonempty(); 388 return _Base::back(); 389 } 390 391 const_reference 392 back() const _GLIBCXX_NOEXCEPT 393 { 394 __glibcxx_check_nonempty(); 395 return _Base::back(); 396 } 397 398 // _GLIBCXX_RESOLVE_LIB_DEFECTS 399 // DR 464. Suggestion for new member functions in standard containers. 400 using _Base::data; 401 402 // 23.2.4.3 modifiers: 403 void 404 push_back(const _Tp& __x) 405 { 406 bool __realloc = _M_requires_reallocation(this->size() + 1); 407 _Base::push_back(__x); 408 if (__realloc) 409 this->_M_invalidate_all(); 410 _M_update_guaranteed_capacity(); 411 } 412 413#if __cplusplus >= 201103L 414 template<typename _Up = _Tp> 415 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 416 void>::__type 417 push_back(_Tp&& __x) 418 { emplace_back(std::move(__x)); } 419 420 template<typename... _Args> 421 void 422 emplace_back(_Args&&... __args) 423 { 424 bool __realloc = _M_requires_reallocation(this->size() + 1); 425 _Base::emplace_back(std::forward<_Args>(__args)...); 426 if (__realloc) 427 this->_M_invalidate_all(); 428 _M_update_guaranteed_capacity(); 429 } 430#endif 431 432 void 433 pop_back() _GLIBCXX_NOEXCEPT 434 { 435 __glibcxx_check_nonempty(); 436 this->_M_invalidate_if(_Equal(--_Base::end())); 437 _Base::pop_back(); 438 } 439 440#if __cplusplus >= 201103L 441 template<typename... _Args> 442 iterator 443 emplace(const_iterator __position, _Args&&... __args) 444 { 445 __glibcxx_check_insert(__position); 446 bool __realloc = _M_requires_reallocation(this->size() + 1); 447 difference_type __offset = __position.base() - _Base::begin(); 448 _Base_iterator __res = _Base::emplace(__position.base(), 449 std::forward<_Args>(__args)...); 450 if (__realloc) 451 this->_M_invalidate_all(); 452 else 453 this->_M_invalidate_after_nth(__offset); 454 _M_update_guaranteed_capacity(); 455 return iterator(__res, this); 456 } 457#endif 458 459 iterator 460#if __cplusplus >= 201103L 461 insert(const_iterator __position, const _Tp& __x) 462#else 463 insert(iterator __position, const _Tp& __x) 464#endif 465 { 466 __glibcxx_check_insert(__position); 467 bool __realloc = _M_requires_reallocation(this->size() + 1); 468 difference_type __offset = __position.base() - _Base::begin(); 469 _Base_iterator __res = _Base::insert(__position.base(), __x); 470 if (__realloc) 471 this->_M_invalidate_all(); 472 else 473 this->_M_invalidate_after_nth(__offset); 474 _M_update_guaranteed_capacity(); 475 return iterator(__res, this); 476 } 477 478#if __cplusplus >= 201103L 479 template<typename _Up = _Tp> 480 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 481 iterator>::__type 482 insert(const_iterator __position, _Tp&& __x) 483 { return emplace(__position, std::move(__x)); } 484 485 iterator 486 insert(const_iterator __position, initializer_list<value_type> __l) 487 { return this->insert(__position, __l.begin(), __l.end()); } 488#endif 489 490#if __cplusplus >= 201103L 491 iterator 492 insert(const_iterator __position, size_type __n, const _Tp& __x) 493 { 494 __glibcxx_check_insert(__position); 495 bool __realloc = _M_requires_reallocation(this->size() + __n); 496 difference_type __offset = __position.base() - _Base::cbegin(); 497 _Base_iterator __res = _Base::insert(__position.base(), __n, __x); 498 if (__realloc) 499 this->_M_invalidate_all(); 500 else 501 this->_M_invalidate_after_nth(__offset); 502 _M_update_guaranteed_capacity(); 503 return iterator(__res, this); 504 } 505#else 506 void 507 insert(iterator __position, size_type __n, const _Tp& __x) 508 { 509 __glibcxx_check_insert(__position); 510 bool __realloc = _M_requires_reallocation(this->size() + __n); 511 difference_type __offset = __position.base() - _Base::begin(); 512 _Base::insert(__position.base(), __n, __x); 513 if (__realloc) 514 this->_M_invalidate_all(); 515 else 516 this->_M_invalidate_after_nth(__offset); 517 _M_update_guaranteed_capacity(); 518 } 519#endif 520 521#if __cplusplus >= 201103L 522 template<class _InputIterator, 523 typename = std::_RequireInputIter<_InputIterator>> 524 iterator 525 insert(const_iterator __position, 526 _InputIterator __first, _InputIterator __last) 527 { 528 __glibcxx_check_insert_range(__position, __first, __last); 529 530 /* Hard to guess if invalidation will occur, because __last 531 - __first can't be calculated in all cases, so we just 532 punt here by checking if it did occur. */ 533 _Base_iterator __old_begin = _M_base().begin(); 534 difference_type __offset = __position.base() - _Base::cbegin(); 535 _Base_iterator __res = _Base::insert(__position.base(), 536 __gnu_debug::__base(__first), 537 __gnu_debug::__base(__last)); 538 539 if (_M_base().begin() != __old_begin) 540 this->_M_invalidate_all(); 541 else 542 this->_M_invalidate_after_nth(__offset); 543 _M_update_guaranteed_capacity(); 544 return iterator(__res, this); 545 } 546#else 547 template<class _InputIterator> 548 void 549 insert(iterator __position, 550 _InputIterator __first, _InputIterator __last) 551 { 552 __glibcxx_check_insert_range(__position, __first, __last); 553 554 /* Hard to guess if invalidation will occur, because __last 555 - __first can't be calculated in all cases, so we just 556 punt here by checking if it did occur. */ 557 _Base_iterator __old_begin = _M_base().begin(); 558 difference_type __offset = __position.base() - _Base::begin(); 559 _Base::insert(__position.base(), __gnu_debug::__base(__first), 560 __gnu_debug::__base(__last)); 561 562 if (_M_base().begin() != __old_begin) 563 this->_M_invalidate_all(); 564 else 565 this->_M_invalidate_after_nth(__offset); 566 _M_update_guaranteed_capacity(); 567 } 568#endif 569 570 iterator 571#if __cplusplus >= 201103L 572 erase(const_iterator __position) 573#else 574 erase(iterator __position) 575#endif 576 { 577 __glibcxx_check_erase(__position); 578 difference_type __offset = __position.base() - _Base::begin(); 579 _Base_iterator __res = _Base::erase(__position.base()); 580 this->_M_invalidate_after_nth(__offset); 581 return iterator(__res, this); 582 } 583 584 iterator 585#if __cplusplus >= 201103L 586 erase(const_iterator __first, const_iterator __last) 587#else 588 erase(iterator __first, iterator __last) 589#endif 590 { 591 // _GLIBCXX_RESOLVE_LIB_DEFECTS 592 // 151. can't currently clear() empty container 593 __glibcxx_check_erase_range(__first, __last); 594 595 if (__first.base() != __last.base()) 596 { 597 difference_type __offset = __first.base() - _Base::begin(); 598 _Base_iterator __res = _Base::erase(__first.base(), 599 __last.base()); 600 this->_M_invalidate_after_nth(__offset); 601 return iterator(__res, this); 602 } 603 else 604#if __cplusplus >= 201103L 605 return begin() + (__first.base() - cbegin().base()); 606#else 607 return __first; 608#endif 609 } 610 611 void 612 swap(vector& __x) 613#if __cplusplus >= 201103L 614 noexcept(_Alloc_traits::_S_nothrow_swap()) 615#endif 616 { 617#if __cplusplus >= 201103L 618 if (!_Alloc_traits::_S_propagate_on_swap()) 619 __glibcxx_check_equal_allocs(__x); 620#endif 621 _Base::swap(__x); 622 this->_M_swap(__x); 623 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity); 624 } 625 626 void 627 clear() _GLIBCXX_NOEXCEPT 628 { 629 _Base::clear(); 630 this->_M_invalidate_all(); 631 _M_guaranteed_capacity = 0; 632 } 633 634 _Base& 635 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 636 637 const _Base& 638 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 639 640 private: 641 size_type _M_guaranteed_capacity; 642 643 bool 644 _M_requires_reallocation(size_type __elements) _GLIBCXX_NOEXCEPT 645 { return __elements > this->capacity(); } 646 647 void 648 _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT 649 { 650 if (this->size() > _M_guaranteed_capacity) 651 _M_guaranteed_capacity = this->size(); 652 } 653 654 void 655 _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT 656 { 657 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 658 this->_M_invalidate_if(_After_nth(__n, _Base::begin())); 659 } 660 }; 661 662 template<typename _Tp, typename _Alloc> 663 inline bool 664 operator==(const vector<_Tp, _Alloc>& __lhs, 665 const vector<_Tp, _Alloc>& __rhs) 666 { return __lhs._M_base() == __rhs._M_base(); } 667 668 template<typename _Tp, typename _Alloc> 669 inline bool 670 operator!=(const vector<_Tp, _Alloc>& __lhs, 671 const vector<_Tp, _Alloc>& __rhs) 672 { return __lhs._M_base() != __rhs._M_base(); } 673 674 template<typename _Tp, typename _Alloc> 675 inline bool 676 operator<(const vector<_Tp, _Alloc>& __lhs, 677 const vector<_Tp, _Alloc>& __rhs) 678 { return __lhs._M_base() < __rhs._M_base(); } 679 680 template<typename _Tp, typename _Alloc> 681 inline bool 682 operator<=(const vector<_Tp, _Alloc>& __lhs, 683 const vector<_Tp, _Alloc>& __rhs) 684 { return __lhs._M_base() <= __rhs._M_base(); } 685 686 template<typename _Tp, typename _Alloc> 687 inline bool 688 operator>=(const vector<_Tp, _Alloc>& __lhs, 689 const vector<_Tp, _Alloc>& __rhs) 690 { return __lhs._M_base() >= __rhs._M_base(); } 691 692 template<typename _Tp, typename _Alloc> 693 inline bool 694 operator>(const vector<_Tp, _Alloc>& __lhs, 695 const vector<_Tp, _Alloc>& __rhs) 696 { return __lhs._M_base() > __rhs._M_base(); } 697 698 template<typename _Tp, typename _Alloc> 699 inline void 700 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 701 { __lhs.swap(__rhs); } 702 703} // namespace __debug 704 705#if __cplusplus >= 201103L 706 // DR 1182. 707 /// std::hash specialization for vector<bool>. 708 template<typename _Alloc> 709 struct hash<__debug::vector<bool, _Alloc>> 710 : public __hash_base<size_t, __debug::vector<bool, _Alloc>> 711 { 712 size_t 713 operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept 714 { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>() 715 (__b._M_base()); } 716 }; 717#endif 718 719} // namespace std 720 721namespace __gnu_debug 722{ 723 template<typename _Tp, typename _Alloc> 724 struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> > 725 : std::__true_type 726 { }; 727 728 template<typename _Alloc> 729 struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> > 730 : std::__false_type 731 { }; 732} 733 734#endif 735