debug.cpp revision 249998
175584Sru//===-------------------------- debug.cpp ---------------------------------===// 2151497Sru// 3114402Sru// The LLVM Compiler Infrastructure 475584Sru// 575584Sru// This file is dual licensed under the MIT and the University of Illinois Open 675584Sru// Source Licenses. See LICENSE.TXT for details. 775584Sru// 875584Sru//===----------------------------------------------------------------------===// 975584Sru 1075584Sru#define _LIBCPP_DEBUG2 1 1175584Sru#include "__config" 1275584Sru#include "__debug" 1375584Sru#include "functional" 1475584Sru#include "algorithm" 1575584Sru#include "__hash_table" 1675584Sru#include "mutex" 1775584Sru 1875584Sru_LIBCPP_BEGIN_NAMESPACE_STD 1975584Sru 20151497Sru_LIBCPP_FUNC_VIS 2175584Sru__libcpp_db* 22151497Sru__get_db() 23151497Sru{ 24151497Sru static __libcpp_db db; 25151497Sru return &db; 2675584Sru} 2775584Sru 2875584Sru_LIBCPP_FUNC_VIS 2975584Sruconst __libcpp_db* 3075584Sru__get_const_db() 3175584Sru{ 3275584Sru return __get_db(); 3375584Sru} 3475584Sru 3575584Srunamespace 3675584Sru{ 3775584Sru 3875584Srutypedef mutex mutex_type; 3975584Srutypedef lock_guard<mutex_type> WLock; 4075584Srutypedef lock_guard<mutex_type> RLock; 41151497Sru 4279543Srumutex_type& 43151497Srumut() 44151497Sru{ 45151497Sru static mutex_type m; 46151497Sru return m; 47151497Sru} 48151497Sru 4975584Sru} // unnamed namespace 5075584Sru 5175584Sru__i_node::~__i_node() 5275584Sru{ 5375584Sru if (__next_) 5475584Sru { 5575584Sru __next_->~__i_node(); 5675584Sru free(__next_); 5775584Sru } 5875584Sru} 5975584Sru 6075584Sru__c_node::~__c_node() 6175584Sru{ 6275584Sru free(beg_); 6375584Sru if (__next_) 6475584Sru { 6575584Sru __next_->~__c_node(); 6675584Sru free(__next_); 6775584Sru } 68151497Sru} 6975584Sru 7075584Sru__libcpp_db::__libcpp_db() 7175584Sru : __cbeg_(nullptr), 7275584Sru __cend_(nullptr), 7375584Sru __csz_(0), 7475584Sru __ibeg_(nullptr), 7575584Sru __iend_(nullptr), 7675584Sru __isz_(0) 7775584Sru{ 7875584Sru} 7975584Sru 8075584Sru__libcpp_db::~__libcpp_db() 8175584Sru{ 8275584Sru if (__cbeg_) 8375584Sru { 8475584Sru for (__c_node** p = __cbeg_; p != __cend_; ++p) 8575584Sru { 8675584Sru if (*p != nullptr) 8775584Sru { 8875584Sru (*p)->~__c_node(); 8975584Sru free(*p); 9075584Sru } 9175584Sru } 9275584Sru free(__cbeg_); 93151497Sru } 9475584Sru if (__ibeg_) 9575584Sru { 9675584Sru for (__i_node** p = __ibeg_; p != __iend_; ++p) 9775584Sru { 9875584Sru if (*p != nullptr) 9975584Sru { 10075584Sru (*p)->~__i_node(); 10175584Sru free(*p); 10275584Sru } 103151497Sru } 10475584Sru free(__ibeg_); 10575584Sru } 10675584Sru} 10775584Sru 10875584Sruvoid* 10975584Sru__libcpp_db::__find_c_from_i(void* __i) const 11075584Sru{ 11175584Sru RLock _(mut()); 11275584Sru __i_node* i = __find_iterator(__i); 11375584Sru _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database."); 11475584Sru return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; 11575584Sru} 11675584Sru 11775584Sruvoid 11875584Sru__libcpp_db::__insert_ic(void* __i, const void* __c) 11975584Sru{ 12075584Sru WLock _(mut()); 12175584Sru __i_node* i = __insert_iterator(__i); 12275584Sru const char* errmsg = 12375584Sru "Container constructed in a translation unit with debug mode disabled." 12475584Sru " But it is being used in a translation unit with debug mode enabled." 12575584Sru " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1"; 12675584Sru _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg); 12775584Sru size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 12875584Sru __c_node* c = __cbeg_[hc]; 12975584Sru _LIBCPP_ASSERT(c != nullptr, errmsg); 13075584Sru while (c->__c_ != __c) 13175584Sru { 13275584Sru c = c->__next_; 13375584Sru _LIBCPP_ASSERT(c != nullptr, errmsg); 13475584Sru } 13575584Sru c->__add(i); 13675584Sru i->__c_ = c; 13775584Sru} 13875584Sru 13975584Sru__c_node* 140114402Sru__libcpp_db::__insert_c(void* __c) 14175584Sru{ 14275584Sru WLock _(mut()); 14375584Sru if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 14475584Sru { 14575584Sru size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 14675584Sru __c_node** cbeg = (__c_node**)calloc(nc, sizeof(void*)); 14775584Sru if (cbeg == nullptr) 14875584Sru#ifndef _LIBCPP_NO_EXCEPTIONS 14975584Sru throw bad_alloc(); 150151497Sru#else 15175584Sru abort(); 15275584Sru#endif 15375584Sru for (__c_node** p = __cbeg_; p != __cend_; ++p) 15475584Sru { 15575584Sru __c_node* q = *p; 15675584Sru while (q != nullptr) 15775584Sru { 15875584Sru size_t h = hash<void*>()(q->__c_) % nc; 15975584Sru __c_node* r = q->__next_; 16075584Sru q->__next_ = cbeg[h]; 16175584Sru cbeg[h] = q; 16275584Sru q = r; 16375584Sru } 16475584Sru } 16575584Sru free(__cbeg_); 16675584Sru __cbeg_ = cbeg; 16775584Sru __cend_ = __cbeg_ + nc; 16875584Sru } 16975584Sru size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 170104862Sru __c_node* p = __cbeg_[hc]; 17175584Sru __c_node* r = __cbeg_[hc] = (__c_node*)malloc(sizeof(__c_node)); 17275584Sru 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