1 // Safe container implementation  -*- C++ -*-
2 
3 // Copyright (C) 2011-2022 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&
_M_cont()62       _M_cont() noexcept
63       { return *static_cast<_Container*>(this); }
64 
65     protected:
66       void
_M_invalidate_locals()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
operator_UContInvalidatePred81               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
operator_UMContInvalidatePred92               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           {
_UContMergeGuard_UContMergeGuard112             _UContMergeGuard(_Source& __src) noexcept
113             : _M_source(__src), _M_size(__src.size()), _M_pred { __src }
114             { }
115 
116             _UContMergeGuard(const _UContMergeGuard&) = delete;
117 
~_UContMergeGuard_UContMergeGuard118             ~_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>>
_S_uc_guard(_ExtractKey,_Source & __src)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>>
_S_umc_guard(_ExtractKey,_Source & __src)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
_M_invalidate_all()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
195