debug_map_base.hpp

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