OSDN Git Service

2011-05-28 Jonathan Wakely <jwakely.gcc@gmail.com>
[pf3gnuchains/gcc-fork.git] / 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 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 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 #ifdef __GXX_EXPERIMENTAL_CXX0X__
643       template<typename _Up, typename... _Args>
644         void
645         construct(_Up* __p, _Args&&... __args)
646         { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
647
648       template<typename _Up>
649         void 
650         destroy(_Up* __p)
651         { _M_allocator.destroy(__p); }
652 #else
653       void
654       construct(pointer __p, const value_type& val)
655       { return _M_allocator.construct(__p, val); }
656
657       void
658       destroy(pointer __p)
659       { _M_allocator.destroy(__p); }
660 #endif
661
662       void
663       deallocate(pointer __p, size_type __n)
664       {
665         erase(__p, sizeof(value_type) * __n);
666         _M_allocator.deallocate(__p, __n);
667       }
668
669       void
670       check_allocated(pointer __p, size_type __n)
671       {
672         size_type __t = sizeof(value_type) * __n;
673         annotate_base::check_allocated(__p, __t);
674       }
675
676       void
677       check_allocated(size_type __n)
678       { annotate_base::check_allocated(__n); }
679   };
680
681   template<typename _Tp, typename _Cond>
682     inline bool
683     operator==(const throw_allocator_base<_Tp, _Cond>&,
684                const throw_allocator_base<_Tp, _Cond>&)
685     { return true; }
686
687   template<typename _Tp, typename _Cond>
688     inline bool
689     operator!=(const throw_allocator_base<_Tp, _Cond>&,
690                const throw_allocator_base<_Tp, _Cond>&)
691     { return false; }
692
693   /// Allocator throwing via limit condition.
694   template<typename _Tp>
695     struct throw_allocator_limit
696     : public throw_allocator_base<_Tp, limit_condition>
697     {
698       template<typename _Tp1>
699         struct rebind
700         { typedef throw_allocator_limit<_Tp1> other; };
701
702       throw_allocator_limit() throw() { }
703
704       throw_allocator_limit(const throw_allocator_limit&) throw() { }
705
706       template<typename _Tp1>
707         throw_allocator_limit(const throw_allocator_limit<_Tp1>&) throw() { }
708
709       ~throw_allocator_limit() throw() { }
710     };
711
712   /// Allocator throwing via random condition.
713   template<typename _Tp>
714     struct throw_allocator_random
715     : public throw_allocator_base<_Tp, random_condition>
716     {
717       template<typename _Tp1>
718         struct rebind
719         { typedef throw_allocator_random<_Tp1> other; };
720
721       throw_allocator_random() throw() { }
722
723       throw_allocator_random(const throw_allocator_random&) throw() { }
724
725       template<typename _Tp1>
726         throw_allocator_random(const throw_allocator_random<_Tp1>&) throw() { }
727
728       ~throw_allocator_random() throw() { }
729     };
730
731 _GLIBCXX_END_NAMESPACE_VERSION
732 } // namespace
733
734 #ifdef __GXX_EXPERIMENTAL_CXX0X__
735
736 # include <bits/functional_hash.h>
737
738 namespace std _GLIBCXX_VISIBILITY(default)
739 {
740   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
741   template<>
742     struct hash<__gnu_cxx::throw_value_limit>
743     : public std::unary_function<__gnu_cxx::throw_value_limit, size_t>
744     {
745       size_t
746       operator()(const __gnu_cxx::throw_value_limit& __val) const
747       {
748         std::hash<std::size_t> __h;
749         size_t __result = __h(__val._M_i);
750         return __result;
751       }
752     };
753
754   /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
755   template<>
756     struct hash<__gnu_cxx::throw_value_random>
757     : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
758     {
759       size_t
760       operator()(const __gnu_cxx::throw_value_random& __val) const
761       {
762         std::hash<std::size_t> __h;
763         size_t __result = __h(__val._M_i);
764         return __result;
765       }
766     };
767 } // end namespace std
768 #endif
769
770 #endif