00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044 #ifndef _THROW_ALLOCATOR_H
00045 #define _THROW_ALLOCATOR_H 1
00046
00047 #include <cmath>
00048 #include <ctime>
00049 #include <map>
00050 #include <set>
00051 #include <string>
00052 #include <ostream>
00053 #include <stdexcept>
00054 #include <utility>
00055 #include <tr1/random>
00056 #include <bits/functexcept.h>
00057 #include <bits/move.h>
00058
00059 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00060
00061 class twister_rand_gen
00062 {
00063 private:
00064 std::tr1::mt19937 _M_generator;
00065
00066 public:
00067 twister_rand_gen(unsigned int s = static_cast<unsigned int>(std::time(0)));
00068
00069 void
00070 init(unsigned int);
00071
00072 double
00073 get_prob();
00074 };
00075
00076
00077
00078
00079
00080 struct forced_exception_error : public std::exception
00081 { };
00082
00083
00084 inline void
00085 __throw_forced_exception_error()
00086 {
00087 #if __EXCEPTIONS
00088 throw forced_exception_error();
00089 #else
00090 __builtin_abort();
00091 #endif
00092 }
00093
00094
00095 class throw_allocator_base
00096 {
00097 public:
00098 void
00099 init(unsigned long seed);
00100
00101 static void
00102 set_throw_prob(double throw_prob);
00103
00104 static double
00105 get_throw_prob();
00106
00107 static void
00108 set_label(size_t l);
00109
00110 static bool
00111 empty();
00112
00113 struct group_throw_prob_adjustor
00114 {
00115 group_throw_prob_adjustor(size_t size) : _M_throw_prob_orig(_S_throw_prob)
00116 {
00117 _S_throw_prob =
00118 1 - std::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
00119 }
00120
00121 ~group_throw_prob_adjustor()
00122 { _S_throw_prob = _M_throw_prob_orig; }
00123
00124 private:
00125 const double _M_throw_prob_orig;
00126 };
00127
00128 struct zero_throw_prob_adjustor
00129 {
00130 zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
00131 { _S_throw_prob = 0; }
00132
00133 ~zero_throw_prob_adjustor()
00134 { _S_throw_prob = _M_throw_prob_orig; }
00135
00136 private:
00137 const double _M_throw_prob_orig;
00138 };
00139
00140 protected:
00141 static void
00142 insert(void*, size_t);
00143
00144 static void
00145 erase(void*, size_t);
00146
00147 static void
00148 throw_conditionally();
00149
00150
00151
00152 static void
00153 check_allocated(void*, size_t);
00154
00155
00156 static void
00157 check_allocated(size_t);
00158
00159 private:
00160 typedef std::pair<size_t, size_t> alloc_data_type;
00161 typedef std::map<void*, alloc_data_type> map_type;
00162 typedef map_type::value_type entry_type;
00163 typedef map_type::const_iterator const_iterator;
00164 typedef map_type::const_reference const_reference;
00165
00166 friend std::ostream&
00167 operator<<(std::ostream&, const throw_allocator_base&);
00168
00169 static entry_type
00170 make_entry(void*, size_t);
00171
00172 static void
00173 print_to_string(std::string&);
00174
00175 static void
00176 print_to_string(std::string&, const_reference);
00177
00178 static twister_rand_gen _S_g;
00179 static map_type _S_map;
00180 static double _S_throw_prob;
00181 static size_t _S_label;
00182 };
00183
00184
00185
00186
00187
00188 template<typename T>
00189 class throw_allocator : public throw_allocator_base
00190 {
00191 public:
00192 typedef size_t size_type;
00193 typedef ptrdiff_t difference_type;
00194 typedef T value_type;
00195 typedef value_type* pointer;
00196 typedef const value_type* const_pointer;
00197 typedef value_type& reference;
00198 typedef const value_type& const_reference;
00199
00200
00201 template<typename U>
00202 struct rebind
00203 {
00204 typedef throw_allocator<U> other;
00205 };
00206
00207 throw_allocator() throw() { }
00208
00209 throw_allocator(const throw_allocator&) throw() { }
00210
00211 template<typename U>
00212 throw_allocator(const throw_allocator<U>&) throw() { }
00213
00214 ~throw_allocator() throw() { }
00215
00216 size_type
00217 max_size() const throw()
00218 { return std::allocator<value_type>().max_size(); }
00219
00220 pointer
00221 allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
00222 {
00223 if (__builtin_expect(__n > this->max_size(), false))
00224 std::__throw_bad_alloc();
00225
00226 throw_conditionally();
00227 value_type* const a = std::allocator<value_type>().allocate(__n, hint);
00228 insert(a, sizeof(value_type) * __n);
00229 return a;
00230 }
00231
00232 void
00233 construct(pointer __p, const T& val)
00234 { return std::allocator<value_type>().construct(__p, val); }
00235
00236 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00237 template<typename... _Args>
00238 void
00239 construct(pointer __p, _Args&&... __args)
00240 {
00241 return std::allocator<value_type>().
00242 construct(__p, std::forward<_Args>(__args)...);
00243 }
00244 #endif
00245
00246 void
00247 destroy(pointer __p)
00248 { std::allocator<value_type>().destroy(__p); }
00249
00250 void
00251 deallocate(pointer __p, size_type __n)
00252 {
00253 erase(__p, sizeof(value_type) * __n);
00254 std::allocator<value_type>().deallocate(__p, __n);
00255 }
00256
00257 void
00258 check_allocated(pointer __p, size_type __n)
00259 { throw_allocator_base::check_allocated(__p, sizeof(value_type) * __n); }
00260
00261 void
00262 check_allocated(size_type label)
00263 { throw_allocator_base::check_allocated(label); }
00264 };
00265
00266 template<typename T>
00267 inline bool
00268 operator==(const throw_allocator<T>&, const throw_allocator<T>&)
00269 { return true; }
00270
00271 template<typename T>
00272 inline bool
00273 operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
00274 { return false; }
00275
00276 std::ostream&
00277 operator<<(std::ostream& os, const throw_allocator_base& alloc)
00278 {
00279 std::string error;
00280 throw_allocator_base::print_to_string(error);
00281 os << error;
00282 return os;
00283 }
00284
00285
00286 twister_rand_gen::
00287 twister_rand_gen(unsigned int seed) : _M_generator(seed) { }
00288
00289 void
00290 twister_rand_gen::
00291 init(unsigned int seed)
00292 { _M_generator.seed(seed); }
00293
00294 double
00295 twister_rand_gen::
00296 get_prob()
00297 {
00298 const double min = _M_generator.min();
00299 const double res = static_cast<const double>(_M_generator() - min);
00300 const double range = static_cast<const double>(_M_generator.max() - min);
00301 const double ret = res / range;
00302 _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
00303 return ret;
00304 }
00305
00306 twister_rand_gen throw_allocator_base::_S_g;
00307
00308 throw_allocator_base::map_type
00309 throw_allocator_base::_S_map;
00310
00311 double throw_allocator_base::_S_throw_prob;
00312
00313 size_t throw_allocator_base::_S_label = 0;
00314
00315 throw_allocator_base::entry_type
00316 throw_allocator_base::make_entry(void* p, size_t size)
00317 { return std::make_pair(p, alloc_data_type(_S_label, size)); }
00318
00319 void
00320 throw_allocator_base::init(unsigned long seed)
00321 { _S_g.init(seed); }
00322
00323 void
00324 throw_allocator_base::set_throw_prob(double throw_prob)
00325 { _S_throw_prob = throw_prob; }
00326
00327 double
00328 throw_allocator_base::get_throw_prob()
00329 { return _S_throw_prob; }
00330
00331 void
00332 throw_allocator_base::set_label(size_t l)
00333 { _S_label = l; }
00334
00335 void
00336 throw_allocator_base::insert(void* p, size_t size)
00337 {
00338 const_iterator found_it = _S_map.find(p);
00339 if (found_it != _S_map.end())
00340 {
00341 std::string error("throw_allocator_base::insert");
00342 error += "double insert!";
00343 error += '\n';
00344 print_to_string(error, make_entry(p, size));
00345 print_to_string(error, *found_it);
00346 std::__throw_logic_error(error.c_str());
00347 }
00348 _S_map.insert(make_entry(p, size));
00349 }
00350
00351 bool
00352 throw_allocator_base::empty()
00353 { return _S_map.empty(); }
00354
00355 void
00356 throw_allocator_base::erase(void* p, size_t size)
00357 {
00358 check_allocated(p, size);
00359 _S_map.erase(p);
00360 }
00361
00362 void
00363 throw_allocator_base::check_allocated(void* p, size_t size)
00364 {
00365 const_iterator found_it = _S_map.find(p);
00366 if (found_it == _S_map.end())
00367 {
00368 std::string error("throw_allocator_base::check_allocated by value ");
00369 error += "null erase!";
00370 error += '\n';
00371 print_to_string(error, make_entry(p, size));
00372 std::__throw_logic_error(error.c_str());
00373 }
00374
00375 if (found_it->second.second != size)
00376 {
00377 std::string error("throw_allocator_base::check_allocated by value ");
00378 error += "wrong-size erase!";
00379 error += '\n';
00380 print_to_string(error, make_entry(p, size));
00381 print_to_string(error, *found_it);
00382 std::__throw_logic_error(error.c_str());
00383 }
00384 }
00385
00386 void
00387 throw_allocator_base::check_allocated(size_t label)
00388 {
00389 std::string found;
00390 const_iterator it = _S_map.begin();
00391 while (it != _S_map.end())
00392 {
00393 if (it->second.first == label)
00394 {
00395 print_to_string(found, *it);
00396 }
00397 ++it;
00398 }
00399
00400 if (!found.empty())
00401 {
00402 std::string error("throw_allocator_base::check_allocated by label ");
00403 error += '\n';
00404 error += found;
00405 std::__throw_logic_error(error.c_str());
00406 }
00407 }
00408
00409 void
00410 throw_allocator_base::throw_conditionally()
00411 {
00412 if (_S_g.get_prob() < _S_throw_prob)
00413 __throw_forced_exception_error();
00414 }
00415
00416 void
00417 throw_allocator_base::print_to_string(std::string& s)
00418 {
00419 const_iterator begin = throw_allocator_base::_S_map.begin();
00420 const_iterator end = throw_allocator_base::_S_map.end();
00421 for (; begin != end; ++begin)
00422 print_to_string(s, *begin);
00423 }
00424
00425 void
00426 throw_allocator_base::print_to_string(std::string& s, const_reference ref)
00427 {
00428 char buf[40];
00429 const char tab('\t');
00430 s += "address: ";
00431 __builtin_sprintf(buf, "%p", ref.first);
00432 s += buf;
00433 s += tab;
00434 s += "label: ";
00435 unsigned long l = static_cast<unsigned long>(ref.second.first);
00436 __builtin_sprintf(buf, "%lu", l);
00437 s += buf;
00438 s += tab;
00439 s += "size: ";
00440 l = static_cast<unsigned long>(ref.second.second);
00441 __builtin_sprintf(buf, "%lu", l);
00442 s += buf;
00443 s += '\n';
00444 }
00445
00446 _GLIBCXX_END_NAMESPACE
00447
00448 #endif