1 // Node handles for containers -*- C++ -*-
3 // Copyright (C) 2016-2018 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 [[nodiscard
]] 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
);
91 __glibcxx_assert(this->_M_alloc
== __nh
._M_alloc
);
96 __glibcxx_assert(_M_alloc
);
98 __nh
._M_ptr
= nullptr;
99 __nh
._M_alloc
= nullopt
;
103 _Node_handle_common(typename
_AllocTraits::pointer __ptr
,
104 const _NodeAlloc
& __alloc
)
105 : _M_ptr(__ptr
), _M_alloc(__alloc
) { }
108 _M_swap(_Node_handle_common
& __nh
) noexcept
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
);
117 __glibcxx_assert(_M_alloc
== __nh
._M_alloc
);
123 _M_destroy() noexcept
125 if (_M_ptr
!= nullptr)
127 allocator_type
__alloc(*_M_alloc
);
128 allocator_traits
<allocator_type
>::destroy(__alloc
,
129 _M_ptr
->_M_valptr());
130 _AllocTraits::deallocate(*_M_alloc
, _M_ptr
, 1);
135 typename
_AllocTraits::pointer _M_ptr
;
137 optional
<_NodeAlloc
> _M_alloc
;
139 template<typename _Key2
, typename _Value2
, typename _KeyOfValue
,
140 typename _Compare
, typename _ValueAlloc
>
141 friend class _Rb_tree
;
144 /// Node handle type for maps.
145 template<typename _Key
, typename _Value
, typename _NodeAlloc
>
146 class _Node_handle
: public _Node_handle_common
<_Value
, _NodeAlloc
>
149 constexpr _Node_handle() noexcept
= default;
150 ~_Node_handle() = default;
151 _Node_handle(_Node_handle
&&) noexcept
= default;
154 operator=(_Node_handle
&&) noexcept
= default;
156 using key_type
= _Key
;
157 using mapped_type
= typename
_Value::second_type
;
162 __glibcxx_assert(!this->empty());
167 mapped() const noexcept
169 __glibcxx_assert(!this->empty());
174 swap(_Node_handle
& __nh
) noexcept
178 swap(_M_pkey
, __nh
._M_pkey
);
179 swap(_M_pmapped
, __nh
._M_pmapped
);
183 swap(_Node_handle
& __x
, _Node_handle
& __y
)
184 noexcept(noexcept(__x
.swap(__y
)))
188 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
190 _Node_handle(typename
_AllocTraits::pointer __ptr
,
191 const _NodeAlloc
& __alloc
)
192 : _Node_handle_common
<_Value
, _NodeAlloc
>(__ptr
, __alloc
)
196 auto& __key
= const_cast<_Key
&>(__ptr
->_M_valptr()->first
);
197 _M_pkey
= _S_pointer_to(__key
);
198 _M_pmapped
= _S_pointer_to(__ptr
->_M_valptr()->second
);
203 _M_pmapped
= nullptr;
207 template<typename _Tp
>
209 = __ptr_rebind
<typename
_AllocTraits::pointer
,
210 remove_reference_t
<_Tp
>>;
212 __pointer
<_Key
> _M_pkey
= nullptr;
213 __pointer
<typename
_Value::second_type
> _M_pmapped
= nullptr;
215 template<typename _Tp
>
217 _S_pointer_to(_Tp
& __obj
)
218 { return pointer_traits
<__pointer
<_Tp
>>::pointer_to(__obj
); }
221 _M_key() const noexcept
{ return key(); }
223 template<typename _Key2
, typename _Value2
, typename _KeyOfValue
,
224 typename _Compare
, typename _ValueAlloc
>
225 friend class _Rb_tree
;
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
;
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
>
240 constexpr _Node_handle() noexcept
= default;
241 ~_Node_handle() = default;
242 _Node_handle(_Node_handle
&&) noexcept
= default;
245 operator=(_Node_handle
&&) noexcept
= default;
247 using value_type
= _Value
;
250 value() const noexcept
252 __glibcxx_assert(!this->empty());
253 return *this->_M_ptr
->_M_valptr();
257 swap(_Node_handle
& __nh
) noexcept
258 { this->_M_swap(__nh
); }
261 swap(_Node_handle
& __x
, _Node_handle
& __y
)
262 noexcept(noexcept(__x
.swap(__y
)))
266 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
268 _Node_handle(typename
_AllocTraits::pointer __ptr
,
269 const _NodeAlloc
& __alloc
)
270 : _Node_handle_common
<_Value
, _NodeAlloc
>(__ptr
, __alloc
) { }
273 _M_key() const noexcept
{ return value(); }
275 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
276 typename _Compare
, typename _Alloc
>
277 friend class _Rb_tree
;
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
;
286 /// Return type of insert(node_handle&&) on unique maps/sets.
287 template<typename _Iterator
, typename _NodeHandle
>
288 struct _Node_insert_return
290 _Iterator position
= _Iterator();
291 bool inserted
= false;
295 _GLIBCXX_END_NAMESPACE_VERSION