Coverage Report

Created: 2022-05-17 06:19

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