1 // Node handles for containers -*- C++ -*-
2
3 // Copyright (C) 2016-2020 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 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>
40 #include <bits/alloc_traits.h>
41 #include <bits/ptr_traits.h>
42
_GLIBCXX_VISIBILITY(default)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
65 [[nodiscard]] bool empty() const noexcept { return _M_ptr == nullptr; }
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
90 {
91 __glibcxx_assert(this->_M_alloc == __nh._M_alloc);
92 }
93 }
94 else
95 {
96 __glibcxx_assert(_M_alloc);
97 }
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);
112 if (_AllocTraits::propagate_on_container_swap::value
113 || !_M_alloc || !__nh._M_alloc)
114 _M_alloc.swap(__nh._M_alloc);
115 else
116 {
117 __glibcxx_assert(_M_alloc == __nh._M_alloc);
118 }
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
190 _Node_handle(typename _AllocTraits::pointer __ptr,
191 const _NodeAlloc& __alloc)
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>
208 using __pointer
209 = __ptr_rebind<typename _AllocTraits::pointer,
210 remove_reference_t<_Tp>>;
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,
269 const _NodeAlloc& __alloc)
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 {
290 _Iterator position = _Iterator();
291 bool inserted = false;
292 _NodeHandle node;
293 };
294
295 _GLIBCXX_END_NAMESPACE_VERSION
296 } // namespace std
297
298 #endif // C++17
299 #endif
300