xref: /openbsd-src/gnu/gcc/libstdc++-v3/include/ext/throw_allocator.h (revision 12bb21d578ad369b898c185f93f157593a02e306)
1404b540aSrobert // -*- C++ -*-
2404b540aSrobert 
3404b540aSrobert // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
4404b540aSrobert //
5404b540aSrobert // This file is part of the GNU ISO C++ Library.  This library is free
6404b540aSrobert // software; you can redistribute it and/or modify it under the terms
7404b540aSrobert // of the GNU General Public License as published by the Free Software
8404b540aSrobert // Foundation; either version 2, or (at your option) any later
9404b540aSrobert // version.
10404b540aSrobert 
11404b540aSrobert // This library is distributed in the hope that it will be useful, but
12404b540aSrobert // WITHOUT ANY WARRANTY; without even the implied warranty of
13404b540aSrobert // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14404b540aSrobert // General Public License for more details.
15404b540aSrobert 
16404b540aSrobert // You should have received a copy of the GNU General Public License
17404b540aSrobert // along with this library; see the file COPYING.  If not, write to
18404b540aSrobert // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19404b540aSrobert // MA 02111-1307, USA.
20404b540aSrobert 
21404b540aSrobert // As a special exception, you may use this file as part of a free
22404b540aSrobert // software library without restriction.  Specifically, if other files
23404b540aSrobert // instantiate templates or use macros or inline functions from this
24404b540aSrobert // file, or you compile this file and link it with other files to
25404b540aSrobert // produce an executable, this file does not by itself cause the
26404b540aSrobert // resulting executable to be covered by the GNU General Public
27404b540aSrobert // License.  This exception does not however invalidate any other
28404b540aSrobert // reasons why the executable file might be covered by the GNU General
29404b540aSrobert // Public License.
30404b540aSrobert 
31404b540aSrobert // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32404b540aSrobert 
33404b540aSrobert // Permission to use, copy, modify, sell, and distribute this software
34404b540aSrobert // is hereby granted without fee, provided that the above copyright
35404b540aSrobert // notice appears in all copies, and that both that copyright notice
36404b540aSrobert // and this permission notice appear in supporting documentation. None
37404b540aSrobert // of the above authors, nor IBM Haifa Research Laboratories, make any
38404b540aSrobert // representation about the suitability of this software for any
39404b540aSrobert // purpose. It is provided "as is" without express or implied
40404b540aSrobert // warranty.
41404b540aSrobert 
42404b540aSrobert /** @file ext/vstring.h
43404b540aSrobert  *  This file is a GNU extension to the Standard C++ Library.
44404b540aSrobert  *
45404b540aSrobert  *  Contains an exception-throwing allocator, useful for testing
46404b540aSrobert  *  exception safety. In addition, allocation addresses are stored and
47404b540aSrobert  *  sanity checked.
48404b540aSrobert  */
49404b540aSrobert 
50404b540aSrobert /**
51404b540aSrobert  * @file throw_allocator.h
52404b540aSrobert  */
53404b540aSrobert 
54404b540aSrobert #ifndef _THROW_ALLOCATOR_H
55404b540aSrobert #define _THROW_ALLOCATOR_H 1
56404b540aSrobert 
57404b540aSrobert #include <cmath>
58404b540aSrobert #include <map>
59404b540aSrobert #include <set>
60404b540aSrobert #include <string>
61404b540aSrobert #include <ostream>
62404b540aSrobert #include <stdexcept>
63404b540aSrobert #include <utility>
64404b540aSrobert #include <tr1/random>
65404b540aSrobert #include <bits/functexcept.h>
66404b540aSrobert 
_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)67404b540aSrobert _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
68404b540aSrobert 
69404b540aSrobert   class twister_rand_gen
70404b540aSrobert   {
71404b540aSrobert   public:
72404b540aSrobert     twister_rand_gen(unsigned int seed =
73404b540aSrobert 		     static_cast<unsigned int>(std::time(0)));
74404b540aSrobert 
75404b540aSrobert     void
76404b540aSrobert     init(unsigned int);
77404b540aSrobert 
78404b540aSrobert     double
79404b540aSrobert     get_prob();
80404b540aSrobert 
81404b540aSrobert   private:
82404b540aSrobert     std::tr1::mt19937 _M_generator;
83404b540aSrobert   };
84404b540aSrobert 
85404b540aSrobert   struct forced_exception_error : public std::exception
86404b540aSrobert   { };
87404b540aSrobert 
88404b540aSrobert   // Substitute for concurrence_error object in the case of -fno-exceptions.
89404b540aSrobert   inline void
__throw_forced_exception_error()90404b540aSrobert   __throw_forced_exception_error()
91404b540aSrobert   {
92404b540aSrobert #if __EXCEPTIONS
93404b540aSrobert     throw forced_exception_error();
94404b540aSrobert #else
95404b540aSrobert     __builtin_abort();
96404b540aSrobert #endif
97404b540aSrobert   }
98404b540aSrobert 
99404b540aSrobert   class throw_allocator_base
100404b540aSrobert   {
101404b540aSrobert   public:
102404b540aSrobert     void
103404b540aSrobert     init(unsigned long seed);
104404b540aSrobert 
105404b540aSrobert     static void
106404b540aSrobert     set_throw_prob(double throw_prob);
107404b540aSrobert 
108404b540aSrobert     static double
109404b540aSrobert     get_throw_prob();
110404b540aSrobert 
111404b540aSrobert     static void
112404b540aSrobert     set_label(size_t l);
113404b540aSrobert 
114404b540aSrobert     static bool
115404b540aSrobert     empty();
116404b540aSrobert 
117404b540aSrobert     struct group_throw_prob_adjustor
118404b540aSrobert     {
group_throw_prob_adjustorgroup_throw_prob_adjustor119404b540aSrobert       group_throw_prob_adjustor(size_t size)
120404b540aSrobert       : _M_throw_prob_orig(_S_throw_prob)
121404b540aSrobert       {
122404b540aSrobert 	_S_throw_prob =
123404b540aSrobert 	  1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
124404b540aSrobert       }
125404b540aSrobert 
~group_throw_prob_adjustorgroup_throw_prob_adjustor126404b540aSrobert       ~group_throw_prob_adjustor()
127404b540aSrobert       { _S_throw_prob = _M_throw_prob_orig; }
128404b540aSrobert 
129404b540aSrobert     private:
130404b540aSrobert       const double _M_throw_prob_orig;
131404b540aSrobert     };
132404b540aSrobert 
133404b540aSrobert     struct zero_throw_prob_adjustor
134404b540aSrobert     {
zero_throw_prob_adjustorzero_throw_prob_adjustor135404b540aSrobert       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
136404b540aSrobert       { _S_throw_prob = 0; }
137404b540aSrobert 
~zero_throw_prob_adjustorzero_throw_prob_adjustor138404b540aSrobert       ~zero_throw_prob_adjustor()
139404b540aSrobert       { _S_throw_prob = _M_throw_prob_orig; }
140404b540aSrobert 
141404b540aSrobert     private:
142404b540aSrobert       const double _M_throw_prob_orig;
143404b540aSrobert     };
144404b540aSrobert 
145404b540aSrobert   protected:
146404b540aSrobert     static void
147404b540aSrobert     insert(void*, size_t);
148404b540aSrobert 
149404b540aSrobert     static void
150404b540aSrobert     erase(void*, size_t);
151404b540aSrobert 
152404b540aSrobert     static void
153404b540aSrobert     throw_conditionally();
154404b540aSrobert 
155404b540aSrobert     // See if a particular address and size has been allocated by this
156404b540aSrobert     // allocator.
157404b540aSrobert     static void
158404b540aSrobert     check_allocated(void*, size_t);
159404b540aSrobert 
160404b540aSrobert     // See if a given label has been allocated by this allocator.
161404b540aSrobert     static void
162404b540aSrobert     check_allocated(size_t);
163404b540aSrobert 
164404b540aSrobert   private:
165404b540aSrobert     typedef std::pair<size_t, size_t> 		alloc_data_type;
166404b540aSrobert     typedef std::map<void*, alloc_data_type> 	map_type;
167404b540aSrobert     typedef map_type::value_type 		entry_type;
168404b540aSrobert     typedef map_type::const_iterator 		const_iterator;
169404b540aSrobert     typedef map_type::const_reference 		const_reference;
170404b540aSrobert 
171404b540aSrobert     friend std::ostream&
172404b540aSrobert     operator<<(std::ostream&, const throw_allocator_base&);
173404b540aSrobert 
174404b540aSrobert     static entry_type
175404b540aSrobert     make_entry(void*, size_t);
176404b540aSrobert 
177404b540aSrobert     static void
178404b540aSrobert     print_to_string(std::string&);
179404b540aSrobert 
180404b540aSrobert     static void
181404b540aSrobert     print_to_string(std::string&, const_reference);
182404b540aSrobert 
183404b540aSrobert     static twister_rand_gen 	_S_g;
184404b540aSrobert     static map_type 		_S_map;
185404b540aSrobert     static double 		_S_throw_prob;
186404b540aSrobert     static size_t 		_S_label;
187404b540aSrobert   };
188404b540aSrobert 
189404b540aSrobert 
190404b540aSrobert   template<typename T>
191404b540aSrobert     class throw_allocator : public throw_allocator_base
192404b540aSrobert     {
193404b540aSrobert     public:
194404b540aSrobert       typedef size_t 				size_type;
195404b540aSrobert       typedef ptrdiff_t 			difference_type;
196404b540aSrobert       typedef T 				value_type;
197404b540aSrobert       typedef value_type* 			pointer;
198404b540aSrobert       typedef const value_type* 		const_pointer;
199404b540aSrobert       typedef value_type& 			reference;
200404b540aSrobert       typedef const value_type& 		const_reference;
201404b540aSrobert 
202404b540aSrobert 
203404b540aSrobert       template<typename U>
204404b540aSrobert       struct rebind
205404b540aSrobert       {
206404b540aSrobert         typedef throw_allocator<U> other;
207404b540aSrobert       };
208404b540aSrobert 
throw()209404b540aSrobert       throw_allocator() throw() { }
210404b540aSrobert 
throw()211404b540aSrobert       throw_allocator(const throw_allocator&) throw() { }
212404b540aSrobert 
213404b540aSrobert       template<typename U>
throw_allocator(const throw_allocator<U> &)214404b540aSrobert       throw_allocator(const throw_allocator<U>&) throw() { }
215404b540aSrobert 
throw()216404b540aSrobert       ~throw_allocator() throw() { }
217404b540aSrobert 
218404b540aSrobert       size_type
max_size()219404b540aSrobert       max_size() const throw()
220404b540aSrobert       { return std::allocator<value_type>().max_size(); }
221404b540aSrobert 
222404b540aSrobert       pointer
223404b540aSrobert       allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
224404b540aSrobert       {
225404b540aSrobert 	throw_conditionally();
226404b540aSrobert 	value_type* const a = std::allocator<value_type>().allocate(num, hint);
227404b540aSrobert 	insert(a, sizeof(value_type) * num);
228404b540aSrobert 	return a;
229404b540aSrobert       }
230404b540aSrobert 
231404b540aSrobert       void
construct(pointer p,const T & val)232404b540aSrobert       construct(pointer p, const T& val)
233404b540aSrobert       { return std::allocator<value_type>().construct(p, val); }
234404b540aSrobert 
235404b540aSrobert       void
destroy(pointer p)236404b540aSrobert       destroy(pointer p)
237404b540aSrobert       { std::allocator<value_type>().destroy(p); }
238404b540aSrobert 
239404b540aSrobert       void
deallocate(pointer p,size_type num)240404b540aSrobert       deallocate(pointer p, size_type num)
241404b540aSrobert       {
242404b540aSrobert 	erase(p, sizeof(value_type) * num);
243404b540aSrobert 	std::allocator<value_type>().deallocate(p, num);
244404b540aSrobert       }
245404b540aSrobert 
246404b540aSrobert       void
check_allocated(pointer p,size_type num)247404b540aSrobert       check_allocated(pointer p, size_type num)
248404b540aSrobert       { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
249404b540aSrobert 
250404b540aSrobert       void
check_allocated(size_type label)251404b540aSrobert       check_allocated(size_type label)
252404b540aSrobert       { throw_allocator_base::check_allocated(label); }
253404b540aSrobert     };
254404b540aSrobert 
255404b540aSrobert   template<typename T>
256404b540aSrobert     inline bool
257404b540aSrobert     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
258404b540aSrobert     { return true; }
259404b540aSrobert 
260404b540aSrobert   template<typename T>
261404b540aSrobert     inline bool
262404b540aSrobert     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
263404b540aSrobert     { return false; }
264404b540aSrobert 
265404b540aSrobert   std::ostream&
266404b540aSrobert   operator<<(std::ostream& os, const throw_allocator_base& alloc)
267404b540aSrobert   {
268404b540aSrobert     std::string error;
269404b540aSrobert     throw_allocator_base::print_to_string(error);
270404b540aSrobert     os << error;
271404b540aSrobert     return os;
272404b540aSrobert   }
273404b540aSrobert 
274404b540aSrobert   // XXX Should be in .cc.
275404b540aSrobert   twister_rand_gen::
twister_rand_gen(unsigned int seed)276404b540aSrobert   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
277404b540aSrobert 
278404b540aSrobert   void
279404b540aSrobert   twister_rand_gen::
init(unsigned int seed)280404b540aSrobert   init(unsigned int seed)
281404b540aSrobert   { _M_generator.seed(seed); }
282404b540aSrobert 
283404b540aSrobert   double
284404b540aSrobert   twister_rand_gen::
get_prob()285404b540aSrobert   get_prob()
286404b540aSrobert   {
287404b540aSrobert     const double eng_min = _M_generator.min();
288404b540aSrobert     const double eng_range =
289404b540aSrobert       static_cast<const double>(_M_generator.max() - eng_min);
290404b540aSrobert 
291404b540aSrobert     const double eng_res =
292404b540aSrobert       static_cast<const double>(_M_generator() - eng_min);
293404b540aSrobert 
294404b540aSrobert     const double ret = eng_res / eng_range;
295404b540aSrobert     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
296404b540aSrobert     return ret;
297404b540aSrobert   }
298404b540aSrobert 
299404b540aSrobert   twister_rand_gen throw_allocator_base::_S_g;
300404b540aSrobert 
301404b540aSrobert   throw_allocator_base::map_type
302404b540aSrobert   throw_allocator_base::_S_map;
303404b540aSrobert 
304404b540aSrobert   double throw_allocator_base::_S_throw_prob;
305404b540aSrobert 
306404b540aSrobert   size_t throw_allocator_base::_S_label = 0;
307404b540aSrobert 
308404b540aSrobert   throw_allocator_base::entry_type
make_entry(void * p,size_t size)309404b540aSrobert   throw_allocator_base::make_entry(void* p, size_t size)
310404b540aSrobert   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
311404b540aSrobert 
312404b540aSrobert   void
init(unsigned long seed)313404b540aSrobert   throw_allocator_base::init(unsigned long seed)
314404b540aSrobert   { _S_g.init(seed); }
315404b540aSrobert 
316404b540aSrobert   void
set_throw_prob(double throw_prob)317404b540aSrobert   throw_allocator_base::set_throw_prob(double throw_prob)
318404b540aSrobert   { _S_throw_prob = throw_prob; }
319404b540aSrobert 
320404b540aSrobert   double
get_throw_prob()321404b540aSrobert   throw_allocator_base::get_throw_prob()
322404b540aSrobert   { return _S_throw_prob; }
323404b540aSrobert 
324404b540aSrobert   void
set_label(size_t l)325404b540aSrobert   throw_allocator_base::set_label(size_t l)
326404b540aSrobert   { _S_label = l; }
327404b540aSrobert 
328404b540aSrobert   void
insert(void * p,size_t size)329404b540aSrobert   throw_allocator_base::insert(void* p, size_t size)
330404b540aSrobert   {
331404b540aSrobert     const_iterator found_it = _S_map.find(p);
332404b540aSrobert     if (found_it != _S_map.end())
333404b540aSrobert       {
334404b540aSrobert 	std::string error("throw_allocator_base::insert");
335404b540aSrobert 	error += "double insert!";
336404b540aSrobert 	error += '\n';
337404b540aSrobert 	print_to_string(error, make_entry(p, size));
338404b540aSrobert 	print_to_string(error, *found_it);
339404b540aSrobert 	std::__throw_logic_error(error.c_str());
340404b540aSrobert       }
341404b540aSrobert     _S_map.insert(make_entry(p, size));
342404b540aSrobert   }
343404b540aSrobert 
344404b540aSrobert   bool
empty()345404b540aSrobert   throw_allocator_base::empty()
346404b540aSrobert   { return _S_map.empty(); }
347404b540aSrobert 
348404b540aSrobert   void
erase(void * p,size_t size)349404b540aSrobert   throw_allocator_base::erase(void* p, size_t size)
350404b540aSrobert   {
351404b540aSrobert     check_allocated(p, size);
352404b540aSrobert     _S_map.erase(p);
353404b540aSrobert   }
354404b540aSrobert 
355404b540aSrobert   void
check_allocated(void * p,size_t size)356404b540aSrobert   throw_allocator_base::check_allocated(void* p, size_t size)
357404b540aSrobert   {
358404b540aSrobert     const_iterator found_it = _S_map.find(p);
359404b540aSrobert     if (found_it == _S_map.end())
360404b540aSrobert       {
361404b540aSrobert 	std::string error("throw_allocator_base::check_allocated by value ");
362404b540aSrobert 	error += "null erase!";
363404b540aSrobert 	error += '\n';
364404b540aSrobert 	print_to_string(error, make_entry(p, size));
365404b540aSrobert 	std::__throw_logic_error(error.c_str());
366404b540aSrobert       }
367404b540aSrobert 
368404b540aSrobert     if (found_it->second.second != size)
369404b540aSrobert       {
370404b540aSrobert 	std::string error("throw_allocator_base::check_allocated by value ");
371404b540aSrobert 	error += "wrong-size erase!";
372404b540aSrobert 	error += '\n';
373404b540aSrobert 	print_to_string(error, make_entry(p, size));
374404b540aSrobert 	print_to_string(error, *found_it);
375404b540aSrobert 	std::__throw_logic_error(error.c_str());
376404b540aSrobert       }
377404b540aSrobert   }
378404b540aSrobert 
379404b540aSrobert   void
check_allocated(size_t label)380404b540aSrobert   throw_allocator_base::check_allocated(size_t label)
381404b540aSrobert   {
382404b540aSrobert     std::string found;
383404b540aSrobert     const_iterator it = _S_map.begin();
384404b540aSrobert     while (it != _S_map.end())
385404b540aSrobert       {
386404b540aSrobert 	if (it->second.first == label)
387404b540aSrobert 	  print_to_string(found, *it);
388404b540aSrobert 	++it;
389404b540aSrobert       }
390404b540aSrobert 
391404b540aSrobert     if (!found.empty())
392404b540aSrobert       {
393404b540aSrobert 	std::string error("throw_allocator_base::check_allocated by label ");
394404b540aSrobert 	error += '\n';
395404b540aSrobert 	error += found;
396404b540aSrobert 	std::__throw_logic_error(error.c_str());
397404b540aSrobert       }
398404b540aSrobert   }
399404b540aSrobert 
400404b540aSrobert   void
throw_conditionally()401404b540aSrobert   throw_allocator_base::throw_conditionally()
402404b540aSrobert   {
403404b540aSrobert     if (_S_g.get_prob() < _S_throw_prob)
404404b540aSrobert       __throw_forced_exception_error();
405404b540aSrobert   }
406404b540aSrobert 
407404b540aSrobert   void
print_to_string(std::string & s)408404b540aSrobert   throw_allocator_base::print_to_string(std::string& s)
409404b540aSrobert   {
410404b540aSrobert     const_iterator begin = throw_allocator_base::_S_map.begin();
411404b540aSrobert     const_iterator end = throw_allocator_base::_S_map.end();
412404b540aSrobert     for (; begin != end; ++begin)
413404b540aSrobert       print_to_string(s, *begin);
414404b540aSrobert   }
415404b540aSrobert 
416404b540aSrobert   void
print_to_string(std::string & s,const_reference ref)417404b540aSrobert   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
418404b540aSrobert   {
419404b540aSrobert     char buf[40];
420404b540aSrobert     const char tab('\t');
421404b540aSrobert     s += "address: ";
422*12bb21d5Sespie     snprintf(buf, sizeof buf, "%p", ref.first);
423404b540aSrobert     s += buf;
424404b540aSrobert     s += tab;
425404b540aSrobert     s += "label: ";
426*12bb21d5Sespie     snprintf(buf, sizeof buf, "%u", ref.second.first);
427404b540aSrobert     s += buf;
428404b540aSrobert     s += tab;
429404b540aSrobert     s += "size: ";
430*12bb21d5Sespie     snprintf(buf, sizeof buf, "%u", ref.second.second);
431404b540aSrobert     s += buf;
432404b540aSrobert     s += '\n';
433404b540aSrobert   }
434404b540aSrobert 
435404b540aSrobert _GLIBCXX_END_NAMESPACE
436404b540aSrobert 
437404b540aSrobert #endif
438