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