libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file debug_map_base.hpp 00038 * Contains a debug-mode base for all maps. 00039 */ 00040 00041 #ifndef PB_DS_DEBUG_MAP_BASE_HPP 00042 #define PB_DS_DEBUG_MAP_BASE_HPP 00043 00044 #ifdef _GLIBCXX_DEBUG 00045 00046 #include <list> 00047 #include <utility> 00048 #include <cstdlib> 00049 #include <iostream> 00050 #include <ext/throw_allocator.h> 00051 #include <debug/debug.h> 00052 00053 namespace __gnu_pbds 00054 { 00055 namespace detail 00056 { 00057 // Need std::pair ostream extractor. 00058 template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2> 00059 inline std::basic_ostream<_CharT, _Traits>& 00060 operator<<(std::basic_ostream<_CharT, _Traits>& __out, 00061 const std::pair<_Tp1, _Tp2>& p) 00062 { return (__out << '(' << p.first << ',' << p.second << ')'); } 00063 00064 #define PB_DS_CLASS_T_DEC \ 00065 template<typename Key, class Eq_Fn, typename Const_Key_Reference> 00066 00067 #define PB_DS_CLASS_C_DEC \ 00068 debug_map_base<Key, Eq_Fn, Const_Key_Reference> 00069 00070 template<typename Key, class Eq_Fn, typename Const_Key_Reference> 00071 class debug_map_base 00072 { 00073 private: 00074 typedef typename std::allocator< Key> key_allocator; 00075 00076 typedef typename key_allocator::size_type size_type; 00077 00078 typedef Const_Key_Reference const_key_reference; 00079 00080 protected: 00081 debug_map_base(); 00082 00083 debug_map_base(const PB_DS_CLASS_C_DEC& other); 00084 00085 ~debug_map_base(); 00086 00087 inline void 00088 insert_new(const_key_reference r_key); 00089 00090 inline void 00091 erase_existing(const_key_reference r_key); 00092 00093 void 00094 clear(); 00095 00096 inline void 00097 check_key_exists(const_key_reference r_key) const; 00098 00099 inline void 00100 check_key_does_not_exist(const_key_reference r_key) const; 00101 00102 inline void 00103 check_size(size_type size) const; 00104 00105 void 00106 swap(PB_DS_CLASS_C_DEC& other); 00107 00108 template<typename Cmp_Fn> 00109 void 00110 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); 00111 00112 void 00113 join(PB_DS_CLASS_C_DEC& other); 00114 00115 private: 00116 typedef std::list< Key> key_set; 00117 typedef typename key_set::iterator key_set_iterator; 00118 typedef typename key_set::const_iterator const_key_set_iterator; 00119 00120 #ifdef _GLIBCXX_DEBUG 00121 void 00122 assert_valid() const; 00123 #endif 00124 00125 const_key_set_iterator 00126 find(const_key_reference r_key) const; 00127 00128 key_set_iterator 00129 find(const_key_reference r_key); 00130 00131 key_set m_key_set; 00132 Eq_Fn m_eq; 00133 }; 00134 00135 PB_DS_CLASS_T_DEC 00136 PB_DS_CLASS_C_DEC:: 00137 debug_map_base() 00138 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 00139 00140 PB_DS_CLASS_T_DEC 00141 PB_DS_CLASS_C_DEC:: 00142 debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set) 00143 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 00144 00145 PB_DS_CLASS_T_DEC 00146 PB_DS_CLASS_C_DEC:: 00147 ~debug_map_base() 00148 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 00149 00150 PB_DS_CLASS_T_DEC 00151 inline void 00152 PB_DS_CLASS_C_DEC:: 00153 insert_new(const_key_reference r_key) 00154 { 00155 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00156 __gnu_cxx::throw_allocator<char> alloc; 00157 const double orig_throw_prob = alloc.get_throw_prob(); 00158 alloc.set_throw_prob(0); 00159 if (find(r_key) != m_key_set.end()) 00160 { 00161 std::cerr << "insert_new" << r_key << std::endl; 00162 std::abort(); 00163 } 00164 00165 __try 00166 { 00167 m_key_set.push_back(r_key); 00168 } 00169 __catch(...) 00170 { 00171 std::cerr << "insert_new" << r_key << std::endl; 00172 std::abort(); 00173 } 00174 alloc.set_throw_prob(orig_throw_prob); 00175 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00176 } 00177 00178 PB_DS_CLASS_T_DEC 00179 inline void 00180 PB_DS_CLASS_C_DEC:: 00181 erase_existing(const_key_reference r_key) 00182 { 00183 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00184 key_set_iterator it = find(r_key); 00185 if (it == m_key_set.end()) 00186 { 00187 std::cerr << "erase_existing" << r_key << std::endl; 00188 std::abort(); 00189 } 00190 m_key_set.erase(it); 00191 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00192 } 00193 00194 PB_DS_CLASS_T_DEC 00195 void 00196 PB_DS_CLASS_C_DEC:: 00197 clear() 00198 { 00199 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00200 m_key_set.clear(); 00201 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00202 } 00203 00204 PB_DS_CLASS_T_DEC 00205 inline void 00206 PB_DS_CLASS_C_DEC:: 00207 check_key_exists(const_key_reference r_key) const 00208 { 00209 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00210 if (find(r_key) == m_key_set.end()) 00211 { 00212 std::cerr << "check_key_exists" << r_key << std::endl; 00213 std::abort(); 00214 } 00215 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00216 } 00217 00218 PB_DS_CLASS_T_DEC 00219 inline void 00220 PB_DS_CLASS_C_DEC:: 00221 check_key_does_not_exist(const_key_reference r_key) const 00222 { 00223 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00224 if (find(r_key) != m_key_set.end()) 00225 { 00226 using std::cerr; 00227 using std::endl; 00228 cerr << "check_key_does_not_exist" << r_key << endl; 00229 std::abort(); 00230 } 00231 } 00232 00233 PB_DS_CLASS_T_DEC 00234 inline void 00235 PB_DS_CLASS_C_DEC:: 00236 check_size(size_type size) const 00237 { 00238 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00239 const size_type key_set_size = m_key_set.size(); 00240 if (size != key_set_size) 00241 { 00242 std::cerr << "check_size " << size 00243 << " " << key_set_size << std::endl; 00244 std::abort(); 00245 } 00246 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00247 } 00248 00249 PB_DS_CLASS_T_DEC 00250 void 00251 PB_DS_CLASS_C_DEC:: 00252 swap(PB_DS_CLASS_C_DEC& other) 00253 { 00254 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00255 m_key_set.swap(other.m_key_set); 00256 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00257 } 00258 00259 PB_DS_CLASS_T_DEC 00260 typename PB_DS_CLASS_C_DEC::const_key_set_iterator 00261 PB_DS_CLASS_C_DEC:: 00262 find(const_key_reference r_key) const 00263 { 00264 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00265 typedef const_key_set_iterator iterator_type; 00266 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it) 00267 if (m_eq(*it, r_key)) 00268 return it; 00269 return m_key_set.end(); 00270 } 00271 00272 PB_DS_CLASS_T_DEC 00273 typename PB_DS_CLASS_C_DEC::key_set_iterator 00274 PB_DS_CLASS_C_DEC:: 00275 find(const_key_reference r_key) 00276 { 00277 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00278 key_set_iterator it = m_key_set.begin(); 00279 while (it != m_key_set.end()) 00280 { 00281 if (m_eq(*it, r_key)) 00282 return it; 00283 ++it; 00284 } 00285 return it; 00286 _GLIBCXX_DEBUG_ONLY(assert_valid();) 00287 } 00288 00289 #ifdef _GLIBCXX_DEBUG 00290 PB_DS_CLASS_T_DEC 00291 void 00292 PB_DS_CLASS_C_DEC:: 00293 assert_valid() const 00294 { 00295 const_key_set_iterator prime_it = m_key_set.begin(); 00296 while (prime_it != m_key_set.end()) 00297 { 00298 const_key_set_iterator sec_it = prime_it; 00299 ++sec_it; 00300 while (sec_it != m_key_set.end()) 00301 { 00302 _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it)); 00303 _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it)); 00304 ++sec_it; 00305 } 00306 ++prime_it; 00307 } 00308 } 00309 #endif 00310 00311 PB_DS_CLASS_T_DEC 00312 template<typename Cmp_Fn> 00313 void 00314 PB_DS_CLASS_C_DEC:: 00315 split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) 00316 { 00317 __gnu_cxx::throw_allocator<char> alloc; 00318 const double orig_throw_prob = alloc.get_throw_prob(); 00319 alloc.set_throw_prob(0); 00320 other.clear(); 00321 key_set_iterator it = m_key_set.begin(); 00322 while (it != m_key_set.end()) 00323 if (cmp_fn(r_key, * it)) 00324 { 00325 other.insert_new(*it); 00326 it = m_key_set.erase(it); 00327 } 00328 else 00329 ++it; 00330 alloc.set_throw_prob(orig_throw_prob); 00331 } 00332 00333 PB_DS_CLASS_T_DEC 00334 void 00335 PB_DS_CLASS_C_DEC:: 00336 join(PB_DS_CLASS_C_DEC& other) 00337 { 00338 __gnu_cxx::throw_allocator<char> alloc; 00339 const double orig_throw_prob = alloc.get_throw_prob(); 00340 alloc.set_throw_prob(0); 00341 key_set_iterator it = other.m_key_set.begin(); 00342 while (it != other.m_key_set.end()) 00343 { 00344 insert_new(*it); 00345 it = other.m_key_set.erase(it); 00346 } 00347 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty()); 00348 alloc.set_throw_prob(orig_throw_prob); 00349 } 00350 00351 #undef PB_DS_CLASS_T_DEC 00352 #undef PB_DS_CLASS_C_DEC 00353 00354 } // namespace detail 00355 } // namespace __gnu_pbds 00356 00357 #endif 00358 00359 #endif 00360