l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/debug/list

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