debug.cpp revision 262801 
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_DEBUG 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    if (__cbeg_ == __cend_)
122        return;
123    size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
124    __c_node* c = __cbeg_[hc];
125    if (c == nullptr)
126        return;
127    while (c->__c_ != __c)
128    {
129        c = c->__next_;
130        if (c == nullptr)
131            return;
132    }
133    __i_node* i = __insert_iterator(__i);
134    c->__add(i);
135    i->__c_ = c;
136}
137
138__c_node*
139__libcpp_db::__insert_c(void* __c)
140{
141    WLock _(mut());
142    if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
143    {
144        size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
145        __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*)));
146        if (cbeg == nullptr)
147#ifndef _LIBCPP_NO_EXCEPTIONS
148            throw bad_alloc();
149#else
150            abort();
151#endif
152        for (__c_node** p = __cbeg_; p != __cend_; ++p)
153        {
154            __c_node* q = *p;
155            while (q != nullptr)
156            {
157                size_t h = hash<void*>()(q->__c_) % nc;
158                __c_node* r = q->__next_;
159                q->__next_ = cbeg[h];
160                cbeg[h] = q;
161                q = r;
162            }
163        }
164        free(__cbeg_);
165        __cbeg_ = cbeg;
166        __cend_ = __cbeg_ + nc;
167    }
168    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
169    __c_node* p = __cbeg_[hc];
170    __c_node* r = __cbeg_[hc] =
171      static_cast<__c_node*>(malloc(sizeof(__c_node)));
172    if (__cbeg_[hc] == nullptr)
173#ifndef _LIBCPP_NO_EXCEPTIONS
174        throw bad_alloc();
175#else
176        abort();
177#endif
178    r->__c_ = __c;
179    r->__next_ = p;
180    ++__csz_;
181    return r;
182}
183
184void
185__libcpp_db::__erase_i(void* __i)
186{
187    WLock _(mut());
188    if (__ibeg_ != __iend_)
189    {
190        size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
191        __i_node* p = __ibeg_[hi];
192        if (p != nullptr)
193        {
194            __i_node* q = nullptr;
195            while (p->__i_ != __i)
196            {
197                q = p;
198                p = p->__next_;
199                if (p == nullptr)
200                    return;
201            }
202            if (q == nullptr)
203                __ibeg_[hi] = p->__next_;
204            else
205                q->__next_ = p->__next_;
206            __c_node* c = p->__c_;
207            free(p);
208            --__isz_;
209            if (c != nullptr)
210                c->__remove(p);
211        }
212    }
213}
214
215void
216__libcpp_db::__invalidate_all(void* __c)
217{
218    WLock _(mut());
219    if (__cend_ != __cbeg_)
220    {
221        size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
222        __c_node* p = __cbeg_[hc];
223        if (p == nullptr)
224            return;
225        while (p->__c_ != __c)
226        {
227            p = p->__next_;
228            if (p == nullptr)
229                return;
230        }
231        while (p->end_ != p->beg_)
232        {
233            --p->end_;
234            (*p->end_)->__c_ = nullptr;
235        }
236    }
237}
238
239__c_node*
240__libcpp_db::__find_c_and_lock(void* __c) const
241{
242    mut().lock();
243    if (__cend_ == __cbeg_)
244    {
245        mut().unlock();
246        return nullptr;
247    }
248    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
249    __c_node* p = __cbeg_[hc];
250    if (p == nullptr)
251    {
252        mut().unlock();
253        return nullptr;
254    }
255    while (p->__c_ != __c)
256    {
257        p = p->__next_;
258        if (p == nullptr)
259        {
260            mut().unlock();
261            return nullptr;
262        }
263    }
264    return p;
265}
266
267__c_node*
268__libcpp_db::__find_c(void* __c) const
269{
270    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
271    __c_node* p = __cbeg_[hc];
272    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
273    while (p->__c_ != __c)
274    {
275        p = p->__next_;
276        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
277    }
278    return p;
279}
280
281void
282__libcpp_db::unlock() const
283{
284    mut().unlock();
285}
286
287void
288__libcpp_db::__erase_c(void* __c)
289{
290    WLock _(mut());
291    if (__cend_ != __cbeg_)
292    {
293        size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
294        __c_node* p = __cbeg_[hc];
295        if (p == nullptr)
296            return;
297        __c_node* q = nullptr;
298        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
299        while (p->__c_ != __c)
300        {
301            q = p;
302            p = p->__next_;
303            if (p == nullptr)
304                return;
305            _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
306        }
307        if (q == nullptr)
308            __cbeg_[hc] = p->__next_;
309        else
310            q->__next_ = p->__next_;
311        while (p->end_ != p->beg_)
312        {
313            --p->end_;
314            (*p->end_)->__c_ = nullptr;
315        }
316        free(p->beg_);
317        free(p);
318        --__csz_;
319    }
320}
321
322void
323__libcpp_db::__iterator_copy(void* __i, const void* __i0)
324{
325    WLock _(mut());
326    __i_node* i = __find_iterator(__i);
327    __i_node* i0 = __find_iterator(__i0);
328    __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
329    if (i == nullptr && i0 != nullptr)
330        i = __insert_iterator(__i);
331    __c_node* c = i != nullptr ? i->__c_ : nullptr;
332    if (c != c0)
333    {
334        if (c != nullptr)
335            c->__remove(i);
336        if (i != nullptr)
337        {
338            i->__c_ = nullptr;
339            if (c0 != nullptr)
340            {
341                i->__c_ = c0;
342                i->__c_->__add(i);
343            }
344        }
345    }
346}
347
348bool
349__libcpp_db::__dereferenceable(const void* __i) const
350{
351    RLock _(mut());
352    __i_node* i = __find_iterator(__i);
353    return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
354}
355
356bool
357__libcpp_db::__decrementable(const void* __i) const
358{
359    RLock _(mut());
360    __i_node* i = __find_iterator(__i);
361    return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
362}
363
364bool
365__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
366{
367    RLock _(mut());
368    __i_node* i = __find_iterator(__i);
369    return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
370}
371
372bool
373__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
374{
375    RLock _(mut());
376    __i_node* i = __find_iterator(__i);
377    return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
378}
379
380bool
381__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
382{
383    RLock _(mut());
384    __i_node* i = __find_iterator(__i);
385    __i_node* j = __find_iterator(__j);
386    __c_node* ci = i != nullptr ? i->__c_ : nullptr;
387    __c_node* cj = j != nullptr ? j->__c_ : nullptr;
388    return ci != nullptr && ci == cj;
389}
390
391void
392__libcpp_db::swap(void* c1, void* c2)
393{
394    WLock _(mut());
395    size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
396    __c_node* p1 = __cbeg_[hc];
397    _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
398    while (p1->__c_ != c1)
399    {
400        p1 = p1->__next_;
401        _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
402    }
403    hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
404    __c_node* p2 = __cbeg_[hc];
405    _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
406    while (p2->__c_ != c2)
407    {
408        p2 = p2->__next_;
409        _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
410    }
411    std::swap(p1->beg_, p2->beg_);
412    std::swap(p1->end_, p2->end_);
413    std::swap(p1->cap_, p2->cap_);
414    for (__i_node** p = p1->beg_; p != p1->end_; ++p)
415        (*p)->__c_ = p1;
416    for (__i_node** p = p2->beg_; p != p2->end_; ++p)
417        (*p)->__c_ = p2;
418}
419
420void
421__libcpp_db::__insert_i(void* __i)
422{
423    WLock _(mut());
424    __insert_iterator(__i);
425}
426
427void
428__c_node::__add(__i_node* i)
429{
430    if (end_ == cap_)
431    {
432        size_t nc = 2*static_cast<size_t>(cap_ - beg_);
433        if (nc == 0)
434            nc = 1;
435        __i_node** beg =
436           static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
437        if (beg == nullptr)
438#ifndef _LIBCPP_NO_EXCEPTIONS
439            throw bad_alloc();
440#else
441            abort();
442#endif
443        if (nc > 1)
444            memcpy(beg, beg_, nc/2*sizeof(__i_node*));
445        free(beg_);
446        beg_ = beg;
447        end_ = beg_ + nc/2;
448        cap_ = beg_ + nc;
449    }
450    *end_++ = i;
451}
452
453// private api
454
455_LIBCPP_HIDDEN
456__i_node*
457__libcpp_db::__insert_iterator(void* __i)
458{
459    if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
460    {
461        size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
462        __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*)));
463        if (ibeg == nullptr)
464#ifndef _LIBCPP_NO_EXCEPTIONS
465            throw bad_alloc();
466#else
467            abort();
468#endif
469        for (__i_node** p = __ibeg_; p != __iend_; ++p)
470        {
471            __i_node* q = *p;
472            while (q != nullptr)
473            {
474                size_t h = hash<void*>()(q->__i_) % nc;
475                __i_node* r = q->__next_;
476                q->__next_ = ibeg[h];
477                ibeg[h] = q;
478                q = r;
479            }
480        }
481        free(__ibeg_);
482        __ibeg_ = ibeg;
483        __iend_ = __ibeg_ + nc;
484    }
485    size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
486    __i_node* p = __ibeg_[hi];
487    __i_node* r = __ibeg_[hi] =
488      static_cast<__i_node*>(malloc(sizeof(__i_node)));
489    if (r == nullptr)
490#ifndef _LIBCPP_NO_EXCEPTIONS
491        throw bad_alloc();
492#else
493        abort();
494#endif
495    ::new(r) __i_node(__i, p, nullptr);
496    ++__isz_;
497    return r;
498}
499
500_LIBCPP_HIDDEN
501__i_node*
502__libcpp_db::__find_iterator(const void* __i) const
503{
504    __i_node* r = nullptr;
505    if (__ibeg_ != __iend_)
506    {
507        size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
508        for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
509        {
510            if (nd->__i_ == __i)
511            {
512                r = nd;
513                break;
514            }
515        }
516    }
517    return r;
518}
519
520_LIBCPP_HIDDEN
521void
522__c_node::__remove(__i_node* p)
523{
524    __i_node** r = find(beg_, end_, p);
525    _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
526    if (--end_ != r)
527        memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
528}
529
530_LIBCPP_END_NAMESPACE_STD
531