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