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