1 //===-------------------------- debug.cpp ---------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
15 #include "__hash_table"
16 #ifndef _LIBCPP_HAS_NO_THREADS
18 #if defined(__unix__) && defined(__ELF__) && defined(_LIBCPP_HAS_COMMENT_LIB_PRAGMA)
19 #pragma comment(lib, "pthread")
23 _LIBCPP_BEGIN_NAMESPACE_STD
25 std::string __libcpp_debug_info::what() const {
27 msg += ":" + to_string(__line_) + ": _LIBCPP_ASSERT '";
33 _LIBCPP_NORETURN void __libcpp_abort_debug_function(__libcpp_debug_info const& info) {
34 std::fprintf(stderr, "%s\n", info.what().c_str());
38 _LIBCPP_SAFE_STATIC __libcpp_debug_function_type
39 __libcpp_debug_function = __libcpp_abort_debug_function;
41 bool __libcpp_set_debug_function(__libcpp_debug_function_type __func) {
42 __libcpp_debug_function = __func;
50 static _LIBCPP_NO_DESTROY __libcpp_db db;
64 #ifndef _LIBCPP_HAS_NO_THREADS
65 typedef mutex mutex_type;
66 typedef lock_guard<mutex_type> WLock;
67 typedef lock_guard<mutex_type> RLock;
72 static _LIBCPP_NO_DESTROY mutex_type m;
75 #endif // !_LIBCPP_HAS_NO_THREADS
77 } // unnamed namespace
98 __libcpp_db::__libcpp_db()
108 __libcpp_db::~__libcpp_db()
112 for (__c_node** p = __cbeg_; p != __cend_; ++p)
124 for (__i_node** p = __ibeg_; p != __iend_; ++p)
137 __libcpp_db::__find_c_from_i(void* __i) const
139 #ifndef _LIBCPP_HAS_NO_THREADS
142 __i_node* i = __find_iterator(__i);
143 _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database.");
144 return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
148 __libcpp_db::__insert_ic(void* __i, const void* __c)
150 #ifndef _LIBCPP_HAS_NO_THREADS
153 if (__cbeg_ == __cend_)
155 size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
156 __c_node* c = __cbeg_[hc];
159 while (c->__c_ != __c)
165 __i_node* i = __insert_iterator(__i);
171 __libcpp_db::__insert_c(void* __c, __libcpp_db::_InsertConstruct *__fn)
173 #ifndef _LIBCPP_HAS_NO_THREADS
176 if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
178 size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
179 __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(__c_node*)));
183 for (__c_node** p = __cbeg_; p != __cend_; ++p)
188 size_t h = hash<void*>()(q->__c_) % nc;
189 __c_node* r = q->__next_;
190 q->__next_ = cbeg[h];
197 __cend_ = __cbeg_ + nc;
199 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
200 __c_node* p = __cbeg_[hc];
201 void *buf = malloc(sizeof(__c_node));
204 __cbeg_[hc] = __fn(buf, __c, p);
210 __libcpp_db::__erase_i(void* __i)
212 #ifndef _LIBCPP_HAS_NO_THREADS
215 if (__ibeg_ != __iend_)
217 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
218 __i_node* p = __ibeg_[hi];
221 __i_node* q = nullptr;
222 while (p->__i_ != __i)
230 __ibeg_[hi] = p->__next_;
232 q->__next_ = p->__next_;
233 __c_node* c = p->__c_;
243 __libcpp_db::__invalidate_all(void* __c)
245 #ifndef _LIBCPP_HAS_NO_THREADS
248 if (__cend_ != __cbeg_)
250 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
251 __c_node* p = __cbeg_[hc];
254 while (p->__c_ != __c)
260 while (p->end_ != p->beg_)
263 (*p->end_)->__c_ = nullptr;
269 __libcpp_db::__find_c_and_lock(void* __c) const
271 #ifndef _LIBCPP_HAS_NO_THREADS
274 if (__cend_ == __cbeg_)
276 #ifndef _LIBCPP_HAS_NO_THREADS
281 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
282 __c_node* p = __cbeg_[hc];
285 #ifndef _LIBCPP_HAS_NO_THREADS
290 while (p->__c_ != __c)
295 #ifndef _LIBCPP_HAS_NO_THREADS
305 __libcpp_db::__find_c(void* __c) const
307 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
308 __c_node* p = __cbeg_[hc];
309 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
310 while (p->__c_ != __c)
313 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
319 __libcpp_db::unlock() const
321 #ifndef _LIBCPP_HAS_NO_THREADS
327 __libcpp_db::__erase_c(void* __c)
329 #ifndef _LIBCPP_HAS_NO_THREADS
332 if (__cend_ != __cbeg_)
334 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
335 __c_node* p = __cbeg_[hc];
338 __c_node* q = nullptr;
339 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
340 while (p->__c_ != __c)
346 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
349 __cbeg_[hc] = p->__next_;
351 q->__next_ = p->__next_;
352 while (p->end_ != p->beg_)
355 (*p->end_)->__c_ = nullptr;
364 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
366 #ifndef _LIBCPP_HAS_NO_THREADS
369 __i_node* i = __find_iterator(__i);
370 __i_node* i0 = __find_iterator(__i0);
371 __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
372 if (i == nullptr && i0 != nullptr)
373 i = __insert_iterator(__i);
374 __c_node* c = i != nullptr ? i->__c_ : nullptr;
392 __libcpp_db::__dereferenceable(const void* __i) const
394 #ifndef _LIBCPP_HAS_NO_THREADS
397 __i_node* i = __find_iterator(__i);
398 return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
402 __libcpp_db::__decrementable(const void* __i) const
404 #ifndef _LIBCPP_HAS_NO_THREADS
407 __i_node* i = __find_iterator(__i);
408 return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
412 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
414 #ifndef _LIBCPP_HAS_NO_THREADS
417 __i_node* i = __find_iterator(__i);
418 return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
422 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
424 #ifndef _LIBCPP_HAS_NO_THREADS
427 __i_node* i = __find_iterator(__i);
428 return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
432 __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
434 #ifndef _LIBCPP_HAS_NO_THREADS
437 __i_node* i = __find_iterator(__i);
438 __i_node* j = __find_iterator(__j);
439 __c_node* ci = i != nullptr ? i->__c_ : nullptr;
440 __c_node* cj = j != nullptr ? j->__c_ : nullptr;
441 return ci != nullptr && ci == cj;
445 __libcpp_db::swap(void* c1, void* c2)
447 #ifndef _LIBCPP_HAS_NO_THREADS
450 size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
451 __c_node* p1 = __cbeg_[hc];
452 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
453 while (p1->__c_ != c1)
456 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
458 hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
459 __c_node* p2 = __cbeg_[hc];
460 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
461 while (p2->__c_ != c2)
464 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
466 std::swap(p1->beg_, p2->beg_);
467 std::swap(p1->end_, p2->end_);
468 std::swap(p1->cap_, p2->cap_);
469 for (__i_node** p = p1->beg_; p != p1->end_; ++p)
471 for (__i_node** p = p2->beg_; p != p2->end_; ++p)
476 __libcpp_db::__insert_i(void* __i)
478 #ifndef _LIBCPP_HAS_NO_THREADS
481 __insert_iterator(__i);
485 __c_node::__add(__i_node* i)
489 size_t nc = 2*static_cast<size_t>(cap_ - beg_);
493 static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
498 memcpy(beg, beg_, nc/2*sizeof(__i_node*));
511 __libcpp_db::__insert_iterator(void* __i)
513 if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
515 size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
516 __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(__i_node*)));
520 for (__i_node** p = __ibeg_; p != __iend_; ++p)
525 size_t h = hash<void*>()(q->__i_) % nc;
526 __i_node* r = q->__next_;
527 q->__next_ = ibeg[h];
534 __iend_ = __ibeg_ + nc;
536 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
537 __i_node* p = __ibeg_[hi];
538 __i_node* r = __ibeg_[hi] =
539 static_cast<__i_node*>(malloc(sizeof(__i_node)));
543 ::new(r) __i_node(__i, p, nullptr);
550 __libcpp_db::__find_iterator(const void* __i) const
552 __i_node* r = nullptr;
553 if (__ibeg_ != __iend_)
555 size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
556 for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
570 __c_node::__remove(__i_node* p)
572 __i_node** r = find(beg_, end_, p);
573 _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
575 memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
578 _LIBCPP_END_NAMESPACE_STD