diff options
author | Benjamin Kosnik <bkoz@redhat.com> | 2006-09-07 22:48:50 +0000 |
---|---|---|
committer | Benjamin Kosnik <bkoz@gcc.gnu.org> | 2006-09-07 22:48:50 +0000 |
commit | 47bea7b87a21a1d5eb42e83941454624c0fe7a89 (patch) | |
tree | 247a242e2b4ff36868d072acef436c650d7340bf /libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_ | |
parent | 5de1a1eb07a702a1a79395f0d956b1bba469138e (diff) | |
download | gcc-47bea7b87a21a1d5eb42e83941454624c0fe7a89.tar.gz |
debug.h (_GLIBCXX_DEBUG_ONLY): New.
2006-09-08 Benjamin Kosnik <bkoz@redhat.com>
* include/debug/debug.h (_GLIBCXX_DEBUG_ONLY): New.
* include/ext/bitmap_allocator.h (_BALLOC_SANITY_CHECK,
_BALLOC_ASSERT): Remove. Use _GLIBCXX_DEBUG,
_GLIBCXX_DEBUG_ASSERT.
* include/ext/pb_ds/hash_policy.hpp (PB_DS_DBG_ASSERT): Convert to
_GLIBCXX_DEBUG_ASSERT. Formatting corrections.
(PB_DS_DBG_VERIFY): Remove, unused.
(PB_DS_DBG_ONLY): Convert to _GLIBCXX_DEBUG blocks.
* include/ext/pb_ds/detail/resize_policy/
hash_load_check_resize_trigger_imp.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
binomial_heap_base_.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
constructor_destructor_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
erase_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
insert_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
constructor_destructor_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
insert_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
debug_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
debug_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
erase_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/unordered_iterator/iterator.hpp: Same.
* include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp: Same.
* include/ext/pb_ds/detail/unordered_iterator/
const_point_iterator.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/head.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/leaf.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/node_base.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/internal_node.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/
split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
constructor_destructor_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
erase_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
insert_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
resize_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
constructor_destructor_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
insert_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
debug_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
debug_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
erase_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
resize_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/types_traits.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
* include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
left_child_next_sibling_heap_.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
const_iterator.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
const_point_iterator.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/map_debug_base.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/
constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/
iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/
rc_binomial_heap_.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/
split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp: Same.
* testsuite/util/regression/res_mng/forced_exception.hpp: Same.
* testsuite/util/regression/res_mng/dbg_ex_allocator_base.hpp: Same.
* testsuite/util/regression/res_mng/dbg_ex_allocator.hpp: Same.
* testsuite/util/rng/twister_rand_gen.cc
* testsuite/util/native_type/assoc/native_multimap.hpp: Same.
* testsuite/util/native_type/assoc/native_hash_multimap.hpp: Same.
From-SVN: r116766
Diffstat (limited to 'libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_')
6 files changed, 110 insertions, 202 deletions
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp index 58290bfd160..de220d95351 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp @@ -60,7 +60,7 @@ PB_DS_CLASS_NAME() { initialize(); - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC @@ -70,7 +70,7 @@ PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : { initialize(); - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC @@ -80,7 +80,7 @@ PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : { initialize(); - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC @@ -90,7 +90,7 @@ PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : { initialize(); - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC @@ -98,11 +98,11 @@ void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) PB_DS_BASE_C_DEC::swap(other); - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp index 13e93cae75a..3a4049e9f8d 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp @@ -44,7 +44,7 @@ * Contains an implementation for rb_tree_. */ -#ifdef PB_DS_RB_TREE_DEBUG_ +#ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type @@ -56,16 +56,12 @@ assert_node_consistent(const node_pointer p_nd) const const size_type l_height = assert_node_consistent(p_nd->m_p_left); const size_type r_height = assert_node_consistent(p_nd->m_p_right); - if (p_nd->m_red) { - PB_DS_DBG_ASSERT(is_effectively_black(p_nd->m_p_left)); - - PB_DS_DBG_ASSERT(is_effectively_black(p_nd->m_p_right)); + _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_left)); + _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_right)); } - - PB_DS_DBG_ASSERT(l_height == r_height); - + _GLIBCXX_DEBUG_ASSERT(l_height == r_height); return ((p_nd->m_red? 0 : 1) + l_height); } @@ -75,18 +71,14 @@ PB_DS_CLASS_C_DEC:: assert_valid() const { PB_DS_BASE_C_DEC::assert_valid(); - const node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; - - PB_DS_DBG_ASSERT(p_head->m_red); - + _GLIBCXX_DEBUG_ASSERT(p_head->m_red); if (p_head->m_p_parent != NULL) { - PB_DS_DBG_ASSERT(!p_head->m_p_parent->m_red); - + _GLIBCXX_DEBUG_ASSERT(!p_head->m_p_parent->m_red); assert_node_consistent(p_head->m_p_parent); } } -#endif // #ifdef PB_DS_RB_TREE_DEBUG_ +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp index e3aadc5515d..cfe212589fc 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp @@ -64,7 +64,7 @@ inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: erase(iterator it) { - PB_DS_DBG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it == PB_DS_BASE_C_DEC::end()) return (it); @@ -75,7 +75,7 @@ erase(iterator it) erase_node(it.m_p_nd); - PB_DS_DBG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(assert_valid()); return (ret_it); } @@ -85,7 +85,7 @@ inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: erase(reverse_iterator it) { - PB_DS_DBG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it.m_p_nd == PB_DS_BASE_C_DEC::m_p_head) return (it); @@ -96,7 +96,7 @@ erase(reverse_iterator it) erase_node(it.m_p_nd); - PB_DS_DBG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(assert_valid()); return (ret_it); } @@ -107,7 +107,7 @@ inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) size_type num_ersd = 0; @@ -125,7 +125,7 @@ erase_if(Pred pred) ++it; } - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) return (num_ersd); } @@ -139,7 +139,7 @@ erase_node(node_pointer p_nd) PB_DS_BASE_C_DEC::actual_erase_node(p_nd); - PB_DS_DBG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(assert_valid()); } PB_DS_CLASS_T_DEC @@ -240,7 +240,7 @@ void PB_DS_CLASS_C_DEC:: remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) { - PB_DS_DBG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent); + _GLIBCXX_DEBUG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent); while (p_x != PB_DS_BASE_C_DEC::m_p_head->m_p_parent&& is_effectively_black(p_x)) diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp index 891c43b6332..d0e5e10fa1b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp @@ -49,7 +49,7 @@ inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> PB_DS_CLASS_C_DEC:: insert(const_reference r_value) { - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) std::pair<point_iterator, bool> ins_pair = PB_DS_BASE_C_DEC::insert_leaf(r_value); @@ -58,12 +58,12 @@ insert(const_reference r_value) { ins_pair.first.m_p_nd->m_red = true; - PB_DS_DBG_ONLY(this->structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();) insert_fixup(ins_pair.first.m_p_nd); } - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) return (ins_pair); } @@ -73,7 +73,7 @@ inline void PB_DS_CLASS_C_DEC:: insert_fixup(node_pointer p_nd) { - PB_DS_DBG_ASSERT(p_nd->m_red == true); + _GLIBCXX_DEBUG_ASSERT(p_nd->m_red == true); while (p_nd != PB_DS_BASE_C_DEC::m_p_head->m_p_parent&& p_nd->m_p_parent->m_red) diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp index c4cc743cfa5..7942480811b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp @@ -52,37 +52,28 @@ #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> -#endif // #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR +#endif +#endif #ifdef PB_DS_DATA_FALSE_INDICATOR #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> -#endif // #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR -#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR +#endif +#endif #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/detail/basic_types.hpp> #include <utility> #include <vector> #include <assert.h> +#include <debug/debug.h> namespace pb_ds { namespace detail { -#ifdef PB_DS_RB_TREE_DEBUG_ -#define PB_DS_DBG_ASSERT(X) assert(X) -#define PB_DS_DBG_VERIFY(X) assert(X) -#define PB_DS_DBG_ONLY(X) X -#else // #ifdef PB_DS_RB_TREE_DEBUG_ -#define PB_DS_DBG_ASSERT(X) -#define PB_DS_DBG_VERIFY(X) {if((X)==0);} -#define PB_DS_DBG_ONLY(X) ; -#endif // #ifdef PB_DS_RB_TREE_DEBUG_ - #define PB_DS_CLASS_T_DEC \ template< \ typename Key, \ @@ -94,22 +85,22 @@ namespace pb_ds #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CLASS_NAME \ rb_tree_data_ -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR - -#ifdef PB_DS_DATA_FALSE_INDICATOR -#define PB_DS_CLASS_NAME \ - rb_tree_no_data_ -#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR +#endif #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_BASE_CLASS_NAME \ bin_search_tree_data_ -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_CLASS_NAME \ + rb_tree_no_data_ +#endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_BASE_CLASS_NAME \ bin_search_tree_no_data_ -#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR +#endif #define PB_DS_CLASS_C_DEC \ PB_DS_CLASS_NAME< \ @@ -131,13 +122,13 @@ namespace pb_ds #define PB_DS_V2F(X) (X).first #define PB_DS_V2S(X) (X).second #define PB_DS_EP2VP(X)& ((X)->m_value) -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR +#endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_V2F(X) (X) #define PB_DS_V2S(X) Mapped_Data() #define PB_DS_EP2VP(X)& ((X)->m_value.first) -#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR +#endif template<typename Key, typename Mapped, @@ -229,40 +220,30 @@ namespace pb_ds void copy_from_range(It first_it, It last_it); - inline std::pair< - point_iterator, - bool> + inline std::pair<point_iterator, bool> insert(const_reference r_value); inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR - PB_DS_DBG_ONLY(assert_valid();) - - std::pair<point_iterator, bool> ins_pair = - PB_DS_BASE_C_DEC::insert_leaf( - value_type( - r_key, - mapped_type())); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + std::pair<point_iterator, bool> ins_pair = + PB_DS_BASE_C_DEC::insert_leaf(value_type(r_key, mapped_type())); if (ins_pair.second == true) { ins_pair.first.m_p_nd->m_red = true; - - PB_DS_DBG_ONLY(this->structure_only_assert_valid();) - - insert_fixup(ins_pair.first.m_p_nd); + _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();) + insert_fixup(ins_pair.first.m_p_nd); } - - PB_DS_DBG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) return (ins_pair.first.m_p_nd->m_value.second); -#else // #ifdef PB_DS_DATA_TRUE_INDICATOR +#else insert(r_key); - return (PB_DS_BASE_C_DEC::s_null_mapped); -#endif // #ifdef PB_DS_DATA_TRUE +#endif } inline bool @@ -288,15 +269,13 @@ namespace pb_ds private: -#ifdef PB_DS_RB_TREE_DEBUG_ - +#ifdef _GLIBCXX_DEBUG void assert_valid() const; size_type assert_node_consistent(const node_pointer p_nd) const; - -#endif // #ifdef PB_DS_RB_TREE_DEBUG_ +#endif inline static bool is_effectively_black(const node_pointer p_nd); @@ -350,19 +329,11 @@ namespace pb_ds #include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp> #undef PB_DS_CLASS_T_DEC - #undef PB_DS_CLASS_C_DEC - #undef PB_DS_CLASS_NAME - #undef PB_DS_BASE_CLASS_NAME - #undef PB_DS_BASE_C_DEC -#undef PB_DS_DBG_ASSERT -#undef PB_DS_DBG_VERIFY -#undef PB_DS_DBG_ONLY - #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp index 633f027a7ba..8cb57501fc7 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp @@ -49,85 +49,68 @@ inline void PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { - PB_DS_DBG_ONLY(assert_valid();) - - PB_DS_DBG_ONLY(other.assert_valid();) - PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) - - if (PB_DS_BASE_C_DEC::join_prep(other) == false) - { - PB_DS_DBG_ONLY(assert_valid();) - PB_DS_DBG_ONLY(other.assert_valid();) - - return; - } + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) + if (PB_DS_BASE_C_DEC::join_prep(other) == false) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; + } const node_pointer p_x = other.split_min(); - join_imp(p_x, other.m_p_head->m_p_parent); - PB_DS_BASE_C_DEC::join_finish(other); - - PB_DS_DBG_ONLY(assert_valid();) - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) - - PB_DS_DBG_ONLY(other.assert_valid();) - PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) + } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: join_imp(node_pointer p_x, node_pointer p_r) { - PB_DS_DBG_ASSERT(p_x != NULL); - + _GLIBCXX_DEBUG_ASSERT(p_x != NULL); if (p_r != NULL) p_r->m_red = false; - const size_type h = - black_height(PB_DS_BASE_C_DEC::m_p_head->m_p_parent); + const size_type h = black_height(PB_DS_BASE_C_DEC::m_p_head->m_p_parent); const size_type other_h = black_height(p_r); - node_pointer p_x_l; node_pointer p_x_r; - std::pair<node_pointer, node_pointer> join_pos; - const bool right_join = h >= other_h; - if (right_join) { - join_pos = find_join_pos_right( PB_DS_BASE_C_DEC::m_p_head->m_p_parent, h, other_h); - + join_pos = find_join_pos_right(PB_DS_BASE_C_DEC::m_p_head->m_p_parent, + h, other_h); p_x_l = join_pos.first; p_x_r = p_r; } else { p_x_l = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_r; if (p_r != NULL) p_r->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; - join_pos = find_join_pos_left( PB_DS_BASE_C_DEC::m_p_head->m_p_parent, h, other_h); - + join_pos = find_join_pos_left(PB_DS_BASE_C_DEC::m_p_head->m_p_parent, + h, other_h); p_x_r = join_pos.first; } node_pointer p_parent = join_pos.second; - if (p_parent == PB_DS_BASE_C_DEC::m_p_head) { PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_x; - p_x->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; } else { p_x->m_p_parent = p_parent; - if (right_join) p_x->m_p_parent->m_p_right = p_x; else @@ -145,14 +128,10 @@ join_imp(node_pointer p_x, node_pointer p_r) p_x->m_red = true; PB_DS_BASE_C_DEC::initialize_min_max(); - - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - - PB_DS_BASE_C_DEC::update_to_top(p_x, (node_update* )this); - + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) + PB_DS_BASE_C_DEC::update_to_top(p_x, (node_update* )this); insert_fixup(p_x); - - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); } PB_DS_CLASS_T_DEC @@ -162,14 +141,12 @@ split_min() { node_pointer p_min = PB_DS_BASE_C_DEC::m_p_head->m_p_left; -#ifdef PB_DS_RB_TREE_DEBUG_ +#ifdef _GLIBCXX_DEBUG const node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; - - PB_DS_DBG_ASSERT(p_min != p_head); -#endif // #ifdef PB_DS_RB_TREE_DEBUG_ + _GLIBCXX_DEBUG_ASSERT(p_min != p_head); +#endif remove_node(p_min); - return (p_min); } @@ -180,40 +157,34 @@ std::pair< PB_DS_CLASS_C_DEC:: find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) { - PB_DS_DBG_ASSERT(h_l >= h_r); + _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == NULL) - return (std::make_pair((node_pointer)NULL, - PB_DS_BASE_C_DEC::m_p_head)); + return (std::make_pair((node_pointer)NULL, PB_DS_BASE_C_DEC::m_p_head)); node_pointer p_l_parent = PB_DS_BASE_C_DEC::m_p_head; - while (h_l > h_r) { if (p_l->m_red == false) { - PB_DS_DBG_ASSERT(h_l > 0); - + _GLIBCXX_DEBUG_ASSERT(h_l > 0); --h_l; } p_l_parent = p_l; - p_l = p_l->m_p_right; } if (!is_effectively_black(p_l)) { p_l_parent = p_l; - p_l = p_l->m_p_right; } - PB_DS_DBG_ASSERT(is_effectively_black(p_l)); - PB_DS_DBG_ASSERT(black_height(p_l) == h_r); - PB_DS_DBG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent); - - return (std::make_pair(p_l, p_l_parent)); + _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l)); + _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r); + _GLIBCXX_DEBUG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent); + return std::make_pair(p_l, p_l_parent); } PB_DS_CLASS_T_DEC @@ -223,40 +194,33 @@ std::pair< PB_DS_CLASS_C_DEC:: find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) { - PB_DS_DBG_ASSERT(h_r > h_l); - + _GLIBCXX_DEBUG_ASSERT(h_r > h_l); if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == NULL) return (std::make_pair((node_pointer)NULL, PB_DS_BASE_C_DEC::m_p_head)); - node_pointer p_r_parent = PB_DS_BASE_C_DEC::m_p_head; - while (h_r > h_l) { if (p_r->m_red == false) { - PB_DS_DBG_ASSERT(h_r > 0); - + _GLIBCXX_DEBUG_ASSERT(h_r > 0); --h_r; } p_r_parent = p_r; - p_r = p_r->m_p_left; } if (!is_effectively_black(p_r)) { p_r_parent = p_r; - p_r = p_r->m_p_left; } - PB_DS_DBG_ASSERT(is_effectively_black(p_r)); - PB_DS_DBG_ASSERT(black_height(p_r) == h_l); - PB_DS_DBG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent); - - return (std::make_pair(p_r, p_r_parent)); + _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r)); + _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l); + _GLIBCXX_DEBUG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent); + return std::make_pair(p_r, p_r_parent); } PB_DS_CLASS_T_DEC @@ -265,16 +229,13 @@ PB_DS_CLASS_C_DEC:: black_height(node_pointer p_nd) { size_type h = 1; - while (p_nd != NULL) { if (p_nd->m_red == false) ++h; - p_nd = p_nd->m_p_left; } - - return (h); + return h; } PB_DS_CLASS_T_DEC @@ -282,68 +243,55 @@ void PB_DS_CLASS_C_DEC:: split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) { - PB_DS_DBG_ONLY(assert_valid()); - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) - PB_DS_DBG_ONLY(other.assert_valid()); - PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid()); + _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) if (PB_DS_BASE_C_DEC::split_prep(r_key, other) == false) { - PB_DS_DBG_ONLY(assert_valid()); - PB_DS_DBG_ONLY(other.assert_valid()); - + _GLIBCXX_DEBUG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(other.assert_valid()); return; } - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - - PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) - - node_pointer p_nd = upper_bound(r_key).m_p_nd; - + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) + node_pointer p_nd = upper_bound(r_key).m_p_nd; do { node_pointer p_next_nd = p_nd->m_p_parent; - - if (Cmp_Fn::operator()( - r_key, - PB_DS_V2F(p_nd->m_value))) + if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) split_at_node(p_nd, other); - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) - - p_nd = p_next_nd; + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) + p_nd = p_next_nd; } while (p_nd != PB_DS_BASE_C_DEC::m_p_head); PB_DS_BASE_C_DEC::split_finish(other); - - PB_DS_DBG_ONLY(assert_valid();) - PB_DS_DBG_ONLY(assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) { - PB_DS_DBG_ASSERT(p_nd != NULL); + _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); node_pointer p_l = p_nd->m_p_left; node_pointer p_r = p_nd->m_p_right; - node_pointer p_parent = p_nd->m_p_parent; - if (p_parent == PB_DS_BASE_C_DEC::m_p_head) { PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_l; - if (p_l != NULL) { p_l->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; - p_l->m_red = false; } } @@ -364,11 +312,8 @@ split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) } PB_DS_BASE_C_DEC::initialize_min_max(); - other.join_imp(p_nd, p_r); - - PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); - - PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid()); + _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); + _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid()); } |