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