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