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