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