OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [ext/] [pb_ds/] [detail/] [bin_search_tree_/] [debug_fn_imps.hpp] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
// -*- C++ -*-
2
 
3
// Copyright (C) 2005, 2006, 2009, 2010, 2011 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 _GLIBCXX_DEBUG
42
 
43
PB_DS_CLASS_T_DEC
44
void
45
PB_DS_CLASS_C_DEC::
46
assert_valid(const char* __file, int __line) const
47
{
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);
52
  if (m_p_head->m_p_parent == 0)
53
    {
54
      PB_DS_DEBUG_VERIFY(m_size == 0);
55
    }
56
  else
57
    {
58
      PB_DS_DEBUG_VERIFY(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 char* __file, int __line) const
66
{
67
  PB_DS_DEBUG_VERIFY(m_p_head != 0);
68
  if (m_p_head->m_p_parent == 0)
69
    {
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);
72
    }
73
  else
74
    {
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);
78
    }
79
 
80
  if (m_p_head->m_p_parent != 0)
81
    assert_node_consistent(m_p_head->m_p_parent, __file, __line);
82
  assert_min(__file, __line);
83
  assert_max(__file, __line);
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,
90
                       const char* __file, int __line) const
91
{
92
  assert_node_consistent_(p_nd, __file, __line);
93
}
94
 
95
PB_DS_CLASS_T_DEC
96
typename PB_DS_CLASS_C_DEC::node_consistent_t
97
PB_DS_CLASS_C_DEC::
98
assert_node_consistent_(const node_pointer p_nd,
99
                        const char* __file, int __line) const
100
{
101
  if (p_nd == 0)
102
    return (std::make_pair((const_pointer)0,(const_pointer)0));
103
 
104
  assert_node_consistent_with_left(p_nd, __file, __line);
105
  assert_node_consistent_with_right(p_nd, __file, __line);
106
 
107
  const std::pair<const_pointer, const_pointer>
108
    l_range = assert_node_consistent_(p_nd->m_p_left, __file, __line);
109
 
110
  if (l_range.second != 0)
111
    PB_DS_DEBUG_VERIFY(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second),
112
                                          PB_DS_V2F(p_nd->m_value)));
113
 
114
  const std::pair<const_pointer, const_pointer>
115
    r_range = assert_node_consistent_(p_nd->m_p_right, __file, __line);
116
 
117
  if (r_range.first != 0)
118
    PB_DS_DEBUG_VERIFY(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value),
119
                                             PB_DS_V2F(*r_range.first)));
120
 
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);
123
}
124
 
125
PB_DS_CLASS_T_DEC
126
void
127
PB_DS_CLASS_C_DEC::
128
assert_node_consistent_with_left(const node_pointer p_nd,
129
                                 const char* __file, int __line) const
130
{
131
  if (p_nd->m_p_left == 0)
132
    return;
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)));
136
}
137
 
138
PB_DS_CLASS_T_DEC
139
void
140
PB_DS_CLASS_C_DEC::
141
assert_node_consistent_with_right(const node_pointer p_nd,
142
                                  const char* __file, int __line) const
143
{
144
  if (p_nd->m_p_right == 0)
145
    return;
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)));
149
}
150
 
151
PB_DS_CLASS_T_DEC
152
void
153
PB_DS_CLASS_C_DEC::
154
assert_min(const char* __file, int __line) const
155
{
156
  assert_min_imp(m_p_head->m_p_parent, __file, __line);
157
}
158
 
159
PB_DS_CLASS_T_DEC
160
void
161
PB_DS_CLASS_C_DEC::
162
assert_min_imp(const node_pointer p_nd, const char* __file, int __line) const
163
{
164
  if (p_nd == 0)
165
    {
166
      PB_DS_DEBUG_VERIFY(m_p_head->m_p_left == m_p_head);
167
      return;
168
    }
169
 
170
  if (p_nd->m_p_left == 0)
171
    {
172
      PB_DS_DEBUG_VERIFY(p_nd == m_p_head->m_p_left);
173
      return;
174
    }
175
  assert_min_imp(p_nd->m_p_left, __file, __line);
176
}
177
 
178
PB_DS_CLASS_T_DEC
179
void
180
PB_DS_CLASS_C_DEC::
181
assert_max(const char* __file, int __line) const
182
{
183
  assert_max_imp(m_p_head->m_p_parent, __file, __line);
184
}
185
 
186
PB_DS_CLASS_T_DEC
187
void
188
PB_DS_CLASS_C_DEC::
189
assert_max_imp(const node_pointer p_nd,
190
               const char* __file, int __line) const
191
{
192
  if (p_nd == 0)
193
    {
194
      PB_DS_DEBUG_VERIFY(m_p_head->m_p_right == m_p_head);
195
      return;
196
    }
197
 
198
  if (p_nd->m_p_right == 0)
199
    {
200
      PB_DS_DEBUG_VERIFY(p_nd == m_p_head->m_p_right);
201
      return;
202
    }
203
 
204
  assert_max_imp(p_nd->m_p_right, __file, __line);
205
}
206
 
207
PB_DS_CLASS_T_DEC
208
void
209
PB_DS_CLASS_C_DEC::
210
assert_iterators(const char* __file, int __line) 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
      PB_DS_DEBUG_VERIFY(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
      PB_DS_DEBUG_VERIFY(upper_bound_it.m_p_nd == it.m_p_nd);
221
 
222
      if (prev_it != end())
223
        PB_DS_DEBUG_VERIFY(Cmp_Fn::operator()(PB_DS_V2F(*prev_it),
224
                                              PB_DS_V2F(*it)));
225
      prev_it = it;
226
    }
227
 
228
  PB_DS_DEBUG_VERIFY(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
      PB_DS_DEBUG_VERIFY(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
      PB_DS_DEBUG_VERIFY(upper_bound_it.m_p_nd == reverse_it.m_p_nd);
241
      if (reverse_prev_it != rend())
242
        PB_DS_DEBUG_VERIFY(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it),
243
                                               PB_DS_V2F(*reverse_it)));
244
      reverse_prev_it = reverse_it;
245
    }
246
  PB_DS_DEBUG_VERIFY(reverse_iterated_num == m_size);
247
}
248
 
249
PB_DS_CLASS_T_DEC
250
void
251
PB_DS_CLASS_C_DEC::
252
assert_consistent_with_debug_base(const char* __file, int __line) const
253
{
254
  debug_base::check_size(m_size, __file, __line);
255
  assert_consistent_with_debug_base(m_p_head->m_p_parent, __file, __line);
256
}
257
 
258
PB_DS_CLASS_T_DEC
259
void
260
PB_DS_CLASS_C_DEC::
261
assert_consistent_with_debug_base(const node_pointer p_nd,
262
                                  const char* __file, int __line) const
263
{
264
  if (p_nd == 0)
265
    return;
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);
269
}
270
 
271
PB_DS_CLASS_T_DEC
272
void
273
PB_DS_CLASS_C_DEC::
274
assert_size(const char* __file, int __line) const
275
{ PB_DS_DEBUG_VERIFY(recursive_count(m_p_head->m_p_parent) == m_size); }
276
 
277
#endif

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.