1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 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 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, class 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 template<typename Key, class Eq_Fn, typename Const_Key_Reference> 72 class debug_map_base 73 { 74 private: 75 typedef typename std::allocator<Key> key_allocator; 76 typedef typename key_allocator::size_type size_type; 77 typedef Const_Key_Reference const_key_reference; 78 typedef std::_GLIBCXX_STD_C::list<Key> key_set; 79 typedef typename key_set::iterator key_set_iterator; 80 typedef typename key_set::const_iterator const_key_set_iterator; 81 typedef __gnu_cxx::throw_allocator_random<Key> key_db_allocator; 82 typedef typename key_db_allocator::never_adjustor never_adjustor; 83 84 protected: 85 debug_map_base(); 86 87 debug_map_base(const PB_DS_CLASS_C_DEC& other); 88 89 ~debug_map_base(); 90 91 inline void 92 insert_new(const_key_reference r_key); 93 94 inline void 95 erase_existing(const_key_reference r_key); 96 97 void 98 clear(); 99 100 inline void 101 check_key_exists(const_key_reference r_key) const; 102 103 inline void 104 check_key_does_not_exist(const_key_reference r_key) const; 105 106 inline void 107 check_size(size_type size) const; 108 109 void 110 swap(PB_DS_CLASS_C_DEC& other); 111 112 template<typename Cmp_Fn> 113 void 114 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); 115 116 void 117 join(PB_DS_CLASS_C_DEC& other); 118 119 private: 120 void 121 assert_valid() const; 122 123 const_key_set_iterator 124 find(const_key_reference r_key) const; 125 126 key_set_iterator 127 find(const_key_reference r_key); 128 129 key_set m_key_set; 130 Eq_Fn m_eq; 131 }; 132 133 PB_DS_CLASS_T_DEC 134 PB_DS_CLASS_C_DEC:: 135 debug_map_base() 136 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 137 138 PB_DS_CLASS_T_DEC 139 PB_DS_CLASS_C_DEC:: 140 debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set) 141 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 142 143 PB_DS_CLASS_T_DEC 144 PB_DS_CLASS_C_DEC:: 145 ~debug_map_base() 146 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 147 148 PB_DS_CLASS_T_DEC 149 inline void 150 PB_DS_CLASS_C_DEC:: 151 insert_new(const_key_reference r_key) 152 { 153 _GLIBCXX_DEBUG_ONLY(assert_valid();) 154 155 if (find(r_key) != m_key_set.end()) 156 { 157 std::cerr << "insert_new key already present " << r_key << std::endl; 158 std::abort; 159 } 160 161 never_adjustor never; 162 __try 163 { 164 m_key_set.push_back(r_key); 165 } 166 __catch(...) 167 { 168 std::cerr << "insert_new " << r_key << std::endl; 169 std::abort(); 170 } 171 172 _GLIBCXX_DEBUG_ONLY(assert_valid();) 173 } 174 175 PB_DS_CLASS_T_DEC 176 inline void 177 PB_DS_CLASS_C_DEC:: 178 erase_existing(const_key_reference r_key) 179 { 180 _GLIBCXX_DEBUG_ONLY(assert_valid();) 181 key_set_iterator it = find(r_key); 182 if (it == m_key_set.end()) 183 { 184 std::cerr << "erase_existing" << r_key << std::endl; 185 std::abort(); 186 } 187 m_key_set.erase(it); 188 _GLIBCXX_DEBUG_ONLY(assert_valid();) 189 } 190 191 PB_DS_CLASS_T_DEC 192 void 193 PB_DS_CLASS_C_DEC:: 194 clear() 195 { 196 _GLIBCXX_DEBUG_ONLY(assert_valid();) 197 m_key_set.clear(); 198 _GLIBCXX_DEBUG_ONLY(assert_valid();) 199 } 200 201 PB_DS_CLASS_T_DEC 202 inline void 203 PB_DS_CLASS_C_DEC:: 204 check_key_exists(const_key_reference r_key) const 205 { 206 _GLIBCXX_DEBUG_ONLY(assert_valid();) 207 if (find(r_key) == m_key_set.end()) 208 { 209 std::cerr << "check_key_exists " << r_key << std::endl; 210 std::abort(); 211 } 212 _GLIBCXX_DEBUG_ONLY(assert_valid();) 213 } 214 215 PB_DS_CLASS_T_DEC 216 inline void 217 PB_DS_CLASS_C_DEC:: 218 check_key_does_not_exist(const_key_reference r_key) const 219 { 220 _GLIBCXX_DEBUG_ONLY(assert_valid();) 221 if (find(r_key) != m_key_set.end()) 222 { 223 using std::cerr; 224 using std::endl; 225 cerr << "check_key_does_not_exist " << 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 234 { 235 _GLIBCXX_DEBUG_ONLY(assert_valid();) 236 const size_type key_set_size = m_key_set.size(); 237 if (size != key_set_size) 238 { 239 std::cerr << "check_size " << size 240 << " " << key_set_size << std::endl; 241 std::abort(); 242 } 243 _GLIBCXX_DEBUG_ONLY(assert_valid();) 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 _GLIBCXX_DEBUG_ONLY(assert_valid();) 252 m_key_set.swap(other.m_key_set); 253 _GLIBCXX_DEBUG_ONLY(assert_valid();) 254 } 255 256 PB_DS_CLASS_T_DEC 257 typename PB_DS_CLASS_C_DEC::const_key_set_iterator 258 PB_DS_CLASS_C_DEC:: 259 find(const_key_reference r_key) const 260 { 261 _GLIBCXX_DEBUG_ONLY(assert_valid();) 262 typedef const_key_set_iterator iterator_type; 263 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it) 264 if (m_eq(*it, r_key)) 265 return it; 266 return m_key_set.end(); 267 } 268 269 PB_DS_CLASS_T_DEC 270 typename PB_DS_CLASS_C_DEC::key_set_iterator 271 PB_DS_CLASS_C_DEC:: 272 find(const_key_reference r_key) 273 { 274 _GLIBCXX_DEBUG_ONLY(assert_valid();) 275 key_set_iterator it = m_key_set.begin(); 276 while (it != m_key_set.end()) 277 { 278 if (m_eq(*it, r_key)) 279 return it; 280 ++it; 281 } 282 return it; 283 _GLIBCXX_DEBUG_ONLY(assert_valid();) 284 } 285 286 PB_DS_CLASS_T_DEC 287 void 288 PB_DS_CLASS_C_DEC:: 289 assert_valid() const 290 { 291 const_key_set_iterator prime_it = m_key_set.begin(); 292 while (prime_it != m_key_set.end()) 293 { 294 const_key_set_iterator sec_it = prime_it; 295 ++sec_it; 296 while (sec_it != m_key_set.end()) 297 { 298 _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it)); 299 _GLIBCXX_DEBUG_ASSERT(!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(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) 311 { 312 other.clear(); 313 key_set_iterator it = m_key_set.begin(); 314 while (it != m_key_set.end()) 315 if (cmp_fn(r_key, * it)) 316 { 317 other.insert_new(*it); 318 it = m_key_set.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) 328 { 329 key_set_iterator it = other.m_key_set.begin(); 330 while (it != other.m_key_set.end()) 331 { 332 insert_new(*it); 333 it = other.m_key_set.erase(it); 334 } 335 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty()); 336 } 337 338 #undef PB_DS_CLASS_T_DEC 339 #undef PB_DS_CLASS_C_DEC 340 341 } // namespace detail 342 } // namespace __gnu_pbds 343 344 #endif 345 346 #endif 347
