1//===-------------------------- debug.cpp ---------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "__config"
10#include "__debug"
11#include "functional"
12#include "algorithm"
13#include "string"
14#include "cstdio"
15#include "__hash_table"
16#ifndef _LIBCPP_HAS_NO_THREADS
17#include "mutex"
18#if defined(__ELF__) && defined(_LIBCPP_LINK_PTHREAD_LIB)
19#pragma comment(lib, "pthread")
20#endif
21#endif
22
23_LIBCPP_BEGIN_NAMESPACE_STD
24
25std::string __libcpp_debug_info::what() const {
26  string msg = __file_;
27  msg += ":" + to_string(__line_) + ": _LIBCPP_ASSERT '";
28  msg += __pred_;
29  msg += "' failed. ";
30  msg += __msg_;
31  return msg;
32}
33_LIBCPP_NORETURN void __libcpp_abort_debug_function(__libcpp_debug_info const& info) {
34    std::fprintf(stderr, "%s\n", info.what().c_str());
35    std::abort();
36}
37
38_LIBCPP_SAFE_STATIC __libcpp_debug_function_type
39    __libcpp_debug_function = __libcpp_abort_debug_function;
40
41bool __libcpp_set_debug_function(__libcpp_debug_function_type __func) {
42  __libcpp_debug_function = __func;
43  return true;
44}
45
46_LIBCPP_FUNC_VIS
47__libcpp_db*
48__get_db()
49{
50    static _LIBCPP_NO_DESTROY __libcpp_db db;
51    return &db;
52}
53
54_LIBCPP_FUNC_VIS
55const __libcpp_db*
56__get_const_db()
57{
58    return __get_db();
59}
60
61namespace
62{
63
64#ifndef _LIBCPP_HAS_NO_THREADS
65typedef mutex mutex_type;
66typedef lock_guard<mutex_type> WLock;
67typedef lock_guard<mutex_type> RLock;
68
69mutex_type&
70mut()
71{
72    static _LIBCPP_NO_DESTROY mutex_type m;
73    return m;
74}
75#endif // !_LIBCPP_HAS_NO_THREADS
76
77}  // unnamed namespace
78
79__i_node::~__i_node()
80{
81    if (__next_)
82    {
83        __next_->~__i_node();
84        free(__next_);
85    }
86}
87
88__c_node::~__c_node()
89{
90    free(beg_);
91    if (__next_)
92    {
93        __next_->~__c_node();
94        free(__next_);
95    }
96}
97
98__libcpp_db::__libcpp_db()
99    : __cbeg_(nullptr),
100      __cend_(nullptr),
101      __csz_(0),
102      __ibeg_(nullptr),
103      __iend_(nullptr),
104      __isz_(0)
105{
106}
107
108__libcpp_db::~__libcpp_db()
109{
110    if (__cbeg_)
111    {
112        for (__c_node** p = __cbeg_; p != __cend_; ++p)
113        {
114            if (*p != nullptr)
115            {
116                (*p)->~__c_node();
117                free(*p);
118            }
119        }
120        free(__cbeg_);
121    }
122    if (__ibeg_)
123    {
124        for (__i_node** p = __ibeg_; p != __iend_; ++p)
125        {
126            if (*p != nullptr)
127            {
128                (*p)->~__i_node();
129                free(*p);
130            }
131        }
132        free(__ibeg_);
133    }
134}
135
136void*
137__libcpp_db::__find_c_from_i(void* __i) const
138{
139#ifndef _LIBCPP_HAS_NO_THREADS
140    RLock _(mut());
141#endif
142    __i_node* i = __find_iterator(__i);
143    _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database.");
144    return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
145}
146
147void
148__libcpp_db::__insert_ic(void* __i, const void* __c)
149{
150#ifndef _LIBCPP_HAS_NO_THREADS
151    WLock _(mut());
152#endif
153    if (__cbeg_ == __cend_)
154        return;
155    size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
156    __c_node* c = __cbeg_[hc];
157    if (c == nullptr)
158        return;
159    while (c->__c_ != __c)
160    {
161        c = c->__next_;
162        if (c == nullptr)
163            return;
164    }
165    __i_node* i = __insert_iterator(__i);
166    c->__add(i);
167    i->__c_ = c;
168}
169
170void
171__libcpp_db::__insert_c(void* __c, __libcpp_db::_InsertConstruct *__fn)
172{
173#ifndef _LIBCPP_HAS_NO_THREADS
174    WLock _(mut());
175#endif
176    if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
177    {
178        size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
179        __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(__c_node*)));
180        if (cbeg == nullptr)
181            __throw_bad_alloc();
182
183        for (__c_node** p = __cbeg_; p != __cend_; ++p)
184        {
185            __c_node* q = *p;
186            while (q != nullptr)
187            {
188                size_t h = hash<void*>()(q->__c_) % nc;
189                __c_node* r = q->__next_;
190                q->__next_ = cbeg[h];
191                cbeg[h] = q;
192                q = r;
193            }
194        }
195        free(__cbeg_);
196        __cbeg_ = cbeg;
197        __cend_ = __cbeg_ + nc;
198    }
199    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
200    __c_node* p = __cbeg_[hc];
201    void *buf = malloc(sizeof(__c_node));
202    if (buf == nullptr)
203      __throw_bad_alloc();
204    __cbeg_[hc] = __fn(buf, __c, p);
205
206    ++__csz_;
207}
208
209void
210__libcpp_db::__erase_i(void* __i)
211{
212#ifndef _LIBCPP_HAS_NO_THREADS
213    WLock _(mut());
214#endif
215    if (__ibeg_ != __iend_)
216    {
217        size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
218        __i_node* p = __ibeg_[hi];
219        if (p != nullptr)
220        {
221            __i_node* q = nullptr;
222            while (p->__i_ != __i)
223            {
224                q = p;
225                p = p->__next_;
226                if (p == nullptr)
227                    return;
228            }
229            if (q == nullptr)
230                __ibeg_[hi] = p->__next_;
231            else
232                q->__next_ = p->__next_;
233            __c_node* c = p->__c_;
234            --__isz_;
235            if (c != nullptr)
236                c->__remove(p);
237            free(p);
238        }
239    }
240}
241
242void
243__libcpp_db::__invalidate_all(void* __c)
244{
245#ifndef _LIBCPP_HAS_NO_THREADS
246    WLock _(mut());
247#endif
248    if (__cend_ != __cbeg_)
249    {
250        size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
251        __c_node* p = __cbeg_[hc];
252        if (p == nullptr)
253            return;
254        while (p->__c_ != __c)
255        {
256            p = p->__next_;
257            if (p == nullptr)
258                return;
259        }
260        while (p->end_ != p->beg_)
261        {
262            --p->end_;
263            (*p->end_)->__c_ = nullptr;
264        }
265    }
266}
267
268__c_node*
269__libcpp_db::__find_c_and_lock(void* __c) const
270{
271#ifndef _LIBCPP_HAS_NO_THREADS
272    mut().lock();
273#endif
274    if (__cend_ == __cbeg_)
275    {
276#ifndef _LIBCPP_HAS_NO_THREADS
277        mut().unlock();
278#endif
279        return nullptr;
280    }
281    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
282    __c_node* p = __cbeg_[hc];
283    if (p == nullptr)
284    {
285#ifndef _LIBCPP_HAS_NO_THREADS
286        mut().unlock();
287#endif
288        return nullptr;
289    }
290    while (p->__c_ != __c)
291    {
292        p = p->__next_;
293        if (p == nullptr)
294        {
295#ifndef _LIBCPP_HAS_NO_THREADS
296            mut().unlock();
297#endif
298            return nullptr;
299        }
300    }
301    return p;
302}
303
304__c_node*
305__libcpp_db::__find_c(void* __c) const
306{
307    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
308    __c_node* p = __cbeg_[hc];
309    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
310    while (p->__c_ != __c)
311    {
312        p = p->__next_;
313        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
314    }
315    return p;
316}
317
318void
319__libcpp_db::unlock() const
320{
321#ifndef _LIBCPP_HAS_NO_THREADS
322    mut().unlock();
323#endif
324}
325
326void
327__libcpp_db::__erase_c(void* __c)
328{
329#ifndef _LIBCPP_HAS_NO_THREADS
330    WLock _(mut());
331#endif
332    if (__cend_ != __cbeg_)
333    {
334        size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
335        __c_node* p = __cbeg_[hc];
336        if (p == nullptr)
337            return;
338        __c_node* q = nullptr;
339        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
340        while (p->__c_ != __c)
341        {
342            q = p;
343            p = p->__next_;
344            if (p == nullptr)
345                return;
346            _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
347        }
348        if (q == nullptr)
349            __cbeg_[hc] = p->__next_;
350        else
351            q->__next_ = p->__next_;
352        while (p->end_ != p->beg_)
353        {
354            --p->end_;
355            (*p->end_)->__c_ = nullptr;
356        }
357        free(p->beg_);
358        free(p);
359        --__csz_;
360    }
361}
362
363void
364__libcpp_db::__iterator_copy(void* __i, const void* __i0)
365{
366#ifndef _LIBCPP_HAS_NO_THREADS
367    WLock _(mut());
368#endif
369    __i_node* i = __find_iterator(__i);
370    __i_node* i0 = __find_iterator(__i0);
371    __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
372    if (i == nullptr && i0 != nullptr)
373        i = __insert_iterator(__i);
374    __c_node* c = i != nullptr ? i->__c_ : nullptr;
375    if (c != c0)
376    {
377        if (c != nullptr)
378            c->__remove(i);
379        if (i != nullptr)
380        {
381            i->__c_ = nullptr;
382            if (c0 != nullptr)
383            {
384                i->__c_ = c0;
385                i->__c_->__add(i);
386            }
387        }
388    }
389}
390
391bool
392__libcpp_db::__dereferenceable(const void* __i) const
393{
394#ifndef _LIBCPP_HAS_NO_THREADS
395    RLock _(mut());
396#endif
397    __i_node* i = __find_iterator(__i);
398    return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
399}
400
401bool
402__libcpp_db::__decrementable(const void* __i) const
403{
404#ifndef _LIBCPP_HAS_NO_THREADS
405    RLock _(mut());
406#endif
407    __i_node* i = __find_iterator(__i);
408    return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
409}
410
411bool
412__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
413{
414#ifndef _LIBCPP_HAS_NO_THREADS
415    RLock _(mut());
416#endif
417    __i_node* i = __find_iterator(__i);
418    return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
419}
420
421bool
422__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
423{
424#ifndef _LIBCPP_HAS_NO_THREADS
425    RLock _(mut());
426#endif
427    __i_node* i = __find_iterator(__i);
428    return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
429}
430
431bool
432__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
433{
434#ifndef _LIBCPP_HAS_NO_THREADS
435    RLock _(mut());
436#endif
437    __i_node* i = __find_iterator(__i);
438    __i_node* j = __find_iterator(__j);
439    __c_node* ci = i != nullptr ? i->__c_ : nullptr;
440    __c_node* cj = j != nullptr ? j->__c_ : nullptr;
441    return ci != nullptr && ci == cj;
442}
443
444void
445__libcpp_db::swap(void* c1, void* c2)
446{
447#ifndef _LIBCPP_HAS_NO_THREADS
448    WLock _(mut());
449#endif
450    size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
451    __c_node* p1 = __cbeg_[hc];
452    _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
453    while (p1->__c_ != c1)
454    {
455        p1 = p1->__next_;
456        _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
457    }
458    hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
459    __c_node* p2 = __cbeg_[hc];
460    _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
461    while (p2->__c_ != c2)
462    {
463        p2 = p2->__next_;
464        _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
465    }
466    std::swap(p1->beg_, p2->beg_);
467    std::swap(p1->end_, p2->end_);
468    std::swap(p1->cap_, p2->cap_);
469    for (__i_node** p = p1->beg_; p != p1->end_; ++p)
470        (*p)->__c_ = p1;
471    for (__i_node** p = p2->beg_; p != p2->end_; ++p)
472        (*p)->__c_ = p2;
473}
474
475void
476__libcpp_db::__insert_i(void* __i)
477{
478#ifndef _LIBCPP_HAS_NO_THREADS
479    WLock _(mut());
480#endif
481    __insert_iterator(__i);
482}
483
484void
485__c_node::__add(__i_node* i)
486{
487    if (end_ == cap_)
488    {
489        size_t nc = 2*static_cast<size_t>(cap_ - beg_);
490        if (nc == 0)
491            nc = 1;
492        __i_node** beg =
493           static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
494        if (beg == nullptr)
495            __throw_bad_alloc();
496
497        if (nc > 1)
498            memcpy(beg, beg_, nc/2*sizeof(__i_node*));
499        free(beg_);
500        beg_ = beg;
501        end_ = beg_ + nc/2;
502        cap_ = beg_ + nc;
503    }
504    *end_++ = i;
505}
506
507// private api
508
509_LIBCPP_HIDDEN
510__i_node*
511__libcpp_db::__insert_iterator(void* __i)
512{
513    if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
514    {
515        size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
516        __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(__i_node*)));
517        if (ibeg == nullptr)
518            __throw_bad_alloc();
519
520        for (__i_node** p = __ibeg_; p != __iend_; ++p)
521        {
522            __i_node* q = *p;
523            while (q != nullptr)
524            {
525                size_t h = hash<void*>()(q->__i_) % nc;
526                __i_node* r = q->__next_;
527                q->__next_ = ibeg[h];
528                ibeg[h] = q;
529                q = r;
530            }
531        }
532        free(__ibeg_);
533        __ibeg_ = ibeg;
534        __iend_ = __ibeg_ + nc;
535    }
536    size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
537    __i_node* p = __ibeg_[hi];
538    __i_node* r = __ibeg_[hi] =
539      static_cast<__i_node*>(malloc(sizeof(__i_node)));
540    if (r == nullptr)
541        __throw_bad_alloc();
542
543    ::new(r) __i_node(__i, p, nullptr);
544    ++__isz_;
545    return r;
546}
547
548_LIBCPP_HIDDEN
549__i_node*
550__libcpp_db::__find_iterator(const void* __i) const
551{
552    __i_node* r = nullptr;
553    if (__ibeg_ != __iend_)
554    {
555        size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
556        for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
557        {
558            if (nd->__i_ == __i)
559            {
560                r = nd;
561                break;
562            }
563        }
564    }
565    return r;
566}
567
568_LIBCPP_HIDDEN
569void
570__c_node::__remove(__i_node* p)
571{
572    __i_node** r = find(beg_, end_, p);
573    _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
574    if (--end_ != r)
575        memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
576}
577
578_LIBCPP_END_NAMESPACE_STD
579