libstdc++
throw_allocator.h
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 /** @file ext/throw_allocator.h
00038  *  This file is a GNU extension to the Standard C++ Library.
00039  *
00040  *  Contains two exception-generating types (throw_value, throw_allocator)
00041  *  intended to be used as value and allocator types while testing
00042  *  exception safety in templatized containers and algorithms. The
00043  *  allocator has additional log and debug features. The exception
00044  *  generated is of type forced_exception_error.
00045  */
00046 
00047 #ifndef _THROW_ALLOCATOR_H
00048 #define _THROW_ALLOCATOR_H 1
00049 
00050 #include <cmath>
00051 #include <ctime>
00052 #include <map>
00053 #include <string>
00054 #include <ostream>
00055 #include <stdexcept>
00056 #include <utility>
00057 #include <bits/functexcept.h>
00058 #include <bits/move.h>
00059 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00060 # include <functional>
00061 # include <random>
00062 #else
00063 # include <tr1/functional>
00064 # include <tr1/random>
00065 #endif
00066 
00067 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00068 {
00069 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00070 
00071   /**
00072    *  @brief Thown by exception safety machinery.
00073    *  @ingroup exceptions
00074    */
00075   struct forced_error : public std::exception
00076   { };
00077 
00078   // Substitute for forced_error object when -fno-exceptions.
00079   inline void
00080   __throw_forced_error()
00081   {
00082 #if __EXCEPTIONS
00083     throw forced_error();
00084 #else
00085     __builtin_abort();
00086 #endif
00087   }
00088 
00089 
00090   /**
00091    *  @brief Base class for checking address and label information
00092    *  about allocations. Create a std::map between the allocated
00093    *  address (void*) and a datum for annotations, which are a pair of
00094    *  numbers corresponding to label and allocated size.
00095    */
00096   struct annotate_base
00097   {
00098     annotate_base()
00099     {
00100       label();
00101       map();
00102     }
00103 
00104     static void
00105     set_label(size_t l)
00106     { label() = l; }
00107 
00108     static size_t
00109     get_label()
00110     { return label(); }
00111 
00112     void
00113     insert(void* p, size_t size)
00114     {
00115       if (!p)
00116     {
00117       std::string error("annotate_base::insert null insert!\n");
00118       log_to_string(error, make_entry(p, size));
00119       std::__throw_logic_error(error.c_str());
00120     }
00121 
00122       const_iterator found = map().find(p);
00123       if (found != map().end())
00124     {
00125       std::string error("annotate_base::insert double insert!\n");
00126       log_to_string(error, make_entry(p, size));
00127       log_to_string(error, *found);
00128       std::__throw_logic_error(error.c_str());
00129     }
00130 
00131       map().insert(make_entry(p, size));
00132     }
00133 
00134     void
00135     erase(void* p, size_t size)
00136     {
00137       check_allocated(p, size);
00138       map().erase(p);
00139     }
00140 
00141     // See if a particular address and allocation size has been saved.
00142     inline void
00143     check_allocated(void* p, size_t size)
00144     {
00145       const_iterator found = map().find(p);
00146       if (found == map().end())
00147     {
00148       std::string error("annotate_base::check_allocated by value "
00149                 "null erase!\n");
00150       log_to_string(error, make_entry(p, size));
00151       std::__throw_logic_error(error.c_str());
00152     }
00153 
00154       if (found->second.second != size)
00155     {
00156       std::string error("annotate_base::check_allocated by value "
00157                 "wrong-size erase!\n");
00158       log_to_string(error, make_entry(p, size));
00159       log_to_string(error, *found);
00160       std::__throw_logic_error(error.c_str());
00161     }
00162     }
00163 
00164     // See if a given label has been allocated.
00165     inline void
00166     check_allocated(size_t label)
00167     {
00168       const_iterator beg = map().begin();
00169       const_iterator end = map().end();
00170       std::string found;
00171       while (beg != end)
00172     {
00173       if (beg->second.first == label)
00174         log_to_string(found, *beg);
00175       ++beg;
00176     }
00177 
00178       if (!found.empty())
00179     {
00180       std::string error("annotate_base::check_allocated by label\n");
00181       error += found;
00182       std::__throw_logic_error(error.c_str());
00183     }
00184     }
00185 
00186   private:
00187     typedef std::pair<size_t, size_t>       data_type;
00188     typedef std::map<void*, data_type>      map_type;
00189     typedef map_type::value_type        entry_type;
00190     typedef map_type::const_iterator        const_iterator;
00191     typedef map_type::const_reference       const_reference;
00192 
00193     friend std::ostream&
00194     operator<<(std::ostream&, const annotate_base&);
00195 
00196     entry_type
00197     make_entry(void* p, size_t size)
00198     { return std::make_pair(p, data_type(get_label(), size)); }
00199 
00200     void
00201     log_to_string(std::string& s, const_reference ref) const
00202     {
00203       char buf[40];
00204       const char tab('\t');
00205       s += "label: ";
00206       unsigned long l = static_cast<unsigned long>(ref.second.first);
00207       __builtin_sprintf(buf, "%lu", l);
00208       s += buf;
00209       s += tab;
00210       s += "size: ";
00211       l = static_cast<unsigned long>(ref.second.second);
00212       __builtin_sprintf(buf, "%lu", l);
00213       s += buf;
00214       s += tab;
00215       s += "address: ";
00216       __builtin_sprintf(buf, "%p", ref.first);
00217       s += buf;
00218       s += '\n';
00219     }
00220 
00221     static size_t&
00222     label()
00223     {
00224       static size_t _S_label(std::numeric_limits<size_t>::max());
00225       return _S_label;
00226     }
00227 
00228     static map_type&
00229     map()
00230     {
00231       static map_type _S_map;
00232       return _S_map;
00233     }
00234   };
00235 
00236   inline std::ostream&
00237   operator<<(std::ostream& os, const annotate_base& __b)
00238   {
00239     std::string error;
00240     typedef annotate_base base_type;
00241     base_type::const_iterator beg = __b.map().begin();
00242     base_type::const_iterator end = __b.map().end();
00243     for (; beg != end; ++beg)
00244       __b.log_to_string(error, *beg);
00245     return os << error;
00246   }
00247 
00248 
00249   /**
00250    *  @brief Base struct for condition policy.
00251    *
00252    * Requires a public member function with the signature
00253    * void throw_conditionally()
00254    */
00255   struct condition_base
00256   {
00257     virtual ~condition_base() { };
00258   };
00259 
00260 
00261   /**
00262    *  @brief Base class for incremental control and throw.
00263    */
00264   struct limit_condition : public condition_base
00265   {
00266     // Scope-level adjustor objects: set limit for throw at the
00267     // beginning of a scope block, and restores to previous limit when
00268     // object is destroyed on exiting the block.
00269     struct adjustor_base
00270     {
00271     private:
00272       const size_t _M_orig;
00273 
00274     public:
00275       adjustor_base() : _M_orig(limit()) { }
00276 
00277       virtual
00278       ~adjustor_base() { set_limit(_M_orig); }
00279     };
00280 
00281     /// Never enter the condition.
00282     struct never_adjustor : public adjustor_base
00283     {
00284       never_adjustor() { set_limit(std::numeric_limits<size_t>::max()); }
00285     };
00286 
00287     /// Always enter the condition.
00288     struct always_adjustor : public adjustor_base
00289     {
00290       always_adjustor() { set_limit(count()); }
00291     };
00292 
00293     /// Enter the nth condition.
00294     struct limit_adjustor : public adjustor_base
00295     {
00296       limit_adjustor(const size_t __l) { set_limit(__l); }
00297     };
00298 
00299     // Increment _S_count every time called.
00300     // If _S_count matches the limit count, throw.
00301     static void
00302     throw_conditionally()
00303     {
00304       if (count() == limit())
00305     __throw_forced_error();
00306       ++count();
00307     }
00308 
00309     static size_t&
00310     count()
00311     {
00312       static size_t _S_count(0);
00313       return _S_count;
00314     }
00315 
00316     static size_t&
00317     limit()
00318     {
00319       static size_t _S_limit(std::numeric_limits<size_t>::max());
00320       return _S_limit;
00321     }
00322 
00323     // Zero the throw counter, set limit to argument.
00324     static void
00325     set_limit(const size_t __l)
00326     {
00327       limit() = __l;
00328       count() = 0;
00329     }
00330   };
00331 
00332 
00333   /**
00334    *  @brief Base class for random probability control and throw.
00335    */
00336   struct random_condition : public condition_base
00337   {
00338     // Scope-level adjustor objects: set probability for throw at the
00339     // beginning of a scope block, and restores to previous
00340     // probability when object is destroyed on exiting the block.
00341     struct adjustor_base
00342     {
00343     private:
00344       const double _M_orig;
00345 
00346     public:
00347       adjustor_base() : _M_orig(probability()) { }
00348 
00349       virtual ~adjustor_base()
00350       { set_probability(_M_orig); }
00351     };
00352 
00353     /// Group condition.
00354     struct group_adjustor : public adjustor_base
00355     {
00356       group_adjustor(size_t size)
00357       { set_probability(1 - std::pow(double(1 - probability()),
00358                      double(0.5 / (size + 1))));
00359       }
00360     };
00361 
00362     /// Never enter the condition.
00363     struct never_adjustor : public adjustor_base
00364     {
00365       never_adjustor() { set_probability(0); }
00366     };
00367 
00368     /// Always enter the condition.
00369     struct always_adjustor : public adjustor_base
00370     {
00371       always_adjustor() { set_probability(1); }
00372     };
00373 
00374     random_condition()
00375     {
00376       probability();
00377       engine();
00378     }
00379 
00380     static void
00381     set_probability(double __p)
00382     { probability() = __p; }
00383 
00384     static void
00385     throw_conditionally()
00386     {
00387       if (generate() < probability())
00388     __throw_forced_error();
00389     }
00390 
00391     void
00392     seed(unsigned long __s)
00393     { engine().seed(__s); }
00394 
00395   private:
00396 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00397     typedef std::uniform_real_distribution<double>  distribution_type;
00398     typedef std::mt19937                engine_type;
00399 #else
00400     typedef std::tr1::uniform_real<double>      distribution_type;
00401     typedef std::tr1::mt19937               engine_type;
00402 #endif
00403 
00404     static double
00405     generate()
00406     {
00407 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00408       const distribution_type distribution(0, 1);
00409       static auto generator = std::bind(distribution, engine());
00410 #else
00411       // Use variate_generator to get normalized results.
00412       typedef std::tr1::variate_generator<engine_type, distribution_type> gen_t;
00413       distribution_type distribution(0, 1);
00414       static gen_t generator(engine(), distribution);
00415 #endif
00416 
00417       double random = generator();
00418       if (random < distribution.min() || random > distribution.max())
00419     {
00420       std::string __s("random_condition::generate");
00421       __s += "\n";
00422       __s += "random number generated is: ";
00423       char buf[40];
00424       __builtin_sprintf(buf, "%f", random);
00425       __s += buf;
00426       std::__throw_out_of_range(__s.c_str());
00427     }
00428 
00429       return random;
00430     }
00431 
00432     static double&
00433     probability()
00434     {
00435       static double _S_p;
00436       return _S_p;
00437     }
00438 
00439     static engine_type&
00440     engine()
00441     {
00442       static engine_type _S_e;
00443       return _S_e;
00444     }
00445   };
00446 
00447 
00448   /**
00449    *  @brief Class with exception generation control. Intended to be
00450    *  used as a value_type in templatized code.
00451    *
00452    *  Note: Destructor not allowed to throw.
00453    */
00454   template<typename _Cond>
00455     struct throw_value_base : public _Cond
00456     {
00457       typedef _Cond                 condition_type;
00458 
00459       using condition_type::throw_conditionally;
00460 
00461       std::size_t                   _M_i;
00462 
00463 #ifndef _GLIBCXX_IS_AGGREGATE
00464       throw_value_base() : _M_i(0)
00465       { throw_conditionally(); }
00466 
00467       throw_value_base(const throw_value_base& __v) : _M_i(__v._M_i)
00468       { throw_conditionally(); }
00469 
00470       explicit throw_value_base(const std::size_t __i) : _M_i(__i)
00471       { throw_conditionally(); }
00472 #endif
00473 
00474       throw_value_base&
00475       operator=(const throw_value_base& __v)
00476       {
00477     throw_conditionally();
00478     _M_i = __v._M_i;
00479     return *this;
00480       }
00481 
00482       throw_value_base&
00483       operator++()
00484       {
00485     throw_conditionally();
00486     ++_M_i;
00487     return *this;
00488       }
00489     };
00490 
00491   template<typename _Cond>
00492     inline void
00493     swap(throw_value_base<_Cond>& __a, throw_value_base<_Cond>& __b)
00494     {
00495       typedef throw_value_base<_Cond> throw_value;
00496       throw_value::throw_conditionally();
00497       throw_value orig(__a);
00498       __a = __b;
00499       __b = orig;
00500     }
00501 
00502   // General instantiable types requirements.
00503   template<typename _Cond>
00504     inline bool
00505     operator==(const throw_value_base<_Cond>& __a,
00506            const throw_value_base<_Cond>& __b)
00507     {
00508       typedef throw_value_base<_Cond> throw_value;
00509       throw_value::throw_conditionally();
00510       bool __ret = __a._M_i == __b._M_i;
00511       return __ret;
00512     }
00513 
00514   template<typename _Cond>
00515     inline bool
00516     operator<(const throw_value_base<_Cond>& __a,
00517           const throw_value_base<_Cond>& __b)
00518     {
00519       typedef throw_value_base<_Cond> throw_value;
00520       throw_value::throw_conditionally();
00521       bool __ret = __a._M_i < __b._M_i;
00522       return __ret;
00523     }
00524 
00525   // Numeric algorithms instantiable types requirements.
00526   template<typename _Cond>
00527     inline throw_value_base<_Cond>
00528     operator+(const throw_value_base<_Cond>& __a,
00529           const throw_value_base<_Cond>& __b)
00530     {
00531       typedef throw_value_base<_Cond> throw_value;
00532       throw_value::throw_conditionally();
00533       throw_value __ret(__a._M_i + __b._M_i);
00534       return __ret;
00535     }
00536 
00537   template<typename _Cond>
00538     inline throw_value_base<_Cond>
00539     operator-(const throw_value_base<_Cond>& __a,
00540           const throw_value_base<_Cond>& __b)
00541     {
00542       typedef throw_value_base<_Cond> throw_value;
00543       throw_value::throw_conditionally();
00544       throw_value __ret(__a._M_i - __b._M_i);
00545       return __ret;
00546     }
00547 
00548   template<typename _Cond>
00549     inline throw_value_base<_Cond>
00550     operator*(const throw_value_base<_Cond>& __a,
00551           const throw_value_base<_Cond>& __b)
00552     {
00553       typedef throw_value_base<_Cond> throw_value;
00554       throw_value::throw_conditionally();
00555       throw_value __ret(__a._M_i * __b._M_i);
00556       return __ret;
00557     }
00558 
00559 
00560   /// Type throwing via limit condition.
00561   struct throw_value_limit : public throw_value_base<limit_condition>
00562   {
00563     typedef throw_value_base<limit_condition> base_type;
00564 
00565 #ifndef _GLIBCXX_IS_AGGREGATE
00566     throw_value_limit() { }
00567 
00568     throw_value_limit(const throw_value_limit& __other)
00569     : base_type(__other._M_i) { }
00570 
00571     explicit throw_value_limit(const std::size_t __i) : base_type(__i) { }
00572 #endif
00573   };
00574 
00575   /// Type throwing via random condition.
00576   struct throw_value_random : public throw_value_base<random_condition>
00577   {
00578     typedef throw_value_base<random_condition> base_type;
00579 
00580 #ifndef _GLIBCXX_IS_AGGREGATE
00581     throw_value_random() { }
00582 
00583     throw_value_random(const throw_value_random& __other)
00584     : base_type(__other._M_i) { }
00585 
00586 
00587     explicit throw_value_random(const std::size_t __i) : base_type(__i) { }
00588 #endif
00589   };
00590 
00591 
00592   /**
00593    *  @brief Allocator class with logging and exception generation control.
00594    * Intended to be used as an allocator_type in templatized code.
00595    *  @ingroup allocators
00596    *
00597    *  Note: Deallocate not allowed to throw.
00598    */
00599   template<typename _Tp, typename _Cond>
00600     class throw_allocator_base
00601     : public annotate_base, public _Cond
00602     {
00603     public:
00604       typedef size_t                size_type;
00605       typedef ptrdiff_t             difference_type;
00606       typedef _Tp               value_type;
00607       typedef value_type*           pointer;
00608       typedef const value_type*         const_pointer;
00609       typedef value_type&           reference;
00610       typedef const value_type&         const_reference;
00611 
00612     private:
00613       typedef _Cond             condition_type;
00614 
00615       std::allocator<value_type>        _M_allocator;
00616 
00617       using condition_type::throw_conditionally;
00618 
00619     public:
00620       size_type
00621       max_size() const throw()
00622       { return _M_allocator.max_size(); }
00623 
00624       pointer
00625       address(reference __x) const { return std::__addressof(__x); }
00626 
00627       const_pointer
00628       address(const_reference __x) const { return std::__addressof(__x); }
00629 
00630       pointer
00631       allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
00632       {
00633     if (__n > this->max_size())
00634       std::__throw_bad_alloc();
00635 
00636     throw_conditionally();
00637     pointer const a = _M_allocator.allocate(__n, hint);
00638     insert(a, sizeof(value_type) * __n);
00639     return a;
00640       }
00641 
00642       void
00643       construct(pointer __p, const value_type& val)
00644       { return _M_allocator.construct(__p, val); }
00645 
00646 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00647       template<typename... _Args>
00648     void
00649     construct(pointer __p, _Args&&... __args)
00650     { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
00651 #endif
00652 
00653       void
00654       destroy(pointer __p)
00655       { _M_allocator.destroy(__p); }
00656 
00657       void
00658       deallocate(pointer __p, size_type __n)
00659       {
00660     erase(__p, sizeof(value_type) * __n);
00661     _M_allocator.deallocate(__p, __n);
00662       }
00663 
00664       void
00665       check_allocated(pointer __p, size_type __n)
00666       {
00667     size_type __t = sizeof(value_type) * __n;
00668     annotate_base::check_allocated(__p, __t);
00669       }
00670 
00671       void
00672       check_allocated(size_type __n)
00673       { annotate_base::check_allocated(__n); }
00674   };
00675 
00676   template<typename _Tp, typename _Cond>
00677     inline bool
00678     operator==(const throw_allocator_base<_Tp, _Cond>&,
00679            const throw_allocator_base<_Tp, _Cond>&)
00680     { return true; }
00681 
00682   template<typename _Tp, typename _Cond>
00683     inline bool
00684     operator!=(const throw_allocator_base<_Tp, _Cond>&,
00685            const throw_allocator_base<_Tp, _Cond>&)
00686     { return false; }
00687 
00688   /// Allocator throwing via limit condition.
00689   template<typename _Tp>
00690     struct throw_allocator_limit
00691     : public throw_allocator_base<_Tp, limit_condition>
00692     {
00693       template<typename _Tp1>
00694     struct rebind
00695     { typedef throw_allocator_limit<_Tp1> other; };
00696 
00697       throw_allocator_limit() throw() { }
00698 
00699       throw_allocator_limit(const throw_allocator_limit&) throw() { }
00700 
00701       template<typename _Tp1>
00702     throw_allocator_limit(const throw_allocator_limit<_Tp1>&) throw() { }
00703 
00704       ~throw_allocator_limit() throw() { }
00705     };
00706 
00707   /// Allocator throwing via random condition.
00708   template<typename _Tp>
00709     struct throw_allocator_random
00710     : public throw_allocator_base<_Tp, random_condition>
00711     {
00712       template<typename _Tp1>
00713     struct rebind
00714     { typedef throw_allocator_random<_Tp1> other; };
00715 
00716       throw_allocator_random() throw() { }
00717 
00718       throw_allocator_random(const throw_allocator_random&) throw() { }
00719 
00720       template<typename _Tp1>
00721     throw_allocator_random(const throw_allocator_random<_Tp1>&) throw() { }
00722 
00723       ~throw_allocator_random() throw() { }
00724     };
00725 
00726 _GLIBCXX_END_NAMESPACE_VERSION
00727 } // namespace
00728 
00729 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00730 
00731 # include <bits/functional_hash.h>
00732 
00733 namespace std _GLIBCXX_VISIBILITY(default)
00734 {
00735   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
00736   template<>
00737     struct hash<__gnu_cxx::throw_value_limit>
00738     : public std::unary_function<__gnu_cxx::throw_value_limit, size_t>
00739     {
00740       size_t
00741       operator()(const __gnu_cxx::throw_value_limit& __val) const
00742       {
00743     std::hash<std::size_t> __h;
00744     size_t __result = __h(__val._M_i);
00745     return __result;
00746       }
00747     };
00748 
00749   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
00750   template<>
00751     struct hash<__gnu_cxx::throw_value_random>
00752     : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
00753     {
00754       size_t
00755       operator()(const __gnu_cxx::throw_value_random& __val) const
00756       {
00757     std::hash<std::size_t> __h;
00758     size_t __result = __h(__val._M_i);
00759     return __result;
00760       }
00761     };
00762 } // end namespace std
00763 #endif
00764 
00765 #endif