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 29 const __libcpp_db* 30 __get_const_db() 31 { 32 return __get_db(); 33 } 34 35 namespace 36 { 37 38 typedef mutex mutex_type; 39 typedef lock_guard<mutex_type> WLock; 40 typedef lock_guard<mutex_type> RLock; 41 42 mutex_type& 43 mut() 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 108 void* 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 117 void 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 184 void 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 215 void 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 281 void 282 __libcpp_db::unlock() const 283 { 284 mut().unlock(); 285 } 286 287 void 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 322 void 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 348 bool 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 356 bool 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 364 bool 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 372 bool 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 380 bool 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 391 void 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 420 void 421 __libcpp_db::__insert_i(void* __i) 422 { 423 WLock _(mut()); 424 __insert_iterator(__i); 425 } 426 427 void 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 521 void 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
