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