1 // Node handles for containers -*- C++ -*-
3 // Copyright (C) 2016-2017 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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}
32 #define _NODE_HANDLE 1
34 #pragma GCC system_header
36 #if __cplusplus > 201402L
37 # define __cpp_lib_node_extract 201606
40 #include <bits/alloc_traits.h>
41 #include <bits/ptr_traits.h>
43 namespace std
_GLIBCXX_VISIBILITY(default)
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
47 /// Base class for node handle types of maps and sets.
48 template<typename _Val
, typename _NodeAlloc
>
49 class _Node_handle_common
51 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
54 using allocator_type
= __alloc_rebind
<_NodeAlloc
, _Val
>;
57 get_allocator() const noexcept
59 __glibcxx_assert(!this->empty());
60 return allocator_type(*_M_alloc
);
63 explicit operator bool() const noexcept
{ return _M_ptr
!= nullptr; }
65 bool empty() const noexcept
{ return _M_ptr
== nullptr; }
68 constexpr _Node_handle_common() noexcept
: _M_ptr(), _M_alloc() {}
70 ~_Node_handle_common() { _M_destroy(); }
72 _Node_handle_common(_Node_handle_common
&& __nh
) noexcept
73 : _M_ptr(__nh
._M_ptr
), _M_alloc(std::move(__nh
._M_alloc
))
75 __nh
._M_ptr
= nullptr;
76 __nh
._M_alloc
= nullopt
;
80 operator=(_Node_handle_common
&& __nh
) noexcept
84 if constexpr (is_move_assignable_v
<_NodeAlloc
>)
86 if (_AllocTraits::propagate_on_container_move_assignment::value
88 this->_M_alloc
= std::move(__nh
._M_alloc
);
90 __glibcxx_assert(this->_M_alloc
== __nh
._M_alloc
);
93 __glibcxx_assert(_M_alloc
);
94 __nh
._M_ptr
= nullptr;
95 __nh
._M_alloc
= nullopt
;
99 _Node_handle_common(typename
_AllocTraits::pointer __ptr
,
100 const _NodeAlloc
& __alloc
)
101 : _M_ptr(__ptr
), _M_alloc(__alloc
) { }
104 _M_swap(_Node_handle_common
& __nh
) noexcept
107 swap(_M_ptr
, __nh
._M_ptr
);
108 if (_AllocTraits::propagate_on_container_swap
109 || !_M_alloc
|| !__nh
._M_alloc
)
110 _M_alloc
.swap(__nh
._M_alloc
);
112 __glibcxx_assert(_M_alloc
== __nh
._M_alloc
);
117 _M_destroy() noexcept
119 if (_M_ptr
!= nullptr)
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);
129 typename
_AllocTraits::pointer _M_ptr
;
131 optional
<_NodeAlloc
> _M_alloc
;
133 template<typename _Key2
, typename _Value2
, typename _KeyOfValue
,
134 typename _Compare
, typename _ValueAlloc
>
135 friend class _Rb_tree
;
138 /// Node handle type for maps.
139 template<typename _Key
, typename _Value
, typename _NodeAlloc
>
140 class _Node_handle
: public _Node_handle_common
<_Value
, _NodeAlloc
>
143 constexpr _Node_handle() noexcept
= default;
144 ~_Node_handle() = default;
145 _Node_handle(_Node_handle
&&) noexcept
= default;
148 operator=(_Node_handle
&&) noexcept
= default;
150 using key_type
= _Key
;
151 using mapped_type
= typename
_Value::second_type
;
156 __glibcxx_assert(!this->empty());
161 mapped() const noexcept
163 __glibcxx_assert(!this->empty());
168 swap(_Node_handle
& __nh
) noexcept
172 swap(_M_pkey
, __nh
._M_pkey
);
173 swap(_M_pmapped
, __nh
._M_pmapped
);
177 swap(_Node_handle
& __x
, _Node_handle
& __y
)
178 noexcept(noexcept(__x
.swap(__y
)))
182 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
184 _Node_handle(typename
_AllocTraits::pointer __ptr
,
185 const _NodeAlloc
& __alloc
)
186 : _Node_handle_common
<_Value
, _NodeAlloc
>(__ptr
, __alloc
)
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
);
197 _M_pmapped
= nullptr;
201 template<typename _Tp
>
202 using __pointer
= __ptr_rebind
<typename
_AllocTraits::pointer
, _Tp
>;
204 __pointer
<_Key
> _M_pkey
= nullptr;
205 __pointer
<typename
_Value::second_type
> _M_pmapped
= nullptr;
207 template<typename _Tp
>
209 _S_pointer_to(_Tp
& __obj
)
210 { return pointer_traits
<__pointer
<_Tp
>>::pointer_to(__obj
); }
213 _M_key() const noexcept
{ return key(); }
215 template<typename _Key2
, typename _Value2
, typename _KeyOfValue
,
216 typename _Compare
, typename _ValueAlloc
>
217 friend class _Rb_tree
;
219 template<typename _Key2
, typename _Value2
, typename _ValueAlloc
,
220 typename _ExtractKey
, typename _Equal
,
221 typename _H1
, typename _H2
, typename _Hash
,
222 typename _RehashPolicy
, typename _Traits
>
223 friend class _Hashtable
;
226 /// Node handle type for sets.
227 template<typename _Value
, typename _NodeAlloc
>
228 class _Node_handle
<_Value
, _Value
, _NodeAlloc
>
229 : public _Node_handle_common
<_Value
, _NodeAlloc
>
232 constexpr _Node_handle() noexcept
= default;
233 ~_Node_handle() = default;
234 _Node_handle(_Node_handle
&&) noexcept
= default;
237 operator=(_Node_handle
&&) noexcept
= default;
239 using value_type
= _Value
;
242 value() const noexcept
244 __glibcxx_assert(!this->empty());
245 return *this->_M_ptr
->_M_valptr();
249 swap(_Node_handle
& __nh
) noexcept
250 { this->_M_swap(__nh
); }
253 swap(_Node_handle
& __x
, _Node_handle
& __y
)
254 noexcept(noexcept(__x
.swap(__y
)))
258 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
260 _Node_handle(typename
_AllocTraits::pointer __ptr
,
261 const _NodeAlloc
& __alloc
)
262 : _Node_handle_common
<_Value
, _NodeAlloc
>(__ptr
, __alloc
) { }
265 _M_key() const noexcept
{ return value(); }
267 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
268 typename _Compare
, typename _Alloc
>
269 friend class _Rb_tree
;
271 template<typename _Key2
, typename _Value2
, typename _ValueAlloc
,
272 typename _ExtractKey
, typename _Equal
,
273 typename _H1
, typename _H2
, typename _Hash
,
274 typename _RehashPolicy
, typename _Traits
>
275 friend class _Hashtable
;
278 /// Return type of insert(node_handle&&) on unique maps/sets.
279 template<typename _Iterator
, typename _NodeHandle
>
280 struct _Node_insert_return
282 _Iterator position
= _Iterator();
283 bool inserted
= false;
287 _GLIBCXX_END_NAMESPACE_VERSION