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