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 10261272Sdim#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 20249989Sdim_LIBCPP_FUNC_VIS 21227825Stheraven__libcpp_db* 22227825Stheraven__get_db() 23227825Stheraven{ 24227825Stheraven static __libcpp_db db; 25227825Stheraven return &db; 26246468Stheraven} 27227825Stheraven 28249989Sdim_LIBCPP_FUNC_VIS 29227825Stheravenconst __libcpp_db* 30227825Stheraven__get_const_db() 31227825Stheraven{ 32227825Stheraven return __get_db(); 33227825Stheraven} 34227825Stheraven 35227825Stheravennamespace 36227825Stheraven{ 37227825Stheraven 38276792Sdim#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} 49276792Sdim#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{ 113276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 114227825Stheraven RLock _(mut()); 115276792Sdim#endif 116227825Stheraven __i_node* i = __find_iterator(__i); 117249989Sdim _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{ 124276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 125227825Stheraven WLock _(mut()); 126276792Sdim#endif 127261272Sdim if (__cbeg_ == __cend_) 128261272Sdim return; 129232924Stheraven size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 130227825Stheraven __c_node* c = __cbeg_[hc]; 131261272Sdim if (c == nullptr) 132261272Sdim return; 133227825Stheraven while (c->__c_ != __c) 134227825Stheraven { 135227825Stheraven c = c->__next_; 136261272Sdim if (c == nullptr) 137261272Sdim return; 138227825Stheraven } 139261272Sdim __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{ 147276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 148227825Stheraven WLock _(mut()); 149276792Sdim#endif 150232924Stheraven if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 151227825Stheraven { 152232924Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 153253146Stheraven __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*))); 154227825Stheraven if (cbeg == nullptr) 155241900Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 156227825Stheraven throw bad_alloc(); 157241900Sdim#else 158241900Sdim abort(); 159241900Sdim#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 } 176232924Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 177227825Stheraven __c_node* p = __cbeg_[hc]; 178253146Stheraven __c_node* r = __cbeg_[hc] = 179253146Stheraven static_cast<__c_node*>(malloc(sizeof(__c_node))); 180227825Stheraven if (__cbeg_[hc] == nullptr) 181241900Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 182227825Stheraven throw bad_alloc(); 183241900Sdim#else 184241900Sdim abort(); 185241900Sdim#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{ 195276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 196227825Stheraven WLock _(mut()); 197276792Sdim#endif 198227825Stheraven if (__ibeg_ != __iend_) 199227825Stheraven { 200232924Stheraven 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 --__isz_; 218227825Stheraven if (c != nullptr) 219227825Stheraven c->__remove(p); 220288943Sdim free(p); 221227825Stheraven } 222227825Stheraven } 223227825Stheraven} 224227825Stheraven 225227825Stheravenvoid 226227825Stheraven__libcpp_db::__invalidate_all(void* __c) 227227825Stheraven{ 228276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 229227825Stheraven WLock _(mut()); 230276792Sdim#endif 231261272Sdim if (__cend_ != __cbeg_) 232227825Stheraven { 233261272Sdim size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 234261272Sdim __c_node* p = __cbeg_[hc]; 235261272Sdim if (p == nullptr) 236261272Sdim return; 237261272Sdim while (p->__c_ != __c) 238261272Sdim { 239261272Sdim p = p->__next_; 240261272Sdim if (p == nullptr) 241261272Sdim return; 242261272Sdim } 243261272Sdim while (p->end_ != p->beg_) 244261272Sdim { 245261272Sdim --p->end_; 246261272Sdim (*p->end_)->__c_ = nullptr; 247261272Sdim } 248227825Stheraven } 249227825Stheraven} 250227825Stheraven 251227825Stheraven__c_node* 252227825Stheraven__libcpp_db::__find_c_and_lock(void* __c) const 253227825Stheraven{ 254276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 255227825Stheraven mut().lock(); 256276792Sdim#endif 257261272Sdim if (__cend_ == __cbeg_) 258261272Sdim { 259276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 260261272Sdim mut().unlock(); 261276792Sdim#endif 262261272Sdim return nullptr; 263261272Sdim } 264232924Stheraven size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 265227825Stheraven __c_node* p = __cbeg_[hc]; 266261272Sdim if (p == nullptr) 267261272Sdim { 268276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 269261272Sdim mut().unlock(); 270276792Sdim#endif 271261272Sdim return nullptr; 272261272Sdim } 273227825Stheraven while (p->__c_ != __c) 274227825Stheraven { 275227825Stheraven p = p->__next_; 276261272Sdim if (p == nullptr) 277261272Sdim { 278276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 279261272Sdim mut().unlock(); 280276792Sdim#endif 281261272Sdim return nullptr; 282261272Sdim } 283227825Stheraven } 284227825Stheraven return p; 285227825Stheraven} 286227825Stheraven 287227825Stheraven__c_node* 288227825Stheraven__libcpp_db::__find_c(void* __c) const 289227825Stheraven{ 290232924Stheraven 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{ 304276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 305227825Stheraven mut().unlock(); 306276792Sdim#endif 307227825Stheraven} 308227825Stheraven 309227825Stheravenvoid 310227825Stheraven__libcpp_db::__erase_c(void* __c) 311227825Stheraven{ 312276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 313227825Stheraven WLock _(mut()); 314276792Sdim#endif 315261272Sdim if (__cend_ != __cbeg_) 316227825Stheraven { 317261272Sdim size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 318261272Sdim __c_node* p = __cbeg_[hc]; 319261272Sdim if (p == nullptr) 320261272Sdim return; 321261272Sdim __c_node* q = nullptr; 322261272Sdim _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 323261272Sdim while (p->__c_ != __c) 324261272Sdim { 325261272Sdim q = p; 326261272Sdim p = p->__next_; 327261272Sdim if (p == nullptr) 328261272Sdim return; 329261272Sdim _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 330261272Sdim } 331261272Sdim if (q == nullptr) 332261272Sdim __cbeg_[hc] = p->__next_; 333261272Sdim else 334261272Sdim q->__next_ = p->__next_; 335261272Sdim while (p->end_ != p->beg_) 336261272Sdim { 337261272Sdim --p->end_; 338261272Sdim (*p->end_)->__c_ = nullptr; 339261272Sdim } 340261272Sdim free(p->beg_); 341261272Sdim free(p); 342261272Sdim --__csz_; 343227825Stheraven } 344227825Stheraven} 345227825Stheraven 346227825Stheravenvoid 347227825Stheraven__libcpp_db::__iterator_copy(void* __i, const void* __i0) 348227825Stheraven{ 349276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 350227825Stheraven WLock _(mut()); 351276792Sdim#endif 352227825Stheraven __i_node* i = __find_iterator(__i); 353227825Stheraven __i_node* i0 = __find_iterator(__i0); 354227825Stheraven __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 355249989Sdim 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{ 377276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 378227825Stheraven RLock _(mut()); 379276792Sdim#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{ 387276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 388227825Stheraven RLock _(mut()); 389276792Sdim#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{ 397276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 398227825Stheraven RLock _(mut()); 399276792Sdim#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{ 407276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 408227825Stheraven RLock _(mut()); 409276792Sdim#endif 410227825Stheraven __i_node* i = __find_iterator(__i); 411227825Stheraven return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 412227825Stheraven} 413227825Stheraven 414227825Stheravenbool 415261272Sdim__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const 416227825Stheraven{ 417276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 418227825Stheraven RLock _(mut()); 419276792Sdim#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{ 430276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 431227825Stheraven WLock _(mut()); 432276792Sdim#endif 433232924Stheraven 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 } 441232924Stheraven 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{ 461276792Sdim#ifndef _LIBCPP_HAS_NO_THREADS 462227825Stheraven WLock _(mut()); 463276792Sdim#endif 464227825Stheraven __insert_iterator(__i); 465227825Stheraven} 466227825Stheraven 467227825Stheravenvoid 468227825Stheraven__c_node::__add(__i_node* i) 469227825Stheraven{ 470227825Stheraven if (end_ == cap_) 471227825Stheraven { 472232924Stheraven size_t nc = 2*static_cast<size_t>(cap_ - beg_); 473227825Stheraven if (nc == 0) 474227825Stheraven nc = 1; 475253146Stheraven __i_node** beg = 476253146Stheraven static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); 477227825Stheraven if (beg == nullptr) 478241900Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 479227825Stheraven throw bad_alloc(); 480241900Sdim#else 481241900Sdim abort(); 482241900Sdim#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{ 499232924Stheraven if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 500227825Stheraven { 501232924Stheraven size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 502253146Stheraven __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*))); 503227825Stheraven if (ibeg == nullptr) 504241900Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 505227825Stheraven throw bad_alloc(); 506241900Sdim#else 507241900Sdim abort(); 508241900Sdim#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 } 525232924Stheraven size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 526227825Stheraven __i_node* p = __ibeg_[hi]; 527253146Stheraven __i_node* r = __ibeg_[hi] = 528253146Stheraven static_cast<__i_node*>(malloc(sizeof(__i_node))); 529227825Stheraven if (r == nullptr) 530241900Sdim#ifndef _LIBCPP_NO_EXCEPTIONS 531227825Stheraven throw bad_alloc(); 532241900Sdim#else 533241900Sdim abort(); 534241900Sdim#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 { 547232924Stheraven 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) 567232924Stheraven memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 568227825Stheraven} 569227825Stheraven 570227825Stheraven_LIBCPP_END_NAMESPACE_STD 571