l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.8/include/debug/vector

   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