//===-------------------------- debug.cpp ---------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#define _LIBCPP_DEBUG 1
#include "__config"
#include "__debug"
#include "functional"
#include "algorithm"
#include "__hash_table"
#include "mutex"

_LIBCPP_BEGIN_NAMESPACE_STD

_LIBCPP_FUNC_VIS
__libcpp_db*
__get_db()
{
    static __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 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;
}

__c_node*
__libcpp_db::__insert_c(void* __c)
{
#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(void*)));
        if (cbeg == nullptr)
#ifndef _LIBCPP_NO_EXCEPTIONS
            throw bad_alloc();
#else
            abort();
#endif
        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];
    __c_node* r = __cbeg_[hc] =
      static_cast<__c_node*>(malloc(sizeof(__c_node)));
    if (__cbeg_[hc] == nullptr)
#ifndef _LIBCPP_NO_EXCEPTIONS
        throw bad_alloc();
#else
        abort();
#endif
    r->__c_ = __c;
    r->__next_ = p;
    ++__csz_;
    return r;
}

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_;
            free(p);
            --__isz_;
            if (c != nullptr)
                c->__remove(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 != nullptr && 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)
#ifndef _LIBCPP_NO_EXCEPTIONS
            throw bad_alloc();
#else
            abort();
#endif
        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(void*)));
        if (ibeg == nullptr)
#ifndef _LIBCPP_NO_EXCEPTIONS
            throw bad_alloc();
#else
            abort();
#endif
        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)
#ifndef _LIBCPP_NO_EXCEPTIONS
        throw bad_alloc();
#else
        abort();
#endif
    ::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