libc++ sources

26 files changed, 10908 insertions, 0 deletions

diff --git a/system/lib/libcxx/LICENSE.txt b/system/lib/libcxx/LICENSE.txt
new file mode 100644
index 00000000..926f0676
--- /dev/null
+++ b/system/lib/libcxx/LICENSE.txt
@@ -0,0 +1,76 @@
+==============================================================================
+libc++ License
+==============================================================================
+
+The libc++ library is dual licensed under both the University of Illinois
+"BSD-Like" license and the MIT license.  As a user of this code you may choose
+to use it under either license.  As a contributor, you agree to allow your code
+to be used under both.
+
+Full text of the relevant licenses is included below.
+
+==============================================================================
+
+University of Illinois/NCSA
+Open Source License
+
+Copyright (c) 2009-2010 by the contributors listed in CREDITS.TXT
+
+All rights reserved.
+
+Developed by:
+
+    LLVM Team
+
+    University of Illinois at Urbana-Champaign
+
+    http://llvm.org
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal with
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+of the Software, and to permit persons to whom the Software is furnished to do
+so, subject to the following conditions:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimers.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimers in the
+      documentation and/or other materials provided with the distribution.
+
+    * Neither the names of the LLVM Team, University of Illinois at
+      Urbana-Champaign, nor the names of its contributors may be used to
+      endorse or promote products derived from this Software without specific
+      prior written permission.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
+SOFTWARE.
+
+==============================================================================
+
+Copyright (c) 2009-2010 by the contributors listed in CREDITS.TXT
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/system/lib/libcxx/algorithm.cpp b/system/lib/libcxx/algorithm.cpp
new file mode 100644
index 00000000..6d5cf7c0
--- /dev/null
+++ b/system/lib/libcxx/algorithm.cpp
@@ -0,0 +1,83 @@
+//===----------------------- algorithm.cpp --------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "algorithm"
+#include "random"
+#include "mutex"
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
+template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+template void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
+template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+template void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
+template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+template void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
+template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+template void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
+template void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
+template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+
+template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
+template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
+template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
+template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
+template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
+template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
+template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+
+template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
+
+static pthread_mutex_t __rs_mut = PTHREAD_MUTEX_INITIALIZER;
+unsigned __rs_default::__c_ = 0;
+
+__rs_default::__rs_default()
+{
+    pthread_mutex_lock(&__rs_mut);
+    __c_ = 1;
+}
+
+__rs_default::__rs_default(const __rs_default&)
+{
+    ++__c_;
+}
+
+__rs_default::~__rs_default()
+{
+    if (--__c_ == 0)
+        pthread_mutex_unlock(&__rs_mut);
+}
+
+__rs_default::result_type
+__rs_default::operator()()
+{
+    static mt19937 __rs_g;
+    return __rs_g();
+}
+
+__rs_default
+__rs_get()
+{
+    return __rs_default();
+}
+
+_LIBCPP_END_NAMESPACE_STD
diff --git a/system/lib/libcxx/bind.cpp b/system/lib/libcxx/bind.cpp
new file mode 100644
index 00000000..cab0b7c0
--- /dev/null
+++ b/system/lib/libcxx/bind.cpp
@@ -0,0 +1,30 @@
+//===-------------------------- bind.cpp ----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "functional"
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace placeholders
+{
+
+__ph<1>   _1;
+__ph<2>   _2;
+__ph<3>   _3;
+__ph<4>   _4;
+__ph<5>   _5;
+__ph<6>   _6;
+__ph<7>   _7;
+__ph<8>   _8;
+__ph<9>   _9;
+__ph<10> _10;
+
+}  // placeholders
+
+_LIBCPP_END_NAMESPACE_STD
diff --git a/system/lib/libcxx/chrono.cpp b/system/lib/libcxx/chrono.cpp
new file mode 100644
index 00000000..416b9501
--- /dev/null
+++ b/system/lib/libcxx/chrono.cpp
@@ -0,0 +1,128 @@
+//===------------------------- chrono.cpp ---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "chrono"
+#include <sys/time.h>        //for gettimeofday and timeval
+#if __APPLE__
+#include <mach/mach_time.h>  // mach_absolute_time, mach_timebase_info_data_t
+#else  /* !__APPLE__ */
+#include <cerrno>  // errno
+#include <system_error>  // __throw_system_error
+#include <time.h>  // clock_gettime, CLOCK_MONOTONIC
+#endif  // __APPLE__
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace chrono
+{
+
+// system_clock
+
+system_clock::time_point
+system_clock::now() _NOEXCEPT
+{
+    timeval tv;
+    gettimeofday(&tv, 0);
+    return time_point(seconds(tv.tv_sec) + microseconds(tv.tv_usec));
+}
+
+time_t
+system_clock::to_time_t(const time_point& t) _NOEXCEPT
+{
+    return time_t(duration_cast<seconds>(t.time_since_epoch()).count());
+}
+
+system_clock::time_point
+system_clock::from_time_t(time_t t) _NOEXCEPT
+{
+    return system_clock::time_point(seconds(t));
+}
+
+// steady_clock
+
+#if __APPLE__
+//   mach_absolute_time() * MachInfo.numer / MachInfo.denom is the number of
+//   nanoseconds since the computer booted up.  MachInfo.numer and MachInfo.denom
+//   are run time constants supplied by the OS.  This clock has no relationship
+//   to the Gregorian calendar.  It's main use is as a high resolution timer.
+
+// MachInfo.numer / MachInfo.denom is often 1 on the latest equipment.  Specialize
+//   for that case as an optimization.
+
+#pragma GCC visibility push(hidden)
+
+static
+steady_clock::rep
+steady_simplified()
+{
+    return mach_absolute_time();
+}
+
+static
+double
+compute_steady_factor()
+{
+    mach_timebase_info_data_t MachInfo;
+    mach_timebase_info(&MachInfo);
+    return static_cast<double>(MachInfo.numer) / MachInfo.denom;
+}
+
+static
+steady_clock::rep
+steady_full()
+{
+    static const double factor = compute_steady_factor();
+    return static_cast<steady_clock::rep>(mach_absolute_time() * factor);
+}
+
+typedef steady_clock::rep (*FP)();
+
+static
+FP
+init_steady_clock()
+{
+    mach_timebase_info_data_t MachInfo;
+    mach_timebase_info(&MachInfo);
+    if (MachInfo.numer == MachInfo.denom)
+        return &steady_simplified;
+    return &steady_full;
+}
+
+#pragma GCC visibility pop
+
+steady_clock::time_point
+steady_clock::now() _NOEXCEPT
+{
+    static FP fp = init_steady_clock();
+    return time_point(duration(fp()));
+}
+
+#else  // __APPLE__
+// FIXME: We assume that clock_gettime(CLOCK_MONOTONIC) works on
+// non-apple systems.  Instead, we should check _POSIX_TIMERS and
+// _POSIX_MONOTONIC_CLOCK and fall back to something else if those
+// don't exist.
+
+// Warning:  If this is not truly steady, then it is non-conforming.  It is
+//  better for it to not exist and have the rest of libc++ use system_clock
+//  instead.
+
+steady_clock::time_point
+steady_clock::now() _NOEXCEPT
+{
+    struct timespec tp;
+    if (0 != clock_gettime(CLOCK_MONOTONIC, &tp))
+        __throw_system_error(errno, "clock_gettime(CLOCK_MONOTONIC) failed");
+    return time_point(seconds(tp.tv_sec) + nanoseconds(tp.tv_nsec));
+}
+#endif  // __APPLE__
+
+}
+
+_LIBCPP_END_NAMESPACE_STD
diff --git a/system/lib/libcxx/condition_variable.cpp b/system/lib/libcxx/condition_variable.cpp
new file mode 100644
index 00000000..ca1dca32
--- /dev/null
+++ b/system/lib/libcxx/condition_variable.cpp
@@ -0,0 +1,70 @@
+//===-------------------- condition_variable.cpp --------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "condition_variable"
+#include "thread"
+#include "system_error"
+#include "cassert"
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+condition_variable::~condition_variable()
+{
+    int e = pthread_cond_destroy(&__cv_);
+//     assert(e == 0);
+}
+
+void
+condition_variable::notify_one()
+{
+    pthread_cond_signal(&__cv_);
+}
+
+void
+condition_variable::notify_all()
+{
+    pthread_cond_broadcast(&__cv_);
+}
+
+void
+condition_variable::wait(unique_lock<mutex>& lk)
+{
+    if (!lk.owns_lock())
+        __throw_system_error(EPERM,
+                                  "condition_variable::wait: mutex not locked");
+    int ec = pthread_cond_wait(&__cv_, lk.mutex()->native_handle());
+    if (ec)
+        __throw_system_error(ec, "condition_variable wait failed");
+}
+
+void
+condition_variable::__do_timed_wait(unique_lock<mutex>& lk,
+               chrono::time_point<chrono::system_clock, chrono::nanoseconds> tp)
+{
+    using namespace chrono;
+    if (!lk.owns_lock())
+        __throw_system_error(EPERM,
+                            "condition_variable::timed wait: mutex not locked");
+    nanoseconds d = tp.time_since_epoch();
+    timespec ts;
+    seconds s = duration_cast<seconds>(d);
+    ts.tv_sec = static_cast<decltype(ts.tv_sec)>(s.count());
+    ts.tv_nsec = static_cast<decltype(ts.tv_nsec)>((d - s).count());
+    int ec = pthread_cond_timedwait(&__cv_, lk.mutex()->native_handle(), &ts);
+    if (ec != 0 && ec != ETIMEDOUT)
+        __throw_system_error(ec, "condition_variable timed_wait failed");
+}
+
+void
+notify_all_at_thread_exit(condition_variable& cond, unique_lock<mutex> lk)
+{
+    __thread_local_data()->notify_all_at_thread_exit(&cond, lk.release());
+}
+
+_LIBCPP_END_NAMESPACE_STD
diff --git a/system/lib/libcxx/debug.cpp b/system/lib/libcxx/debug.cpp
new file mode 100644
index 00000000..2d2d6432
--- /dev/null
+++ b/system/lib/libcxx/debug.cpp
@@ -0,0 +1,473 @@
+//===-------------------------- debug.cpp ---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define _LIBCPP_DEBUG2 1
+#include "__config"
+#include "__debug"
+#include "functional"
+#include "algorithm"
+#include "__hash_table"
+#include "mutex"
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+_LIBCPP_VISIBLE
+__libcpp_db*
+__get_db()
+{
+    static __libcpp_db db;
+    return &db;
+};
+
+_LIBCPP_VISIBLE
+const __libcpp_db*
+__get_const_db()
+{
+    return __get_db();
+}
+
+namespace
+{
+
+typedef mutex mutex_type;
+typedef lock_guard<mutex_type> WLock;
+typedef lock_guard<mutex_type> RLock;
+
+mutex_type&
+mut()
+{
+    static mutex_type m;
+    return m;
+}
+
+}  // unnamed namespace
+
+__i_node::~__i_node()
+{
+    if (__next_)
+    {
+        __next_->~__i_node();
+        free(__next_);
+    }
+}
+
+__c_node::~__c_node()
+{
+    free(beg_);
+    if (__next_)
+    {
+        __next_->~__c_node();
+        free(__next_);
+    }
+}
+
+__libcpp_db::__libcpp_db()
+    : __cbeg_(nullptr),
+      __cend_(nullptr),
+      __csz_(0),
+      __ibeg_(nullptr),
+      __iend_(nullptr),
+      __isz_(0)
+{
+}
+
+__libcpp_db::~__libcpp_db()
+{
+    if (__cbeg_)
+    {
+        for (__c_node** p = __cbeg_; p != __cend_; ++p)
+        {
+            if (*p != nullptr)
+            {
+                (*p)->~__c_node();
+                free(*p);
+            }
+        }
+        free(__cbeg_);
+    }
+    if (__ibeg_)
+    {
+        for (__i_node** p = __ibeg_; p != __iend_; ++p)
+        {
+            if (*p != nullptr)
+            {
+                (*p)->~__i_node();
+                free(*p);
+            }
+        }
+        free(__ibeg_);
+    }
+}
+
+void*
+__libcpp_db::__find_c_from_i(void* __i) const
+{
+    RLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    _LIBCPP_ASSERT(i != nullptr, "iterator constructed in translation unit with debug mode not enabled."
+                   "  #define _LIBCPP_DEBUG2 1 for that translation unit.");
+    return i->__c_ != nullptr ? i->__c_->__c_ : nullptr;
+}
+
+void
+__libcpp_db::__insert_ic(void* __i, const void* __c)
+{
+    WLock _(mut());
+    __i_node* i = __insert_iterator(__i);
+    _LIBCPP_ASSERT(__cbeg_ != __cend_, "Container constructed in a translation unit with debug mode disabled."
+                   " But it is being used in a translation unit with debug mode enabled."
+                   " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1");
+    size_t hc = hash<const void*>()(__c) % (__cend_ - __cbeg_);
+    __c_node* c = __cbeg_[hc];
+    _LIBCPP_ASSERT(c != nullptr, "Container constructed in a translation unit with debug mode disabled."
+                   " But it is being used in a translation unit with debug mode enabled."
+                   " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1");
+    while (c->__c_ != __c)
+    {
+        c = c->__next_;
+        _LIBCPP_ASSERT(c != nullptr, "Container constructed in a translation unit with debug mode disabled."
+                   " But it is being used in a translation unit with debug mode enabled."
+                   " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1");
+    }
+    c->__add(i);
+    i->__c_ = c;
+}
+
+__c_node*
+__libcpp_db::__insert_c(void* __c)
+{
+    WLock _(mut());
+    if (__csz_ + 1 > __cend_ - __cbeg_)
+    {
+        size_t nc = __next_prime(2*(__cend_ - __cbeg_) + 1);
+        __c_node** cbeg = (__c_node**)calloc(nc, sizeof(void*));
+        if (cbeg == nullptr)
+            throw bad_alloc();
+        for (__c_node** p = __cbeg_; p != __cend_; ++p)
+        {
+            __c_node* q = *p;
+            while (q != nullptr)
+            {
+                size_t h = hash<void*>()(q->__c_) % nc;
+                __c_node* r = q->__next_;
+                q->__next_ = cbeg[h];
+                cbeg[h] = q;
+                q = r;
+            }
+        }
+        free(__cbeg_);
+        __cbeg_ = cbeg;
+        __cend_ = __cbeg_ + nc;
+    }
+    size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_);
+    __c_node* p = __cbeg_[hc];
+    __c_node* r = __cbeg_[hc] = (__c_node*)malloc(sizeof(__c_node));
+    if (__cbeg_[hc] == nullptr)
+        throw bad_alloc();
+    r->__c_ = __c;
+    r->__next_ = p;
+    ++__csz_;
+    return r;
+}
+
+void
+__libcpp_db::__erase_i(void* __i)
+{
+    WLock _(mut());
+    if (__ibeg_ != __iend_)
+    {
+        size_t hi = hash<void*>()(__i) % (__iend_ - __ibeg_);
+        __i_node* p = __ibeg_[hi];
+        if (p != nullptr)
+        {
+            __i_node* q = nullptr;
+            while (p->__i_ != __i)
+            {
+                q = p;
+                p = p->__next_;
+                if (p == nullptr)
+                    return;
+            }
+            if (q == nullptr)
+                __ibeg_[hi] = p->__next_;
+            else
+                q->__next_ = p->__next_;
+            __c_node* c = p->__c_;
+            free(p);
+            --__isz_;
+            if (c != nullptr)
+                c->__remove(p);
+        }
+    }
+}
+
+void
+__libcpp_db::__invalidate_all(void* __c)
+{
+    WLock _(mut());
+    size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_);
+    __c_node* p = __cbeg_[hc];
+    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A");
+    while (p->__c_ != __c)
+    {
+        p = p->__next_;
+        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B");
+    }
+    while (p->end_ != p->beg_)
+    {
+        --p->end_;
+        (*p->end_)->__c_ = nullptr;
+    }
+}
+
+__c_node*
+__libcpp_db::__find_c_and_lock(void* __c) const
+{
+    mut().lock();
+    size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_);
+    __c_node* p = __cbeg_[hc];
+    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A");
+    while (p->__c_ != __c)
+    {
+        p = p->__next_;
+        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B");
+    }
+    return p;
+}
+
+void
+__libcpp_db::unlock() const
+{
+    mut().unlock();
+}
+
+void
+__libcpp_db::__erase_c(void* __c)
+{
+    WLock _(mut());
+    size_t hc = hash<void*>()(__c) % (__cend_ - __cbeg_);
+    __c_node* p = __cbeg_[hc];
+    __c_node* q = nullptr;
+    _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A");
+    while (p->__c_ != __c)
+    {
+        q = p;
+        p = p->__next_;
+        _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B");
+    }
+    if (q == nullptr)
+        __cbeg_[hc] = p->__next_;
+    else
+        q->__next_ = p->__next_;
+    while (p->end_ != p->beg_)
+    {
+        --p->end_;
+        (*p->end_)->__c_ = nullptr;
+    }
+    free(p->beg_);
+    free(p);
+    --__csz_;
+}
+
+void
+__libcpp_db::__iterator_copy(void* __i, const void* __i0)
+{
+    WLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    __i_node* i0 = __find_iterator(__i0);
+    __c_node* c0 = i0 != nullptr ? i0->__c_ : nullptr;
+    if (i == nullptr && c0 != nullptr)
+        i = __insert_iterator(__i);
+    __c_node* c = i != nullptr ? i->__c_ : nullptr;
+    if (c != c0)
+    {
+        if (c != nullptr)
+            c->__remove(i);
+        if (i != nullptr)
+        {
+            i->__c_ = nullptr;
+            if (c0 != nullptr)
+            {
+                i->__c_ = c0;
+                i->__c_->__add(i);
+            }
+        }
+    }
+}
+
+bool
+__libcpp_db::__dereferenceable(const void* __i) const
+{
+    RLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    return i != nullptr && i->__c_ != nullptr && i->__c_->__dereferenceable(__i);
+}
+
+bool
+__libcpp_db::__decrementable(const void* __i) const
+{
+    RLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    return i != nullptr && i->__c_ != nullptr && i->__c_->__decrementable(__i);
+}
+
+bool
+__libcpp_db::__addable(const void* __i, ptrdiff_t __n) const
+{
+    RLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    return i != nullptr && i->__c_ != nullptr && i->__c_->__addable(__i, __n);
+}
+
+bool
+__libcpp_db::__subscriptable(const void* __i, ptrdiff_t __n) const
+{
+    RLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    return i != nullptr && i->__c_ != nullptr && i->__c_->__subscriptable(__i, __n);
+}
+
+bool
+__libcpp_db::__comparable(const void* __i, const void* __j) const
+{
+    RLock _(mut());
+    __i_node* i = __find_iterator(__i);
+    __i_node* j = __find_iterator(__j);
+    __c_node* ci = i != nullptr ? i->__c_ : nullptr;
+    __c_node* cj = j != nullptr ? j->__c_ : nullptr;
+    return ci != nullptr && ci == cj;
+}
+
+void
+__libcpp_db::swap(void* c1, void* c2)
+{
+    WLock _(mut());
+    size_t hc = hash<void*>()(c1) % (__cend_ - __cbeg_);
+    __c_node* p1 = __cbeg_[hc];
+    _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap A");
+    while (p1->__c_ != c1)
+    {
+        p1 = p1->__next_;
+        _LIBCPP_ASSERT(p1 != nullptr, "debug mode internal logic error swap B");
+    }
+    hc = hash<void*>()(c2) % (__cend_ - __cbeg_);
+    __c_node* p2 = __cbeg_[hc];
+    _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap C");
+    while (p2->__c_ != c2)
+    {
+        p2 = p2->__next_;
+        _LIBCPP_ASSERT(p2 != nullptr, "debug mode internal logic error swap D");
+    }
+    std::swap(p1->beg_, p2->beg_);
+    std::swap(p1->end_, p2->end_);
+    std::swap(p1->cap_, p2->cap_);
+    for (__i_node** p = p1->beg_; p != p1->end_; ++p)
+        (*p)->__c_ = p1;
+    for (__i_node** p = p2->beg_; p != p2->end_; ++p)
+        (*p)->__c_ = p2;
+}
+
+void
+__libcpp_db::__insert_i(void* __i)
+{
+    WLock _(mut());
+    __insert_iterator(__i);
+}
+
+// private api
+
+_LIBCPP_HIDDEN
+__i_node*
+__libcpp_db::__insert_iterator(void* __i)
+{
+    if (__isz_ + 1 > __iend_ - __ibeg_)
+    {
+        size_t nc = __next_prime(2*(__iend_ - __ibeg_) + 1);
+        __i_node** ibeg = (__i_node**)calloc(nc, sizeof(void*));
+        if (ibeg == nullptr)
+            throw bad_alloc();
+        for (__i_node** p = __ibeg_; p != __iend_; ++p)
+        {
+            __i_node* q = *p;
+            while (q != nullptr)
+            {
+                size_t h = hash<void*>()(q->__i_) % nc;
+                __i_node* r = q->__next_;
+                q->__next_ = ibeg[h];
+                ibeg[h] = q;
+                q = r;
+            }
+        }
+        free(__ibeg_);
+        __ibeg_ = ibeg;
+        __iend_ = __ibeg_ + nc;
+    }
+    size_t hi = hash<void*>()(__i) % (__iend_ - __ibeg_);
+    __i_node* p = __ibeg_[hi];
+    __i_node* r = __ibeg_[hi] = (__i_node*)malloc(sizeof(__i_node));
+    if (r == nullptr)
+        throw bad_alloc();
+    ::new(r) __i_node(__i, p, nullptr);
+    ++__isz_;
+    return r;
+}
+
+_LIBCPP_HIDDEN
+__i_node*
+__libcpp_db::__find_iterator(const void* __i) const
+{
+    __i_node* r = nullptr;
+    if (__ibeg_ != __iend_)
+    {
+        size_t h = hash<const void*>()(__i) % (__iend_ - __ibeg_);
+        for (__i_node* nd = __ibeg_[h]; nd != nullptr; nd = nd->__next_)
+        {
+            if (nd->__i_ == __i)
+            {
+                r = nd;
+                break;
+            }
+        }
+    }
+    return r;
+}