Revert "[libc] Use best-fit binary trie to make malloc logarithmic" (#117065)
[llvm-project.git] / libcxx / include / new
blob49e500809e158fe54f348e4bfe515d869af53ce7
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 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP_NEW
11 #define _LIBCPP_NEW
14     new synopsis
16 namespace std
19 class bad_alloc
20     : public exception
22 public:
23     bad_alloc() noexcept;
24     bad_alloc(const bad_alloc&) noexcept;
25     bad_alloc& operator=(const bad_alloc&) noexcept;
26     virtual const char* what() const noexcept;
29 class bad_array_new_length : public bad_alloc // C++14
31 public:
32     bad_array_new_length() noexcept;
35 enum class align_val_t : size_t {}; // C++17
37 struct destroying_delete_t { // C++20
38   explicit destroying_delete_t() = default;
40 inline constexpr destroying_delete_t destroying_delete{}; // C++20
42 struct nothrow_t { explicit nothrow_t() = default; };
43 extern const nothrow_t nothrow;
44 typedef void (*new_handler)();
45 new_handler set_new_handler(new_handler new_p) noexcept;
46 new_handler get_new_handler() noexcept;
48 // 21.6.4, pointer optimization barrier
49 template <class T> [[nodiscard]] constexpr T* launder(T* p) noexcept;   // C++17, nodiscard since C++20
50 }  // std
52 void* operator new(std::size_t size);                                   // replaceable, nodiscard in C++20
53 void* operator new(std::size_t size, std::align_val_t alignment);       // replaceable, C++17, nodiscard in C++20
54 void* operator new(std::size_t size, const std::nothrow_t&) noexcept;   // replaceable, nodiscard in C++20
55 void* operator new(std::size_t size, std::align_val_t alignment,
56                    const std::nothrow_t&) noexcept;                     // replaceable, C++17, nodiscard in C++20
57 void  operator delete(void* ptr) noexcept;                              // replaceable
58 void  operator delete(void* ptr, std::size_t size) noexcept;            // replaceable, C++14
59 void  operator delete(void* ptr, std::align_val_t alignment) noexcept;  // replaceable, C++17
60 void  operator delete(void* ptr, std::size_t size,
61                       std::align_val_t alignment) noexcept;             // replaceable, C++17
62 void  operator delete(void* ptr, const std::nothrow_t&) noexcept;       // replaceable
63 void  operator delete(void* ptr, std:align_val_t alignment,
64                       const std::nothrow_t&) noexcept;                  // replaceable, C++17
66 void* operator new[](std::size_t size);                                 // replaceable, nodiscard in C++20
67 void* operator new[](std::size_t size,
68                      std::align_val_t alignment) noexcept;              // replaceable, C++17, nodiscard in C++20
69 void* operator new[](std::size_t size, const std::nothrow_t&) noexcept; // replaceable, nodiscard in C++20
70 void* operator new[](std::size_t size, std::align_val_t alignment,
71                      const std::nothrow_t&) noexcept;                   // replaceable, C++17, nodiscard in C++20
72 void  operator delete[](void* ptr) noexcept;                            // replaceable
73 void  operator delete[](void* ptr, std::size_t size) noexcept;          // replaceable, C++14
74 void  operator delete[](void* ptr,
75                         std::align_val_t alignment) noexcept;           // replaceable, C++17
76 void  operator delete[](void* ptr, std::size_t size,
77                         std::align_val_t alignment) noexcept;           // replaceable, C++17
78 void  operator delete[](void* ptr, const std::nothrow_t&) noexcept;     // replaceable
79 void  operator delete[](void* ptr, std::align_val_t alignment,
80                         const std::nothrow_t&) noexcept;                // replaceable, C++17
82 void* operator new  (std::size_t size, void* ptr) noexcept;             // nodiscard in C++20, constexpr since C++26
83 void* operator new[](std::size_t size, void* ptr) noexcept;             // nodiscard in C++20, constexpr since C++26
84 void  operator delete  (void* ptr, void*) noexcept;
85 void  operator delete[](void* ptr, void*) noexcept;
89 #include <__config>
90 #include <__cstddef/max_align_t.h>
91 #include <__cstddef/size_t.h>
92 #include <__exception/exception.h>
93 #include <__type_traits/is_function.h>
94 #include <__type_traits/is_void.h>
95 #include <__verbose_abort>
96 #include <version>
98 #if defined(_LIBCPP_ABI_VCRUNTIME)
99 #  include <new.h>
100 #endif
102 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
103 #  pragma GCC system_header
104 #endif
106 #if defined(__cpp_sized_deallocation) && __cpp_sized_deallocation >= 201309L
107 #  define _LIBCPP_HAS_LANGUAGE_SIZED_DEALLOCATION 1
108 #else
109 #  define _LIBCPP_HAS_LANGUAGE_SIZED_DEALLOCATION 0
110 #endif
112 #if _LIBCPP_STD_VER >= 14 || _LIBCPP_HAS_LANGUAGE_SIZED_DEALLOCATION
113 #  define _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION 1
114 #else
115 #  define _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION 0
116 #endif
118 #if _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION && _LIBCPP_HAS_LANGUAGE_SIZED_DEALLOCATION
119 #  define _LIBCPP_HAS_SIZED_DEALLOCATION 1
120 #else
121 #  define _LIBCPP_HAS_SIZED_DEALLOCATION 0
122 #endif
124 namespace std // purposefully not using versioning namespace
127 #if !defined(_LIBCPP_ABI_VCRUNTIME)
128 struct _LIBCPP_EXPORTED_FROM_ABI nothrow_t {
129   explicit nothrow_t() = default;
131 extern _LIBCPP_EXPORTED_FROM_ABI const nothrow_t nothrow;
133 class _LIBCPP_EXPORTED_FROM_ABI bad_alloc : public exception {
134 public:
135   bad_alloc() _NOEXCEPT;
136   _LIBCPP_HIDE_FROM_ABI bad_alloc(const bad_alloc&) _NOEXCEPT            = default;
137   _LIBCPP_HIDE_FROM_ABI bad_alloc& operator=(const bad_alloc&) _NOEXCEPT = default;
138   ~bad_alloc() _NOEXCEPT override;
139   const char* what() const _NOEXCEPT override;
142 class _LIBCPP_EXPORTED_FROM_ABI bad_array_new_length : public bad_alloc {
143 public:
144   bad_array_new_length() _NOEXCEPT;
145   _LIBCPP_HIDE_FROM_ABI bad_array_new_length(const bad_array_new_length&) _NOEXCEPT            = default;
146   _LIBCPP_HIDE_FROM_ABI bad_array_new_length& operator=(const bad_array_new_length&) _NOEXCEPT = default;
147   ~bad_array_new_length() _NOEXCEPT override;
148   const char* what() const _NOEXCEPT override;
151 typedef void (*new_handler)();
152 _LIBCPP_EXPORTED_FROM_ABI new_handler set_new_handler(new_handler) _NOEXCEPT;
153 _LIBCPP_EXPORTED_FROM_ABI new_handler get_new_handler() _NOEXCEPT;
155 #elif defined(_HAS_EXCEPTIONS) && _HAS_EXCEPTIONS == 0 // !_LIBCPP_ABI_VCRUNTIME
157 // When _HAS_EXCEPTIONS == 0, these complete definitions are needed,
158 // since they would normally be provided in vcruntime_exception.h
159 class bad_alloc : public exception {
160 public:
161   bad_alloc() noexcept : exception("bad allocation") {}
163 private:
164   friend class bad_array_new_length;
166   bad_alloc(char const* const __message) noexcept : exception(__message) {}
169 class bad_array_new_length : public bad_alloc {
170 public:
171   bad_array_new_length() noexcept : bad_alloc("bad array new length") {}
173 #endif // defined(_LIBCPP_ABI_VCRUNTIME) && defined(_HAS_EXCEPTIONS) && _HAS_EXCEPTIONS == 0
175 [[__noreturn__]] _LIBCPP_EXPORTED_FROM_ABI void __throw_bad_alloc(); // not in C++ spec
177 [[__noreturn__]] inline _LIBCPP_HIDE_FROM_ABI void __throw_bad_array_new_length() {
178 #if _LIBCPP_HAS_EXCEPTIONS
179   throw bad_array_new_length();
180 #else
181   _LIBCPP_VERBOSE_ABORT("bad_array_new_length was thrown in -fno-exceptions mode");
182 #endif
185 #if _LIBCPP_HAS_LIBRARY_ALIGNED_ALLOCATION && !defined(_LIBCPP_ABI_VCRUNTIME)
186 #  ifndef _LIBCPP_CXX03_LANG
187 enum class align_val_t : size_t {};
188 #  else
189 enum align_val_t { __zero = 0, __max = (size_t)-1 };
190 #  endif
191 #endif
193 #if _LIBCPP_STD_VER >= 20
194 // Enable the declaration even if the compiler doesn't support the language
195 // feature.
196 struct destroying_delete_t {
197   explicit destroying_delete_t() = default;
199 inline constexpr destroying_delete_t destroying_delete{};
200 #endif // _LIBCPP_STD_VER >= 20
202 } // namespace std
204 #if defined(_LIBCPP_CXX03_LANG)
205 #  define _THROW_BAD_ALLOC throw(std::bad_alloc)
206 #else
207 #  define _THROW_BAD_ALLOC
208 #endif
210 #if !defined(_LIBCPP_ABI_VCRUNTIME)
212 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void* operator new(std::size_t __sz) _THROW_BAD_ALLOC;
213 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void* operator new(std::size_t __sz, const std::nothrow_t&) _NOEXCEPT
214     _LIBCPP_NOALIAS;
215 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete(void* __p) _NOEXCEPT;
216 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete(void* __p, const std::nothrow_t&) _NOEXCEPT;
217 #  if _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION
218 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete(void* __p, std::size_t __sz) _NOEXCEPT;
219 #  endif
221 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void* operator new[](std::size_t __sz) _THROW_BAD_ALLOC;
222 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void* operator new[](std::size_t __sz, const std::nothrow_t&) _NOEXCEPT
223     _LIBCPP_NOALIAS;
224 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete[](void* __p) _NOEXCEPT;
225 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete[](void* __p, const std::nothrow_t&) _NOEXCEPT;
226 #  if _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION
227 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete[](void* __p, std::size_t __sz) _NOEXCEPT;
228 #  endif
230 #  if _LIBCPP_HAS_LIBRARY_ALIGNED_ALLOCATION
231 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void* operator new(std::size_t __sz, std::align_val_t) _THROW_BAD_ALLOC;
232 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void*
233 operator new(std::size_t __sz, std::align_val_t, const std::nothrow_t&) _NOEXCEPT _LIBCPP_NOALIAS;
234 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete(void* __p, std::align_val_t) _NOEXCEPT;
235 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete(void* __p, std::align_val_t, const std::nothrow_t&) _NOEXCEPT;
236 #    if _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION
237 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete(void* __p, std::size_t __sz, std::align_val_t) _NOEXCEPT;
238 #    endif
240 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void*
241 operator new[](std::size_t __sz, std::align_val_t) _THROW_BAD_ALLOC;
242 [[__nodiscard__]] _LIBCPP_OVERRIDABLE_FUNC_VIS void*
243 operator new[](std::size_t __sz, std::align_val_t, const std::nothrow_t&) _NOEXCEPT _LIBCPP_NOALIAS;
244 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete[](void* __p, std::align_val_t) _NOEXCEPT;
245 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete[](void* __p, std::align_val_t, const std::nothrow_t&) _NOEXCEPT;
246 #    if _LIBCPP_HAS_LIBRARY_SIZED_DEALLOCATION
247 _LIBCPP_OVERRIDABLE_FUNC_VIS void operator delete[](void* __p, std::size_t __sz, std::align_val_t) _NOEXCEPT;
248 #    endif
249 #  endif
251 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void*
252 operator new(std::size_t, void* __p) _NOEXCEPT {
253   return __p;
255 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void*
256 operator new[](std::size_t, void* __p) _NOEXCEPT {
257   return __p;
259 inline _LIBCPP_HIDE_FROM_ABI void operator delete(void*, void*) _NOEXCEPT {}
260 inline _LIBCPP_HIDE_FROM_ABI void operator delete[](void*, void*) _NOEXCEPT {}
262 #endif // !_LIBCPP_ABI_VCRUNTIME
264 _LIBCPP_BEGIN_NAMESPACE_STD
266 _LIBCPP_CONSTEXPR inline _LIBCPP_HIDE_FROM_ABI bool __is_overaligned_for_new(size_t __align) _NOEXCEPT {
267 #ifdef __STDCPP_DEFAULT_NEW_ALIGNMENT__
268   return __align > __STDCPP_DEFAULT_NEW_ALIGNMENT__;
269 #else
270   return __align > _LIBCPP_ALIGNOF(max_align_t);
271 #endif
274 template <class... _Args>
275 _LIBCPP_HIDE_FROM_ABI void* __libcpp_operator_new(_Args... __args) {
276 #if __has_builtin(__builtin_operator_new) && __has_builtin(__builtin_operator_delete)
277   return __builtin_operator_new(__args...);
278 #else
279   return ::operator new(__args...);
280 #endif
283 template <class... _Args>
284 _LIBCPP_HIDE_FROM_ABI void __libcpp_operator_delete(_Args... __args) _NOEXCEPT {
285 #if __has_builtin(__builtin_operator_new) && __has_builtin(__builtin_operator_delete)
286   __builtin_operator_delete(__args...);
287 #else
288   ::operator delete(__args...);
289 #endif
292 inline _LIBCPP_HIDE_FROM_ABI void* __libcpp_allocate(size_t __size, size_t __align) {
293 #if _LIBCPP_HAS_ALIGNED_ALLOCATION
294   if (__is_overaligned_for_new(__align)) {
295     const align_val_t __align_val = static_cast<align_val_t>(__align);
296     return __libcpp_operator_new(__size, __align_val);
297   }
298 #endif
300   (void)__align;
301   return __libcpp_operator_new(__size);
304 template <class... _Args>
305 _LIBCPP_HIDE_FROM_ABI void __do_deallocate_handle_size(void* __ptr, size_t __size, _Args... __args) _NOEXCEPT {
306 #if !_LIBCPP_HAS_SIZED_DEALLOCATION
307   (void)__size;
308   return std::__libcpp_operator_delete(__ptr, __args...);
309 #else
310   return std::__libcpp_operator_delete(__ptr, __size, __args...);
311 #endif
314 inline _LIBCPP_HIDE_FROM_ABI void __libcpp_deallocate(void* __ptr, size_t __size, size_t __align) _NOEXCEPT {
315 #if !_LIBCPP_HAS_ALIGNED_ALLOCATION
316   (void)__align;
317   return __do_deallocate_handle_size(__ptr, __size);
318 #else
319   if (__is_overaligned_for_new(__align)) {
320     const align_val_t __align_val = static_cast<align_val_t>(__align);
321     return __do_deallocate_handle_size(__ptr, __size, __align_val);
322   } else {
323     return __do_deallocate_handle_size(__ptr, __size);
324   }
325 #endif
328 inline _LIBCPP_HIDE_FROM_ABI void __libcpp_deallocate_unsized(void* __ptr, size_t __align) _NOEXCEPT {
329 #if !_LIBCPP_HAS_ALIGNED_ALLOCATION
330   (void)__align;
331   return __libcpp_operator_delete(__ptr);
332 #else
333   if (__is_overaligned_for_new(__align)) {
334     const align_val_t __align_val = static_cast<align_val_t>(__align);
335     return __libcpp_operator_delete(__ptr, __align_val);
336   } else {
337     return __libcpp_operator_delete(__ptr);
338   }
339 #endif
342 template <class _Tp>
343 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Tp* __launder(_Tp* __p) _NOEXCEPT {
344   static_assert(!(is_function<_Tp>::value), "can't launder functions");
345   static_assert(!is_void<_Tp>::value, "can't launder cv-void");
346   return __builtin_launder(__p);
349 #if _LIBCPP_STD_VER >= 17
350 template <class _Tp>
351 [[nodiscard]] inline _LIBCPP_HIDE_FROM_ABI constexpr _Tp* launder(_Tp* __p) noexcept {
352   return std::__launder(__p);
354 #endif
356 #if _LIBCPP_STD_VER >= 17
358 #  if defined(__GCC_DESTRUCTIVE_SIZE) && defined(__GCC_CONSTRUCTIVE_SIZE)
360 inline constexpr size_t hardware_destructive_interference_size  = __GCC_DESTRUCTIVE_SIZE;
361 inline constexpr size_t hardware_constructive_interference_size = __GCC_CONSTRUCTIVE_SIZE;
363 #  endif // defined(__GCC_DESTRUCTIVE_SIZE) && defined(__GCC_CONSTRUCTIVE_SIZE)
365 #endif // _LIBCPP_STD_VER >= 17
367 _LIBCPP_END_NAMESPACE_STD
369 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
370 #  include <cstddef>
371 #  include <cstdlib>
372 #  include <type_traits>
373 #endif
375 #endif // _LIBCPP_NEW