libstdc++
throw_allocator.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
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 _GLIBCXX_USE_NOEXCEPT
00622       { return _M_allocator.max_size(); }
00623 
00624       pointer
00625       address(reference __x) const _GLIBCXX_NOEXCEPT
00626       { return std::__addressof(__x); }
00627 
00628       const_pointer
00629       address(const_reference __x) const _GLIBCXX_NOEXCEPT
00630       { return std::__addressof(__x); }
00631 
00632       pointer
00633       allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
00634       {
00635     if (__n > this->max_size())
00636       std::__throw_bad_alloc();
00637 
00638     throw_conditionally();
00639     pointer const a = _M_allocator.allocate(__n, hint);
00640     insert(a, sizeof(value_type) * __n);
00641     return a;
00642       }
00643 
00644 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00645       template<typename _Up, typename... _Args>
00646         void
00647         construct(_Up* __p, _Args&&... __args)
00648     { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
00649 
00650       template<typename _Up>
00651         void 
00652         destroy(_Up* __p)
00653         { _M_allocator.destroy(__p); }
00654 #else
00655       void
00656       construct(pointer __p, const value_type& val)
00657       { return _M_allocator.construct(__p, val); }
00658 
00659       void
00660       destroy(pointer __p)
00661       { _M_allocator.destroy(__p); }
00662 #endif
00663 
00664       void
00665       deallocate(pointer __p, size_type __n)
00666       {
00667     erase(__p, sizeof(value_type) * __n);
00668     _M_allocator.deallocate(__p, __n);
00669       }
00670 
00671       void
00672       check_allocated(pointer __p, size_type __n)
00673       {
00674     size_type __t = sizeof(value_type) * __n;
00675     annotate_base::check_allocated(__p, __t);
00676       }
00677 
00678       void
00679       check_allocated(size_type __n)
00680       { annotate_base::check_allocated(__n); }
00681   };
00682 
00683   template<typename _Tp, typename _Cond>
00684     inline bool
00685     operator==(const throw_allocator_base<_Tp, _Cond>&,
00686            const throw_allocator_base<_Tp, _Cond>&)
00687     { return true; }
00688 
00689   template<typename _Tp, typename _Cond>
00690     inline bool
00691     operator!=(const throw_allocator_base<_Tp, _Cond>&,
00692            const throw_allocator_base<_Tp, _Cond>&)
00693     { return false; }
00694 
00695   /// Allocator throwing via limit condition.
00696   template<typename _Tp>
00697     struct throw_allocator_limit
00698     : public throw_allocator_base<_Tp, limit_condition>
00699     {
00700       template<typename _Tp1>
00701     struct rebind
00702     { typedef throw_allocator_limit<_Tp1> other; };
00703 
00704       throw_allocator_limit() _GLIBCXX_USE_NOEXCEPT { }
00705 
00706       throw_allocator_limit(const throw_allocator_limit&)
00707       _GLIBCXX_USE_NOEXCEPT { }
00708 
00709       template<typename _Tp1>
00710     throw_allocator_limit(const throw_allocator_limit<_Tp1>&)
00711     _GLIBCXX_USE_NOEXCEPT { }
00712 
00713       ~throw_allocator_limit() _GLIBCXX_USE_NOEXCEPT { }
00714     };
00715 
00716   /// Allocator throwing via random condition.
00717   template<typename _Tp>
00718     struct throw_allocator_random
00719     : public throw_allocator_base<_Tp, random_condition>
00720     {
00721       template<typename _Tp1>
00722     struct rebind
00723     { typedef throw_allocator_random<_Tp1> other; };
00724 
00725       throw_allocator_random() _GLIBCXX_USE_NOEXCEPT { }
00726 
00727       throw_allocator_random(const throw_allocator_random&)
00728       _GLIBCXX_USE_NOEXCEPT { }
00729 
00730       template<typename _Tp1>
00731     throw_allocator_random(const throw_allocator_random<_Tp1>&)
00732     _GLIBCXX_USE_NOEXCEPT { }
00733 
00734       ~throw_allocator_random() _GLIBCXX_USE_NOEXCEPT { }
00735     };
00736 
00737 _GLIBCXX_END_NAMESPACE_VERSION
00738 } // namespace
00739 
00740 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00741 
00742 # include <bits/functional_hash.h>
00743 
00744 namespace std _GLIBCXX_VISIBILITY(default)
00745 {
00746   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
00747   template<>
00748     struct hash<__gnu_cxx::throw_value_limit>
00749     : public std::unary_function<__gnu_cxx::throw_value_limit, size_t>
00750     {
00751       size_t
00752       operator()(const __gnu_cxx::throw_value_limit& __val) const
00753       {
00754     std::hash<std::size_t> __h;
00755     size_t __result = __h(__val._M_i);
00756     return __result;
00757       }
00758     };
00759 
00760   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
00761   template<>
00762     struct hash<__gnu_cxx::throw_value_random>
00763     : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
00764     {
00765       size_t
00766       operator()(const __gnu_cxx::throw_value_random& __val) const
00767       {
00768     std::hash<std::size_t> __h;
00769     size_t __result = __h(__val._M_i);
00770     return __result;
00771       }
00772     };
00773 } // end namespace std
00774 #endif
00775 
00776 #endif