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

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