debug.cpp revision 249998
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 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 __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 = (__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] = (__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 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 220 __c_node* p = __cbeg_[hc]; 221 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A"); 222 while (p->__c_ != __c) 223 { 224 p = p->__next_; 225 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B"); 226 } 227 while (p->end_ != p->beg_) 228 { 229 --p->end_; 230 (*p->end_)->__c_ = nullptr; 231 } 232} 233 234__c_node* 235__libcpp_db::__find_c_and_lock(void* __c) const 236{ 237 mut().lock(); 238 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 239 __c_node* p = __cbeg_[hc]; 240 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A"); 241 while (p->__c_ != __c) 242 { 243 p = p->__next_; 244 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B"); 245 } 246 return p; 247} 248 249__c_node* 250__libcpp_db::__find_c(void* __c) const 251{ 252 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 253 __c_node* p = __cbeg_[hc]; 254 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 255 while (p->__c_ != __c) 256 { 257 p = p->__next_; 258 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 259 } 260 return p; 261} 262 263void 264__libcpp_db::unlock() const 265{ 266 mut().unlock(); 267} 268 269void 270__libcpp_db::__erase_c(void* __c) 271{ 272 WLock _(mut()); 273 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 274 __c_node* p = __cbeg_[hc]; 275 __c_node* q = nullptr; 276 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 277 while (p->__c_ != __c) 278 { 279 q = p; 280 p = p->__next_; 281 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 282 } 283 if (q == nullptr) 284 __cbeg_[hc] = p->__next_; 285 else 286 q->__next_ = p->__next_; 287 while (p->end_ != p->beg_) 288 { 289 --p->end_; 290 (*p->end_)->__c_ = nullptr; 291 } 292 free(p->beg_); 293 free(p); 294 --__csz_; 295} 296 297void 298__libcpp_db::__iterator_copy(void* __i, const void* __i0) 299{ 300 WLock _(mut()); 301 __i_node* i = __find_iterator(__i); 302 __i_node* i0 = __find_iterator(__i0); 303 __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 304 if (i == nullptr && i0 != nullptr) 305 i = __insert_iterator(__i); 306 __c_node* c = i != nullptr ? i->__c_ : nullptr; 307 if (c != c0) 308 { 309 if (c != nullptr) 310 c->__remove(i); 311 if (i != nullptr) 312 { 313 i->__c_ = nullptr; 314 if (c0 != nullptr) 315 { 316 i->__c_ = c0; 317 i->__c_->__add(i); 318 } 319 } 320 } 321} 322 323bool 324__libcpp_db::__dereferenceable(const void* __i) const 325{ 326 RLock _(mut()); 327 __i_node* i = __find_iterator(__i); 328 return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 329} 330 331bool 332__libcpp_db::__decrementable(const void* __i) const 333{ 334 RLock _(mut()); 335 __i_node* i = __find_iterator(__i); 336 return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 337} 338 339bool 340__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 341{ 342 RLock _(mut()); 343 __i_node* i = __find_iterator(__i); 344 return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 345} 346 347bool 348__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 349{ 350 RLock _(mut()); 351 __i_node* i = __find_iterator(__i); 352 return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 353} 354 355bool 356__libcpp_db::__comparable(const void* __i, const void* __j) const 357{ 358 RLock _(mut()); 359 __i_node* i = __find_iterator(__i); 360 __i_node* j = __find_iterator(__j); 361 __c_node* ci = i != nullptr ? i->__c_ : nullptr; 362 __c_node* cj = j != nullptr ? j->__c_ : nullptr; 363 return ci != nullptr && ci == cj; 364} 365 366void 367__libcpp_db::swap(void* c1, void* c2) 368{ 369 WLock _(mut()); 370 size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); 371 __c_node* p1 = __cbeg_[hc]; 372 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 373 while (p1->__c_ != c1) 374 { 375 p1 = p1->__next_; 376 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 377 } 378 hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); 379 __c_node* p2 = __cbeg_[hc]; 380 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 381 while (p2->__c_ != c2) 382 { 383 p2 = p2->__next_; 384 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 385 } 386 std::swap(p1->beg_, p2->beg_); 387 std::swap(p1->end_, p2->end_); 388 std::swap(p1->cap_, p2->cap_); 389 for (__i_node** p = p1->beg_; p != p1->end_; ++p) 390 (*p)->__c_ = p1; 391 for (__i_node** p = p2->beg_; p != p2->end_; ++p) 392 (*p)->__c_ = p2; 393} 394 395void 396__libcpp_db::__insert_i(void* __i) 397{ 398 WLock _(mut()); 399 __insert_iterator(__i); 400} 401 402void 403__c_node::__add(__i_node* i) 404{ 405 if (end_ == cap_) 406 { 407 size_t nc = 2*static_cast<size_t>(cap_ - beg_); 408 if (nc == 0) 409 nc = 1; 410 __i_node** beg = (__i_node**)malloc(nc * sizeof(__i_node*)); 411 if (beg == nullptr) 412#ifndef _LIBCPP_NO_EXCEPTIONS 413 throw bad_alloc(); 414#else 415 abort(); 416#endif 417 if (nc > 1) 418 memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 419 free(beg_); 420 beg_ = beg; 421 end_ = beg_ + nc/2; 422 cap_ = beg_ + nc; 423 } 424 *end_++ = i; 425} 426 427// private api 428 429_LIBCPP_HIDDEN 430__i_node* 431__libcpp_db::__insert_iterator(void* __i) 432{ 433 if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 434 { 435 size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 436 __i_node** ibeg = (__i_node**)calloc(nc, sizeof(void*)); 437 if (ibeg == nullptr) 438#ifndef _LIBCPP_NO_EXCEPTIONS 439 throw bad_alloc(); 440#else 441 abort(); 442#endif 443 for (__i_node** p = __ibeg_; p != __iend_; ++p) 444 { 445 __i_node* q = *p; 446 while (q != nullptr) 447 { 448 size_t h = hash<void*>()(q->__i_) % nc; 449 __i_node* r = q->__next_; 450 q->__next_ = ibeg[h]; 451 ibeg[h] = q; 452 q = r; 453 } 454 } 455 free(__ibeg_); 456 __ibeg_ = ibeg; 457 __iend_ = __ibeg_ + nc; 458 } 459 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 460 __i_node* p = __ibeg_[hi]; 461 __i_node* r = __ibeg_[hi] = (__i_node*)malloc(sizeof(__i_node)); 462 if (r == nullptr) 463#ifndef _LIBCPP_NO_EXCEPTIONS 464 throw bad_alloc(); 465#else 466 abort(); 467#endif 468 ::new(r) __i_node(__i, p, nullptr); 469 ++__isz_; 470 return r; 471} 472 473_LIBCPP_HIDDEN 474__i_node* 475__libcpp_db::__find_iterator(const void* __i) const 476{ 477 __i_node* r = nullptr; 478 if (__ibeg_ != __iend_) 479 { 480 size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 481 for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 482 { 483 if (nd->__i_ == __i) 484 { 485 r = nd; 486 break; 487 } 488 } 489 } 490 return r; 491} 492 493_LIBCPP_HIDDEN 494void 495__c_node::__remove(__i_node* p) 496{ 497 __i_node** r = find(beg_, end_, p); 498 _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 499 if (--end_ != r) 500 memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 501} 502 503_LIBCPP_END_NAMESPACE_STD 504