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
00051
00052
00053
00054 #ifndef _THROW_ALLOCATOR_H
00055 #define _THROW_ALLOCATOR_H 1
00056
00057 #include <cmath>
00058 #include <map>
00059 #include <set>
00060 #include <string>
00061 #include <ostream>
00062 #include <stdexcept>
00063 #include <utility>
00064 #include <tr1/random>
00065 #include <bits/functexcept.h>
00066
00067 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00068
00069 class twister_rand_gen
00070 {
00071 public:
00072 twister_rand_gen(unsigned int seed =
00073 static_cast<unsigned int>(std::time(0)));
00074
00075 void
00076 init(unsigned int);
00077
00078 double
00079 get_prob();
00080
00081 private:
00082 std::tr1::mt19937 _M_generator;
00083 };
00084
00085 struct forced_exception_error : public std::exception
00086 { };
00087
00088
00089 inline void
00090 __throw_forced_exception_error()
00091 {
00092 #if __EXCEPTIONS
00093 throw forced_exception_error();
00094 #else
00095 __builtin_abort();
00096 #endif
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 - ::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 num, std::allocator<void>::const_pointer hint = 0)
00224 {
00225 throw_conditionally();
00226 value_type* const a = std::allocator<value_type>().allocate(num, hint);
00227 insert(a, sizeof(value_type) * num);
00228 return a;
00229 }
00230
00231 void
00232 construct(pointer p, const T& val)
00233 { return std::allocator<value_type>().construct(p, val); }
00234
00235 void
00236 destroy(pointer p)
00237 { std::allocator<value_type>().destroy(p); }
00238
00239 void
00240 deallocate(pointer p, size_type num)
00241 {
00242 erase(p, sizeof(value_type) * num);
00243 std::allocator<value_type>().deallocate(p, num);
00244 }
00245
00246 void
00247 check_allocated(pointer p, size_type num)
00248 { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
00249
00250 void
00251 check_allocated(size_type label)
00252 { throw_allocator_base::check_allocated(label); }
00253 };
00254
00255 template<typename T>
00256 inline bool
00257 operator==(const throw_allocator<T>&, const throw_allocator<T>&)
00258 { return true; }
00259
00260 template<typename T>
00261 inline bool
00262 operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
00263 { return false; }
00264
00265 std::ostream&
00266 operator<<(std::ostream& os, const throw_allocator_base& alloc)
00267 {
00268 std::string error;
00269 throw_allocator_base::print_to_string(error);
00270 os << error;
00271 return os;
00272 }
00273
00274
00275 twister_rand_gen::
00276 twister_rand_gen(unsigned int seed) : _M_generator(seed) { }
00277
00278 void
00279 twister_rand_gen::
00280 init(unsigned int seed)
00281 { _M_generator.seed(seed); }
00282
00283 double
00284 twister_rand_gen::
00285 get_prob()
00286 {
00287 const double eng_min = _M_generator.min();
00288 const double eng_range =
00289 static_cast<const double>(_M_generator.max() - eng_min);
00290
00291 const double eng_res =
00292 static_cast<const double>(_M_generator() - eng_min);
00293
00294 const double ret = eng_res / eng_range;
00295 _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
00296 return ret;
00297 }
00298
00299 twister_rand_gen throw_allocator_base::_S_g;
00300
00301 throw_allocator_base::map_type
00302 throw_allocator_base::_S_map;
00303
00304 double throw_allocator_base::_S_throw_prob;
00305
00306 size_t throw_allocator_base::_S_label = 0;
00307
00308 throw_allocator_base::entry_type
00309 throw_allocator_base::make_entry(void* p, size_t size)
00310 { return std::make_pair(p, alloc_data_type(_S_label, size)); }
00311
00312 void
00313 throw_allocator_base::init(unsigned long seed)
00314 { _S_g.init(seed); }
00315
00316 void
00317 throw_allocator_base::set_throw_prob(double throw_prob)
00318 { _S_throw_prob = throw_prob; }
00319
00320 double
00321 throw_allocator_base::get_throw_prob()
00322 { return _S_throw_prob; }
00323
00324 void
00325 throw_allocator_base::set_label(size_t l)
00326 { _S_label = l; }
00327
00328 void
00329 throw_allocator_base::insert(void* p, size_t size)
00330 {
00331 const_iterator found_it = _S_map.find(p);
00332 if (found_it != _S_map.end())
00333 {
00334 std::string error("throw_allocator_base::insert");
00335 error += "double insert!";
00336 error += '\n';
00337 print_to_string(error, make_entry(p, size));
00338 print_to_string(error, *found_it);
00339 std::__throw_logic_error(error.c_str());
00340 }
00341 _S_map.insert(make_entry(p, size));
00342 }
00343
00344 bool
00345 throw_allocator_base::empty()
00346 { return _S_map.empty(); }
00347
00348 void
00349 throw_allocator_base::erase(void* p, size_t size)
00350 {
00351 check_allocated(p, size);
00352 _S_map.erase(p);
00353 }
00354
00355 void
00356 throw_allocator_base::check_allocated(void* p, size_t size)
00357 {
00358 const_iterator found_it = _S_map.find(p);
00359 if (found_it == _S_map.end())
00360 {
00361 std::string error("throw_allocator_base::check_allocated by value ");
00362 error += "null erase!";
00363 error += '\n';
00364 print_to_string(error, make_entry(p, size));
00365 std::__throw_logic_error(error.c_str());
00366 }
00367
00368 if (found_it->second.second != size)
00369 {
00370 std::string error("throw_allocator_base::check_allocated by value ");
00371 error += "wrong-size erase!";
00372 error += '\n';
00373 print_to_string(error, make_entry(p, size));
00374 print_to_string(error, *found_it);
00375 std::__throw_logic_error(error.c_str());
00376 }
00377 }
00378
00379 void
00380 throw_allocator_base::check_allocated(size_t label)
00381 {
00382 std::string found;
00383 const_iterator it = _S_map.begin();
00384 while (it != _S_map.end())
00385 {
00386 if (it->second.first == label)
00387 print_to_string(found, *it);
00388 ++it;
00389 }
00390
00391 if (!found.empty())
00392 {
00393 std::string error("throw_allocator_base::check_allocated by label ");
00394 error += '\n';
00395 error += found;
00396 std::__throw_logic_error(error.c_str());
00397 }
00398 }
00399
00400 void
00401 throw_allocator_base::throw_conditionally()
00402 {
00403 if (_S_g.get_prob() < _S_throw_prob)
00404 __throw_forced_exception_error();
00405 }
00406
00407 void
00408 throw_allocator_base::print_to_string(std::string& s)
00409 {
00410 const_iterator begin = throw_allocator_base::_S_map.begin();
00411 const_iterator end = throw_allocator_base::_S_map.end();
00412 for (; begin != end; ++begin)
00413 print_to_string(s, *begin);
00414 }
00415
00416 void
00417 throw_allocator_base::print_to_string(std::string& s, const_reference ref)
00418 {
00419 char buf[40];
00420 const char tab('\t');
00421 s += "address: ";
00422 sprintf(buf, "%p", ref.first);
00423 s += buf;
00424 s += tab;
00425 s += "label: ";
00426 sprintf(buf, "%u", ref.second.first);
00427 s += buf;
00428 s += tab;
00429 s += "size: ";
00430 sprintf(buf, "%u", ref.second.second);
00431 s += buf;
00432 s += '\n';
00433 }
00434
00435 _GLIBCXX_END_NAMESPACE
00436
00437 #endif