This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
pb_ds debug patch ?
- From: François Dumont <francois dot cppdevs at free dot fr>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Mon, 07 Mar 2011 21:11:02 +0100
- Subject: pb_ds debug patch ?
Hi
While working on libstdc++ I experiment a regression in usage of
pb_ds priority_queue. To find out what was wrong I made some
modifications in debug mode of this type to have the
binary_heap_::assert_valid method report the file:line where the
assert_valid is invoked and not always a line in the method
implementation code. As most of methods are using a assert_valid after
enter and an other before exit it helps me detect exactly after what
code the data structure got corrupted.
Here is the patch. Now that I found my regression should I revert
those modifications or are you interested in me generalizing this
approach to other priority_queue data structure policies and submit a
final patch ? If so tell me if new macro names are ok with you ?
Regards
Index: include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp (working copy)
@@ -43,8 +43,8 @@
PB_DS_CLASS_C_DEC::
top() const
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
- _GLIBCXX_DEBUG_ASSERT(!empty());
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
+ _GLIBCXX_DEBUG_ASSERT(!empty());
return top_imp(s_no_throw_copies_ind);
}
Index: include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp (working copy)
@@ -64,7 +64,7 @@
std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -74,7 +74,7 @@
m_actual_size(resize_policy::min_size),
m_a_entries(s_entry_allocator.allocate(m_actual_size))
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -85,7 +85,7 @@
m_actual_size(resize_policy::min_size),
m_a_entries(s_entry_allocator.allocate(m_actual_size))
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -97,7 +97,7 @@
m_actual_size(other.m_actual_size),
m_a_entries(s_entry_allocator.allocate(m_actual_size))
{
- _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID(other)
_GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries);
const_iterator first_it = other.begin();
@@ -119,7 +119,7 @@
s_entry_allocator.deallocate(m_a_entries, m_actual_size);
__throw_exception_again;
}
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -127,14 +127,14 @@
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
- _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
+ _GLIBCXX_DEBUG_ASSERT_VALID(other)
_GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries);
value_swap(other);
std::swap((entry_cmp& )(*this), (entry_cmp& )other);
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
- _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
+ _GLIBCXX_DEBUG_ASSERT_VALID(other)
}
PB_DS_CLASS_T_DEC
Index: include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp (working copy)
@@ -43,14 +43,14 @@
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
-assert_valid() const
+assert_valid(const char* __file, int __line) const
{
#ifdef PB_DS_REGRESSION
s_entry_allocator.check_allocated(m_a_entries, m_actual_size);
#endif
- resize_policy::assert_valid();
- _GLIBCXX_DEBUG_ASSERT(m_size <= m_actual_size);
+ resize_policy::assert_valid(__file, __line);
+ _GLIBCXX_DEBUG_VERIFY_PB(m_size <= m_actual_size);
for (size_type i = 0; i < m_size; ++i)
{
#ifdef PB_DS_REGRESSION
@@ -58,14 +58,14 @@
#endif
if (left_child(i) < m_size)
- _GLIBCXX_DEBUG_ASSERT(!entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child(i)]));
+ _GLIBCXX_DEBUG_VERIFY_PB(!entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child(i)]));
- _GLIBCXX_DEBUG_ASSERT(parent(left_child(i)) == i);
+ _GLIBCXX_DEBUG_VERIFY_PB(parent(left_child(i)) == i);
if (right_child(i) < m_size)
- _GLIBCXX_DEBUG_ASSERT(!entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child(i)]));
+ _GLIBCXX_DEBUG_VERIFY_PB(!entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child(i)]));
- _GLIBCXX_DEBUG_ASSERT(parent(right_child(i)) == i);
+ _GLIBCXX_DEBUG_VERIFY_PB(parent(right_child(i)) == i);
}
}
Index: include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp (working copy)
@@ -66,7 +66,7 @@
m_size = 0;
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -89,7 +89,7 @@
PB_DS_CLASS_C_DEC::
pop()
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
_GLIBCXX_DEBUG_ASSERT(!empty());
erase_at(m_a_entries, 0, s_no_throw_copies_ind);
@@ -102,7 +102,7 @@
_GLIBCXX_DEBUG_ASSERT(m_size > 0);
--m_size;
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -111,7 +111,7 @@
PB_DS_CLASS_C_DEC::
erase_if(Pred pred)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
typedef typename entry_pred<value_type, Pred, simple_value, Allocator>::type
pred_t;
@@ -148,7 +148,7 @@
std::make_heap(m_a_entries, m_a_entries + m_size,
static_cast<entry_cmp& >(*this));
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
return ersd;
}
@@ -158,7 +158,7 @@
PB_DS_CLASS_C_DEC::
erase(point_iterator it)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
_GLIBCXX_DEBUG_ASSERT(!empty());
const size_type fix_pos = it.m_p_e - m_a_entries;
@@ -177,7 +177,7 @@
if (fix_pos != m_size)
fix(m_a_entries + fix_pos);
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
Index: include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp (working copy)
@@ -43,11 +43,11 @@
PB_DS_CLASS_C_DEC::
push(const_reference r_val)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
insert_value(r_val, s_no_throw_copies_ind);
std::push_heap(m_a_entries, m_a_entries + m_size,
static_cast<entry_cmp&>(*this));
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
return point_iterator(m_a_entries);
}
@@ -108,10 +108,10 @@
PB_DS_CLASS_C_DEC::
modify(point_iterator it, const_reference r_new_val)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind);
fix(it.m_p_e);
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -131,7 +131,7 @@
parent_i = parent(i);
}
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
return;
}
Index: include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp (working copy)
@@ -45,6 +45,17 @@
* Based on CLRS.
*/
+#define _GLIBCXX_DEBUG_ASSERT_VALID(X) \
+ _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
+
+#define _GLIBCXX_DEBUG_VERIFY_PB(_Condition) \
+ do \
+ { \
+ if (! (_Condition)) \
+ __gnu_debug::_Error_formatter::_M_at(__file, __line) \
+ ._M_message(#_Condition)._M_error(); \
+ } while (false)
+
#include <queue>
#include <algorithm>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
@@ -310,7 +321,7 @@
#ifdef _GLIBCXX_DEBUG
void
- assert_valid() const;
+ assert_valid(const char* file, int line) const;
#endif
#ifdef PB_DS_BINARY_HEAP_TRACE_
@@ -350,6 +361,8 @@
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_ENTRY_CMP_DEC
#undef PB_DS_RESIZE_POLICY_DEC
+#undef _GLIBCXX_DEBUG_VERIFY_PB
+#undef _GLIBCXX_DEBUG_ASSERT_VALID
} // namespace detail
} // namespace __gnu_pbds
Index: include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp (working copy)
@@ -102,7 +102,7 @@
#ifdef _GLIBCXX_DEBUG
void
- assert_valid() const;
+ assert_valid(const char* file, int line) const;
#endif
#ifdef PB_DS_BINARY_HEAP_TRACE_
@@ -128,7 +128,7 @@
resize_policy() :
m_next_shrink_size(0),
m_next_grow_size(min_size)
- { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
+ { _GLIBCXX_DEBUG_ASSERT_VALID((*this)) }
PB_DS_CLASS_T_DEC
inline void
@@ -188,11 +188,11 @@
PB_DS_CLASS_C_DEC::
notify_grow_resize()
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
_GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
m_next_grow_size *= factor;
m_next_shrink_size = m_next_grow_size / ratio;
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -200,14 +200,14 @@
PB_DS_CLASS_C_DEC::
notify_shrink_resize()
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
m_next_shrink_size /= factor;
if (m_next_shrink_size == 1)
m_next_shrink_size = 0;
m_next_grow_size =
std::max(m_next_grow_size / factor, static_cast<size_type>(min_size));
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -217,19 +217,19 @@
{
m_next_grow_size = actual_size;
m_next_shrink_size = m_next_grow_size / ratio;
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
}
#ifdef _GLIBCXX_DEBUG
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
- assert_valid() const
+ assert_valid(const char* __file, int __line) const
{
- _GLIBCXX_DEBUG_ASSERT(m_next_shrink_size == 0 ||
+ _GLIBCXX_DEBUG_VERIFY_PB(m_next_shrink_size == 0 ||
m_next_shrink_size* ratio == m_next_grow_size);
- _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
+ _GLIBCXX_DEBUG_VERIFY_PB(m_next_grow_size >= min_size);
}
#endif
Index: include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp (revision 170373)
+++ include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp (working copy)
@@ -45,9 +45,9 @@
PB_DS_CLASS_C_DEC::
split(Pred pred, PB_DS_CLASS_C_DEC& other)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
- typedef
+ typedef
typename entry_pred<
value_type,
Pred,
@@ -114,17 +114,17 @@
resize_policy::notify_arbitrary(m_actual_size);
other.notify_arbitrary(other.m_actual_size);
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
- _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
- }
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
+ _GLIBCXX_DEBUG_ASSERT_VALID(other)
+}
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
- _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
+ _GLIBCXX_DEBUG_ASSERT_VALID(other)
const size_type len = m_size + other.m_size;
const size_type actual_size = resize_policy::get_new_size_for_arbitrary(len);
@@ -167,7 +167,7 @@
other.notify_arbitrary(resize_policy::min_size);
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
- _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
+ _GLIBCXX_DEBUG_ASSERT_VALID((*this))
+ _GLIBCXX_DEBUG_ASSERT_VALID(other)
}