libstdc++
node_handle.h
Go to the documentation of this file.
1 // Node handles for containers -*- C++ -*-
2 
3 // Copyright (C) 2016-2021 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 >= 201703L
37 # define __cpp_lib_node_extract 201606
38 
39 #include <new>
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>
50  {
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._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() { }
69 
71  {
72  if (!empty())
73  _M_reset();
74  }
75 
77  : _M_ptr(__nh._M_ptr)
78  {
79  if (_M_ptr)
80  _M_move(std::move(__nh));
81  }
82 
84  operator=(_Node_handle_common&& __nh) noexcept
85  {
86  if (empty())
87  {
88  if (!__nh.empty())
89  _M_move(std::move(__nh));
90  }
91  else if (__nh.empty())
92  _M_reset();
93  else
94  {
95  // Free the current node before replacing the allocator.
96  _AllocTraits::destroy(*_M_alloc, _M_ptr->_M_valptr());
97  _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1);
98 
99  _M_alloc = __nh._M_alloc.release(); // assigns if POCMA
100  _M_ptr = __nh._M_ptr;
101  __nh._M_ptr = nullptr;
102  }
103  return *this;
104  }
105 
107  const _NodeAlloc& __alloc)
108  : _M_ptr(__ptr), _M_alloc(__alloc)
109  {
110  __glibcxx_assert(__ptr != nullptr);
111  }
112 
113  void
114  _M_swap(_Node_handle_common& __nh) noexcept
115  {
116  if (empty())
117  {
118  if (!__nh.empty())
119  _M_move(std::move(__nh));
120  }
121  else if (__nh.empty())
122  __nh._M_move(std::move(*this));
123  else
124  {
125  using std::swap;
126  swap(_M_ptr, __nh._M_ptr);
127  _M_alloc.swap(__nh._M_alloc); // swaps if POCS
128  }
129  }
130 
131  private:
132  // Moves the pointer and allocator from __nh to *this.
133  // Precondition: empty() && !__nh.empty()
134  // Postcondition: !empty() && __nh.empty()
135  void
136  _M_move(_Node_handle_common&& __nh) noexcept
137  {
138  ::new (std::__addressof(_M_alloc)) _NodeAlloc(__nh._M_alloc.release());
139  _M_ptr = __nh._M_ptr;
140  __nh._M_ptr = nullptr;
141  }
142 
143  // Deallocates the node, destroys the allocator.
144  // Precondition: !empty()
145  // Postcondition: empty()
146  void
147  _M_reset() noexcept
148  {
149  _NodeAlloc __alloc = _M_alloc.release();
150  _AllocTraits::destroy(__alloc, _M_ptr->_M_valptr());
151  _AllocTraits::deallocate(__alloc, _M_ptr, 1);
152  _M_ptr = nullptr;
153  }
154 
155  protected:
156  typename _AllocTraits::pointer _M_ptr;
157 
158  private:
159  // A simplified, non-copyable std::optional<_NodeAlloc>.
160  // Call release() before destruction iff the allocator member is active.
161  union _Optional_alloc
162  {
163  _Optional_alloc() { }
164  ~_Optional_alloc() { }
165 
166  _Optional_alloc(_Optional_alloc&&) = delete;
167  _Optional_alloc& operator=(_Optional_alloc&&) = delete;
168 
169  _Optional_alloc(const _NodeAlloc& __alloc) noexcept
170  : _M_alloc(__alloc)
171  { }
172 
173  // Precondition: _M_alloc is the active member of the union.
174  void
175  operator=(_NodeAlloc&& __alloc) noexcept
176  {
177  using _ATr = _AllocTraits;
178  if constexpr (_ATr::propagate_on_container_move_assignment::value)
179  _M_alloc = std::move(__alloc);
180  else if constexpr (!_AllocTraits::is_always_equal::value)
181  __glibcxx_assert(_M_alloc == __alloc);
182  }
183 
184  // Precondition: _M_alloc is the active member of both unions.
185  void
186  swap(_Optional_alloc& __other) noexcept
187  {
188  using std::swap;
189  if constexpr (_AllocTraits::propagate_on_container_swap::value)
190  swap(_M_alloc, __other._M_alloc);
191  else if constexpr (!_AllocTraits::is_always_equal::value)
192  __glibcxx_assert(_M_alloc == __other._M_alloc);
193  }
194 
195  // Precondition: _M_alloc is the active member of the union.
196  _NodeAlloc& operator*() noexcept { return _M_alloc; }
197 
198  // Precondition: _M_alloc is the active member of the union.
199  _NodeAlloc release() noexcept
200  {
201  _NodeAlloc __tmp = std::move(_M_alloc);
202  _M_alloc.~_NodeAlloc();
203  return __tmp;
204  }
205 
206  struct _Empty { };
207 
208  [[__no_unique_address__]] _Empty _M_empty;
209  [[__no_unique_address__]] _NodeAlloc _M_alloc;
210  };
211 
212  [[__no_unique_address__]] _Optional_alloc _M_alloc;
213 
214  template<typename _Key2, typename _Value2, typename _KeyOfValue,
215  typename _Compare, typename _ValueAlloc>
216  friend class _Rb_tree;
217  };
218 
219  /// Node handle type for maps.
220  template<typename _Key, typename _Value, typename _NodeAlloc>
221  class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc>
222  {
223  public:
224  constexpr _Node_handle() noexcept = default;
225  ~_Node_handle() = default;
226  _Node_handle(_Node_handle&&) noexcept = default;
227 
228  _Node_handle&
229  operator=(_Node_handle&&) noexcept = default;
230 
231  using key_type = _Key;
232  using mapped_type = typename _Value::second_type;
233 
234  key_type&
235  key() const noexcept
236  {
237  __glibcxx_assert(!this->empty());
238  return *_M_pkey;
239  }
240 
241  mapped_type&
242  mapped() const noexcept
243  {
244  __glibcxx_assert(!this->empty());
245  return *_M_pmapped;
246  }
247 
248  void
249  swap(_Node_handle& __nh) noexcept
250  {
251  this->_M_swap(__nh);
252  using std::swap;
253  swap(_M_pkey, __nh._M_pkey);
254  swap(_M_pmapped, __nh._M_pmapped);
255  }
256 
257  friend void
258  swap(_Node_handle& __x, _Node_handle& __y)
259  noexcept(noexcept(__x.swap(__y)))
260  { __x.swap(__y); }
261 
262  private:
264 
265  _Node_handle(typename _AllocTraits::pointer __ptr,
266  const _NodeAlloc& __alloc)
268  {
269  if (__ptr)
270  {
271  auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
272  _M_pkey = _S_pointer_to(__key);
273  _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
274  }
275  else
276  {
277  _M_pkey = nullptr;
278  _M_pmapped = nullptr;
279  }
280  }
281 
282  template<typename _Tp>
283  using __pointer
286 
287  __pointer<_Key> _M_pkey = nullptr;
288  __pointer<typename _Value::second_type> _M_pmapped = nullptr;
289 
290  template<typename _Tp>
291  __pointer<_Tp>
292  _S_pointer_to(_Tp& __obj)
293  { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
294 
295  const key_type&
296  _M_key() const noexcept { return key(); }
297 
298  template<typename _Key2, typename _Value2, typename _KeyOfValue,
299  typename _Compare, typename _ValueAlloc>
300  friend class _Rb_tree;
301 
302  template<typename _Key2, typename _Value2, typename _ValueAlloc,
303  typename _ExtractKey, typename _Equal,
304  typename _Hash, typename _RangeHash, typename _Unused,
305  typename _RehashPolicy, typename _Traits>
306  friend class _Hashtable;
307  };
308 
309  /// Node handle type for sets.
310  template<typename _Value, typename _NodeAlloc>
311  class _Node_handle<_Value, _Value, _NodeAlloc>
312  : public _Node_handle_common<_Value, _NodeAlloc>
313  {
314  public:
315  constexpr _Node_handle() noexcept = default;
316  ~_Node_handle() = default;
317  _Node_handle(_Node_handle&&) noexcept = default;
318 
319  _Node_handle&
320  operator=(_Node_handle&&) noexcept = default;
321 
322  using value_type = _Value;
323 
324  value_type&
325  value() const noexcept
326  {
327  __glibcxx_assert(!this->empty());
328  return *this->_M_ptr->_M_valptr();
329  }
330 
331  void
332  swap(_Node_handle& __nh) noexcept
333  { this->_M_swap(__nh); }
334 
335  friend void
336  swap(_Node_handle& __x, _Node_handle& __y)
337  noexcept(noexcept(__x.swap(__y)))
338  { __x.swap(__y); }
339 
340  private:
342 
343  _Node_handle(typename _AllocTraits::pointer __ptr,
344  const _NodeAlloc& __alloc)
345  : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
346 
347  const value_type&
348  _M_key() const noexcept { return value(); }
349 
350  template<typename _Key, typename _Val, typename _KeyOfValue,
351  typename _Compare, typename _Alloc>
352  friend class _Rb_tree;
353 
354  template<typename _Key2, typename _Value2, typename _ValueAlloc,
355  typename _ExtractKey, typename _Equal,
356  typename _Hash, typename _RangeHash, typename _Unused,
357  typename _RehashPolicy, typename _Traits>
358  friend class _Hashtable;
359  };
360 
361  /// Return type of insert(node_handle&&) on unique maps/sets.
362  template<typename _Iterator, typename _NodeHandle>
364  {
365  _Iterator position = _Iterator();
366  bool inserted = false;
367  _NodeHandle node;
368  };
369 
370 _GLIBCXX_END_NAMESPACE_VERSION
371 } // namespace std
372 
373 #endif // C++17
374 #endif
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:392
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1645
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:422
ISO C++ entities toplevel namespace is std.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
Definition: ptr_traits.h:152
Uniform interface to all allocator types.
__detected_or_t< value_type *, __pointer, _Alloc > pointer
The allocator's pointer type.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr void destroy(_Alloc &__a, _Tp *__p) noexcept(noexcept(_S_destroy(__a, __p, 0)))
Destroy an object of type _Tp.
Base class for node handle types of maps and sets.
Definition: node_handle.h:50
Node handle type for maps.
Definition: node_handle.h:222
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:364
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:84