1// Node handles for containers -*- C++ -*-
2
3// Copyright (C) 2016-2017 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
43namespace 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 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 __glibcxx_assert(this->_M_alloc == __nh._M_alloc);
91 }
92 else
93 __glibcxx_assert(_M_alloc);
94 __nh._M_ptr = nullptr;
95 __nh._M_alloc = nullopt;
96 return *this;
97 }
98
99 _Node_handle_common(typename _AllocTraits::pointer __ptr,
100 const _NodeAlloc& __alloc)
101 : _M_ptr(__ptr), _M_alloc(__alloc) { }
102
103 void
104 _M_swap(_Node_handle_common& __nh) noexcept
105 {
106 using std::swap;
107 swap(_M_ptr, __nh._M_ptr);
108 if (_AllocTraits::propagate_on_container_swap::value
109 || !_M_alloc || !__nh._M_alloc)
110 _M_alloc.swap(__nh._M_alloc);
111 else
112 __glibcxx_assert(_M_alloc == __nh._M_alloc);
113 }
114
115 private:
116 void
117 _M_destroy() noexcept
118 {
119 if (_M_ptr != nullptr)
120 {
121 allocator_type __alloc(*_M_alloc);
122 allocator_traits<allocator_type>::destroy(__alloc,
123 _M_ptr->_M_valptr());
124 _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1);
125 }
126 }
127
128 protected:
129 typename _AllocTraits::pointer _M_ptr;
130 private:
131 optional<_NodeAlloc> _M_alloc;
132
133 template<typename _Key2, typename _Value2, typename _KeyOfValue,
134 typename _Compare, typename _ValueAlloc>
135 friend class _Rb_tree;
136 };
137
138 /// Node handle type for maps.
139 template<typename _Key, typename _Value, typename _NodeAlloc>
140 class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc>
141 {
142 public:
143 constexpr _Node_handle() noexcept = default;
144 ~_Node_handle() = default;
145 _Node_handle(_Node_handle&&) noexcept = default;
146
147 _Node_handle&
148 operator=(_Node_handle&&) noexcept = default;
149
150 using key_type = _Key;
151 using mapped_type = typename _Value::second_type;
152
153 key_type&
154 key() const noexcept
155 {
156 __glibcxx_assert(!this->empty());
157 return *_M_pkey;
158 }
159
160 mapped_type&
161 mapped() const noexcept
162 {
163 __glibcxx_assert(!this->empty());
164 return *_M_pmapped;
165 }
166
167 void
168 swap(_Node_handle& __nh) noexcept
169 {
170 this->_M_swap(__nh);
171 using std::swap;
172 swap(_M_pkey, __nh._M_pkey);
173 swap(_M_pmapped, __nh._M_pmapped);
174 }
175
176 friend void
177 swap(_Node_handle& __x, _Node_handle& __y)
178 noexcept(noexcept(__x.swap(__y)))
179 { __x.swap(__y); }
180
181 private:
182 using _AllocTraits = allocator_traits<_NodeAlloc>;
183
184 _Node_handle(typename _AllocTraits::pointer __ptr,
185 const _NodeAlloc& __alloc)
186 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
187 {
188 if (__ptr)
189 {
190 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
191 _M_pkey = _S_pointer_to(__key);
192 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
193 }
194 else
195 {
196 _M_pkey = nullptr;
197 _M_pmapped = nullptr;
198 }
199 }
200
201 template<typename _Tp>
202 using __pointer
203 = __ptr_rebind<typename _AllocTraits::pointer,
204 remove_reference_t<_Tp>>;
205
206 __pointer<_Key> _M_pkey = nullptr;
207 __pointer<typename _Value::second_type> _M_pmapped = nullptr;
208
209 template<typename _Tp>
210 __pointer<_Tp>
211 _S_pointer_to(_Tp& __obj)
212 { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
213
214 const key_type&
215 _M_key() const noexcept { return key(); }
216
217 template<typename _Key2, typename _Value2, typename _KeyOfValue,
218 typename _Compare, typename _ValueAlloc>
219 friend class _Rb_tree;
220
221 template<typename _Key2, typename _Value2, typename _ValueAlloc,
222 typename _ExtractKey, typename _Equal,
223 typename _H1, typename _H2, typename _Hash,
224 typename _RehashPolicy, typename _Traits>
225 friend class _Hashtable;
226 };
227
228 /// Node handle type for sets.
229 template<typename _Value, typename _NodeAlloc>
230 class _Node_handle<_Value, _Value, _NodeAlloc>
231 : public _Node_handle_common<_Value, _NodeAlloc>
232 {
233 public:
234 constexpr _Node_handle() noexcept = default;
235 ~_Node_handle() = default;
236 _Node_handle(_Node_handle&&) noexcept = default;
237
238 _Node_handle&
239 operator=(_Node_handle&&) noexcept = default;
240
241 using value_type = _Value;
242
243 value_type&
244 value() const noexcept
245 {
246 __glibcxx_assert(!this->empty());
247 return *this->_M_ptr->_M_valptr();
248 }
249
250 void
251 swap(_Node_handle& __nh) noexcept
252 { this->_M_swap(__nh); }
253
254 friend void
255 swap(_Node_handle& __x, _Node_handle& __y)
256 noexcept(noexcept(__x.swap(__y)))
257 { __x.swap(__y); }
258
259 private:
260 using _AllocTraits = allocator_traits<_NodeAlloc>;
261
262 _Node_handle(typename _AllocTraits::pointer __ptr,
263 const _NodeAlloc& __alloc)
264 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
265
266 const value_type&
267 _M_key() const noexcept { return value(); }
268
269 template<typename _Key, typename _Val, typename _KeyOfValue,
270 typename _Compare, typename _Alloc>
271 friend class _Rb_tree;
272
273 template<typename _Key2, typename _Value2, typename _ValueAlloc,
274 typename _ExtractKey, typename _Equal,
275 typename _H1, typename _H2, typename _Hash,
276 typename _RehashPolicy, typename _Traits>
277 friend class _Hashtable;
278 };
279
280 /// Return type of insert(node_handle&&) on unique maps/sets.
281 template<typename _Iterator, typename _NodeHandle>
282 struct _Node_insert_return
283 {
284 _Iterator position = _Iterator();
285 bool inserted = false;
286 _NodeHandle node;
287 };
288
289_GLIBCXX_END_NAMESPACE_VERSION
290} // namespace std
291
292#endif // C++17
293#endif
294