OSDN Git Service

2007-06-01 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / throw_allocator.h
1 // -*- C++ -*-
2
3 // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
9 // version.
10
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 // General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING.  If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
20
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction.  Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License.  This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
29 // Public License.
30
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
40 // warranty.
41
42 /** @file ext/vstring.h
43  *  This file is a GNU extension to the Standard C++ Library.
44  *
45  *  Contains an exception-throwing allocator, useful for testing
46  *  exception safety. In addition, allocation addresses are stored and
47  *  sanity checked.
48  */
49
50 /**
51  * @file throw_allocator.h 
52  */
53
54 #ifndef _THROW_ALLOCATOR_H
55 #define _THROW_ALLOCATOR_H 1
56
57 #include <cmath>
58 #include <ctime>
59 #include <map>
60 #include <set>
61 #include <string>
62 #include <ostream>
63 #include <stdexcept>
64 #include <utility>
65 #include <tr1/random>
66
67 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
68
69   class twister_rand_gen
70   {
71   public:
72     twister_rand_gen(unsigned int seed = 
73                      static_cast<unsigned int>(std::time(0)));
74     
75     void
76     init(unsigned int);
77     
78     double
79     get_prob();
80     
81   private:
82     std::tr1::mt19937 _M_generator;
83   };
84
85
86   struct forced_exception_error : public std::exception
87   { };
88
89   class throw_allocator_base
90   {
91   public:
92     void
93     init(unsigned long seed);
94
95     static void
96     set_throw_prob(double throw_prob);
97
98     static double
99     get_throw_prob();
100
101     static void
102     set_label(size_t l);
103
104     static bool
105     empty();
106
107     struct group_throw_prob_adjustor
108     {
109       group_throw_prob_adjustor(size_t size) 
110       : _M_throw_prob_orig(_S_throw_prob)
111       {
112         _S_throw_prob =
113           1 - std::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
114       }
115
116       ~group_throw_prob_adjustor()
117       { _S_throw_prob = _M_throw_prob_orig; }
118
119     private:
120       const double _M_throw_prob_orig;
121     };
122
123     struct zero_throw_prob_adjustor
124     {
125       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
126       { _S_throw_prob = 0; }
127
128       ~zero_throw_prob_adjustor()
129       { _S_throw_prob = _M_throw_prob_orig; }
130
131     private:
132       const double _M_throw_prob_orig;
133     };
134
135   protected:
136     static void
137     insert(void*, size_t);
138
139     static void
140     erase(void*, size_t);
141
142     static void
143     throw_conditionally();
144
145     // See if a particular address and size has been allocated by this
146     // allocator.
147     static void
148     check_allocated(void*, size_t);
149
150     // See if a given label has been allocated by this allocator.
151     static void
152     check_allocated(size_t);
153
154   private:
155     typedef std::pair<size_t, size_t>           alloc_data_type;
156     typedef std::map<void*, alloc_data_type>    map_type;
157     typedef map_type::value_type                entry_type;
158     typedef map_type::const_iterator            const_iterator;
159     typedef map_type::const_reference           const_reference;
160
161     friend std::ostream& 
162     operator<<(std::ostream&, const throw_allocator_base&);
163
164     static entry_type
165     make_entry(void*, size_t);
166
167     static void
168     print_to_string(std::string&);
169
170     static void
171     print_to_string(std::string&, const_reference);
172
173     static twister_rand_gen     _S_g;
174     static map_type             _S_map;
175     static double               _S_throw_prob;
176     static size_t               _S_label;
177   };
178
179
180   template<typename T>
181     class throw_allocator : public throw_allocator_base
182     {
183     public:
184       typedef size_t                            size_type;
185       typedef ptrdiff_t                         difference_type;
186       typedef T                                 value_type;
187       typedef value_type*                       pointer;
188       typedef const value_type*                 const_pointer;
189       typedef value_type&                       reference;
190       typedef const value_type&                 const_reference;
191
192
193       template<typename U>
194       struct rebind
195       {
196         typedef throw_allocator<U> other;
197       };
198
199       throw_allocator() throw() { }
200
201       throw_allocator(const throw_allocator&) throw() { }
202
203       template<typename U>
204       throw_allocator(const throw_allocator<U>&) throw() { }
205
206       ~throw_allocator() throw() { }
207
208       size_type
209       max_size() const throw()
210       { return std::allocator<value_type>().max_size(); }
211
212       pointer
213       allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
214       {
215         if (__builtin_expect(__n > this->max_size(), false))
216           std::__throw_bad_alloc();
217
218         throw_conditionally();
219         value_type* const a = std::allocator<value_type>().allocate(__n, hint);
220         insert(a, sizeof(value_type) * __n);
221         return a;
222       }
223
224       void
225       construct(pointer __p, const T& val)
226       { return std::allocator<value_type>().construct(__p, val); }
227
228       void
229       destroy(pointer __p)
230       { std::allocator<value_type>().destroy(__p); }
231
232       void
233       deallocate(pointer __p, size_type __n)
234       {
235         erase(__p, sizeof(value_type) * __n);
236         std::allocator<value_type>().deallocate(__p, __n);
237       }
238
239       void
240       check_allocated(pointer __p, size_type __n)
241       { throw_allocator_base::check_allocated(__p, sizeof(value_type) * __n); }
242
243       void
244       check_allocated(size_type label)
245       { throw_allocator_base::check_allocated(label); }
246     };
247
248   template<typename T>
249     inline bool
250     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
251     { return true; }
252
253   template<typename T>
254     inline bool
255     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
256     { return false; }
257
258   std::ostream& 
259   operator<<(std::ostream& os, const throw_allocator_base& alloc)
260   {
261     std::string error;
262     throw_allocator_base::print_to_string(error);
263     os << error;
264     return os;
265   }
266
267   // XXX Should be in .cc.
268   twister_rand_gen::
269   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
270
271   void
272   twister_rand_gen::
273   init(unsigned int seed)
274   { _M_generator.seed(seed); }
275
276   double
277   twister_rand_gen::
278   get_prob()
279   {
280     const double eng_min = _M_generator.min();
281     const double eng_range =
282       static_cast<const double>(_M_generator.max() - eng_min);
283
284     const double eng_res =
285       static_cast<const double>(_M_generator() - eng_min);
286
287     const double ret = eng_res / eng_range;
288     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
289     return ret;
290   }
291
292   twister_rand_gen throw_allocator_base::_S_g;
293
294   throw_allocator_base::map_type
295   throw_allocator_base::_S_map;
296
297   double throw_allocator_base::_S_throw_prob;
298
299   size_t throw_allocator_base::_S_label = 0;
300
301   throw_allocator_base::entry_type
302   throw_allocator_base::make_entry(void* p, size_t size)
303   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
304
305   void
306   throw_allocator_base::init(unsigned long seed)
307   { _S_g.init(seed); }
308
309   void
310   throw_allocator_base::set_throw_prob(double throw_prob)
311   { _S_throw_prob = throw_prob; }
312
313   double
314   throw_allocator_base::get_throw_prob()
315   { return _S_throw_prob; }
316
317   void
318   throw_allocator_base::set_label(size_t l)
319   { _S_label = l; }
320
321   void
322   throw_allocator_base::insert(void* p, size_t size)
323   {
324     const_iterator found_it = _S_map.find(p);
325     if (found_it != _S_map.end())
326       {
327         std::string error("throw_allocator_base::insert");
328         error += "double insert!";
329         error += '\n';
330         print_to_string(error, make_entry(p, size));
331         print_to_string(error, *found_it);
332         throw std::logic_error(error);
333       }
334     _S_map.insert(make_entry(p, size));
335   }
336
337   bool
338   throw_allocator_base::empty()
339   { return _S_map.empty(); }
340
341   void
342   throw_allocator_base::erase(void* p, size_t size)
343   {
344     check_allocated(p, size);
345     _S_map.erase(p);
346   }
347
348   void
349   throw_allocator_base::check_allocated(void* p, size_t size)
350   {
351     const_iterator found_it = _S_map.find(p);
352     if (found_it == _S_map.end())
353       {
354         std::string error("throw_allocator_base::check_allocated by value ");
355         error += "null erase!";
356         error += '\n';
357         print_to_string(error, make_entry(p, size));
358         throw std::logic_error(error);
359       }
360
361     if (found_it->second.second != size)
362       {
363         std::string error("throw_allocator_base::check_allocated by value ");
364         error += "wrong-size erase!";
365         error += '\n';
366         print_to_string(error, make_entry(p, size));
367         print_to_string(error, *found_it);
368         throw std::logic_error(error);
369       }
370   }
371
372   void
373   throw_allocator_base::check_allocated(size_t label)
374   {
375     std::string found;
376     const_iterator it = _S_map.begin();
377     while (it != _S_map.end())
378       {
379         if (it->second.first == label)
380           print_to_string(found, *it);
381         ++it;
382       }
383
384     if (!found.empty())
385       {
386         std::string error("throw_allocator_base::check_allocated by label ");
387         error += '\n';
388         error += found;
389         throw std::logic_error(error);
390       } 
391   }
392
393   void
394   throw_allocator_base::throw_conditionally()
395   {
396     if (_S_g.get_prob() < _S_throw_prob)
397       throw forced_exception_error();
398   }
399
400   void
401   throw_allocator_base::print_to_string(std::string& s)
402   {
403     const_iterator begin = throw_allocator_base::_S_map.begin();
404     const_iterator end = throw_allocator_base::_S_map.end();
405     for (; begin != end; ++begin)
406       print_to_string(s, *begin);
407   }
408
409   void
410   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
411   {
412     char buf[40];
413     const char tab('\t');
414     s += "address: ";
415     sprintf(buf, "%p", ref.first);
416     s += buf;
417     s += tab;
418     s += "label: ";
419     sprintf(buf, "%u", ref.second.first);
420     s += buf;
421     s += tab;
422     s += "size: ";
423     sprintf(buf, "%u", ref.second.second);
424     s += buf;
425     s += '\n';
426   }
427
428 _GLIBCXX_END_NAMESPACE
429
430 #endif