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* 29__get_db() 30{ 31 static _LIBCPP_NO_DESTROY __libcpp_db db; 32 return &db; 33} 34 35_LIBCPP_FUNC_VIS 36const __libcpp_db* 37__get_const_db() 38{ 39 return __get_db(); 40} 41 42namespace 43{ 44 45#ifndef _LIBCPP_HAS_NO_THREADS 46typedef mutex mutex_type; 47typedef lock_guard<mutex_type> WLock; 48typedef lock_guard<mutex_type> RLock; 49 50mutex_type& 51mut() 52{ 53 static _LIBCPP_NO_DESTROY mutex_type m; 54 return m; 55} 56#endif // !_LIBCPP_HAS_NO_THREADS 57 58} // unnamed namespace 59 60__i_node::~__i_node() 61{ 62 if (__next_) 63 { 64 __next_->~__i_node(); 65 free(__next_); 66 } 67} 68 69__c_node::~__c_node() 70{ 71 free(beg_); 72 if (__next_) 73 { 74 __next_->~__c_node(); 75 free(__next_); 76 } 77} 78 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 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 117void* 118__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 128void 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 151void 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 190void 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 223void 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* 250__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* 286__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 299void 300__libcpp_db::unlock() const 301{ 302#ifndef _LIBCPP_HAS_NO_THREADS 303 mut().unlock(); 304#endif 305} 306 307void 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 344void 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 372bool 373__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 382bool 383__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 392bool 393__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 402bool 403__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 412bool 413__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 425void 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 456void 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 465void 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* 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* 531__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 550void 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