libstdc++
|
00001 // Node handles for containers -*- C++ -*- 00002 00003 // Copyright (C) 2016-2017 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 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 __glibcxx_assert(this->_M_alloc == __nh._M_alloc); 00091 } 00092 else 00093 __glibcxx_assert(_M_alloc); 00094 __nh._M_ptr = nullptr; 00095 __nh._M_alloc = nullopt; 00096 return *this; 00097 } 00098 00099 _Node_handle_common(typename _AllocTraits::pointer __ptr, 00100 const _NodeAlloc& __alloc) 00101 : _M_ptr(__ptr), _M_alloc(__alloc) { } 00102 00103 void 00104 _M_swap(_Node_handle_common& __nh) noexcept 00105 { 00106 using std::swap; 00107 swap(_M_ptr, __nh._M_ptr); 00108 if (_AllocTraits::propagate_on_container_swap 00109 || !_M_alloc || !__nh._M_alloc) 00110 _M_alloc.swap(__nh._M_alloc); 00111 else 00112 __glibcxx_assert(_M_alloc == __nh._M_alloc); 00113 } 00114 00115 private: 00116 void 00117 _M_destroy() noexcept 00118 { 00119 if (_M_ptr != nullptr) 00120 { 00121 allocator_type __alloc(*_M_alloc); 00122 allocator_traits<allocator_type>::destroy(__alloc, 00123 _M_ptr->_M_valptr()); 00124 _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1); 00125 } 00126 } 00127 00128 protected: 00129 typename _AllocTraits::pointer _M_ptr; 00130 private: 00131 optional<_NodeAlloc> _M_alloc; 00132 00133 template<typename _Key2, typename _Value2, typename _KeyOfValue, 00134 typename _Compare, typename _ValueAlloc> 00135 friend class _Rb_tree; 00136 }; 00137 00138 /// Node handle type for maps. 00139 template<typename _Key, typename _Value, typename _NodeAlloc> 00140 class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc> 00141 { 00142 public: 00143 constexpr _Node_handle() noexcept = default; 00144 ~_Node_handle() = default; 00145 _Node_handle(_Node_handle&&) noexcept = default; 00146 00147 _Node_handle& 00148 operator=(_Node_handle&&) noexcept = default; 00149 00150 using key_type = _Key; 00151 using mapped_type = typename _Value::second_type; 00152 00153 key_type& 00154 key() const noexcept 00155 { 00156 __glibcxx_assert(!this->empty()); 00157 return *_M_pkey; 00158 } 00159 00160 mapped_type& 00161 mapped() const noexcept 00162 { 00163 __glibcxx_assert(!this->empty()); 00164 return *_M_pmapped; 00165 } 00166 00167 void 00168 swap(_Node_handle& __nh) noexcept 00169 { 00170 this->_M_swap(__nh); 00171 using std::swap; 00172 swap(_M_pkey, __nh._M_pkey); 00173 swap(_M_pmapped, __nh._M_pmapped); 00174 } 00175 00176 friend void 00177 swap(_Node_handle& __x, _Node_handle& __y) 00178 noexcept(noexcept(__x.swap(__y))) 00179 { __x.swap(__y); } 00180 00181 private: 00182 using _AllocTraits = allocator_traits<_NodeAlloc>; 00183 00184 _Node_handle(typename _AllocTraits::pointer __ptr, 00185 const _NodeAlloc& __alloc) 00186 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) 00187 { 00188 if (__ptr) 00189 { 00190 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first); 00191 _M_pkey = _S_pointer_to(__key); 00192 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second); 00193 } 00194 else 00195 { 00196 _M_pkey = nullptr; 00197 _M_pmapped = nullptr; 00198 } 00199 } 00200 00201 template<typename _Tp> 00202 using __pointer 00203 = __ptr_rebind<typename _AllocTraits::pointer, 00204 remove_reference_t<_Tp>>; 00205 00206 __pointer<_Key> _M_pkey = nullptr; 00207 __pointer<typename _Value::second_type> _M_pmapped = nullptr; 00208 00209 template<typename _Tp> 00210 __pointer<_Tp> 00211 _S_pointer_to(_Tp& __obj) 00212 { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); } 00213 00214 const key_type& 00215 _M_key() const noexcept { return key(); } 00216 00217 template<typename _Key2, typename _Value2, typename _KeyOfValue, 00218 typename _Compare, typename _ValueAlloc> 00219 friend class _Rb_tree; 00220 00221 template<typename _Key2, typename _Value2, typename _ValueAlloc, 00222 typename _ExtractKey, typename _Equal, 00223 typename _H1, typename _H2, typename _Hash, 00224 typename _RehashPolicy, typename _Traits> 00225 friend class _Hashtable; 00226 }; 00227 00228 /// Node handle type for sets. 00229 template<typename _Value, typename _NodeAlloc> 00230 class _Node_handle<_Value, _Value, _NodeAlloc> 00231 : public _Node_handle_common<_Value, _NodeAlloc> 00232 { 00233 public: 00234 constexpr _Node_handle() noexcept = default; 00235 ~_Node_handle() = default; 00236 _Node_handle(_Node_handle&&) noexcept = default; 00237 00238 _Node_handle& 00239 operator=(_Node_handle&&) noexcept = default; 00240 00241 using value_type = _Value; 00242 00243 value_type& 00244 value() const noexcept 00245 { 00246 __glibcxx_assert(!this->empty()); 00247 return *this->_M_ptr->_M_valptr(); 00248 } 00249 00250 void 00251 swap(_Node_handle& __nh) noexcept 00252 { this->_M_swap(__nh); } 00253 00254 friend void 00255 swap(_Node_handle& __x, _Node_handle& __y) 00256 noexcept(noexcept(__x.swap(__y))) 00257 { __x.swap(__y); } 00258 00259 private: 00260 using _AllocTraits = allocator_traits<_NodeAlloc>; 00261 00262 _Node_handle(typename _AllocTraits::pointer __ptr, 00263 const _NodeAlloc& __alloc) 00264 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { } 00265 00266 const value_type& 00267 _M_key() const noexcept { return value(); } 00268 00269 template<typename _Key, typename _Val, typename _KeyOfValue, 00270 typename _Compare, typename _Alloc> 00271 friend class _Rb_tree; 00272 00273 template<typename _Key2, typename _Value2, typename _ValueAlloc, 00274 typename _ExtractKey, typename _Equal, 00275 typename _H1, typename _H2, typename _Hash, 00276 typename _RehashPolicy, typename _Traits> 00277 friend class _Hashtable; 00278 }; 00279 00280 /// Return type of insert(node_handle&&) on unique maps/sets. 00281 template<typename _Iterator, typename _NodeHandle> 00282 struct _Node_insert_return 00283 { 00284 _Iterator position = _Iterator(); 00285 bool inserted = false; 00286 _NodeHandle node; 00287 }; 00288 00289 _GLIBCXX_END_NAMESPACE_VERSION 00290 } // namespace std 00291 00292 #endif // C++17 00293 #endif