# 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