release/src-rt-6.x.4708/toolchains/hndtools-arm-linux-2.6.36-uclibc-4.5.3/arm-brcm-linux-uclibcgnueabi/include/c++/4.5.3/debug/list

   1 // Debugging list 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/list
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_LIST
  31 #define _GLIBCXX_DEBUG_LIST 1
  32
  33 #include <list>
  34 #include <debug/safe_sequence.h>
  35 #include <debug/safe_iterator.h>
  36
  37 namespace std
  38 {
  39 namespace __debug
  40 {
  41   /// Class std::list with safety/checking/debug instrumentation.
  42   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  43     class list
  44     : public _GLIBCXX_STD_D::list<_Tp, _Allocator>,
  45       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
  46     {
  47       typedef _GLIBCXX_STD_D::list<_Tp, _Allocator> _Base;
  48       typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
  49
  50     public:
  51       typedef typename _Base::reference             reference;
  52       typedef typename _Base::const_reference       const_reference;
  53
  54       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
  55                                                     iterator;
  56       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
  57                                                     const_iterator;
  58
  59       typedef typename _Base::size_type             size_type;
  60       typedef typename _Base::difference_type       difference_type;
  61
  62       typedef _Tp                                   value_type;
  63       typedef _Allocator                            allocator_type;
  64       typedef typename _Base::pointer               pointer;
  65       typedef typename _Base::const_pointer         const_pointer;
  66       typedef std::reverse_iterator<iterator>       reverse_iterator;
  67       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  68
  69       // 23.2.2.1 construct/copy/destroy:
  70       explicit list(const _Allocator& __a = _Allocator())
  71       : _Base(__a) { }
  72
  73       explicit list(size_type __n, const _Tp& __value = _Tp(),
  74                     const _Allocator& __a = _Allocator())
  75       : _Base(__n, __value, __a) { }
  76
  77       template<class _InputIterator>
  78       list(_InputIterator __first, _InputIterator __last,
  79            const _Allocator& __a = _Allocator())
  80       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
  81       { }
  82
  83
  84       list(const list& __x)
  85       : _Base(__x), _Safe_base() { }
  86
  87       list(const _Base& __x)
  88       : _Base(__x), _Safe_base() { }
  89
  90 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  91       list(list&& __x)
  92       : _Base(std::forward<list>(__x)), _Safe_base()
  93       { this->_M_swap(__x); }
  94
  95       list(initializer_list<value_type> __l,
  96            const allocator_type& __a = allocator_type())
  97         : _Base(__l, __a), _Safe_base() { }
  98 #endif
  99
 100       ~list() { }
 101
 102       list&
 103       operator=(const list& __x)
 104       {
 105         static_cast<_Base&>(*this) = __x;
 106         this->_M_invalidate_all();
 107         return *this;
 108       }
 109
 110 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 111       list&
 112       operator=(list&& __x)
 113       {
 114         // NB: DR 1204.
 115         // NB: DR 675.
 116         clear();
 117         swap(__x);
 118         return *this;
 119       }
 120
 121       list&
 122       operator=(initializer_list<value_type> __l)
 123       {
 124         static_cast<_Base&>(*this) = __l;
 125         this->_M_invalidate_all();
 126         return *this;
 127       }
 128
 129       void
 130       assign(initializer_list<value_type> __l)
 131       {
 132         _Base::assign(__l);
 133         this->_M_invalidate_all();
 134       }
 135 #endif
 136
 137       template<class _InputIterator>
 138         void
 139         assign(_InputIterator __first, _InputIterator __last)
 140         {
 141           __glibcxx_check_valid_range(__first, __last);
 142           _Base::assign(__first, __last);
 143           this->_M_invalidate_all();
 144         }
 145
 146       void
 147       assign(size_type __n, const _Tp& __t)
 148       {
 149         _Base::assign(__n, __t);
 150         this->_M_invalidate_all();
 151       }
 152
 153       using _Base::get_allocator;
 154
 155       // iterators:
 156       iterator
 157       begin()
 158       { return iterator(_Base::begin(), this); }
 159
 160       const_iterator
 161       begin() const
 162       { return const_iterator(_Base::begin(), this); }
 163
 164       iterator
 165       end()
 166       { return iterator(_Base::end(), this); }
 167
 168       const_iterator
 169       end() const
 170       { return const_iterator(_Base::end(), this); }
 171
 172       reverse_iterator
 173       rbegin()
 174       { return reverse_iterator(end()); }
 175
 176       const_reverse_iterator
 177       rbegin() const
 178       { return const_reverse_iterator(end()); }
 179
 180       reverse_iterator
 181       rend()
 182       { return reverse_iterator(begin()); }
 183
 184       const_reverse_iterator
 185       rend() const
 186       { return const_reverse_iterator(begin()); }
 187
 188 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 189       const_iterator
 190       cbegin() const
 191       { return const_iterator(_Base::begin(), this); }
 192
 193       const_iterator
 194       cend() const
 195       { return const_iterator(_Base::end(), this); }
 196
 197       const_reverse_iterator
 198       crbegin() const
 199       { return const_reverse_iterator(end()); }
 200
 201       const_reverse_iterator
 202       crend() const
 203       { return const_reverse_iterator(begin()); }
 204 #endif
 205
 206       // 23.2.2.2 capacity:
 207       using _Base::empty;
 208       using _Base::size;
 209       using _Base::max_size;
 210
 211       void
 212       resize(size_type __sz, _Tp __c = _Tp())
 213       {
 214         this->_M_detach_singular();
 215
 216         // if __sz < size(), invalidate all iterators in [begin+__sz, end())
 217         iterator __victim = begin();
 218         iterator __end = end();
 219         for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 220           ++__victim;
 221
 222         while (__victim != __end)
 223           {
 224             iterator __real_victim = __victim++;
 225             __real_victim._M_invalidate();
 226           }
 227
 228         __try
 229           {
 230             _Base::resize(__sz, __c);
 231           }
 232         __catch(...)
 233           {
 234             this->_M_revalidate_singular();
 235             __throw_exception_again;
 236           }
 237       }
 238
 239       // element access:
 240       reference
 241       front()
 242       {
 243         __glibcxx_check_nonempty();
 244         return _Base::front();
 245       }
 246
 247       const_reference
 248       front() const
 249       {
 250         __glibcxx_check_nonempty();
 251         return _Base::front();
 252       }
 253
 254       reference
 255       back()
 256       {
 257         __glibcxx_check_nonempty();
 258         return _Base::back();
 259       }
 260
 261       const_reference
 262       back() const
 263       {
 264         __glibcxx_check_nonempty();
 265         return _Base::back();
 266       }
 267
 268       // 23.2.2.3 modifiers:
 269       using _Base::push_front;
 270
 271 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 272       using _Base::emplace_front;
 273 #endif
 274
 275       void
 276       pop_front()
 277       {
 278         __glibcxx_check_nonempty();
 279         iterator __victim = begin();
 280         __victim._M_invalidate();
 281         _Base::pop_front();
 282       }
 283
 284       using _Base::push_back;
 285
 286 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 287       using _Base::emplace_back;
 288 #endif
 289
 290       void
 291       pop_back()
 292       {
 293         __glibcxx_check_nonempty();
 294         iterator __victim = end();
 295         --__victim;
 296         __victim._M_invalidate();
 297         _Base::pop_back();
 298       }
 299
 300 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 301       template<typename... _Args>
 302         iterator
 303         emplace(iterator __position, _Args&&... __args)
 304         {
 305           __glibcxx_check_insert(__position);
 306           return iterator(_Base::emplace(__position.base(),
 307                                         std::forward<_Args>(__args)...), this);
 308         }
 309 #endif
 310
 311       iterator
 312       insert(iterator __position, const _Tp& __x)
 313       {
 314         __glibcxx_check_insert(__position);
 315         return iterator(_Base::insert(__position.base(), __x), this);
 316       }
 317
 318 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 319       iterator
 320       insert(iterator __position, _Tp&& __x)
 321       { return emplace(__position, std::move(__x)); }
 322
 323       void
 324       insert(iterator __p, initializer_list<value_type> __l)
 325       {
 326         __glibcxx_check_insert(__p);
 327         _Base::insert(__p, __l);
 328       }
 329 #endif
 330
 331       void
 332       insert(iterator __position, size_type __n, const _Tp& __x)
 333       {
 334         __glibcxx_check_insert(__position);
 335         _Base::insert(__position.base(), __n, __x);
 336       }
 337
 338       template<class _InputIterator>
 339         void
 340         insert(iterator __position, _InputIterator __first,
 341                _InputIterator __last)
 342         {
 343           __glibcxx_check_insert_range(__position, __first, __last);
 344           _Base::insert(__position.base(), __first, __last);
 345         }
 346
 347       iterator
 348       erase(iterator __position)
 349       {
 350         __glibcxx_check_erase(__position);
 351         __position._M_invalidate();
 352         return iterator(_Base::erase(__position.base()), this);
 353       }
 354
 355       iterator
 356       erase(iterator __position, iterator __last)
 357       {
 358         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 359         // 151. can't currently clear() empty container
 360         __glibcxx_check_erase_range(__position, __last);
 361         for (iterator __victim = __position; __victim != __last; )
 362           {
 363             iterator __old = __victim;
 364             ++__victim;
 365             __old._M_invalidate();
 366           }
 367         return iterator(_Base::erase(__position.base(), __last.base()), this);
 368       }
 369
 370       void
 371       swap(list& __x)
 372       {
 373         _Base::swap(__x);
 374         this->_M_swap(__x);
 375       }
 376
 377       void
 378       clear()
 379       {
 380         _Base::clear();
 381         this->_M_invalidate_all();
 382       }
 383
 384       // 23.2.2.4 list operations:
 385       void
 386 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 387       splice(iterator __position, list&& __x)
 388 #else
 389       splice(iterator __position, list& __x)
 390 #endif
 391       {
 392         _GLIBCXX_DEBUG_VERIFY(&__x != this,
 393                               _M_message(__gnu_debug::__msg_self_splice)
 394                               ._M_sequence(*this, "this"));
 395         this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
 396       }
 397
 398 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 399       void
 400       splice(iterator __position, list& __x)
 401       { splice(__position, std::move(__x)); }
 402 #endif
 403
 404       void
 405 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 406       splice(iterator __position, list&& __x, iterator __i)
 407 #else
 408       splice(iterator __position, list& __x, iterator __i)
 409 #endif
 410       {
 411         __glibcxx_check_insert(__position);
 412
 413         // We used to perform the splice_alloc check:  not anymore, redundant
 414         // after implementing the relevant bits of N1599.
 415
 416         _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
 417                               _M_message(__gnu_debug::__msg_splice_bad)
 418                               ._M_iterator(__i, "__i"));
 419         _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
 420                               _M_message(__gnu_debug::__msg_splice_other)
 421                              ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
 422
 423         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 424         // 250. splicing invalidates iterators
 425         this->_M_transfer_iter(__i);
 426         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 427                       __i.base());
 428       }
 429
 430 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 431       void
 432       splice(iterator __position, list& __x, iterator __i)
 433       { splice(__position, std::move(__x), __i); }
 434 #endif
 435
 436       void
 437 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 438       splice(iterator __position, list&& __x, iterator __first,
 439              iterator __last)
 440 #else
 441       splice(iterator __position, list& __x, iterator __first,
 442              iterator __last)
 443 #endif
 444       {
 445         __glibcxx_check_insert(__position);
 446         __glibcxx_check_valid_range(__first, __last);
 447         _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
 448                               _M_message(__gnu_debug::__msg_splice_other)
 449                               ._M_sequence(__x, "x")
 450                               ._M_iterator(__first, "first"));
 451
 452         // We used to perform the splice_alloc check:  not anymore, redundant
 453         // after implementing the relevant bits of N1599.
 454
 455         for (iterator __tmp = __first; __tmp != __last; )
 456           {
 457             _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
 458                                 _M_message(__gnu_debug::__msg_splice_overlap)
 459                                   ._M_iterator(__tmp, "position")
 460                                   ._M_iterator(__first, "first")
 461                                   ._M_iterator(__last, "last"));
 462             iterator __victim = __tmp++;
 463             // _GLIBCXX_RESOLVE_LIB_DEFECTS
 464             // 250. splicing invalidates iterators
 465             this->_M_transfer_iter(__victim);
 466           }
 467
 468         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 469                       __first.base(), __last.base());
 470       }
 471
 472 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 473       void
 474       splice(iterator __position, list& __x, iterator __first, iterator __last)
 475       { splice(__position, std::move(__x), __first, __last); }
 476 #endif
 477
 478       void
 479       remove(const _Tp& __value)
 480       {
 481         for (iterator __x = begin(); __x.base() != _Base::end(); )
 482           {
 483             if (*__x == __value)
 484               __x = erase(__x);
 485             else
 486               ++__x;
 487           }
 488       }
 489
 490       template<class _Predicate>
 491         void
 492         remove_if(_Predicate __pred)
 493         {
 494           for (iterator __x = begin(); __x.base() != _Base::end(); )
 495             {
 496               if (__pred(*__x))
 497                 __x = erase(__x);
 498               else
 499                 ++__x;
 500             }
 501         }
 502
 503       void
 504       unique()
 505       {
 506         iterator __first = begin();
 507         iterator __last = end();
 508         if (__first == __last)
 509           return;
 510         iterator __next = __first;
 511         while (++__next != __last)
 512           {
 513             if (*__first == *__next)
 514               erase(__next);
 515             else
 516               __first = __next;
 517             __next = __first;
 518           }
 519       }
 520
 521       template<class _BinaryPredicate>
 522         void
 523         unique(_BinaryPredicate __binary_pred)
 524         {
 525           iterator __first = begin();
 526           iterator __last = end();
 527           if (__first == __last)
 528             return;
 529           iterator __next = __first;
 530           while (++__next != __last)
 531             {
 532               if (__binary_pred(*__first, *__next))
 533                 erase(__next);
 534               else
 535                 __first = __next;
 536               __next = __first;
 537             }
 538         }
 539
 540       void
 541 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 542       merge(list&& __x)
 543 #else
 544       merge(list& __x)
 545 #endif
 546       {
 547         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 548         // 300. list::merge() specification incomplete
 549         if (this != &__x)
 550           {
 551             __glibcxx_check_sorted(_Base::begin(), _Base::end());
 552             __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
 553             for (iterator __tmp = __x.begin(); __tmp != __x.end();)
 554               {
 555                 iterator __victim = __tmp++;
 556                 this->_M_transfer_iter(__victim);
 557               }
 558             _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
 559           }
 560       }
 561
 562 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 563       void
 564       merge(list& __x)
 565       { merge(std::move(__x)); }
 566 #endif
 567
 568       template<class _Compare>
 569         void
 570 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 571         merge(list&& __x, _Compare __comp)
 572 #else
 573         merge(list& __x, _Compare __comp)
 574 #endif
 575         {
 576           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 577           // 300. list::merge() specification incomplete
 578           if (this != &__x)
 579             {
 580               __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
 581                                           __comp);
 582               __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
 583                                           __comp);
 584               for (iterator __tmp = __x.begin(); __tmp != __x.end();)
 585                 {
 586                   iterator __victim = __tmp++;
 587                   this->_M_transfer_iter(__victim);
 588                 }
 589               _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
 590             }
 591         }
 592
 593 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 594       template<typename _Compare>
 595         void
 596         merge(list& __x, _Compare __comp)
 597         { merge(std::move(__x), __comp); }
 598 #endif
 599
 600       void
 601       sort() { _Base::sort(); }
 602
 603       template<typename _StrictWeakOrdering>
 604         void
 605         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
 606
 607       using _Base::reverse;
 608
 609       _Base&
 610       _M_base()       { return *this; }
 611
 612       const _Base&
 613       _M_base() const { return *this; }
 614
 615     private:
 616       void
 617       _M_invalidate_all()
 618       {
 619         typedef typename _Base::const_iterator _Base_const_iterator;
 620         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 621         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 622       }
 623     };
 624
 625   template<typename _Tp, typename _Alloc>
 626     inline bool
 627     operator==(const list<_Tp, _Alloc>& __lhs,
 628                const list<_Tp, _Alloc>& __rhs)
 629     { return __lhs._M_base() == __rhs._M_base(); }
 630
 631   template<typename _Tp, typename _Alloc>
 632     inline bool
 633     operator!=(const list<_Tp, _Alloc>& __lhs,
 634                const list<_Tp, _Alloc>& __rhs)
 635     { return __lhs._M_base() != __rhs._M_base(); }
 636
 637   template<typename _Tp, typename _Alloc>
 638     inline bool
 639     operator<(const list<_Tp, _Alloc>& __lhs,
 640               const list<_Tp, _Alloc>& __rhs)
 641     { return __lhs._M_base() < __rhs._M_base(); }
 642
 643   template<typename _Tp, typename _Alloc>
 644     inline bool
 645     operator<=(const list<_Tp, _Alloc>& __lhs,
 646                const list<_Tp, _Alloc>& __rhs)
 647     { return __lhs._M_base() <= __rhs._M_base(); }
 648
 649   template<typename _Tp, typename _Alloc>
 650     inline bool
 651     operator>=(const list<_Tp, _Alloc>& __lhs,
 652                const list<_Tp, _Alloc>& __rhs)
 653     { return __lhs._M_base() >= __rhs._M_base(); }
 654
 655   template<typename _Tp, typename _Alloc>
 656     inline bool
 657     operator>(const list<_Tp, _Alloc>& __lhs,
 658               const list<_Tp, _Alloc>& __rhs)
 659     { return __lhs._M_base() > __rhs._M_base(); }
 660
 661   template<typename _Tp, typename _Alloc>
 662     inline void
 663     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 664     { __lhs.swap(__rhs); }
 665
 666 } // namespace __debug
 667 } // namespace std
 668
 669 #endif