| //===----------------------------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include <__assert> |
| #include <__config> |
| #include <__debug> |
| #include <__hash_table> |
| #include <algorithm> |
| #include <cstdio> |
| #include <functional> |
| #include <string> |
| |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| # include <mutex> |
| # if defined(__ELF__) && defined(_LIBCPP_LINK_PTHREAD_LIB) |
| # pragma comment(lib, "pthread") |
| # endif |
| #endif |
| |
| _LIBCPP_BEGIN_NAMESPACE_STD |
| |
| _LIBCPP_FUNC_VIS |
| __libcpp_db* |
| __get_db() |
| { |
| static _LIBCPP_NO_DESTROY __libcpp_db db; |
| return &db; |
| } |
| |
| _LIBCPP_FUNC_VIS |
| const __libcpp_db* |
| __get_const_db() |
| { |
| return __get_db(); |
| } |
| |
| namespace |
| { |
| |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| typedef mutex mutex_type; |
| typedef lock_guard<mutex_type> WLock; |
| typedef lock_guard<mutex_type> RLock; |
| |
| mutex_type& |
| mut() |
| { |
| static _LIBCPP_NO_DESTROY mutex_type m; |
| return m; |
| } |
| #endif // !_LIBCPP_HAS_NO_THREADS |
| |
| } // unnamed namespace |
| |
| __i_node::~__i_node() |
| { |
| if (__next_) |
| { |
| __next_->~__i_node(); |
| free(__next_); |
| } |
| } |
| |
| __c_node::~__c_node() |
| { |
| free(beg_); |
| if (__next_) |
| { |
| __next_->~__c_node(); |
| free(__next_); |
| } |
| } |
| |
| __libcpp_db::__libcpp_db() |
| : __cbeg_(nullptr), |
| __cend_(nullptr), |
| __csz_(0), |
| __ibeg_(nullptr), |
| __iend_(nullptr), |
| __isz_(0) |
| { |
| } |
| |
| __libcpp_db::~__libcpp_db() |
| { |
| if (__cbeg_) |
| { |
| for (__c_node** p = __cbeg_; p != __cend_; ++p) |
| { |
| if (*p != nullptr) |
| { |
| (*p)->~__c_node(); |
| free(*p); |
| } |
| } |
| free(__cbeg_); |
| } |
| if (__ibeg_) |
| { |
| for (__i_node** p = __ibeg_; p != __iend_; ++p) |
| { |
| if (*p != nullptr) |
| { |
| (*p)->~__i_node(); |
| free(*p); |
| } |
| } |
| free(__ibeg_); |
| } |
| } |
| |
| void* |
| __libcpp_db::__find_c_from_i(void* __i) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| RLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database."); |
| return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; |
| } |
| |
| void |
| __libcpp_db::__insert_ic(void* __i, const void* __c) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| if (__cbeg_ == __cend_) |
| return; |
| size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* c = __cbeg_[hc]; |
| if (c == nullptr) |
| return; |
| while (c->__c_ != __c) |
| { |
| c = c->__next_; |
| if (c == nullptr) |
| return; |
| } |
| __i_node* i = __insert_iterator(__i); |
| c->__add(i); |
| i->__c_ = c; |
| } |
| |
| void |
| __libcpp_db::__insert_c(void* __c, __libcpp_db::_InsertConstruct *__fn) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) |
| { |
| size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); |
| __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(__c_node*))); |
| if (cbeg == nullptr) |
| __throw_bad_alloc(); |
| |
| for (__c_node** p = __cbeg_; p != __cend_; ++p) |
| { |
| __c_node* q = *p; |
| while (q != nullptr) |
| { |
| size_t h = hash<void*>()(q->__c_) % nc; |
| __c_node* r = q->__next_; |
| q->__next_ = cbeg[h]; |
| cbeg[h] = q; |
| q = r; |
| } |
| } |
| free(__cbeg_); |
| __cbeg_ = cbeg; |
| __cend_ = __cbeg_ + nc; |
| } |
| size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p = __cbeg_[hc]; |
| void *buf = malloc(sizeof(__c_node)); |
| if (buf == nullptr) |
| __throw_bad_alloc(); |
| __cbeg_[hc] = __fn(buf, __c, p); |
| |
| ++__csz_; |
| } |
| |
| void |
| __libcpp_db::__erase_i(void* __i) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| if (__ibeg_ != __iend_) |
| { |
| size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); |
| __i_node* p = __ibeg_[hi]; |
| if (p != nullptr) |
| { |
| __i_node* q = nullptr; |
| while (p->__i_ != __i) |
| { |
| q = p; |
| p = p->__next_; |
| if (p == nullptr) |
| return; |
| } |
| if (q == nullptr) |
| __ibeg_[hi] = p->__next_; |
| else |
| q->__next_ = p->__next_; |
| __c_node* c = p->__c_; |
| --__isz_; |
| if (c != nullptr) |
| c->__remove(p); |
| free(p); |
| } |
| } |
| } |
| |
| void |
| __libcpp_db::__invalidate_all(void* __c) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| if (__cend_ != __cbeg_) |
| { |
| size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p = __cbeg_[hc]; |
| if (p == nullptr) |
| return; |
| while (p->__c_ != __c) |
| { |
| p = p->__next_; |
| if (p == nullptr) |
| return; |
| } |
| while (p->end_ != p->beg_) |
| { |
| --p->end_; |
| (*p->end_)->__c_ = nullptr; |
| } |
| } |
| } |
| |
| __c_node* |
| __libcpp_db::__find_c_and_lock(void* __c) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| mut().lock(); |
| #endif |
| if (__cend_ == __cbeg_) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| mut().unlock(); |
| #endif |
| return nullptr; |
| } |
| size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p = __cbeg_[hc]; |
| if (p == nullptr) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| mut().unlock(); |
| #endif |
| return nullptr; |
| } |
| while (p->__c_ != __c) |
| { |
| p = p->__next_; |
| if (p == nullptr) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| mut().unlock(); |
| #endif |
| return nullptr; |
| } |
| } |
| return p; |
| } |
| |
| __c_node* |
| __libcpp_db::__find_c(void* __c) const |
| { |
| size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p = __cbeg_[hc]; |
| _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); |
| while (p->__c_ != __c) |
| { |
| p = p->__next_; |
| _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); |
| } |
| return p; |
| } |
| |
| void |
| __libcpp_db::unlock() const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| mut().unlock(); |
| #endif |
| } |
| |
| void |
| __libcpp_db::__erase_c(void* __c) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| if (__cend_ != __cbeg_) |
| { |
| size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p = __cbeg_[hc]; |
| if (p == nullptr) |
| return; |
| __c_node* q = nullptr; |
| _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); |
| while (p->__c_ != __c) |
| { |
| q = p; |
| p = p->__next_; |
| if (p == nullptr) |
| return; |
| _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); |
| } |
| if (q == nullptr) |
| __cbeg_[hc] = p->__next_; |
| else |
| q->__next_ = p->__next_; |
| while (p->end_ != p->beg_) |
| { |
| --p->end_; |
| (*p->end_)->__c_ = nullptr; |
| } |
| free(p->beg_); |
| free(p); |
| --__csz_; |
| } |
| } |
| |
| void |
| __libcpp_db::__iterator_copy(void* __i, const void* __i0) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| __i_node* i0 = __find_iterator(__i0); |
| __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; |
| if (i == nullptr && i0 != nullptr) |
| i = __insert_iterator(__i); |
| __c_node* c = i != nullptr ? i->__c_ : nullptr; |
| if (c != c0) |
| { |
| if (c != nullptr) |
| c->__remove(i); |
| if (i != nullptr) |
| { |
| i->__c_ = nullptr; |
| if (c0 != nullptr) |
| { |
| i->__c_ = c0; |
| i->__c_->__add(i); |
| } |
| } |
| } |
| } |
| |
| bool |
| __libcpp_db::__dereferenceable(const void* __i) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| RLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); |
| } |
| |
| bool |
| __libcpp_db::__decrementable(const void* __i) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| RLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); |
| } |
| |
| bool |
| __libcpp_db::__addable(const void* __i, ptrdiff_t __n) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| RLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); |
| } |
| |
| bool |
| __libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| RLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); |
| } |
| |
| bool |
| __libcpp_db::__less_than_comparable(const void* __i, const void* __j) const |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| RLock _(mut()); |
| #endif |
| __i_node* i = __find_iterator(__i); |
| __i_node* j = __find_iterator(__j); |
| __c_node* ci = i != nullptr ? i->__c_ : nullptr; |
| __c_node* cj = j != nullptr ? j->__c_ : nullptr; |
| return ci == cj; |
| } |
| |
| void |
| __libcpp_db::swap(void* c1, void* c2) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p1 = __cbeg_[hc]; |
| _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); |
| while (p1->__c_ != c1) |
| { |
| p1 = p1->__next_; |
| _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); |
| } |
| hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); |
| __c_node* p2 = __cbeg_[hc]; |
| _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); |
| while (p2->__c_ != c2) |
| { |
| p2 = p2->__next_; |
| _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); |
| } |
| std::swap(p1->beg_, p2->beg_); |
| std::swap(p1->end_, p2->end_); |
| std::swap(p1->cap_, p2->cap_); |
| for (__i_node** p = p1->beg_; p != p1->end_; ++p) |
| (*p)->__c_ = p1; |
| for (__i_node** p = p2->beg_; p != p2->end_; ++p) |
| (*p)->__c_ = p2; |
| } |
| |
| void |
| __libcpp_db::__insert_i(void* __i) |
| { |
| #ifndef _LIBCPP_HAS_NO_THREADS |
| WLock _(mut()); |
| #endif |
| __insert_iterator(__i); |
| } |
| |
| void |
| __c_node::__add(__i_node* i) |
| { |
| if (end_ == cap_) |
| { |
| size_t nc = 2*static_cast<size_t>(cap_ - beg_); |
| if (nc == 0) |
| nc = 1; |
| __i_node** beg = |
| static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); |
| if (beg == nullptr) |
| __throw_bad_alloc(); |
| |
| if (nc > 1) |
| memcpy(beg, beg_, nc/2*sizeof(__i_node*)); |
| free(beg_); |
| beg_ = beg; |
| end_ = beg_ + nc/2; |
| cap_ = beg_ + nc; |
| } |
| *end_++ = i; |
| } |
| |
| // private api |
| |
| _LIBCPP_HIDDEN |
| __i_node* |
| __libcpp_db::__insert_iterator(void* __i) |
| { |
| if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) |
| { |
| size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); |
| __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(__i_node*))); |
| if (ibeg == nullptr) |
| __throw_bad_alloc(); |
| |
| for (__i_node** p = __ibeg_; p != __iend_; ++p) |
| { |
| __i_node* q = *p; |
| while (q != nullptr) |
| { |
| size_t h = hash<void*>()(q->__i_) % nc; |
| __i_node* r = q->__next_; |
| q->__next_ = ibeg[h]; |
| ibeg[h] = q; |
| q = r; |
| } |
| } |
| free(__ibeg_); |
| __ibeg_ = ibeg; |
| __iend_ = __ibeg_ + nc; |
| } |
| size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); |
| __i_node* p = __ibeg_[hi]; |
| __i_node* r = __ibeg_[hi] = |
| static_cast<__i_node*>(malloc(sizeof(__i_node))); |
| if (r == nullptr) |
| __throw_bad_alloc(); |
| |
| ::new(r) __i_node(__i, p, nullptr); |
| ++__isz_; |
| return r; |
| } |
| |
| _LIBCPP_HIDDEN |
| __i_node* |
| __libcpp_db::__find_iterator(const void* __i) const |
| { |
| __i_node* r = nullptr; |
| if (__ibeg_ != __iend_) |
| { |
| size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); |
| for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) |
| { |
| if (nd->__i_ == __i) |
| { |
| r = nd; |
| break; |
| } |
| } |
| } |
| return r; |
| } |
| |
| _LIBCPP_HIDDEN |
| void |
| __c_node::__remove(__i_node* p) |
| { |
| __i_node** r = find(beg_, end_, p); |
| _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); |
| if (--end_ != r) |
| memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); |
| } |
| |
| _LIBCPP_END_NAMESPACE_STD |
