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