1227825Stheraven//===-------------------------- debug.cpp ---------------------------------===// 2227825Stheraven// 3227825Stheraven// The LLVM Compiler Infrastructure 4227825Stheraven// 5227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 6227825Stheraven// Source Licenses. See LICENSE.TXT for details. 7227825Stheraven// 8227825Stheraven//===----------------------------------------------------------------------===// 9227825Stheraven 10262801Sdim#define _LIBCPP_DEBUG 1 11227825Stheraven#include "__config" 12227825Stheraven#include "__debug" 13227825Stheraven#include "functional" 14227825Stheraven#include "algorithm" 15227825Stheraven#include "__hash_table" 16227825Stheraven#include "mutex" 17227825Stheraven 18227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 19227825Stheraven 20249998Sdim_LIBCPP_FUNC_VIS 21227825Stheraven__libcpp_db* 22227825Stheraven__get_db() 23227825Stheraven{ 24227825Stheraven static __libcpp_db db; 25227825Stheraven return &db; 26246487Stheraven} 27227825Stheraven 28249998Sdim_LIBCPP_FUNC_VIS 29227825Stheravenconst __libcpp_db* 30227825Stheraven__get_const_db() 31227825Stheraven{ 32227825Stheraven return __get_db(); 33227825Stheraven} 34227825Stheraven 35227825Stheravennamespace 36227825Stheraven{ 37227825Stheraven 38278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 39227825Stheraventypedef mutex mutex_type; 40227825Stheraventypedef lock_guard<mutex_type> WLock; 41227825Stheraventypedef lock_guard<mutex_type> RLock; 42227825Stheraven 43227825Stheravenmutex_type& 44227825Stheravenmut() 45227825Stheraven{ 46227825Stheraven static mutex_type m; 47227825Stheraven return m; 48227825Stheraven} 49278724Sdim#endif // !_LIBCPP_HAS_NO_THREADS 50227825Stheraven 51227825Stheraven} // unnamed namespace 52227825Stheraven 53227825Stheraven__i_node::~__i_node() 54227825Stheraven{ 55227825Stheraven if (__next_) 56227825Stheraven { 57227825Stheraven __next_->~__i_node(); 58227825Stheraven free(__next_); 59227825Stheraven } 60227825Stheraven} 61227825Stheraven 62227825Stheraven__c_node::~__c_node() 63227825Stheraven{ 64227825Stheraven free(beg_); 65227825Stheraven if (__next_) 66227825Stheraven { 67227825Stheraven __next_->~__c_node(); 68227825Stheraven free(__next_); 69227825Stheraven } 70227825Stheraven} 71227825Stheraven 72227825Stheraven__libcpp_db::__libcpp_db() 73227825Stheraven : __cbeg_(nullptr), 74227825Stheraven __cend_(nullptr), 75227825Stheraven __csz_(0), 76227825Stheraven __ibeg_(nullptr), 77227825Stheraven __iend_(nullptr), 78227825Stheraven __isz_(0) 79227825Stheraven{ 80227825Stheraven} 81227825Stheraven 82227825Stheraven__libcpp_db::~__libcpp_db() 83227825Stheraven{ 84227825Stheraven if (__cbeg_) 85227825Stheraven { 86227825Stheraven for (__c_node** p = __cbeg_; p != __cend_; ++p) 87227825Stheraven { 88227825Stheraven if (*p != nullptr) 89227825Stheraven { 90227825Stheraven (*p)->~__c_node(); 91227825Stheraven free(*p); 92227825Stheraven } 93227825Stheraven } 94227825Stheraven free(__cbeg_); 95227825Stheraven } 96227825Stheraven if (__ibeg_) 97227825Stheraven { 98227825Stheraven for (__i_node** p = __ibeg_; p != __iend_; ++p) 99227825Stheraven { 100227825Stheraven if (*p != nullptr) 101227825Stheraven { 102227825Stheraven (*p)->~__i_node(); 103227825Stheraven free(*p); 104227825Stheraven } 105227825Stheraven } 106227825Stheraven free(__ibeg_); 107227825Stheraven } 108227825Stheraven} 109227825Stheraven 110227825Stheravenvoid* 111227825Stheraven__libcpp_db::__find_c_from_i(void* __i) const 112227825Stheraven{ 113278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 114227825Stheraven RLock _(mut()); 115278724Sdim#endif 116227825Stheraven __i_node* i = __find_iterator(__i); 117249998Sdim _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database."); 118227825Stheraven return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; 119227825Stheraven} 120227825Stheraven 121227825Stheravenvoid 122227825Stheraven__libcpp_db::__insert_ic(void* __i, const void* __c) 123227825Stheraven{ 124278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 125227825Stheraven WLock _(mut()); 126278724Sdim#endif 127262801Sdim if (__cbeg_ == __cend_) 128262801Sdim return; 129232950Stheraven size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 130227825Stheraven __c_node* c = __cbeg_[hc]; 131262801Sdim if (c == nullptr) 132262801Sdim return; 133227825Stheraven while (c->__c_ != __c) 134227825Stheraven { 135227825Stheraven c = c->__next_; 136262801Sdim if (c == nullptr) 137262801Sdim return; 138227825Stheraven } 139262801Sdim __i_node* i = __insert_iterator(__i); 140227825Stheraven c->__add(i); 141227825Stheraven i->__c_ = c; 142227825Stheraven} 143227825Stheraven 144227825Stheraven__c_node* 145227825Stheraven__libcpp_db::__insert_c(void* __c) 146227825Stheraven{ 147278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 148227825Stheraven WLock _(mut()); 149278724Sdim#endif 150232950Stheraven if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 151227825Stheraven { 152232950Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 153253159Stheraven __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*))); 154227825Stheraven if (cbeg == nullptr) 155241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 156227825Stheraven throw bad_alloc(); 157241903Sdim#else 158241903Sdim abort(); 159241903Sdim#endif 160227825Stheraven for (__c_node** p = __cbeg_; p != __cend_; ++p) 161227825Stheraven { 162227825Stheraven __c_node* q = *p; 163227825Stheraven while (q != nullptr) 164227825Stheraven { 165227825Stheraven size_t h = hash<void*>()(q->__c_) % nc; 166227825Stheraven __c_node* r = q->__next_; 167227825Stheraven q->__next_ = cbeg[h]; 168227825Stheraven cbeg[h] = q; 169227825Stheraven q = r; 170227825Stheraven } 171227825Stheraven } 172227825Stheraven free(__cbeg_); 173227825Stheraven __cbeg_ = cbeg; 174227825Stheraven __cend_ = __cbeg_ + nc; 175227825Stheraven } 176232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 177227825Stheraven __c_node* p = __cbeg_[hc]; 178253159Stheraven __c_node* r = __cbeg_[hc] = 179253159Stheraven static_cast<__c_node*>(malloc(sizeof(__c_node))); 180227825Stheraven if (__cbeg_[hc] == nullptr) 181241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 182227825Stheraven throw bad_alloc(); 183241903Sdim#else 184241903Sdim abort(); 185241903Sdim#endif 186227825Stheraven r->__c_ = __c; 187227825Stheraven r->__next_ = p; 188227825Stheraven ++__csz_; 189227825Stheraven return r; 190227825Stheraven} 191227825Stheraven 192227825Stheravenvoid 193227825Stheraven__libcpp_db::__erase_i(void* __i) 194227825Stheraven{ 195278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 196227825Stheraven WLock _(mut()); 197278724Sdim#endif 198227825Stheraven if (__ibeg_ != __iend_) 199227825Stheraven { 200232950Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 201227825Stheraven __i_node* p = __ibeg_[hi]; 202227825Stheraven if (p != nullptr) 203227825Stheraven { 204227825Stheraven __i_node* q = nullptr; 205227825Stheraven while (p->__i_ != __i) 206227825Stheraven { 207227825Stheraven q = p; 208227825Stheraven p = p->__next_; 209227825Stheraven if (p == nullptr) 210227825Stheraven return; 211227825Stheraven } 212227825Stheraven if (q == nullptr) 213227825Stheraven __ibeg_[hi] = p->__next_; 214227825Stheraven else 215227825Stheraven q->__next_ = p->__next_; 216227825Stheraven __c_node* c = p->__c_; 217227825Stheraven free(p); 218227825Stheraven --__isz_; 219227825Stheraven if (c != nullptr) 220227825Stheraven c->__remove(p); 221227825Stheraven } 222227825Stheraven } 223227825Stheraven} 224227825Stheraven 225227825Stheravenvoid 226227825Stheraven__libcpp_db::__invalidate_all(void* __c) 227227825Stheraven{ 228278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 229227825Stheraven WLock _(mut()); 230278724Sdim#endif 231262801Sdim if (__cend_ != __cbeg_) 232227825Stheraven { 233262801Sdim size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 234262801Sdim __c_node* p = __cbeg_[hc]; 235262801Sdim if (p == nullptr) 236262801Sdim return; 237262801Sdim while (p->__c_ != __c) 238262801Sdim { 239262801Sdim p = p->__next_; 240262801Sdim if (p == nullptr) 241262801Sdim return; 242262801Sdim } 243262801Sdim while (p->end_ != p->beg_) 244262801Sdim { 245262801Sdim --p->end_; 246262801Sdim (*p->end_)->__c_ = nullptr; 247262801Sdim } 248227825Stheraven } 249227825Stheraven} 250227825Stheraven 251227825Stheraven__c_node* 252227825Stheraven__libcpp_db::__find_c_and_lock(void* __c) const 253227825Stheraven{ 254278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 255227825Stheraven mut().lock(); 256278724Sdim#endif 257262801Sdim if (__cend_ == __cbeg_) 258262801Sdim { 259278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 260262801Sdim mut().unlock(); 261278724Sdim#endif 262262801Sdim return nullptr; 263262801Sdim } 264232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 265227825Stheraven __c_node* p = __cbeg_[hc]; 266262801Sdim if (p == nullptr) 267262801Sdim { 268278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 269262801Sdim mut().unlock(); 270278724Sdim#endif 271262801Sdim return nullptr; 272262801Sdim } 273227825Stheraven while (p->__c_ != __c) 274227825Stheraven { 275227825Stheraven p = p->__next_; 276262801Sdim if (p == nullptr) 277262801Sdim { 278278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 279262801Sdim mut().unlock(); 280278724Sdim#endif 281262801Sdim return nullptr; 282262801Sdim } 283227825Stheraven } 284227825Stheraven return p; 285227825Stheraven} 286227825Stheraven 287227825Stheraven__c_node* 288227825Stheraven__libcpp_db::__find_c(void* __c) const 289227825Stheraven{ 290232950Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 291227825Stheraven __c_node* p = __cbeg_[hc]; 292227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 293227825Stheraven while (p->__c_ != __c) 294227825Stheraven { 295227825Stheraven p = p->__next_; 296227825Stheraven _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 297227825Stheraven } 298227825Stheraven return p; 299227825Stheraven} 300227825Stheraven 301227825Stheravenvoid 302227825Stheraven__libcpp_db::unlock() const 303227825Stheraven{ 304278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 305227825Stheraven mut().unlock(); 306278724Sdim#endif 307227825Stheraven} 308227825Stheraven 309227825Stheravenvoid 310227825Stheraven__libcpp_db::__erase_c(void* __c) 311227825Stheraven{ 312278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 313227825Stheraven WLock _(mut()); 314278724Sdim#endif 315262801Sdim if (__cend_ != __cbeg_) 316227825Stheraven { 317262801Sdim size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 318262801Sdim __c_node* p = __cbeg_[hc]; 319262801Sdim if (p == nullptr) 320262801Sdim return; 321262801Sdim __c_node* q = nullptr; 322262801Sdim _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 323262801Sdim while (p->__c_ != __c) 324262801Sdim { 325262801Sdim q = p; 326262801Sdim p = p->__next_; 327262801Sdim if (p == nullptr) 328262801Sdim return; 329262801Sdim _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 330262801Sdim } 331262801Sdim if (q == nullptr) 332262801Sdim __cbeg_[hc] = p->__next_; 333262801Sdim else 334262801Sdim q->__next_ = p->__next_; 335262801Sdim while (p->end_ != p->beg_) 336262801Sdim { 337262801Sdim --p->end_; 338262801Sdim (*p->end_)->__c_ = nullptr; 339262801Sdim } 340262801Sdim free(p->beg_); 341262801Sdim free(p); 342262801Sdim --__csz_; 343227825Stheraven } 344227825Stheraven} 345227825Stheraven 346227825Stheravenvoid 347227825Stheraven__libcpp_db::__iterator_copy(void* __i, const void* __i0) 348227825Stheraven{ 349278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 350227825Stheraven WLock _(mut()); 351278724Sdim#endif 352227825Stheraven __i_node* i = __find_iterator(__i); 353227825Stheraven __i_node* i0 = __find_iterator(__i0); 354227825Stheraven __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 355249998Sdim if (i == nullptr && i0 != nullptr) 356227825Stheraven i = __insert_iterator(__i); 357227825Stheraven __c_node* c = i != nullptr ? i->__c_ : nullptr; 358227825Stheraven if (c != c0) 359227825Stheraven { 360227825Stheraven if (c != nullptr) 361227825Stheraven c->__remove(i); 362227825Stheraven if (i != nullptr) 363227825Stheraven { 364227825Stheraven i->__c_ = nullptr; 365227825Stheraven if (c0 != nullptr) 366227825Stheraven { 367227825Stheraven i->__c_ = c0; 368227825Stheraven i->__c_->__add(i); 369227825Stheraven } 370227825Stheraven } 371227825Stheraven } 372227825Stheraven} 373227825Stheraven 374227825Stheravenbool 375227825Stheraven__libcpp_db::__dereferenceable(const void* __i) const 376227825Stheraven{ 377278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 378227825Stheraven RLock _(mut()); 379278724Sdim#endif 380227825Stheraven __i_node* i = __find_iterator(__i); 381227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 382227825Stheraven} 383227825Stheraven 384227825Stheravenbool 385227825Stheraven__libcpp_db::__decrementable(const void* __i) const 386227825Stheraven{ 387278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 388227825Stheraven RLock _(mut()); 389278724Sdim#endif 390227825Stheraven __i_node* i = __find_iterator(__i); 391227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 392227825Stheraven} 393227825Stheraven 394227825Stheravenbool 395227825Stheraven__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 396227825Stheraven{ 397278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 398227825Stheraven RLock _(mut()); 399278724Sdim#endif 400227825Stheraven __i_node* i = __find_iterator(__i); 401227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 402227825Stheraven} 403227825Stheraven 404227825Stheravenbool 405227825Stheraven__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 406227825Stheraven{ 407278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 408227825Stheraven RLock _(mut()); 409278724Sdim#endif 410227825Stheraven __i_node* i = __find_iterator(__i); 411227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 412227825Stheraven} 413227825Stheraven 414227825Stheravenbool 415262801Sdim__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const 416227825Stheraven{ 417278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 418227825Stheraven RLock _(mut()); 419278724Sdim#endif 420227825Stheraven __i_node* i = __find_iterator(__i); 421227825Stheraven __i_node* j = __find_iterator(__j); 422227825Stheraven __c_node* ci = i != nullptr ? i->__c_ : nullptr; 423227825Stheraven __c_node* cj = j != nullptr ? j->__c_ : nullptr; 424227825Stheraven return ci != nullptr && ci == cj; 425227825Stheraven} 426227825Stheraven 427227825Stheravenvoid 428227825Stheraven__libcpp_db::swap(void* c1, void* c2) 429227825Stheraven{ 430278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 431227825Stheraven WLock _(mut()); 432278724Sdim#endif 433232950Stheraven size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); 434227825Stheraven __c_node* p1 = __cbeg_[hc]; 435227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 436227825Stheraven while (p1->__c_ != c1) 437227825Stheraven { 438227825Stheraven p1 = p1->__next_; 439227825Stheraven _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 440227825Stheraven } 441232950Stheraven hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); 442227825Stheraven __c_node* p2 = __cbeg_[hc]; 443227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 444227825Stheraven while (p2->__c_ != c2) 445227825Stheraven { 446227825Stheraven p2 = p2->__next_; 447227825Stheraven _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 448227825Stheraven } 449227825Stheraven std::swap(p1->beg_, p2->beg_); 450227825Stheraven std::swap(p1->end_, p2->end_); 451227825Stheraven std::swap(p1->cap_, p2->cap_); 452227825Stheraven for (__i_node** p = p1->beg_; p != p1->end_; ++p) 453227825Stheraven (*p)->__c_ = p1; 454227825Stheraven for (__i_node** p = p2->beg_; p != p2->end_; ++p) 455227825Stheraven (*p)->__c_ = p2; 456227825Stheraven} 457227825Stheraven 458227825Stheravenvoid 459227825Stheraven__libcpp_db::__insert_i(void* __i) 460227825Stheraven{ 461278724Sdim#ifndef _LIBCPP_HAS_NO_THREADS 462227825Stheraven WLock _(mut()); 463278724Sdim#endif 464227825Stheraven __insert_iterator(__i); 465227825Stheraven} 466227825Stheraven 467227825Stheravenvoid 468227825Stheraven__c_node::__add(__i_node* i) 469227825Stheraven{ 470227825Stheraven if (end_ == cap_) 471227825Stheraven { 472232950Stheraven size_t nc = 2*static_cast<size_t>(cap_ - beg_); 473227825Stheraven if (nc == 0) 474227825Stheraven nc = 1; 475253159Stheraven __i_node** beg = 476253159Stheraven static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); 477227825Stheraven if (beg == nullptr) 478241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 479227825Stheraven throw bad_alloc(); 480241903Sdim#else 481241903Sdim abort(); 482241903Sdim#endif 483227825Stheraven if (nc > 1) 484227825Stheraven memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 485227825Stheraven free(beg_); 486227825Stheraven beg_ = beg; 487227825Stheraven end_ = beg_ + nc/2; 488227825Stheraven cap_ = beg_ + nc; 489227825Stheraven } 490227825Stheraven *end_++ = i; 491227825Stheraven} 492227825Stheraven 493227825Stheraven// private api 494227825Stheraven 495227825Stheraven_LIBCPP_HIDDEN 496227825Stheraven__i_node* 497227825Stheraven__libcpp_db::__insert_iterator(void* __i) 498227825Stheraven{ 499232950Stheraven if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 500227825Stheraven { 501232950Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 502253159Stheraven __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*))); 503227825Stheraven if (ibeg == nullptr) 504241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 505227825Stheraven throw bad_alloc(); 506241903Sdim#else 507241903Sdim abort(); 508241903Sdim#endif 509227825Stheraven for (__i_node** p = __ibeg_; p != __iend_; ++p) 510227825Stheraven { 511227825Stheraven __i_node* q = *p; 512227825Stheraven while (q != nullptr) 513227825Stheraven { 514227825Stheraven size_t h = hash<void*>()(q->__i_) % nc; 515227825Stheraven __i_node* r = q->__next_; 516227825Stheraven q->__next_ = ibeg[h]; 517227825Stheraven ibeg[h] = q; 518227825Stheraven q = r; 519227825Stheraven } 520227825Stheraven } 521227825Stheraven free(__ibeg_); 522227825Stheraven __ibeg_ = ibeg; 523227825Stheraven __iend_ = __ibeg_ + nc; 524227825Stheraven } 525232950Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 526227825Stheraven __i_node* p = __ibeg_[hi]; 527253159Stheraven __i_node* r = __ibeg_[hi] = 528253159Stheraven static_cast<__i_node*>(malloc(sizeof(__i_node))); 529227825Stheraven if (r == nullptr) 530241903Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 531227825Stheraven throw bad_alloc(); 532241903Sdim#else 533241903Sdim abort(); 534241903Sdim#endif 535227825Stheraven ::new(r) __i_node(__i, p, nullptr); 536227825Stheraven ++__isz_; 537227825Stheraven return r; 538227825Stheraven} 539227825Stheraven 540227825Stheraven_LIBCPP_HIDDEN 541227825Stheraven__i_node* 542227825Stheraven__libcpp_db::__find_iterator(const void* __i) const 543227825Stheraven{ 544227825Stheraven __i_node* r = nullptr; 545227825Stheraven if (__ibeg_ != __iend_) 546227825Stheraven { 547232950Stheraven size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 548227825Stheraven for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 549227825Stheraven { 550227825Stheraven if (nd->__i_ == __i) 551227825Stheraven { 552227825Stheraven r = nd; 553227825Stheraven break; 554227825Stheraven } 555227825Stheraven } 556227825Stheraven } 557227825Stheraven return r; 558227825Stheraven} 559227825Stheraven 560227825Stheraven_LIBCPP_HIDDEN 561227825Stheravenvoid 562227825Stheraven__c_node::__remove(__i_node* p) 563227825Stheraven{ 564227825Stheraven __i_node** r = find(beg_, end_, p); 565227825Stheraven _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 566227825Stheraven if (--end_ != r) 567232950Stheraven memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 568227825Stheraven} 569227825Stheraven 570227825Stheraven_LIBCPP_END_NAMESPACE_STD 571