1 //===-------------------------- debug.cpp ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define _LIBCPP_DEBUG 1
15 #include "__hash_table"
18 _LIBCPP_BEGIN_NAMESPACE_STD
24 static __libcpp_db db;
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;
49 #endif // !_LIBCPP_HAS_NO_THREADS
51 } // unnamed namespace
72 __libcpp_db::__libcpp_db()
82 __libcpp_db::~__libcpp_db()
86 for (__c_node** p = __cbeg_; p != __cend_; ++p)
98 for (__i_node** p = __ibeg_; p != __iend_; ++p)
111 __libcpp_db::__find_c_from_i(void* __i) const
113 #ifndef _LIBCPP_HAS_NO_THREADS
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;
122 __libcpp_db::__insert_ic(void* __i, const void* __c)
124 #ifndef _LIBCPP_HAS_NO_THREADS
127 if (__cbeg_ == __cend_)
129 size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
130 __c_node* c = __cbeg_[hc];
133 while (c->__c_ != __c)
139 __i_node* i = __insert_iterator(__i);
145 __libcpp_db::__insert_c(void* __c)
147 #ifndef _LIBCPP_HAS_NO_THREADS
150 if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
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*)));
155 #ifndef _LIBCPP_NO_EXCEPTIONS
160 for (__c_node** p = __cbeg_; p != __cend_; ++p)
165 size_t h = hash<void*>()(q->__c_) % nc;
166 __c_node* r = q->__next_;
167 q->__next_ = cbeg[h];
174 __cend_ = __cbeg_ + nc;
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
193 __libcpp_db::__erase_i(void* __i)
195 #ifndef _LIBCPP_HAS_NO_THREADS
198 if (__ibeg_ != __iend_)
200 size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
201 __i_node* p = __ibeg_[hi];
204 __i_node* q = nullptr;
205 while (p->__i_ != __i)
213 __ibeg_[hi] = p->__next_;
215 q->__next_ = p->__next_;
216 __c_node* c = p->__c_;
226 __libcpp_db::__invalidate_all(void* __c)
228 #ifndef _LIBCPP_HAS_NO_THREADS
231 if (__cend_ != __cbeg_)
233 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
234 __c_node* p = __cbeg_[hc];
237 while (p->__c_ != __c)
243 while (p->end_ != p->beg_)
246 (*p->end_)->__c_ = nullptr;
252 __libcpp_db::__find_c_and_lock(void* __c) const
254 #ifndef _LIBCPP_HAS_NO_THREADS
257 if (__cend_ == __cbeg_)
259 #ifndef _LIBCPP_HAS_NO_THREADS
264 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
265 __c_node* p = __cbeg_[hc];
268 #ifndef _LIBCPP_HAS_NO_THREADS
273 while (p->__c_ != __c)
278 #ifndef _LIBCPP_HAS_NO_THREADS
288 __libcpp_db::__find_c(void* __c) const
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)
296 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
302 __libcpp_db::unlock() const
304 #ifndef _LIBCPP_HAS_NO_THREADS
310 __libcpp_db::__erase_c(void* __c)
312 #ifndef _LIBCPP_HAS_NO_THREADS
315 if (__cend_ != __cbeg_)
317 size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
318 __c_node* p = __cbeg_[hc];
321 __c_node* q = nullptr;
322 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
323 while (p->__c_ != __c)
329 _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
332 __cbeg_[hc] = p->__next_;
334 q->__next_ = p->__next_;
335 while (p->end_ != p->beg_)
338 (*p->end_)->__c_ = nullptr;
347 __libcpp_db::__iterator_copy(void* __i, const void* __i0)
349 #ifndef _LIBCPP_HAS_NO_THREADS
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;
375 __libcpp_db::__dereferenceable(const void* __i) const
377 #ifndef _LIBCPP_HAS_NO_THREADS
380 __i_node* i = __find_iterator(__i);
381 return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
385 __libcpp_db::__decrementable(const void* __i) const
387 #ifndef _LIBCPP_HAS_NO_THREADS
390 __i_node* i = __find_iterator(__i);
391 return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
395 __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
397 #ifndef _LIBCPP_HAS_NO_THREADS
400 __i_node* i = __find_iterator(__i);
401 return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
405 __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
407 #ifndef _LIBCPP_HAS_NO_THREADS
410 __i_node* i = __find_iterator(__i);
411 return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
415 __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
417 #ifndef _LIBCPP_HAS_NO_THREADS
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;
428 __libcpp_db::swap(void* c1, void* c2)
430 #ifndef _LIBCPP_HAS_NO_THREADS
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)
439 _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
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)
447 _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
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)
454 for (__i_node** p = p2->beg_; p != p2->end_; ++p)
459 __libcpp_db::__insert_i(void* __i)
461 #ifndef _LIBCPP_HAS_NO_THREADS
464 __insert_iterator(__i);
468 __c_node::__add(__i_node* i)
472 size_t nc = 2*static_cast<size_t>(cap_ - beg_);
476 static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
478 #ifndef _LIBCPP_NO_EXCEPTIONS
484 memcpy(beg, beg_, nc/2*sizeof(__i_node*));
497 __libcpp_db::__insert_iterator(void* __i)
499 if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
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*)));
504 #ifndef _LIBCPP_NO_EXCEPTIONS
509 for (__i_node** p = __ibeg_; p != __iend_; ++p)
514 size_t h = hash<void*>()(q->__i_) % nc;
515 __i_node* r = q->__next_;
516 q->__next_ = ibeg[h];
523 __iend_ = __ibeg_ + nc;
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)));
530 #ifndef _LIBCPP_NO_EXCEPTIONS
535 ::new(r) __i_node(__i, p, nullptr);
542 __libcpp_db::__find_iterator(const void* __i) const
544 __i_node* r = nullptr;
545 if (__ibeg_ != __iend_)
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_)
562 __c_node::__remove(__i_node* p)
564 __i_node** r = find(beg_, end_, p);
565 _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
567 memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
570 _LIBCPP_END_NAMESPACE_STD