debug.cpp revision 227825
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 20227825Stheraven_LIBCPP_VISIBLE 21227825Stheraven__libcpp_db* 22227825Stheraven__get_db() 23227825Stheraven{ 24227825Stheraven static __libcpp_db db; 25227825Stheraven return &db; 26227825Stheraven}; 27227825Stheraven 28227825Stheraven_LIBCPP_VISIBLE 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); 113227825Stheraven _LIBCPP_ASSERT(i != nullptr, "iterator constructed in translation unit with debug mode not enabled." 114227825Stheraven " #define _LIBCPP_DEBUG2 1 for that translation unit."); 115227825Stheraven return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; 116227825Stheraven} 117227825Stheraven 118227825Stheravenvoid 119227825Stheraven__libcpp_db::__insert_ic(void* __i, const void* __c) 120227825Stheraven{ 121227825Stheraven WLock _(mut()); 122227825Stheraven __i_node* i = __insert_iterator(__i); 123227825Stheraven const char* errmsg = 124227825Stheraven "Container constructed in a translation unit with debug mode disabled." 125227825Stheraven " But it is being used in a translation unit with debug mode enabled." 126227825Stheraven " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1"; 127227825Stheraven _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg); 128227825Stheraven size_t hc = hash<const void*>()(__c) % (__cend_ - __cbeg_); 129227825Stheraven __c_node* c = __cbeg_[hc]; 130227825Stheraven _LIBCPP_ASSERT(c != nullptr, errmsg); 131227825Stheraven while (c->__c_ != __c) 132227825Stheraven { 133227825Stheraven c = c->__next_; 134227825Stheraven _LIBCPP_ASSERT(c != nullptr, errmsg); 135227825Stheraven } 136227825Stheraven c->__add(i); 137227825Stheraven i->__c_ = c; 138227825Stheraven} 139227825Stheraven 140227825Stheraven__c_node* 141227825Stheraven__libcpp_db::__insert_c(void* __c) 142227825Stheraven{ 143227825Stheraven WLock _(mut()); 144227825Stheraven if (__csz_ + 1 > __cend_ - __cbeg_) 145227825Stheraven { 146227825Stheraven size_t nc = __next_prime(2*(__cend_ - __cbeg_) + 1); 147227825Stheraven __c_node** cbeg = (__c_node**)calloc(nc, sizeof(void*)); 148227825Stheraven if (cbeg == nullptr) 149227825Stheraven throw bad_alloc(); 150227825Stheraven for (__c_node** p = __cbeg_; p != __cend_; ++p) 151227825Stheraven { 152227825Stheraven __c_node* q = *p; 153227825Stheraven while (q != nullptr) 154227825Stheraven { 155227825Stheraven size_t h = hash<void*>()(q->__c_) % nc; 156227825Stheraven __c_node* r = q->__next_; 157227825Stheraven q->__next_ = cbeg[h]; 158227825Stheraven cbeg[h] = q; 159227825Stheraven q = r; 160227825Stheraven } 161227825Stheraven } 162227825Stheraven free(__cbeg_); 163227825Stheraven __cbeg_ = cbeg; 164227825Stheraven __cend_ = __cbeg_ + nc; 165227825Stheraven } 166227825Stheraven size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 167227825Stheraven __c_node* p = __cbeg_[hc]; 168227825Stheraven __c_node* r = __cbeg_[hc] = (__c_node*)malloc(sizeof(__c_node)); 169227825Stheraven if (__cbeg_[hc] == nullptr) 170227825Stheraven throw bad_alloc(); 171227825Stheraven r->__c_ = __c; 172227825Stheraven r->__next_ = p; 173227825Stheraven ++__csz_; 174227825Stheraven return r; 175227825Stheraven} 176227825Stheraven 177227825Stheravenvoid 178227825Stheraven__libcpp_db::__erase_i(void* __i) 179227825Stheraven{ 180227825Stheraven WLock _(mut()); 181227825Stheraven if (__ibeg_ != __iend_) 182227825Stheraven { 183227825Stheraven size_t hi = hash<void*>()(__i) % (__iend_ - __ibeg_); 184227825Stheraven __i_node* p = __ibeg_[hi]; 185227825Stheraven if (p != nullptr) 186227825Stheraven { 187227825Stheraven __i_node* q = nullptr; 188227825Stheraven while (p->__i_ != __i) 189227825Stheraven { 190227825Stheraven q = p; 191227825Stheraven p = p->__next_; 192227825Stheraven if (p == nullptr) 193227825Stheraven return; 194227825Stheraven } 195227825Stheraven if (q == nullptr) 196227825Stheraven __ibeg_[hi] = p->__next_; 197227825Stheraven else 198227825Stheraven q->__next_ = p->__next_; 199227825Stheraven __c_node* c = p->__c_; 200227825Stheraven free(p); 201227825Stheraven --__isz_; 202227825Stheraven if (c != nullptr) 203227825Stheraven c->__remove(p); 204227825Stheraven } 205227825Stheraven } 206227825Stheraven} 207227825Stheraven 208227825Stheravenvoid 209227825Stheraven__libcpp_db::__invalidate_all(void* __c) 210227825Stheraven{ 211227825Stheraven WLock _(mut()); 212227825Stheraven size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 213227825Stheraven __c_node* p = __cbeg_[hc]; 214227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A"); 215227825Stheraven while (p->__c_ != __c) 216227825Stheraven { 217227825Stheraven p = p->__next_; 218227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B"); 219227825Stheraven } 220227825Stheraven while (p->end_ != p->beg_) 221227825Stheraven { 222227825Stheraven --p->end_; 223227825Stheraven (*p->end_)->__c_ = nullptr; 224227825Stheraven } 225227825Stheraven} 226227825Stheraven 227227825Stheraven__c_node* 228227825Stheraven__libcpp_db::__find_c_and_lock(void* __c) const 229227825Stheraven{ 230227825Stheraven mut().lock(); 231227825Stheraven size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 232227825Stheraven __c_node* p = __cbeg_[hc]; 233227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A"); 234227825Stheraven while (p->__c_ != __c) 235227825Stheraven { 236227825Stheraven p = p->__next_; 237227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B"); 238227825Stheraven } 239227825Stheraven return p; 240227825Stheraven} 241227825Stheraven 242227825Stheraven__c_node* 243227825Stheraven__libcpp_db::__find_c(void* __c) const 244227825Stheraven{ 245227825Stheraven size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 246227825Stheraven __c_node* p = __cbeg_[hc]; 247227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 248227825Stheraven while (p->__c_ != __c) 249227825Stheraven { 250227825Stheraven p = p->__next_; 251227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 252227825Stheraven } 253227825Stheraven return p; 254227825Stheraven} 255227825Stheraven 256227825Stheravenvoid 257227825Stheraven__libcpp_db::unlock() const 258227825Stheraven{ 259227825Stheraven mut().unlock(); 260227825Stheraven} 261227825Stheraven 262227825Stheravenvoid 263227825Stheraven__libcpp_db::__erase_c(void* __c) 264227825Stheraven{ 265227825Stheraven WLock _(mut()); 266227825Stheraven size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_); 267227825Stheraven __c_node* p = __cbeg_[hc]; 268227825Stheraven __c_node* q = nullptr; 269227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 270227825Stheraven while (p->__c_ != __c) 271227825Stheraven { 272227825Stheraven q = p; 273227825Stheraven p = p->__next_; 274227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 275227825Stheraven } 276227825Stheraven if (q == nullptr) 277227825Stheraven __cbeg_[hc] = p->__next_; 278227825Stheraven else 279227825Stheraven q->__next_ = p->__next_; 280227825Stheraven while (p->end_ != p->beg_) 281227825Stheraven { 282227825Stheraven --p->end_; 283227825Stheraven (*p->end_)->__c_ = nullptr; 284227825Stheraven } 285227825Stheraven free(p->beg_); 286227825Stheraven free(p); 287227825Stheraven --__csz_; 288227825Stheraven} 289227825Stheraven 290227825Stheravenvoid 291227825Stheraven__libcpp_db::__iterator_copy(void* __i, const void* __i0) 292227825Stheraven{ 293227825Stheraven WLock _(mut()); 294227825Stheraven __i_node* i = __find_iterator(__i); 295227825Stheraven __i_node* i0 = __find_iterator(__i0); 296227825Stheraven __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 297227825Stheraven if (i == nullptr && c0 != nullptr) 298227825Stheraven i = __insert_iterator(__i); 299227825Stheraven __c_node* c = i != nullptr ? i->__c_ : nullptr; 300227825Stheraven if (c != c0) 301227825Stheraven { 302227825Stheraven if (c != nullptr) 303227825Stheraven c->__remove(i); 304227825Stheraven if (i != nullptr) 305227825Stheraven { 306227825Stheraven i->__c_ = nullptr; 307227825Stheraven if (c0 != nullptr) 308227825Stheraven { 309227825Stheraven i->__c_ = c0; 310227825Stheraven i->__c_->__add(i); 311227825Stheraven } 312227825Stheraven } 313227825Stheraven } 314227825Stheraven} 315227825Stheraven 316227825Stheravenbool 317227825Stheraven__libcpp_db::__dereferenceable(const void* __i) const 318227825Stheraven{ 319227825Stheraven RLock _(mut()); 320227825Stheraven __i_node* i = __find_iterator(__i); 321227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 322227825Stheraven} 323227825Stheraven 324227825Stheravenbool 325227825Stheraven__libcpp_db::__decrementable(const void* __i) const 326227825Stheraven{ 327227825Stheraven RLock _(mut()); 328227825Stheraven __i_node* i = __find_iterator(__i); 329227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 330227825Stheraven} 331227825Stheraven 332227825Stheravenbool 333227825Stheraven__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 334227825Stheraven{ 335227825Stheraven RLock _(mut()); 336227825Stheraven __i_node* i = __find_iterator(__i); 337227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 338227825Stheraven} 339227825Stheraven 340227825Stheravenbool 341227825Stheraven__libcpp_db::__subscriptable(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_->__subscriptable(__i, __n); 346227825Stheraven} 347227825Stheraven 348227825Stheravenbool 349227825Stheraven__libcpp_db::__comparable(const void* __i, const void* __j) const 350227825Stheraven{ 351227825Stheraven RLock _(mut()); 352227825Stheraven __i_node* i = __find_iterator(__i); 353227825Stheraven __i_node* j = __find_iterator(__j); 354227825Stheraven __c_node* ci = i != nullptr ? i->__c_ : nullptr; 355227825Stheraven __c_node* cj = j != nullptr ? j->__c_ : nullptr; 356227825Stheraven return ci != nullptr && ci == cj; 357227825Stheraven} 358227825Stheraven 359227825Stheravenvoid 360227825Stheraven__libcpp_db::swap(void* c1, void* c2) 361227825Stheraven{ 362227825Stheraven WLock _(mut()); 363227825Stheraven size_t hc = hash<void*>()(c1) % (__cend_ - __cbeg_); 364227825Stheraven __c_node* p1 = __cbeg_[hc]; 365227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 366227825Stheraven while (p1->__c_ != c1) 367227825Stheraven { 368227825Stheraven p1 = p1->__next_; 369227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 370227825Stheraven } 371227825Stheraven hc = hash<void*>()(c2) % (__cend_ - __cbeg_); 372227825Stheraven __c_node* p2 = __cbeg_[hc]; 373227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 374227825Stheraven while (p2->__c_ != c2) 375227825Stheraven { 376227825Stheraven p2 = p2->__next_; 377227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 378227825Stheraven } 379227825Stheraven std::swap(p1->beg_, p2->beg_); 380227825Stheraven std::swap(p1->end_, p2->end_); 381227825Stheraven std::swap(p1->cap_, p2->cap_); 382227825Stheraven for (__i_node** p = p1->beg_; p != p1->end_; ++p) 383227825Stheraven (*p)->__c_ = p1; 384227825Stheraven for (__i_node** p = p2->beg_; p != p2->end_; ++p) 385227825Stheraven (*p)->__c_ = p2; 386227825Stheraven} 387227825Stheraven 388227825Stheravenvoid 389227825Stheraven__libcpp_db::__insert_i(void* __i) 390227825Stheraven{ 391227825Stheraven WLock _(mut()); 392227825Stheraven __insert_iterator(__i); 393227825Stheraven} 394227825Stheraven 395227825Stheravenvoid 396227825Stheraven__c_node::__add(__i_node* i) 397227825Stheraven{ 398227825Stheraven if (end_ == cap_) 399227825Stheraven { 400227825Stheraven size_t nc = 2*(cap_ - beg_); 401227825Stheraven if (nc == 0) 402227825Stheraven nc = 1; 403227825Stheraven __i_node** beg = (__i_node**)malloc(nc * sizeof(__i_node*)); 404227825Stheraven if (beg == nullptr) 405227825Stheraven throw bad_alloc(); 406227825Stheraven if (nc > 1) 407227825Stheraven memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 408227825Stheraven free(beg_); 409227825Stheraven beg_ = beg; 410227825Stheraven end_ = beg_ + nc/2; 411227825Stheraven cap_ = beg_ + nc; 412227825Stheraven } 413227825Stheraven *end_++ = i; 414227825Stheraven} 415227825Stheraven 416227825Stheraven// private api 417227825Stheraven 418227825Stheraven_LIBCPP_HIDDEN 419227825Stheraven__i_node* 420227825Stheraven__libcpp_db::__insert_iterator(void* __i) 421227825Stheraven{ 422227825Stheraven if (__isz_ + 1 > __iend_ - __ibeg_) 423227825Stheraven { 424227825Stheraven size_t nc = __next_prime(2*(__iend_ - __ibeg_) + 1); 425227825Stheraven __i_node** ibeg = (__i_node**)calloc(nc, sizeof(void*)); 426227825Stheraven if (ibeg == nullptr) 427227825Stheraven throw bad_alloc(); 428227825Stheraven for (__i_node** p = __ibeg_; p != __iend_; ++p) 429227825Stheraven { 430227825Stheraven __i_node* q = *p; 431227825Stheraven while (q != nullptr) 432227825Stheraven { 433227825Stheraven size_t h = hash<void*>()(q->__i_) % nc; 434227825Stheraven __i_node* r = q->__next_; 435227825Stheraven q->__next_ = ibeg[h]; 436227825Stheraven ibeg[h] = q; 437227825Stheraven q = r; 438227825Stheraven } 439227825Stheraven } 440227825Stheraven free(__ibeg_); 441227825Stheraven __ibeg_ = ibeg; 442227825Stheraven __iend_ = __ibeg_ + nc; 443227825Stheraven } 444227825Stheraven size_t hi = hash<void*>()(__i) % (__iend_ - __ibeg_); 445227825Stheraven __i_node* p = __ibeg_[hi]; 446227825Stheraven __i_node* r = __ibeg_[hi] = (__i_node*)malloc(sizeof(__i_node)); 447227825Stheraven if (r == nullptr) 448227825Stheraven throw bad_alloc(); 449227825Stheraven ::new(r) __i_node(__i, p, nullptr); 450227825Stheraven ++__isz_; 451227825Stheraven return r; 452227825Stheraven} 453227825Stheraven 454227825Stheraven_LIBCPP_HIDDEN 455227825Stheraven__i_node* 456227825Stheraven__libcpp_db::__find_iterator(const void* __i) const 457227825Stheraven{ 458227825Stheraven __i_node* r = nullptr; 459227825Stheraven if (__ibeg_ != __iend_) 460227825Stheraven { 461227825Stheraven size_t h = hash<const void*>()(__i) % (__iend_ - __ibeg_); 462227825Stheraven for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 463227825Stheraven { 464227825Stheraven if (nd->__i_ == __i) 465227825Stheraven { 466227825Stheraven r = nd; 467227825Stheraven break; 468227825Stheraven } 469227825Stheraven } 470227825Stheraven } 471227825Stheraven return r; 472227825Stheraven} 473227825Stheraven 474227825Stheraven_LIBCPP_HIDDEN 475227825Stheravenvoid 476227825Stheraven__c_node::__remove(__i_node* p) 477227825Stheraven{ 478227825Stheraven __i_node** r = find(beg_, end_, p); 479227825Stheraven _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 480227825Stheraven if (--end_ != r) 481227825Stheraven memmove(r, r+1, (end_ - r)*sizeof(__i_node*)); 482227825Stheraven} 483227825Stheraven 484227825Stheraven_LIBCPP_END_NAMESPACE_STD 485