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*
__get_db()29 __get_db()
30 {
31 static _LIBCPP_NO_DESTROY __libcpp_db db;
32 return &db;
33 }
34
35 _LIBCPP_FUNC_VIS
36 const __libcpp_db*
__get_const_db()37 __get_const_db()
38 {
39 return __get_db();
40 }
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&
mut()51 mut()
52 {
53 static _LIBCPP_NO_DESTROY mutex_type m;
54 return m;
55 }
56 #endif // !_LIBCPP_HAS_NO_THREADS
57
58 } // unnamed namespace
59
~__i_node()60 __i_node::~__i_node()
61 {
62 if (__next_)
63 {
64 __next_->~__i_node();
65 free(__next_);
66 }
67 }
68
~__c_node()69 __c_node::~__c_node()
70 {
71 free(beg_);
72 if (__next_)
73 {
74 __next_->~__c_node();
75 free(__next_);
76 }
77 }
78
__libcpp_db()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
~__libcpp_db()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
117 void*
__find_c_from_i(void * __i) const118 __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
128 void
__insert_ic(void * __i,const void * __c)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
151 void
__insert_c(void * __c,__libcpp_db::_InsertConstruct * __fn)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
190 void
__erase_i(void * __i)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
223 void
__invalidate_all(void * __c)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*
__find_c_and_lock(void * __c) const250 __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*
__find_c(void * __c) const286 __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
299 void
unlock() const300 __libcpp_db::unlock() const
301 {
302 #ifndef _LIBCPP_HAS_NO_THREADS
303 mut().unlock();
304 #endif
305 }
306
307 void
__erase_c(void * __c)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
344 void
__iterator_copy(void * __i,const void * __i0)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
372 bool
__dereferenceable(const void * __i) const373 __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
382 bool
__decrementable(const void * __i) const383 __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
392 bool
__addable(const void * __i,ptrdiff_t __n) const393 __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
402 bool
__subscriptable(const void * __i,ptrdiff_t __n) const403 __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
412 bool
__less_than_comparable(const void * __i,const void * __j) const413 __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
425 void
swap(void * c1,void * c2)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
456 void
__insert_i(void * __i)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
465 void
__add(__i_node * i)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*
__insert_iterator(void * __i)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*
__find_iterator(const void * __i) const531 __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
550 void
__remove(__i_node * p)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