17a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant//===-------------------------- debug.cpp ---------------------------------===// 27a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// 37a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// The LLVM Compiler Infrastructure 47a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// 57a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// This file is dual licensed under the MIT and the University of Illinois Open 67a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// Source Licenses. See LICENSE.TXT for details. 77a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// 87a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant//===----------------------------------------------------------------------===// 97a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 105e57142c5902c3f73a6fdcb8cab55e88ffb43a56Howard Hinnant#define _LIBCPP_DEBUG 1 11abe2628b43f13fd81fb90b43dc14472f88b927ccHoward Hinnant#include "__config" 127a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant#include "__debug" 137a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant#include "functional" 147a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant#include "algorithm" 157a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant#include "__hash_table" 167a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant#include "mutex" 177a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 187a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant_LIBCPP_BEGIN_NAMESPACE_STD 197a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 2083eade6abb414e0e814977921bcb6e46853cae03Howard Hinnant_LIBCPP_FUNC_VIS 217a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db* 227a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__get_db() 237a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 247a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant static __libcpp_db db; 257a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return &db; 26c6e54b964f22f489309e4e98554ddd7a42ccd291Howard Hinnant} 277a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 2883eade6abb414e0e814977921bcb6e46853cae03Howard Hinnant_LIBCPP_FUNC_VIS 297a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantconst __libcpp_db* 307a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__get_const_db() 317a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 327a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return __get_db(); 337a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 347a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 357a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantnamespace 367a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 377a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 387112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 397a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnanttypedef mutex mutex_type; 407a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnanttypedef lock_guard<mutex_type> WLock; 417a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnanttypedef lock_guard<mutex_type> RLock; 427a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 437a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantmutex_type& 447a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantmut() 457a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 467a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant static mutex_type m; 477a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return m; 487a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 497112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif // !_LIBCPP_HAS_NO_THREADS 507a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 517a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} // unnamed namespace 527a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 537a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__i_node::~__i_node() 547a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 557a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__next_) 567a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 577a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __next_->~__i_node(); 587a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(__next_); 597a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 607a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 617a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 627a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__c_node::~__c_node() 637a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 647a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(beg_); 657a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__next_) 667a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 677a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __next_->~__c_node(); 687a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(__next_); 697a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 707a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 717a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 727a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__libcpp_db() 737a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant : __cbeg_(nullptr), 747a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __cend_(nullptr), 757a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __csz_(0), 767a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __ibeg_(nullptr), 777a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __iend_(nullptr), 787a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __isz_(0) 797a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 807a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 817a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 827a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::~__libcpp_db() 837a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 847a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__cbeg_) 857a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 867a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__c_node** p = __cbeg_; p != __cend_; ++p) 877a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 887a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (*p != nullptr) 897a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 907a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant (*p)->~__c_node(); 917a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(*p); 927a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 937a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 947a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(__cbeg_); 957a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 967a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__ibeg_) 977a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 987a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__i_node** p = __ibeg_; p != __iend_; ++p) 997a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 1007a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (*p != nullptr) 1017a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 1027a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant (*p)->~__i_node(); 1037a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(*p); 1047a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 1057a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 1067a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(__ibeg_); 1077a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 1087a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 1097a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 1107a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid* 1117a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__find_c_from_i(void* __i) const 1127a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 1137112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 1147a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant RLock _(mut()); 1157112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 1167a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 1176dcaf3ee1a1d97ce320d87df842848c5846c2564Howard Hinnant _LIBCPP_ASSERT(i != nullptr, "iterator not found in debug database."); 1187608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant return i->__c_ != nullptr ? i->__c_->__c_ : nullptr; 1197a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 1207a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 1217a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 1227a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__insert_ic(void* __i, const void* __c) 1237a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 1247112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 1257a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 1267112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 127499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (__cbeg_ == __cend_) 128499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 129ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 1307a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* c = __cbeg_[hc]; 131499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (c == nullptr) 132499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 1337a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (c->__c_ != __c) 1347a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 1357a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant c = c->__next_; 136499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (c == nullptr) 137499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 1387a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 139499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant __i_node* i = __insert_iterator(__i); 1407a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant c->__add(i); 1417a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant i->__c_ = c; 1427a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 1437a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 1447a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__c_node* 1457a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__insert_c(void* __c) 1467a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 1477112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 1487a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 1497112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 150ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant if (__csz_ + 1 > static_cast<size_t>(__cend_ - __cbeg_)) 1517a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 152ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t nc = __next_prime(2*static_cast<size_t>(__cend_ - __cbeg_) + 1); 153912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger __c_node** cbeg = static_cast<__c_node**>(calloc(nc, sizeof(void*))); 1547a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (cbeg == nullptr) 1553882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#ifndef _LIBCPP_NO_EXCEPTIONS 1567a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant throw bad_alloc(); 1573882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#else 1583882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant abort(); 1593882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#endif 1607a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__c_node** p = __cbeg_; p != __cend_; ++p) 1617a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 1627a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* q = *p; 1637a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (q != nullptr) 1647a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 1657a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant size_t h = hash<void*>()(q->__c_) % nc; 1667a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* r = q->__next_; 1677a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant q->__next_ = cbeg[h]; 1687a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant cbeg[h] = q; 1697a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant q = r; 1707a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 1717a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 1727a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(__cbeg_); 1737a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __cbeg_ = cbeg; 1747a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __cend_ = __cbeg_ + nc; 1757a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 176ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 1777a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* p = __cbeg_[hc]; 178912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger __c_node* r = __cbeg_[hc] = 179912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger static_cast<__c_node*>(malloc(sizeof(__c_node))); 1807a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__cbeg_[hc] == nullptr) 1813882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#ifndef _LIBCPP_NO_EXCEPTIONS 1827a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant throw bad_alloc(); 1833882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#else 1843882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant abort(); 1853882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#endif 1867a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant r->__c_ = __c; 1877a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant r->__next_ = p; 1887a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant ++__csz_; 1897a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return r; 1907a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 1917a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 1927a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 1937a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__erase_i(void* __i) 1947a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 1957112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 1967a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 1977112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 1987a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__ibeg_ != __iend_) 1997a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 200ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 2017a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* p = __ibeg_[hi]; 2027a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (p != nullptr) 2037a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 2047a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* q = nullptr; 2057a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (p->__i_ != __i) 2067a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 2077a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant q = p; 2087a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant p = p->__next_; 2097a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (p == nullptr) 2107a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return; 2117a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 2127a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (q == nullptr) 2137a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __ibeg_[hi] = p->__next_; 2147a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant else 2157a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant q->__next_ = p->__next_; 2167a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* c = p->__c_; 2177a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(p); 2187a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant --__isz_; 2197a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (c != nullptr) 2207a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant c->__remove(p); 2217a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 2227a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 2237a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 2247a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 2257a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 2267a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__invalidate_all(void* __c) 2277a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 2287112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 2297a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 2307112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 231499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (__cend_ != __cbeg_) 2327a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 233499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 234499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant __c_node* p = __cbeg_[hc]; 235499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (p == nullptr) 236499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 237499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant while (p->__c_ != __c) 238499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 239499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant p = p->__next_; 240499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (p == nullptr) 241499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 242499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 243499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant while (p->end_ != p->beg_) 244499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 245499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant --p->end_; 246499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant (*p->end_)->__c_ = nullptr; 247499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 2487a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 2497a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 2507a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 2517a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__c_node* 2527a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__find_c_and_lock(void* __c) const 2537a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 2547112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 2557a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant mut().lock(); 2567112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 257499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (__cend_ == __cbeg_) 258499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 2597112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 260499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant mut().unlock(); 2617112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 262499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return nullptr; 263499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 264ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 2657a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* p = __cbeg_[hc]; 266499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (p == nullptr) 267499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 2687112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 269499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant mut().unlock(); 2707112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 271499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return nullptr; 272499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 2737a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (p->__c_ != __c) 2747a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 2757a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant p = p->__next_; 276499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (p == nullptr) 277499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 2787112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 279499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant mut().unlock(); 2807112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 281499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return nullptr; 282499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 2837a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 2847a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return p; 2857a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 2867a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 2871c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant__c_node* 2881c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant__libcpp_db::__find_c(void* __c) const 2891c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant{ 290ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 2911c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant __c_node* p = __cbeg_[hc]; 2921c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c A"); 2931c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant while (p->__c_ != __c) 2941c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant { 2951c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant p = p->__next_; 2961c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c B"); 2971c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant } 2981c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant return p; 2991c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant} 3001c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant 3017a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 3027a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::unlock() const 3037a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 3047112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 3057a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant mut().unlock(); 3067112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 3077a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 3087a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 3097a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 3107a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__erase_c(void* __c) 3117a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 3127112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 3137a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 3147112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 315499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (__cend_ != __cbeg_) 3167a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 317499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); 318499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant __c_node* p = __cbeg_[hc]; 319499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (p == nullptr) 320499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 321499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant __c_node* q = nullptr; 322499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); 323499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant while (p->__c_ != __c) 324499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 325499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant q = p; 326499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant p = p->__next_; 327499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (p == nullptr) 328499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant return; 329499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); 330499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 331499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant if (q == nullptr) 332499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant __cbeg_[hc] = p->__next_; 333499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant else 334499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant q->__next_ = p->__next_; 335499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant while (p->end_ != p->beg_) 336499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant { 337499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant --p->end_; 338499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant (*p->end_)->__c_ = nullptr; 339499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant } 340499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant free(p->beg_); 341499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant free(p); 342499cea12bb2b1c440f28274227d9fd98cd1c609eHoward Hinnant --__csz_; 3437a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 3447a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 3457a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 3467a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 3477a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__iterator_copy(void* __i, const void* __i0) 3487a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 3497112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 3507a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 3517112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 3527a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 3537a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i0 = __find_iterator(__i0); 3547a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr; 3556dcaf3ee1a1d97ce320d87df842848c5846c2564Howard Hinnant if (i == nullptr && i0 != nullptr) 3567a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant i = __insert_iterator(__i); 3577a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* c = i != nullptr ? i->__c_ : nullptr; 3587a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (c != c0) 3597a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 3607a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (c != nullptr) 3617a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant c->__remove(i); 3627a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (i != nullptr) 3637a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 3647a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant i->__c_ = nullptr; 3657a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (c0 != nullptr) 3667a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 3677a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant i->__c_ = c0; 3687a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant i->__c_->__add(i); 3697a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 3707a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 3717a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 3727a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 3737a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 3747a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantbool 3757a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__dereferenceable(const void* __i) const 3767a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 3777112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 3787a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant RLock _(mut()); 3797112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 3807a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 3817a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i); 3827a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 3837a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 3847a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantbool 3857a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__decrementable(const void* __i) const 3867a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 3877112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 3887a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant RLock _(mut()); 3897112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 3907a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 3917a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i); 3927a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 3937a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 3947a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantbool 3957a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const 3967a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 3977112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 3987a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant RLock _(mut()); 3997112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 4007a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 4017a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n); 4027a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 4037a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 4047a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantbool 4057a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const 4067a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 4077112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 4087a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant RLock _(mut()); 4097112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 4107a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 4117a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n); 4127a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 4137a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 4147a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantbool 4158b00e6c96091c828b40ac410b6f123c7429a653dHoward Hinnant__libcpp_db::__less_than_comparable(const void* __i, const void* __j) const 4167a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 4177112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 4187a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant RLock _(mut()); 4197112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 4207a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* i = __find_iterator(__i); 4217a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* j = __find_iterator(__j); 4227a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* ci = i != nullptr ? i->__c_ : nullptr; 4237a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* cj = j != nullptr ? j->__c_ : nullptr; 4247a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return ci != nullptr && ci == cj; 4257a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 4267a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 4277a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 4287a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::swap(void* c1, void* c2) 4297a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 4307112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 4317a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant WLock _(mut()); 4327112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 433ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hc = hash<void*>()(c1) % static_cast<size_t>(__cend_ - __cbeg_); 4347a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* p1 = __cbeg_[hc]; 4357a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A"); 4367a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (p1->__c_ != c1) 4377a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 4387a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant p1 = p1->__next_; 4397a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B"); 4407a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 441ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant hc = hash<void*>()(c2) % static_cast<size_t>(__cend_ - __cbeg_); 4427a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __c_node* p2 = __cbeg_[hc]; 4437a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C"); 4447a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (p2->__c_ != c2) 4457a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 4467a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant p2 = p2->__next_; 4477a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D"); 4487a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 4497a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant std::swap(p1->beg_, p2->beg_); 4507a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant std::swap(p1->end_, p2->end_); 4517a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant std::swap(p1->cap_, p2->cap_); 4527a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__i_node** p = p1->beg_; p != p1->end_; ++p) 4537a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant (*p)->__c_ = p1; 4547a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__i_node** p = p2->beg_; p != p2->end_; ++p) 4557a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant (*p)->__c_ = p2; 4567a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 4577a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 4587608b4aac2bcdaa948387355a2248884758482eaHoward Hinnantvoid 4597608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant__libcpp_db::__insert_i(void* __i) 4607608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant{ 4617112dae6acac544a0271a85d95342c583441e2d1Dan Albert#ifndef _LIBCPP_HAS_NO_THREADS 4627608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant WLock _(mut()); 4637112dae6acac544a0271a85d95342c583441e2d1Dan Albert#endif 4647608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant __insert_iterator(__i); 4657608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant} 4667608b4aac2bcdaa948387355a2248884758482eaHoward Hinnant 4671c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnantvoid 4681c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant__c_node::__add(__i_node* i) 4691c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant{ 4701c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant if (end_ == cap_) 4711c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant { 472ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t nc = 2*static_cast<size_t>(cap_ - beg_); 4731c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant if (nc == 0) 4741c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant nc = 1; 475912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger __i_node** beg = 476912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger static_cast<__i_node**>(malloc(nc * sizeof(__i_node*))); 4771c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant if (beg == nullptr) 4783882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#ifndef _LIBCPP_NO_EXCEPTIONS 4791c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant throw bad_alloc(); 4803882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#else 4813882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant abort(); 4823882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#endif 4831c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant if (nc > 1) 4841c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant memcpy(beg, beg_, nc/2*sizeof(__i_node*)); 4851c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant free(beg_); 4861c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant beg_ = beg; 4871c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant end_ = beg_ + nc/2; 4881c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant cap_ = beg_ + nc; 4891c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant } 4901c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant *end_++ = i; 4911c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant} 4921c3ec6d480ae2443d7fb25089a137b4a8d9d43ccHoward Hinnant 4937a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant// private api 4947a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 4957a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant_LIBCPP_HIDDEN 4967a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__i_node* 4977a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__insert_iterator(void* __i) 4987a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 499ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant if (__isz_ + 1 > static_cast<size_t>(__iend_ - __ibeg_)) 5007a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 501ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t nc = __next_prime(2*static_cast<size_t>(__iend_ - __ibeg_) + 1); 502912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger __i_node** ibeg = static_cast<__i_node**>(calloc(nc, sizeof(void*))); 5037a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (ibeg == nullptr) 5043882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#ifndef _LIBCPP_NO_EXCEPTIONS 5057a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant throw bad_alloc(); 5063882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#else 5073882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant abort(); 5083882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#endif 5097a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__i_node** p = __ibeg_; p != __iend_; ++p) 5107a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 5117a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* q = *p; 5127a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant while (q != nullptr) 5137a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 5147a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant size_t h = hash<void*>()(q->__i_) % nc; 5157a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* r = q->__next_; 5167a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant q->__next_ = ibeg[h]; 5177a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant ibeg[h] = q; 5187a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant q = r; 5197a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 5207a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 5217a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant free(__ibeg_); 5227a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __ibeg_ = ibeg; 5237a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __iend_ = __ibeg_ + nc; 5247a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 525ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t hi = hash<void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 5267a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* p = __ibeg_[hi]; 527912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger __i_node* r = __ibeg_[hi] = 528912438c272dcf15aef344b5437287bbf90dd99aaJoerg Sonnenberger static_cast<__i_node*>(malloc(sizeof(__i_node))); 5297a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (r == nullptr) 5303882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#ifndef _LIBCPP_NO_EXCEPTIONS 5317a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant throw bad_alloc(); 5323882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#else 5333882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant abort(); 5343882d397c4ad38506d1fe21e5ee3d1d9c82091e4Howard Hinnant#endif 5357a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant ::new(r) __i_node(__i, p, nullptr); 5367a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant ++__isz_; 5377a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return r; 5387a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 5397a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 5407a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant_LIBCPP_HIDDEN 5417a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__i_node* 5427a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__libcpp_db::__find_iterator(const void* __i) const 5437a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 5447a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node* r = nullptr; 5457a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (__ibeg_ != __iend_) 5467a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 547ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant size_t h = hash<const void*>()(__i) % static_cast<size_t>(__iend_ - __ibeg_); 5487a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_) 5497a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 5507a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (nd->__i_ == __i) 5517a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant { 5527a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant r = nd; 5537a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant break; 5547a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 5557a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 5567a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant } 5577a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant return r; 5587a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 5597a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 5607a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant_LIBCPP_HIDDEN 5617a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnantvoid 5627a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant__c_node::__remove(__i_node* p) 5637a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant{ 5647a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant __i_node** r = find(beg_, end_, p); 5657a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant _LIBCPP_ASSERT(r != end_, "debug mode internal logic error __c_node::__remove"); 5667a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant if (--end_ != r) 567ec3773c2dadbeadfc5def927116c2ee9d9c53066Howard Hinnant memmove(r, r+1, static_cast<size_t>(end_ - r)*sizeof(__i_node*)); 5687a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant} 5697a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant 5707a563db09ab5bec75c9f132958cc269032eb2862Howard Hinnant_LIBCPP_END_NAMESPACE_STD 571