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_DEBUG2 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 __i_node* i = __insert_iterator(__i); 122 const char* errmsg = 123 "Container constructed in a translation unit with debug mode disabled." 124 " But it is being used in a translation unit with debug mode enabled." 125 " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1"; 126 _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg); 127 size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 128 __c_node* c = __cbeg_[hc]; 129 _LIBCPP_ASSERT(c != nullptr, errmsg); 130 while (c->__c_ != __c) 131 { 132 c = c->__next_; 133 _LIBCPP_ASSERT(c != nullptr, errmsg); 134 } 135 c->__add(i); 136 i->__c_ = c; 137 } 138 139 __c_node* 140 __libcpp_db::__insert_c(void* __c) 141 { 142 WLock _(mut()); 143 if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 144 { 145 size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 146 __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*))); 147 if (cbeg == nullptr) 148 #ifndef _LIBCPP_NO_EXCEPTIONS 149 throw bad_alloc(); 150 #else 151 abort(); 152 #endif 153 for (__c_node** p = __cbeg_; p != __cend_; ++p) 154 { 155 __c_node* q = *p; 156 while (q != nullptr) 157 { 158 size_t h = hash<void*>()(q->__c_) % nc; 159 __c_node* r = q->__next_; 160 q->__next_ = cbeg[h]; 161 cbeg[h] = q; 162 q = r; 163 } 164 } 165 free(__cbeg_); 166 __cbeg_ = cbeg; 167 __cend_ = __cbeg_ + nc; 168 } 169 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 170 __c_node* p = __cbeg_[hc]; 171 __c_node* r = __cbeg_[hc] = 172 static_cast<__c_node*>(malloc(sizeof(__c_node))); 173 if (__cbeg_[hc] == nullptr) 174 #ifndef _LIBCPP_NO_EXCEPTIONS 175 throw bad_alloc(); 176 #else 177 abort(); 178 #endif 179 r->__c_ = __c; 180 r->__next_ = p; 181 ++__csz_; 182 return r; 183 } 184 185 void 186 __libcpp_db::__erase_i(void* __i) 187 { 188 WLock _(mut()); 189 if (__ibeg_ != __iend_) 190 { 191 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 192 __i_node* p = __ibeg_[hi]; 193 if (p != nullptr) 194 { 195 __i_node* q = nullptr; 196 while (p->__i_ != __i) 197 { 198 q = p; 199 p = p->__next_; 200 if (p == nullptr) 201 return; 202 } 203 if (q == nullptr) 204 __ibeg_[hi] = p->__next_; 205 else 206 q->__next_ = p->__next_; 207 __c_node* c = p->__c_; 208 free(p); 209 --__isz_; 210 if (c != nullptr) 211 c->__remove(p); 212 } 213 } 214 } 215 216 void 217 __libcpp_db::__invalidate_all(void* __c) 218 { 219 WLock _(mut()); 220 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 221 __c_node* p = __cbeg_[hc]; 222 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A"); 223 while (p->__c_ != __c) 224 { 225 p = p->__next_; 226 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B"); 227 } 228 while (p->end_ != p->beg_) 229 { 230 --p->end_; 231 (*p->end_)->__c_ = nullptr; 232 } 233 } 234 235 __c_node* 236 __libcpp_db::__find_c_and_lock(void* __c) const 237 { 238 mut().lock(); 239 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 240 __c_node* p = __cbeg_[hc]; 241 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A"); 242 while (p->__c_ != __c) 243 { 244 p = p->__next_; 245 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B"); 246 } 247 return p; 248 } 249 250 __c_node* 251 __libcpp_db::__find_c(void* __c) const 252 { 253 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 254 __c_node* p = __cbeg_[hc]; 255 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 256 while (p->__c_ != __c) 257 { 258 p = p->__next_; 259 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 260 } 261 return p; 262 } 263 264 void 265 __libcpp_db::unlock() const 266 { 267 mut().unlock(); 268 } 269 270 void 271 __libcpp_db::__erase_c(void* __c) 272 { 273 WLock _(mut()); 274 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 275 __c_node* p = __cbeg_[hc]; 276 __c_node* q = nullptr; 277 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 278 while (p->__c_ != __c) 279 { 280 q = p; 281 p = p->__next_; 282 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 283 } 284 if (q == nullptr) 285 __cbeg_[hc] = p->__next_; 286 else 287 q->__next_ = p->__next_; 288 while (p->end_ != p->beg_) 289 { 290 --p->end_; 291 (*p->end_)->__c_ = nullptr; 292 } 293 free(p->beg_); 294 free(p); 295 --__csz_; 296 } 297 298 void 299 __libcpp_db::__iterator_copy(void* __i, const void* __i0) 300 { 301 WLock _(mut()); 302 __i_node* i = __find_iterator(__i); 303 __i_node* i0 = __find_iterator(__i0); 304 __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 305 if (i == nullptr && i0 != nullptr) 306 i = __insert_iterator(__i); 307 __c_node* c = i != nullptr ? i->__c_ : nullptr; 308 if (c != c0) 309 { 310 if (c != nullptr) 311 c->__remove(i); 312 if (i != nullptr) 313 { 314 i->__c_ = nullptr; 315 if (c0 != nullptr) 316 { 317 i->__c_ = c0; 318 i->__c_->__add(i); 319 } 320 } 321 } 322 } 323 324 bool 325 __libcpp_db::__dereferenceable(const void* __i) const 326 { 327 RLock _(mut()); 328 __i_node* i = __find_iterator(__i); 329 return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 330 } 331 332 bool 333 __libcpp_db::__decrementable(const void* __i) const 334 { 335 RLock _(mut()); 336 __i_node* i = __find_iterator(__i); 337 return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 338 } 339 340 bool 341 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 342 { 343 RLock _(mut()); 344 __i_node* i = __find_iterator(__i); 345 return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 346 } 347 348 bool 349 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 350 { 351 RLock _(mut()); 352 __i_node* i = __find_iterator(__i); 353 return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 354 } 355 356 bool 357 __libcpp_db::__comparable(const void* __i, const void* __j) const 358 { 359 RLock _(mut()); 360 __i_node* i = __find_iterator(__i); 361 __i_node* j = __find_iterator(__j); 362 __c_node* ci = i != nullptr ? i->__c_ : nullptr; 363 __c_node* cj = j != nullptr ? j->__c_ : nullptr; 364 return ci != nullptr && ci == cj; 365 } 366 367 void 368 __libcpp_db::swap(void* c1, void* c2) 369 { 370 WLock _(mut()); 371 size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); 372 __c_node* p1 = __cbeg_[hc]; 373 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 374 while (p1->__c_ != c1) 375 { 376 p1 = p1->__next_; 377 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 378 } 379 hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); 380 __c_node* p2 = __cbeg_[hc]; 381 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 382 while (p2->__c_ != c2) 383 { 384 p2 = p2->__next_; 385 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 386 } 387 std::swap(p1->beg_, p2->beg_); 388 std::swap(p1->end_, p2->end_); 389 std::swap(p1->cap_, p2->cap_); 390 for (__i_node** p = p1->beg_; p != p1->end_; ++p) 391 (*p)->__c_ = p1; 392 for (__i_node** p = p2->beg_; p != p2->end_; ++p) 393 (*p)->__c_ = p2; 394 } 395 396 void 397 __libcpp_db::__insert_i(void* __i) 398 { 399 WLock _(mut()); 400 __insert_iterator(__i); 401 } 402 403 void 404 __c_node::__add(__i_node* i) 405 { 406 if (end_ == cap_) 407 { 408 size_t nc = 2*static_cast<size_t>(cap_ - beg_); 409 if (nc == 0) 410 nc = 1; 411 __i_node** beg = 412 static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); 413 if (beg == nullptr) 414 #ifndef _LIBCPP_NO_EXCEPTIONS 415 throw bad_alloc(); 416 #else 417 abort(); 418 #endif 419 if (nc > 1) 420 memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 421 free(beg_); 422 beg_ = beg; 423 end_ = beg_ + nc/2; 424 cap_ = beg_ + nc; 425 } 426 *end_++ = i; 427 } 428 429 // private api 430 431 _LIBCPP_HIDDEN 432 __i_node* 433 __libcpp_db::__insert_iterator(void* __i) 434 { 435 if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 436 { 437 size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 438 __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*))); 439 if (ibeg == nullptr) 440 #ifndef _LIBCPP_NO_EXCEPTIONS 441 throw bad_alloc(); 442 #else 443 abort(); 444 #endif 445 for (__i_node** p = __ibeg_; p != __iend_; ++p) 446 { 447 __i_node* q = *p; 448 while (q != nullptr) 449 { 450 size_t h = hash<void*>()(q->__i_) % nc; 451 __i_node* r = q->__next_; 452 q->__next_ = ibeg[h]; 453 ibeg[h] = q; 454 q = r; 455 } 456 } 457 free(__ibeg_); 458 __ibeg_ = ibeg; 459 __iend_ = __ibeg_ + nc; 460 } 461 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 462 __i_node* p = __ibeg_[hi]; 463 __i_node* r = __ibeg_[hi] = 464 static_cast<__i_node*>(malloc(sizeof(__i_node))); 465 if (r == nullptr) 466 #ifndef _LIBCPP_NO_EXCEPTIONS 467 throw bad_alloc(); 468 #else 469 abort(); 470 #endif 471 ::new(r) __i_node(__i, p, nullptr); 472 ++__isz_; 473 return r; 474 } 475 476 _LIBCPP_HIDDEN 477 __i_node* 478 __libcpp_db::__find_iterator(const void* __i) const 479 { 480 __i_node* r = nullptr; 481 if (__ibeg_ != __iend_) 482 { 483 size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 484 for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 485 { 486 if (nd->__i_ == __i) 487 { 488 r = nd; 489 break; 490 } 491 } 492 } 493 return r; 494 } 495 496 _LIBCPP_HIDDEN 497 void 498 __c_node::__remove(__i_node* p) 499 { 500 __i_node** r = find(beg_, end_, p); 501 _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 502 if (--end_ != r) 503 memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 504 } 505 506 _LIBCPP_END_NAMESPACE_STD 507
