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 21static 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 33bool __libcpp_set_debug_function(__libcpp_debug_function_type __func) { 34 __libcpp_debug_function = __func; 35 return true; 36} 37 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 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 51struct __libcpp_debug_exception::__libcpp_debug_exception_imp { 52 __libcpp_debug_info __info_; 53 std::string __what_str_; 54}; 55 56__libcpp_debug_exception::__libcpp_debug_exception() _NOEXCEPT 57 : __imp_(nullptr) { 58} 59 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} 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 72__libcpp_debug_exception::~__libcpp_debug_exception() _NOEXCEPT { 73 if (__imp_) 74 delete __imp_; 75} 76 77const 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* 85__get_db() 86{ 87 static __libcpp_db db; 88 return &db; 89} 90 91_LIBCPP_FUNC_VIS 92const __libcpp_db* 93__get_const_db() 94{ 95 return __get_db(); 96} 97 98namespace 99{ 100 101#ifndef _LIBCPP_HAS_NO_THREADS 102typedef mutex mutex_type; 103typedef lock_guard<mutex_type> WLock; 104typedef lock_guard<mutex_type> RLock; 105 106mutex_type& 107mut() 108{ 109 static mutex_type m; 110 return m; 111} 112#endif // !_LIBCPP_HAS_NO_THREADS 113 114} // unnamed namespace 115 116__i_node::~__i_node() 117{ 118 if (__next_) 119 { 120 __next_->~__i_node(); 121 free(__next_); 122 } 123} 124 125__c_node::~__c_node() 126{ 127 free(beg_); 128 if (__next_) 129 { 130 __next_->~__c_node(); 131 free(__next_); 132 } 133} 134 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 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 173void* 174__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 184void 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* 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 249void 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 282void 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* 309__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* 345__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 358void 359__libcpp_db::unlock() const 360{ 361#ifndef _LIBCPP_HAS_NO_THREADS 362 mut().unlock(); 363#endif 364} 365 366void 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 403void 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 431bool 432__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 441bool 442__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 451bool 452__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 461bool 462__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 471bool 472__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 484void 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 515void 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 524void 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* 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* 590__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 609void 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