1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the terms 8 // of the GNU General Public License as published by the Free Software 9 // Foundation; either version 3, or (at your option) any later 10 // version. 11 12 // This library is distributed in the hope that it will be useful, but 13 // WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 // General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 27 28 // Permission to use, copy, modify, sell, and distribute this software 29 // is hereby granted without fee, provided that the above copyright 30 // notice appears in all copies, and that both that copyright notice 31 // and this permission notice appear in supporting documentation. None 32 // of the above authors, nor IBM Haifa Research Laboratories, make any 33 // representation about the suitability of this software for any 34 // purpose. It is provided "as is" without express or implied 35 // warranty. 36 37 /** 38 * @file detail/debug_map_base.hpp 39 * Contains a debug-mode base for all maps. 40 */ 41 42 #ifndef PB_DS_DEBUG_MAP_BASE_HPP 43 #define PB_DS_DEBUG_MAP_BASE_HPP 44 45 #ifdef _GLIBCXX_DEBUG 46 47 #include <list> 48 #include <utility> 49 #include <cstdlib> 50 #include <iostream> 51 #include <ext/throw_allocator.h> 52 #include <debug/debug.h> 53 54 namespace __gnu_pbds 55 { 56 namespace detail 57 { 58 // Need std::pair ostream extractor. 59 template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2> 60 inline std::basic_ostream<_CharT, _Traits>& 61 operator<<(std::basic_ostream<_CharT, _Traits>& __out, 62 const std::pair<_Tp1, _Tp2>& p) 63 { return (__out << '(' << p.first << ',' << p.second << ')'); } 64 65 #define PB_DS_CLASS_T_DEC \ 66 template<typename Key, typename Eq_Fn, typename Const_Key_Reference> 67 68 #define PB_DS_CLASS_C_DEC \ 69 debug_map_base<Key, Eq_Fn, Const_Key_Reference> 70 71 /// Debug base class. 72 template<typename Key, typename Eq_Fn, typename Const_Key_Reference> 73 class debug_map_base 74 { 75 private: 76 typedef Const_Key_Reference key_const_reference; 77 typedef std::_GLIBCXX_STD_C::list<Key> key_repository; 78 typedef typename key_repository::size_type size_type; 79 typedef typename key_repository::iterator iterator; 80 typedef typename key_repository::const_iterator const_iterator; 81 82 protected: 83 debug_map_base(); 84 85 debug_map_base(const PB_DS_CLASS_C_DEC&); 86 87 ~debug_map_base(); 88 89 inline void 90 insert_new(key_const_reference); 91 92 inline void 93 erase_existing(key_const_reference); 94 95 void 96 clear(); 97 98 inline void 99 check_key_exists(key_const_reference, const char*, int) const; 100 101 inline void 102 check_key_does_not_exist(key_const_reference, const char*, int) const; 103 104 inline void 105 check_size(size_type, const char*, int) const; 106 107 void 108 swap(PB_DS_CLASS_C_DEC&); 109 110 template<typename Cmp_Fn> 111 void 112 split(key_const_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); 113 114 void 115 join(PB_DS_CLASS_C_DEC&, bool with_cleanup = true); 116 117 private: 118 void 119 assert_valid(const char*, int) const; 120 121 const_iterator 122 find(key_const_reference) const; 123 124 iterator 125 find(key_const_reference); 126 127 key_repository m_keys; 128 Eq_Fn m_eq; 129 }; 130 131 PB_DS_CLASS_T_DEC 132 PB_DS_CLASS_C_DEC:: 133 debug_map_base() 134 { PB_DS_ASSERT_VALID((*this)) } 135 136 PB_DS_CLASS_T_DEC 137 PB_DS_CLASS_C_DEC:: 138 debug_map_base(const PB_DS_CLASS_C_DEC& other) 139 : m_keys(other.m_keys), m_eq(other.m_eq) 140 { PB_DS_ASSERT_VALID((*this)) } 141 142 PB_DS_CLASS_T_DEC 143 PB_DS_CLASS_C_DEC:: 144 ~debug_map_base() 145 { PB_DS_ASSERT_VALID((*this)) } 146 147 PB_DS_CLASS_T_DEC 148 inline void 149 PB_DS_CLASS_C_DEC:: 150 insert_new(key_const_reference r_key) 151 { 152 PB_DS_ASSERT_VALID((*this)) 153 154 if (find(r_key) != m_keys.end()) 155 { 156 std::cerr << "insert_new key already present " << r_key << std::endl; 157 std::abort(); 158 } 159 160 __try 161 { 162 m_keys.push_back(r_key); 163 } 164 __catch(...) 165 { 166 std::cerr << "insert_new " << r_key << std::endl; 167 std::abort(); 168 } 169 170 PB_DS_ASSERT_VALID((*this)) 171 } 172 173 PB_DS_CLASS_T_DEC 174 inline void 175 PB_DS_CLASS_C_DEC:: 176 erase_existing(key_const_reference r_key) 177 { 178 PB_DS_ASSERT_VALID((*this)) 179 iterator it = find(r_key); 180 if (it == m_keys.end()) 181 { 182 std::cerr << "erase_existing" << r_key << std::endl; 183 std::abort(); 184 } 185 m_keys.erase(it); 186 PB_DS_ASSERT_VALID((*this)) 187 } 188 189 PB_DS_CLASS_T_DEC 190 void 191 PB_DS_CLASS_C_DEC:: 192 clear() 193 { 194 PB_DS_ASSERT_VALID((*this)) 195 m_keys.clear(); 196 PB_DS_ASSERT_VALID((*this)) 197 } 198 199 PB_DS_CLASS_T_DEC 200 inline void 201 PB_DS_CLASS_C_DEC:: 202 check_key_exists(key_const_reference r_key, 203 const char* __file, int __line) const 204 { 205 assert_valid(__file, __line); 206 if (find(r_key) == m_keys.end()) 207 { 208 std::cerr << __file << ':' << __line << ": check_key_exists " 209 << r_key << std::endl; 210 std::abort(); 211 } 212 } 213 214 PB_DS_CLASS_T_DEC 215 inline void 216 PB_DS_CLASS_C_DEC:: 217 check_key_does_not_exist(key_const_reference r_key, 218 const char* __file, int __line) const 219 { 220 assert_valid(__file, __line); 221 if (find(r_key) != m_keys.end()) 222 { 223 using std::cerr; 224 using std::endl; 225 cerr << __file << ':' << __line << ": check_key_does_not_exist " 226 << r_key << endl; 227 std::abort(); 228 } 229 } 230 231 PB_DS_CLASS_T_DEC 232 inline void 233 PB_DS_CLASS_C_DEC:: 234 check_size(size_type size, const char* __file, int __line) const 235 { 236 assert_valid(__file, __line); 237 const size_type keys_size = m_keys.size(); 238 if (size != keys_size) 239 { 240 std::cerr << __file << ':' << __line << ": check_size " 241 << size << " != " << keys_size << std::endl; 242 std::abort(); 243 } 244 } 245 246 PB_DS_CLASS_T_DEC 247 void 248 PB_DS_CLASS_C_DEC:: 249 swap(PB_DS_CLASS_C_DEC& other) 250 { 251 PB_DS_ASSERT_VALID((*this)) 252 m_keys.swap(other.m_keys); 253 std::swap(m_eq, other.m_eq); 254 PB_DS_ASSERT_VALID((*this)) 255 } 256 257 PB_DS_CLASS_T_DEC 258 typename PB_DS_CLASS_C_DEC::const_iterator 259 PB_DS_CLASS_C_DEC:: 260 find(key_const_reference r_key) const 261 { 262 PB_DS_ASSERT_VALID((*this)) 263 typedef const_iterator iterator_type; 264 for (iterator_type it = m_keys.begin(); it != m_keys.end(); ++it) 265 if (m_eq(*it, r_key)) 266 return it; 267 return m_keys.end(); 268 } 269 270 PB_DS_CLASS_T_DEC 271 typename PB_DS_CLASS_C_DEC::iterator 272 PB_DS_CLASS_C_DEC:: 273 find(key_const_reference r_key) 274 { 275 PB_DS_ASSERT_VALID((*this)) 276 iterator it = m_keys.begin(); 277 while (it != m_keys.end()) 278 { 279 if (m_eq(*it, r_key)) 280 return it; 281 ++it; 282 } 283 return it; 284 } 285 286 PB_DS_CLASS_T_DEC 287 void 288 PB_DS_CLASS_C_DEC:: 289 assert_valid(const char* __file, int __line) const 290 { 291 const_iterator prime_it = m_keys.begin(); 292 while (prime_it != m_keys.end()) 293 { 294 const_iterator sec_it = prime_it; 295 ++sec_it; 296 while (sec_it != m_keys.end()) 297 { 298 PB_DS_DEBUG_VERIFY(!m_eq(*sec_it, *prime_it)); 299 PB_DS_DEBUG_VERIFY(!m_eq(*prime_it, *sec_it)); 300 ++sec_it; 301 } 302 ++prime_it; 303 } 304 } 305 306 PB_DS_CLASS_T_DEC 307 template<typename Cmp_Fn> 308 void 309 PB_DS_CLASS_C_DEC:: 310 split(key_const_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) 311 { 312 other.clear(); 313 iterator it = m_keys.begin(); 314 while (it != m_keys.end()) 315 if (cmp_fn(r_key, *it)) 316 { 317 other.insert_new(*it); 318 it = m_keys.erase(it); 319 } 320 else 321 ++it; 322 } 323 324 PB_DS_CLASS_T_DEC 325 void 326 PB_DS_CLASS_C_DEC:: 327 join(PB_DS_CLASS_C_DEC& other, bool with_cleanup) 328 { 329 iterator it = other.m_keys.begin(); 330 while (it != other.m_keys.end()) 331 { 332 insert_new(*it); 333 if (with_cleanup) 334 it = other.m_keys.erase(it); 335 else 336 ++it; 337 } 338 _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty()); 339 } 340 341 #undef PB_DS_CLASS_T_DEC 342 #undef PB_DS_CLASS_C_DEC 343 344 } // namespace detail 345 } // namespace __gnu_pbds 346 347 348 #endif 349 350 #endif 351
