1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file debug_fn_imps.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41#ifdef _GLIBCXX_DEBUG 42 43PB_DS_CLASS_T_DEC 44void 45PB_DS_CLASS_C_DEC:: 46assert_valid() const 47{ 48 structure_only_assert_valid(); 49 assert_consistent_with_debug_base(); 50 assert_size(); 51 assert_iterators(); 52 if (m_p_head->m_p_parent == 0) 53 { 54 _GLIBCXX_DEBUG_ASSERT(m_size == 0); 55 } 56 else 57 { 58 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 59 } 60} 61 62PB_DS_CLASS_T_DEC 63void 64PB_DS_CLASS_C_DEC:: 65structure_only_assert_valid() const 66{ 67 _GLIBCXX_DEBUG_ASSERT(m_p_head != 0); 68 if (m_p_head->m_p_parent == 0) 69 { 70 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); 71 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); 72 } 73 else 74 { 75 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head); 76 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head); 77 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head); 78 } 79 80 if (m_p_head->m_p_parent != 0) 81 assert_node_consistent(m_p_head->m_p_parent); 82 assert_min(); 83 assert_max(); 84} 85 86PB_DS_CLASS_T_DEC 87void 88PB_DS_CLASS_C_DEC:: 89assert_node_consistent(const node_pointer p_nd) const 90{ 91 assert_node_consistent_(p_nd); 92} 93 94PB_DS_CLASS_T_DEC 95typename PB_DS_CLASS_C_DEC::node_consistent_t 96PB_DS_CLASS_C_DEC:: 97assert_node_consistent_(const node_pointer p_nd) const 98{ 99 if (p_nd == 0) 100 return (std::make_pair((const_pointer)0,(const_pointer)0)); 101 102 assert_node_consistent_with_left(p_nd); 103 assert_node_consistent_with_right(p_nd); 104 105 const std::pair<const_pointer, const_pointer> 106 l_range = assert_node_consistent_(p_nd->m_p_left); 107 108 if (l_range.second != 0) 109 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second), 110 PB_DS_V2F(p_nd->m_value))); 111 112 const std::pair<const_pointer, const_pointer> 113 r_range = assert_node_consistent_(p_nd->m_p_right); 114 115 if (r_range.first != 0) 116 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 117 PB_DS_V2F(*r_range.first))); 118 119 return (std::make_pair((l_range.first != 0)? l_range.first :& p_nd->m_value,(r_range.second != 0)? r_range.second :& p_nd->m_value)); 120} 121 122PB_DS_CLASS_T_DEC 123void 124PB_DS_CLASS_C_DEC:: 125assert_node_consistent_with_left(const node_pointer p_nd) const 126{ 127 if (p_nd->m_p_left == 0) 128 return; 129 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd); 130 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 131 PB_DS_V2F(p_nd->m_p_left->m_value))); 132} 133 134PB_DS_CLASS_T_DEC 135void 136PB_DS_CLASS_C_DEC:: 137assert_node_consistent_with_right(const node_pointer p_nd) const 138{ 139 if (p_nd->m_p_right == 0) 140 return; 141 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd); 142 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value), 143 PB_DS_V2F(p_nd->m_value))); 144} 145 146PB_DS_CLASS_T_DEC 147void 148PB_DS_CLASS_C_DEC:: 149assert_min() const 150{ 151 assert_min_imp(m_p_head->m_p_parent); 152} 153 154PB_DS_CLASS_T_DEC 155void 156PB_DS_CLASS_C_DEC:: 157assert_min_imp(const node_pointer p_nd) const 158{ 159 if (p_nd == 0) 160 { 161 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); 162 return; 163 } 164 165 if (p_nd->m_p_left == 0) 166 { 167 _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left); 168 return; 169 } 170 assert_min_imp(p_nd->m_p_left); 171} 172 173PB_DS_CLASS_T_DEC 174void 175PB_DS_CLASS_C_DEC:: 176assert_max() const 177{ 178 assert_max_imp(m_p_head->m_p_parent); 179} 180 181PB_DS_CLASS_T_DEC 182void 183PB_DS_CLASS_C_DEC:: 184assert_max_imp(const node_pointer p_nd) const 185{ 186 if (p_nd == 0) 187 { 188 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); 189 return; 190 } 191 192 if (p_nd->m_p_right == 0) 193 { 194 _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right); 195 return; 196 } 197 198 assert_max_imp(p_nd->m_p_right); 199} 200 201PB_DS_CLASS_T_DEC 202void 203PB_DS_CLASS_C_DEC:: 204assert_iterators() const 205{ 206 size_type iterated_num = 0; 207 const_iterator prev_it = end(); 208 for (const_iterator it = begin(); it != end(); ++it) 209 { 210 ++iterated_num; 211 _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd); 212 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); 213 --upper_bound_it; 214 _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd); 215 216 if (prev_it != end()) 217 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it), 218 PB_DS_V2F(*it))); 219 prev_it = it; 220 } 221 222 _GLIBCXX_DEBUG_ASSERT(iterated_num == m_size); 223 size_type reverse_iterated_num = 0; 224 const_reverse_iterator reverse_prev_it = rend(); 225 for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend(); 226 ++reverse_it) 227 { 228 ++reverse_iterated_num; 229 _GLIBCXX_DEBUG_ASSERT(lower_bound( 230 PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd); 231 232 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it)); 233 --upper_bound_it; 234 _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd); 235 if (reverse_prev_it != rend()) 236 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it), 237 PB_DS_V2F(*reverse_it))); 238 reverse_prev_it = reverse_it; 239 } 240 _GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size); 241} 242 243PB_DS_CLASS_T_DEC 244void 245PB_DS_CLASS_C_DEC:: 246assert_consistent_with_debug_base() const 247{ 248 debug_base::check_size(m_size); 249 assert_consistent_with_debug_base(m_p_head->m_p_parent); 250} 251 252PB_DS_CLASS_T_DEC 253void 254PB_DS_CLASS_C_DEC:: 255assert_consistent_with_debug_base(const node_pointer p_nd) const 256{ 257 if (p_nd == 0) 258 return; 259 debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value)); 260 assert_consistent_with_debug_base(p_nd->m_p_left); 261 assert_consistent_with_debug_base(p_nd->m_p_right); 262} 263 264PB_DS_CLASS_T_DEC 265void 266PB_DS_CLASS_C_DEC:: 267assert_size() const 268{ 269 _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size); 270} 271 272#endif 273