1 //===-------------------------- debug.cpp ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define _LIBCPP_DEBUG 1
15 #include "__hash_table"
18 _LIBCPP_BEGIN_NAMESPACE_STD
24 static __libcpp_db db
;
38 #ifndef _LIBCPP_HAS_NO_THREADS
39 typedef mutex mutex_type
;
40 typedef lock_guard
<mutex_type
> WLock
;
41 typedef lock_guard
<mutex_type
> RLock
;
49 #endif // !_LIBCPP_HAS_NO_THREADS
51 } // unnamed namespace
72 __libcpp_db::__libcpp_db()
82 __libcpp_db::~__libcpp_db()
86 for (__c_node
** p
= __cbeg_
; p
!= __cend_
; ++p
)
98 for (__i_node
** p
= __ibeg_
; p
!= __iend_
; ++p
)
111 __libcpp_db::__find_c_from_i(void* __i
) const
113 #ifndef _LIBCPP_HAS_NO_THREADS
116 __i_node
* i
= __find_iterator(__i
);
117 _LIBCPP_ASSERT(i
!= nullptr, "iterator not found in debug database.");
118 return i
->__c_
!= nullptr ? i
->__c_
->__c_
: nullptr;
122 __libcpp_db::__insert_ic(void* __i
, const void* __c
)
124 #ifndef _LIBCPP_HAS_NO_THREADS
127 if (__cbeg_
== __cend_
)
129 size_t hc
= hash
<const void*>()(__c
) % static_cast<size_t>(__cend_
- __cbeg_
);
130 __c_node
* c
= __cbeg_
[hc
];
133 while (c
->__c_
!= __c
)
139 __i_node
* i
= __insert_iterator(__i
);
145 __libcpp_db::__insert_c(void* __c
)
147 #ifndef _LIBCPP_HAS_NO_THREADS
150 if (__csz_
+ 1 > static_cast<size_t>(__cend_
- __cbeg_
))
152 size_t nc
= __next_prime(2*static_cast<size_t>(__cend_
- __cbeg_
) + 1);
153 __c_node
** cbeg
= static_cast<__c_node
**>(calloc(nc
, sizeof(void*)));
155 #ifndef _LIBCPP_NO_EXCEPTIONS
160 for (__c_node
** p
= __cbeg_
; p
!= __cend_
; ++p
)
165 size_t h
= hash
<void*>()(q
->__c_
) % nc
;
166 __c_node
* r
= q
->__next_
;
167 q
->__next_
= cbeg
[h
];
174 __cend_
= __cbeg_
+ nc
;
176 size_t hc
= hash
<void*>()(__c
) % static_cast<size_t>(__cend_
- __cbeg_
);
177 __c_node
* p
= __cbeg_
[hc
];
178 __c_node
* r
= __cbeg_
[hc
] =
179 static_cast<__c_node
*>(malloc(sizeof(__c_node
)));
180 if (__cbeg_
[hc
] == nullptr)
181 #ifndef _LIBCPP_NO_EXCEPTIONS
193 __libcpp_db::__erase_i(void* __i
)
195 #ifndef _LIBCPP_HAS_NO_THREADS
198 if (__ibeg_
!= __iend_
)
200 size_t hi
= hash
<void*>()(__i
) % static_cast<size_t>(__iend_
- __ibeg_
);
201 __i_node
* p
= __ibeg_
[hi
];
204 __i_node
* q
= nullptr;
205 while (p
->__i_
!= __i
)
213 __ibeg_
[hi
] = p
->__next_
;
215 q
->__next_
= p
->__next_
;
216 __c_node
* c
= p
->__c_
;
226 __libcpp_db::__invalidate_all(void* __c
)
228 #ifndef _LIBCPP_HAS_NO_THREADS
231 if (__cend_
!= __cbeg_
)
233 size_t hc
= hash
<void*>()(__c
) % static_cast<size_t>(__cend_
- __cbeg_
);
234 __c_node
* p
= __cbeg_
[hc
];
237 while (p
->__c_
!= __c
)
243 while (p
->end_
!= p
->beg_
)
246 (*p
->end_
)->__c_
= nullptr;
252 __libcpp_db::__find_c_and_lock(void* __c
) const
254 #ifndef _LIBCPP_HAS_NO_THREADS
257 if (__cend_
== __cbeg_
)
259 #ifndef _LIBCPP_HAS_NO_THREADS
264 size_t hc
= hash
<void*>()(__c
) % static_cast<size_t>(__cend_
- __cbeg_
);
265 __c_node
* p
= __cbeg_
[hc
];
268 #ifndef _LIBCPP_HAS_NO_THREADS
273 while (p
->__c_
!= __c
)
278 #ifndef _LIBCPP_HAS_NO_THREADS
288 __libcpp_db::__find_c(void* __c
) const
290 size_t hc
= hash
<void*>()(__c
) % static_cast<size_t>(__cend_
- __cbeg_
);
291 __c_node
* p
= __cbeg_
[hc
];
292 _LIBCPP_ASSERT(p
!= nullptr, "debug mode internal logic error __find_c A");
293 while (p
->__c_
!= __c
)
296 _LIBCPP_ASSERT(p
!= nullptr, "debug mode internal logic error __find_c B");
302 __libcpp_db::unlock() const
304 #ifndef _LIBCPP_HAS_NO_THREADS
310 __libcpp_db::__erase_c(void* __c
)
312 #ifndef _LIBCPP_HAS_NO_THREADS
315 if (__cend_
!= __cbeg_
)
317 size_t hc
= hash
<void*>()(__c
) % static_cast<size_t>(__cend_
- __cbeg_
);
318 __c_node
* p
= __cbeg_
[hc
];
321 __c_node
* q
= nullptr;
322 _LIBCPP_ASSERT(p
!= nullptr, "debug mode internal logic error __erase_c A");
323 while (p
->__c_
!= __c
)
329 _LIBCPP_ASSERT(p
!= nullptr, "debug mode internal logic error __erase_c B");
332 __cbeg_
[hc
] = p
->__next_
;
334 q
->__next_
= p
->__next_
;
335 while (p
->end_
!= p
->beg_
)
338 (*p
->end_
)->__c_
= nullptr;
347 __libcpp_db::__iterator_copy(void* __i
, const void* __i0
)
349 #ifndef _LIBCPP_HAS_NO_THREADS
352 __i_node
* i
= __find_iterator(__i
);
353 __i_node
* i0
= __find_iterator(__i0
);
354 __c_node
* c0
= i0
!= nullptr ? i0
->__c_
: nullptr;
355 if (i
== nullptr && i0
!= nullptr)
356 i
= __insert_iterator(__i
);
357 __c_node
* c
= i
!= nullptr ? i
->__c_
: nullptr;
375 __libcpp_db::__dereferenceable(const void* __i
) const
377 #ifndef _LIBCPP_HAS_NO_THREADS
380 __i_node
* i
= __find_iterator(__i
);
381 return i
!= nullptr && i
->__c_
!= nullptr && i
->__c_
->__dereferenceable(__i
);
385 __libcpp_db::__decrementable(const void* __i
) const
387 #ifndef _LIBCPP_HAS_NO_THREADS
390 __i_node
* i
= __find_iterator(__i
);
391 return i
!= nullptr && i
->__c_
!= nullptr && i
->__c_
->__decrementable(__i
);
395 __libcpp_db::__addable(const void* __i
, ptrdiff_t __n
) const
397 #ifndef _LIBCPP_HAS_NO_THREADS
400 __i_node
* i
= __find_iterator(__i
);
401 return i
!= nullptr && i
->__c_
!= nullptr && i
->__c_
->__addable(__i
, __n
);
405 __libcpp_db::__subscriptable(const void* __i
, ptrdiff_t __n
) const
407 #ifndef _LIBCPP_HAS_NO_THREADS
410 __i_node
* i
= __find_iterator(__i
);
411 return i
!= nullptr && i
->__c_
!= nullptr && i
->__c_
->__subscriptable(__i
, __n
);
415 __libcpp_db::__less_than_comparable(const void* __i
, const void* __j
) const
417 #ifndef _LIBCPP_HAS_NO_THREADS
420 __i_node
* i
= __find_iterator(__i
);
421 __i_node
* j
= __find_iterator(__j
);
422 __c_node
* ci
= i
!= nullptr ? i
->__c_
: nullptr;
423 __c_node
* cj
= j
!= nullptr ? j
->__c_
: nullptr;
424 return ci
!= nullptr && ci
== cj
;
428 __libcpp_db::swap(void* c1
, void* c2
)
430 #ifndef _LIBCPP_HAS_NO_THREADS
433 size_t hc
= hash
<void*>()(c1
) % static_cast<size_t>(__cend_
- __cbeg_
);
434 __c_node
* p1
= __cbeg_
[hc
];
435 _LIBCPP_ASSERT(p1
!= nullptr, "debug mode internal logic error swap A");
436 while (p1
->__c_
!= c1
)
439 _LIBCPP_ASSERT(p1
!= nullptr, "debug mode internal logic error swap B");
441 hc
= hash
<void*>()(c2
) % static_cast<size_t>(__cend_
- __cbeg_
);
442 __c_node
* p2
= __cbeg_
[hc
];
443 _LIBCPP_ASSERT(p2
!= nullptr, "debug mode internal logic error swap C");
444 while (p2
->__c_
!= c2
)
447 _LIBCPP_ASSERT(p2
!= nullptr, "debug mode internal logic error swap D");
449 std::swap(p1
->beg_
, p2
->beg_
);
450 std::swap(p1
->end_
, p2
->end_
);
451 std::swap(p1
->cap_
, p2
->cap_
);
452 for (__i_node
** p
= p1
->beg_
; p
!= p1
->end_
; ++p
)
454 for (__i_node
** p
= p2
->beg_
; p
!= p2
->end_
; ++p
)
459 __libcpp_db::__insert_i(void* __i
)
461 #ifndef _LIBCPP_HAS_NO_THREADS
464 __insert_iterator(__i
);
468 __c_node::__add(__i_node
* i
)
472 size_t nc
= 2*static_cast<size_t>(cap_
- beg_
);
476 static_cast<__i_node
**>(malloc(nc
* sizeof(__i_node
*)));
478 #ifndef _LIBCPP_NO_EXCEPTIONS
484 memcpy(beg
, beg_
, nc
/2*sizeof(__i_node
*));
497 __libcpp_db::__insert_iterator(void* __i
)
499 if (__isz_
+ 1 > static_cast<size_t>(__iend_
- __ibeg_
))
501 size_t nc
= __next_prime(2*static_cast<size_t>(__iend_
- __ibeg_
) + 1);
502 __i_node
** ibeg
= static_cast<__i_node
**>(calloc(nc
, sizeof(void*)));
504 #ifndef _LIBCPP_NO_EXCEPTIONS
509 for (__i_node
** p
= __ibeg_
; p
!= __iend_
; ++p
)
514 size_t h
= hash
<void*>()(q
->__i_
) % nc
;
515 __i_node
* r
= q
->__next_
;
516 q
->__next_
= ibeg
[h
];
523 __iend_
= __ibeg_
+ nc
;
525 size_t hi
= hash
<void*>()(__i
) % static_cast<size_t>(__iend_
- __ibeg_
);
526 __i_node
* p
= __ibeg_
[hi
];
527 __i_node
* r
= __ibeg_
[hi
] =
528 static_cast<__i_node
*>(malloc(sizeof(__i_node
)));
530 #ifndef _LIBCPP_NO_EXCEPTIONS
535 ::new(r
) __i_node(__i
, p
, nullptr);
542 __libcpp_db::__find_iterator(const void* __i
) const
544 __i_node
* r
= nullptr;
545 if (__ibeg_
!= __iend_
)
547 size_t h
= hash
<const void*>()(__i
) % static_cast<size_t>(__iend_
- __ibeg_
);
548 for (__i_node
* nd
= __ibeg_
[h
]; nd
!= nullptr; nd
= nd
->__next_
)
562 __c_node::__remove(__i_node
* p
)
564 __i_node
** r
= find(beg_
, end_
, p
);
565 _LIBCPP_ASSERT(r
!= end_
, "debug mode internal logic error __c_node::__remove");
567 memmove(r
, r
+1, static_cast<size_t>(end_
- r
)*sizeof(__i_node
*));
570 _LIBCPP_END_NAMESPACE_STD