Home | History | Annotate | Download | only in bin_search_tree_ 
      1 // -*- C++ -*-
      2 
      3 // Copyright (C) 2005-2013 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
    278