contrib/libc++/src/debug.cpp

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