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