1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___NODE_HANDLE
11#define _LIBCPP___NODE_HANDLE
12
13/*
14
15template<unspecified>
16class node-handle {
17public:
18 using value_type = see below; // not present for map containers
19 using key_type = see below; // not present for set containers
20 using mapped_type = see below; // not present for set containers
21 using allocator_type = see below;
22
23private:
24 using container_node_type = unspecified; // exposition only
25 using ator_traits = allocator_traits<allocator_type>; // exposition only
26
27 typename ator_traits::template
28 rebind_traits<container_node_type>::pointer ptr_; // exposition only
29 optional<allocator_type> alloc_; // exposition only
30
31public:
32 // [container.node.cons], constructors, copy, and assignment
33 constexpr node-handle() noexcept : ptr_(), alloc_() {}
34 constexpr node-handle(node-handle&&) noexcept; // constexpr since C++26
35 constexpr node-handle& operator=(node-handle&&); // constexpr since C++26
36
37 // [container.node.dtor], destructor
38 constexpr ~node-handle(); // constexpr since C++26
39
40 // [container.node.observers], observers
41 value_type& value() const; // not present for map containers
42 key_type& key() const; // not present for set containers
43 constexpr mapped_type& mapped() const; // not present for set containers, constexpr since C++26
44
45 constexpr allocator_type get_allocator() const; // constexpr since C++26
46 constexpr explicit operator bool() const noexcept; // constexpr since C++26
47 [[nodiscard]] constexpr bool empty() const noexcept; // nodiscard since C++20, constexpr since C++26
48
49 // [container.node.modifiers], modifiers
50 constexpr void swap(node-handle&)
51 noexcept(ator_traits::propagate_on_container_swap::value ||
52 ator_traits::is_always_equal::value); // constexpr since C++26
53
54 constexpr friend void swap(node-handle& x, node-handle& y) noexcept(noexcept(x.swap(y))) {
55 x.swap(y);
56 } // constexpr since C++26
57};
58
59*/
60
61#include <__assert>
62#include <__config>
63#include <__memory/allocator_traits.h>
64#include <__memory/pointer_traits.h>
65#include <__optional/comparison.h>
66#include <__optional/nullopt_t.h>
67#include <__optional/optional.h>
68#include <__type_traits/is_specialization.h>
69#include <__type_traits/remove_const.h>
70#include <__utility/exchange.h>
71#include <__utility/move.h>
72
73#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
74# pragma GCC system_header
75#endif
76
77_LIBCPP_PUSH_MACROS
78#include <__undef_macros>
79
80#if _LIBCPP_STD_VER >= 17
81
82_LIBCPP_BEGIN_NAMESPACE_STD
83
84// Specialized in __tree & __hash_table for their _NodeType.
85template <class _NodeType, class _Alloc>
86struct __generic_container_node_destructor;
87
88template <class _NodeType, class _Alloc, template <class, class> class _MapOrSetSpecifics>
89class __basic_node_handle
90 : public _MapOrSetSpecifics< _NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>> {
91 template <class _Tp, class _Compare, class _Allocator>
92 friend class __tree;
93 template <class _Tp, class _Hash, class _Equal, class _Allocator>
94 friend class __hash_table;
95 friend struct _MapOrSetSpecifics< _NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>;
96
97 typedef allocator_traits<_Alloc> __alloc_traits;
98 typedef __rebind_pointer_t<typename __alloc_traits::void_pointer, _NodeType> __node_pointer_type;
99
100public:
101 typedef _Alloc allocator_type;
102
103private:
104 __node_pointer_type __ptr_ = nullptr;
105 optional<allocator_type> __alloc_;
106
107 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __release_ptr() {
108 __ptr_ = nullptr;
109 __alloc_ = std::nullopt;
110 }
111
112 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __destroy_node_pointer() {
113 if (__ptr_ != nullptr) {
114 typedef typename __allocator_traits_rebind< allocator_type, _NodeType>::type __node_alloc_type;
115 __node_alloc_type __alloc(*__alloc_);
116 __generic_container_node_destructor<_NodeType, __node_alloc_type>(__alloc, true)(__ptr_);
117 __ptr_ = nullptr;
118 }
119 }
120
121 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
122 __basic_node_handle(__node_pointer_type __ptr, allocator_type const& __alloc)
123 : __ptr_(__ptr), __alloc_(__alloc) {}
124
125public:
126 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __basic_node_handle() = default;
127
128 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __basic_node_handle(__basic_node_handle&& __other) noexcept
129 : __ptr_(std::exchange(__other.__ptr_, nullptr)), __alloc_(std::exchange(__other.__alloc_, std::nullopt)) {}
130
131 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __basic_node_handle& operator=(__basic_node_handle&& __other) {
132 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
133 __alloc_ == std::nullopt || __alloc_traits::propagate_on_container_move_assignment::value ||
134 __alloc_ == __other.__alloc_,
135 "node_type with incompatible allocator passed to "
136 "node_type::operator=(node_type&&)");
137
138 __destroy_node_pointer();
139 __ptr_ = std::exchange(__other.__ptr_, nullptr);
140
141 if (__alloc_traits::propagate_on_container_move_assignment::value || __alloc_ == std::nullopt)
142 __alloc_ = std::move(__other.__alloc_);
143
144 __other.__alloc_ = std::nullopt;
145
146 return *this;
147 }
148
149 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 allocator_type get_allocator() const { return *__alloc_; }
150
151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit operator bool() const { return __ptr_ != nullptr; }
152
153 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const { return __ptr_ == nullptr; }
154
155 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(__basic_node_handle& __other) noexcept(
156 __alloc_traits::propagate_on_container_swap::value || __alloc_traits::is_always_equal::value) {
157 using std::swap;
158 swap(__ptr_, __other.__ptr_);
159 if (__alloc_traits::propagate_on_container_swap::value || __alloc_ == std::nullopt ||
160 __other.__alloc_ == std::nullopt)
161 swap(__alloc_, __other.__alloc_);
162 }
163
164 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend void
165 swap(__basic_node_handle& __a, __basic_node_handle& __b) noexcept(noexcept(__a.swap(other&: __b))) {
166 __a.swap(other&: __b);
167 }
168
169 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 ~__basic_node_handle() { __destroy_node_pointer(); }
170};
171
172template <class _NodeType, class _Derived>
173struct __set_node_handle_specifics {
174 typedef typename _NodeType::__node_value_type value_type;
175
176 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_type& value() const {
177 return static_cast<_Derived const*>(this)->__ptr_->__get_value();
178 }
179};
180
181template <class _NodeType, class _Derived>
182struct __map_node_handle_specifics {
183 using key_type = __remove_const_t<typename _NodeType::__node_value_type::first_type>;
184 using mapped_type = typename _NodeType::__node_value_type::second_type;
185
186 // This method is not constexpr as per the standard.
187 _LIBCPP_HIDE_FROM_ABI key_type& key() const {
188 return const_cast<key_type&>(static_cast<_Derived const*>(this)->__ptr_->__get_value().first);
189 }
190
191 _LIBCPP_HIDE_FROM_ABI mapped_type& mapped() const {
192 return static_cast<_Derived const*>(this)->__ptr_->__get_value().second;
193 }
194};
195
196template <class _NodeType, class _Alloc>
197using __set_node_handle _LIBCPP_NODEBUG = __basic_node_handle< _NodeType, _Alloc, __set_node_handle_specifics>;
198
199template <class _NodeType, class _Alloc>
200using __map_node_handle _LIBCPP_NODEBUG = __basic_node_handle< _NodeType, _Alloc, __map_node_handle_specifics>;
201
202template <class _Iterator, class _NodeType>
203struct __insert_return_type {
204 _Iterator position;
205 bool inserted;
206 _NodeType node;
207};
208
209_LIBCPP_END_NAMESPACE_STD
210
211#endif // _LIBCPP_STD_VER >= 17
212
213_LIBCPP_POP_MACROS
214
215#endif // _LIBCPP___NODE_HANDLE
216