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