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