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