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___DEBUG
11#define _LIBCPP___DEBUG
12
13#include <__assert>
14#include <__config>
15#include <type_traits>
16
17#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
18#  pragma GCC system_header
19#endif
20
21// Catch invalid uses of the legacy _LIBCPP_DEBUG toggle.
22#if defined(_LIBCPP_DEBUG) && _LIBCPP_DEBUG != 0 && !defined(_LIBCPP_ENABLE_DEBUG_MODE)
23#   error "Enabling the debug mode now requires having configured the library with support for the debug mode"
24#endif
25
26#if defined(_LIBCPP_ENABLE_DEBUG_MODE) && !defined(_LIBCPP_CXX03_LANG) && !defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
27# define _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
28#endif
29
30// TODO: Define this as a function instead
31#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
32# if defined(_LIBCPP_CXX03_LANG)
33#   error Support for unspecified stability is only for C++11 and higher
34# endif
35# define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last)                                                         \
36    do {                                                                                                        \
37      if (!__builtin_is_constant_evaluated())                                                                   \
38        std::shuffle(__first, __last, __libcpp_debug_randomizer());                                             \
39    } while (false)
40#else
41# define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last)                                                         \
42    do {                                                                                                        \
43    } while (false)
44#endif
45
46#ifdef _LIBCPP_ENABLE_DEBUG_MODE
47#   define _LIBCPP_DEBUG_ASSERT(x, m) _LIBCPP_ASSERT(::std::__libcpp_is_constant_evaluated() || (x), m)
48#else
49#   define _LIBCPP_DEBUG_ASSERT(x, m) ((void)0)
50#endif
51
52#if defined(_LIBCPP_ENABLE_DEBUG_MODE) || defined(_LIBCPP_BUILDING_LIBRARY)
53
54#include <cstddef>
55#include <cstdio>
56#include <cstdlib>
57
58_LIBCPP_BEGIN_NAMESPACE_STD
59
60struct _LIBCPP_TYPE_VIS __c_node;
61
62struct _LIBCPP_TYPE_VIS __i_node
63{
64    void* __i_;
65    __i_node* __next_;
66    __c_node* __c_;
67
68    __i_node(const __i_node&) = delete;
69    __i_node& operator=(const __i_node&) = delete;
70
71    _LIBCPP_INLINE_VISIBILITY
72    __i_node(void* __i, __i_node* __next, __c_node* __c)
73        : __i_(__i), __next_(__next), __c_(__c) {}
74    ~__i_node();
75};
76
77struct _LIBCPP_TYPE_VIS __c_node
78{
79    void* __c_;
80    __c_node* __next_;
81    __i_node** beg_;
82    __i_node** end_;
83    __i_node** cap_;
84
85    __c_node(const __c_node&) = delete;
86    __c_node& operator=(const __c_node&) = delete;
87
88    _LIBCPP_INLINE_VISIBILITY
89    explicit __c_node(void* __c, __c_node* __next)
90        : __c_(__c), __next_(__next), beg_(nullptr), end_(nullptr), cap_(nullptr) {}
91    virtual ~__c_node();
92
93    virtual bool __dereferenceable(const void*) const = 0;
94    virtual bool __decrementable(const void*) const = 0;
95    virtual bool __addable(const void*, ptrdiff_t) const = 0;
96    virtual bool __subscriptable(const void*, ptrdiff_t) const = 0;
97
98    void __add(__i_node* __i);
99    _LIBCPP_HIDDEN void __remove(__i_node* __i);
100};
101
102template <class _Cont>
103struct _C_node
104    : public __c_node
105{
106    explicit _C_node(void* __c, __c_node* __n)
107        : __c_node(__c, __n) {}
108
109    virtual bool __dereferenceable(const void*) const;
110    virtual bool __decrementable(const void*) const;
111    virtual bool __addable(const void*, ptrdiff_t) const;
112    virtual bool __subscriptable(const void*, ptrdiff_t) const;
113};
114
115template <class _Cont>
116inline bool
117_C_node<_Cont>::__dereferenceable(const void* __i) const
118{
119    typedef typename _Cont::const_iterator iterator;
120    const iterator* __j = static_cast<const iterator*>(__i);
121    _Cont* _Cp = static_cast<_Cont*>(__c_);
122    return _Cp->__dereferenceable(__j);
123}
124
125template <class _Cont>
126inline bool
127_C_node<_Cont>::__decrementable(const void* __i) const
128{
129    typedef typename _Cont::const_iterator iterator;
130    const iterator* __j = static_cast<const iterator*>(__i);
131    _Cont* _Cp = static_cast<_Cont*>(__c_);
132    return _Cp->__decrementable(__j);
133}
134
135template <class _Cont>
136inline bool
137_C_node<_Cont>::__addable(const void* __i, ptrdiff_t __n) const
138{
139    typedef typename _Cont::const_iterator iterator;
140    const iterator* __j = static_cast<const iterator*>(__i);
141    _Cont* _Cp = static_cast<_Cont*>(__c_);
142    return _Cp->__addable(__j, __n);
143}
144
145template <class _Cont>
146inline bool
147_C_node<_Cont>::__subscriptable(const void* __i, ptrdiff_t __n) const
148{
149    typedef typename _Cont::const_iterator iterator;
150    const iterator* __j = static_cast<const iterator*>(__i);
151    _Cont* _Cp = static_cast<_Cont*>(__c_);
152    return _Cp->__subscriptable(__j, __n);
153}
154
155class _LIBCPP_TYPE_VIS __libcpp_db
156{
157    __c_node** __cbeg_;
158    __c_node** __cend_;
159    size_t   __csz_;
160    __i_node** __ibeg_;
161    __i_node** __iend_;
162    size_t   __isz_;
163
164    explicit __libcpp_db();
165public:
166    __libcpp_db(const __libcpp_db&) = delete;
167    __libcpp_db& operator=(const __libcpp_db&) = delete;
168
169    ~__libcpp_db();
170
171    class __db_c_iterator;
172    class __db_c_const_iterator;
173    class __db_i_iterator;
174    class __db_i_const_iterator;
175
176    __db_c_const_iterator __c_end() const;
177    __db_i_const_iterator __i_end() const;
178
179    typedef __c_node*(_InsertConstruct)(void*, void*, __c_node*);
180
181    template <class _Cont>
182    _LIBCPP_INLINE_VISIBILITY static __c_node* __create_C_node(void *__mem, void *__c, __c_node *__next) {
183        return ::new (__mem) _C_node<_Cont>(__c, __next);
184    }
185
186    template <class _Cont>
187    _LIBCPP_INLINE_VISIBILITY
188    void __insert_c(_Cont* __c)
189    {
190        __insert_c(static_cast<void*>(__c), &__create_C_node<_Cont>);
191    }
192
193    void __insert_i(void* __i);
194    void __insert_c(void* __c, _InsertConstruct* __fn);
195    void __erase_c(void* __c);
196
197    void __insert_ic(void* __i, const void* __c);
198    void __iterator_copy(void* __i, const void* __i0);
199    void __erase_i(void* __i);
200
201    void* __find_c_from_i(void* __i) const;
202    void __invalidate_all(void* __c);
203    __c_node* __find_c_and_lock(void* __c) const;
204    __c_node* __find_c(void* __c) const;
205    void unlock() const;
206
207    void swap(void* __c1, void* __c2);
208
209
210    bool __dereferenceable(const void* __i) const;
211    bool __decrementable(const void* __i) const;
212    bool __addable(const void* __i, ptrdiff_t __n) const;
213    bool __subscriptable(const void* __i, ptrdiff_t __n) const;
214    bool __less_than_comparable(const void* __i, const void* __j) const;
215private:
216    _LIBCPP_HIDDEN
217    __i_node* __insert_iterator(void* __i);
218    _LIBCPP_HIDDEN
219    __i_node* __find_iterator(const void* __i) const;
220
221    friend _LIBCPP_FUNC_VIS __libcpp_db* __get_db();
222};
223
224_LIBCPP_FUNC_VIS __libcpp_db* __get_db();
225_LIBCPP_FUNC_VIS const __libcpp_db* __get_const_db();
226
227_LIBCPP_END_NAMESPACE_STD
228
229#endif // defined(_LIBCPP_ENABLE_DEBUG_MODE) || defined(_LIBCPP_BUILDING_LIBRARY)
230
231_LIBCPP_BEGIN_NAMESPACE_STD
232
233template <class _Tp>
234_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_insert_c(_Tp* __c) {
235#ifdef _LIBCPP_ENABLE_DEBUG_MODE
236    if (!__libcpp_is_constant_evaluated())
237        __get_db()->__insert_c(__c);
238#else
239    (void)(__c);
240#endif
241}
242
243template <class _Tp>
244_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_insert_i(_Tp* __i) {
245#ifdef _LIBCPP_ENABLE_DEBUG_MODE
246    if (!__libcpp_is_constant_evaluated())
247        __get_db()->__insert_i(__i);
248#else
249    (void)(__i);
250#endif
251}
252
253template <class _Tp>
254_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_erase_c(_Tp* __c) {
255#ifdef _LIBCPP_ENABLE_DEBUG_MODE
256    if (!__libcpp_is_constant_evaluated())
257        __get_db()->__erase_c(__c);
258#else
259    (void)(__c);
260#endif
261}
262
263template <class _Tp>
264_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_swap(_Tp* __lhs, _Tp* __rhs) {
265#ifdef _LIBCPP_ENABLE_DEBUG_MODE
266    if (!__libcpp_is_constant_evaluated())
267        __get_db()->swap(__lhs, __rhs);
268#else
269    (void)(__lhs);
270    (void)(__rhs);
271#endif
272}
273
274template <class _Tp>
275_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_invalidate_all(_Tp* __c) {
276#ifdef _LIBCPP_ENABLE_DEBUG_MODE
277    if (!__libcpp_is_constant_evaluated())
278        __get_db()->__invalidate_all(__c);
279#else
280    (void)(__c);
281#endif
282}
283
284_LIBCPP_END_NAMESPACE_STD
285
286#endif // _LIBCPP___DEBUG
287