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