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 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