map_debug_base.hpp

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00032 
00033 // Permission to use, copy, modify, sell, and distribute this software
00034 // is hereby granted without fee, provided that the above copyright
00035 // notice appears in all copies, and that both that copyright notice
00036 // and this permission notice appear in supporting documentation. None
00037 // of the above authors, nor IBM Haifa Research Laboratories, make any
00038 // representation about the suitability of this software for any
00039 // purpose. It is provided "as is" without express or implied
00040 // warranty.
00041  
00042 /**
00043  * @file map_debug_base.hpp
00044  * Contains a debug-mode base for all maps.
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 } // namespace detail
00351 } // namespace pb_ds
00352 
00353 #endif 
00354 
00355 #endif 
00356 

Generated on Thu Nov 1 13:12:09 2007 for libstdc++ by  doxygen 1.5.1