1227825Stheraven//===-------------------------- debug.cpp ---------------------------------===// 2227825Stheraven// 3227825Stheraven// The LLVM Compiler Infrastructure 4227825Stheraven// 5227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 6227825Stheraven// Source Licenses. See LICENSE.TXT for details. 7227825Stheraven// 8227825Stheraven//===----------------------------------------------------------------------===// 9227825Stheraven 10262801Sdim#define _LIBCPP_DEBUG 1 11227825Stheraven#include "__config" 12227825Stheraven#include "__debug" 13227825Stheraven#include "functional" 14227825Stheraven#include "algorithm" 15227825Stheraven#include "__hash_table" 16227825Stheraven#include "mutex" 17227825Stheraven 18227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 19227825Stheraven 20249998Sdim_LIBCPP_FUNC_VIS 21227825Stheraven__libcpp_db* 22227825Stheraven__get_db() 23227825Stheraven{ 24227825Stheraven static __libcpp_db db; 25227825Stheraven return &db; 26246487Stheraven} 27227825Stheraven 28249998Sdim_LIBCPP_FUNC_VIS 29227825Stheravenconst __libcpp_db* 30227825Stheraven__get_const_db() 31227825Stheraven{ 32227825Stheraven return __get_db(); 33227825Stheraven} 34227825Stheraven 35227825Stheravennamespace 36227825Stheraven{ 37227825Stheraven 38227825Stheraventypedef mutex mutex_type; 39227825Stheraventypedef lock_guard<mutex_type> WLock; 40227825Stheraventypedef lock_guard<mutex_type> RLock; 41227825Stheraven 42227825Stheravenmutex_type& 43227825Stheravenmut() 44227825Stheraven{ 45227825Stheraven static mutex_type m; 46227825Stheraven return m; 47227825Stheraven} 48227825Stheraven 49227825Stheraven} // unnamed namespace 50227825Stheraven 51227825Stheraven__i_node::~__i_node() 52227825Stheraven{ 53227825Stheraven if (__next_) 54227825Stheraven { 55227825Stheraven __next_->~__i_node(); 56227825Stheraven free(__next_); 57227825Stheraven } 58227825Stheraven} 59227825Stheraven 60227825Stheraven__c_node::~__c_node() 61227825Stheraven{ 62227825Stheraven free(beg_); 63227825Stheraven if (__next_) 64227825Stheraven { 65227825Stheraven __next_->~__c_node(); 66227825Stheraven free(__next_); 67227825Stheraven } 68227825Stheraven} 69227825Stheraven 70227825Stheraven__libcpp_db::__libcpp_db() 71227825Stheraven : __cbeg_(nullptr), 72227825Stheraven __cend_(nullptr), 73227825Stheraven __csz_(0), 74227825Stheraven __ibeg_(nullptr), 75227825Stheraven __iend_(nullptr), 76227825Stheraven __isz_(0) 77227825Stheraven{ 78227825Stheraven} 79227825Stheraven 80227825Stheraven__libcpp_db::~__libcpp_db() 81227825Stheraven{ 82227825Stheraven if (__cbeg_) 83227825Stheraven { 84227825Stheraven for (__c_node** p = __cbeg_; p != __cend_; ++p) 85227825Stheraven { 86227825Stheraven if (*p != nullptr) 87227825Stheraven { 88227825Stheraven (*p)->~__c_node(); 89227825Stheraven free(*p); 90227825Stheraven } 91227825Stheraven } 92227825Stheraven free(__cbeg_); 93227825Stheraven } 94227825Stheraven if (__ibeg_) 95227825Stheraven { 96227825Stheraven for (__i_node** p = __ibeg_; p != __iend_; ++p) 97227825Stheraven { 98227825Stheraven if (*p != nullptr) 99227825Stheraven { 100227825Stheraven (*p)->~__i_node(); 101227825Stheraven free(*p); 102227825Stheraven } 103227825Stheraven } 104227825Stheraven free(__ibeg_); 105227825Stheraven } 106227825Stheraven} 107227825Stheraven 108227825Stheravenvoid* 109227825Stheraven__libcpp_db::__find_c_from_i(void* __i) const 110227825Stheraven{ 111227825Stheraven RLock _(mut()); 112227825Stheraven __i_node* i = __find_iterator(__i); 113249998Sdim _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database."); 114227825Stheraven return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; 115227825Stheraven} 116227825Stheraven 117227825Stheravenvoid 118227825Stheraven__libcpp_db::__insert_ic(void* __i, const void* __c) 119227825Stheraven{ 120227825Stheraven WLock _(mut()); 121262801Sdim if (__cbeg_ == __cend_) 122262801Sdim return; 123232950Stheraven size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 124227825Stheraven __c_node* c = __cbeg_[hc]; 125262801Sdim if (c == nullptr) 126262801Sdim return; 127227825Stheraven while (c->__c_ != __c) 128227825Stheraven { 129227825Stheraven c = c->__next_; 130262801Sdim if (c == nullptr) 131262801Sdim return; 132227825Stheraven } 133262801Sdim __i_node* i = __insert_iterator(__i); 134227825Stheraven c->__add(i); 135227825Stheraven i->__c_ = c; 136227825Stheraven} 137227825Stheraven 138227825Stheraven__c_node* 139227825Stheraven__libcpp_db::__insert_c(void* __c) 140227825Stheraven{ 141227825Stheraven WLock _(mut()); 142232950Stheraven if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 143227825Stheraven { 144232950Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 145253159Stheraven __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*))); 146227825Stheraven if (cbeg == nullptr) 147241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 148227825Stheraven throw bad_alloc(); 149241903Sdim#else 150241903Sdim abort(); 151241903Sdim#endif 152227825Stheraven for (__c_node** p = __cbeg_; p != __cend_; ++p) 153227825Stheraven { 154227825Stheraven __c_node* q = *p; 155227825Stheraven while (q != nullptr) 156227825Stheraven { 157227825Stheraven size_t h = hash<void*>()(q->__c_) % nc; 158227825Stheraven __c_node* r = q->__next_; 159227825Stheraven q->__next_ = cbeg[h]; 160227825Stheraven cbeg[h] = q; 161227825Stheraven q = r; 162227825Stheraven } 163227825Stheraven } 164227825Stheraven free(__cbeg_); 165227825Stheraven __cbeg_ = cbeg; 166227825Stheraven __cend_ = __cbeg_ + nc; 167227825Stheraven } 168232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 169227825Stheraven __c_node* p = __cbeg_[hc]; 170253159Stheraven __c_node* r = __cbeg_[hc] = 171253159Stheraven static_cast<__c_node*>(malloc(sizeof(__c_node))); 172227825Stheraven if (__cbeg_[hc] == nullptr) 173241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 174227825Stheraven throw bad_alloc(); 175241903Sdim#else 176241903Sdim abort(); 177241903Sdim#endif 178227825Stheraven r->__c_ = __c; 179227825Stheraven r->__next_ = p; 180227825Stheraven ++__csz_; 181227825Stheraven return r; 182227825Stheraven} 183227825Stheraven 184227825Stheravenvoid 185227825Stheraven__libcpp_db::__erase_i(void* __i) 186227825Stheraven{ 187227825Stheraven WLock _(mut()); 188227825Stheraven if (__ibeg_ != __iend_) 189227825Stheraven { 190232950Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 191227825Stheraven __i_node* p = __ibeg_[hi]; 192227825Stheraven if (p != nullptr) 193227825Stheraven { 194227825Stheraven __i_node* q = nullptr; 195227825Stheraven while (p->__i_ != __i) 196227825Stheraven { 197227825Stheraven q = p; 198227825Stheraven p = p->__next_; 199227825Stheraven if (p == nullptr) 200227825Stheraven return; 201227825Stheraven } 202227825Stheraven if (q == nullptr) 203227825Stheraven __ibeg_[hi] = p->__next_; 204227825Stheraven else 205227825Stheraven q->__next_ = p->__next_; 206227825Stheraven __c_node* c = p->__c_; 207227825Stheraven free(p); 208227825Stheraven --__isz_; 209227825Stheraven if (c != nullptr) 210227825Stheraven c->__remove(p); 211227825Stheraven } 212227825Stheraven } 213227825Stheraven} 214227825Stheraven 215227825Stheravenvoid 216227825Stheraven__libcpp_db::__invalidate_all(void* __c) 217227825Stheraven{ 218227825Stheraven WLock _(mut()); 219262801Sdim if (__cend_ != __cbeg_) 220227825Stheraven { 221262801Sdim size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 222262801Sdim __c_node* p = __cbeg_[hc]; 223262801Sdim if (p == nullptr) 224262801Sdim return; 225262801Sdim while (p->__c_ != __c) 226262801Sdim { 227262801Sdim p = p->__next_; 228262801Sdim if (p == nullptr) 229262801Sdim return; 230262801Sdim } 231262801Sdim while (p->end_ != p->beg_) 232262801Sdim { 233262801Sdim --p->end_; 234262801Sdim (*p->end_)->__c_ = nullptr; 235262801Sdim } 236227825Stheraven } 237227825Stheraven} 238227825Stheraven 239227825Stheraven__c_node* 240227825Stheraven__libcpp_db::__find_c_and_lock(void* __c) const 241227825Stheraven{ 242227825Stheraven mut().lock(); 243262801Sdim if (__cend_ == __cbeg_) 244262801Sdim { 245262801Sdim mut().unlock(); 246262801Sdim return nullptr; 247262801Sdim } 248232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 249227825Stheraven __c_node* p = __cbeg_[hc]; 250262801Sdim if (p == nullptr) 251262801Sdim { 252262801Sdim mut().unlock(); 253262801Sdim return nullptr; 254262801Sdim } 255227825Stheraven while (p->__c_ != __c) 256227825Stheraven { 257227825Stheraven p = p->__next_; 258262801Sdim if (p == nullptr) 259262801Sdim { 260262801Sdim mut().unlock(); 261262801Sdim return nullptr; 262262801Sdim } 263227825Stheraven } 264227825Stheraven return p; 265227825Stheraven} 266227825Stheraven 267227825Stheraven__c_node* 268227825Stheraven__libcpp_db::__find_c(void* __c) const 269227825Stheraven{ 270232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 271227825Stheraven __c_node* p = __cbeg_[hc]; 272227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 273227825Stheraven while (p->__c_ != __c) 274227825Stheraven { 275227825Stheraven p = p->__next_; 276227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 277227825Stheraven } 278227825Stheraven return p; 279227825Stheraven} 280227825Stheraven 281227825Stheravenvoid 282227825Stheraven__libcpp_db::unlock() const 283227825Stheraven{ 284227825Stheraven mut().unlock(); 285227825Stheraven} 286227825Stheraven 287227825Stheravenvoid 288227825Stheraven__libcpp_db::__erase_c(void* __c) 289227825Stheraven{ 290227825Stheraven WLock _(mut()); 291262801Sdim if (__cend_ != __cbeg_) 292227825Stheraven { 293262801Sdim size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 294262801Sdim __c_node* p = __cbeg_[hc]; 295262801Sdim if (p == nullptr) 296262801Sdim return; 297262801Sdim __c_node* q = nullptr; 298262801Sdim _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 299262801Sdim while (p->__c_ != __c) 300262801Sdim { 301262801Sdim q = p; 302262801Sdim p = p->__next_; 303262801Sdim if (p == nullptr) 304262801Sdim return; 305262801Sdim _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 306262801Sdim } 307262801Sdim if (q == nullptr) 308262801Sdim __cbeg_[hc] = p->__next_; 309262801Sdim else 310262801Sdim q->__next_ = p->__next_; 311262801Sdim while (p->end_ != p->beg_) 312262801Sdim { 313262801Sdim --p->end_; 314262801Sdim (*p->end_)->__c_ = nullptr; 315262801Sdim } 316262801Sdim free(p->beg_); 317262801Sdim free(p); 318262801Sdim --__csz_; 319227825Stheraven } 320227825Stheraven} 321227825Stheraven 322227825Stheravenvoid 323227825Stheraven__libcpp_db::__iterator_copy(void* __i, const void* __i0) 324227825Stheraven{ 325227825Stheraven WLock _(mut()); 326227825Stheraven __i_node* i = __find_iterator(__i); 327227825Stheraven __i_node* i0 = __find_iterator(__i0); 328227825Stheraven __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 329249998Sdim if (i == nullptr && i0 != nullptr) 330227825Stheraven i = __insert_iterator(__i); 331227825Stheraven __c_node* c = i != nullptr ? i->__c_ : nullptr; 332227825Stheraven if (c != c0) 333227825Stheraven { 334227825Stheraven if (c != nullptr) 335227825Stheraven c->__remove(i); 336227825Stheraven if (i != nullptr) 337227825Stheraven { 338227825Stheraven i->__c_ = nullptr; 339227825Stheraven if (c0 != nullptr) 340227825Stheraven { 341227825Stheraven i->__c_ = c0; 342227825Stheraven i->__c_->__add(i); 343227825Stheraven } 344227825Stheraven } 345227825Stheraven } 346227825Stheraven} 347227825Stheraven 348227825Stheravenbool 349227825Stheraven__libcpp_db::__dereferenceable(const void* __i) const 350227825Stheraven{ 351227825Stheraven RLock _(mut()); 352227825Stheraven __i_node* i = __find_iterator(__i); 353227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 354227825Stheraven} 355227825Stheraven 356227825Stheravenbool 357227825Stheraven__libcpp_db::__decrementable(const void* __i) const 358227825Stheraven{ 359227825Stheraven RLock _(mut()); 360227825Stheraven __i_node* i = __find_iterator(__i); 361227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 362227825Stheraven} 363227825Stheraven 364227825Stheravenbool 365227825Stheraven__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 366227825Stheraven{ 367227825Stheraven RLock _(mut()); 368227825Stheraven __i_node* i = __find_iterator(__i); 369227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 370227825Stheraven} 371227825Stheraven 372227825Stheravenbool 373227825Stheraven__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 374227825Stheraven{ 375227825Stheraven RLock _(mut()); 376227825Stheraven __i_node* i = __find_iterator(__i); 377227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 378227825Stheraven} 379227825Stheraven 380227825Stheravenbool 381262801Sdim__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const 382227825Stheraven{ 383227825Stheraven RLock _(mut()); 384227825Stheraven __i_node* i = __find_iterator(__i); 385227825Stheraven __i_node* j = __find_iterator(__j); 386227825Stheraven __c_node* ci = i != nullptr ? i->__c_ : nullptr; 387227825Stheraven __c_node* cj = j != nullptr ? j->__c_ : nullptr; 388227825Stheraven return ci != nullptr && ci == cj; 389227825Stheraven} 390227825Stheraven 391227825Stheravenvoid 392227825Stheraven__libcpp_db::swap(void* c1, void* c2) 393227825Stheraven{ 394227825Stheraven WLock _(mut()); 395232950Stheraven size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); 396227825Stheraven __c_node* p1 = __cbeg_[hc]; 397227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 398227825Stheraven while (p1->__c_ != c1) 399227825Stheraven { 400227825Stheraven p1 = p1->__next_; 401227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 402227825Stheraven } 403232950Stheraven hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); 404227825Stheraven __c_node* p2 = __cbeg_[hc]; 405227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 406227825Stheraven while (p2->__c_ != c2) 407227825Stheraven { 408227825Stheraven p2 = p2->__next_; 409227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 410227825Stheraven } 411227825Stheraven std::swap(p1->beg_, p2->beg_); 412227825Stheraven std::swap(p1->end_, p2->end_); 413227825Stheraven std::swap(p1->cap_, p2->cap_); 414227825Stheraven for (__i_node** p = p1->beg_; p != p1->end_; ++p) 415227825Stheraven (*p)->__c_ = p1; 416227825Stheraven for (__i_node** p = p2->beg_; p != p2->end_; ++p) 417227825Stheraven (*p)->__c_ = p2; 418227825Stheraven} 419227825Stheraven 420227825Stheravenvoid 421227825Stheraven__libcpp_db::__insert_i(void* __i) 422227825Stheraven{ 423227825Stheraven WLock _(mut()); 424227825Stheraven __insert_iterator(__i); 425227825Stheraven} 426227825Stheraven 427227825Stheravenvoid 428227825Stheraven__c_node::__add(__i_node* i) 429227825Stheraven{ 430227825Stheraven if (end_ == cap_) 431227825Stheraven { 432232950Stheraven size_t nc = 2*static_cast<size_t>(cap_ - beg_); 433227825Stheraven if (nc == 0) 434227825Stheraven nc = 1; 435253159Stheraven __i_node** beg = 436253159Stheraven static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); 437227825Stheraven if (beg == nullptr) 438241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 439227825Stheraven throw bad_alloc(); 440241903Sdim#else 441241903Sdim abort(); 442241903Sdim#endif 443227825Stheraven if (nc > 1) 444227825Stheraven memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 445227825Stheraven free(beg_); 446227825Stheraven beg_ = beg; 447227825Stheraven end_ = beg_ + nc/2; 448227825Stheraven cap_ = beg_ + nc; 449227825Stheraven } 450227825Stheraven *end_++ = i; 451227825Stheraven} 452227825Stheraven 453227825Stheraven// private api 454227825Stheraven 455227825Stheraven_LIBCPP_HIDDEN 456227825Stheraven__i_node* 457227825Stheraven__libcpp_db::__insert_iterator(void* __i) 458227825Stheraven{ 459232950Stheraven if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 460227825Stheraven { 461232950Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 462253159Stheraven __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*))); 463227825Stheraven if (ibeg == nullptr) 464241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 465227825Stheraven throw bad_alloc(); 466241903Sdim#else 467241903Sdim abort(); 468241903Sdim#endif 469227825Stheraven for (__i_node** p = __ibeg_; p != __iend_; ++p) 470227825Stheraven { 471227825Stheraven __i_node* q = *p; 472227825Stheraven while (q != nullptr) 473227825Stheraven { 474227825Stheraven size_t h = hash<void*>()(q->__i_) % nc; 475227825Stheraven __i_node* r = q->__next_; 476227825Stheraven q->__next_ = ibeg[h]; 477227825Stheraven ibeg[h] = q; 478227825Stheraven q = r; 479227825Stheraven } 480227825Stheraven } 481227825Stheraven free(__ibeg_); 482227825Stheraven __ibeg_ = ibeg; 483227825Stheraven __iend_ = __ibeg_ + nc; 484227825Stheraven } 485232950Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 486227825Stheraven __i_node* p = __ibeg_[hi]; 487253159Stheraven __i_node* r = __ibeg_[hi] = 488253159Stheraven static_cast<__i_node*>(malloc(sizeof(__i_node))); 489227825Stheraven if (r == nullptr) 490241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 491227825Stheraven throw bad_alloc(); 492241903Sdim#else 493241903Sdim abort(); 494241903Sdim#endif 495227825Stheraven ::new(r) __i_node(__i, p, nullptr); 496227825Stheraven ++__isz_; 497227825Stheraven return r; 498227825Stheraven} 499227825Stheraven 500227825Stheraven_LIBCPP_HIDDEN 501227825Stheraven__i_node* 502227825Stheraven__libcpp_db::__find_iterator(const void* __i) const 503227825Stheraven{ 504227825Stheraven __i_node* r = nullptr; 505227825Stheraven if (__ibeg_ != __iend_) 506227825Stheraven { 507232950Stheraven size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 508227825Stheraven for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 509227825Stheraven { 510227825Stheraven if (nd->__i_ == __i) 511227825Stheraven { 512227825Stheraven r = nd; 513227825Stheraven break; 514227825Stheraven } 515227825Stheraven } 516227825Stheraven } 517227825Stheraven return r; 518227825Stheraven} 519227825Stheraven 520227825Stheraven_LIBCPP_HIDDEN 521227825Stheravenvoid 522227825Stheraven__c_node::__remove(__i_node* p) 523227825Stheraven{ 524227825Stheraven __i_node** r = find(beg_, end_, p); 525227825Stheraven _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 526227825Stheraven if (--end_ != r) 527232950Stheraven memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 528227825Stheraven} 529227825Stheraven 530227825Stheraven_LIBCPP_END_NAMESPACE_STD 531