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