debug_fn_imps.hpp revision 169692
1100206Sdd// -*- C++ -*- 2100206Sdd 3100206Sdd// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4100206Sdd// 5100206Sdd// This file is part of the GNU ISO C++ Library. This library is free 6100206Sdd// software; you can redistribute it and/or modify it under the terms 7100206Sdd// of the GNU General Public License as published by the Free Software 8100206Sdd// Foundation; either version 2, or (at your option) any later 9100206Sdd// version. 10100206Sdd 11100206Sdd// This library is distributed in the hope that it will be useful, but 12100206Sdd// WITHOUT ANY WARRANTY; without even the implied warranty of 13100206Sdd// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14100206Sdd// General Public License for more details. 15100206Sdd 16100206Sdd// You should have received a copy of the GNU General Public License 17100206Sdd// along with this library; see the file COPYING. If not, write to 18100206Sdd// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19100206Sdd// MA 02111-1307, USA. 20100206Sdd 21100206Sdd// As a special exception, you may use this file as part of a free 22100206Sdd// software library without restriction. Specifically, if other files 23100206Sdd// instantiate templates or use macros or inline functions from this 24100206Sdd// file, or you compile this file and link it with other files to 25100206Sdd// produce an executable, this file does not by itself cause the 26100206Sdd// resulting executable to be covered by the GNU General Public 27100206Sdd// License. This exception does not however invalidate any other 28253252Sjh// reasons why the executable file might be covered by the GNU General 29100206Sdd// Public License. 30100206Sdd 31100206Sdd// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32100206Sdd 33100206Sdd// Permission to use, copy, modify, sell, and distribute this software 34100206Sdd// is hereby granted without fee, provided that the above copyright 35100206Sdd// notice appears in all copies, and that both that copyright notice 36100206Sdd// and this permission notice appear in supporting documentation. None 37107703Sru// of the above authors, nor IBM Haifa Research Laboratories, make any 38100206Sdd// representation about the suitability of this software for any 39100206Sdd// purpose. It is provided "as is" without express or implied 40100206Sdd// warranty. 41100206Sdd 42100206Sdd/** 43100206Sdd * @file debug_fn_imps.hpp 44100206Sdd * Contains an implementation class for bin_search_tree_. 45100206Sdd */ 46118056Ssimon 47118056Ssimon#ifdef _GLIBCXX_DEBUG 48118056Ssimon 49100206SddPB_DS_CLASS_T_DEC 50100206Sddvoid 51100206SddPB_DS_CLASS_C_DEC:: 52100206Sddassert_valid() const 53100206Sdd{ 54100206Sdd structure_only_assert_valid(); 55236780Sjoel assert_consistent_with_debug_base(); 56100206Sdd assert_size(); 57100206Sdd assert_iterators(); 58100206Sdd if (m_p_head->m_p_parent == NULL) 59100206Sdd { 60100206Sdd _GLIBCXX_DEBUG_ASSERT(m_size == 0); 61100206Sdd } 62100206Sdd else 63100206Sdd { 64100206Sdd _GLIBCXX_DEBUG_ASSERT(m_size > 0); 65100206Sdd } 66100206Sdd} 67100795Sdd 68100206SddPB_DS_CLASS_T_DEC 69100206Sddvoid 70100206SddPB_DS_CLASS_C_DEC:: 71100206Sddstructure_only_assert_valid() const 72100206Sdd{ 73100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head != NULL); 74100206Sdd if (m_p_head->m_p_parent == NULL) 75100206Sdd { 76100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); 77100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); 78100206Sdd } 79100206Sdd else 80100206Sdd { 81100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head); 82100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head); 83100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head); 84100206Sdd } 85100206Sdd 86100206Sdd if (m_p_head->m_p_parent != NULL) 87100206Sdd assert_node_consistent(m_p_head->m_p_parent); 88100206Sdd assert_min(); 89100206Sdd assert_max(); 90100206Sdd} 91236780Sjoel 92100206SddPB_DS_CLASS_T_DEC 93100206Sddvoid 94100206SddPB_DS_CLASS_C_DEC:: 95100206Sddassert_node_consistent(const node_pointer p_nd) const 96100206Sdd{ 97100206Sdd assert_node_consistent_(p_nd); 98100206Sdd} 99100206Sdd 100100206SddPB_DS_CLASS_T_DEC 101236780Sjoeltypename PB_DS_CLASS_C_DEC::node_consistent_t 102100206SddPB_DS_CLASS_C_DEC:: 103100206Sddassert_node_consistent_(const node_pointer p_nd) const 104100206Sdd{ 105100206Sdd if (p_nd == NULL) 106100206Sdd return (std::make_pair((const_pointer)NULL,(const_pointer)NULL)); 107100206Sdd 108100206Sdd assert_node_consistent_with_left(p_nd); 109100206Sdd assert_node_consistent_with_right(p_nd); 110100206Sdd 111107703Sru const std::pair<const_pointer, const_pointer> 112100206Sdd l_range = assert_node_consistent_(p_nd->m_p_left); 113100206Sdd 114100206Sdd if (l_range.second != NULL) 115100206Sdd _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second), 116100206Sdd PB_DS_V2F(p_nd->m_value))); 117107703Sru 118107703Sru const std::pair<const_pointer, const_pointer> 119107703Sru r_range = assert_node_consistent_(p_nd->m_p_right); 120137304Sdd 121100206Sdd if (r_range.first != NULL) 122100206Sdd _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 123107703Sru PB_DS_V2F(*r_range.first))); 124107703Sru 125100206Sdd 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)); 126100206Sdd} 127100206Sdd 128100206SddPB_DS_CLASS_T_DEC 129100206Sddvoid 130100206SddPB_DS_CLASS_C_DEC:: 131100206Sddassert_node_consistent_with_left(const node_pointer p_nd) const 132100206Sdd{ 133100206Sdd if (p_nd->m_p_left == NULL) 134100206Sdd return; 135100206Sdd _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd); 136100206Sdd _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 137100206Sdd PB_DS_V2F(p_nd->m_p_left->m_value))); 138100206Sdd} 139100206Sdd 140100206SddPB_DS_CLASS_T_DEC 141100206Sddvoid 142100206SddPB_DS_CLASS_C_DEC:: 143100206Sddassert_node_consistent_with_right(const node_pointer p_nd) const 144100206Sdd{ 145100206Sdd if (p_nd->m_p_right == NULL) 146137304Sdd return; 147100206Sdd _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd); 148100206Sdd _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value), 149142669Sphk PB_DS_V2F(p_nd->m_value))); 150142669Sphk} 151100799Sdd 152107703SruPB_DS_CLASS_T_DEC 153100799Sddvoid 154100799SddPB_DS_CLASS_C_DEC:: 155100206Sddassert_min() const 156100206Sdd{ 157100206Sdd assert_min_imp(m_p_head->m_p_parent); 158100206Sdd} 159236780Sjoel 160100206SddPB_DS_CLASS_T_DEC 161100206Sddvoid 162137304SddPB_DS_CLASS_C_DEC:: 163137304Sddassert_min_imp(const node_pointer p_nd) const 164100206Sdd{ 165100206Sdd if (p_nd == NULL) 166100206Sdd { 167100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); 168100206Sdd return; 169100206Sdd } 170107703Sru 171100206Sdd if (p_nd->m_p_left == NULL) 172107703Sru { 173100206Sdd _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left); 174100206Sdd return; 175100206Sdd } 176100206Sdd assert_min_imp(p_nd->m_p_left); 177100206Sdd} 178236780Sjoel 179100206SddPB_DS_CLASS_T_DEC 180100206Sddvoid 181100206SddPB_DS_CLASS_C_DEC:: 182100206Sddassert_max() const 183100206Sdd{ 184100206Sdd assert_max_imp(m_p_head->m_p_parent); 185100206Sdd} 186100206Sdd 187100206SddPB_DS_CLASS_T_DEC 188100206Sddvoid 189137304SddPB_DS_CLASS_C_DEC:: 190100206Sddassert_max_imp(const node_pointer p_nd) const 191100206Sdd{ 192100206Sdd if (p_nd == NULL) 193253252Sjh { 194100206Sdd _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); 195100206Sdd return; 196100206Sdd } 197100206Sdd 198100206Sdd if (p_nd->m_p_right == NULL) 199100206Sdd { 200204166Sgavin _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right); 201204166Sgavin return; 202204166Sgavin } 203100206Sdd 204100206Sdd assert_max_imp(p_nd->m_p_right); 205100206Sdd} 206137303Sdd 207137303SddPB_DS_CLASS_T_DEC 208100206Sddvoid 209100206SddPB_DS_CLASS_C_DEC:: 210100206Sddassert_iterators() const 211100206Sdd{ 212100206Sdd size_type iterated_num = 0; 213100206Sdd const_iterator prev_it = end(); 214100206Sdd for (const_iterator it = begin(); it != end(); ++it) 215100206Sdd { 216100206Sdd ++iterated_num; 217253252Sjh _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd); 218253252Sjh const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); 219100206Sdd --upper_bound_it; 220100795Sdd _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd); 221137304Sdd 222100206Sdd if (prev_it != end()) 223100206Sdd _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it), 224137304Sdd PB_DS_V2F(*it))); 225137304Sdd prev_it = it; 226100206Sdd } 227137304Sdd 228100206Sdd _GLIBCXX_DEBUG_ASSERT(iterated_num == m_size); 229100795Sdd size_type reverse_iterated_num = 0; 230100206Sdd const_reverse_iterator reverse_prev_it = rend(); 231100206Sdd for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend(); 232100206Sdd ++reverse_it) 233100206Sdd { 234100795Sdd ++reverse_iterated_num; 235100206Sdd _GLIBCXX_DEBUG_ASSERT(lower_bound( 236100206Sdd PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd); 237100206Sdd 238100206Sdd const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it)); 239100206Sdd --upper_bound_it; 240100206Sdd _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd); 241137304Sdd if (reverse_prev_it != rend()) 242100206Sdd _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it), 243147369Sru PB_DS_V2F(*reverse_it))); 244236780Sjoel reverse_prev_it = reverse_it; 245147369Sru } 246164006Sdanger _GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size); 247164006Sdanger} 248164006Sdanger 249147369SruPB_DS_CLASS_T_DEC 250164006Sdangervoid 251164006SdangerPB_DS_CLASS_C_DEC:: 252204166Sgavinassert_consistent_with_debug_base() const 253233648Seadler{ 254233648Seadler map_debug_base::check_size(m_size); 255164006Sdanger assert_consistent_with_debug_base(m_p_head->m_p_parent); 256164006Sdanger} 257164006Sdanger 258164006SdangerPB_DS_CLASS_T_DEC 259164006Sdangervoid 260164006SdangerPB_DS_CLASS_C_DEC:: 261164006Sdangerassert_consistent_with_debug_base(const node_pointer p_nd) const 262164006Sdanger{ 263147369Sru if (p_nd == NULL) 264100795Sdd return; 265100206Sdd map_debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value)); 266100206Sdd assert_consistent_with_debug_base(p_nd->m_p_left); 267100206Sdd assert_consistent_with_debug_base(p_nd->m_p_right); 268100206Sdd} 269107703Sru 270100206SddPB_DS_CLASS_T_DEC 271100206Sddvoid 272100206SddPB_DS_CLASS_C_DEC:: 273100206Sddassert_size() const 274100206Sdd{ 275100206Sdd _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size); 276100206Sdd} 277249720Sjoel 278100206Sdd#endif 279249720Sjoel