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 43 PB_DS_CLASS_T_DEC 44 void 45 PB_DS_CLASS_C_DEC:: 46 assert_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 62 PB_DS_CLASS_T_DEC 63 void 64 PB_DS_CLASS_C_DEC:: 65 structure_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 86 PB_DS_CLASS_T_DEC 87 void 88 PB_DS_CLASS_C_DEC:: 89 assert_node_consistent(const node_pointer p_nd) const 90 { 91 assert_node_consistent_(p_nd); 92 } 93 94 PB_DS_CLASS_T_DEC 95 typename PB_DS_CLASS_C_DEC::node_consistent_t 96 PB_DS_CLASS_C_DEC:: 97 assert_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 122 PB_DS_CLASS_T_DEC 123 void 124 PB_DS_CLASS_C_DEC:: 125 assert_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 134 PB_DS_CLASS_T_DEC 135 void 136 PB_DS_CLASS_C_DEC:: 137 assert_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 146 PB_DS_CLASS_T_DEC 147 void 148 PB_DS_CLASS_C_DEC:: 149 assert_min() const 150 { 151 assert_min_imp(m_p_head->m_p_parent); 152 } 153 154 PB_DS_CLASS_T_DEC 155 void 156 PB_DS_CLASS_C_DEC:: 157 assert_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 173 PB_DS_CLASS_T_DEC 174 void 175 PB_DS_CLASS_C_DEC:: 176 assert_max() const 177 { 178 assert_max_imp(m_p_head->m_p_parent); 179 } 180 181 PB_DS_CLASS_T_DEC 182 void 183 PB_DS_CLASS_C_DEC:: 184 assert_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 201 PB_DS_CLASS_T_DEC 202 void 203 PB_DS_CLASS_C_DEC:: 204 assert_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 243 PB_DS_CLASS_T_DEC 244 void 245 PB_DS_CLASS_C_DEC:: 246 assert_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 252 PB_DS_CLASS_T_DEC 253 void 254 PB_DS_CLASS_C_DEC:: 255 assert_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 264 PB_DS_CLASS_T_DEC 265 void 266 PB_DS_CLASS_C_DEC:: 267 assert_size() const 268 { 269 _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size); 270 } 271 272 #endif 273