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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2017 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        */
 240       pointer
 241       operator->() const
 242       {
 243         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 244                               _M_message(__msg_bad_deref)
 245                               ._M_iterator(*this, "this"));
 246         return base().operator->();
 247       }
 248
 249       // ------ Input iterator requirements ------
 250       /**
 251        *  @brief Iterator preincrement
 252        *  @pre iterator is incrementable
 253        */
 254       _Safe_local_iterator&
 255       operator++()
 256       {
 257         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 258                               _M_message(__msg_bad_inc)
 259                               ._M_iterator(*this, "this"));
 260         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 261         ++base();
 262         return *this;
 263       }
 264
 265       /**
 266        *  @brief Iterator postincrement
 267        *  @pre iterator is incrementable
 268        */
 269       _Safe_local_iterator
 270       operator++(int)
 271       {
 272         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 273                               _M_message(__msg_bad_inc)
 274                               ._M_iterator(*this, "this"));
 275         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 276         return _Safe_local_iterator(base()++, this->_M_sequence,
 277                                     _Attach_single());
 278       }
 279
 280       // ------ Utilities ------
 281       /**
 282        * @brief Return the underlying iterator
 283        */
 284       _Iterator&
 285       base() noexcept { return *this; }
 286
 287       const _Iterator&
 288       base() const noexcept { return *this; }
 289
 290       /**
 291        * @brief Return the bucket
 292        */
 293       size_type
 294       bucket() const { return base()._M_get_bucket(); }
 295
 296       /**
 297        * @brief Conversion to underlying non-debug iterator to allow
 298        * better interaction with non-debug containers.
 299        */
 300       operator _Iterator() const { return *this; }
 301
 302       /** Attach iterator to the given sequence. */
 303       void
 304       _M_attach(_Safe_sequence_base* __seq)
 305       { _Safe_base::_M_attach(__seq, _M_constant()); }
 306
 307       /** Likewise, but not thread-safe. */
 308       void
 309       _M_attach_single(_Safe_sequence_base* __seq)
 310       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
 311
 312       /// Is the iterator dereferenceable?
 313       bool
 314       _M_dereferenceable() const
 315       { return !this->_M_singular() && !_M_is_end(); }
 316
 317       /// Is the iterator incrementable?
 318       bool
 319       _M_incrementable() const
 320       { return !this->_M_singular() && !_M_is_end(); }
 321
 322       // Is the iterator range [*this, __rhs) valid?
 323       bool
 324       _M_valid_range(const _Safe_local_iterator& __rhs,
 325                      std::pair<difference_type,
 326                                _Distance_precision>& __dist_info) const;
 327
 328       // The sequence this iterator references.
 329       typename
 330       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
 331                                                     _Safe_local_iterator>::__value,
 332                                     const _Sequence*,
 333                                     _Sequence*>::__type
 334       _M_get_sequence() const
 335       { return static_cast<_Sequence*>(_M_sequence); }
 336
 337       /// Is this iterator equal to the sequence's begin(bucket) iterator?
 338       bool _M_is_begin() const
 339       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
 340
 341       /// Is this iterator equal to the sequence's end(bucket) iterator?
 342       bool _M_is_end() const
 343       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
 344
 345       /// Is this iterator part of the same bucket as the other one?
 346       template<typename _Other>
 347         bool
 348         _M_in_same_bucket(const _Safe_local_iterator<_Other,
 349                                                      _Sequence>& __other) const
 350         { return bucket() == __other.bucket(); }
 351     };
 352
 353   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 354     inline bool
 355     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 356                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 357     {
 358       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 359                             _M_message(__msg_iter_compare_bad)
 360                             ._M_iterator(__lhs, "lhs")
 361                             ._M_iterator(__rhs, "rhs"));
 362       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 363                             _M_message(__msg_compare_different)
 364                             ._M_iterator(__lhs, "lhs")
 365                             ._M_iterator(__rhs, "rhs"));
 366       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 367                             _M_message(__msg_local_iter_compare_bad)
 368                             ._M_iterator(__lhs, "lhs")
 369                             ._M_iterator(__rhs, "rhs"));
 370       return __lhs.base() == __rhs.base();
 371     }
 372
 373   template<typename _Iterator, typename _Sequence>
 374     inline bool
 375     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 376                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 377     {
 378       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 379                             _M_message(__msg_iter_compare_bad)
 380                             ._M_iterator(__lhs, "lhs")
 381                             ._M_iterator(__rhs, "rhs"));
 382       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 383                             _M_message(__msg_compare_different)
 384                             ._M_iterator(__lhs, "lhs")
 385                             ._M_iterator(__rhs, "rhs"));
 386       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 387                             _M_message(__msg_local_iter_compare_bad)
 388                             ._M_iterator(__lhs, "lhs")
 389                             ._M_iterator(__rhs, "rhs"));
 390       return __lhs.base() == __rhs.base();
 391     }
 392
 393   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 394     inline bool
 395     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 396                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 397     {
 398       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 399                             _M_message(__msg_iter_compare_bad)
 400                             ._M_iterator(__lhs, "lhs")
 401                             ._M_iterator(__rhs, "rhs"));
 402       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 403                             _M_message(__msg_compare_different)
 404                             ._M_iterator(__lhs, "lhs")
 405                             ._M_iterator(__rhs, "rhs"));
 406       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 407                             _M_message(__msg_local_iter_compare_bad)
 408                             ._M_iterator(__lhs, "lhs")
 409                             ._M_iterator(__rhs, "rhs"));
 410       return __lhs.base() != __rhs.base();
 411     }
 412
 413   template<typename _Iterator, typename _Sequence>
 414     inline bool
 415     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 416                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 417     {
 418       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 419                             _M_message(__msg_iter_compare_bad)
 420                             ._M_iterator(__lhs, "lhs")
 421                             ._M_iterator(__rhs, "rhs"));
 422       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 423                             _M_message(__msg_compare_different)
 424                             ._M_iterator(__lhs, "lhs")
 425                             ._M_iterator(__rhs, "rhs"));
 426       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 427                             _M_message(__msg_local_iter_compare_bad)
 428                             ._M_iterator(__lhs, "lhs")
 429                             ._M_iterator(__rhs, "rhs"));
 430       return __lhs.base() != __rhs.base();
 431     }
 432
 433   /** Safe local iterators know if they are dereferenceable. */
 434   template<typename _Iterator, typename _Sequence>
 435     inline bool
 436     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
 437                                                        _Sequence>& __x)
 438     { return __x._M_dereferenceable(); }
 439
 440   /** Safe local iterators know how to check if they form a valid range. */
 441   template<typename _Iterator, typename _Sequence>
 442     inline bool
 443     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 444                   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
 445                   typename _Distance_traits<_Iterator>::__type& __dist_info)
 446     { return __first._M_valid_range(__last, __dist_info); }
 447
 448   /** Safe local iterators need a special method to get distance between each
 449       other. */
 450   template<typename _Iterator, typename _Sequence>
 451     inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
 452                      _Distance_precision>
 453     __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 454                    const _Safe_local_iterator<_Iterator, _Sequence>& __last,
 455                    std::input_iterator_tag)
 456     {
 457       if (__first.base() == __last.base())
 458         return { 0, __dp_exact };
 459
 460       if (__first._M_is_begin())
 461         {
 462           if (__last._M_is_end())
 463             return
 464               {
 465                 __first._M_get_sequence()->bucket_size(__first.bucket()),
 466                 __dp_exact
 467               };
 468
 469           return { 1, __dp_sign };
 470         }
 471
 472       if (__first._M_is_end())
 473         {
 474           if (__last._M_is_begin())
 475             return
 476               {
 477                 -__first._M_get_sequence()->bucket_size(__first.bucket()),
 478                 __dp_exact
 479               };
 480
 481           return { -1, __dp_sign };
 482         }
 483
 484       if (__last._M_is_begin())
 485         return { -1, __dp_sign };
 486
 487       if (__last._M_is_end())
 488         return { 1, __dp_sign };
 489
 490       return { 1, __dp_equality };
 491     }
 492
 493 #if __cplusplus < 201103L
 494   template<typename _Iterator, typename _Sequence>
 495     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
 496     { typedef _Iterator _Type; };
 497 #endif
 498
 499   template<typename _Iterator, typename _Sequence>
 500     inline _Iterator
 501     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
 502     { return __it.base(); }
 503
 504 } // namespace __gnu_debug
 505
 506 #include <debug/safe_local_iterator.tcc>
 507
 508 #endif