libstdc++
debug_map_base.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the terms
00008 // of the GNU General Public License as published by the Free Software
00009 // Foundation; either version 3, or (at your option) any later
00010 // version.
00011 
00012 // This library is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 // General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00027 
00028 // Permission to use, copy, modify, sell, and distribute this software
00029 // is hereby granted without fee, provided that the above copyright
00030 // notice appears in all copies, and that both that copyright notice
00031 // and this permission notice appear in supporting documentation. None
00032 // of the above authors, nor IBM Haifa Research Laboratories, make any
00033 // representation about the suitability of this software for any
00034 // purpose. It is provided "as is" without express or implied
00035 // warranty.
00036 
00037 /**
00038  * @file detail/debug_map_base.hpp
00039  * Contains a debug-mode base for all maps.
00040  */
00041 
00042 #ifndef PB_DS_DEBUG_MAP_BASE_HPP
00043 #define PB_DS_DEBUG_MAP_BASE_HPP
00044 
00045 #ifdef _GLIBCXX_DEBUG
00046 
00047 #include <list>
00048 #include <utility>
00049 #include <cstdlib>
00050 #include <iostream>
00051 #include <ext/throw_allocator.h>
00052 #include <debug/debug.h>
00053 
00054 namespace __gnu_pbds
00055 {
00056   namespace detail
00057   {
00058     // Need std::pair ostream extractor.
00059     template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2>
00060     inline std::basic_ostream<_CharT, _Traits>&
00061     operator<<(std::basic_ostream<_CharT, _Traits>& __out,
00062            const std::pair<_Tp1, _Tp2>& p)
00063     { return (__out << '(' << p.first << ',' << p.second << ')'); }
00064 
00065 #define PB_DS_CLASS_T_DEC \
00066     template<typename Key, typename Eq_Fn, typename Const_Key_Reference>
00067 
00068 #define PB_DS_CLASS_C_DEC \
00069     debug_map_base<Key, Eq_Fn, Const_Key_Reference>
00070 
00071     /// Debug base class.
00072     template<typename Key, typename Eq_Fn, typename Const_Key_Reference>
00073     class debug_map_base
00074     {
00075     private:
00076       typedef Const_Key_Reference           key_const_reference;
00077       typedef std::_GLIBCXX_STD_C::list<Key>        key_repository;
00078       typedef typename key_repository::size_type        size_type;
00079       typedef typename key_repository::iterator         iterator;
00080       typedef typename key_repository::const_iterator   const_iterator;
00081 
00082     protected:
00083       debug_map_base();
00084 
00085       debug_map_base(const PB_DS_CLASS_C_DEC&);
00086 
00087       ~debug_map_base();
00088 
00089       inline void
00090       insert_new(key_const_reference);
00091 
00092       inline void
00093       erase_existing(key_const_reference);
00094 
00095       void
00096       clear();
00097 
00098       inline void
00099       check_key_exists(key_const_reference, const char*, int) const;
00100 
00101       inline void
00102       check_key_does_not_exist(key_const_reference, const char*, int) const;
00103 
00104       inline void
00105       check_size(size_type, const char*, int) const;
00106 
00107       void
00108       swap(PB_DS_CLASS_C_DEC&);
00109 
00110       template<typename Cmp_Fn>
00111       void
00112       split(key_const_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
00113 
00114       void
00115       join(PB_DS_CLASS_C_DEC&, bool with_cleanup = true);
00116 
00117     private:
00118       void
00119       assert_valid(const char*, int) const;
00120 
00121       const_iterator
00122       find(key_const_reference) const;
00123 
00124       iterator
00125       find(key_const_reference);
00126 
00127       key_repository    m_keys;
00128       Eq_Fn         m_eq;
00129     };
00130 
00131     PB_DS_CLASS_T_DEC
00132     PB_DS_CLASS_C_DEC::
00133     debug_map_base()
00134     { PB_DS_ASSERT_VALID((*this)) }
00135 
00136     PB_DS_CLASS_T_DEC
00137     PB_DS_CLASS_C_DEC::
00138     debug_map_base(const PB_DS_CLASS_C_DEC& other)
00139     : m_keys(other.m_keys), m_eq(other.m_eq)
00140     { PB_DS_ASSERT_VALID((*this)) }
00141 
00142     PB_DS_CLASS_T_DEC
00143     PB_DS_CLASS_C_DEC::
00144     ~debug_map_base()
00145     { PB_DS_ASSERT_VALID((*this)) }
00146 
00147     PB_DS_CLASS_T_DEC
00148     inline void
00149     PB_DS_CLASS_C_DEC::
00150     insert_new(key_const_reference r_key)
00151     {
00152       PB_DS_ASSERT_VALID((*this))
00153 
00154       if (find(r_key) != m_keys.end())
00155     {
00156       std::cerr << "insert_new key already present " << r_key << std::endl;
00157       std::abort();
00158     }
00159 
00160       __try
00161     {
00162       m_keys.push_back(r_key);
00163     }
00164       __catch(...)
00165     {
00166       std::cerr << "insert_new " << r_key << std::endl;
00167       std::abort();
00168     }
00169 
00170       PB_DS_ASSERT_VALID((*this))
00171     }
00172 
00173     PB_DS_CLASS_T_DEC
00174     inline void
00175     PB_DS_CLASS_C_DEC::
00176     erase_existing(key_const_reference r_key)
00177     {
00178       PB_DS_ASSERT_VALID((*this))
00179       iterator it = find(r_key);
00180       if (it == m_keys.end())
00181     {
00182       std::cerr << "erase_existing" << r_key << std::endl;
00183       std::abort();
00184     }
00185       m_keys.erase(it);
00186       PB_DS_ASSERT_VALID((*this))
00187     }
00188 
00189     PB_DS_CLASS_T_DEC
00190     void
00191     PB_DS_CLASS_C_DEC::
00192     clear()
00193     {
00194       PB_DS_ASSERT_VALID((*this))
00195       m_keys.clear();
00196       PB_DS_ASSERT_VALID((*this))
00197     }
00198 
00199     PB_DS_CLASS_T_DEC
00200     inline void
00201     PB_DS_CLASS_C_DEC::
00202     check_key_exists(key_const_reference r_key,
00203              const char* __file, int __line) const
00204     {
00205       assert_valid(__file, __line);
00206       if (find(r_key) == m_keys.end())
00207     {
00208       std::cerr << __file << ':' << __line << ": check_key_exists "
00209             << r_key << std::endl;
00210       std::abort();
00211     }
00212     }
00213 
00214     PB_DS_CLASS_T_DEC
00215     inline void
00216     PB_DS_CLASS_C_DEC::
00217     check_key_does_not_exist(key_const_reference r_key,
00218                  const char* __file, int __line) const
00219     {
00220       assert_valid(__file, __line);
00221       if (find(r_key) != m_keys.end())
00222     {
00223       using std::cerr;
00224       using std::endl;
00225       cerr << __file << ':' << __line << ": check_key_does_not_exist "
00226            << r_key << endl;
00227       std::abort();
00228     }
00229     }
00230 
00231     PB_DS_CLASS_T_DEC
00232     inline void
00233     PB_DS_CLASS_C_DEC::
00234     check_size(size_type size, const char* __file, int __line) const
00235     {
00236       assert_valid(__file, __line);
00237       const size_type keys_size = m_keys.size();
00238       if (size != keys_size)
00239     {
00240       std::cerr << __file << ':' << __line << ": check_size "
00241             << size << " != " << keys_size << std::endl;
00242       std::abort();
00243     }
00244      }
00245 
00246     PB_DS_CLASS_T_DEC
00247     void
00248     PB_DS_CLASS_C_DEC::
00249     swap(PB_DS_CLASS_C_DEC& other)
00250     {
00251       PB_DS_ASSERT_VALID((*this))
00252       m_keys.swap(other.m_keys);
00253       std::swap(m_eq, other.m_eq);
00254       PB_DS_ASSERT_VALID((*this))
00255     }
00256 
00257     PB_DS_CLASS_T_DEC
00258     typename PB_DS_CLASS_C_DEC::const_iterator
00259     PB_DS_CLASS_C_DEC::
00260     find(key_const_reference r_key) const
00261     {
00262       PB_DS_ASSERT_VALID((*this))
00263       typedef const_iterator iterator_type;
00264       for (iterator_type it = m_keys.begin(); it != m_keys.end(); ++it)
00265     if (m_eq(*it, r_key))
00266       return it;
00267       return m_keys.end();
00268     }
00269 
00270     PB_DS_CLASS_T_DEC
00271     typename PB_DS_CLASS_C_DEC::iterator
00272     PB_DS_CLASS_C_DEC::
00273     find(key_const_reference r_key)
00274     {
00275       PB_DS_ASSERT_VALID((*this))
00276       iterator it = m_keys.begin();
00277       while (it != m_keys.end())
00278     {
00279       if (m_eq(*it, r_key))
00280         return it;
00281       ++it;
00282     }
00283       return it;
00284      }
00285 
00286     PB_DS_CLASS_T_DEC
00287     void
00288     PB_DS_CLASS_C_DEC::
00289     assert_valid(const char* __file, int __line) const
00290     {
00291       const_iterator prime_it = m_keys.begin();
00292       while (prime_it != m_keys.end())
00293     {
00294       const_iterator sec_it = prime_it;
00295       ++sec_it;
00296       while (sec_it != m_keys.end())
00297         {
00298           PB_DS_DEBUG_VERIFY(!m_eq(*sec_it, *prime_it));
00299           PB_DS_DEBUG_VERIFY(!m_eq(*prime_it, *sec_it));
00300           ++sec_it;
00301         }
00302       ++prime_it;
00303     }
00304     }
00305 
00306     PB_DS_CLASS_T_DEC
00307     template<typename Cmp_Fn>
00308     void
00309     PB_DS_CLASS_C_DEC::
00310     split(key_const_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
00311     {
00312       other.clear();
00313       iterator it = m_keys.begin();
00314       while (it != m_keys.end())
00315     if (cmp_fn(r_key, *it))
00316       {
00317         other.insert_new(*it);
00318         it = m_keys.erase(it);
00319       }
00320     else
00321       ++it;
00322     }
00323 
00324     PB_DS_CLASS_T_DEC
00325     void
00326     PB_DS_CLASS_C_DEC::
00327     join(PB_DS_CLASS_C_DEC& other, bool with_cleanup)
00328     {
00329       iterator it = other.m_keys.begin();
00330       while (it != other.m_keys.end())
00331     {
00332       insert_new(*it);
00333       if (with_cleanup)
00334         it = other.m_keys.erase(it);
00335       else
00336         ++it;
00337     }
00338       _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty());
00339     }
00340 
00341 #undef PB_DS_CLASS_T_DEC
00342 #undef PB_DS_CLASS_C_DEC
00343 
00344 } // namespace detail
00345 } // namespace __gnu_pbds
00346 
00347 
00348 #endif
00349 
00350 #endif