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 25 std::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 41 bool __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 55 const __libcpp_db* 56 __get_const_db() 57 { 58 return __get_db(); 59 } 60 61 namespace 62 { 63 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; 68 69 mutex_type& 70 mut() 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 136 void* 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 147 void 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 170 void 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 209 void 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 242 void 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 318 void 319 __libcpp_db::unlock() const 320 { 321 #ifndef _LIBCPP_HAS_NO_THREADS 322 mut().unlock(); 323 #endif 324 } 325 326 void 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 363 void 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 391 bool 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 401 bool 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 411 bool 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 421 bool 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 431 bool 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 == cj; 442 } 443 444 void 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 475 void 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 484 void 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 569 void 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
Indexes created Tue Aug 18 00:25:06 UTC 2026