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