Line data Source code
1 : // Node handles for containers -*- C++ -*-
2 :
3 : // Copyright (C) 2016-2018 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 :
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 176 : ~_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 176 : _Node_handle_common(typename _AllocTraits::pointer __ptr,
104 : const _NodeAlloc& __alloc)
105 176 : : _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 176 : _M_destroy() noexcept
124 : {
125 176 : if (_M_ptr != nullptr)
126 : {
127 0 : allocator_type __alloc(*_M_alloc);
128 0 : allocator_traits<allocator_type>::destroy(__alloc,
129 0 : _M_ptr->_M_valptr());
130 0 : _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1);
131 : }
132 176 : }
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 176 : ~_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 176 : _Node_handle(typename _AllocTraits::pointer __ptr,
191 : const _NodeAlloc& __alloc)
192 176 : : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
193 : {
194 176 : if (__ptr)
195 : {
196 176 : auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
197 176 : _M_pkey = _S_pointer_to(__key);
198 176 : _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
199 : }
200 : else
201 : {
202 0 : _M_pkey = nullptr;
203 0 : _M_pmapped = nullptr;
204 : }
205 176 : }
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 352 : _S_pointer_to(_Tp& __obj)
218 352 : { 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
|
