1// Safe container implementation -*- C++ -*-
2
3// Copyright (C) 2011-2026 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
37namespace __gnu_debug
38{
39 template<typename _Container>
40 class _Safe_unordered_container;
41
42#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
43 template<typename _ExtractKey, typename _Source>
44 struct _UContInvalidatePred
45 {
46 template<typename _Iterator>
47 bool
48 operator()(_Iterator __it) const
49 { return _M_source._M_cont().count(_ExtractKey{}(*__it)) == 0; }
50
51 const _Safe_unordered_container<_Source>& _M_source;
52 };
53
54 template<typename _ExtractKey, typename _Source>
55 struct _UMContInvalidatePred
56 {
57 template<typename _Iterator>
58 bool
59 operator()(_Iterator __it) const
60 {
61 auto __rng =
62 _M_source._M_cont()._M_base().equal_range(_ExtractKey{}(*__it));
63 for (auto __rit = __rng.first;
64 __rit != __rng.second; ++__rit)
65 {
66 if (__it == __rit)
67 return false;
68 }
69
70 return true;
71 }
72
73 const _Safe_unordered_container<_Source>& _M_source;
74 };
75
76 template<typename _Source, typename _InvalidatePred>
77 struct _UContMergeGuard
78 {
79 _UContMergeGuard(_Safe_unordered_container<_Source>& __src) noexcept
80 : _M_source(__src), _M_size(__src._M_cont().size()), _M_pred { __src }
81 { }
82
83 _UContMergeGuard(const _UContMergeGuard&) = delete;
84
85 ~_UContMergeGuard()
86 {
87 const std::size_t __size = _M_source._M_cont().size();
88 if (__size == _M_size)
89 return;
90
91 __try
92 {
93 if (__size == 0)
94 _M_source._M_invalidate_all();
95 else
96 _M_source._M_invalidate_all_if(_M_pred);
97 }
98 __catch(...)
99 {
100 _M_source._M_invalidate_all();
101 }
102 }
103
104 _Safe_unordered_container<_Source>& _M_source;
105 const std::size_t _M_size;
106 _InvalidatePred _M_pred;
107 };
108#endif // >= C++17 && HOSTED
109
110 /**
111 * @brief Base class for constructing a @a safe unordered container type
112 * that tracks iterators that reference it.
113 *
114 * The class template %_Safe_unordered_container simplifies the
115 * construction of @a safe unordered containers that track the iterators
116 * that reference the container, so that the iterators are notified of
117 * changes in the container that may affect their operation, e.g., if
118 * the container invalidates its iterators or is destructed. This class
119 * template may only be used by deriving from it and passing the name
120 * of the derived class as its template parameter via the curiously
121 * recurring template pattern. The derived class must have @c
122 * iterator and @c const_iterator types that are instantiations of
123 * class template _Safe_iterator for this container and @c local_iterator
124 * and @c const_local_iterator types that are instantiations of class
125 * template _Safe_local_iterator for this container. Iterators will
126 * then be tracked automatically.
127 */
128 template<typename _Container>
129 class _Safe_unordered_container : public _Safe_unordered_container_base
130 {
131 const _Container&
132 _M_cont() const noexcept
133 { return *static_cast<const _Container*>(this); }
134
135 const _Safe_unordered_container*
136 _M_self() const
137 { return this; }
138
139 protected:
140#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
141 template<typename _ExtractKey, typename _Source>
142 friend struct ::__gnu_debug::_UContInvalidatePred;
143
144 template<typename _ExtractKey, typename _Source>
145 friend struct ::__gnu_debug::_UMContInvalidatePred;
146
147 template<typename _Source, typename _InvalidatePred>
148 friend struct ::__gnu_debug::_UContMergeGuard;
149
150 template<typename _ExtractKey, typename _Source>
151 static _UContMergeGuard<_Source,
152 _UContInvalidatePred<_ExtractKey, _Source>>
153 _S_uc_guard(_ExtractKey, _Safe_unordered_container<_Source>& __src)
154 {
155 typedef _UContInvalidatePred<_ExtractKey, _Source> _InvalidatePred;
156 return _UContMergeGuard<_Source, _InvalidatePred>(__src);
157 }
158
159 template<typename _ExtractKey, typename _Source>
160 static _UContMergeGuard<_Source,
161 _UMContInvalidatePred<_ExtractKey, _Source>>
162 _S_umc_guard(_ExtractKey, _Safe_unordered_container<_Source>& __src)
163 {
164 typedef _UMContInvalidatePred<_ExtractKey, _Source> _InvalidatePred;
165 return _UContMergeGuard<_Source, _InvalidatePred>(__src);
166 }
167#endif // >= C++17 && HOSTED
168
169 void
170 _M_invalidate_all()
171 {
172 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
173 auto __end = _M_cont()._M_base().cend();
174 _M_invalidate_if(
175 [__end](decltype(__end) __it)
176 { return __it != __end; },
177 sentry);
178
179 auto __local_end = _M_cont()._M_base().cend(0);
180 _M_invalidate_local_if(
181 [__local_end](decltype(__local_end) __it)
182 { return __it != __local_end; },
183 sentry);
184 }
185
186 template<typename _Predicate>
187 void
188 _M_invalidate_all_if(_Predicate __pred)
189 {
190 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
191 _M_invalidate_if(__pred, sentry);
192 _M_invalidate_local_if(__pred, sentry);
193 }
194
195 template<typename _VictimIt>
196 void
197 _M_invalidate(_VictimIt __victim)
198 {
199 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
200 _M_invalidate(__victim, sentry);
201 }
202
203 template<typename _VictimIt>
204 void
205 _M_invalidate(_VictimIt __victim, const __gnu_cxx::__scoped_lock& __lock)
206 {
207 auto __end = _M_cont()._M_base().cend();
208 _M_invalidate_if(
209 [__victim](decltype(__end) __it)
210 { return __it == __victim; },
211 __lock);
212
213 auto __local_end = _M_cont()._M_base().cend(0);
214 _M_invalidate_local_if(
215 [__victim](decltype(__local_end) __it)
216 { return __it == __victim; },
217 __lock);
218 }
219
220 private:
221 /** Invalidates all iterators @c x that reference this container,
222 are not singular, and for which @c __pred(x) returns @c
223 true. @c __pred will be invoked with the normal iterators nested
224 in the safe ones. */
225 template<typename _Predicate>
226 void
227 _M_invalidate_if(_Predicate __pred, const __gnu_cxx::__scoped_lock&);
228
229 /** Invalidates all local iterators @c x that reference this container,
230 are not singular, and for which @c __pred(x) returns @c
231 true. @c __pred will be invoked with the normal local iterators
232 nested in the safe ones. */
233 template<typename _Predicate>
234 void
235 _M_invalidate_local_if(_Predicate __pred,
236 const __gnu_cxx::__scoped_lock&);
237 };
238} // namespace __gnu_debug
239
240#include <debug/safe_unordered_container.tcc>
241
242#endif
243