Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/node_handle.h
1 // Node handles for containers -*- C++ -*- 2 3 // Copyright (C) 2016-2025 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 #ifdef _GLIBCXX_SYSHDR 35 #pragma GCC system_header 36 #endif 37 38 #include <bits/version.h> 39 40 #ifdef __glibcxx_node_extract // C++ >= 17 && HOSTED 41 42 #include <new> 43 #include <bits/alloc_traits.h> 44 #include <bits/ptr_traits.h> 45 46 namespace std _GLIBCXX_VISIBILITY(default) 47 { 48 _GLIBCXX_BEGIN_NAMESPACE_VERSION 49 50 /** 51 * @defgroup node_handles Node handles 52 * @ingroup associative_containers 53 * @since C++17 54 * 55 * The associative containers (`map`, `set`, `multimap` and `multiset`) 56 * support extracting and re-inserting nodes from the container. Those 57 * operations use the container's `node_handle` type, which is an alias 58 * for a `_Node_handle<...>` type. You should always use the container's 59 * `node_handle` type (e.g. `std::set<int>::node_handle`) to refer to 60 * these types, not the non-standard internal `_Node_handle` names. 61 * 62 * @{ 63 */ 64 65 /// Base class for node handle types of maps and sets. 66 template<typename _Val, typename _NodeAlloc> 67 class _Node_handle_common 68 { 69 using _AllocTraits = allocator_traits<_NodeAlloc>; 70 71 public: 72 using allocator_type = __alloc_rebind<_NodeAlloc, _Val>; 73 74 allocator_type 75 get_allocator() const noexcept 76 { 77 __glibcxx_assert(!this->empty()); 78 return allocator_type(_M_alloc._M_alloc); 79 } 80 81 explicit operator bool() const noexcept { return _M_ptr != nullptr; } 82 83 [[nodiscard]] bool empty() const noexcept { return _M_ptr == nullptr; } 84 85 /// @cond undocumented 86 protected: 87 constexpr _Node_handle_common() noexcept : _M_ptr() { } 88 89 ~_Node_handle_common() 90 { 91 if (!empty()) 92 _M_reset(); 93 } 94 95 _Node_handle_common(_Node_handle_common&& __nh) noexcept 96 : _M_ptr(__nh._M_ptr) 97 { 98 if (_M_ptr) 99 _M_move(std::move(__nh)); 100 } 101 102 _Node_handle_common& 103 operator=(_Node_handle_common&& __nh) noexcept 104 { 105 if (empty()) 106 { 107 if (!__nh.empty()) 108 _M_move(std::move(__nh)); 109 } 110 else if (__nh.empty()) 111 _M_reset(); 112 else 113 { 114 // Free the current node before replacing the allocator. 115 _AllocTraits::destroy(*_M_alloc, _M_ptr->_M_valptr()); 116 _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1); 117 118 _M_alloc = __nh._M_alloc.release(); // assigns if POCMA 119 _M_ptr = __nh._M_ptr; 120 __nh._M_ptr = nullptr; 121 } 122 return *this; 123 } 124 125 _Node_handle_common(typename _AllocTraits::pointer __ptr, 126 const _NodeAlloc& __alloc) 127 : _M_ptr(__ptr), _M_alloc(__alloc) 128 { 129 __glibcxx_assert(__ptr != nullptr); 130 } 131 132 void 133 _M_swap(_Node_handle_common& __nh) noexcept 134 { 135 if (empty()) 136 { 137 if (!__nh.empty()) 138 _M_move(std::move(__nh)); 139 } 140 else if (__nh.empty()) 141 __nh._M_move(std::move(*this)); 142 else 143 { 144 using std::swap; 145 swap(_M_ptr, __nh._M_ptr); 146 _M_alloc.swap(__nh._M_alloc); // swaps if POCS 147 } 148 } 149 150 private: 151 // Moves the pointer and allocator from __nh to *this. 152 // Precondition: empty() && !__nh.empty() 153 // Postcondition: !empty() && __nh.empty() 154 void 155 _M_move(_Node_handle_common&& __nh) noexcept 156 { 157 ::new (std::__addressof(_M_alloc)) _NodeAlloc(__nh._M_alloc.release()); 158 _M_ptr = __nh._M_ptr; 159 __nh._M_ptr = nullptr; 160 } 161 162 // Deallocates the node, destroys the allocator. 163 // Precondition: !empty() 164 // Postcondition: empty() 165 void 166 _M_reset() noexcept 167 { 168 _NodeAlloc __alloc = _M_alloc.release(); 169 _AllocTraits::destroy(__alloc, _M_ptr->_M_valptr()); 170 _AllocTraits::deallocate(__alloc, _M_ptr, 1); 171 _M_ptr = nullptr; 172 } 173 174 // Destroys the allocator. Does not deallocate or destroy the node. 175 // Precondition: !empty() 176 // Postcondition: empty() 177 void 178 release() noexcept 179 { 180 _M_alloc.release(); 181 _M_ptr = nullptr; 182 } 183 184 protected: 185 typename _AllocTraits::pointer _M_ptr; 186 187 private: 188 // A simplified, non-copyable std::optional<_NodeAlloc>. 189 // Call release() before destruction iff the allocator member is active. 190 union _Optional_alloc 191 { 192 _Optional_alloc() { } 193 ~_Optional_alloc() { } 194 195 _Optional_alloc(_Optional_alloc&&) = delete; 196 _Optional_alloc& operator=(_Optional_alloc&&) = delete; 197 198 _Optional_alloc(const _NodeAlloc& __alloc) noexcept 199 : _M_alloc(__alloc) 200 { } 201 202 // Precondition: _M_alloc is the active member of the union. 203 void 204 operator=(_NodeAlloc&& __alloc) noexcept 205 { 206 using _ATr = _AllocTraits; 207 if constexpr (_ATr::propagate_on_container_move_assignment::value) 208 _M_alloc = std::move(__alloc); 209 else if constexpr (!_AllocTraits::is_always_equal::value) 210 __glibcxx_assert(_M_alloc == __alloc); 211 } 212 213 // Precondition: _M_alloc is the active member of both unions. 214 void 215 swap(_Optional_alloc& __other) noexcept 216 { 217 using std::swap; 218 if constexpr (_AllocTraits::propagate_on_container_swap::value) 219 swap(_M_alloc, __other._M_alloc); 220 else if constexpr (!_AllocTraits::is_always_equal::value) 221 __glibcxx_assert(_M_alloc == __other._M_alloc); 222 } 223 224 // Precondition: _M_alloc is the active member of the union. 225 _NodeAlloc& operator*() noexcept { return _M_alloc; } 226 227 // Precondition: _M_alloc is the active member of the union. 228 _NodeAlloc release() noexcept 229 { 230 _NodeAlloc __tmp = std::move(_M_alloc); 231 _M_alloc.~_NodeAlloc(); 232 return __tmp; 233 } 234 235 [[__no_unique_address__]] _NodeAlloc _M_alloc; 236 }; 237 238 [[__no_unique_address__]] _Optional_alloc _M_alloc; 239 240 template<typename _Key2, typename _Value2, typename _KeyOfValue, 241 typename _Compare, typename _ValueAlloc> 242 friend class _Rb_tree; 243 244 template<typename _Key2, typename _Value2, typename _ValueAlloc, 245 typename _ExtractKey, typename _Equal, 246 typename _Hash, typename _RangeHash, typename _Unused, 247 typename _RehashPolicy, typename _Traits> 248 friend class _Hashtable; 249 250 /// @endcond 251 }; 252 253 /// Node handle type for maps. 254 template<typename _Key, typename _Value, typename _NodeAlloc> 255 class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc> 256 { 257 public: 258 constexpr _Node_handle() noexcept = default; 259 ~_Node_handle() = default; 260 _Node_handle(_Node_handle&&) noexcept = default; 261 262 _Node_handle& 263 operator=(_Node_handle&&) noexcept = default; 264 265 using key_type = _Key; 266 using mapped_type = typename _Value::second_type; 267 268 key_type& 269 key() const noexcept 270 { 271 __glibcxx_assert(!this->empty()); 272 return *_M_pkey; 273 } 274 275 mapped_type& 276 mapped() const noexcept 277 { 278 __glibcxx_assert(!this->empty()); 279 return *_M_pmapped; 280 } 281 282 void 283 swap(_Node_handle& __nh) noexcept 284 { 285 this->_M_swap(__nh); 286 using std::swap; 287 swap(_M_pkey, __nh._M_pkey); 288 swap(_M_pmapped, __nh._M_pmapped); 289 } 290 291 friend void 292 swap(_Node_handle& __x, _Node_handle& __y) 293 noexcept(noexcept(__x.swap(__y))) 294 { __x.swap(__y); } 295 296 private: 297 using _AllocTraits = allocator_traits<_NodeAlloc>; 298 299 _Node_handle(typename _AllocTraits::pointer __ptr, 300 const _NodeAlloc& __alloc) 301 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) 302 { 303 if (__ptr) 304 { 305 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first); 306 _M_pkey = _S_pointer_to(__key); 307 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second); 308 } 309 else 310 { 311 _M_pkey = nullptr; 312 _M_pmapped = nullptr; 313 } 314 } 315 316 template<typename _Tp> 317 using __pointer 318 = __ptr_rebind<typename _AllocTraits::pointer, 319 remove_reference_t<_Tp>>; 320 321 __pointer<_Key> _M_pkey = nullptr; 322 __pointer<typename _Value::second_type> _M_pmapped = nullptr; 323 324 template<typename _Tp> 325 __pointer<_Tp> 326 _S_pointer_to(_Tp& __obj) 327 { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); } 328 329 const key_type& 330 _M_key() const noexcept { return key(); } 331 332 template<typename _Key2, typename _Value2, typename _KeyOfValue, 333 typename _Compare, typename _ValueAlloc> 334 friend class _Rb_tree; 335 336 template<typename _Key2, typename _Value2, typename _ValueAlloc, 337 typename _ExtractKey, typename _Equal, 338 typename _Hash, typename _RangeHash, typename _Unused, 339 typename _RehashPolicy, typename _Traits> 340 friend class _Hashtable; 341 }; 342 343 /// Node handle type for sets. 344 template<typename _Value, typename _NodeAlloc> 345 class _Node_handle<_Value, _Value, _NodeAlloc> 346 : public _Node_handle_common<_Value, _NodeAlloc> 347 { 348 public: 349 constexpr _Node_handle() noexcept = default; 350 ~_Node_handle() = default; 351 _Node_handle(_Node_handle&&) noexcept = default; 352 353 _Node_handle& 354 operator=(_Node_handle&&) noexcept = default; 355 356 using value_type = _Value; 357 358 value_type& 359 value() const noexcept 360 { 361 __glibcxx_assert(!this->empty()); 362 return *this->_M_ptr->_M_valptr(); 363 } 364 365 void 366 swap(_Node_handle& __nh) noexcept 367 { this->_M_swap(__nh); } 368 369 friend void 370 swap(_Node_handle& __x, _Node_handle& __y) 371 noexcept(noexcept(__x.swap(__y))) 372 { __x.swap(__y); } 373 374 private: 375 using _AllocTraits = allocator_traits<_NodeAlloc>; 376 377 _Node_handle(typename _AllocTraits::pointer __ptr, 378 const _NodeAlloc& __alloc) 379 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { } 380 381 const value_type& 382 _M_key() const noexcept { return value(); } 383 384 template<typename _Key, typename _Val, typename _KeyOfValue, 385 typename _Compare, typename _Alloc> 386 friend class _Rb_tree; 387 388 template<typename _Key2, typename _Value2, typename _ValueAlloc, 389 typename _ExtractKey, typename _Equal, 390 typename _Hash, typename _RangeHash, typename _Unused, 391 typename _RehashPolicy, typename _Traits> 392 friend class _Hashtable; 393 }; 394 395 /// Return type of insert(node_handle&&) on unique maps/sets. 396 template<typename _Iterator, typename _NodeHandle> 397 struct _Node_insert_return 398 { 399 _Iterator position = _Iterator(); 400 bool inserted = false; 401 _NodeHandle node; 402 }; 403 404 /// @} 405 406 _GLIBCXX_END_NAMESPACE_VERSION 407 } // namespace std 408 409 #endif // __glibcxx_node_extract 410 #endif
