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
00042
00043
00044
00045
00046
00047 #ifndef PB_DS_MAP_DEBUG_BASE_HPP
00048 #define PB_DS_MAP_DEBUG_BASE_HPP
00049
00050 #ifdef _GLIBCXX_DEBUG
00051
00052 #include <list>
00053 #include <utility>
00054 #include <ext/throw_allocator.h>
00055 #include <debug/debug.h>
00056
00057 namespace pb_ds
00058 {
00059 namespace detail
00060 {
00061
00062 #define PB_DS_CLASS_T_DEC \
00063 template<typename Key, class Eq_Fn, typename Const_Key_Reference>
00064
00065 #define PB_DS_CLASS_C_DEC \
00066 map_debug_base<Key, Eq_Fn, Const_Key_Reference>
00067
00068 template<typename Key, class Eq_Fn, typename Const_Key_Reference>
00069 class map_debug_base
00070 {
00071 private:
00072 typedef typename std::allocator< Key> key_allocator;
00073
00074 typedef typename key_allocator::size_type size_type;
00075
00076 typedef Const_Key_Reference const_key_reference;
00077
00078 protected:
00079 map_debug_base();
00080
00081 map_debug_base(const PB_DS_CLASS_C_DEC& other);
00082
00083 ~map_debug_base();
00084
00085 inline void
00086 insert_new(const_key_reference r_key);
00087
00088 inline void
00089 erase_existing(const_key_reference r_key);
00090
00091 void
00092 clear();
00093
00094 inline void
00095 check_key_exists(const_key_reference r_key) const;
00096
00097 inline void
00098 check_key_does_not_exist(const_key_reference r_key) const;
00099
00100 inline void
00101 check_size(size_type size) const;
00102
00103 void
00104 swap(PB_DS_CLASS_C_DEC& other);
00105
00106 template<typename Cmp_Fn>
00107 void
00108 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
00109
00110 void
00111 join(PB_DS_CLASS_C_DEC& other);
00112
00113 private:
00114 typedef std::list< Key> key_set;
00115 typedef typename key_set::iterator key_set_iterator;
00116 typedef typename key_set::const_iterator const_key_set_iterator;
00117
00118 #ifdef _GLIBCXX_DEBUG
00119 void
00120 assert_valid() const;
00121 #endif
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 map_debug_base()
00136 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00137
00138 PB_DS_CLASS_T_DEC
00139 PB_DS_CLASS_C_DEC::
00140 map_debug_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 ~map_debug_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 __gnu_cxx::throw_allocator<char> alloc;
00155 const double orig_throw_prob = alloc.get_throw_prob();
00156 alloc.set_throw_prob(0);
00157 if (find(r_key) != m_key_set.end())
00158 {
00159 std::cerr << "insert_new " << r_key << std::endl;
00160 abort();
00161 }
00162
00163 try
00164 {
00165 m_key_set.push_back(r_key);
00166 }
00167 catch(...)
00168 {
00169 std::cerr << "insert_new 1" << r_key << std::endl;
00170 abort();
00171 }
00172 alloc.set_throw_prob(orig_throw_prob);
00173 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00174 }
00175
00176 PB_DS_CLASS_T_DEC
00177 inline void
00178 PB_DS_CLASS_C_DEC::
00179 erase_existing(const_key_reference r_key)
00180 {
00181 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00182 key_set_iterator it = find(r_key);
00183 if (it == m_key_set.end())
00184 {
00185 std::cerr << "erase_existing " << r_key << std::endl;
00186 abort();
00187 }
00188 m_key_set.erase(it);
00189 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00190 }
00191
00192 PB_DS_CLASS_T_DEC
00193 void
00194 PB_DS_CLASS_C_DEC::
00195 clear()
00196 {
00197 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00198 m_key_set.clear();
00199 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00200 }
00201
00202 PB_DS_CLASS_T_DEC
00203 inline void
00204 PB_DS_CLASS_C_DEC::
00205 check_key_exists(const_key_reference r_key) const
00206 {
00207 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00208 if (find(r_key) == m_key_set.end())
00209 {
00210 std::cerr << "check_key_exists " << r_key << std::endl;
00211 abort();
00212 }
00213 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00214 }
00215
00216 PB_DS_CLASS_T_DEC
00217 inline void
00218 PB_DS_CLASS_C_DEC::
00219 check_key_does_not_exist(const_key_reference r_key) const
00220 {
00221 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00222 if (find(r_key) != m_key_set.end())
00223 {
00224 std::cerr << "check_key_does_not_exist " << r_key << std::endl;
00225 abort();
00226 }
00227 }
00228
00229 PB_DS_CLASS_T_DEC
00230 inline void
00231 PB_DS_CLASS_C_DEC::
00232 check_size(size_type size) const
00233 {
00234 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00235 const size_type key_set_size = m_key_set.size();
00236 if (size != key_set_size)
00237 {
00238 std::cerr << "check_size " << size
00239 << " " << key_set_size << std::endl;
00240 abort();
00241 }
00242 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00243 }
00244
00245 PB_DS_CLASS_T_DEC
00246 void
00247 PB_DS_CLASS_C_DEC::
00248 swap(PB_DS_CLASS_C_DEC& other)
00249 {
00250 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00251 m_key_set.swap(other.m_key_set);
00252 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00253 }
00254
00255 PB_DS_CLASS_T_DEC
00256 typename PB_DS_CLASS_C_DEC::const_key_set_iterator
00257 PB_DS_CLASS_C_DEC::
00258 find(const_key_reference r_key) const
00259 {
00260 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00261 typedef const_key_set_iterator iterator_type;
00262 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
00263 if (m_eq(*it, r_key))
00264 return it;
00265 return m_key_set.end();
00266 }
00267
00268 PB_DS_CLASS_T_DEC
00269 typename PB_DS_CLASS_C_DEC::key_set_iterator
00270 PB_DS_CLASS_C_DEC::
00271 find(const_key_reference r_key)
00272 {
00273 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00274 key_set_iterator it = m_key_set.begin();
00275 while (it != m_key_set.end())
00276 {
00277 if (m_eq(*it, r_key))
00278 return it;
00279 ++it;
00280 }
00281 return it;
00282 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00283 }
00284
00285 #ifdef _GLIBCXX_DEBUG
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 #endif
00306
00307 PB_DS_CLASS_T_DEC
00308 template<typename Cmp_Fn>
00309 void
00310 PB_DS_CLASS_C_DEC::
00311 split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
00312 {
00313 __gnu_cxx::throw_allocator<char> alloc;
00314 const double orig_throw_prob = alloc.get_throw_prob();
00315 alloc.set_throw_prob(0);
00316 other.clear();
00317 key_set_iterator it = m_key_set.begin();
00318 while (it != m_key_set.end())
00319 if (cmp_fn(r_key, * it))
00320 {
00321 other.insert_new(*it);
00322 it = m_key_set.erase(it);
00323 }
00324 else
00325 ++it;
00326 alloc.set_throw_prob(orig_throw_prob);
00327 }
00328
00329 PB_DS_CLASS_T_DEC
00330 void
00331 PB_DS_CLASS_C_DEC::
00332 join(PB_DS_CLASS_C_DEC& other)
00333 {
00334 __gnu_cxx::throw_allocator<char> alloc;
00335 const double orig_throw_prob = alloc.get_throw_prob();
00336 alloc.set_throw_prob(0);
00337 key_set_iterator it = other.m_key_set.begin();
00338 while (it != other.m_key_set.end())
00339 {
00340 insert_new(*it);
00341 it = other.m_key_set.erase(it);
00342 }
00343 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
00344 alloc.set_throw_prob(orig_throw_prob);
00345 }
00346
00347 #undef PB_DS_CLASS_T_DEC
00348 #undef PB_DS_CLASS_C_DEC
00349
00350 }
00351 }
00352
00353 #endif
00354
00355 #endif
00356