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

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