throw_allocator.h

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 /** @file ext/vstring.h
00043  *  This file is a GNU extension to the Standard C++ Library.
00044  *
00045  *  Contains an exception-throwing allocator, useful for testing
00046  *  exception safety. In addition, allocation addresses are stored and
00047  *  sanity checked.
00048  */
00049 
00050 /**
00051  * @file throw_allocator.h 
00052  */
00053 
00054 #ifndef _THROW_ALLOCATOR_H
00055 #define _THROW_ALLOCATOR_H 1
00056 
00057 #include <cmath>
00058 #include <map>
00059 #include <set>
00060 #include <string>
00061 #include <ostream>
00062 #include <stdexcept>
00063 #include <utility>
00064 #include <tr1/random>
00065 #include <bits/functexcept.h>
00066 
00067 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00068 
00069   class twister_rand_gen
00070   {
00071   public:
00072     twister_rand_gen(unsigned int seed = 
00073              static_cast<unsigned int>(std::time(0)));
00074     
00075     void
00076     init(unsigned int);
00077     
00078     double
00079     get_prob();
00080     
00081   private:
00082     std::tr1::mt19937 _M_generator;
00083   };
00084 
00085   struct forced_exception_error : public std::exception
00086   { };
00087 
00088   // Substitute for concurrence_error object in the case of -fno-exceptions.
00089   inline void
00090   __throw_forced_exception_error()
00091   {
00092 #if __EXCEPTIONS
00093     throw forced_exception_error();
00094 #else
00095     __builtin_abort();
00096 #endif
00097   }
00098 
00099   class throw_allocator_base
00100   {
00101   public:
00102     void
00103     init(unsigned long seed);
00104 
00105     static void
00106     set_throw_prob(double throw_prob);
00107 
00108     static double
00109     get_throw_prob();
00110 
00111     static void
00112     set_label(size_t l);
00113 
00114     static bool
00115     empty();
00116 
00117     struct group_throw_prob_adjustor
00118     {
00119       group_throw_prob_adjustor(size_t size) 
00120       : _M_throw_prob_orig(_S_throw_prob)
00121       {
00122     _S_throw_prob =
00123       1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
00124       }
00125 
00126       ~group_throw_prob_adjustor()
00127       { _S_throw_prob = _M_throw_prob_orig; }
00128 
00129     private:
00130       const double _M_throw_prob_orig;
00131     };
00132 
00133     struct zero_throw_prob_adjustor
00134     {
00135       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
00136       { _S_throw_prob = 0; }
00137 
00138       ~zero_throw_prob_adjustor()
00139       { _S_throw_prob = _M_throw_prob_orig; }
00140 
00141     private:
00142       const double _M_throw_prob_orig;
00143     };
00144 
00145   protected:
00146     static void
00147     insert(void*, size_t);
00148 
00149     static void
00150     erase(void*, size_t);
00151 
00152     static void
00153     throw_conditionally();
00154 
00155     // See if a particular address and size has been allocated by this
00156     // allocator.
00157     static void
00158     check_allocated(void*, size_t);
00159 
00160     // See if a given label has been allocated by this allocator.
00161     static void
00162     check_allocated(size_t);
00163 
00164   private:
00165     typedef std::pair<size_t, size_t>       alloc_data_type;
00166     typedef std::map<void*, alloc_data_type>    map_type;
00167     typedef map_type::value_type        entry_type;
00168     typedef map_type::const_iterator        const_iterator;
00169     typedef map_type::const_reference       const_reference;
00170 
00171     friend std::ostream& 
00172     operator<<(std::ostream&, const throw_allocator_base&);
00173 
00174     static entry_type
00175     make_entry(void*, size_t);
00176 
00177     static void
00178     print_to_string(std::string&);
00179 
00180     static void
00181     print_to_string(std::string&, const_reference);
00182 
00183     static twister_rand_gen     _S_g;
00184     static map_type         _S_map;
00185     static double       _S_throw_prob;
00186     static size_t       _S_label;
00187   };
00188 
00189 
00190   template<typename T>
00191     class throw_allocator : public throw_allocator_base
00192     {
00193     public:
00194       typedef size_t                size_type;
00195       typedef ptrdiff_t             difference_type;
00196       typedef T                 value_type;
00197       typedef value_type*           pointer;
00198       typedef const value_type*         const_pointer;
00199       typedef value_type&           reference;
00200       typedef const value_type&         const_reference;
00201 
00202 
00203       template<typename U>
00204       struct rebind
00205       {
00206         typedef throw_allocator<U> other;
00207       };
00208 
00209       throw_allocator() throw() { }
00210 
00211       throw_allocator(const throw_allocator&) throw() { }
00212 
00213       template<typename U>
00214       throw_allocator(const throw_allocator<U>&) throw() { }
00215 
00216       ~throw_allocator() throw() { }
00217 
00218       size_type
00219       max_size() const throw()
00220       { return std::allocator<value_type>().max_size(); }
00221 
00222       pointer
00223       allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
00224       {
00225     throw_conditionally();
00226     value_type* const a = std::allocator<value_type>().allocate(num, hint);
00227     insert(a, sizeof(value_type) * num);
00228     return a;
00229       }
00230 
00231       void
00232       construct(pointer p, const T& val)
00233       { return std::allocator<value_type>().construct(p, val); }
00234 
00235       void
00236       destroy(pointer p)
00237       { std::allocator<value_type>().destroy(p); }
00238 
00239       void
00240       deallocate(pointer p, size_type num)
00241       {
00242     erase(p, sizeof(value_type) * num);
00243     std::allocator<value_type>().deallocate(p, num);
00244       }
00245 
00246       void
00247       check_allocated(pointer p, size_type num)
00248       { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
00249 
00250       void
00251       check_allocated(size_type label)
00252       { throw_allocator_base::check_allocated(label); }
00253     };
00254 
00255   template<typename T>
00256     inline bool
00257     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
00258     { return true; }
00259 
00260   template<typename T>
00261     inline bool
00262     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
00263     { return false; }
00264 
00265   std::ostream& 
00266   operator<<(std::ostream& os, const throw_allocator_base& alloc)
00267   {
00268     std::string error;
00269     throw_allocator_base::print_to_string(error);
00270     os << error;
00271     return os;
00272   }
00273 
00274   // XXX Should be in .cc.
00275   twister_rand_gen::
00276   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
00277 
00278   void
00279   twister_rand_gen::
00280   init(unsigned int seed)
00281   { _M_generator.seed(seed); }
00282 
00283   double
00284   twister_rand_gen::
00285   get_prob()
00286   {
00287     const double eng_min = _M_generator.min();
00288     const double eng_range =
00289       static_cast<const double>(_M_generator.max() - eng_min);
00290 
00291     const double eng_res =
00292       static_cast<const double>(_M_generator() - eng_min);
00293 
00294     const double ret = eng_res / eng_range;
00295     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
00296     return ret;
00297   }
00298 
00299   twister_rand_gen throw_allocator_base::_S_g;
00300 
00301   throw_allocator_base::map_type
00302   throw_allocator_base::_S_map;
00303 
00304   double throw_allocator_base::_S_throw_prob;
00305 
00306   size_t throw_allocator_base::_S_label = 0;
00307 
00308   throw_allocator_base::entry_type
00309   throw_allocator_base::make_entry(void* p, size_t size)
00310   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
00311 
00312   void
00313   throw_allocator_base::init(unsigned long seed)
00314   { _S_g.init(seed); }
00315 
00316   void
00317   throw_allocator_base::set_throw_prob(double throw_prob)
00318   { _S_throw_prob = throw_prob; }
00319 
00320   double
00321   throw_allocator_base::get_throw_prob()
00322   { return _S_throw_prob; }
00323 
00324   void
00325   throw_allocator_base::set_label(size_t l)
00326   { _S_label = l; }
00327 
00328   void
00329   throw_allocator_base::insert(void* p, size_t size)
00330   {
00331     const_iterator found_it = _S_map.find(p);
00332     if (found_it != _S_map.end())
00333       {
00334     std::string error("throw_allocator_base::insert");
00335     error += "double insert!";
00336     error += '\n';
00337     print_to_string(error, make_entry(p, size));
00338     print_to_string(error, *found_it);
00339     std::__throw_logic_error(error.c_str());
00340       }
00341     _S_map.insert(make_entry(p, size));
00342   }
00343 
00344   bool
00345   throw_allocator_base::empty()
00346   { return _S_map.empty(); }
00347 
00348   void
00349   throw_allocator_base::erase(void* p, size_t size)
00350   {
00351     check_allocated(p, size);
00352     _S_map.erase(p);
00353   }
00354 
00355   void
00356   throw_allocator_base::check_allocated(void* p, size_t size)
00357   {
00358     const_iterator found_it = _S_map.find(p);
00359     if (found_it == _S_map.end())
00360       {
00361     std::string error("throw_allocator_base::check_allocated by value ");
00362     error += "null erase!";
00363     error += '\n';
00364     print_to_string(error, make_entry(p, size));
00365     std::__throw_logic_error(error.c_str());
00366       }
00367 
00368     if (found_it->second.second != size)
00369       {
00370     std::string error("throw_allocator_base::check_allocated by value ");
00371     error += "wrong-size erase!";
00372     error += '\n';
00373     print_to_string(error, make_entry(p, size));
00374     print_to_string(error, *found_it);
00375     std::__throw_logic_error(error.c_str());
00376       }
00377   }
00378 
00379   void
00380   throw_allocator_base::check_allocated(size_t label)
00381   {
00382     std::string found;
00383     const_iterator it = _S_map.begin();
00384     while (it != _S_map.end())
00385       {
00386     if (it->second.first == label)
00387       print_to_string(found, *it);
00388     ++it;
00389       }
00390 
00391     if (!found.empty())
00392       {
00393     std::string error("throw_allocator_base::check_allocated by label ");
00394     error += '\n';
00395     error += found;
00396     std::__throw_logic_error(error.c_str());
00397       } 
00398   }
00399 
00400   void
00401   throw_allocator_base::throw_conditionally()
00402   {
00403     if (_S_g.get_prob() < _S_throw_prob)
00404       __throw_forced_exception_error();
00405   }
00406 
00407   void
00408   throw_allocator_base::print_to_string(std::string& s)
00409   {
00410     const_iterator begin = throw_allocator_base::_S_map.begin();
00411     const_iterator end = throw_allocator_base::_S_map.end();
00412     for (; begin != end; ++begin)
00413       print_to_string(s, *begin);
00414   }
00415 
00416   void
00417   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
00418   {
00419     char buf[40];
00420     const char tab('\t');
00421     s += "address: ";
00422     sprintf(buf, "%p", ref.first);
00423     s += buf;
00424     s += tab;
00425     s += "label: ";
00426     sprintf(buf, "%u", ref.second.first);
00427     s += buf;
00428     s += tab;
00429     s += "size: ";
00430     sprintf(buf, "%u", ref.second.second);
00431     s += buf;
00432     s += '\n';
00433   }
00434 
00435 _GLIBCXX_END_NAMESPACE
00436 
00437 #endif 

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