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_VISIBLE
  21 __libcpp_db*
  22 __get_db()
  23 {
  24     static __libcpp_db db;
  25     return &db;
  26 };
  27
  28 _LIBCPP_VISIBLE
  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 constructed in translation unit with debug mode not enabled."
 114                    "  #define _LIBCPP_DEBUG2 1 for that translation unit.");
 115     return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
 116 }
 117
 118 void
 119 __libcpp_db::__insert_ic(void* __i, const void* __c)
 120 {
 121     WLock _(mut());
 122     __i_node* i = __insert_iterator(__i);
 123     const char* errmsg =
 124         "Container constructed in a translation unit with debug mode disabled."
 125         " But it is being used in a translation unit with debug mode enabled."
 126         " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1";
 127     _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg);
 128     size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 129     __c_node* c = __cbeg_[hc];
 130     _LIBCPP_ASSERT(c != nullptr, errmsg);
 131     while (c->__c_ != __c)
 132     {
 133         c = c->__next_;
 134         _LIBCPP_ASSERT(c != nullptr, errmsg);
 135     }
 136     c->__add(i);
 137     i->__c_ = c;
 138 }
 139
 140 __c_node*
 141 __libcpp_db::__insert_c(void* __c)
 142 {
 143     WLock _(mut());
 144     if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
 145     {
 146         size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
 147         __c_node** cbeg = (__c_node**)calloc(nc, sizeof(void*));
 148         if (cbeg == nullptr)
 149             throw bad_alloc();
 150         for (__c_node** p = __cbeg_; p != __cend_; ++p)
 151         {
 152             __c_node* q = *p;
 153             while (q != nullptr)
 154             {
 155                 size_t h = hash<void*>()(q->__c_) % nc;
 156                 __c_node* r = q->__next_;
 157                 q->__next_ = cbeg[h];
 158                 cbeg[h] = q;
 159                 q = r;
 160             }
 161         }
 162         free(__cbeg_);
 163         __cbeg_ = cbeg;
 164         __cend_ = __cbeg_ + nc;
 165     }
 166     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 167     __c_node* p = __cbeg_[hc];
 168     __c_node* r = __cbeg_[hc] = (__c_node*)malloc(sizeof(__c_node));
 169     if (__cbeg_[hc] == nullptr)
 170         throw bad_alloc();
 171     r->__c_ = __c;
 172     r->__next_ = p;
 173     ++__csz_;
 174     return r;
 175 }
 176
 177 void
 178 __libcpp_db::__erase_i(void* __i)
 179 {
 180     WLock _(mut());
 181     if (__ibeg_ != __iend_)
 182     {
 183         size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
 184         __i_node* p = __ibeg_[hi];
 185         if (p != nullptr)
 186         {
 187             __i_node* q = nullptr;
 188             while (p->__i_ != __i)
 189             {
 190                 q = p;
 191                 p = p->__next_;
 192                 if (p == nullptr)
 193                     return;
 194             }
 195             if (q == nullptr)
 196                 __ibeg_[hi] = p->__next_;
 197             else
 198                 q->__next_ = p->__next_;
 199             __c_node* c = p->__c_;
 200             free(p);
 201             --__isz_;
 202             if (c != nullptr)
 203                 c->__remove(p);
 204         }
 205     }
 206 }
 207
 208 void
 209 __libcpp_db::__invalidate_all(void* __c)
 210 {
 211     WLock _(mut());
 212     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 213     __c_node* p = __cbeg_[hc];
 214     _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A");
 215     while (p->__c_ != __c)
 216     {
 217         p = p->__next_;
 218         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B");
 219     }
 220     while (p->end_ != p->beg_)
 221     {
 222         --p->end_;
 223         (*p->end_)->__c_ = nullptr;
 224     }
 225 }
 226
 227 __c_node*
 228 __libcpp_db::__find_c_and_lock(void* __c) const
 229 {
 230     mut().lock();
 231     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 232     __c_node* p = __cbeg_[hc];
 233     _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A");
 234     while (p->__c_ != __c)
 235     {
 236         p = p->__next_;
 237         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B");
 238     }
 239     return p;
 240 }
 241
 242 __c_node*
 243 __libcpp_db::__find_c(void* __c) const
 244 {
 245     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 246     __c_node* p = __cbeg_[hc];
 247     _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
 248     while (p->__c_ != __c)
 249     {
 250         p = p->__next_;
 251         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
 252     }
 253     return p;
 254 }
 255
 256 void
 257 __libcpp_db::unlock() const
 258 {
 259     mut().unlock();
 260 }
 261
 262 void
 263 __libcpp_db::__erase_c(void* __c)
 264 {
 265     WLock _(mut());
 266     size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
 267     __c_node* p = __cbeg_[hc];
 268     __c_node* q = nullptr;
 269     _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
 270     while (p->__c_ != __c)
 271     {
 272         q = p;
 273         p = p->__next_;
 274         _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
 275     }
 276     if (q == nullptr)
 277         __cbeg_[hc] = p->__next_;
 278     else
 279         q->__next_ = p->__next_;
 280     while (p->end_ != p->beg_)
 281     {
 282         --p->end_;
 283         (*p->end_)->__c_ = nullptr;
 284     }
 285     free(p->beg_);
 286     free(p);
 287     --__csz_;
 288 }
 289
 290 void
 291 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
 292 {
 293     WLock _(mut());
 294     __i_node* i = __find_iterator(__i);
 295     __i_node* i0 = __find_iterator(__i0);
 296     __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
 297     if (i == nullptr && c0 != nullptr)
 298         i = __insert_iterator(__i);
 299     __c_node* c = i != nullptr ? i->__c_ : nullptr;
 300     if (c != c0)
 301     {
 302         if (c != nullptr)
 303             c->__remove(i);
 304         if (i != nullptr)
 305         {
 306             i->__c_ = nullptr;
 307             if (c0 != nullptr)
 308             {
 309                 i->__c_ = c0;
 310                 i->__c_->__add(i);
 311             }
 312         }
 313     }
 314 }
 315
 316 bool
 317 __libcpp_db::__dereferenceable(const void* __i) const
 318 {
 319     RLock _(mut());
 320     __i_node* i = __find_iterator(__i);
 321     return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
 322 }
 323
 324 bool
 325 __libcpp_db::__decrementable(const void* __i) const
 326 {
 327     RLock _(mut());
 328     __i_node* i = __find_iterator(__i);
 329     return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
 330 }
 331
 332 bool
 333 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
 334 {
 335     RLock _(mut());
 336     __i_node* i = __find_iterator(__i);
 337     return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
 338 }
 339
 340 bool
 341 __libcpp_db::__subscriptable(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_->__subscriptable(__i, __n);
 346 }
 347
 348 bool
 349 __libcpp_db::__comparable(const void* __i, const void* __j) const
 350 {
 351     RLock _(mut());
 352     __i_node* i = __find_iterator(__i);
 353     __i_node* j = __find_iterator(__j);
 354     __c_node* ci = i != nullptr ? i->__c_ : nullptr;
 355     __c_node* cj = j != nullptr ? j->__c_ : nullptr;
 356     return ci != nullptr && ci == cj;
 357 }
 358
 359 void
 360 __libcpp_db::swap(void* c1, void* c2)
 361 {
 362     WLock _(mut());
 363     size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
 364     __c_node* p1 = __cbeg_[hc];
 365     _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
 366     while (p1->__c_ != c1)
 367     {
 368         p1 = p1->__next_;
 369         _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
 370     }
 371     hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
 372     __c_node* p2 = __cbeg_[hc];
 373     _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
 374     while (p2->__c_ != c2)
 375     {
 376         p2 = p2->__next_;
 377         _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
 378     }
 379     std::swap(p1->beg_, p2->beg_);
 380     std::swap(p1->end_, p2->end_);
 381     std::swap(p1->cap_, p2->cap_);
 382     for (__i_node** p = p1->beg_; p != p1->end_; ++p)
 383         (*p)->__c_ = p1;
 384     for (__i_node** p = p2->beg_; p != p2->end_; ++p)
 385         (*p)->__c_ = p2;
 386 }
 387
 388 void
 389 __libcpp_db::__insert_i(void* __i)
 390 {
 391     WLock _(mut());
 392     __insert_iterator(__i);
 393 }
 394
 395 void
 396 __c_node::__add(__i_node* i)
 397 {
 398     if (end_ == cap_)
 399     {
 400         size_t nc = 2*static_cast<size_t>(cap_ - beg_);
 401         if (nc == 0)
 402             nc = 1;
 403         __i_node** beg = (__i_node**)malloc(nc * sizeof(__i_node*));
 404         if (beg == nullptr)
 405             throw bad_alloc();
 406         if (nc > 1)
 407             memcpy(beg, beg_, nc/2*sizeof(__i_node*));
 408         free(beg_);
 409         beg_ = beg;
 410         end_ = beg_ + nc/2;
 411         cap_ = beg_ + nc;
 412     }
 413     *end_++ = i;
 414 }
 415
 416 // private api
 417
 418 _LIBCPP_HIDDEN
 419 __i_node*
 420 __libcpp_db::__insert_iterator(void* __i)
 421 {
 422     if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
 423     {
 424         size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
 425         __i_node** ibeg = (__i_node**)calloc(nc, sizeof(void*));
 426         if (ibeg == nullptr)
 427             throw bad_alloc();
 428         for (__i_node** p = __ibeg_; p != __iend_; ++p)
 429         {
 430             __i_node* q = *p;
 431             while (q != nullptr)
 432             {
 433                 size_t h = hash<void*>()(q->__i_) % nc;
 434                 __i_node* r = q->__next_;
 435                 q->__next_ = ibeg[h];
 436                 ibeg[h] = q;
 437                 q = r;
 438             }
 439         }
 440         free(__ibeg_);
 441         __ibeg_ = ibeg;
 442         __iend_ = __ibeg_ + nc;
 443     }
 444     size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
 445     __i_node* p = __ibeg_[hi];
 446     __i_node* r = __ibeg_[hi] = (__i_node*)malloc(sizeof(__i_node));
 447     if (r == nullptr)
 448         throw bad_alloc();
 449     ::new(r) __i_node(__i, p, nullptr);
 450     ++__isz_;
 451     return r;
 452 }
 453
 454 _LIBCPP_HIDDEN
 455 __i_node*
 456 __libcpp_db::__find_iterator(const void* __i) const
 457 {
 458     __i_node* r = nullptr;
 459     if (__ibeg_ != __iend_)
 460     {
 461         size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
 462         for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
 463         {
 464             if (nd->__i_ == __i)
 465             {
 466                 r = nd;
 467                 break;
 468             }
 469         }
 470     }
 471     return r;
 472 }
 473
 474 _LIBCPP_HIDDEN
 475 void
 476 __c_node::__remove(__i_node* p)
 477 {
 478     __i_node** r = find(beg_, end_, p);
 479     _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
 480     if (--end_ != r)
 481         memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
 482 }
 483
 484 _LIBCPP_END_NAMESPACE_STD