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#define _LIBCPP_DEBUG2 1
11#include "__config"
12#include "__debug"
13#include "functional"
14#include "algorithm"
15#include "__hash_table"
16#include "mutex"
17
18_LIBCPP_BEGIN_NAMESPACE_STD
19
20_LIBCPP_FUNC_VIS
21__libcpp_db*
22__get_db()
23{
24    static __libcpp_db db;
25    return &db;
26}
27
28_LIBCPP_FUNC_VIS
29const __libcpp_db*
30__get_const_db()
31{
32    return __get_db();
33}
34
35namespace
36{
37
38typedef mutex mutex_type;
39typedef lock_guard<mutex_type> WLock;
40typedef lock_guard<mutex_type> RLock;
41
42mutex_type&
43mut()
44{
45    static mutex_type m;
46    return m;
47}
48
49}  // unnamed namespace
50
51__i_node::~__i_node()
52{
53    if (__next_)
54    {
55        __next_->~__i_node();
56        free(__next_);
57    }
58}
59
60__c_node::~__c_node()
61{
62    free(beg_);
63    if (__next_)
64    {
65        __next_->~__c_node();
66        free(__next_);
67    }
68}
69
70__libcpp_db::__libcpp_db()
71    : __cbeg_(nullptr),
72      __cend_(nullptr),
73      __csz_(0),
74      __ibeg_(nullptr),
75      __iend_(nullptr),
76      __isz_(0)
77{
78}
79
80__libcpp_db::~__libcpp_db()
81{
82    if (__cbeg_)
83    {
84        for (__c_node** p = __cbeg_; p != __cend_; ++p)
85        {
86            if (*p != nullptr)
87            {
88                (*p)->~__c_node();
89                free(*p);
90            }
91        }
92        free(__cbeg_);
93    }
94    if (__ibeg_)
95    {
96        for (__i_node** p = __ibeg_; p != __iend_; ++p)
97        {
98            if (*p != nullptr)
99            {
100                (*p)->~__i_node();
101                free(*p);
102            }
103        }
104        free(__ibeg_);
105    }
106}
107
108void*
109__libcpp_db::__find_c_from_i(void* __i) const
110{
111    RLock _(mut());
112    __i_node* i = __find_iterator(__i);
113    _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database.");
114    return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
115}
116
117void
118__libcpp_db::__insert_ic(void* __i, const void* __c)
119{
120    WLock _(mut());
121    __i_node* i = __insert_iterator(__i);
122    const char* errmsg =
123        "Container constructed in a translation unit with debug mode disabled."
124        " But it is being used in a translation unit with debug mode enabled."
125        " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1";
126    _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg);
127    size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
128    __c_node* c = __cbeg_[hc];
129    _LIBCPP_ASSERT(c != nullptr, errmsg);
130    while (c->__c_ != __c)
131    {
132        c = c->__next_;
133        _LIBCPP_ASSERT(c != nullptr, errmsg);
134    }
135    c->__add(i);
136    i->__c_ = c;
137}
138
139__c_node*
140__libcpp_db::__insert_c(void* __c)
141{
142    WLock _(mut());
143    if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
144    {
145        size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
146        __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*)));
147        if (cbeg == nullptr)
148#ifndef _LIBCPP_NO_EXCEPTIONS
149            throw bad_alloc();
150#else
151            abort();
152#endif
153        for (__c_node** p = __cbeg_; p != __cend_; ++p)
154        {
155            __c_node* q = *p;
156            while (q != nullptr)
157            {
158                size_t h = hash<void*>()(q->__c_) % nc;
159                __c_node* r = q->__next_;
160                q->__next_ = cbeg[h];
161                cbeg[h] = q;
162                q = r;
163            }
164        }
165        free(__cbeg_);
166        __cbeg_ = cbeg;
167        __cend_ = __cbeg_ + nc;
168    }
169    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
170    __c_node* p = __cbeg_[hc];
171    __c_node* r = __cbeg_[hc] =
172      static_cast<__c_node*>(malloc(sizeof(__c_node)));
173    if (__cbeg_[hc] == nullptr)
174#ifndef _LIBCPP_NO_EXCEPTIONS
175        throw bad_alloc();
176#else
177        abort();
178#endif
179    r->__c_ = __c;
180    r->__next_ = p;
181    ++__csz_;
182    return r;
183}
184
185void
186__libcpp_db::__erase_i(void* __i)
187{
188    WLock _(mut());
189    if (__ibeg_ != __iend_)
190    {
191        size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
192        __i_node* p = __ibeg_[hi];
193        if (p != nullptr)
194        {
195            __i_node* q = nullptr;
196            while (p->__i_ != __i)
197            {
198                q = p;
199                p = p->__next_;
200                if (p == nullptr)
201                    return;
202            }
203            if (q == nullptr)
204                __ibeg_[hi] = p->__next_;
205            else
206                q->__next_ = p->__next_;
207            __c_node* c = p->__c_;
208            free(p);
209            --__isz_;
210            if (c != nullptr)
211                c->__remove(p);
212        }
213    }
214}
215
216void
217__libcpp_db::__invalidate_all(void* __c)
218{
219    WLock _(mut());
220    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
221    __c_node* p = __cbeg_[hc];
222    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A");
223    while (p->__c_ != __c)
224    {
225        p = p->__next_;
226        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B");
227    }
228    while (p->end_ != p->beg_)
229    {
230        --p->end_;
231        (*p->end_)->__c_ = nullptr;
232    }
233}
234
235__c_node*
236__libcpp_db::__find_c_and_lock(void* __c) const
237{
238    mut().lock();
239    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
240    __c_node* p = __cbeg_[hc];
241    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A");
242    while (p->__c_ != __c)
243    {
244        p = p->__next_;
245        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B");
246    }
247    return p;
248}
249
250__c_node*
251__libcpp_db::__find_c(void* __c) const
252{
253    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
254    __c_node* p = __cbeg_[hc];
255    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
256    while (p->__c_ != __c)
257    {
258        p = p->__next_;
259        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
260    }
261    return p;
262}
263
264void
265__libcpp_db::unlock() const
266{
267    mut().unlock();
268}
269
270void
271__libcpp_db::__erase_c(void* __c)
272{
273    WLock _(mut());
274    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
275    __c_node* p = __cbeg_[hc];
276    __c_node* q = nullptr;
277    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
278    while (p->__c_ != __c)
279    {
280        q = p;
281        p = p->__next_;
282        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
283    }
284    if (q == nullptr)
285        __cbeg_[hc] = p->__next_;
286    else
287        q->__next_ = p->__next_;
288    while (p->end_ != p->beg_)
289    {
290        --p->end_;
291        (*p->end_)->__c_ = nullptr;
292    }
293    free(p->beg_);
294    free(p);
295    --__csz_;
296}
297
298void
299__libcpp_db::__iterator_copy(void* __i, const void* __i0)
300{
301    WLock _(mut());
302    __i_node* i = __find_iterator(__i);
303    __i_node* i0 = __find_iterator(__i0);
304    __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
305    if (i == nullptr && i0 != nullptr)
306        i = __insert_iterator(__i);
307    __c_node* c = i != nullptr ? i->__c_ : nullptr;
308    if (c != c0)
309    {
310        if (c != nullptr)
311            c->__remove(i);
312        if (i != nullptr)
313        {
314            i->__c_ = nullptr;
315            if (c0 != nullptr)
316            {
317                i->__c_ = c0;
318                i->__c_->__add(i);
319            }
320        }
321    }
322}
323
324bool
325__libcpp_db::__dereferenceable(const void* __i) const
326{
327    RLock _(mut());
328    __i_node* i = __find_iterator(__i);
329    return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
330}
331
332bool
333__libcpp_db::__decrementable(const void* __i) const
334{
335    RLock _(mut());
336    __i_node* i = __find_iterator(__i);
337    return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
338}
339
340bool
341__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
342{
343    RLock _(mut());
344    __i_node* i = __find_iterator(__i);
345    return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
346}
347
348bool
349__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
350{
351    RLock _(mut());
352    __i_node* i = __find_iterator(__i);
353    return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
354}
355
356bool
357__libcpp_db::__comparable(const void* __i, const void* __j) const
358{
359    RLock _(mut());
360    __i_node* i = __find_iterator(__i);
361    __i_node* j = __find_iterator(__j);
362    __c_node* ci = i != nullptr ? i->__c_ : nullptr;
363    __c_node* cj = j != nullptr ? j->__c_ : nullptr;
364    return ci != nullptr && ci == cj;
365}
366
367void
368__libcpp_db::swap(void* c1, void* c2)
369{
370    WLock _(mut());
371    size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
372    __c_node* p1 = __cbeg_[hc];
373    _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
374    while (p1->__c_ != c1)
375    {
376        p1 = p1->__next_;
377        _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
378    }
379    hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
380    __c_node* p2 = __cbeg_[hc];
381    _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
382    while (p2->__c_ != c2)
383    {
384        p2 = p2->__next_;
385        _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
386    }
387    std::swap(p1->beg_, p2->beg_);
388    std::swap(p1->end_, p2->end_);
389    std::swap(p1->cap_, p2->cap_);
390    for (__i_node** p = p1->beg_; p != p1->end_; ++p)
391        (*p)->__c_ = p1;
392    for (__i_node** p = p2->beg_; p != p2->end_; ++p)
393        (*p)->__c_ = p2;
394}
395
396void
397__libcpp_db::__insert_i(void* __i)
398{
399    WLock _(mut());
400    __insert_iterator(__i);
401}
402
403void
404__c_node::__add(__i_node* i)
405{
406    if (end_ == cap_)
407    {
408        size_t nc = 2*static_cast<size_t>(cap_ - beg_);
409        if (nc == 0)
410            nc = 1;
411        __i_node** beg =
412           static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
413        if (beg == nullptr)
414#ifndef _LIBCPP_NO_EXCEPTIONS
415            throw bad_alloc();
416#else
417            abort();
418#endif
419        if (nc > 1)
420            memcpy(beg, beg_, nc/2*sizeof(__i_node*));
421        free(beg_);
422        beg_ = beg;
423        end_ = beg_ + nc/2;
424        cap_ = beg_ + nc;
425    }
426    *end_++ = i;
427}
428
429// private api
430
431_LIBCPP_HIDDEN
432__i_node*
433__libcpp_db::__insert_iterator(void* __i)
434{
435    if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
436    {
437        size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
438        __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*)));
439        if (ibeg == nullptr)
440#ifndef _LIBCPP_NO_EXCEPTIONS
441            throw bad_alloc();
442#else
443            abort();
444#endif
445        for (__i_node** p = __ibeg_; p != __iend_; ++p)
446        {
447            __i_node* q = *p;
448            while (q != nullptr)
449            {
450                size_t h = hash<void*>()(q->__i_) % nc;
451                __i_node* r = q->__next_;
452                q->__next_ = ibeg[h];
453                ibeg[h] = q;
454                q = r;
455            }
456        }
457        free(__ibeg_);
458        __ibeg_ = ibeg;
459        __iend_ = __ibeg_ + nc;
460    }
461    size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
462    __i_node* p = __ibeg_[hi];
463    __i_node* r = __ibeg_[hi] =
464      static_cast<__i_node*>(malloc(sizeof(__i_node)));
465    if (r == nullptr)
466#ifndef _LIBCPP_NO_EXCEPTIONS
467        throw bad_alloc();
468#else
469        abort();
470#endif
471    ::new(r) __i_node(__i, p, nullptr);
472    ++__isz_;
473    return r;
474}
475
476_LIBCPP_HIDDEN
477__i_node*
478__libcpp_db::__find_iterator(const void* __i) const
479{
480    __i_node* r = nullptr;
481    if (__ibeg_ != __iend_)
482    {
483        size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
484        for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
485        {
486            if (nd->__i_ == __i)
487            {
488                r = nd;
489                break;
490            }
491        }
492    }
493    return r;
494}
495
496_LIBCPP_HIDDEN
497void
498__c_node::__remove(__i_node* p)
499{
500    __i_node** r = find(beg_, end_, p);
501    _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
502    if (--end_ != r)
503        memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
504}
505
506_LIBCPP_END_NAMESPACE_STD
507