debug.cpp revision 227983
10SN/A//===-------------------------- debug.cpp ---------------------------------===// 22362SN/A// 30SN/A// The LLVM Compiler Infrastructure 40SN/A// 50SN/A// This file is dual licensed under the MIT and the University of Illinois Open 60SN/A// Source Licenses. See LICENSE.TXT for details. 72362SN/A// 80SN/A//===----------------------------------------------------------------------===// 92362SN/A 100SN/A#define _LIBCPP_DEBUG2 1 110SN/A#include "__config" 120SN/A#include "__debug" 130SN/A#include "functional" 140SN/A#include "algorithm" 150SN/A#include "__hash_table" 160SN/A#include "mutex" 170SN/A 180SN/A_LIBCPP_BEGIN_NAMESPACE_STD 190SN/A 200SN/A_LIBCPP_VISIBLE 212362SN/A__libcpp_db* 222362SN/A__get_db() 232362SN/A{ 240SN/A static __libcpp_db db; 250SN/A return &db; 260SN/A}; 270SN/A 280SN/A_LIBCPP_VISIBLE 290SN/Aconst __libcpp_db* 300SN/A__get_const_db() 310SN/A{ 320SN/A return __get_db(); 330SN/A} 340SN/A 350SN/Anamespace 360SN/A{ 370SN/A 380SN/Atypedef mutex mutex_type; 390SN/Atypedef lock_guard<mutex_type> WLock; 400SN/Atypedef lock_guard<mutex_type> RLock; 410SN/A 420SN/Amutex_type& 430SN/Amut() 440SN/A{ 450SN/A static mutex_type m; 460SN/A return m; 470SN/A} 480SN/A 490SN/A} // unnamed namespace 500SN/A 510SN/A__i_node::~__i_node() 520SN/A{ 530SN/A if (__next_) 540SN/A { 550SN/A __next_->~__i_node(); 560SN/A free(__next_); 570SN/A } 580SN/A} 590SN/A 600SN/A__c_node::~__c_node() 610SN/A{ 620SN/A free(beg_); 630SN/A if (__next_) 640SN/A { 650SN/A __next_->~__c_node(); 660SN/A free(__next_); 670SN/A } 680SN/A} 690SN/A 700SN/A__libcpp_db::__libcpp_db() 710SN/A : __cbeg_(nullptr), 720SN/A __cend_(nullptr), 730SN/A __csz_(0), 740SN/A __ibeg_(nullptr), 750SN/A __iend_(nullptr), 760SN/A __isz_(0) 770SN/A{ 780SN/A} 790SN/A 800SN/A__libcpp_db::~__libcpp_db() 810SN/A{ 820SN/A if (__cbeg_) 830SN/A { 840SN/A for (__c_node** p = __cbeg_; p != __cend_; ++p) 850SN/A { 860SN/A if (*p != nullptr) 870SN/A { 880SN/A (*p)->~__c_node(); 890SN/A free(*p); 900SN/A } 910SN/A } 920SN/A free(__cbeg_); 930SN/A } 940SN/A if (__ibeg_) 950SN/A { 960SN/A for (__i_node** p = __ibeg_; p != __iend_; ++p) 970SN/A { 980SN/A if (*p != nullptr) 990SN/A { 1000SN/A (*p)->~__i_node(); 1010SN/A free(*p); 1020SN/A } 1030SN/A } 1040SN/A free(__ibeg_); 1050SN/A } 1060SN/A} 1070SN/A 1080SN/Avoid* 1090SN/A__libcpp_db::__find_c_from_i(void* __i) const 1100SN/A{ 1110SN/A RLock _(mut()); 1120SN/A __i_node* i = __find_iterator(__i); 1130SN/A _LIBCPP_ASSERT(i != nullptr, "iterator constructed in translation unit with debug mode not enabled." 1140SN/A " #define _LIBCPP_DEBUG2 1 for that translation unit."); 1150SN/A return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; 1160SN/A} 1170SN/A 1180SN/Avoid 1190SN/A__libcpp_db::__insert_ic(void* __i, const void* __c) 1200SN/A{ 1210SN/A WLock _(mut()); 1220SN/A __i_node* i = __insert_iterator(__i); 1230SN/A const char* errmsg = 1240SN/A "Container constructed in a translation unit with debug mode disabled." 1250SN/A " But it is being used in a translation unit with debug mode enabled." 1260SN/A " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1"; 1270SN/A _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg); 1280SN/A size_t hc = hash<const void*>()(__c) % (__cend_ - __cbeg_); 1290SN/A __c_node* c = __cbeg_[hc]; 1300SN/A _LIBCPP_ASSERT(c != nullptr, errmsg); 1310SN/A while (c->__c_ != __c) 1320SN/A { 1330SN/A c = c->__next_; 1340SN/A _LIBCPP_ASSERT(c != nullptr, errmsg); 1350SN/A } 1360SN/A c->__add(i); 1370SN/A i->__c_ = c; 1380SN/A} 1390SN/A 1400SN/A__c_node* 1410SN/A__libcpp_db::__insert_c(void* __c) 1420SN/A{ 1430SN/A WLock _(mut()); 1440SN/A if (__csz_ + 1 > __cend_ - __cbeg_) 1450SN/A { 1460SN/A size_t nc = __next_prime(2*(__cend_ - __cbeg_) + 1); 1470SN/A __c_node** cbeg = (__c_node**)calloc(nc, sizeof(void*)); 1480SN/A if (cbeg == nullptr) 1490SN/A throw bad_alloc(); 1500SN/A for (__c_node** p = __cbeg_; p != __cend_; ++p) 1510SN/A { 1520SN/A __c_node* q = *p; 1530SN/A while (q != nullptr) 1540SN/A { 1550SN/A size_t h = hash<void*>()(q->__c_) % nc; 1560SN/A __c_node* r = q->__next_; 1570SN/A q->__next_ = cbeg[h]; 1580SN/A cbeg[h] = q; 1590SN/A q = r; 1600SN/A } 1610SN/A } 1620SN/A free(__cbeg_); 1630SN/A __cbeg_ = cbeg; 1640SN/A __cend_ = __cbeg_ + nc; 1650SN/A } 1660SN/A size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 1670SN/A __c_node* p = __cbeg_[hc]; 1680SN/A __c_node* r = __cbeg_[hc] = (__c_node*)malloc(sizeof(__c_node)); 1690SN/A if (__cbeg_[hc] == nullptr) 1700SN/A throw bad_alloc(); 1710SN/A r->__c_ = __c; 1720SN/A r->__next_ = p; 1730SN/A ++__csz_; 1740SN/A return r; 1750SN/A} 1760SN/A 1770SN/Avoid 1780SN/A__libcpp_db::__erase_i(void* __i) 1790SN/A{ 1800SN/A WLock _(mut()); 1810SN/A if (__ibeg_ != __iend_) 1820SN/A { 1830SN/A size_t hi = hash<void*>()(__i) % (__iend_ - __ibeg_); 1840SN/A __i_node* p = __ibeg_[hi]; 1850SN/A if (p != nullptr) 1860SN/A { 1870SN/A __i_node* q = nullptr; 1880SN/A while (p->__i_ != __i) 1890SN/A { 1900SN/A q = p; 1910SN/A p = p->__next_; 1920SN/A if (p == nullptr) 1930SN/A return; 1940SN/A } 1950SN/A if (q == nullptr) 1960SN/A __ibeg_[hi] = p->__next_; 1970SN/A else 1980SN/A q->__next_ = p->__next_; 1990SN/A __c_node* c = p->__c_; 2000SN/A free(p); 2010SN/A --__isz_; 2020SN/A if (c != nullptr) 2030SN/A c->__remove(p); 2040SN/A } 2050SN/A } 2060SN/A} 2070SN/A 2080SN/Avoid 2090SN/A__libcpp_db::__invalidate_all(void* __c) 2100SN/A{ 2110SN/A WLock _(mut()); 2120SN/A size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 2130SN/A __c_node* p = __cbeg_[hc]; 2140SN/A _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A"); 2150SN/A while (p->__c_ != __c) 2160SN/A { 2170SN/A p = p->__next_; 2180SN/A _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B"); 2190SN/A } 2200SN/A while (p->end_ != p->beg_) 2210SN/A { 2220SN/A --p->end_; 2230SN/A (*p->end_)->__c_ = nullptr; 2240SN/A } 2250SN/A} 2260SN/A 2270SN/A__c_node* 2280SN/A__libcpp_db::__find_c_and_lock(void* __c) const 2290SN/A{ 2300SN/A mut().lock(); 2310SN/A size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 2320SN/A __c_node* p = __cbeg_[hc]; 2330SN/A _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A"); 2340SN/A while (p->__c_ != __c) 2350SN/A { 2360SN/A p = p->__next_; 2370SN/A _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B"); 2380SN/A } 2390SN/A return p; 2400SN/A} 2410SN/A 2420SN/A__c_node* 243__libcpp_db::__find_c(void* __c) const 244{ 245 size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 246 __c_node* p = __cbeg_[hc]; 247 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 248 while (p->__c_ != __c) 249 { 250 p = p->__next_; 251 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 252 } 253 return p; 254} 255 256void 257__libcpp_db::unlock() const 258{ 259 mut().unlock(); 260} 261 262void 263__libcpp_db::__erase_c(void* __c) 264{ 265 WLock _(mut()); 266 size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 267 __c_node* p = __cbeg_[hc]; 268 __c_node* q = nullptr; 269 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 270 while (p->__c_ != __c) 271 { 272 q = p; 273 p = p->__next_; 274 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 275 } 276 if (q == nullptr) 277 __cbeg_[hc] = p->__next_; 278 else 279 q->__next_ = p->__next_; 280 while (p->end_ != p->beg_) 281 { 282 --p->end_; 283 (*p->end_)->__c_ = nullptr; 284 } 285 free(p->beg_); 286 free(p); 287 --__csz_; 288} 289 290void 291__libcpp_db::__iterator_copy(void* __i, const void* __i0) 292{ 293 WLock _(mut()); 294 __i_node* i = __find_iterator(__i); 295 __i_node* i0 = __find_iterator(__i0); 296 __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 297 if (i == nullptr && c0 != nullptr) 298 i = __insert_iterator(__i); 299 __c_node* c = i != nullptr ? i->__c_ : nullptr; 300 if (c != c0) 301 { 302 if (c != nullptr) 303 c->__remove(i); 304 if (i != nullptr) 305 { 306 i->__c_ = nullptr; 307 if (c0 != nullptr) 308 { 309 i->__c_ = c0; 310 i->__c_->__add(i); 311 } 312 } 313 } 314} 315 316bool 317__libcpp_db::__dereferenceable(const void* __i) const 318{ 319 RLock _(mut()); 320 __i_node* i = __find_iterator(__i); 321 return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 322} 323 324bool 325__libcpp_db::__decrementable(const void* __i) const 326{ 327 RLock _(mut()); 328 __i_node* i = __find_iterator(__i); 329 return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 330} 331 332bool 333__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 334{ 335 RLock _(mut()); 336 __i_node* i = __find_iterator(__i); 337 return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 338} 339 340bool 341__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 342{ 343 RLock _(mut()); 344 __i_node* i = __find_iterator(__i); 345 return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 346} 347 348bool 349__libcpp_db::__comparable(const void* __i, const void* __j) const 350{ 351 RLock _(mut()); 352 __i_node* i = __find_iterator(__i); 353 __i_node* j = __find_iterator(__j); 354 __c_node* ci = i != nullptr ? i->__c_ : nullptr; 355 __c_node* cj = j != nullptr ? j->__c_ : nullptr; 356 return ci != nullptr && ci == cj; 357} 358 359void 360__libcpp_db::swap(void* c1, void* c2) 361{ 362 WLock _(mut()); 363 size_t hc = hash<void*>()(c1) % (__cend_ - __cbeg_); 364 __c_node* p1 = __cbeg_[hc]; 365 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 366 while (p1->__c_ != c1) 367 { 368 p1 = p1->__next_; 369 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 370 } 371 hc = hash<void*>()(c2) % (__cend_ - __cbeg_); 372 __c_node* p2 = __cbeg_[hc]; 373 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 374 while (p2->__c_ != c2) 375 { 376 p2 = p2->__next_; 377 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 378 } 379 std::swap(p1->beg_, p2->beg_); 380 std::swap(p1->end_, p2->end_); 381 std::swap(p1->cap_, p2->cap_); 382 for (__i_node** p = p1->beg_; p != p1->end_; ++p) 383 (*p)->__c_ = p1; 384 for (__i_node** p = p2->beg_; p != p2->end_; ++p) 385 (*p)->__c_ = p2; 386} 387 388void 389__libcpp_db::__insert_i(void* __i) 390{ 391 WLock _(mut()); 392 __insert_iterator(__i); 393} 394 395void 396__c_node::__add(__i_node* i) 397{ 398 if (end_ == cap_) 399 { 400 size_t nc = 2*(cap_ - beg_); 401 if (nc == 0) 402 nc = 1; 403 __i_node** beg = (__i_node**)malloc(nc * sizeof(__i_node*)); 404 if (beg == nullptr) 405 throw bad_alloc(); 406 if (nc > 1) 407 memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 408 free(beg_); 409 beg_ = beg; 410 end_ = beg_ + nc/2; 411 cap_ = beg_ + nc; 412 } 413 *end_++ = i; 414} 415 416// private api 417 418_LIBCPP_HIDDEN 419__i_node* 420__libcpp_db::__insert_iterator(void* __i) 421{ 422 if (__isz_ + 1 > __iend_ - __ibeg_) 423 { 424 size_t nc = __next_prime(2*(__iend_ - __ibeg_) + 1); 425 __i_node** ibeg = (__i_node**)calloc(nc, sizeof(void*)); 426 if (ibeg == nullptr) 427 throw bad_alloc(); 428 for (__i_node** p = __ibeg_; p != __iend_; ++p) 429 { 430 __i_node* q = *p; 431 while (q != nullptr) 432 { 433 size_t h = hash<void*>()(q->__i_) % nc; 434 __i_node* r = q->__next_; 435 q->__next_ = ibeg[h]; 436 ibeg[h] = q; 437 q = r; 438 } 439 } 440 free(__ibeg_); 441 __ibeg_ = ibeg; 442 __iend_ = __ibeg_ + nc; 443 } 444 size_t hi = hash<void*>()(__i) % (__iend_ - __ibeg_); 445 __i_node* p = __ibeg_[hi]; 446 __i_node* r = __ibeg_[hi] = (__i_node*)malloc(sizeof(__i_node)); 447 if (r == nullptr) 448 throw bad_alloc(); 449 ::new(r) __i_node(__i, p, nullptr); 450 ++__isz_; 451 return r; 452} 453 454_LIBCPP_HIDDEN 455__i_node* 456__libcpp_db::__find_iterator(const void* __i) const 457{ 458 __i_node* r = nullptr; 459 if (__ibeg_ != __iend_) 460 { 461 size_t h = hash<const void*>()(__i) % (__iend_ - __ibeg_); 462 for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 463 { 464 if (nd->__i_ == __i) 465 { 466 r = nd; 467 break; 468 } 469 } 470 } 471 return r; 472} 473 474_LIBCPP_HIDDEN 475void 476__c_node::__remove(__i_node* p) 477{ 478 __i_node** r = find(beg_, end_, p); 479 _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 480 if (--end_ != r) 481 memmove(r, r+1, (end_ - r)*sizeof(__i_node*)); 482} 483 484_LIBCPP_END_NAMESPACE_STD 485