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