debug_map_base.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
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
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, class 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 template<typename Key, class Eq_Fn, typename Const_Key_Reference>
00071 class debug_map_base
00072 {
00073 private:
00074 typedef typename std::allocator< Key> key_allocator;
00075
00076 typedef typename key_allocator::size_type size_type;
00077
00078 typedef Const_Key_Reference const_key_reference;
00079
00080 protected:
00081 debug_map_base();
00082
00083 debug_map_base(const PB_DS_CLASS_C_DEC& other);
00084
00085 ~debug_map_base();
00086
00087 inline void
00088 insert_new(const_key_reference r_key);
00089
00090 inline void
00091 erase_existing(const_key_reference r_key);
00092
00093 void
00094 clear();
00095
00096 inline void
00097 check_key_exists(const_key_reference r_key) const;
00098
00099 inline void
00100 check_key_does_not_exist(const_key_reference r_key) const;
00101
00102 inline void
00103 check_size(size_type size) const;
00104
00105 void
00106 swap(PB_DS_CLASS_C_DEC& other);
00107
00108 template<typename Cmp_Fn>
00109 void
00110 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
00111
00112 void
00113 join(PB_DS_CLASS_C_DEC& other);
00114
00115 private:
00116 typedef std::list< Key> key_set;
00117 typedef typename key_set::iterator key_set_iterator;
00118 typedef typename key_set::const_iterator const_key_set_iterator;
00119
00120 #ifdef _GLIBCXX_DEBUG
00121 void
00122 assert_valid() const;
00123 #endif
00124
00125 const_key_set_iterator
00126 find(const_key_reference r_key) const;
00127
00128 key_set_iterator
00129 find(const_key_reference r_key);
00130
00131 key_set m_key_set;
00132 Eq_Fn m_eq;
00133 };
00134
00135 PB_DS_CLASS_T_DEC
00136 PB_DS_CLASS_C_DEC::
00137 debug_map_base()
00138 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00139
00140 PB_DS_CLASS_T_DEC
00141 PB_DS_CLASS_C_DEC::
00142 debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set)
00143 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00144
00145 PB_DS_CLASS_T_DEC
00146 PB_DS_CLASS_C_DEC::
00147 ~debug_map_base()
00148 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00149
00150 PB_DS_CLASS_T_DEC
00151 inline void
00152 PB_DS_CLASS_C_DEC::
00153 insert_new(const_key_reference r_key)
00154 {
00155 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00156 __gnu_cxx::throw_allocator<char> alloc;
00157 const double orig_throw_prob = alloc.get_throw_prob();
00158 alloc.set_throw_prob(0);
00159 if (find(r_key) != m_key_set.end())
00160 {
00161 std::cerr << "insert_new" << r_key << std::endl;
00162 std::abort();
00163 }
00164
00165 __try
00166 {
00167 m_key_set.push_back(r_key);
00168 }
00169 __catch(...)
00170 {
00171 std::cerr << "insert_new" << r_key << std::endl;
00172 std::abort();
00173 }
00174 alloc.set_throw_prob(orig_throw_prob);
00175 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00176 }
00177
00178 PB_DS_CLASS_T_DEC
00179 inline void
00180 PB_DS_CLASS_C_DEC::
00181 erase_existing(const_key_reference r_key)
00182 {
00183 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00184 key_set_iterator it = find(r_key);
00185 if (it == m_key_set.end())
00186 {
00187 std::cerr << "erase_existing" << r_key << std::endl;
00188 std::abort();
00189 }
00190 m_key_set.erase(it);
00191 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00192 }
00193
00194 PB_DS_CLASS_T_DEC
00195 void
00196 PB_DS_CLASS_C_DEC::
00197 clear()
00198 {
00199 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00200 m_key_set.clear();
00201 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00202 }
00203
00204 PB_DS_CLASS_T_DEC
00205 inline void
00206 PB_DS_CLASS_C_DEC::
00207 check_key_exists(const_key_reference r_key) const
00208 {
00209 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00210 if (find(r_key) == m_key_set.end())
00211 {
00212 std::cerr << "check_key_exists" << r_key << std::endl;
00213 std::abort();
00214 }
00215 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00216 }
00217
00218 PB_DS_CLASS_T_DEC
00219 inline void
00220 PB_DS_CLASS_C_DEC::
00221 check_key_does_not_exist(const_key_reference r_key) const
00222 {
00223 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00224 if (find(r_key) != m_key_set.end())
00225 {
00226 using std::cerr;
00227 using std::endl;
00228 cerr << "check_key_does_not_exist" << r_key << endl;
00229 std::abort();
00230 }
00231 }
00232
00233 PB_DS_CLASS_T_DEC
00234 inline void
00235 PB_DS_CLASS_C_DEC::
00236 check_size(size_type size) const
00237 {
00238 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00239 const size_type key_set_size = m_key_set.size();
00240 if (size != key_set_size)
00241 {
00242 std::cerr << "check_size " << size
00243 << " " << key_set_size << std::endl;
00244 std::abort();
00245 }
00246 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00247 }
00248
00249 PB_DS_CLASS_T_DEC
00250 void
00251 PB_DS_CLASS_C_DEC::
00252 swap(PB_DS_CLASS_C_DEC& other)
00253 {
00254 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00255 m_key_set.swap(other.m_key_set);
00256 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00257 }
00258
00259 PB_DS_CLASS_T_DEC
00260 typename PB_DS_CLASS_C_DEC::const_key_set_iterator
00261 PB_DS_CLASS_C_DEC::
00262 find(const_key_reference r_key) const
00263 {
00264 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00265 typedef const_key_set_iterator iterator_type;
00266 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
00267 if (m_eq(*it, r_key))
00268 return it;
00269 return m_key_set.end();
00270 }
00271
00272 PB_DS_CLASS_T_DEC
00273 typename PB_DS_CLASS_C_DEC::key_set_iterator
00274 PB_DS_CLASS_C_DEC::
00275 find(const_key_reference r_key)
00276 {
00277 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00278 key_set_iterator it = m_key_set.begin();
00279 while (it != m_key_set.end())
00280 {
00281 if (m_eq(*it, r_key))
00282 return it;
00283 ++it;
00284 }
00285 return it;
00286 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00287 }
00288
00289 #ifdef _GLIBCXX_DEBUG
00290 PB_DS_CLASS_T_DEC
00291 void
00292 PB_DS_CLASS_C_DEC::
00293 assert_valid() const
00294 {
00295 const_key_set_iterator prime_it = m_key_set.begin();
00296 while (prime_it != m_key_set.end())
00297 {
00298 const_key_set_iterator sec_it = prime_it;
00299 ++sec_it;
00300 while (sec_it != m_key_set.end())
00301 {
00302 _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it));
00303 _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it));
00304 ++sec_it;
00305 }
00306 ++prime_it;
00307 }
00308 }
00309 #endif
00310
00311 PB_DS_CLASS_T_DEC
00312 template<typename Cmp_Fn>
00313 void
00314 PB_DS_CLASS_C_DEC::
00315 split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
00316 {
00317 __gnu_cxx::throw_allocator<char> alloc;
00318 const double orig_throw_prob = alloc.get_throw_prob();
00319 alloc.set_throw_prob(0);
00320 other.clear();
00321 key_set_iterator it = m_key_set.begin();
00322 while (it != m_key_set.end())
00323 if (cmp_fn(r_key, * it))
00324 {
00325 other.insert_new(*it);
00326 it = m_key_set.erase(it);
00327 }
00328 else
00329 ++it;
00330 alloc.set_throw_prob(orig_throw_prob);
00331 }
00332
00333 PB_DS_CLASS_T_DEC
00334 void
00335 PB_DS_CLASS_C_DEC::
00336 join(PB_DS_CLASS_C_DEC& other)
00337 {
00338 __gnu_cxx::throw_allocator<char> alloc;
00339 const double orig_throw_prob = alloc.get_throw_prob();
00340 alloc.set_throw_prob(0);
00341 key_set_iterator it = other.m_key_set.begin();
00342 while (it != other.m_key_set.end())
00343 {
00344 insert_new(*it);
00345 it = other.m_key_set.erase(it);
00346 }
00347 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
00348 alloc.set_throw_prob(orig_throw_prob);
00349 }
00350
00351 #undef PB_DS_CLASS_T_DEC
00352 #undef PB_DS_CLASS_C_DEC
00353
00354 }
00355 }
00356
00357 #endif
00358
00359 #endif
00360