//===----------------------------------------------------------------------===//

//

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