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*
__get_db()22 __get_db()
23 {
24     static __libcpp_db db;
25     return &db;
26 }
27 
28 _LIBCPP_FUNC_VIS
29 const __libcpp_db*
__get_const_db()30 __get_const_db()
31 {
32     return __get_db();
33 }
34 
35 namespace
36 {
37 
38 #if !_LIBCPP_SINGLE_THREADED
39 typedef mutex mutex_type;
40 typedef lock_guard<mutex_type> WLock;
41 typedef lock_guard<mutex_type> RLock;
42 
43 mutex_type&
mut()44 mut()
45 {
46     static mutex_type m;
47     return m;
48 }
49 #endif // !_LIBCPP_SINGLE_THREADED
50 
51 }  // unnamed namespace
52 
~__i_node()53 __i_node::~__i_node()
54 {
55     if (__next_)
56     {
57         __next_->~__i_node();
58         free(__next_);
59     }
60 }
61 
~__c_node()62 __c_node::~__c_node()
63 {
64     free(beg_);
65     if (__next_)
66     {
67         __next_->~__c_node();
68         free(__next_);
69     }
70 }
71 
__libcpp_db()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 
~__libcpp_db()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 
110 void*
__find_c_from_i(void * __i) const111 __libcpp_db::__find_c_from_i(void* __i) const
112 {
113 #if !_LIBCPP_SINGLE_THREADED
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 
121 void
__insert_ic(void * __i,const void * __c)122 __libcpp_db::__insert_ic(void* __i, const void* __c)
123 {
124 #if !_LIBCPP_SINGLE_THREADED
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*
__insert_c(void * __c)145 __libcpp_db::__insert_c(void* __c)
146 {
147 #if !_LIBCPP_SINGLE_THREADED
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 
192 void
__erase_i(void * __i)193 __libcpp_db::__erase_i(void* __i)
194 {
195 #if !_LIBCPP_SINGLE_THREADED
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 
225 void
__invalidate_all(void * __c)226 __libcpp_db::__invalidate_all(void* __c)
227 {
228 #if !_LIBCPP_SINGLE_THREADED
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*
__find_c_and_lock(void * __c) const252 __libcpp_db::__find_c_and_lock(void* __c) const
253 {
254 #if !_LIBCPP_SINGLE_THREADED
255     mut().lock();
256 #endif
257     if (__cend_ == __cbeg_)
258     {
259 #if !_LIBCPP_SINGLE_THREADED
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 #if !_LIBCPP_SINGLE_THREADED
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 #if !_LIBCPP_SINGLE_THREADED
279             mut().unlock();
280 #endif
281             return nullptr;
282         }
283     }
284     return p;
285 }
286 
287 __c_node*
__find_c(void * __c) const288 __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 
301 void
unlock() const302 __libcpp_db::unlock() const
303 {
304 #if !_LIBCPP_SINGLE_THREADED
305     mut().unlock();
306 #endif
307 }
308 
309 void
__erase_c(void * __c)310 __libcpp_db::__erase_c(void* __c)
311 {
312 #if !_LIBCPP_SINGLE_THREADED
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 
346 void
__iterator_copy(void * __i,const void * __i0)347 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
348 {
349 #if !_LIBCPP_SINGLE_THREADED
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 
374 bool
__dereferenceable(const void * __i) const375 __libcpp_db::__dereferenceable(const void* __i) const
376 {
377 #if !_LIBCPP_SINGLE_THREADED
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 
384 bool
__decrementable(const void * __i) const385 __libcpp_db::__decrementable(const void* __i) const
386 {
387 #if !_LIBCPP_SINGLE_THREADED
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 
394 bool
__addable(const void * __i,ptrdiff_t __n) const395 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
396 {
397 #if !_LIBCPP_SINGLE_THREADED
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 
404 bool
__subscriptable(const void * __i,ptrdiff_t __n) const405 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
406 {
407 #if !_LIBCPP_SINGLE_THREADED
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 
414 bool
__less_than_comparable(const void * __i,const void * __j) const415 __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
416 {
417 #if !_LIBCPP_SINGLE_THREADED
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 
427 void
swap(void * c1,void * c2)428 __libcpp_db::swap(void* c1, void* c2)
429 {
430 #if !_LIBCPP_SINGLE_THREADED
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 
458 void
__insert_i(void * __i)459 __libcpp_db::__insert_i(void* __i)
460 {
461 #if !_LIBCPP_SINGLE_THREADED
462     WLock _(mut());
463 #endif
464     __insert_iterator(__i);
465 }
466 
467 void
__add(__i_node * i)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*
__insert_iterator(void * __i)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*
__find_iterator(const void * __i) const542 __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
561 void
__remove(__i_node * p)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