1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file debug_fn_imps.hpp 44 * Contains an implementation class for bin_search_tree_. 45 */ 46 47#ifdef _GLIBCXX_DEBUG 48 49PB_DS_CLASS_T_DEC 50void 51PB_DS_CLASS_C_DEC:: 52assert_valid() const 53{ 54 structure_only_assert_valid(); 55 assert_consistent_with_debug_base(); 56 assert_size(); 57 assert_iterators(); 58 if (m_p_head->m_p_parent == NULL) 59 { 60 _GLIBCXX_DEBUG_ASSERT(m_size == 0); 61 } 62 else 63 { 64 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 65 } 66} 67 68PB_DS_CLASS_T_DEC 69void 70PB_DS_CLASS_C_DEC:: 71structure_only_assert_valid() const 72{ 73 _GLIBCXX_DEBUG_ASSERT(m_p_head != NULL); 74 if (m_p_head->m_p_parent == NULL) 75 { 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 else 80 { 81 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head); 82 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head); 83 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head); 84 } 85 86 if (m_p_head->m_p_parent != NULL) 87 assert_node_consistent(m_p_head->m_p_parent); 88 assert_min(); 89 assert_max(); 90} 91 92PB_DS_CLASS_T_DEC 93void 94PB_DS_CLASS_C_DEC:: 95assert_node_consistent(const node_pointer p_nd) const 96{ 97 assert_node_consistent_(p_nd); 98} 99 100PB_DS_CLASS_T_DEC 101typename PB_DS_CLASS_C_DEC::node_consistent_t 102PB_DS_CLASS_C_DEC:: 103assert_node_consistent_(const node_pointer p_nd) const 104{ 105 if (p_nd == NULL) 106 return (std::make_pair((const_pointer)NULL,(const_pointer)NULL)); 107 108 assert_node_consistent_with_left(p_nd); 109 assert_node_consistent_with_right(p_nd); 110 111 const std::pair<const_pointer, const_pointer> 112 l_range = assert_node_consistent_(p_nd->m_p_left); 113 114 if (l_range.second != NULL) 115 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second), 116 PB_DS_V2F(p_nd->m_value))); 117 118 const std::pair<const_pointer, const_pointer> 119 r_range = assert_node_consistent_(p_nd->m_p_right); 120 121 if (r_range.first != NULL) 122 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 123 PB_DS_V2F(*r_range.first))); 124 125 return (std::make_pair((l_range.first != NULL)? l_range.first :& p_nd->m_value,(r_range.second != NULL)? r_range.second :& p_nd->m_value)); 126} 127 128PB_DS_CLASS_T_DEC 129void 130PB_DS_CLASS_C_DEC:: 131assert_node_consistent_with_left(const node_pointer p_nd) const 132{ 133 if (p_nd->m_p_left == NULL) 134 return; 135 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd); 136 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 137 PB_DS_V2F(p_nd->m_p_left->m_value))); 138} 139 140PB_DS_CLASS_T_DEC 141void 142PB_DS_CLASS_C_DEC:: 143assert_node_consistent_with_right(const node_pointer p_nd) const 144{ 145 if (p_nd->m_p_right == NULL) 146 return; 147 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd); 148 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value), 149 PB_DS_V2F(p_nd->m_value))); 150} 151 152PB_DS_CLASS_T_DEC 153void 154PB_DS_CLASS_C_DEC:: 155assert_min() const 156{ 157 assert_min_imp(m_p_head->m_p_parent); 158} 159 160PB_DS_CLASS_T_DEC 161void 162PB_DS_CLASS_C_DEC:: 163assert_min_imp(const node_pointer p_nd) const 164{ 165 if (p_nd == NULL) 166 { 167 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); 168 return; 169 } 170 171 if (p_nd->m_p_left == NULL) 172 { 173 _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left); 174 return; 175 } 176 assert_min_imp(p_nd->m_p_left); 177} 178 179PB_DS_CLASS_T_DEC 180void 181PB_DS_CLASS_C_DEC:: 182assert_max() const 183{ 184 assert_max_imp(m_p_head->m_p_parent); 185} 186 187PB_DS_CLASS_T_DEC 188void 189PB_DS_CLASS_C_DEC:: 190assert_max_imp(const node_pointer p_nd) const 191{ 192 if (p_nd == NULL) 193 { 194 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); 195 return; 196 } 197 198 if (p_nd->m_p_right == NULL) 199 { 200 _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right); 201 return; 202 } 203 204 assert_max_imp(p_nd->m_p_right); 205} 206 207PB_DS_CLASS_T_DEC 208void 209PB_DS_CLASS_C_DEC:: 210assert_iterators() const 211{ 212 size_type iterated_num = 0; 213 const_iterator prev_it = end(); 214 for (const_iterator it = begin(); it != end(); ++it) 215 { 216 ++iterated_num; 217 _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd); 218 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); 219 --upper_bound_it; 220 _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd); 221 222 if (prev_it != end()) 223 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it), 224 PB_DS_V2F(*it))); 225 prev_it = it; 226 } 227 228 _GLIBCXX_DEBUG_ASSERT(iterated_num == m_size); 229 size_type reverse_iterated_num = 0; 230 const_reverse_iterator reverse_prev_it = rend(); 231 for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend(); 232 ++reverse_it) 233 { 234 ++reverse_iterated_num; 235 _GLIBCXX_DEBUG_ASSERT(lower_bound( 236 PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd); 237 238 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it)); 239 --upper_bound_it; 240 _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd); 241 if (reverse_prev_it != rend()) 242 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it), 243 PB_DS_V2F(*reverse_it))); 244 reverse_prev_it = reverse_it; 245 } 246 _GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size); 247} 248 249PB_DS_CLASS_T_DEC 250void 251PB_DS_CLASS_C_DEC:: 252assert_consistent_with_debug_base() const 253{ 254 map_debug_base::check_size(m_size); 255 assert_consistent_with_debug_base(m_p_head->m_p_parent); 256} 257 258PB_DS_CLASS_T_DEC 259void 260PB_DS_CLASS_C_DEC:: 261assert_consistent_with_debug_base(const node_pointer p_nd) const 262{ 263 if (p_nd == NULL) 264 return; 265 map_debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value)); 266 assert_consistent_with_debug_base(p_nd->m_p_left); 267 assert_consistent_with_debug_base(p_nd->m_p_right); 268} 269 270PB_DS_CLASS_T_DEC 271void 272PB_DS_CLASS_C_DEC:: 273assert_size() const 274{ 275 _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size); 276} 277 278#endif 279