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/__hash_table b/include/__hash_table
index 2b282d3..55398e4 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -105,16 +105,67 @@
#endif
pointer;
- _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT {}
+ _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__insert_i(this);
+#endif
+ }
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return __node_->__value_;}
+ __hash_iterator(const __hash_iterator& __i)
+ : __node_(__i.__node_)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ }
+
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
+ ~__hash_iterator()
+ {
+ __get_db()->__erase_i(this);
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_iterator& operator=(const __hash_iterator& __i)
+ {
+ if (this != &__i)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ __node_ = __i.__node_;
+ }
+ return *this;
+ }
+
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
+
+ _LIBCPP_INLINE_VISIBILITY
+ reference operator*() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container iterator");
+#endif
+ return __node_->__value_;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ pointer operator->() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container iterator");
+#endif
+ return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ }
_LIBCPP_INLINE_VISIBILITY
__hash_iterator& operator++()
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to increment non-incrementable unordered container iterator");
+#endif
__node_ = __node_->__next_;
return *this;
}
@@ -129,16 +180,31 @@
friend _LIBCPP_INLINE_VISIBILITY
bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
- {return __x.__node_ == __y.__node_;}
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
+ "Attempted to compare non-comparable unordered container iterator");
+#endif
+ return __x.__node_ == __y.__node_;
+ }
friend _LIBCPP_INLINE_VISIBILITY
bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
- {return __x.__node_ != __y.__node_;}
+ {return !(__x == __y);}
private:
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
+ : __node_(__node)
+ {
+ __get_db()->__insert_ic(this, __c);
+ }
+#else
_LIBCPP_INLINE_VISIBILITY
__hash_iterator(__node_pointer __node) _NOEXCEPT
: __node_(__node)
{}
+#endif
template <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
@@ -179,20 +245,75 @@
__non_const_node_pointer;
typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
- _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT {}
+ _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__insert_i(this);
+#endif
+ }
_LIBCPP_INLINE_VISIBILITY
__hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
: __node_(__x.__node_)
- {}
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__iterator_copy(this, &__x);
+#endif
+ }
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return __node_->__value_;}
+ __hash_const_iterator(const __hash_const_iterator& __i)
+ : __node_(__i.__node_)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ }
+
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
+ ~__hash_const_iterator()
+ {
+ __get_db()->__erase_i(this);
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_const_iterator& operator=(const __hash_const_iterator& __i)
+ {
+ if (this != &__i)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ __node_ = __i.__node_;
+ }
+ return *this;
+ }
+
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
+
+ _LIBCPP_INLINE_VISIBILITY
+ reference operator*() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container const_iterator");
+#endif
+ return __node_->__value_;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ pointer operator->() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container const_iterator");
+#endif
+ return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ }
_LIBCPP_INLINE_VISIBILITY
__hash_const_iterator& operator++()
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to increment non-incrementable unordered container const_iterator");
+#endif
__node_ = __node_->__next_;
return *this;
}
@@ -207,16 +328,31 @@
friend _LIBCPP_INLINE_VISIBILITY
bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
- {return __x.__node_ == __y.__node_;}
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
+ "Attempted to compare non-comparable unordered container const_iterator");
+#endif
+ return __x.__node_ == __y.__node_;
+ }
friend _LIBCPP_INLINE_VISIBILITY
bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
- {return __x.__node_ != __y.__node_;}
+ {return !(__x == __y);}
private:
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
+ : __node_(__node)
+ {
+ __get_db()->__insert_ic(this, __c);
+ }
+#else
_LIBCPP_INLINE_VISIBILITY
__hash_const_iterator(__node_pointer __node) _NOEXCEPT
: __node_(__node)
{}
+#endif
template <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
@@ -249,16 +385,71 @@
#endif
pointer;
- _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT {}
+ _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__insert_i(this);
+#endif
+ }
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return __node_->__value_;}
+ __hash_local_iterator(const __hash_local_iterator& __i)
+ : __node_(__i.__node_),
+ __bucket_(__i.__bucket_),
+ __bucket_count_(__i.__bucket_count_)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ }
+
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
+ ~__hash_local_iterator()
+ {
+ __get_db()->__erase_i(this);
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_local_iterator& operator=(const __hash_local_iterator& __i)
+ {
+ if (this != &__i)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ __node_ = __i.__node_;
+ __bucket_ = __i.__bucket_;
+ __bucket_count_ = __i.__bucket_count_;
+ }
+ return *this;
+ }
+
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
+
+ _LIBCPP_INLINE_VISIBILITY
+ reference operator*() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container local_iterator");
+#endif
+ return __node_->__value_;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ pointer operator->() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container local_iterator");
+#endif
+ return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ }
_LIBCPP_INLINE_VISIBILITY
__hash_local_iterator& operator++()
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to increment non-incrementable unordered container local_iterator");
+#endif
__node_ = __node_->__next_;
if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
__node_ = nullptr;
@@ -275,12 +466,31 @@
friend _LIBCPP_INLINE_VISIBILITY
bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
- {return __x.__node_ == __y.__node_;}
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
+ "Attempted to compare non-comparable unordered container local_iterator");
+#endif
+ return __x.__node_ == __y.__node_;
+ }
friend _LIBCPP_INLINE_VISIBILITY
bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
- {return __x.__node_ != __y.__node_;}
+ {return !(__x == __y);}
private:
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_local_iterator(__node_pointer __node, size_t __bucket,
+ size_t __bucket_count, const void* __c) _NOEXCEPT
+ : __node_(__node),
+ __bucket_(__bucket),
+ __bucket_count_(__bucket_count)
+ {
+ __get_db()->__insert_ic(this, __c);
+ if (__node_ != nullptr)
+ __node_ = __node_->__next_;
+ }
+#else
_LIBCPP_INLINE_VISIBILITY
__hash_local_iterator(__node_pointer __node, size_t __bucket,
size_t __bucket_count) _NOEXCEPT
@@ -291,7 +501,7 @@
if (__node_ != nullptr)
__node_ = __node_->__next_;
}
-
+#endif
template <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator;
@@ -333,22 +543,82 @@
#endif
pointer;
- _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT {}
+ _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__insert_i(this);
+#endif
+ }
+
_LIBCPP_INLINE_VISIBILITY
__hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
: __node_(__x.__node_),
__bucket_(__x.__bucket_),
__bucket_count_(__x.__bucket_count_)
- {}
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__iterator_copy(this, &__x);
+#endif
+ }
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return __node_->__value_;}
+ __hash_const_local_iterator(const __hash_const_local_iterator& __i)
+ : __node_(__i.__node_),
+ __bucket_(__i.__bucket_),
+ __bucket_count_(__i.__bucket_count_)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ }
+
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
+ ~__hash_const_local_iterator()
+ {
+ __get_db()->__erase_i(this);
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
+ {
+ if (this != &__i)
+ {
+ __get_db()->__iterator_copy(this, &__i);
+ __node_ = __i.__node_;
+ __bucket_ = __i.__bucket_;
+ __bucket_count_ = __i.__bucket_count_;
+ }
+ return *this;
+ }
+
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
+
+ _LIBCPP_INLINE_VISIBILITY
+ reference operator*() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
+#endif
+ return __node_->__value_;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ pointer operator->() const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
+#endif
+ return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ }
_LIBCPP_INLINE_VISIBILITY
__hash_const_local_iterator& operator++()
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+ "Attempted to increment non-incrementable unordered container const_local_iterator");
+#endif
__node_ = __node_->__next_;
if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
__node_ = nullptr;
@@ -365,12 +635,31 @@
friend _LIBCPP_INLINE_VISIBILITY
bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
- {return __x.__node_ == __y.__node_;}
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
+ "Attempted to compare non-comparable unordered container local_const_iterator");
+#endif
+ return __x.__node_ == __y.__node_;
+ }
friend _LIBCPP_INLINE_VISIBILITY
bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
- {return __x.__node_ != __y.__node_;}
+ {return !(__x == __y);}
private:
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_INLINE_VISIBILITY
+ __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
+ size_t __bucket_count, const void* __c) _NOEXCEPT
+ : __node_(__node),
+ __bucket_(__bucket),
+ __bucket_count_(__bucket_count)
+ {
+ __get_db()->__insert_ic(this, __c);
+ if (__node_ != nullptr)
+ __node_ = __node_->__next_;
+ }
+#else
_LIBCPP_INLINE_VISIBILITY
__hash_const_local_iterator(__node_pointer __node, size_t __bucket,
size_t __bucket_count) _NOEXCEPT
@@ -381,7 +670,7 @@
if (__node_ != nullptr)
__node_ = __node_->__next_;
}
-
+#endif
template <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
};
@@ -722,14 +1011,59 @@
_LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
{max_load_factor() = _VSTD::max(__mlf, load_factor());}
- _LIBCPP_INLINE_VISIBILITY local_iterator begin(size_type __n)
- {return local_iterator(__bucket_list_[__n], __n, bucket_count());}
- _LIBCPP_INLINE_VISIBILITY local_iterator end(size_type __n)
- {return local_iterator(nullptr, __n, bucket_count());}
- _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const
- {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());}
- _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const
- {return const_local_iterator(nullptr, __n, bucket_count());}
+ _LIBCPP_INLINE_VISIBILITY
+ local_iterator
+ begin(size_type __n)
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
+#else
+ return local_iterator(__bucket_list_[__n], __n, bucket_count());
+#endif
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ local_iterator
+ end(size_type __n)
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return local_iterator(nullptr, __n, bucket_count(), this);
+#else
+ return local_iterator(nullptr, __n, bucket_count());
+#endif
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ const_local_iterator
+ cbegin(size_type __n) const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
+#else
+ return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
+#endif
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ const_local_iterator
+ cend(size_type __n) const
+ {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return const_local_iterator(nullptr, __n, bucket_count(), this);
+#else
+ return const_local_iterator(nullptr, __n, bucket_count());
+#endif
+ }
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
+
+ bool __dereferenceable(const const_iterator* __i) const;
+ bool __decrementable(const const_iterator* __i) const;
+ bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
+ bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
+
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
+
private:
void __rehash(size_type __n);
@@ -939,6 +1273,9 @@
__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
{
__deallocate(__p1_.first().__next_);
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__erase_c(this);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -980,6 +1317,21 @@
while (__np != nullptr)
{
__node_pointer __next = __np->__next_;
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __c_node* __c = __get_db()->__find_c_and_lock(this);
+ for (__i_node** __p = __c->end_; __p != __c->beg_; )
+ {
+ --__p;
+ iterator* __i = static_cast<iterator*>((*__p)->__i_);
+ if (__i->__node_ == __np)
+ {
+ (*__p)->__c_ = nullptr;
+ if (--__c->end_ != __p)
+ memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
+ }
+ }
+ __get_db()->unlock();
+#endif
__node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
__node_traits::deallocate(__na, __np, 1);
__np = __next;
@@ -1027,6 +1379,9 @@
__u.__p1_.first().__next_ = nullptr;
__u.size() = 0;
}
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->swap(this, &__u);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1167,7 +1522,11 @@
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return iterator(__p1_.first().__next_, this);
+#else
return iterator(__p1_.first().__next_);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1175,7 +1534,11 @@
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return iterator(nullptr, this);
+#else
return iterator(nullptr);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1183,7 +1546,11 @@
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return const_iterator(__p1_.first().__next_, this);
+#else
return const_iterator(__p1_.first().__next_);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1191,7 +1558,11 @@
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return const_iterator(nullptr, this);
+#else
return const_iterator(nullptr);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1264,7 +1635,11 @@
__inserted = true;
}
__done:
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
+#else
return pair<iterator, bool>(iterator(__ndptr), __inserted);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1321,7 +1696,11 @@
}
}
++size();
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return iterator(__cp, this);
+#else
return iterator(__cp);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1347,7 +1726,11 @@
__cp->__next_ = __np;
__pp->__next_ = __cp;
++size();
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return iterator(__cp, this);
+#else
return iterator(__cp);
+#endif
}
return __node_insert_multi(__cp);
}
@@ -1408,7 +1791,11 @@
__inserted = true;
}
__done:
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return pair<iterator, bool>(iterator(__nd, this), __inserted);
+#else
return pair<iterator, bool>(iterator(__nd), __inserted);
+#endif
}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1543,6 +1930,9 @@
void
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->__invalidate_all(this);
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
__pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
__bucket_list_.reset(__nbc > 0 ?
__pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
@@ -1608,7 +1998,11 @@
__nd = __nd->__next_)
{
if (key_eq()(__nd->__value_, __k))
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return iterator(__nd, this);
+#else
return iterator(__nd);
+#endif
}
}
}
@@ -1633,7 +2027,11 @@
__nd = __nd->__next_)
{
if (key_eq()(__nd->__value_, __k))
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return const_iterator(__nd, this);
+#else
return const_iterator(__nd);
+#endif
}
}
@@ -1710,7 +2108,16 @@
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
{
__node_pointer __np = __p.__node_;
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
+ "unordered container erase(iterator) called with an iterator not"
+ " referring to this container");
+ _LIBCPP_ASSERT(__p != end(),
+ "unordered container erase(iterator) called with a non-dereferenceable iterator");
+ iterator __r(__np, this);
+#else
iterator __r(__np);
+#endif
++__r;
remove(__p);
return __r;
@@ -1721,13 +2128,25 @@
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
const_iterator __last)
{
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
+ "unodered container::erase(iterator, iterator) called with an iterator not"
+ " referring to this unodered container");
+ _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
+ "unodered container::erase(iterator, iterator) called with an iterator not"
+ " referring to this unodered container");
+#endif
for (const_iterator __p = __first; __first != __last; __p = __first)
{
++__first;
erase(__p);
}
__node_pointer __np = __last.__node_;
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ return iterator (__np, this);
+#else
return iterator (__np);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1793,6 +2212,21 @@
__pn->__next_ = __cn->__next_;
__cn->__next_ = nullptr;
--size();
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __c_node* __c = __get_db()->__find_c_and_lock(this);
+ for (__i_node** __p = __c->end_; __p != __c->beg_; )
+ {
+ --__p;
+ iterator* __i = static_cast<iterator*>((*__p)->__i_);
+ if (__i->__node_ == __cn)
+ {
+ (*__p)->__c_ = nullptr;
+ if (--__c->end_ != __p)
+ memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
+ }
+ }
+ __get_db()->unlock();
+#endif
return __node_holder(__cn, _Dp(__node_alloc(), true));
}
@@ -1921,6 +2355,9 @@
if (__u.size() > 0)
__u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
+#if _LIBCPP_DEBUG_LEVEL >= 2
+ __get_db()->swap(this, &__u);
+#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1950,6 +2387,37 @@
__x.swap(__y);
}
+#if _LIBCPP_DEBUG_LEVEL >= 2
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+bool
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
+{
+ return __i->__node_ != nullptr;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+bool
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
+{
+ return false;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+bool
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
+{
+ return false;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+bool
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
+{
+ return false;
+}
+
+#endif // _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_END_NAMESPACE_STD
#endif // _LIBCPP__HASH_TABLE