]>
Commit | Line | Data |
---|---|---|
2dbe56bd JW |
1 | // Node handles for containers -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2016-2019 Free Software Foundation, Inc. |
2dbe56bd JW |
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 bits/node_handle.h | |
26 | * This is an internal header file, included by other library headers. | |
27 | * Do not attempt to use it directly. | |
28 | * @headername{map,set,unordered_map,unordered_set} | |
29 | */ | |
30 | ||
31 | #ifndef _NODE_HANDLE | |
32 | #define _NODE_HANDLE 1 | |
33 | ||
34 | #pragma GCC system_header | |
35 | ||
36 | #if __cplusplus > 201402L | |
37 | # define __cpp_lib_node_extract 201606 | |
38 | ||
39 | #include <optional> | |
2dbe56bd JW |
40 | #include <bits/alloc_traits.h> |
41 | #include <bits/ptr_traits.h> | |
42 | ||
43 | namespace std _GLIBCXX_VISIBILITY(default) | |
44 | { | |
45 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
46 | ||
47 | /// Base class for node handle types of maps and sets. | |
48 | template<typename _Val, typename _NodeAlloc> | |
49 | class _Node_handle_common | |
50 | { | |
51 | using _AllocTraits = allocator_traits<_NodeAlloc>; | |
52 | ||
53 | public: | |
54 | using allocator_type = __alloc_rebind<_NodeAlloc, _Val>; | |
55 | ||
56 | allocator_type | |
57 | get_allocator() const noexcept | |
58 | { | |
59 | __glibcxx_assert(!this->empty()); | |
60 | return allocator_type(*_M_alloc); | |
61 | } | |
62 | ||
63 | explicit operator bool() const noexcept { return _M_ptr != nullptr; } | |
64 | ||
d69f1ec7 | 65 | [[nodiscard]] bool empty() const noexcept { return _M_ptr == nullptr; } |
2dbe56bd JW |
66 | |
67 | protected: | |
68 | constexpr _Node_handle_common() noexcept : _M_ptr(), _M_alloc() {} | |
69 | ||
70 | ~_Node_handle_common() { _M_destroy(); } | |
71 | ||
72 | _Node_handle_common(_Node_handle_common&& __nh) noexcept | |
73 | : _M_ptr(__nh._M_ptr), _M_alloc(std::move(__nh._M_alloc)) | |
74 | { | |
75 | __nh._M_ptr = nullptr; | |
76 | __nh._M_alloc = nullopt; | |
77 | } | |
78 | ||
79 | _Node_handle_common& | |
80 | operator=(_Node_handle_common&& __nh) noexcept | |
81 | { | |
82 | _M_destroy(); | |
83 | _M_ptr = __nh._M_ptr; | |
84 | if constexpr (is_move_assignable_v<_NodeAlloc>) | |
85 | { | |
86 | if (_AllocTraits::propagate_on_container_move_assignment::value | |
87 | || !this->_M_alloc) | |
88 | this->_M_alloc = std::move(__nh._M_alloc); | |
89 | else | |
b7b61489 JW |
90 | { |
91 | __glibcxx_assert(this->_M_alloc == __nh._M_alloc); | |
92 | } | |
2dbe56bd JW |
93 | } |
94 | else | |
b7b61489 JW |
95 | { |
96 | __glibcxx_assert(_M_alloc); | |
97 | } | |
2dbe56bd JW |
98 | __nh._M_ptr = nullptr; |
99 | __nh._M_alloc = nullopt; | |
100 | return *this; | |
101 | } | |
102 | ||
103 | _Node_handle_common(typename _AllocTraits::pointer __ptr, | |
104 | const _NodeAlloc& __alloc) | |
105 | : _M_ptr(__ptr), _M_alloc(__alloc) { } | |
106 | ||
107 | void | |
108 | _M_swap(_Node_handle_common& __nh) noexcept | |
109 | { | |
110 | using std::swap; | |
111 | swap(_M_ptr, __nh._M_ptr); | |
3846b8e4 | 112 | if (_AllocTraits::propagate_on_container_swap::value |
2dbe56bd JW |
113 | || !_M_alloc || !__nh._M_alloc) |
114 | _M_alloc.swap(__nh._M_alloc); | |
115 | else | |
b7b61489 JW |
116 | { |
117 | __glibcxx_assert(_M_alloc == __nh._M_alloc); | |
118 | } | |
2dbe56bd JW |
119 | } |
120 | ||
121 | private: | |
122 | void | |
123 | _M_destroy() noexcept | |
124 | { | |
125 | if (_M_ptr != nullptr) | |
126 | { | |
127 | allocator_type __alloc(*_M_alloc); | |
128 | allocator_traits<allocator_type>::destroy(__alloc, | |
129 | _M_ptr->_M_valptr()); | |
130 | _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1); | |
131 | } | |
132 | } | |
133 | ||
134 | protected: | |
135 | typename _AllocTraits::pointer _M_ptr; | |
136 | private: | |
137 | optional<_NodeAlloc> _M_alloc; | |
138 | ||
139 | template<typename _Key2, typename _Value2, typename _KeyOfValue, | |
140 | typename _Compare, typename _ValueAlloc> | |
141 | friend class _Rb_tree; | |
142 | }; | |
143 | ||
144 | /// Node handle type for maps. | |
145 | template<typename _Key, typename _Value, typename _NodeAlloc> | |
146 | class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc> | |
147 | { | |
148 | public: | |
149 | constexpr _Node_handle() noexcept = default; | |
150 | ~_Node_handle() = default; | |
151 | _Node_handle(_Node_handle&&) noexcept = default; | |
152 | ||
153 | _Node_handle& | |
154 | operator=(_Node_handle&&) noexcept = default; | |
155 | ||
156 | using key_type = _Key; | |
157 | using mapped_type = typename _Value::second_type; | |
158 | ||
159 | key_type& | |
160 | key() const noexcept | |
161 | { | |
162 | __glibcxx_assert(!this->empty()); | |
163 | return *_M_pkey; | |
164 | } | |
165 | ||
166 | mapped_type& | |
167 | mapped() const noexcept | |
168 | { | |
169 | __glibcxx_assert(!this->empty()); | |
170 | return *_M_pmapped; | |
171 | } | |
172 | ||
173 | void | |
174 | swap(_Node_handle& __nh) noexcept | |
175 | { | |
176 | this->_M_swap(__nh); | |
177 | using std::swap; | |
178 | swap(_M_pkey, __nh._M_pkey); | |
179 | swap(_M_pmapped, __nh._M_pmapped); | |
180 | } | |
181 | ||
182 | friend void | |
183 | swap(_Node_handle& __x, _Node_handle& __y) | |
184 | noexcept(noexcept(__x.swap(__y))) | |
185 | { __x.swap(__y); } | |
186 | ||
187 | private: | |
188 | using _AllocTraits = allocator_traits<_NodeAlloc>; | |
189 | ||
2dbe56bd | 190 | _Node_handle(typename _AllocTraits::pointer __ptr, |
d72d690a | 191 | const _NodeAlloc& __alloc) |
2dbe56bd JW |
192 | : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) |
193 | { | |
194 | if (__ptr) | |
195 | { | |
196 | auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first); | |
197 | _M_pkey = _S_pointer_to(__key); | |
198 | _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second); | |
199 | } | |
200 | else | |
201 | { | |
202 | _M_pkey = nullptr; | |
203 | _M_pmapped = nullptr; | |
204 | } | |
205 | } | |
206 | ||
207 | template<typename _Tp> | |
5f939178 JW |
208 | using __pointer |
209 | = __ptr_rebind<typename _AllocTraits::pointer, | |
210 | remove_reference_t<_Tp>>; | |
2dbe56bd JW |
211 | |
212 | __pointer<_Key> _M_pkey = nullptr; | |
213 | __pointer<typename _Value::second_type> _M_pmapped = nullptr; | |
214 | ||
215 | template<typename _Tp> | |
216 | __pointer<_Tp> | |
217 | _S_pointer_to(_Tp& __obj) | |
218 | { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); } | |
219 | ||
220 | const key_type& | |
221 | _M_key() const noexcept { return key(); } | |
222 | ||
223 | template<typename _Key2, typename _Value2, typename _KeyOfValue, | |
224 | typename _Compare, typename _ValueAlloc> | |
225 | friend class _Rb_tree; | |
226 | ||
227 | template<typename _Key2, typename _Value2, typename _ValueAlloc, | |
228 | typename _ExtractKey, typename _Equal, | |
229 | typename _H1, typename _H2, typename _Hash, | |
230 | typename _RehashPolicy, typename _Traits> | |
231 | friend class _Hashtable; | |
232 | }; | |
233 | ||
234 | /// Node handle type for sets. | |
235 | template<typename _Value, typename _NodeAlloc> | |
236 | class _Node_handle<_Value, _Value, _NodeAlloc> | |
237 | : public _Node_handle_common<_Value, _NodeAlloc> | |
238 | { | |
239 | public: | |
240 | constexpr _Node_handle() noexcept = default; | |
241 | ~_Node_handle() = default; | |
242 | _Node_handle(_Node_handle&&) noexcept = default; | |
243 | ||
244 | _Node_handle& | |
245 | operator=(_Node_handle&&) noexcept = default; | |
246 | ||
247 | using value_type = _Value; | |
248 | ||
249 | value_type& | |
250 | value() const noexcept | |
251 | { | |
252 | __glibcxx_assert(!this->empty()); | |
253 | return *this->_M_ptr->_M_valptr(); | |
254 | } | |
255 | ||
256 | void | |
257 | swap(_Node_handle& __nh) noexcept | |
258 | { this->_M_swap(__nh); } | |
259 | ||
260 | friend void | |
261 | swap(_Node_handle& __x, _Node_handle& __y) | |
262 | noexcept(noexcept(__x.swap(__y))) | |
263 | { __x.swap(__y); } | |
264 | ||
265 | private: | |
266 | using _AllocTraits = allocator_traits<_NodeAlloc>; | |
267 | ||
268 | _Node_handle(typename _AllocTraits::pointer __ptr, | |
d72d690a | 269 | const _NodeAlloc& __alloc) |
2dbe56bd JW |
270 | : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { } |
271 | ||
272 | const value_type& | |
273 | _M_key() const noexcept { return value(); } | |
274 | ||
275 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
276 | typename _Compare, typename _Alloc> | |
277 | friend class _Rb_tree; | |
278 | ||
279 | template<typename _Key2, typename _Value2, typename _ValueAlloc, | |
280 | typename _ExtractKey, typename _Equal, | |
281 | typename _H1, typename _H2, typename _Hash, | |
282 | typename _RehashPolicy, typename _Traits> | |
283 | friend class _Hashtable; | |
284 | }; | |
285 | ||
286 | /// Return type of insert(node_handle&&) on unique maps/sets. | |
287 | template<typename _Iterator, typename _NodeHandle> | |
288 | struct _Node_insert_return | |
289 | { | |
2dbe56bd | 290 | _Iterator position = _Iterator(); |
85c05b5e | 291 | bool inserted = false; |
2dbe56bd | 292 | _NodeHandle node; |
2dbe56bd JW |
293 | }; |
294 | ||
2dbe56bd JW |
295 | _GLIBCXX_END_NAMESPACE_VERSION |
296 | } // namespace std | |
297 | ||
298 | #endif // C++17 | |
299 | #endif |