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
what() const25 std::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 }
__libcpp_abort_debug_function(__libcpp_debug_info const & info)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
__libcpp_set_debug_function(__libcpp_debug_function_type __func)41 bool __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*
__get_db()48 __get_db()
49 {
50 static _LIBCPP_NO_DESTROY __libcpp_db db;
51 return &db;
52 }
53
54 _LIBCPP_FUNC_VIS
55 const __libcpp_db*
__get_const_db()56 __get_const_db()
57 {
58 return __get_db();
59 }
60
61 namespace
62 {
63
64 #ifndef _LIBCPP_HAS_NO_THREADS
65 typedef mutex mutex_type;
66 typedef lock_guard<mutex_type> WLock;
67 typedef lock_guard<mutex_type> RLock;
68
69 mutex_type&
mut()70 mut()
71 {
72 static _LIBCPP_NO_DESTROY mutex_type m;
73 return m;
74 }
75 #endif // !_LIBCPP_HAS_NO_THREADS
76
77 } // unnamed namespace
78
~__i_node()79 __i_node::~__i_node()
80 {
81 if (__next_)
82 {
83 __next_->~__i_node();
84 free(__next_);
85 }
86 }
87
~__c_node()88 __c_node::~__c_node()
89 {
90 free(beg_);
91 if (__next_)
92 {
93 __next_->~__c_node();
94 free(__next_);
95 }
96 }
97
__libcpp_db()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
~__libcpp_db()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
136 void*
__find_c_from_i(void * __i) const137 __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
147 void
__insert_ic(void * __i,const void * __c)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
170 void
__insert_c(void * __c,__libcpp_db::_InsertConstruct * __fn)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
209 void
__erase_i(void * __i)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
242 void
__invalidate_all(void * __c)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*
__find_c_and_lock(void * __c) const269 __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*
__find_c(void * __c) const305 __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
318 void
unlock() const319 __libcpp_db::unlock() const
320 {
321 #ifndef _LIBCPP_HAS_NO_THREADS
322 mut().unlock();
323 #endif
324 }
325
326 void
__erase_c(void * __c)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
363 void
__iterator_copy(void * __i,const void * __i0)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
391 bool
__dereferenceable(const void * __i) const392 __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
401 bool
__decrementable(const void * __i) const402 __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
411 bool
__addable(const void * __i,ptrdiff_t __n) const412 __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
421 bool
__subscriptable(const void * __i,ptrdiff_t __n) const422 __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
431 bool
__less_than_comparable(const void * __i,const void * __j) const432 __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
444 void
swap(void * c1,void * c2)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
475 void
__insert_i(void * __i)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
484 void
__add(__i_node * i)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*
__insert_iterator(void * __i)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*
__find_iterator(const void * __i) const550 __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
569 void
__remove(__i_node * p)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