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#if _LIBCPP_DEBUG_LEVEL >= 1 || defined(_LIBCPP_BUILDING_LIBRARY)
22#   include <cstddef>
23#   include <cstdio>
24#   include <cstdlib>
25#endif
26
27#if _LIBCPP_DEBUG_LEVEL == 0 || _LIBCPP_DEBUG_LEVEL == 1
28#   define _LIBCPP_DEBUG_ASSERT(x, m) ((void)0)
29#elif _LIBCPP_DEBUG_LEVEL == 2
30#   define _LIBCPP_DEBUG_ASSERT(x, m) _LIBCPP_ASSERT(::std::__libcpp_is_constant_evaluated() || (x), m)
31#else
32#   error _LIBCPP_DEBUG_LEVEL must be one of 0, 1, 2
33#endif
34
35_LIBCPP_BEGIN_NAMESPACE_STD
36
37#if _LIBCPP_DEBUG_LEVEL == 2 || defined(_LIBCPP_BUILDING_LIBRARY)
38
39struct _LIBCPP_TYPE_VIS __c_node;
40
41struct _LIBCPP_TYPE_VIS __i_node
42{
43    void* __i_;
44    __i_node* __next_;
45    __c_node* __c_;
46
47    __i_node(const __i_node&) = delete;
48    __i_node& operator=(const __i_node&) = delete;
49
50    _LIBCPP_INLINE_VISIBILITY
51    __i_node(void* __i, __i_node* __next, __c_node* __c)
52        : __i_(__i), __next_(__next), __c_(__c) {}
53    ~__i_node();
54};
55
56struct _LIBCPP_TYPE_VIS __c_node
57{
58    void* __c_;
59    __c_node* __next_;
60    __i_node** beg_;
61    __i_node** end_;
62    __i_node** cap_;
63
64    __c_node(const __c_node&) = delete;
65    __c_node& operator=(const __c_node&) = delete;
66
67    _LIBCPP_INLINE_VISIBILITY
68    explicit __c_node(void* __c, __c_node* __next)
69        : __c_(__c), __next_(__next), beg_(nullptr), end_(nullptr), cap_(nullptr) {}
70    virtual ~__c_node();
71
72    virtual bool __dereferenceable(const void*) const = 0;
73    virtual bool __decrementable(const void*) const = 0;
74    virtual bool __addable(const void*, ptrdiff_t) const = 0;
75    virtual bool __subscriptable(const void*, ptrdiff_t) const = 0;
76
77    void __add(__i_node* __i);
78    _LIBCPP_HIDDEN void __remove(__i_node* __i);
79};
80
81template <class _Cont>
82struct _C_node
83    : public __c_node
84{
85    explicit _C_node(void* __c, __c_node* __n)
86        : __c_node(__c, __n) {}
87
88    virtual bool __dereferenceable(const void*) const;
89    virtual bool __decrementable(const void*) const;
90    virtual bool __addable(const void*, ptrdiff_t) const;
91    virtual bool __subscriptable(const void*, ptrdiff_t) const;
92};
93
94template <class _Cont>
95inline bool
96_C_node<_Cont>::__dereferenceable(const void* __i) const
97{
98    typedef typename _Cont::const_iterator iterator;
99    const iterator* __j = static_cast<const iterator*>(__i);
100    _Cont* _Cp = static_cast<_Cont*>(__c_);
101    return _Cp->__dereferenceable(__j);
102}
103
104template <class _Cont>
105inline bool
106_C_node<_Cont>::__decrementable(const void* __i) const
107{
108    typedef typename _Cont::const_iterator iterator;
109    const iterator* __j = static_cast<const iterator*>(__i);
110    _Cont* _Cp = static_cast<_Cont*>(__c_);
111    return _Cp->__decrementable(__j);
112}
113
114template <class _Cont>
115inline bool
116_C_node<_Cont>::__addable(const void* __i, ptrdiff_t __n) const
117{
118    typedef typename _Cont::const_iterator iterator;
119    const iterator* __j = static_cast<const iterator*>(__i);
120    _Cont* _Cp = static_cast<_Cont*>(__c_);
121    return _Cp->__addable(__j, __n);
122}
123
124template <class _Cont>
125inline bool
126_C_node<_Cont>::__subscriptable(const void* __i, ptrdiff_t __n) const
127{
128    typedef typename _Cont::const_iterator iterator;
129    const iterator* __j = static_cast<const iterator*>(__i);
130    _Cont* _Cp = static_cast<_Cont*>(__c_);
131    return _Cp->__subscriptable(__j, __n);
132}
133
134class _LIBCPP_TYPE_VIS __libcpp_db
135{
136    __c_node** __cbeg_;
137    __c_node** __cend_;
138    size_t   __csz_;
139    __i_node** __ibeg_;
140    __i_node** __iend_;
141    size_t   __isz_;
142
143    explicit __libcpp_db();
144public:
145    __libcpp_db(const __libcpp_db&) = delete;
146    __libcpp_db& operator=(const __libcpp_db&) = delete;
147
148    ~__libcpp_db();
149
150    class __db_c_iterator;
151    class __db_c_const_iterator;
152    class __db_i_iterator;
153    class __db_i_const_iterator;
154
155    __db_c_const_iterator __c_end() const;
156    __db_i_const_iterator __i_end() const;
157
158    typedef __c_node*(_InsertConstruct)(void*, void*, __c_node*);
159
160    template <class _Cont>
161    _LIBCPP_INLINE_VISIBILITY static __c_node* __create_C_node(void *__mem, void *__c, __c_node *__next) {
162        return ::new (__mem) _C_node<_Cont>(__c, __next);
163    }
164
165    template <class _Cont>
166    _LIBCPP_INLINE_VISIBILITY
167    void __insert_c(_Cont* __c)
168    {
169        __insert_c(static_cast<void*>(__c), &__create_C_node<_Cont>);
170    }
171
172    void __insert_i(void* __i);
173    void __insert_c(void* __c, _InsertConstruct* __fn);
174    void __erase_c(void* __c);
175
176    void __insert_ic(void* __i, const void* __c);
177    void __iterator_copy(void* __i, const void* __i0);
178    void __erase_i(void* __i);
179
180    void* __find_c_from_i(void* __i) const;
181    void __invalidate_all(void* __c);
182    __c_node* __find_c_and_lock(void* __c) const;
183    __c_node* __find_c(void* __c) const;
184    void unlock() const;
185
186    void swap(void* __c1, void* __c2);
187
188
189    bool __dereferenceable(const void* __i) const;
190    bool __decrementable(const void* __i) const;
191    bool __addable(const void* __i, ptrdiff_t __n) const;
192    bool __subscriptable(const void* __i, ptrdiff_t __n) const;
193    bool __less_than_comparable(const void* __i, const void* __j) const;
194private:
195    _LIBCPP_HIDDEN
196    __i_node* __insert_iterator(void* __i);
197    _LIBCPP_HIDDEN
198    __i_node* __find_iterator(const void* __i) const;
199
200    friend _LIBCPP_FUNC_VIS __libcpp_db* __get_db();
201};
202
203_LIBCPP_FUNC_VIS __libcpp_db* __get_db();
204_LIBCPP_FUNC_VIS const __libcpp_db* __get_const_db();
205
206
207#endif // _LIBCPP_DEBUG_LEVEL == 2 || defined(_LIBCPP_BUILDING_LIBRARY)
208
209template <class _Tp>
210_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_insert_c(_Tp* __c) {
211#if _LIBCPP_DEBUG_LEVEL == 2
212    if (!__libcpp_is_constant_evaluated())
213        __get_db()->__insert_c(__c);
214#else
215    (void)(__c);
216#endif
217}
218
219template <class _Tp>
220_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 inline void __debug_db_insert_i(_Tp* __i) {
221#if _LIBCPP_DEBUG_LEVEL == 2
222    if (!__libcpp_is_constant_evaluated())
223        __get_db()->__insert_i(__i);
224#else
225    (void)(__i);
226#endif
227}
228
229_LIBCPP_END_NAMESPACE_STD
230
231#endif // _LIBCPP___DEBUG
232