libstdc++-v3/include/ext/throw_allocator.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /** @file ext/throw_allocator.h
  37  *  This file is a GNU extension to the Standard C++ Library.
  38  *
  39  *  Contains two exception-generating types (throw_value, throw_allocator)
  40  *  intended to be used as value and allocator types while testing
  41  *  exception safety in templatized containers and algorithms. The
  42  *  allocator has additional log and debug features. The exception
  43  *  generated is of type forced_exception_error.
  44  */
  45
  46 #ifndef _THROW_ALLOCATOR_H
  47 #define _THROW_ALLOCATOR_H 1
  48
  49 #include <cmath>
  50 #include <ctime>
  51 #include <map>
  52 #include <string>
  53 #include <ostream>
  54 #include <stdexcept>
  55 #include <utility>
  56 #include <bits/functexcept.h>
  57 #include <bits/move.h>
  58 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  59 # include <functional>
  60 # include <random>
  61 #else
  62 # include <tr1/functional>
  63 # include <tr1/random>
  64 #endif
  65
  66 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  67
  68   /**
  69    *  @brief Thown by exception safety machinery.
  70    *  @ingroup exceptions
  71    */
  72   struct forced_error : public std::exception
  73   { };
  74
  75   // Substitute for forced_error object when -fno-exceptions.
  76   inline void
  77   __throw_forced_error()
  78   {
  79 #if __EXCEPTIONS
  80     throw forced_error();
  81 #else
  82     __builtin_abort();
  83 #endif
  84   }
  85
  86
  87   /**
  88    *  @brief Base class for checking address and label information
  89    *  about allocations. Create a std::map between the allocated
  90    *  address (void*) and a datum for annotations, which are a pair of
  91    *  numbers corresponding to label and allocated size.
  92    */
  93   struct annotate_base
  94   {
  95     annotate_base()
  96     {
  97       label();
  98       map();
  99     }
 100
 101     static void
 102     set_label(size_t l)
 103     { label() = l; }
 104
 105     static size_t
 106     get_label()
 107     { return label(); }
 108
 109     void
 110     insert(void* p, size_t size)
 111     {
 112       if (p == NULL)
 113         {
 114           std::string error("annotate_base::insert null insert!\n");
 115           log_to_string(error, make_entry(p, size));
 116           std::__throw_logic_error(error.c_str());
 117         }
 118
 119       const_iterator found = map().find(p);
 120       if (found != map().end())
 121         {
 122           std::string error("annotate_base::insert double insert!\n");
 123           log_to_string(error, make_entry(p, size));
 124           log_to_string(error, *found);
 125           std::__throw_logic_error(error.c_str());
 126         }
 127
 128       map().insert(make_entry(p, size));
 129     }
 130
 131     void
 132     erase(void* p, size_t size)
 133     {
 134       check_allocated(p, size);
 135       map().erase(p);
 136     }
 137
 138     // See if a particular address and allocation size has been saved.
 139     inline void
 140     check_allocated(void* p, size_t size)
 141     {
 142       const_iterator found = map().find(p);
 143       if (found == map().end())
 144         {
 145           std::string error("annotate_base::check_allocated by value "
 146                             "null erase!\n");
 147           log_to_string(error, make_entry(p, size));
 148           std::__throw_logic_error(error.c_str());
 149         }
 150
 151       if (found->second.second != size)
 152         {
 153           std::string error("annotate_base::check_allocated by value "
 154                             "wrong-size erase!\n");
 155           log_to_string(error, make_entry(p, size));
 156           log_to_string(error, *found);
 157           std::__throw_logic_error(error.c_str());
 158         }
 159     }
 160
 161     // See if a given label has been allocated.
 162     inline void
 163     check_allocated(size_t label)
 164     {
 165       const_iterator beg = map().begin();
 166       const_iterator end = map().end();
 167       std::string found;
 168       while (beg != end)
 169         {
 170           if (beg->second.first == label)
 171             log_to_string(found, *beg);
 172           ++beg;
 173         }
 174
 175       if (!found.empty())
 176         {
 177           std::string error("annotate_base::check_allocated by label\n");
 178           error += found;
 179           std::__throw_logic_error(error.c_str());
 180         }
 181     }
 182
 183   private:
 184     typedef std::pair<size_t, size_t>           data_type;
 185     typedef std::map<void*, data_type>          map_type;
 186     typedef map_type::value_type                entry_type;
 187     typedef map_type::const_iterator            const_iterator;
 188     typedef map_type::const_reference           const_reference;
 189
 190     friend std::ostream&
 191     operator<<(std::ostream&, const annotate_base&);
 192
 193     entry_type
 194     make_entry(void* p, size_t size)
 195     { return std::make_pair(p, data_type(get_label(), size)); }
 196
 197     void
 198     log_to_string(std::string& s, const_reference ref) const
 199     {
 200       char buf[40];
 201       const char tab('\t');
 202       s += "label: ";
 203       unsigned long l = static_cast<unsigned long>(ref.second.first);
 204       __builtin_sprintf(buf, "%lu", l);
 205       s += buf;
 206       s += tab;
 207       s += "size: ";
 208       l = static_cast<unsigned long>(ref.second.second);
 209       __builtin_sprintf(buf, "%lu", l);
 210       s += buf;
 211       s += tab;
 212       s += "address: ";
 213       __builtin_sprintf(buf, "%p", ref.first);
 214       s += buf;
 215       s += '\n';
 216     }
 217
 218     static size_t&
 219     label()
 220     {
 221       static size_t _S_label(std::numeric_limits<size_t>::max());
 222       return _S_label;
 223     }
 224
 225     static map_type&
 226     map()
 227     {
 228       static map_type _S_map;
 229       return _S_map;
 230     }
 231   };
 232
 233   inline std::ostream&
 234   operator<<(std::ostream& os, const annotate_base& __b)
 235   {
 236     std::string error;
 237     typedef annotate_base base_type;
 238     base_type::const_iterator beg = __b.map().begin();
 239     base_type::const_iterator end = __b.map().end();
 240     for (; beg != end; ++beg)
 241       __b.log_to_string(error, *beg);
 242     return os << error;
 243   }
 244
 245
 246   /**
 247    *  @brief Base struct for condition policy.
 248    *
 249    * Requires a public member function with the signature
 250    * void throw_conditionally()
 251    */
 252   struct condition_base
 253   {
 254     virtual ~condition_base() { };
 255   };
 256
 257
 258   /**
 259    *  @brief Base class for incremental control and throw.
 260    */
 261   struct limit_condition : public condition_base
 262   {
 263     // Scope-level adjustor objects: set limit for throw at the
 264     // beginning of a scope block, and restores to previous limit when
 265     // object is destroyed on exiting the block.
 266     struct adjustor_base
 267     {
 268     private:
 269       const size_t _M_orig;
 270
 271     public:
 272       adjustor_base() : _M_orig(limit()) { }
 273
 274       virtual
 275       ~adjustor_base() { set_limit(_M_orig); }
 276     };
 277
 278     /// Never enter the condition.
 279     struct never_adjustor : public adjustor_base
 280     {
 281       never_adjustor() { set_limit(std::numeric_limits<size_t>::max()); }
 282     };
 283
 284     /// Always enter the condition.
 285     struct always_adjustor : public adjustor_base
 286     {
 287       always_adjustor() { set_limit(count()); }
 288     };
 289
 290     /// Enter the nth condition.
 291     struct limit_adjustor : public adjustor_base
 292     {
 293       limit_adjustor(const size_t __l) { set_limit(__l); }
 294     };
 295
 296     // Increment _S_count every time called.
 297     // If _S_count matches the limit count, throw.
 298     static void
 299     throw_conditionally()
 300     {
 301       if (count() == limit())
 302         __throw_forced_error();
 303       ++count();
 304     }
 305
 306     static size_t&
 307     count()
 308     {
 309       static size_t _S_count(0);
 310       return _S_count;
 311     }
 312
 313     static size_t&
 314     limit()
 315     {
 316       static size_t _S_limit(std::numeric_limits<size_t>::max());
 317       return _S_limit;
 318     }
 319
 320     // Zero the throw counter, set limit to argument.
 321     static void
 322     set_limit(const size_t __l)
 323     {
 324       limit() = __l;
 325       count() = 0;
 326     }
 327   };
 328
 329
 330   /**
 331    *  @brief Base class for random probability control and throw.
 332    */
 333   struct random_condition : public condition_base
 334   {
 335     // Scope-level adjustor objects: set probability for throw at the
 336     // beginning of a scope block, and restores to previous
 337     // probability when object is destroyed on exiting the block.
 338     struct adjustor_base
 339     {
 340     private:
 341       const double _M_orig;
 342
 343     public:
 344       adjustor_base() : _M_orig(probability()) { }
 345
 346       virtual ~adjustor_base()
 347       { set_probability(_M_orig); }
 348     };
 349
 350     /// Group condition.
 351     struct group_adjustor : public adjustor_base
 352     {
 353       group_adjustor(size_t size)
 354       { set_probability(1 - std::pow(double(1 - probability()),
 355                                      double(0.5 / (size + 1))));
 356       }
 357     };
 358
 359     /// Never enter the condition.
 360     struct never_adjustor : public adjustor_base
 361     {
 362       never_adjustor() { set_probability(0); }
 363     };
 364
 365     /// Always enter the condition.
 366     struct always_adjustor : public adjustor_base
 367     {
 368       always_adjustor() { set_probability(1); }
 369     };
 370
 371     random_condition()
 372     {
 373       probability();
 374       engine();
 375     }
 376
 377     static void
 378     set_probability(double __p)
 379     { probability() = __p; }
 380
 381     static void
 382     throw_conditionally()
 383     {
 384       if (generate() < probability())
 385         __throw_forced_error();
 386     }
 387
 388     void
 389     seed(unsigned long __s)
 390     { engine().seed(__s); }
 391
 392   private:
 393 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 394     typedef std::uniform_real_distribution<double>      distribution_type;
 395     typedef std::mt19937                                engine_type;
 396 #else
 397     typedef std::tr1::uniform_real<double>              distribution_type;
 398     typedef std::tr1::mt19937                           engine_type;
 399 #endif
 400
 401     static double
 402     generate()
 403     {
 404 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 405       const distribution_type distribution(0, 1);
 406       static auto generator = std::bind(distribution, engine());
 407 #else
 408       // Use variate_generator to get normalized results.
 409       typedef std::tr1::variate_generator<engine_type, distribution_type> gen_t;
 410       distribution_type distribution(0, 1);
 411       static gen_t generator(engine(), distribution);
 412 #endif
 413
 414       double random = generator();
 415       if (random < distribution.min() || random > distribution.max())
 416         {
 417           std::string __s("random_condition::generate");
 418           __s += "\n";
 419           __s += "random number generated is: ";
 420           char buf[40];
 421           __builtin_sprintf(buf, "%f", random);
 422           __s += buf;
 423           std::__throw_out_of_range(__s.c_str());
 424         }
 425
 426       return random;
 427     }
 428
 429     static double&
 430     probability()
 431     {
 432       static double _S_p;
 433       return _S_p;
 434     }
 435
 436     static engine_type&
 437     engine()
 438     {
 439       static engine_type _S_e;
 440       return _S_e;
 441     }
 442   };
 443
 444
 445   /**
 446    *  @brief Class with exception generation control. Intended to be
 447    *  used as a value_type in templatized code.
 448    *
 449    *  Note: Destructor not allowed to throw.
 450    */
 451   template<typename _Cond>
 452     struct throw_value_base : public _Cond
 453     {
 454       typedef _Cond                             condition_type;
 455
 456       using condition_type::throw_conditionally;
 457
 458       std::size_t                               _M_i;
 459
 460 #ifndef _GLIBCXX_IS_AGGREGATE
 461       throw_value_base() : _M_i(0)
 462       { throw_conditionally(); }
 463
 464       throw_value_base(const throw_value_base& __v) : _M_i(__v._M_i)
 465       { throw_conditionally(); }
 466
 467       explicit throw_value_base(const std::size_t __i) : _M_i(__i)
 468       { throw_conditionally(); }
 469 #endif
 470
 471       throw_value_base&
 472       operator=(const throw_value_base& __v)
 473       {
 474         throw_conditionally();
 475         _M_i = __v._M_i;
 476         return *this;
 477       }
 478
 479       throw_value_base&
 480       operator++()
 481       {
 482         throw_conditionally();
 483         ++_M_i;
 484         return *this;
 485       }
 486     };
 487
 488   template<typename _Cond>
 489     inline void
 490     swap(throw_value_base<_Cond>& __a, throw_value_base<_Cond>& __b)
 491     {
 492       typedef throw_value_base<_Cond> throw_value;
 493       throw_value::throw_conditionally();
 494       throw_value orig(__a);
 495       __a = __b;
 496       __b = orig;
 497     }
 498
 499   // General instantiable types requirements.
 500   template<typename _Cond>
 501     inline bool
 502     operator==(const throw_value_base<_Cond>& __a,
 503                const throw_value_base<_Cond>& __b)
 504     {
 505       typedef throw_value_base<_Cond> throw_value;
 506       throw_value::throw_conditionally();
 507       bool __ret = __a._M_i == __b._M_i;
 508       return __ret;
 509     }
 510
 511   template<typename _Cond>
 512     inline bool
 513     operator<(const throw_value_base<_Cond>& __a,
 514               const throw_value_base<_Cond>& __b)
 515     {
 516       typedef throw_value_base<_Cond> throw_value;
 517       throw_value::throw_conditionally();
 518       bool __ret = __a._M_i < __b._M_i;
 519       return __ret;
 520     }
 521
 522   // Numeric algorithms instantiable types requirements.
 523   template<typename _Cond>
 524     inline throw_value_base<_Cond>
 525     operator+(const throw_value_base<_Cond>& __a,
 526               const throw_value_base<_Cond>& __b)
 527     {
 528       typedef throw_value_base<_Cond> throw_value;
 529       throw_value::throw_conditionally();
 530       throw_value __ret(__a._M_i + __b._M_i);
 531       return __ret;
 532     }
 533
 534   template<typename _Cond>
 535     inline throw_value_base<_Cond>
 536     operator-(const throw_value_base<_Cond>& __a,
 537               const throw_value_base<_Cond>& __b)
 538     {
 539       typedef throw_value_base<_Cond> throw_value;
 540       throw_value::throw_conditionally();
 541       throw_value __ret(__a._M_i - __b._M_i);
 542       return __ret;
 543     }
 544
 545   template<typename _Cond>
 546     inline throw_value_base<_Cond>
 547     operator*(const throw_value_base<_Cond>& __a,
 548               const throw_value_base<_Cond>& __b)
 549     {
 550       typedef throw_value_base<_Cond> throw_value;
 551       throw_value::throw_conditionally();
 552       throw_value __ret(__a._M_i * __b._M_i);
 553       return __ret;
 554     }
 555
 556
 557   /// Type throwing via limit condition.
 558   struct throw_value_limit : public throw_value_base<limit_condition>
 559   {
 560     typedef throw_value_base<limit_condition> base_type;
 561
 562 #ifndef _GLIBCXX_IS_AGGREGATE
 563     throw_value_limit() { }
 564
 565     throw_value_limit(const throw_value_limit& __other)
 566     : base_type(__other._M_i) { }
 567
 568     explicit throw_value_limit(const std::size_t __i) : base_type(__i) { }
 569 #endif
 570   };
 571
 572   /// Type throwing via random condition.
 573   struct throw_value_random : public throw_value_base<random_condition>
 574   {
 575     typedef throw_value_base<random_condition> base_type;
 576
 577 #ifndef _GLIBCXX_IS_AGGREGATE
 578     throw_value_random() { }
 579
 580     throw_value_random(const throw_value_random& __other)
 581     : base_type(__other._M_i) { }
 582
 583
 584     explicit throw_value_random(const std::size_t __i) : base_type(__i) { }
 585 #endif
 586   };
 587
 588
 589   /**
 590    *  @brief Allocator class with logging and exception generation control.
 591    * Intended to be used as an allocator_type in templatized code.
 592    *  @ingroup allocators
 593    *
 594    *  Note: Deallocate not allowed to throw.
 595    */
 596   template<typename _Tp, typename _Cond>
 597     class throw_allocator_base
 598     : public annotate_base, public _Cond
 599     {
 600     public:
 601       typedef size_t                            size_type;
 602       typedef ptrdiff_t                         difference_type;
 603       typedef _Tp                               value_type;
 604       typedef value_type*                       pointer;
 605       typedef const value_type*                 const_pointer;
 606       typedef value_type&                       reference;
 607       typedef const value_type&                 const_reference;
 608
 609     private:
 610       typedef _Cond                             condition_type;
 611
 612       std::allocator<value_type>                _M_allocator;
 613
 614       using condition_type::throw_conditionally;
 615
 616     public:
 617       size_type
 618       max_size() const throw()
 619       { return _M_allocator.max_size(); }
 620
 621       pointer
 622       allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
 623       {
 624         if (__n > this->max_size())
 625           std::__throw_bad_alloc();
 626
 627         throw_conditionally();
 628         pointer const a = _M_allocator.allocate(__n, hint);
 629         insert(a, sizeof(value_type) * __n);
 630         return a;
 631       }
 632
 633       void
 634       construct(pointer __p, const value_type& val)
 635       { return _M_allocator.construct(__p, val); }
 636
 637 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 638       template<typename... _Args>
 639         void
 640         construct(pointer __p, _Args&&... __args)
 641         { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
 642 #endif
 643
 644       void
 645       destroy(pointer __p)
 646       { _M_allocator.destroy(__p); }
 647
 648       void
 649       deallocate(pointer __p, size_type __n)
 650       {
 651         erase(__p, sizeof(value_type) * __n);
 652         _M_allocator.deallocate(__p, __n);
 653       }
 654
 655       void
 656       check_allocated(pointer __p, size_type __n)
 657       {
 658         size_type __t = sizeof(value_type) * __n;
 659         annotate_base::check_allocated(__p, __t);
 660       }
 661
 662       void
 663       check_allocated(size_type __n)
 664       { annotate_base::check_allocated(__n); }
 665   };
 666
 667   template<typename _Tp, typename _Cond>
 668     inline bool
 669     operator==(const throw_allocator_base<_Tp, _Cond>&,
 670                const throw_allocator_base<_Tp, _Cond>&)
 671     { return true; }
 672
 673   template<typename _Tp, typename _Cond>
 674     inline bool
 675     operator!=(const throw_allocator_base<_Tp, _Cond>&,
 676                const throw_allocator_base<_Tp, _Cond>&)
 677     { return false; }
 678
 679   /// Allocator throwing via limit condition.
 680   template<typename _Tp>
 681     struct throw_allocator_limit
 682     : public throw_allocator_base<_Tp, limit_condition>
 683     {
 684       template<typename _Tp1>
 685         struct rebind
 686         { typedef throw_allocator_limit<_Tp1> other; };
 687
 688       throw_allocator_limit() throw() { }
 689
 690       throw_allocator_limit(const throw_allocator_limit&) throw() { }
 691
 692       template<typename _Tp1>
 693         throw_allocator_limit(const throw_allocator_limit<_Tp1>&) throw() { }
 694
 695       ~throw_allocator_limit() throw() { }
 696     };
 697
 698   /// Allocator throwing via random condition.
 699   template<typename _Tp>
 700     struct throw_allocator_random
 701     : public throw_allocator_base<_Tp, random_condition>
 702     {
 703       template<typename _Tp1>
 704         struct rebind
 705         { typedef throw_allocator_random<_Tp1> other; };
 706
 707       throw_allocator_random() throw() { }
 708
 709       throw_allocator_random(const throw_allocator_random&) throw() { }
 710
 711       template<typename _Tp1>
 712         throw_allocator_random(const throw_allocator_random<_Tp1>&) throw() { }
 713
 714       ~throw_allocator_random() throw() { }
 715     };
 716
 717 _GLIBCXX_END_NAMESPACE
 718
 719 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 720
 721 # include <bits/functional_hash.h>
 722
 723 namespace std
 724 {
 725   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
 726   template<>
 727     struct hash<__gnu_cxx::throw_value_limit>
 728     : public std::unary_function<__gnu_cxx::throw_value_limit, size_t>
 729     {
 730       size_t
 731       operator()(__gnu_cxx::throw_value_limit __val) const
 732       {
 733         std::hash<std::size_t> h;
 734         size_t __result = h(__val._M_i);
 735         return __result;
 736       }
 737     };
 738
 739   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
 740   template<>
 741     struct hash<__gnu_cxx::throw_value_random>
 742     : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
 743     {
 744       size_t
 745       operator()(__gnu_cxx::throw_value_random __val) const
 746       {
 747         std::hash<std::size_t> h;
 748         size_t __result = h(__val._M_i);
 749         return __result;
 750       }
 751     };
 752 } // end namespace std
 753 #endif
 754
 755 #endif