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