libstdc++-v3/include/debug/safe_local_iterator.h

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2015 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/safe_local_iterator.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
  30 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
  31
  32 #include <debug/safe_unordered_base.h>
  33
  34 namespace __gnu_debug
  35 {
  36   /** \brief Safe iterator wrapper.
  37    *
  38    *  The class template %_Safe_local_iterator is a wrapper around an
  39    *  iterator that tracks the iterator's movement among sequences and
  40    *  checks that operations performed on the "safe" iterator are
  41    *  legal. In additional to the basic iterator operations (which are
  42    *  validated, and then passed to the underlying iterator),
  43    *  %_Safe_local_iterator has member functions for iterator invalidation,
  44    *  attaching/detaching the iterator from sequences, and querying
  45    *  the iterator's state.
  46    */
  47   template<typename _Iterator, typename _Sequence>
  48     class _Safe_local_iterator
  49     : private _Iterator
  50     , public _Safe_local_iterator_base
  51     {
  52       typedef _Iterator _Iter_base;
  53       typedef _Safe_local_iterator_base _Safe_base;
  54       typedef typename _Sequence::const_local_iterator _Const_local_iterator;
  55       typedef typename _Sequence::size_type size_type;
  56
  57       /// Determine if this is a constant iterator.
  58       bool
  59       _M_constant() const
  60       {
  61         return std::__are_same<_Const_local_iterator,
  62                                _Safe_local_iterator>::__value;
  63       }
  64
  65       typedef std::iterator_traits<_Iterator> _Traits;
  66
  67       struct _Attach_single
  68       { };
  69
  70       _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
  71                            _Attach_single) noexcept
  72       : _Iter_base(__i)
  73       { _M_attach_single(__cont); }
  74
  75     public:
  76       typedef _Iterator                                 iterator_type;
  77       typedef typename _Traits::iterator_category       iterator_category;
  78       typedef typename _Traits::value_type              value_type;
  79       typedef typename _Traits::difference_type         difference_type;
  80       typedef typename _Traits::reference               reference;
  81       typedef typename _Traits::pointer                 pointer;
  82
  83       /// @post the iterator is singular and unattached
  84       _Safe_local_iterator() noexcept : _Iter_base() { }
  85
  86       /**
  87        * @brief Safe iterator construction from an unsafe iterator and
  88        * its sequence.
  89        *
  90        * @pre @p seq is not NULL
  91        * @post this is not singular
  92        */
  93       _Safe_local_iterator(const _Iterator& __i,
  94                            const _Safe_sequence_base* __cont)
  95       : _Iter_base(__i), _Safe_base(__cont, _M_constant())
  96       {
  97         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
  98                               _M_message(__msg_init_singular)
  99                               ._M_iterator(*this, "this"));
 100       }
 101
 102       /**
 103        * @brief Copy construction.
 104        */
 105       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
 106       : _Iter_base(__x.base())
 107       {
 108         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 109         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 110         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 111                               || __x.base() == _Iterator(),
 112                               _M_message(__msg_init_copy_singular)
 113                               ._M_iterator(*this, "this")
 114                               ._M_iterator(__x, "other"));
 115         _M_attach(__x._M_sequence);
 116       }
 117
 118       /**
 119        * @brief Move construction.
 120        * @post __x is singular and unattached
 121        */
 122       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
 123       : _Iter_base()
 124       {
 125         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 126                               || __x.base() == _Iterator(),
 127                               _M_message(__msg_init_copy_singular)
 128                               ._M_iterator(*this, "this")
 129                               ._M_iterator(__x, "other"));
 130         auto __cont = __x._M_sequence;
 131         __x._M_detach();
 132         std::swap(base(), __x.base());
 133         _M_attach(__cont);
 134       }
 135
 136       /**
 137        *  @brief Converting constructor from a mutable iterator to a
 138        *  constant iterator.
 139       */
 140       template<typename _MutableIterator>
 141         _Safe_local_iterator(
 142           const _Safe_local_iterator<_MutableIterator,
 143           typename __gnu_cxx::__enable_if<std::__are_same<
 144               _MutableIterator,
 145               typename _Sequence::local_iterator::iterator_type>::__value,
 146                                           _Sequence>::__type>& __x)
 147         : _Iter_base(__x.base())
 148         {
 149           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 150           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 151           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 152                                 || __x.base() == _Iterator(),
 153                                 _M_message(__msg_init_const_singular)
 154                                 ._M_iterator(*this, "this")
 155                                 ._M_iterator(__x, "other"));
 156           _M_attach(__x._M_sequence);
 157         }
 158
 159       /**
 160        * @brief Copy assignment.
 161        */
 162       _Safe_local_iterator&
 163       operator=(const _Safe_local_iterator& __x)
 164       {
 165         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 166         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 167         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 168                               || __x.base() == _Iterator(),
 169                               _M_message(__msg_copy_singular)
 170                               ._M_iterator(*this, "this")
 171                               ._M_iterator(__x, "other"));
 172
 173         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 174           {
 175             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 176             base() = __x.base();
 177             _M_version = __x._M_sequence->_M_version;
 178           }
 179         else
 180           {
 181             _M_detach();
 182             base() = __x.base();
 183             _M_attach(__x._M_sequence);
 184           }
 185
 186         return *this;
 187       }
 188
 189       /**
 190        * @brief Move assignment.
 191        * @post __x is singular and unattached
 192        */
 193       _Safe_local_iterator&
 194       operator=(_Safe_local_iterator&& __x) noexcept
 195       {
 196         _GLIBCXX_DEBUG_VERIFY(this != &__x,
 197                               _M_message(__msg_self_move_assign)
 198                               ._M_iterator(*this, "this"));
 199         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 200                               || __x.base() == _Iterator(),
 201                               _M_message(__msg_copy_singular)
 202                               ._M_iterator(*this, "this")
 203                               ._M_iterator(__x, "other"));
 204
 205         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 206           {
 207             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 208             base() = __x.base();
 209             _M_version = __x._M_sequence->_M_version;
 210           }
 211         else
 212           {
 213             _M_detach();
 214             base() = __x.base();
 215             _M_attach(__x._M_sequence);
 216           }
 217
 218         __x._M_detach();
 219         __x.base() = _Iterator();
 220         return *this;
 221       }
 222
 223       /**
 224        *  @brief Iterator dereference.
 225        *  @pre iterator is dereferenceable
 226        */
 227       reference
 228       operator*() const
 229       {
 230         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 231                               _M_message(__msg_bad_deref)
 232                               ._M_iterator(*this, "this"));
 233         return *base();
 234       }
 235
 236       /**
 237        *  @brief Iterator dereference.
 238        *  @pre iterator is dereferenceable
 239        *  @todo Make this correct w.r.t. iterators that return proxies
 240        */
 241       pointer
 242       operator->() const
 243       {
 244         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 245                               _M_message(__msg_bad_deref)
 246                               ._M_iterator(*this, "this"));
 247         return std::__addressof(*base());
 248       }
 249
 250       // ------ Input iterator requirements ------
 251       /**
 252        *  @brief Iterator preincrement
 253        *  @pre iterator is incrementable
 254        */
 255       _Safe_local_iterator&
 256       operator++()
 257       {
 258         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 259                               _M_message(__msg_bad_inc)
 260                               ._M_iterator(*this, "this"));
 261         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 262         ++base();
 263         return *this;
 264       }
 265
 266       /**
 267        *  @brief Iterator postincrement
 268        *  @pre iterator is incrementable
 269        */
 270       _Safe_local_iterator
 271       operator++(int)
 272       {
 273         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 274                               _M_message(__msg_bad_inc)
 275                               ._M_iterator(*this, "this"));
 276         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 277         return _Safe_local_iterator(base()++, this->_M_sequence,
 278                                     _Attach_single());
 279       }
 280
 281       // ------ Utilities ------
 282       /**
 283        * @brief Return the underlying iterator
 284        */
 285       _Iterator&
 286       base() noexcept { return *this; }
 287
 288       const _Iterator&
 289       base() const noexcept { return *this; }
 290
 291       /**
 292        * @brief Return the bucket
 293        */
 294       size_type
 295       bucket() const { return base()._M_get_bucket(); }
 296
 297       /**
 298        * @brief Conversion to underlying non-debug iterator to allow
 299        * better interaction with non-debug containers.
 300        */
 301       operator _Iterator() const { return *this; }
 302
 303       /** Attach iterator to the given sequence. */
 304       void
 305       _M_attach(_Safe_sequence_base* __seq)
 306       { _Safe_base::_M_attach(__seq, _M_constant()); }
 307
 308       /** Likewise, but not thread-safe. */
 309       void
 310       _M_attach_single(_Safe_sequence_base* __seq)
 311       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
 312
 313       /// Is the iterator dereferenceable?
 314       bool
 315       _M_dereferenceable() const
 316       { return !this->_M_singular() && !_M_is_end(); }
 317
 318       /// Is the iterator incrementable?
 319       bool
 320       _M_incrementable() const
 321       { return !this->_M_singular() && !_M_is_end(); }
 322
 323       // Is the iterator range [*this, __rhs) valid?
 324       bool
 325       _M_valid_range(const _Safe_local_iterator& __rhs,
 326                      std::pair<difference_type,
 327                                _Distance_precision>& __dist_info) const;
 328
 329       // The sequence this iterator references.
 330       typename
 331       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
 332                                                     _Safe_local_iterator>::__value,
 333                                     const _Sequence*,
 334                                     _Sequence*>::__type
 335       _M_get_sequence() const
 336       { return static_cast<_Sequence*>(_M_sequence); }
 337
 338       /// Is this iterator equal to the sequence's begin(bucket) iterator?
 339       bool _M_is_begin() const
 340       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
 341
 342       /// Is this iterator equal to the sequence's end(bucket) iterator?
 343       bool _M_is_end() const
 344       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
 345
 346       /// Is this iterator part of the same bucket as the other one?
 347       template<typename _Other>
 348         bool
 349         _M_in_same_bucket(const _Safe_local_iterator<_Other,
 350                                                      _Sequence>& __other) const
 351         { return bucket() == __other.bucket(); }
 352     };
 353
 354   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 355     inline bool
 356     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 357                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 358     {
 359       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 360                             _M_message(__msg_iter_compare_bad)
 361                             ._M_iterator(__lhs, "lhs")
 362                             ._M_iterator(__rhs, "rhs"));
 363       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 364                             _M_message(__msg_compare_different)
 365                             ._M_iterator(__lhs, "lhs")
 366                             ._M_iterator(__rhs, "rhs"));
 367       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 368                             _M_message(__msg_local_iter_compare_bad)
 369                             ._M_iterator(__lhs, "lhs")
 370                             ._M_iterator(__rhs, "rhs"));
 371       return __lhs.base() == __rhs.base();
 372     }
 373
 374   template<typename _Iterator, typename _Sequence>
 375     inline bool
 376     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 377                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 378     {
 379       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 380                             _M_message(__msg_iter_compare_bad)
 381                             ._M_iterator(__lhs, "lhs")
 382                             ._M_iterator(__rhs, "rhs"));
 383       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 384                             _M_message(__msg_compare_different)
 385                             ._M_iterator(__lhs, "lhs")
 386                             ._M_iterator(__rhs, "rhs"));
 387       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 388                             _M_message(__msg_local_iter_compare_bad)
 389                             ._M_iterator(__lhs, "lhs")
 390                             ._M_iterator(__rhs, "rhs"));
 391       return __lhs.base() == __rhs.base();
 392     }
 393
 394   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 395     inline bool
 396     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 397                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 398     {
 399       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 400                             _M_message(__msg_iter_compare_bad)
 401                             ._M_iterator(__lhs, "lhs")
 402                             ._M_iterator(__rhs, "rhs"));
 403       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 404                             _M_message(__msg_compare_different)
 405                             ._M_iterator(__lhs, "lhs")
 406                             ._M_iterator(__rhs, "rhs"));
 407       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 408                             _M_message(__msg_local_iter_compare_bad)
 409                             ._M_iterator(__lhs, "lhs")
 410                             ._M_iterator(__rhs, "rhs"));
 411       return __lhs.base() != __rhs.base();
 412     }
 413
 414   template<typename _Iterator, typename _Sequence>
 415     inline bool
 416     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 417                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 418     {
 419       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 420                             _M_message(__msg_iter_compare_bad)
 421                             ._M_iterator(__lhs, "lhs")
 422                             ._M_iterator(__rhs, "rhs"));
 423       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 424                             _M_message(__msg_compare_different)
 425                             ._M_iterator(__lhs, "lhs")
 426                             ._M_iterator(__rhs, "rhs"));
 427       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 428                             _M_message(__msg_local_iter_compare_bad)
 429                             ._M_iterator(__lhs, "lhs")
 430                             ._M_iterator(__rhs, "rhs"));
 431       return __lhs.base() != __rhs.base();
 432     }
 433
 434   /** Safe local iterators know if they are dereferenceable. */
 435   template<typename _Iterator, typename _Sequence>
 436     inline bool
 437     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
 438                                                        _Sequence>& __x)
 439     { return __x._M_dereferenceable(); }
 440
 441   /** Safe local iterators know how to check if they form a valid range. */
 442   template<typename _Iterator, typename _Sequence>
 443     inline bool
 444     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 445                   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
 446                   typename _Distance_traits<_Iterator>::__type& __dist_info)
 447     { return __first._M_valid_range(__last, __dist_info); }
 448
 449   /** Safe local iterators need a special method to get distance between each
 450       other. */
 451   template<typename _Iterator, typename _Sequence>
 452     inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
 453                      _Distance_precision>
 454     __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 455                    const _Safe_local_iterator<_Iterator, _Sequence>& __last,
 456                    std::input_iterator_tag)
 457     {
 458       if (__first.base() == __last.base())
 459         return { 0, __dp_exact };
 460
 461       if (__first._M_is_begin())
 462         {
 463           if (__last._M_is_end())
 464             return
 465               {
 466                 __first._M_get_sequence()->bucket_size(__first.bucket()),
 467                 __dp_exact
 468               };
 469
 470           return { 1, __dp_sign };
 471         }
 472
 473       if (__first._M_is_end())
 474         {
 475           if (__last._M_is_begin())
 476             return
 477               {
 478                 -__first._M_get_sequence()->bucket_size(__first.bucket()),
 479                 __dp_exact
 480               };
 481
 482           return { -1, __dp_sign };
 483         }
 484
 485       if (__last._M_is_begin())
 486         return { -1, __dp_sign };
 487
 488       if (__last._M_is_end())
 489         return { 1, __dp_sign };
 490
 491       return { 1, __dp_equality };
 492     }
 493
 494 #if __cplusplus < 201103L
 495   template<typename _Iterator, typename _Sequence>
 496     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
 497     { typedef _Iterator _Type; };
 498 #endif
 499
 500   template<typename _Iterator, typename _Sequence>
 501     inline _Iterator
 502     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
 503     { return __it.base(); }
 504
 505 } // namespace __gnu_debug
 506
 507 #include <debug/safe_local_iterator.tcc>
 508
 509 #endif