libstdc++
node_handle.h
Go to the documentation of this file.
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 <tuple>
41 #include <bits/alloc_traits.h>
42 #include <bits/ptr_traits.h>
43 
44 namespace std _GLIBCXX_VISIBILITY(default)
45 {
46 _GLIBCXX_BEGIN_NAMESPACE_VERSION
47 
48  /// Base class for node handle types of maps and sets.
49  template<typename _Val, typename _NodeAlloc>
50  class _Node_handle_common
51  {
52  using _AllocTraits = allocator_traits<_NodeAlloc>;
53 
54  public:
55  using allocator_type = __alloc_rebind<_NodeAlloc, _Val>;
56 
57  allocator_type
58  get_allocator() const noexcept
59  {
60  __glibcxx_assert(!this->empty());
61  return allocator_type(*_M_alloc);
62  }
63 
64  explicit operator bool() const noexcept { return _M_ptr != nullptr; }
65 
66  bool empty() const noexcept { return _M_ptr == nullptr; }
67 
68  protected:
69  constexpr _Node_handle_common() noexcept : _M_ptr(), _M_alloc() {}
70 
71  ~_Node_handle_common() { _M_destroy(); }
72 
73  _Node_handle_common(_Node_handle_common&& __nh) noexcept
74  : _M_ptr(__nh._M_ptr), _M_alloc(std::move(__nh._M_alloc))
75  {
76  __nh._M_ptr = nullptr;
77  __nh._M_alloc = nullopt;
78  }
79 
80  _Node_handle_common&
81  operator=(_Node_handle_common&& __nh) noexcept
82  {
83  _M_destroy();
84  _M_ptr = __nh._M_ptr;
85  if constexpr (is_move_assignable_v<_NodeAlloc>)
86  {
87  if (_AllocTraits::propagate_on_container_move_assignment::value
88  || !this->_M_alloc)
89  this->_M_alloc = std::move(__nh._M_alloc);
90  else
91  __glibcxx_assert(this->_M_alloc == __nh._M_alloc);
92  }
93  else
94  __glibcxx_assert(_M_alloc);
95  __nh._M_ptr = nullptr;
96  __nh._M_alloc = nullopt;
97  return *this;
98  }
99 
100  _Node_handle_common(typename _AllocTraits::pointer __ptr,
101  const _NodeAlloc& __alloc)
102  : _M_ptr(__ptr), _M_alloc(__alloc) { }
103 
104  void
105  _M_swap(_Node_handle_common& __nh) noexcept
106  {
107  using std::swap;
108  swap(_M_ptr, __nh._M_ptr);
109  if (_AllocTraits::propagate_on_container_swap
110  || !_M_alloc || !__nh._M_alloc)
111  _M_alloc.swap(__nh._M_alloc);
112  else
113  __glibcxx_assert(_M_alloc == __nh._M_alloc);
114  }
115 
116  private:
117  void
118  _M_destroy() noexcept
119  {
120  if (_M_ptr != nullptr)
121  {
122  allocator_type __alloc(*_M_alloc);
124  _M_ptr->_M_valptr());
125  _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1);
126  }
127  }
128 
129  protected:
130  typename _AllocTraits::pointer _M_ptr;
131  private:
132  optional<_NodeAlloc> _M_alloc;
133 
134  template<typename _Key2, typename _Value2, typename _KeyOfValue,
135  typename _Compare, typename _ValueAlloc>
136  friend class _Rb_tree;
137  };
138 
139  /// Node handle type for maps.
140  template<typename _Key, typename _Value, typename _NodeAlloc>
141  class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc>
142  {
143  public:
144  constexpr _Node_handle() noexcept = default;
145  ~_Node_handle() = default;
146  _Node_handle(_Node_handle&&) noexcept = default;
147 
148  _Node_handle&
149  operator=(_Node_handle&&) noexcept = default;
150 
151  using key_type = _Key;
152  using mapped_type = typename _Value::second_type;
153 
154  key_type&
155  key() const noexcept
156  {
157  __glibcxx_assert(!this->empty());
158  return *_M_pkey;
159  }
160 
161  mapped_type&
162  mapped() const noexcept
163  {
164  __glibcxx_assert(!this->empty());
165  return *_M_pmapped;
166  }
167 
168  void
169  swap(_Node_handle& __nh) noexcept
170  {
171  this->_M_swap(__nh);
172  using std::swap;
173  swap(_M_pkey, __nh._M_pkey);
174  swap(_M_pmapped, __nh._M_pmapped);
175  }
176 
177  friend void
178  swap(_Node_handle& __x, _Node_handle& __y)
179  noexcept(noexcept(__x.swap(__y)))
180  { __x.swap(__y); }
181 
182  private:
183  using _AllocTraits = allocator_traits<_NodeAlloc>;
184 
185  _Node_handle(typename _AllocTraits::pointer __ptr,
186  const _NodeAlloc& __alloc)
187  : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
188  {
189  if (__ptr)
190  {
191  auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
192  _M_pkey = _S_pointer_to(__key);
193  _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
194  }
195  else
196  {
197  _M_pkey = nullptr;
198  _M_pmapped = nullptr;
199  }
200  }
201 
202  template<typename _Tp>
203  using __pointer = __ptr_rebind<typename _AllocTraits::pointer, _Tp>;
204 
205  __pointer<_Key> _M_pkey = nullptr;
206  __pointer<typename _Value::second_type> _M_pmapped = nullptr;
207 
208  template<typename _Tp>
209  __pointer<_Tp>
210  _S_pointer_to(_Tp& __obj)
211  { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
212 
213  const key_type&
214  _M_key() const noexcept { return key(); }
215 
216  template<typename _Key2, typename _Value2, typename _KeyOfValue,
217  typename _Compare, typename _ValueAlloc>
218  friend class _Rb_tree;
219 
220  template<typename _Key2, typename _Value2, typename _ValueAlloc,
221  typename _ExtractKey, typename _Equal,
222  typename _H1, typename _H2, typename _Hash,
223  typename _RehashPolicy, typename _Traits>
224  friend class _Hashtable;
225  };
226 
227  /// Node handle type for sets.
228  template<typename _Value, typename _NodeAlloc>
229  class _Node_handle<_Value, _Value, _NodeAlloc>
230  : public _Node_handle_common<_Value, _NodeAlloc>
231  {
232  public:
233  constexpr _Node_handle() noexcept = default;
234  ~_Node_handle() = default;
235  _Node_handle(_Node_handle&&) noexcept = default;
236 
237  _Node_handle&
238  operator=(_Node_handle&&) noexcept = default;
239 
240  using value_type = _Value;
241 
242  value_type&
243  value() const noexcept
244  {
245  __glibcxx_assert(!this->empty());
246  return *this->_M_ptr->_M_valptr();
247  }
248 
249  void
250  swap(_Node_handle& __nh) noexcept
251  { this->_M_swap(__nh); }
252 
253  friend void
254  swap(_Node_handle& __x, _Node_handle& __y)
255  noexcept(noexcept(__x.swap(__y)))
256  { __x.swap(__y); }
257 
258  private:
259  using _AllocTraits = allocator_traits<_NodeAlloc>;
260 
261  _Node_handle(typename _AllocTraits::pointer __ptr,
262  const _NodeAlloc& __alloc)
263  : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
264 
265  const value_type&
266  _M_key() const noexcept { return value(); }
267 
268  template<typename _Key, typename _Val, typename _KeyOfValue,
269  typename _Compare, typename _Alloc>
270  friend class _Rb_tree;
271 
272  template<typename _Key2, typename _Value2, typename _ValueAlloc,
273  typename _ExtractKey, typename _Equal,
274  typename _H1, typename _H2, typename _Hash,
275  typename _RehashPolicy, typename _Traits>
276  friend class _Hashtable;
277  };
278 
279  /// Return type of insert(node_handle&&) on unique maps/sets.
280  template<typename _Iterator, typename _NodeHandle>
281  struct _Node_insert_return
282  {
283  bool inserted = false;
284  _Iterator position = _Iterator();
285  _NodeHandle node;
286 
287  template<size_t _Idx>
288  decltype(auto) get() &
289  { return std::get<_Idx>(std::tie(inserted, position, node)); }
290 
291  template<size_t _Idx>
292  decltype(auto) get() const &
293  { return std::get<_Idx>(std::tie(inserted, position, node)); }
294 
295  template<size_t _Idx>
296  decltype(auto) get() &&
297  {
298  return std::move(std::get<_Idx>(std::tie(inserted, position, node)));
299  }
300 
301  template<size_t _Idx>
302  decltype(auto) get() const &&
303  {
304  return std::move(std::get<_Idx>(std::tie(inserted, position, node)));
305  }
306  };
307 
308  template<typename _Iterator, typename _NodeHandle>
309  struct tuple_size<_Node_insert_return<_Iterator, _NodeHandle>>
310  : integral_constant<size_t, 3> { };
311 
312  template<typename _Iterator, typename _NodeHandle>
313  struct tuple_element<0, _Node_insert_return<_Iterator, _NodeHandle>>
314  { using type = bool; };
315 
316  template<typename _Iterator, typename _NodeHandle>
317  struct tuple_element<1, _Node_insert_return<_Iterator, _NodeHandle>>
318  { using type = _Iterator; };
319 
320  template<typename _Iterator, typename _NodeHandle>
321  struct tuple_element<2, _Node_insert_return<_Iterator, _NodeHandle>>
322  { using type = _NodeHandle; };
323 
324 _GLIBCXX_END_NAMESPACE_VERSION
325 } // namespace std
326 
327 #endif // C++17
328 #endif
constexpr nullopt_t nullopt
Tag to disengage optional objects.
Definition: optional:109
ISO C++ entities toplevel namespace is std.
static void destroy(_Alloc &__a, _Tp *__p)
Destroy an object of type _Tp.
constexpr tuple< _Elements &... > tie(_Elements &...__args) noexcept
tie
Definition: tuple:1589