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