Debug mode for unordered_set.  I believe this to be fairly complete for
unordered_set, however it is not complete yet for unordered_multiset,
unordered_map or unordered_multimap.  There has been a lot of work done
for these other three containers, however that work was done just to
keep all of the tests passing.

You can try this out with -D_LIBCPP_DEBUG2.  You will have to link to a
libc++.dylib that has been compiled with src/debug.cpp.  So far, vector
(but not vector<bool>), list, and unordered_set are treated.  I hope to
get the other three unordered containers up fairly quickly now that
unordered_set is done.

The flag _LIBCPP_DEBUG2 will eventually be changed to _LIBCPP_DEBUG, but
not today.  This is my second effort at getting debug mode going for
libc++, and I'm not quite yet ready to throw all of the work under the
first attempt away.

The basic design is that all of the debug information is kept in a
central database, instead of in the containers.  This has been done as
an attempt to have debug mode and non-debug mode be ABI compatible with
each other.  There are some circumstances where if you construct a
container in an environment without debug mode and pass it into debug
mode, the checking will get confused and let you know with a readable
error message.  Passing containers the other way: from debug mode out to
a non-debugging mode container should be 100% safe (at least that is the
goal).

git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@186991 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/unordered_map b/include/unordered_map
index 78e6307..55db2f5 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -624,6 +624,8 @@
     typedef pair<key_type, mapped_type>                    __nc_value_type;
     typedef value_type&                                    reference;
     typedef const value_type&                              const_reference;
+    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
+                  "Invalid allocator::value_type");
 
 private:
 #if __cplusplus >= 201103L
@@ -706,7 +708,11 @@
     _LIBCPP_INLINE_VISIBILITY
     unordered_map()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
-        {} // = default;
+        {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+            __get_db()->__insert_c(this);
+#endif
+        }
     explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
                            const key_equal& __eql = key_equal());
     unordered_map(size_type __n, const hasher& __hf,
@@ -905,6 +911,19 @@
     _LIBCPP_INLINE_VISIBILITY
     void reserve(size_type __n) {__table_.reserve(__n);}
 
+#if _LIBCPP_DEBUG_LEVEL >= 2
+
+    bool __dereferenceable(const const_iterator* __i) const
+        {return __table_.__dereferenceable(&__i->__i_);}
+    bool __decrementable(const const_iterator* __i) const
+        {return __table_.__decrementable(&__i->__i_);}
+    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(&__i->__i_, __n);}
+    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(&__i->__i_, __n);}
+
+#endif  // _LIBCPP_DEBUG_LEVEL >= 2
+
 private:
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     __node_holder __construct_node();
@@ -925,6 +944,9 @@
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -934,6 +956,9 @@
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -943,6 +968,9 @@
         const allocator_type& __a)
     : __table_(__a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
@@ -950,6 +978,9 @@
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         _InputIterator __first, _InputIterator __last)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__first, __last);
 }
 
@@ -960,6 +991,9 @@
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -971,6 +1005,9 @@
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -980,6 +1017,9 @@
         const unordered_map& __u)
     : __table_(__u.__table_)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -989,6 +1029,9 @@
         const unordered_map& __u, const allocator_type& __a)
     : __table_(__u.__table_, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -1002,6 +1045,9 @@
     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
     : __table_(_VSTD::move(__u.__table_))
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
@@ -1009,6 +1055,9 @@
         unordered_map&& __u, const allocator_type& __a)
     : __table_(_VSTD::move(__u.__table_), __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     if (__a != __u.get_allocator())
     {
         iterator __i = __u.begin();
@@ -1027,6 +1076,9 @@
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         initializer_list<value_type> __il)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__il.begin(), __il.end());
 }
 
@@ -1036,6 +1088,9 @@
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }
@@ -1046,6 +1101,9 @@
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }
@@ -1286,6 +1344,8 @@
     typedef pair<key_type, mapped_type>                    __nc_value_type;
     typedef value_type&                                    reference;
     typedef const value_type&                              const_reference;
+    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
+                  "Invalid allocator::value_type");
 
 private:
 #if __cplusplus >= 201103L
@@ -1366,7 +1426,11 @@
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
-        {} // = default;
+        {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+            __get_db()->__insert_c(this);
+#endif
+        }
     explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
                                 const key_equal& __eql = key_equal());
     unordered_multimap(size_type __n, const hasher& __hf,
@@ -1556,6 +1620,19 @@
     _LIBCPP_INLINE_VISIBILITY
     void reserve(size_type __n) {__table_.reserve(__n);}
 
+#if _LIBCPP_DEBUG_LEVEL >= 2
+
+    bool __dereferenceable(const const_iterator* __i) const
+        {return __table_.__dereferenceable(&__i->__i_);}
+    bool __decrementable(const const_iterator* __i) const
+        {return __table_.__decrementable(&__i->__i_);}
+    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(&__i->__i_, __n);}
+    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(&__i->__i_, __n);}
+
+#endif  // _LIBCPP_DEBUG_LEVEL >= 2
+
 private:
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     __node_holder __construct_node();
@@ -1574,6 +1651,9 @@
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -1583,6 +1663,9 @@
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -1591,6 +1674,9 @@
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         _InputIterator __first, _InputIterator __last)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__first, __last);
 }
 
@@ -1601,6 +1687,9 @@
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -1612,6 +1701,9 @@
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -1622,6 +1714,9 @@
         const allocator_type& __a)
     : __table_(__a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
@@ -1629,6 +1724,9 @@
         const unordered_multimap& __u)
     : __table_(__u.__table_)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -1638,6 +1736,9 @@
         const unordered_multimap& __u, const allocator_type& __a)
     : __table_(__u.__table_, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -1651,6 +1752,9 @@
     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
     : __table_(_VSTD::move(__u.__table_))
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
@@ -1658,15 +1762,18 @@
         unordered_multimap&& __u, const allocator_type& __a)
     : __table_(_VSTD::move(__u.__table_), __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     if (__a != __u.get_allocator())
     {
         iterator __i = __u.begin();
         while (__u.size() != 0)
-{
+        {
             __table_.__insert_multi(
                 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
                                    );
-}
+        }
     }
 }
 
@@ -1678,6 +1785,9 @@
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         initializer_list<value_type> __il)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__il.begin(), __il.end());
 }
 
@@ -1687,6 +1797,9 @@
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }
@@ -1697,6 +1810,9 @@
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }