1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include <__assert>
10#include <__config>
11#include <__debug>
12#include <__hash_table>
13#include <algorithm>
14#include <cstdio>
15#include <functional>
16#include <string>
17
18#ifndef _LIBCPP_HAS_NO_THREADS
19#  include <mutex>
20#  if defined(__ELF__) && defined(_LIBCPP_LINK_PTHREAD_LIB)
21#    pragma comment(lib, "pthread")
22#  endif
23#endif
24
25_LIBCPP_BEGIN_NAMESPACE_STD
26
27_LIBCPP_FUNC_VIS
28__libcpp_db*
29__get_db()
30{
31    static _LIBCPP_NO_DESTROY __libcpp_db db;
32    return &db;
33}
34
35_LIBCPP_FUNC_VIS
36const __libcpp_db*
37__get_const_db()
38{
39    return __get_db();
40}
41
42namespace
43{
44
45#ifndef _LIBCPP_HAS_NO_THREADS
46typedef mutex mutex_type;
47typedef lock_guard<mutex_type> WLock;
48typedef lock_guard<mutex_type> RLock;
49
50mutex_type&
51mut()
52{
53    static _LIBCPP_NO_DESTROY mutex_type m;
54    return m;
55}
56#endif // !_LIBCPP_HAS_NO_THREADS
57
58}  // unnamed namespace
59
60__i_node::~__i_node()
61{
62    if (__next_)
63    {
64        __next_->~__i_node();
65        free(__next_);
66    }
67}
68
69__c_node::~__c_node()
70{
71    free(beg_);
72    if (__next_)
73    {
74        __next_->~__c_node();
75        free(__next_);
76    }
77}
78
79__libcpp_db::__libcpp_db()
80    : __cbeg_(nullptr),
81      __cend_(nullptr),
82      __csz_(0),
83      __ibeg_(nullptr),
84      __iend_(nullptr),
85      __isz_(0)
86{
87}
88
89__libcpp_db::~__libcpp_db()
90{
91    if (__cbeg_)
92    {
93        for (__c_node** p = __cbeg_; p != __cend_; ++p)
94        {
95            if (*p != nullptr)
96            {
97                (*p)->~__c_node();
98                free(*p);
99            }
100        }
101        free(__cbeg_);
102    }
103    if (__ibeg_)
104    {
105        for (__i_node** p = __ibeg_; p != __iend_; ++p)
106        {
107            if (*p != nullptr)
108            {
109                (*p)->~__i_node();
110                free(*p);
111            }
112        }
113        free(__ibeg_);
114    }
115}
116
117void*
118__libcpp_db::__find_c_from_i(void* __i) const
119{
120#ifndef _LIBCPP_HAS_NO_THREADS
121    RLock _(mut());
122#endif
123    __i_node* i = __find_iterator(__i);
124    _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database.");
125    return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
126}
127
128void
129__libcpp_db::__insert_ic(void* __i, const void* __c)
130{
131#ifndef _LIBCPP_HAS_NO_THREADS
132    WLock _(mut());
133#endif
134    if (__cbeg_ == __cend_)
135        return;
136    size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
137    __c_node* c = __cbeg_[hc];
138    if (c == nullptr)
139        return;
140    while (c->__c_ != __c)
141    {
142        c = c->__next_;
143        if (c == nullptr)
144            return;
145    }
146    __i_node* i = __insert_iterator(__i);
147    c->__add(i);
148    i->__c_ = c;
149}
150
151void
152__libcpp_db::__insert_c(void* __c, __libcpp_db::_InsertConstruct *__fn)
153{
154#ifndef _LIBCPP_HAS_NO_THREADS
155    WLock _(mut());
156#endif
157    if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_))
158    {
159        size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1);
160        __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(__c_node*)));
161        if (cbeg == nullptr)
162            __throw_bad_alloc();
163
164        for (__c_node** p = __cbeg_; p != __cend_; ++p)
165        {
166            __c_node* q = *p;
167            while (q != nullptr)
168            {
169                size_t h = hash<void*>()(q->__c_) % nc;
170                __c_node* r = q->__next_;
171                q->__next_ = cbeg[h];
172                cbeg[h] = q;
173                q = r;
174            }
175        }
176        free(__cbeg_);
177        __cbeg_ = cbeg;
178        __cend_ = __cbeg_ + nc;
179    }
180    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
181    __c_node* p = __cbeg_[hc];
182    void *buf = malloc(sizeof(__c_node));
183    if (buf == nullptr)
184      __throw_bad_alloc();
185    __cbeg_[hc] = __fn(buf, __c, p);
186
187    ++__csz_;
188}
189
190void
191__libcpp_db::__erase_i(void* __i)
192{
193#ifndef _LIBCPP_HAS_NO_THREADS
194    WLock _(mut());
195#endif
196    if (__ibeg_ != __iend_)
197    {
198        size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
199        __i_node* p = __ibeg_[hi];
200        if (p != nullptr)
201        {
202            __i_node* q = nullptr;
203            while (p->__i_ != __i)
204            {
205                q = p;
206                p = p->__next_;
207                if (p == nullptr)
208                    return;
209            }
210            if (q == nullptr)
211                __ibeg_[hi] = p->__next_;
212            else
213                q->__next_ = p->__next_;
214            __c_node* c = p->__c_;
215            --__isz_;
216            if (c != nullptr)
217                c->__remove(p);
218            free(p);
219        }
220    }
221}
222
223void
224__libcpp_db::__invalidate_all(void* __c)
225{
226#ifndef _LIBCPP_HAS_NO_THREADS
227    WLock _(mut());
228#endif
229    if (__cend_ != __cbeg_)
230    {
231        size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
232        __c_node* p = __cbeg_[hc];
233        if (p == nullptr)
234            return;
235        while (p->__c_ != __c)
236        {
237            p = p->__next_;
238            if (p == nullptr)
239                return;
240        }
241        while (p->end_ != p->beg_)
242        {
243            --p->end_;
244            (*p->end_)->__c_ = nullptr;
245        }
246    }
247}
248
249__c_node*
250__libcpp_db::__find_c_and_lock(void* __c) const
251{
252#ifndef _LIBCPP_HAS_NO_THREADS
253    mut().lock();
254#endif
255    if (__cend_ == __cbeg_)
256    {
257#ifndef _LIBCPP_HAS_NO_THREADS
258        mut().unlock();
259#endif
260        return nullptr;
261    }
262    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
263    __c_node* p = __cbeg_[hc];
264    if (p == nullptr)
265    {
266#ifndef _LIBCPP_HAS_NO_THREADS
267        mut().unlock();
268#endif
269        return nullptr;
270    }
271    while (p->__c_ != __c)
272    {
273        p = p->__next_;
274        if (p == nullptr)
275        {
276#ifndef _LIBCPP_HAS_NO_THREADS
277            mut().unlock();
278#endif
279            return nullptr;
280        }
281    }
282    return p;
283}
284
285__c_node*
286__libcpp_db::__find_c(void* __c) const
287{
288    size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
289    __c_node* p = __cbeg_[hc];
290    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A");
291    while (p->__c_ != __c)
292    {
293        p = p->__next_;
294        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B");
295    }
296    return p;
297}
298
299void
300__libcpp_db::unlock() const
301{
302#ifndef _LIBCPP_HAS_NO_THREADS
303    mut().unlock();
304#endif
305}
306
307void
308__libcpp_db::__erase_c(void* __c)
309{
310#ifndef _LIBCPP_HAS_NO_THREADS
311    WLock _(mut());
312#endif
313    if (__cend_ != __cbeg_)
314    {
315        size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_);
316        __c_node* p = __cbeg_[hc];
317        if (p == nullptr)
318            return;
319        __c_node* q = nullptr;
320        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
321        while (p->__c_ != __c)
322        {
323            q = p;
324            p = p->__next_;
325            if (p == nullptr)
326                return;
327            _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
328        }
329        if (q == nullptr)
330            __cbeg_[hc] = p->__next_;
331        else
332            q->__next_ = p->__next_;
333        while (p->end_ != p->beg_)
334        {
335            --p->end_;
336            (*p->end_)->__c_ = nullptr;
337        }
338        free(p->beg_);
339        free(p);
340        --__csz_;
341    }
342}
343
344void
345__libcpp_db::__iterator_copy(void* __i, const void* __i0)
346{
347#ifndef _LIBCPP_HAS_NO_THREADS
348    WLock _(mut());
349#endif
350    __i_node* i = __find_iterator(__i);
351    __i_node* i0 = __find_iterator(__i0);
352    __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
353    if (i == nullptr && i0 != nullptr)
354        i = __insert_iterator(__i);
355    __c_node* c = i != nullptr ? i->__c_ : nullptr;
356    if (c != c0)
357    {
358        if (c != nullptr)
359            c->__remove(i);
360        if (i != nullptr)
361        {
362            i->__c_ = nullptr;
363            if (c0 != nullptr)
364            {
365                i->__c_ = c0;
366                i->__c_->__add(i);
367            }
368        }
369    }
370}
371
372bool
373__libcpp_db::__dereferenceable(const void* __i) const
374{
375#ifndef _LIBCPP_HAS_NO_THREADS
376    RLock _(mut());
377#endif
378    __i_node* i = __find_iterator(__i);
379    return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
380}
381
382bool
383__libcpp_db::__decrementable(const void* __i) const
384{
385#ifndef _LIBCPP_HAS_NO_THREADS
386    RLock _(mut());
387#endif
388    __i_node* i = __find_iterator(__i);
389    return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
390}
391
392bool
393__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
394{
395#ifndef _LIBCPP_HAS_NO_THREADS
396    RLock _(mut());
397#endif
398    __i_node* i = __find_iterator(__i);
399    return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
400}
401
402bool
403__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
404{
405#ifndef _LIBCPP_HAS_NO_THREADS
406    RLock _(mut());
407#endif
408    __i_node* i = __find_iterator(__i);
409    return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
410}
411
412bool
413__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const
414{
415#ifndef _LIBCPP_HAS_NO_THREADS
416    RLock _(mut());
417#endif
418    __i_node* i = __find_iterator(__i);
419    __i_node* j = __find_iterator(__j);
420    __c_node* ci = i != nullptr ? i->__c_ : nullptr;
421    __c_node* cj = j != nullptr ? j->__c_ : nullptr;
422    return ci == cj;
423}
424
425void
426__libcpp_db::swap(void* c1, void* c2)
427{
428#ifndef _LIBCPP_HAS_NO_THREADS
429    WLock _(mut());
430#endif
431    size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_);
432    __c_node* p1 = __cbeg_[hc];
433    _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
434    while (p1->__c_ != c1)
435    {
436        p1 = p1->__next_;
437        _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
438    }
439    hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_);
440    __c_node* p2 = __cbeg_[hc];
441    _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
442    while (p2->__c_ != c2)
443    {
444        p2 = p2->__next_;
445        _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
446    }
447    std::swap(p1->beg_, p2->beg_);
448    std::swap(p1->end_, p2->end_);
449    std::swap(p1->cap_, p2->cap_);
450    for (__i_node** p = p1->beg_; p != p1->end_; ++p)
451        (*p)->__c_ = p1;
452    for (__i_node** p = p2->beg_; p != p2->end_; ++p)
453        (*p)->__c_ = p2;
454}
455
456void
457__libcpp_db::__insert_i(void* __i)
458{
459#ifndef _LIBCPP_HAS_NO_THREADS
460    WLock _(mut());
461#endif
462    __insert_iterator(__i);
463}
464
465void
466__c_node::__add(__i_node* i)
467{
468    if (end_ == cap_)
469    {
470        size_t nc = 2*static_cast<size_t>(cap_ - beg_);
471        if (nc == 0)
472            nc = 1;
473        __i_node** beg =
474           static_cast<__i_node**>(malloc(nc * sizeof(__i_node*)));
475        if (beg == nullptr)
476            __throw_bad_alloc();
477
478        if (nc > 1)
479            memcpy(beg, beg_, nc/2*sizeof(__i_node*));
480        free(beg_);
481        beg_ = beg;
482        end_ = beg_ + nc/2;
483        cap_ = beg_ + nc;
484    }
485    *end_++ = i;
486}
487
488// private api
489
490_LIBCPP_HIDDEN
491__i_node*
492__libcpp_db::__insert_iterator(void* __i)
493{
494    if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_))
495    {
496        size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1);
497        __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(__i_node*)));
498        if (ibeg == nullptr)
499            __throw_bad_alloc();
500
501        for (__i_node** p = __ibeg_; p != __iend_; ++p)
502        {
503            __i_node* q = *p;
504            while (q != nullptr)
505            {
506                size_t h = hash<void*>()(q->__i_) % nc;
507                __i_node* r = q->__next_;
508                q->__next_ = ibeg[h];
509                ibeg[h] = q;
510                q = r;
511            }
512        }
513        free(__ibeg_);
514        __ibeg_ = ibeg;
515        __iend_ = __ibeg_ + nc;
516    }
517    size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
518    __i_node* p = __ibeg_[hi];
519    __i_node* r = __ibeg_[hi] =
520      static_cast<__i_node*>(malloc(sizeof(__i_node)));
521    if (r == nullptr)
522        __throw_bad_alloc();
523
524    ::new(r) __i_node(__i, p, nullptr);
525    ++__isz_;
526    return r;
527}
528
529_LIBCPP_HIDDEN
530__i_node*
531__libcpp_db::__find_iterator(const void* __i) const
532{
533    __i_node* r = nullptr;
534    if (__ibeg_ != __iend_)
535    {
536        size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_);
537        for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
538        {
539            if (nd->__i_ == __i)
540            {
541                r = nd;
542                break;
543            }
544        }
545    }
546    return r;
547}
548
549_LIBCPP_HIDDEN
550void
551__c_node::__remove(__i_node* p)
552{
553    __i_node** r = find(beg_, end_, p);
554    _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove");
555    if (--end_ != r)
556        memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*));
557}
558
559_LIBCPP_END_NAMESPACE_STD
560