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 10227825Stheraven#define _LIBCPP_DEBUG2 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()); 121227825Stheraven __i_node* i = __insert_iterator(__i); 122227825Stheraven const char* errmsg = 123227825Stheraven "Container constructed in a translation unit with debug mode disabled." 124227825Stheraven " But it is being used in a translation unit with debug mode enabled." 125227825Stheraven " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1"; 126227825Stheraven _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg); 127232950Stheraven size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 128227825Stheraven __c_node* c = __cbeg_[hc]; 129227825Stheraven _LIBCPP_ASSERT(c != nullptr, errmsg); 130227825Stheraven while (c->__c_ != __c) 131227825Stheraven { 132227825Stheraven c = c->__next_; 133227825Stheraven _LIBCPP_ASSERT(c != nullptr, errmsg); 134227825Stheraven } 135227825Stheraven c->__add(i); 136227825Stheraven i->__c_ = c; 137227825Stheraven} 138227825Stheraven 139227825Stheraven__c_node* 140227825Stheraven__libcpp_db::__insert_c(void* __c) 141227825Stheraven{ 142227825Stheraven WLock _(mut()); 143232950Stheraven if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 144227825Stheraven { 145232950Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 146253159Stheraven __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*))); 147227825Stheraven if (cbeg == nullptr) 148241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 149227825Stheraven throw bad_alloc(); 150241903Sdim#else 151241903Sdim abort(); 152241903Sdim#endif 153227825Stheraven for (__c_node** p = __cbeg_; p != __cend_; ++p) 154227825Stheraven { 155227825Stheraven __c_node* q = *p; 156227825Stheraven while (q != nullptr) 157227825Stheraven { 158227825Stheraven size_t h = hash<void*>()(q->__c_) % nc; 159227825Stheraven __c_node* r = q->__next_; 160227825Stheraven q->__next_ = cbeg[h]; 161227825Stheraven cbeg[h] = q; 162227825Stheraven q = r; 163227825Stheraven } 164227825Stheraven } 165227825Stheraven free(__cbeg_); 166227825Stheraven __cbeg_ = cbeg; 167227825Stheraven __cend_ = __cbeg_ + nc; 168227825Stheraven } 169232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 170227825Stheraven __c_node* p = __cbeg_[hc]; 171253159Stheraven __c_node* r = __cbeg_[hc] = 172253159Stheraven static_cast<__c_node*>(malloc(sizeof(__c_node))); 173227825Stheraven if (__cbeg_[hc] == nullptr) 174241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 175227825Stheraven throw bad_alloc(); 176241903Sdim#else 177241903Sdim abort(); 178241903Sdim#endif 179227825Stheraven r->__c_ = __c; 180227825Stheraven r->__next_ = p; 181227825Stheraven ++__csz_; 182227825Stheraven return r; 183227825Stheraven} 184227825Stheraven 185227825Stheravenvoid 186227825Stheraven__libcpp_db::__erase_i(void* __i) 187227825Stheraven{ 188227825Stheraven WLock _(mut()); 189227825Stheraven if (__ibeg_ != __iend_) 190227825Stheraven { 191232950Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 192227825Stheraven __i_node* p = __ibeg_[hi]; 193227825Stheraven if (p != nullptr) 194227825Stheraven { 195227825Stheraven __i_node* q = nullptr; 196227825Stheraven while (p->__i_ != __i) 197227825Stheraven { 198227825Stheraven q = p; 199227825Stheraven p = p->__next_; 200227825Stheraven if (p == nullptr) 201227825Stheraven return; 202227825Stheraven } 203227825Stheraven if (q == nullptr) 204227825Stheraven __ibeg_[hi] = p->__next_; 205227825Stheraven else 206227825Stheraven q->__next_ = p->__next_; 207227825Stheraven __c_node* c = p->__c_; 208227825Stheraven free(p); 209227825Stheraven --__isz_; 210227825Stheraven if (c != nullptr) 211227825Stheraven c->__remove(p); 212227825Stheraven } 213227825Stheraven } 214227825Stheraven} 215227825Stheraven 216227825Stheravenvoid 217227825Stheraven__libcpp_db::__invalidate_all(void* __c) 218227825Stheraven{ 219227825Stheraven WLock _(mut()); 220232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 221227825Stheraven __c_node* p = __cbeg_[hc]; 222227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A"); 223227825Stheraven while (p->__c_ != __c) 224227825Stheraven { 225227825Stheraven p = p->__next_; 226227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B"); 227227825Stheraven } 228227825Stheraven while (p->end_ != p->beg_) 229227825Stheraven { 230227825Stheraven --p->end_; 231227825Stheraven (*p->end_)->__c_ = nullptr; 232227825Stheraven } 233227825Stheraven} 234227825Stheraven 235227825Stheraven__c_node* 236227825Stheraven__libcpp_db::__find_c_and_lock(void* __c) const 237227825Stheraven{ 238227825Stheraven mut().lock(); 239232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 240227825Stheraven __c_node* p = __cbeg_[hc]; 241227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A"); 242227825Stheraven while (p->__c_ != __c) 243227825Stheraven { 244227825Stheraven p = p->__next_; 245227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B"); 246227825Stheraven } 247227825Stheraven return p; 248227825Stheraven} 249227825Stheraven 250227825Stheraven__c_node* 251227825Stheraven__libcpp_db::__find_c(void* __c) const 252227825Stheraven{ 253232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 254227825Stheraven __c_node* p = __cbeg_[hc]; 255227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 256227825Stheraven while (p->__c_ != __c) 257227825Stheraven { 258227825Stheraven p = p->__next_; 259227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 260227825Stheraven } 261227825Stheraven return p; 262227825Stheraven} 263227825Stheraven 264227825Stheravenvoid 265227825Stheraven__libcpp_db::unlock() const 266227825Stheraven{ 267227825Stheraven mut().unlock(); 268227825Stheraven} 269227825Stheraven 270227825Stheravenvoid 271227825Stheraven__libcpp_db::__erase_c(void* __c) 272227825Stheraven{ 273227825Stheraven WLock _(mut()); 274232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 275227825Stheraven __c_node* p = __cbeg_[hc]; 276227825Stheraven __c_node* q = nullptr; 277227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 278227825Stheraven while (p->__c_ != __c) 279227825Stheraven { 280227825Stheraven q = p; 281227825Stheraven p = p->__next_; 282227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 283227825Stheraven } 284227825Stheraven if (q == nullptr) 285227825Stheraven __cbeg_[hc] = p->__next_; 286227825Stheraven else 287227825Stheraven q->__next_ = p->__next_; 288227825Stheraven while (p->end_ != p->beg_) 289227825Stheraven { 290227825Stheraven --p->end_; 291227825Stheraven (*p->end_)->__c_ = nullptr; 292227825Stheraven } 293227825Stheraven free(p->beg_); 294227825Stheraven free(p); 295227825Stheraven --__csz_; 296227825Stheraven} 297227825Stheraven 298227825Stheravenvoid 299227825Stheraven__libcpp_db::__iterator_copy(void* __i, const void* __i0) 300227825Stheraven{ 301227825Stheraven WLock _(mut()); 302227825Stheraven __i_node* i = __find_iterator(__i); 303227825Stheraven __i_node* i0 = __find_iterator(__i0); 304227825Stheraven __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 305249998Sdim if (i == nullptr && i0 != nullptr) 306227825Stheraven i = __insert_iterator(__i); 307227825Stheraven __c_node* c = i != nullptr ? i->__c_ : nullptr; 308227825Stheraven if (c != c0) 309227825Stheraven { 310227825Stheraven if (c != nullptr) 311227825Stheraven c->__remove(i); 312227825Stheraven if (i != nullptr) 313227825Stheraven { 314227825Stheraven i->__c_ = nullptr; 315227825Stheraven if (c0 != nullptr) 316227825Stheraven { 317227825Stheraven i->__c_ = c0; 318227825Stheraven i->__c_->__add(i); 319227825Stheraven } 320227825Stheraven } 321227825Stheraven } 322227825Stheraven} 323227825Stheraven 324227825Stheravenbool 325227825Stheraven__libcpp_db::__dereferenceable(const void* __i) const 326227825Stheraven{ 327227825Stheraven RLock _(mut()); 328227825Stheraven __i_node* i = __find_iterator(__i); 329227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 330227825Stheraven} 331227825Stheraven 332227825Stheravenbool 333227825Stheraven__libcpp_db::__decrementable(const void* __i) const 334227825Stheraven{ 335227825Stheraven RLock _(mut()); 336227825Stheraven __i_node* i = __find_iterator(__i); 337227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 338227825Stheraven} 339227825Stheraven 340227825Stheravenbool 341227825Stheraven__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 342227825Stheraven{ 343227825Stheraven RLock _(mut()); 344227825Stheraven __i_node* i = __find_iterator(__i); 345227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 346227825Stheraven} 347227825Stheraven 348227825Stheravenbool 349227825Stheraven__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 350227825Stheraven{ 351227825Stheraven RLock _(mut()); 352227825Stheraven __i_node* i = __find_iterator(__i); 353227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 354227825Stheraven} 355227825Stheraven 356227825Stheravenbool 357227825Stheraven__libcpp_db::__comparable(const void* __i, const void* __j) const 358227825Stheraven{ 359227825Stheraven RLock _(mut()); 360227825Stheraven __i_node* i = __find_iterator(__i); 361227825Stheraven __i_node* j = __find_iterator(__j); 362227825Stheraven __c_node* ci = i != nullptr ? i->__c_ : nullptr; 363227825Stheraven __c_node* cj = j != nullptr ? j->__c_ : nullptr; 364227825Stheraven return ci != nullptr && ci == cj; 365227825Stheraven} 366227825Stheraven 367227825Stheravenvoid 368227825Stheraven__libcpp_db::swap(void* c1, void* c2) 369227825Stheraven{ 370227825Stheraven WLock _(mut()); 371232950Stheraven size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); 372227825Stheraven __c_node* p1 = __cbeg_[hc]; 373227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 374227825Stheraven while (p1->__c_ != c1) 375227825Stheraven { 376227825Stheraven p1 = p1->__next_; 377227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 378227825Stheraven } 379232950Stheraven hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); 380227825Stheraven __c_node* p2 = __cbeg_[hc]; 381227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 382227825Stheraven while (p2->__c_ != c2) 383227825Stheraven { 384227825Stheraven p2 = p2->__next_; 385227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 386227825Stheraven } 387227825Stheraven std::swap(p1->beg_, p2->beg_); 388227825Stheraven std::swap(p1->end_, p2->end_); 389227825Stheraven std::swap(p1->cap_, p2->cap_); 390227825Stheraven for (__i_node** p = p1->beg_; p != p1->end_; ++p) 391227825Stheraven (*p)->__c_ = p1; 392227825Stheraven for (__i_node** p = p2->beg_; p != p2->end_; ++p) 393227825Stheraven (*p)->__c_ = p2; 394227825Stheraven} 395227825Stheraven 396227825Stheravenvoid 397227825Stheraven__libcpp_db::__insert_i(void* __i) 398227825Stheraven{ 399227825Stheraven WLock _(mut()); 400227825Stheraven __insert_iterator(__i); 401227825Stheraven} 402227825Stheraven 403227825Stheravenvoid 404227825Stheraven__c_node::__add(__i_node* i) 405227825Stheraven{ 406227825Stheraven if (end_ == cap_) 407227825Stheraven { 408232950Stheraven size_t nc = 2*static_cast<size_t>(cap_ - beg_); 409227825Stheraven if (nc == 0) 410227825Stheraven nc = 1; 411253159Stheraven __i_node** beg = 412253159Stheraven static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); 413227825Stheraven if (beg == nullptr) 414241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 415227825Stheraven throw bad_alloc(); 416241903Sdim#else 417241903Sdim abort(); 418241903Sdim#endif 419227825Stheraven if (nc > 1) 420227825Stheraven memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 421227825Stheraven free(beg_); 422227825Stheraven beg_ = beg; 423227825Stheraven end_ = beg_ + nc/2; 424227825Stheraven cap_ = beg_ + nc; 425227825Stheraven } 426227825Stheraven *end_++ = i; 427227825Stheraven} 428227825Stheraven 429227825Stheraven// private api 430227825Stheraven 431227825Stheraven_LIBCPP_HIDDEN 432227825Stheraven__i_node* 433227825Stheraven__libcpp_db::__insert_iterator(void* __i) 434227825Stheraven{ 435232950Stheraven if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 436227825Stheraven { 437232950Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 438253159Stheraven __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*))); 439227825Stheraven if (ibeg == nullptr) 440241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 441227825Stheraven throw bad_alloc(); 442241903Sdim#else 443241903Sdim abort(); 444241903Sdim#endif 445227825Stheraven for (__i_node** p = __ibeg_; p != __iend_; ++p) 446227825Stheraven { 447227825Stheraven __i_node* q = *p; 448227825Stheraven while (q != nullptr) 449227825Stheraven { 450227825Stheraven size_t h = hash<void*>()(q->__i_) % nc; 451227825Stheraven __i_node* r = q->__next_; 452227825Stheraven q->__next_ = ibeg[h]; 453227825Stheraven ibeg[h] = q; 454227825Stheraven q = r; 455227825Stheraven } 456227825Stheraven } 457227825Stheraven free(__ibeg_); 458227825Stheraven __ibeg_ = ibeg; 459227825Stheraven __iend_ = __ibeg_ + nc; 460227825Stheraven } 461232950Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 462227825Stheraven __i_node* p = __ibeg_[hi]; 463253159Stheraven __i_node* r = __ibeg_[hi] = 464253159Stheraven static_cast<__i_node*>(malloc(sizeof(__i_node))); 465227825Stheraven if (r == nullptr) 466241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 467227825Stheraven throw bad_alloc(); 468241903Sdim#else 469241903Sdim abort(); 470241903Sdim#endif 471227825Stheraven ::new(r) __i_node(__i, p, nullptr); 472227825Stheraven ++__isz_; 473227825Stheraven return r; 474227825Stheraven} 475227825Stheraven 476227825Stheraven_LIBCPP_HIDDEN 477227825Stheraven__i_node* 478227825Stheraven__libcpp_db::__find_iterator(const void* __i) const 479227825Stheraven{ 480227825Stheraven __i_node* r = nullptr; 481227825Stheraven if (__ibeg_ != __iend_) 482227825Stheraven { 483232950Stheraven size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 484227825Stheraven for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 485227825Stheraven { 486227825Stheraven if (nd->__i_ == __i) 487227825Stheraven { 488227825Stheraven r = nd; 489227825Stheraven break; 490227825Stheraven } 491227825Stheraven } 492227825Stheraven } 493227825Stheraven return r; 494227825Stheraven} 495227825Stheraven 496227825Stheraven_LIBCPP_HIDDEN 497227825Stheravenvoid 498227825Stheraven__c_node::__remove(__i_node* p) 499227825Stheraven{ 500227825Stheraven __i_node** r = find(beg_, end_, p); 501227825Stheraven _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 502227825Stheraven if (--end_ != r) 503232950Stheraven memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 504227825Stheraven} 505227825Stheraven 506227825Stheraven_LIBCPP_END_NAMESPACE_STD 507