libstdc++
throw_allocator.h
Go to the documentation of this file.
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 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  */
97  {
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:
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  */
256  {
257  virtual ~condition_base() { };
258  };
259 
260 
261  /**
262  * @brief Base class for incremental control and throw.
263  */
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  {
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  */
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 
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 
475  operator=(const throw_value_base& __v)
476  {
477  throw_conditionally();
478  _M_i = __v._M_i;
479  return *this;
480  }
481 
483  operator++()
484  {
485  throw_conditionally();
486  ++_M_i;
487  return *this;
488  }
489  };
490 
491  template<typename _Cond>
492  inline void
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>
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 throw()
622  { return _M_allocator.max_size(); }
623 
624  pointer
625  address(reference __x) const { return std::__addressof(__x); }
626 
627  const_pointer
628  address(const_reference __x) const { return std::__addressof(__x); }
629 
630  pointer
631  allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
632  {
633  if (__n > this->max_size())
634  std::__throw_bad_alloc();
635 
636  throw_conditionally();
637  pointer const a = _M_allocator.allocate(__n, hint);
638  insert(a, sizeof(value_type) * __n);
639  return a;
640  }
641 
642  void
643  construct(pointer __p, const value_type& val)
644  { return _M_allocator.construct(__p, val); }
645 
646 #ifdef __GXX_EXPERIMENTAL_CXX0X__
647  template<typename... _Args>
648  void
649  construct(pointer __p, _Args&&... __args)
650  { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
651 #endif
652 
653  void
654  destroy(pointer __p)
655  { _M_allocator.destroy(__p); }
656 
657  void
658  deallocate(pointer __p, size_type __n)
659  {
660  erase(__p, sizeof(value_type) * __n);
661  _M_allocator.deallocate(__p, __n);
662  }
663 
664  void
665  check_allocated(pointer __p, size_type __n)
666  {
667  size_type __t = sizeof(value_type) * __n;
668  annotate_base::check_allocated(__p, __t);
669  }
670 
671  void
672  check_allocated(size_type __n)
673  { annotate_base::check_allocated(__n); }
674  };
675 
676  template<typename _Tp, typename _Cond>
677  inline bool
678  operator==(const throw_allocator_base<_Tp, _Cond>&,
680  { return true; }
681 
682  template<typename _Tp, typename _Cond>
683  inline bool
684  operator!=(const throw_allocator_base<_Tp, _Cond>&,
685  const throw_allocator_base<_Tp, _Cond>&)
686  { return false; }
687 
688  /// Allocator throwing via limit condition.
689  template<typename _Tp>
691  : public throw_allocator_base<_Tp, limit_condition>
692  {
693  template<typename _Tp1>
694  struct rebind
695  { typedef throw_allocator_limit<_Tp1> other; };
696 
697  throw_allocator_limit() throw() { }
698 
699  throw_allocator_limit(const throw_allocator_limit&) throw() { }
700 
701  template<typename _Tp1>
703 
704  ~throw_allocator_limit() throw() { }
705  };
706 
707  /// Allocator throwing via random condition.
708  template<typename _Tp>
710  : public throw_allocator_base<_Tp, random_condition>
711  {
712  template<typename _Tp1>
713  struct rebind
714  { typedef throw_allocator_random<_Tp1> other; };
715 
716  throw_allocator_random() throw() { }
717 
719 
720  template<typename _Tp1>
722 
723  ~throw_allocator_random() throw() { }
724  };
725 
726 _GLIBCXX_END_NAMESPACE_VERSION
727 } // namespace
728 
729 #ifdef __GXX_EXPERIMENTAL_CXX0X__
730 
731 # include <bits/functional_hash.h>
732 
733 namespace std _GLIBCXX_VISIBILITY(default)
734 {
735  /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
736  template<>
737  struct hash<__gnu_cxx::throw_value_limit>
738  : public std::unary_function<__gnu_cxx::throw_value_limit, size_t>
739  {
740  size_t
741  operator()(const __gnu_cxx::throw_value_limit& __val) const
742  {
744  size_t __result = __h(__val._M_i);
745  return __result;
746  }
747  };
748 
749  /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
750  template<>
751  struct hash<__gnu_cxx::throw_value_random>
752  : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
753  {
754  size_t
755  operator()(const __gnu_cxx::throw_value_random& __val) const
756  {
758  size_t __result = __h(__val._M_i);
759  return __result;
760  }
761  };
762 } // end namespace std
763 #endif
764 
765 #endif
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:87
_Bind_helper< _Functor, _ArgTypes...>::type bind(_Functor &&__f, _ArgTypes &&...__args)
Function template for std::bind.
Definition: functional:1444
Controlling output.This is the base class for all output streams. It provides text formatting of all ...
Definition: iosfwd:88
Base class for checking address and label information about allocations. Create a std::map between th...
Base class for random probability control and throw.
Class with exception generation control. Intended to be used as a value_type in templatized code...
mersenne_twister_engine< uint_fast32_t, 32, 624, 397, 31, 0x9908b0dfUL, 11, 0xffffffffUL, 7, 0x9d2c5680UL, 15, 0xefc60000UL, 18, 1812433253UL > mt19937
Definition: random.h:1471
reference_wrapper< _Tp > ref(_Tp &__t)
Denotes a reference should be taken to a variable.
Definition: functional:470
complex< _Tp > pow(const complex< _Tp > &, const _Tp &)
Return x to the y'th power.
Definition: complex:986
Uniform continuous distribution for random numbers.
Definition: random.h:1782
Primary class template hash.
Definition: system_error:112
iterator end()
Definition: stl_map.h:327
Allocator throwing via random condition.
pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:262
constexpr size_t size() const
Returns the total number of bits.
Definition: bitset:1275
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:517
Type throwing via random condition.
iterator find(const key_type &__x)
Tries to locate an element in a map.
Definition: stl_map.h:741
Base struct for condition policy.
constexpr const _Tp * end(initializer_list< _Tp > __ils)
Return an iterator pointing to one past the last element of the initilizer_list.
iterator erase(const_iterator __position)
Erases an element from a map.
Definition: stl_map.h:613
Allocator throwing via limit condition.
Thown by exception safety machinery.
Base class for all library exceptions.
Definition: exception:61
iterator begin()
Definition: stl_map.h:309
Properties of fundamental types.
Definition: limits:304
Type throwing via limit condition.
const _CharT * c_str() const
Return const pointer to null-terminated contents.
bool empty() const
Definition: basic_string.h:803
Base class for incremental control and throw.
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_map.h:88
Allocator class with logging and exception generation control. Intended to be used as an allocator_ty...