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 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 33 bool __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 51 struct __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 77 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* 85 __get_db() 86 { 87 static __libcpp_db db; 88 return &db; 89 } 90 91 _LIBCPP_FUNC_VIS 92 const __libcpp_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& 107 mut() 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 173 void* 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 184 void 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 249 void 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 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 358 void 359 __libcpp_db::unlock() const 360 { 361 #ifndef _LIBCPP_HAS_NO_THREADS 362 mut().unlock(); 363 #endif 364 } 365 366 void 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 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 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 441 bool 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 451 bool 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 461 bool 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 471 bool 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 484 void 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 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 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 609 void 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
