Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/11/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp
$ cat -n /usr/include/c++/11/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp 1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2021 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 bin_search_tree_/debug_fn_imps.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41 #ifdef PB_DS_CLASS_C_DEC 42 43 #ifdef _GLIBCXX_DEBUG 44 45 PB_DS_CLASS_T_DEC 46 void 47 PB_DS_CLASS_C_DEC:: 48 assert_valid(const char* __file, int __line) const 49 { 50 structure_only_assert_valid(__file, __line); 51 assert_consistent_with_debug_base(__file, __line); 52 assert_size(__file, __line); 53 assert_iterators(__file, __line); 54 if (m_p_head->m_p_parent == 0) 55 { 56 PB_DS_DEBUG_VERIFY(m_size == 0); 57 } 58 else 59 { 60 PB_DS_DEBUG_VERIFY(m_size > 0); 61 } 62 } 63 64 PB_DS_CLASS_T_DEC 65 void 66 PB_DS_CLASS_C_DEC:: 67 structure_only_assert_valid(const char* __file, int __line) const 68 { 69 PB_DS_DEBUG_VERIFY(m_p_head != 0); 70 if (m_p_head->m_p_parent == 0) 71 { 72 PB_DS_DEBUG_VERIFY(m_p_head->m_p_left == m_p_head); 73 PB_DS_DEBUG_VERIFY(m_p_head->m_p_right == m_p_head); 74 } 75 else 76 { 77 PB_DS_DEBUG_VERIFY(m_p_head->m_p_parent->m_p_parent == m_p_head); 78 PB_DS_DEBUG_VERIFY(m_p_head->m_p_left != m_p_head); 79 PB_DS_DEBUG_VERIFY(m_p_head->m_p_right != m_p_head); 80 } 81 82 if (m_p_head->m_p_parent != 0) 83 assert_node_consistent(m_p_head->m_p_parent, __file, __line); 84 assert_min(__file, __line); 85 assert_max(__file, __line); 86 } 87 88 PB_DS_CLASS_T_DEC 89 void 90 PB_DS_CLASS_C_DEC:: 91 assert_node_consistent(const node_pointer p_nd, 92 const char* __file, int __line) const 93 { 94 assert_node_consistent_(p_nd, __file, __line); 95 } 96 97 PB_DS_CLASS_T_DEC 98 typename PB_DS_CLASS_C_DEC::node_consistent_t 99 PB_DS_CLASS_C_DEC:: 100 assert_node_consistent_(const node_pointer p_nd, 101 const char* __file, int __line) const 102 { 103 if (p_nd == 0) 104 return (std::make_pair((const_pointer)0,(const_pointer)0)); 105 106 assert_node_consistent_with_left(p_nd, __file, __line); 107 assert_node_consistent_with_right(p_nd, __file, __line); 108 109 const std::pair<const_pointer, const_pointer> 110 l_range = assert_node_consistent_(p_nd->m_p_left, __file, __line); 111 112 if (l_range.second != 0) 113 PB_DS_DEBUG_VERIFY(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second), 114 PB_DS_V2F(p_nd->m_value))); 115 116 const std::pair<const_pointer, const_pointer> 117 r_range = assert_node_consistent_(p_nd->m_p_right, __file, __line); 118 119 if (r_range.first != 0) 120 PB_DS_DEBUG_VERIFY(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 121 PB_DS_V2F(*r_range.first))); 122 123 return std::make_pair((l_range.first != 0) ? l_range.first : &p_nd->m_value, 124 (r_range.second != 0)? r_range.second : &p_nd->m_value); 125 } 126 127 PB_DS_CLASS_T_DEC 128 void 129 PB_DS_CLASS_C_DEC:: 130 assert_node_consistent_with_left(const node_pointer p_nd, 131 const char* __file, int __line) const 132 { 133 if (p_nd->m_p_left == 0) 134 return; 135 PB_DS_DEBUG_VERIFY(p_nd->m_p_left->m_p_parent == p_nd); 136 PB_DS_DEBUG_VERIFY(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), 137 PB_DS_V2F(p_nd->m_p_left->m_value))); 138 } 139 140 PB_DS_CLASS_T_DEC 141 void 142 PB_DS_CLASS_C_DEC:: 143 assert_node_consistent_with_right(const node_pointer p_nd, 144 const char* __file, int __line) const 145 { 146 if (p_nd->m_p_right == 0) 147 return; 148 PB_DS_DEBUG_VERIFY(p_nd->m_p_right->m_p_parent == p_nd); 149 PB_DS_DEBUG_VERIFY(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value), 150 PB_DS_V2F(p_nd->m_value))); 151 } 152 153 PB_DS_CLASS_T_DEC 154 void 155 PB_DS_CLASS_C_DEC:: 156 assert_min(const char* __file, int __line) const 157 { 158 assert_min_imp(m_p_head->m_p_parent, __file, __line); 159 } 160 161 PB_DS_CLASS_T_DEC 162 void 163 PB_DS_CLASS_C_DEC:: 164 assert_min_imp(const node_pointer p_nd, const char* __file, int __line) const 165 { 166 if (p_nd == 0) 167 { 168 PB_DS_DEBUG_VERIFY(m_p_head->m_p_left == m_p_head); 169 return; 170 } 171 172 if (p_nd->m_p_left == 0) 173 { 174 PB_DS_DEBUG_VERIFY(p_nd == m_p_head->m_p_left); 175 return; 176 } 177 assert_min_imp(p_nd->m_p_left, __file, __line); 178 } 179 180 PB_DS_CLASS_T_DEC 181 void 182 PB_DS_CLASS_C_DEC:: 183 assert_max(const char* __file, int __line) const 184 { 185 assert_max_imp(m_p_head->m_p_parent, __file, __line); 186 } 187 188 PB_DS_CLASS_T_DEC 189 void 190 PB_DS_CLASS_C_DEC:: 191 assert_max_imp(const node_pointer p_nd, 192 const char* __file, int __line) const 193 { 194 if (p_nd == 0) 195 { 196 PB_DS_DEBUG_VERIFY(m_p_head->m_p_right == m_p_head); 197 return; 198 } 199 200 if (p_nd->m_p_right == 0) 201 { 202 PB_DS_DEBUG_VERIFY(p_nd == m_p_head->m_p_right); 203 return; 204 } 205 206 assert_max_imp(p_nd->m_p_right, __file, __line); 207 } 208 209 PB_DS_CLASS_T_DEC 210 void 211 PB_DS_CLASS_C_DEC:: 212 assert_iterators(const char* __file, int __line) const 213 { 214 size_type iterated_num = 0; 215 const_iterator prev_it = end(); 216 for (const_iterator it = begin(); it != end(); ++it) 217 { 218 ++iterated_num; 219 PB_DS_DEBUG_VERIFY(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd); 220 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); 221 --upper_bound_it; 222 PB_DS_DEBUG_VERIFY(upper_bound_it.m_p_nd == it.m_p_nd); 223 224 if (prev_it != end()) 225 PB_DS_DEBUG_VERIFY(Cmp_Fn::operator()(PB_DS_V2F(*prev_it), 226 PB_DS_V2F(*it))); 227 prev_it = it; 228 } 229 230 PB_DS_DEBUG_VERIFY(iterated_num == m_size); 231 size_type reverse_iterated_num = 0; 232 const_reverse_iterator reverse_prev_it = rend(); 233 for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend(); 234 ++reverse_it) 235 { 236 ++reverse_iterated_num; 237 PB_DS_DEBUG_VERIFY(lower_bound( 238 PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd); 239 240 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it)); 241 --upper_bound_it; 242 PB_DS_DEBUG_VERIFY(upper_bound_it.m_p_nd == reverse_it.m_p_nd); 243 if (reverse_prev_it != rend()) 244 PB_DS_DEBUG_VERIFY(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it), 245 PB_DS_V2F(*reverse_it))); 246 reverse_prev_it = reverse_it; 247 } 248 PB_DS_DEBUG_VERIFY(reverse_iterated_num == m_size); 249 } 250 251 PB_DS_CLASS_T_DEC 252 void 253 PB_DS_CLASS_C_DEC:: 254 assert_consistent_with_debug_base(const char* __file, int __line) const 255 { 256 debug_base::check_size(m_size, __file, __line); 257 assert_consistent_with_debug_base(m_p_head->m_p_parent, __file, __line); 258 } 259 260 PB_DS_CLASS_T_DEC 261 void 262 PB_DS_CLASS_C_DEC:: 263 assert_consistent_with_debug_base(const node_pointer p_nd, 264 const char* __file, int __line) const 265 { 266 if (p_nd == 0) 267 return; 268 debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value), __file, __line); 269 assert_consistent_with_debug_base(p_nd->m_p_left, __file, __line); 270 assert_consistent_with_debug_base(p_nd->m_p_right, __file, __line); 271 } 272 273 PB_DS_CLASS_T_DEC 274 void 275 PB_DS_CLASS_C_DEC:: 276 assert_size(const char* __file, int __line) const 277 { PB_DS_DEBUG_VERIFY(recursive_count(m_p_head->m_p_parent) == m_size); } 278 279 #endif 280 #endif
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
