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