libstdc++
|
00001 // Node handles for containers -*- C++ -*- 00002 00003 // Copyright (C) 2016-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file bits/node_handle.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. 00028 * @headername{map,set,unordered_map,unordered_set} 00029 */ 00030 00031 #ifndef _NODE_HANDLE 00032 #define _NODE_HANDLE 1 00033 00034 #pragma GCC system_header 00035 00036 #if __cplusplus > 201402L 00037 # define __cpp_lib_node_extract 201606 00038 00039 #include <optional> 00040 #include <bits/alloc_traits.h> 00041 #include <bits/ptr_traits.h> 00042 00043 namespace std _GLIBCXX_VISIBILITY(default) 00044 { 00045 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00046 00047 /// Base class for node handle types of maps and sets. 00048 template<typename _Val, typename _NodeAlloc> 00049 class _Node_handle_common 00050 { 00051 using _AllocTraits = allocator_traits<_NodeAlloc>; 00052 00053 public: 00054 using allocator_type = __alloc_rebind<_NodeAlloc, _Val>; 00055 00056 allocator_type 00057 get_allocator() const noexcept 00058 { 00059 __glibcxx_assert(!this->empty()); 00060 return allocator_type(*_M_alloc); 00061 } 00062 00063 explicit operator bool() const noexcept { return _M_ptr != nullptr; } 00064 00065 [[nodiscard]] bool empty() const noexcept { return _M_ptr == nullptr; } 00066 00067 protected: 00068 constexpr _Node_handle_common() noexcept : _M_ptr(), _M_alloc() {} 00069 00070 ~_Node_handle_common() { _M_destroy(); } 00071 00072 _Node_handle_common(_Node_handle_common&& __nh) noexcept 00073 : _M_ptr(__nh._M_ptr), _M_alloc(std::move(__nh._M_alloc)) 00074 { 00075 __nh._M_ptr = nullptr; 00076 __nh._M_alloc = nullopt; 00077 } 00078 00079 _Node_handle_common& 00080 operator=(_Node_handle_common&& __nh) noexcept 00081 { 00082 _M_destroy(); 00083 _M_ptr = __nh._M_ptr; 00084 if constexpr (is_move_assignable_v<_NodeAlloc>) 00085 { 00086 if (_AllocTraits::propagate_on_container_move_assignment::value 00087 || !this->_M_alloc) 00088 this->_M_alloc = std::move(__nh._M_alloc); 00089 else 00090 { 00091 __glibcxx_assert(this->_M_alloc == __nh._M_alloc); 00092 } 00093 } 00094 else 00095 { 00096 __glibcxx_assert(_M_alloc); 00097 } 00098 __nh._M_ptr = nullptr; 00099 __nh._M_alloc = nullopt; 00100 return *this; 00101 } 00102 00103 _Node_handle_common(typename _AllocTraits::pointer __ptr, 00104 const _NodeAlloc& __alloc) 00105 : _M_ptr(__ptr), _M_alloc(__alloc) { } 00106 00107 void 00108 _M_swap(_Node_handle_common& __nh) noexcept 00109 { 00110 using std::swap; 00111 swap(_M_ptr, __nh._M_ptr); 00112 if (_AllocTraits::propagate_on_container_swap::value 00113 || !_M_alloc || !__nh._M_alloc) 00114 _M_alloc.swap(__nh._M_alloc); 00115 else 00116 { 00117 __glibcxx_assert(_M_alloc == __nh._M_alloc); 00118 } 00119 } 00120 00121 private: 00122 void 00123 _M_destroy() noexcept 00124 { 00125 if (_M_ptr != nullptr) 00126 { 00127 allocator_type __alloc(*_M_alloc); 00128 allocator_traits<allocator_type>::destroy(__alloc, 00129 _M_ptr->_M_valptr()); 00130 _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1); 00131 } 00132 } 00133 00134 protected: 00135 typename _AllocTraits::pointer _M_ptr; 00136 private: 00137 optional<_NodeAlloc> _M_alloc; 00138 00139 template<typename _Key2, typename _Value2, typename _KeyOfValue, 00140 typename _Compare, typename _ValueAlloc> 00141 friend class _Rb_tree; 00142 }; 00143 00144 /// Node handle type for maps. 00145 template<typename _Key, typename _Value, typename _NodeAlloc> 00146 class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc> 00147 { 00148 public: 00149 constexpr _Node_handle() noexcept = default; 00150 ~_Node_handle() = default; 00151 _Node_handle(_Node_handle&&) noexcept = default; 00152 00153 _Node_handle& 00154 operator=(_Node_handle&&) noexcept = default; 00155 00156 using key_type = _Key; 00157 using mapped_type = typename _Value::second_type; 00158 00159 key_type& 00160 key() const noexcept 00161 { 00162 __glibcxx_assert(!this->empty()); 00163 return *_M_pkey; 00164 } 00165 00166 mapped_type& 00167 mapped() const noexcept 00168 { 00169 __glibcxx_assert(!this->empty()); 00170 return *_M_pmapped; 00171 } 00172 00173 void 00174 swap(_Node_handle& __nh) noexcept 00175 { 00176 this->_M_swap(__nh); 00177 using std::swap; 00178 swap(_M_pkey, __nh._M_pkey); 00179 swap(_M_pmapped, __nh._M_pmapped); 00180 } 00181 00182 friend void 00183 swap(_Node_handle& __x, _Node_handle& __y) 00184 noexcept(noexcept(__x.swap(__y))) 00185 { __x.swap(__y); } 00186 00187 private: 00188 using _AllocTraits = allocator_traits<_NodeAlloc>; 00189 00190 _Node_handle(typename _AllocTraits::pointer __ptr, 00191 const _NodeAlloc& __alloc) 00192 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) 00193 { 00194 if (__ptr) 00195 { 00196 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first); 00197 _M_pkey = _S_pointer_to(__key); 00198 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second); 00199 } 00200 else 00201 { 00202 _M_pkey = nullptr; 00203 _M_pmapped = nullptr; 00204 } 00205 } 00206 00207 template<typename _Tp> 00208 using __pointer 00209 = __ptr_rebind<typename _AllocTraits::pointer, 00210 remove_reference_t<_Tp>>; 00211 00212 __pointer<_Key> _M_pkey = nullptr; 00213 __pointer<typename _Value::second_type> _M_pmapped = nullptr; 00214 00215 template<typename _Tp> 00216 __pointer<_Tp> 00217 _S_pointer_to(_Tp& __obj) 00218 { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); } 00219 00220 const key_type& 00221 _M_key() const noexcept { return key(); } 00222 00223 template<typename _Key2, typename _Value2, typename _KeyOfValue, 00224 typename _Compare, typename _ValueAlloc> 00225 friend class _Rb_tree; 00226 00227 template<typename _Key2, typename _Value2, typename _ValueAlloc, 00228 typename _ExtractKey, typename _Equal, 00229 typename _H1, typename _H2, typename _Hash, 00230 typename _RehashPolicy, typename _Traits> 00231 friend class _Hashtable; 00232 }; 00233 00234 /// Node handle type for sets. 00235 template<typename _Value, typename _NodeAlloc> 00236 class _Node_handle<_Value, _Value, _NodeAlloc> 00237 : public _Node_handle_common<_Value, _NodeAlloc> 00238 { 00239 public: 00240 constexpr _Node_handle() noexcept = default; 00241 ~_Node_handle() = default; 00242 _Node_handle(_Node_handle&&) noexcept = default; 00243 00244 _Node_handle& 00245 operator=(_Node_handle&&) noexcept = default; 00246 00247 using value_type = _Value; 00248 00249 value_type& 00250 value() const noexcept 00251 { 00252 __glibcxx_assert(!this->empty()); 00253 return *this->_M_ptr->_M_valptr(); 00254 } 00255 00256 void 00257 swap(_Node_handle& __nh) noexcept 00258 { this->_M_swap(__nh); } 00259 00260 friend void 00261 swap(_Node_handle& __x, _Node_handle& __y) 00262 noexcept(noexcept(__x.swap(__y))) 00263 { __x.swap(__y); } 00264 00265 private: 00266 using _AllocTraits = allocator_traits<_NodeAlloc>; 00267 00268 _Node_handle(typename _AllocTraits::pointer __ptr, 00269 const _NodeAlloc& __alloc) 00270 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { } 00271 00272 const value_type& 00273 _M_key() const noexcept { return value(); } 00274 00275 template<typename _Key, typename _Val, typename _KeyOfValue, 00276 typename _Compare, typename _Alloc> 00277 friend class _Rb_tree; 00278 00279 template<typename _Key2, typename _Value2, typename _ValueAlloc, 00280 typename _ExtractKey, typename _Equal, 00281 typename _H1, typename _H2, typename _Hash, 00282 typename _RehashPolicy, typename _Traits> 00283 friend class _Hashtable; 00284 }; 00285 00286 /// Return type of insert(node_handle&&) on unique maps/sets. 00287 template<typename _Iterator, typename _NodeHandle> 00288 struct _Node_insert_return 00289 { 00290 _Iterator position = _Iterator(); 00291 bool inserted = false; 00292 _NodeHandle node; 00293 }; 00294 00295 _GLIBCXX_END_NAMESPACE_VERSION 00296 } // namespace std 00297 00298 #endif // C++17 00299 #endif