1 //===-------------------------- debug.cpp ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
16 #include "__hash_table"
19 _LIBCPP_BEGIN_NAMESPACE_STD
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 '";
30 _LIBCPP_SAFE_STATIC __libcpp_debug_function_type
31 __libcpp_debug_function = __libcpp_abort_debug_function;
33 bool __libcpp_set_debug_function(__libcpp_debug_function_type __func) {
34 __libcpp_debug_function = __func;
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());
43 _LIBCPP_NORETURN void __libcpp_throw_debug_function(__libcpp_debug_info const& info) {
44 #ifndef _LIBCPP_NO_EXCEPTIONS
45 throw __libcpp_debug_exception(info);
47 __libcpp_abort_debug_function(info);
51 struct __libcpp_debug_exception::__libcpp_debug_exception_imp {
52 __libcpp_debug_info __info_;
53 std::string __what_str_;
56 __libcpp_debug_exception::__libcpp_debug_exception() _NOEXCEPT
60 __libcpp_debug_exception::__libcpp_debug_exception(
61 __libcpp_debug_info const& info) : __imp_(new __libcpp_debug_exception_imp)
63 __imp_->__info_ = info;
64 __imp_->__what_str_ = make_what_str(info);
66 __libcpp_debug_exception::__libcpp_debug_exception(
67 __libcpp_debug_exception const& other) : __imp_(nullptr) {
69 __imp_ = new __libcpp_debug_exception_imp(*other.__imp_);
72 __libcpp_debug_exception::~__libcpp_debug_exception() _NOEXCEPT {
77 const char* __libcpp_debug_exception::what() const _NOEXCEPT {
79 return __imp_->__what_str_.c_str();
80 return "__libcpp_debug_exception";
87 static __libcpp_db db;
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;
112 #endif // !_LIBCPP_HAS_NO_THREADS
114 } // unnamed namespace
116 __i_node::~__i_node()
120 __next_->~__i_node();
125 __c_node::~__c_node()
130 __next_->~__c_node();
135 __libcpp_db::__libcpp_db()
145 __libcpp_db::~__libcpp_db()
149 for (__c_node** p = __cbeg_; p != __cend_; ++p)
161 for (__i_node** p = __ibeg_; p != __iend_; ++p)
174 __libcpp_db::__find_c_from_i(void* __i) const
176 #ifndef _LIBCPP_HAS_NO_THREADS
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;
185 __libcpp_db::__insert_ic(void* __i, const void* __c)
187 #ifndef _LIBCPP_HAS_NO_THREADS
190 if (__cbeg_ == __cend_)
192 size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
193 __c_node* c = __cbeg_[hc];
196 while (c->__c_ != __c)
202 __i_node* i = __insert_iterator(__i);
208 __libcpp_db::__insert_c(void* __c)
210 #ifndef _LIBCPP_HAS_NO_THREADS
213 if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
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*)));
220 for (__c_node** p = __cbeg_; p != __cend_; ++p)
225 size_t h = hash<void*>()(q->__c_) % nc;
226 __c_node* r = q->__next_;
227 q->__next_ = cbeg[h];
234 __cend_ = __cbeg_ + nc;
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)
250 __libcpp_db::__erase_i(void* __i)
252 #ifndef _LIBCPP_HAS_NO_THREADS
255 if (__ibeg_ != __iend_)
257 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
258 __i_node* p = __ibeg_[hi];
261 __i_node* q = nullptr;
262 while (p->__i_ != __i)
270 __ibeg_[hi] = p->__next_;
272 q->__next_ = p->__next_;
273 __c_node* c = p->__c_;
283 __libcpp_db::__invalidate_all(void* __c)
285 #ifndef _LIBCPP_HAS_NO_THREADS
288 if (__cend_ != __cbeg_)
290 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
291 __c_node* p = __cbeg_[hc];
294 while (p->__c_ != __c)
300 while (p->end_ != p->beg_)
303 (*p->end_)->__c_ = nullptr;
309 __libcpp_db::__find_c_and_lock(void* __c) const
311 #ifndef _LIBCPP_HAS_NO_THREADS
314 if (__cend_ == __cbeg_)
316 #ifndef _LIBCPP_HAS_NO_THREADS
321 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
322 __c_node* p = __cbeg_[hc];
325 #ifndef _LIBCPP_HAS_NO_THREADS
330 while (p->__c_ != __c)
335 #ifndef _LIBCPP_HAS_NO_THREADS
345 __libcpp_db::__find_c(void* __c) const
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)
353 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
359 __libcpp_db::unlock() const
361 #ifndef _LIBCPP_HAS_NO_THREADS
367 __libcpp_db::__erase_c(void* __c)
369 #ifndef _LIBCPP_HAS_NO_THREADS
372 if (__cend_ != __cbeg_)
374 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
375 __c_node* p = __cbeg_[hc];
378 __c_node* q = nullptr;
379 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
380 while (p->__c_ != __c)
386 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
389 __cbeg_[hc] = p->__next_;
391 q->__next_ = p->__next_;
392 while (p->end_ != p->beg_)
395 (*p->end_)->__c_ = nullptr;
404 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
406 #ifndef _LIBCPP_HAS_NO_THREADS
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;
432 __libcpp_db::__dereferenceable(const void* __i) const
434 #ifndef _LIBCPP_HAS_NO_THREADS
437 __i_node* i = __find_iterator(__i);
438 return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
442 __libcpp_db::__decrementable(const void* __i) const
444 #ifndef _LIBCPP_HAS_NO_THREADS
447 __i_node* i = __find_iterator(__i);
448 return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
452 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
454 #ifndef _LIBCPP_HAS_NO_THREADS
457 __i_node* i = __find_iterator(__i);
458 return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
462 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
464 #ifndef _LIBCPP_HAS_NO_THREADS
467 __i_node* i = __find_iterator(__i);
468 return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
472 __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
474 #ifndef _LIBCPP_HAS_NO_THREADS
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;
485 __libcpp_db::swap(void* c1, void* c2)
487 #ifndef _LIBCPP_HAS_NO_THREADS
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)
496 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
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)
504 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
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)
511 for (__i_node** p = p2->beg_; p != p2->end_; ++p)
516 __libcpp_db::__insert_i(void* __i)
518 #ifndef _LIBCPP_HAS_NO_THREADS
521 __insert_iterator(__i);
525 __c_node::__add(__i_node* i)
529 size_t nc = 2*static_cast<size_t>(cap_ - beg_);
533 static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
538 memcpy(beg, beg_, nc/2*sizeof(__i_node*));
551 __libcpp_db::__insert_iterator(void* __i)
553 if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
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*)));
560 for (__i_node** p = __ibeg_; p != __iend_; ++p)
565 size_t h = hash<void*>()(q->__i_) % nc;
566 __i_node* r = q->__next_;
567 q->__next_ = ibeg[h];
574 __iend_ = __ibeg_ + nc;
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)));
583 ::new(r) __i_node(__i, p, nullptr);
590 __libcpp_db::__find_iterator(const void* __i) const
592 __i_node* r = nullptr;
593 if (__ibeg_ != __iend_)
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_)
610 __c_node::__remove(__i_node* p)
612 __i_node** r = find(beg_, end_, p);
613 _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
615 memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
618 _LIBCPP_END_NAMESPACE_STD