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

   1 // Safe container implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2024 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_unordered_container.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_SAFE_UNORDERED_CONTAINER_H
  30 #define _GLIBCXX_DEBUG_SAFE_UNORDERED_CONTAINER_H 1
  31
  32 #include <debug/assertions.h>
  33 #include <debug/macros.h>
  34 #include <debug/functions.h>
  35 #include <debug/safe_unordered_base.h>
  36
  37 namespace __gnu_debug
  38 {
  39   /**
  40    * @brief Base class for constructing a @a safe unordered container type
  41    * that tracks iterators that reference it.
  42    *
  43    * The class template %_Safe_unordered_container simplifies the
  44    * construction of @a safe unordered containers that track the iterators
  45    * that reference the container, so that the iterators are notified of
  46    * changes in the container that may affect their operation, e.g., if
  47    * the container invalidates its iterators or is destructed. This class
  48    * template may only be used by deriving from it and passing the name
  49    * of the derived class as its template parameter via the curiously
  50    * recurring template pattern. The derived class must have @c
  51    * iterator and @c const_iterator types that are instantiations of
  52    * class template _Safe_iterator for this container and @c local_iterator
  53    * and @c const_local_iterator types that are instantiations of class
  54    * template _Safe_local_iterator for this container. Iterators will
  55    * then be tracked automatically.
  56    */
  57   template<typename _Container>
  58     class _Safe_unordered_container : public _Safe_unordered_container_base
  59     {
  60     private:
  61       _Container&
  62       _M_cont() noexcept
  63       { return *static_cast<_Container*>(this); }
  64
  65     protected:
  66       void
  67       _M_invalidate_locals()
  68       {
  69         auto __local_end = _M_cont()._M_base().cend(0);
  70         this->_M_invalidate_local_if(
  71                 [__local_end](__decltype(__local_end) __it)
  72                 { return __it != __local_end; });
  73       }
  74
  75 #if __cplusplus > 201402L
  76       template<typename _ExtractKey, typename _Source>
  77         struct _UContInvalidatePred
  78         {
  79           template<typename _Iterator>
  80             bool
  81             operator()(_Iterator __it) const
  82             { return _M_source.count(_ExtractKey{}(*__it)) == 0; }
  83
  84           const _Source& _M_source;
  85         };
  86
  87       template<typename _ExtractKey, typename _Source>
  88         struct _UMContInvalidatePred
  89         {
  90           template<typename _Iterator>
  91             bool
  92             operator()(_Iterator __it) const
  93             {
  94               auto __rng =
  95                 _M_source._M_base().equal_range(_ExtractKey{}(*__it));
  96               for (auto __rit = __rng.first;
  97                    __rit != __rng.second; ++__rit)
  98                 {
  99                   if (__it == __rit)
 100                     return false;
 101                 }
 102
 103               return true;
 104             }
 105
 106           const _Source& _M_source;
 107         };
 108
 109       template<typename _Source, typename _InvalidatePred>
 110         struct _UContMergeGuard
 111         {
 112           _UContMergeGuard(_Source& __src) noexcept
 113           : _M_source(__src), _M_size(__src.size()), _M_pred { __src }
 114           { }
 115
 116           _UContMergeGuard(const _UContMergeGuard&) = delete;
 117
 118           ~_UContMergeGuard()
 119           {
 120             const std::size_t __size = _M_source.size();
 121             if (__size == _M_size)
 122               return;
 123
 124             __try
 125               {
 126                 if (__size == 0)
 127                   _M_source._M_invalidate_all();
 128                 else
 129                   {
 130                     _M_source._M_invalidate_if(_M_pred);
 131                     _M_source._M_invalidate_local_if(_M_pred);
 132                   }
 133               }
 134             __catch(...)
 135               {
 136                 _M_source._M_invalidate_all();
 137               }
 138           }
 139
 140           _Source& _M_source;
 141           const std::size_t _M_size;
 142           _InvalidatePred _M_pred;
 143         };
 144
 145       template<typename _ExtractKey, typename _Source>
 146         static _UContMergeGuard<_Source,
 147                                 _UContInvalidatePred<_ExtractKey, _Source>>
 148         _S_uc_guard(_ExtractKey, _Source& __src)
 149         {
 150           typedef _UContInvalidatePred<_ExtractKey, _Source> _InvalidatePred;
 151           return _UContMergeGuard<_Source, _InvalidatePred>(__src);
 152         }
 153
 154       template<typename _ExtractKey, typename _Source>
 155         static _UContMergeGuard<_Source,
 156                                 _UMContInvalidatePred<_ExtractKey, _Source>>
 157         _S_umc_guard(_ExtractKey, _Source& __src)
 158         {
 159           typedef _UMContInvalidatePred<_ExtractKey, _Source> _InvalidatePred;
 160           return _UContMergeGuard<_Source, _InvalidatePred>(__src);
 161         }
 162 #endif // C++17
 163
 164     public:
 165       void
 166       _M_invalidate_all()
 167       {
 168         auto __end = _M_cont()._M_base().cend();
 169         this->_M_invalidate_if([__end](__decltype(__end) __it)
 170                                { return __it != __end; });
 171         _M_invalidate_locals();
 172       }
 173
 174       /** Invalidates all iterators @c x that reference this container,
 175           are not singular, and for which @c __pred(x) returns @c
 176           true. @c __pred will be invoked with the normal iterators nested
 177           in the safe ones. */
 178       template<typename _Predicate>
 179         void
 180         _M_invalidate_if(_Predicate __pred);
 181
 182       /** Invalidates all local iterators @c x that reference this container,
 183           are not singular, and for which @c __pred(x) returns @c
 184           true. @c __pred will be invoked with the normal local iterators
 185           nested in the safe ones. */
 186       template<typename _Predicate>
 187         void
 188         _M_invalidate_local_if(_Predicate __pred);
 189     };
 190 } // namespace __gnu_debug
 191
 192 #include <debug/safe_unordered_container.tcc>
 193
 194 #endif