libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 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 detail/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, typename 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 /// Debug base class. 00071 template<typename Key, typename Eq_Fn, typename Const_Key_Reference> 00072 class debug_map_base 00073 { 00074 private: 00075 typedef Const_Key_Reference key_const_reference; 00076 typedef std::_GLIBCXX_STD_C::list<Key> key_repository; 00077 typedef typename key_repository::size_type size_type; 00078 typedef typename key_repository::iterator iterator; 00079 typedef typename key_repository::const_iterator const_iterator; 00080 00081 protected: 00082 debug_map_base(); 00083 00084 debug_map_base(const PB_DS_CLASS_C_DEC&); 00085 00086 ~debug_map_base(); 00087 00088 inline void 00089 insert_new(key_const_reference); 00090 00091 inline void 00092 erase_existing(key_const_reference); 00093 00094 void 00095 clear(); 00096 00097 inline void 00098 check_key_exists(key_const_reference, const char*, int) const; 00099 00100 inline void 00101 check_key_does_not_exist(key_const_reference, const char*, int) const; 00102 00103 inline void 00104 check_size(size_type, const char*, int) const; 00105 00106 void 00107 swap(PB_DS_CLASS_C_DEC&); 00108 00109 template<typename Cmp_Fn> 00110 void 00111 split(key_const_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); 00112 00113 void 00114 join(PB_DS_CLASS_C_DEC&, bool with_cleanup = true); 00115 00116 private: 00117 void 00118 assert_valid(const char*, int) const; 00119 00120 const_iterator 00121 find(key_const_reference) const; 00122 00123 iterator 00124 find(key_const_reference); 00125 00126 key_repository m_keys; 00127 Eq_Fn m_eq; 00128 }; 00129 00130 PB_DS_CLASS_T_DEC 00131 PB_DS_CLASS_C_DEC:: 00132 debug_map_base() 00133 { PB_DS_ASSERT_VALID((*this)) } 00134 00135 PB_DS_CLASS_T_DEC 00136 PB_DS_CLASS_C_DEC:: 00137 debug_map_base(const PB_DS_CLASS_C_DEC& other) 00138 : m_keys(other.m_keys), m_eq(other.m_eq) 00139 { PB_DS_ASSERT_VALID((*this)) } 00140 00141 PB_DS_CLASS_T_DEC 00142 PB_DS_CLASS_C_DEC:: 00143 ~debug_map_base() 00144 { PB_DS_ASSERT_VALID((*this)) } 00145 00146 PB_DS_CLASS_T_DEC 00147 inline void 00148 PB_DS_CLASS_C_DEC:: 00149 insert_new(key_const_reference r_key) 00150 { 00151 PB_DS_ASSERT_VALID((*this)) 00152 00153 if (find(r_key) != m_keys.end()) 00154 { 00155 std::cerr << "insert_new key already present " << r_key << std::endl; 00156 std::abort(); 00157 } 00158 00159 __try 00160 { 00161 m_keys.push_back(r_key); 00162 } 00163 __catch(...) 00164 { 00165 std::cerr << "insert_new " << r_key << std::endl; 00166 std::abort(); 00167 } 00168 00169 PB_DS_ASSERT_VALID((*this)) 00170 } 00171 00172 PB_DS_CLASS_T_DEC 00173 inline void 00174 PB_DS_CLASS_C_DEC:: 00175 erase_existing(key_const_reference r_key) 00176 { 00177 PB_DS_ASSERT_VALID((*this)) 00178 iterator it = find(r_key); 00179 if (it == m_keys.end()) 00180 { 00181 std::cerr << "erase_existing" << r_key << std::endl; 00182 std::abort(); 00183 } 00184 m_keys.erase(it); 00185 PB_DS_ASSERT_VALID((*this)) 00186 } 00187 00188 PB_DS_CLASS_T_DEC 00189 void 00190 PB_DS_CLASS_C_DEC:: 00191 clear() 00192 { 00193 PB_DS_ASSERT_VALID((*this)) 00194 m_keys.clear(); 00195 PB_DS_ASSERT_VALID((*this)) 00196 } 00197 00198 PB_DS_CLASS_T_DEC 00199 inline void 00200 PB_DS_CLASS_C_DEC:: 00201 check_key_exists(key_const_reference r_key, 00202 const char* __file, int __line) const 00203 { 00204 assert_valid(__file, __line); 00205 if (find(r_key) == m_keys.end()) 00206 { 00207 std::cerr << __file << ':' << __line << ": check_key_exists " 00208 << r_key << std::endl; 00209 std::abort(); 00210 } 00211 } 00212 00213 PB_DS_CLASS_T_DEC 00214 inline void 00215 PB_DS_CLASS_C_DEC:: 00216 check_key_does_not_exist(key_const_reference r_key, 00217 const char* __file, int __line) const 00218 { 00219 assert_valid(__file, __line); 00220 if (find(r_key) != m_keys.end()) 00221 { 00222 using std::cerr; 00223 using std::endl; 00224 cerr << __file << ':' << __line << ": check_key_does_not_exist " 00225 << r_key << endl; 00226 std::abort(); 00227 } 00228 } 00229 00230 PB_DS_CLASS_T_DEC 00231 inline void 00232 PB_DS_CLASS_C_DEC:: 00233 check_size(size_type size, const char* __file, int __line) const 00234 { 00235 assert_valid(__file, __line); 00236 const size_type keys_size = m_keys.size(); 00237 if (size != keys_size) 00238 { 00239 std::cerr << __file << ':' << __line << ": check_size " 00240 << size << " != " << keys_size << std::endl; 00241 std::abort(); 00242 } 00243 } 00244 00245 PB_DS_CLASS_T_DEC 00246 void 00247 PB_DS_CLASS_C_DEC:: 00248 swap(PB_DS_CLASS_C_DEC& other) 00249 { 00250 PB_DS_ASSERT_VALID((*this)) 00251 m_keys.swap(other.m_keys); 00252 std::swap(m_eq, other.m_eq); 00253 PB_DS_ASSERT_VALID((*this)) 00254 } 00255 00256 PB_DS_CLASS_T_DEC 00257 typename PB_DS_CLASS_C_DEC::const_iterator 00258 PB_DS_CLASS_C_DEC:: 00259 find(key_const_reference r_key) const 00260 { 00261 PB_DS_ASSERT_VALID((*this)) 00262 typedef const_iterator iterator_type; 00263 for (iterator_type it = m_keys.begin(); it != m_keys.end(); ++it) 00264 if (m_eq(*it, r_key)) 00265 return it; 00266 return m_keys.end(); 00267 } 00268 00269 PB_DS_CLASS_T_DEC 00270 typename PB_DS_CLASS_C_DEC::iterator 00271 PB_DS_CLASS_C_DEC:: 00272 find(key_const_reference r_key) 00273 { 00274 PB_DS_ASSERT_VALID((*this)) 00275 iterator it = m_keys.begin(); 00276 while (it != m_keys.end()) 00277 { 00278 if (m_eq(*it, r_key)) 00279 return it; 00280 ++it; 00281 } 00282 return it; 00283 } 00284 00285 PB_DS_CLASS_T_DEC 00286 void 00287 PB_DS_CLASS_C_DEC:: 00288 assert_valid(const char* __file, int __line) const 00289 { 00290 const_iterator prime_it = m_keys.begin(); 00291 while (prime_it != m_keys.end()) 00292 { 00293 const_iterator sec_it = prime_it; 00294 ++sec_it; 00295 while (sec_it != m_keys.end()) 00296 { 00297 PB_DS_DEBUG_VERIFY(!m_eq(*sec_it, *prime_it)); 00298 PB_DS_DEBUG_VERIFY(!m_eq(*prime_it, *sec_it)); 00299 ++sec_it; 00300 } 00301 ++prime_it; 00302 } 00303 } 00304 00305 PB_DS_CLASS_T_DEC 00306 template<typename Cmp_Fn> 00307 void 00308 PB_DS_CLASS_C_DEC:: 00309 split(key_const_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) 00310 { 00311 other.clear(); 00312 iterator it = m_keys.begin(); 00313 while (it != m_keys.end()) 00314 if (cmp_fn(r_key, *it)) 00315 { 00316 other.insert_new(*it); 00317 it = m_keys.erase(it); 00318 } 00319 else 00320 ++it; 00321 } 00322 00323 PB_DS_CLASS_T_DEC 00324 void 00325 PB_DS_CLASS_C_DEC:: 00326 join(PB_DS_CLASS_C_DEC& other, bool with_cleanup) 00327 { 00328 iterator it = other.m_keys.begin(); 00329 while (it != other.m_keys.end()) 00330 { 00331 insert_new(*it); 00332 if (with_cleanup) 00333 it = other.m_keys.erase(it); 00334 else 00335 ++it; 00336 } 00337 _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty()); 00338 } 00339 00340 #undef PB_DS_CLASS_T_DEC 00341 #undef PB_DS_CLASS_C_DEC 00342 00343 } // namespace detail 00344 } // namespace __gnu_pbds 00345 00346 00347 #endif 00348 00349 #endif