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 #ifndef _THROW_ALLOCATOR_H
00048 #define _THROW_ALLOCATOR_H 1
00049
00050 #include <cmath>
00051 #include <ctime>
00052 #include <map>
00053 #include <string>
00054 #include <ostream>
00055 #include <stdexcept>
00056 #include <utility>
00057 #include <bits/functexcept.h>
00058 #include <bits/move.h>
00059 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00060 # include <functional>
00061 # include <random>
00062 #else
00063 # include <tr1/functional>
00064 # include <tr1/random>
00065 #endif
00066
00067 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00068
00069
00070
00071
00072
00073 struct forced_error : public std::exception
00074 { };
00075
00076
00077 inline void
00078 __throw_forced_error()
00079 {
00080 #if __EXCEPTIONS
00081 throw forced_error();
00082 #else
00083 __builtin_abort();
00084 #endif
00085 }
00086
00087
00088
00089
00090
00091
00092
00093
00094 struct annotate_base
00095 {
00096 annotate_base()
00097 {
00098 label();
00099 map();
00100 }
00101
00102 static void
00103 set_label(size_t l)
00104 { label() = l; }
00105
00106 static size_t
00107 get_label()
00108 { return label(); }
00109
00110 void
00111 insert(void* p, size_t size)
00112 {
00113 if (p == NULL)
00114 {
00115 std::string error("annotate_base::insert null insert!\n");
00116 log_to_string(error, make_entry(p, size));
00117 std::__throw_logic_error(error.c_str());
00118 }
00119
00120 const_iterator found = map().find(p);
00121 if (found != map().end())
00122 {
00123 std::string error("annotate_base::insert double insert!\n");
00124 log_to_string(error, make_entry(p, size));
00125 log_to_string(error, *found);
00126 std::__throw_logic_error(error.c_str());
00127 }
00128
00129 map().insert(make_entry(p, size));
00130 }
00131
00132 void
00133 erase(void* p, size_t size)
00134 {
00135 check_allocated(p, size);
00136 map().erase(p);
00137 }
00138
00139
00140 inline void
00141 check_allocated(void* p, size_t size)
00142 {
00143 const_iterator found = map().find(p);
00144 if (found == map().end())
00145 {
00146 std::string error("annotate_base::check_allocated by value "
00147 "null erase!\n");
00148 log_to_string(error, make_entry(p, size));
00149 std::__throw_logic_error(error.c_str());
00150 }
00151
00152 if (found->second.second != size)
00153 {
00154 std::string error("annotate_base::check_allocated by value "
00155 "wrong-size erase!\n");
00156 log_to_string(error, make_entry(p, size));
00157 log_to_string(error, *found);
00158 std::__throw_logic_error(error.c_str());
00159 }
00160 }
00161
00162
00163 inline void
00164 check_allocated(size_t label)
00165 {
00166 const_iterator beg = map().begin();
00167 const_iterator end = map().end();
00168 std::string found;
00169 while (beg != end)
00170 {
00171 if (beg->second.first == label)
00172 log_to_string(found, *beg);
00173 ++beg;
00174 }
00175
00176 if (!found.empty())
00177 {
00178 std::string error("annotate_base::check_allocated by label\n");
00179 error += found;
00180 std::__throw_logic_error(error.c_str());
00181 }
00182 }
00183
00184 private:
00185 typedef std::pair<size_t, size_t> data_type;
00186 typedef std::map<void*, data_type> map_type;
00187 typedef map_type::value_type entry_type;
00188 typedef map_type::const_iterator const_iterator;
00189 typedef map_type::const_reference const_reference;
00190
00191 friend std::ostream&
00192 operator<<(std::ostream&, const annotate_base&);
00193
00194 entry_type
00195 make_entry(void* p, size_t size)
00196 { return std::make_pair(p, data_type(get_label(), size)); }
00197
00198 void
00199 log_to_string(std::string& s, const_reference ref) const
00200 {
00201 char buf[40];
00202 const char tab('\t');
00203 s += "label: ";
00204 unsigned long l = static_cast<unsigned long>(ref.second.first);
00205 __builtin_sprintf(buf, "%lu", l);
00206 s += buf;
00207 s += tab;
00208 s += "size: ";
00209 l = static_cast<unsigned long>(ref.second.second);
00210 __builtin_sprintf(buf, "%lu", l);
00211 s += buf;
00212 s += tab;
00213 s += "address: ";
00214 __builtin_sprintf(buf, "%p", ref.first);
00215 s += buf;
00216 s += '\n';
00217 }
00218
00219 static size_t&
00220 label()
00221 {
00222 static size_t _S_label(std::numeric_limits<size_t>::max());
00223 return _S_label;
00224 }
00225
00226 static map_type&
00227 map()
00228 {
00229 static map_type _S_map;
00230 return _S_map;
00231 }
00232 };
00233
00234 inline std::ostream&
00235 operator<<(std::ostream& os, const annotate_base& __b)
00236 {
00237 std::string error;
00238 typedef annotate_base base_type;
00239 base_type::const_iterator beg = __b.map().begin();
00240 base_type::const_iterator end = __b.map().end();
00241 for (; beg != end; ++beg)
00242 __b.log_to_string(error, *beg);
00243 return os << error;
00244 }
00245
00246
00247
00248
00249
00250
00251
00252
00253 struct condition_base
00254 {
00255 virtual ~condition_base() { };
00256 };
00257
00258
00259
00260
00261
00262 struct limit_condition : public condition_base
00263 {
00264
00265
00266
00267 struct adjustor_base
00268 {
00269 private:
00270 const size_t _M_orig;
00271
00272 public:
00273 adjustor_base() : _M_orig(limit()) { }
00274
00275 virtual
00276 ~adjustor_base() { set_limit(_M_orig); }
00277 };
00278
00279
00280 struct never_adjustor : public adjustor_base
00281 {
00282 never_adjustor() { set_limit(std::numeric_limits<size_t>::max()); }
00283 };
00284
00285
00286 struct always_adjustor : public adjustor_base
00287 {
00288 always_adjustor() { set_limit(count()); }
00289 };
00290
00291
00292 struct limit_adjustor : public adjustor_base
00293 {
00294 limit_adjustor(const size_t __l) { set_limit(__l); }
00295 };
00296
00297
00298
00299 static void
00300 throw_conditionally()
00301 {
00302 if (count() == limit())
00303 __throw_forced_error();
00304 ++count();
00305 }
00306
00307 static size_t&
00308 count()
00309 {
00310 static size_t _S_count(0);
00311 return _S_count;
00312 }
00313
00314 static size_t&
00315 limit()
00316 {
00317 static size_t _S_limit(std::numeric_limits<size_t>::max());
00318 return _S_limit;
00319 }
00320
00321
00322 static void
00323 set_limit(const size_t __l)
00324 {
00325 limit() = __l;
00326 count() = 0;
00327 }
00328 };
00329
00330
00331
00332
00333
00334 struct random_condition : public condition_base
00335 {
00336
00337
00338
00339 struct adjustor_base
00340 {
00341 private:
00342 const double _M_orig;
00343
00344 public:
00345 adjustor_base() : _M_orig(probability()) { }
00346
00347 virtual ~adjustor_base()
00348 { set_probability(_M_orig); }
00349 };
00350
00351
00352 struct group_adjustor : public adjustor_base
00353 {
00354 group_adjustor(size_t size)
00355 { set_probability(1 - std::pow(double(1 - probability()),
00356 double(0.5 / (size + 1))));
00357 }
00358 };
00359
00360
00361 struct never_adjustor : public adjustor_base
00362 {
00363 never_adjustor() { set_probability(0); }
00364 };
00365
00366
00367 struct always_adjustor : public adjustor_base
00368 {
00369 always_adjustor() { set_probability(1); }
00370 };
00371
00372 random_condition()
00373 {
00374 probability();
00375 engine();
00376 }
00377
00378 static void
00379 set_probability(double __p)
00380 { probability() = __p; }
00381
00382 static void
00383 throw_conditionally()
00384 {
00385 if (generate() < probability())
00386 __throw_forced_error();
00387 }
00388
00389 void
00390 seed(unsigned long __s)
00391 { engine().seed(__s); }
00392
00393 private:
00394 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00395 typedef std::uniform_real_distribution<double> distribution_type;
00396 typedef std::mt19937 engine_type;
00397 #else
00398 typedef std::tr1::uniform_real<double> distribution_type;
00399 typedef std::tr1::mt19937 engine_type;
00400 #endif
00401
00402 static double
00403 generate()
00404 {
00405 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00406 const distribution_type distribution(0, 1);
00407 static auto generator = std::bind(distribution, engine());
00408 #else
00409
00410 typedef std::tr1::variate_generator<engine_type, distribution_type> gen_t;
00411 distribution_type distribution(0, 1);
00412 static gen_t generator(engine(), distribution);
00413 #endif
00414
00415 double random = generator();
00416 if (random < distribution.min() || random > distribution.max())
00417 {
00418 std::string __s("random_condition::generate");
00419 __s += "\n";
00420 __s += "random number generated is: ";
00421 char buf[40];
00422 __builtin_sprintf(buf, "%f", random);
00423 __s += buf;
00424 std::__throw_out_of_range(__s.c_str());
00425 }
00426
00427 return random;
00428 }
00429
00430 static double&
00431 probability()
00432 {
00433 static double _S_p;
00434 return _S_p;
00435 }
00436
00437 static engine_type&
00438 engine()
00439 {
00440 static engine_type _S_e;
00441 return _S_e;
00442 }
00443 };
00444
00445
00446
00447
00448
00449
00450
00451
00452 template<typename _Cond>
00453 struct throw_value_base : public _Cond
00454 {
00455 typedef _Cond condition_type;
00456
00457 using condition_type::throw_conditionally;
00458
00459 std::size_t _M_i;
00460
00461 #ifndef _GLIBCXX_IS_AGGREGATE
00462 throw_value_base() : _M_i(0)
00463 { throw_conditionally(); }
00464
00465 throw_value_base(const throw_value_base& __v) : _M_i(__v._M_i)
00466 { throw_conditionally(); }
00467
00468 explicit throw_value_base(const std::size_t __i) : _M_i(__i)
00469 { throw_conditionally(); }
00470 #endif
00471
00472 throw_value_base&
00473 operator=(const throw_value_base& __v)
00474 {
00475 throw_conditionally();
00476 _M_i = __v._M_i;
00477 return *this;
00478 }
00479
00480 throw_value_base&
00481 operator++()
00482 {
00483 throw_conditionally();
00484 ++_M_i;
00485 return *this;
00486 }
00487 };
00488
00489 template<typename _Cond>
00490 inline void
00491 swap(throw_value_base<_Cond>& __a, throw_value_base<_Cond>& __b)
00492 {
00493 typedef throw_value_base<_Cond> throw_value;
00494 throw_value::throw_conditionally();
00495 throw_value orig(__a);
00496 __a = __b;
00497 __b = orig;
00498 }
00499
00500
00501 template<typename _Cond>
00502 inline bool
00503 operator==(const throw_value_base<_Cond>& __a,
00504 const throw_value_base<_Cond>& __b)
00505 {
00506 typedef throw_value_base<_Cond> throw_value;
00507 throw_value::throw_conditionally();
00508 bool __ret = __a._M_i == __b._M_i;
00509 return __ret;
00510 }
00511
00512 template<typename _Cond>
00513 inline bool
00514 operator<(const throw_value_base<_Cond>& __a,
00515 const throw_value_base<_Cond>& __b)
00516 {
00517 typedef throw_value_base<_Cond> throw_value;
00518 throw_value::throw_conditionally();
00519 bool __ret = __a._M_i < __b._M_i;
00520 return __ret;
00521 }
00522
00523
00524 template<typename _Cond>
00525 inline throw_value_base<_Cond>
00526 operator+(const throw_value_base<_Cond>& __a,
00527 const throw_value_base<_Cond>& __b)
00528 {
00529 typedef throw_value_base<_Cond> throw_value;
00530 throw_value::throw_conditionally();
00531 throw_value __ret(__a._M_i + __b._M_i);
00532 return __ret;
00533 }
00534
00535 template<typename _Cond>
00536 inline throw_value_base<_Cond>
00537 operator-(const throw_value_base<_Cond>& __a,
00538 const throw_value_base<_Cond>& __b)
00539 {
00540 typedef throw_value_base<_Cond> throw_value;
00541 throw_value::throw_conditionally();
00542 throw_value __ret(__a._M_i - __b._M_i);
00543 return __ret;
00544 }
00545
00546 template<typename _Cond>
00547 inline throw_value_base<_Cond>
00548 operator*(const throw_value_base<_Cond>& __a,
00549 const throw_value_base<_Cond>& __b)
00550 {
00551 typedef throw_value_base<_Cond> throw_value;
00552 throw_value::throw_conditionally();
00553 throw_value __ret(__a._M_i * __b._M_i);
00554 return __ret;
00555 }
00556
00557
00558
00559 struct throw_value_limit : public throw_value_base<limit_condition>
00560 {
00561 typedef throw_value_base<limit_condition> base_type;
00562
00563 #ifndef _GLIBCXX_IS_AGGREGATE
00564 throw_value_limit() { }
00565
00566 throw_value_limit(const throw_value_limit& __other)
00567 : base_type(__other._M_i) { }
00568
00569 explicit throw_value_limit(const std::size_t __i) : base_type(__i) { }
00570 #endif
00571 };
00572
00573
00574 struct throw_value_random : public throw_value_base<random_condition>
00575 {
00576 typedef throw_value_base<random_condition> base_type;
00577
00578 #ifndef _GLIBCXX_IS_AGGREGATE
00579 throw_value_random() { }
00580
00581 throw_value_random(const throw_value_random& __other)
00582 : base_type(__other._M_i) { }
00583
00584
00585 explicit throw_value_random(const std::size_t __i) : base_type(__i) { }
00586 #endif
00587 };
00588
00589
00590
00591
00592
00593
00594
00595
00596
00597 template<typename _Tp, typename _Cond>
00598 class throw_allocator_base
00599 : public annotate_base, public _Cond
00600 {
00601 public:
00602 typedef size_t size_type;
00603 typedef ptrdiff_t difference_type;
00604 typedef _Tp value_type;
00605 typedef value_type* pointer;
00606 typedef const value_type* const_pointer;
00607 typedef value_type& reference;
00608 typedef const value_type& const_reference;
00609
00610 private:
00611 typedef _Cond condition_type;
00612
00613 std::allocator<value_type> _M_allocator;
00614
00615 using condition_type::throw_conditionally;
00616
00617 public:
00618 size_type
00619 max_size() const throw()
00620 { return _M_allocator.max_size(); }
00621
00622 pointer
00623 allocate(size_type __n, std::allocator<void>::const_pointer hint = 0)
00624 {
00625 if (__n > this->max_size())
00626 std::__throw_bad_alloc();
00627
00628 throw_conditionally();
00629 pointer const a = _M_allocator.allocate(__n, hint);
00630 insert(a, sizeof(value_type) * __n);
00631 return a;
00632 }
00633
00634 void
00635 construct(pointer __p, const value_type& val)
00636 { return _M_allocator.construct(__p, val); }
00637
00638 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00639 template<typename... _Args>
00640 void
00641 construct(pointer __p, _Args&&... __args)
00642 { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
00643 #endif
00644
00645 void
00646 destroy(pointer __p)
00647 { _M_allocator.destroy(__p); }
00648
00649 void
00650 deallocate(pointer __p, size_type __n)
00651 {
00652 erase(__p, sizeof(value_type) * __n);
00653 _M_allocator.deallocate(__p, __n);
00654 }
00655
00656 void
00657 check_allocated(pointer __p, size_type __n)
00658 {
00659 size_type __t = sizeof(value_type) * __n;
00660 annotate_base::check_allocated(__p, __t);
00661 }
00662
00663 void
00664 check_allocated(size_type __n)
00665 { annotate_base::check_allocated(__n); }
00666 };
00667
00668 template<typename _Tp, typename _Cond>
00669 inline bool
00670 operator==(const throw_allocator_base<_Tp, _Cond>&,
00671 const throw_allocator_base<_Tp, _Cond>&)
00672 { return true; }
00673
00674 template<typename _Tp, typename _Cond>
00675 inline bool
00676 operator!=(const throw_allocator_base<_Tp, _Cond>&,
00677 const throw_allocator_base<_Tp, _Cond>&)
00678 { return false; }
00679
00680
00681 template<typename _Tp>
00682 struct throw_allocator_limit
00683 : public throw_allocator_base<_Tp, limit_condition>
00684 {
00685 template<typename _Tp1>
00686 struct rebind
00687 { typedef throw_allocator_limit<_Tp1> other; };
00688
00689 throw_allocator_limit() throw() { }
00690
00691 throw_allocator_limit(const throw_allocator_limit&) throw() { }
00692
00693 template<typename _Tp1>
00694 throw_allocator_limit(const throw_allocator_limit<_Tp1>&) throw() { }
00695
00696 ~throw_allocator_limit() throw() { }
00697 };
00698
00699
00700 template<typename _Tp>
00701 struct throw_allocator_random
00702 : public throw_allocator_base<_Tp, random_condition>
00703 {
00704 template<typename _Tp1>
00705 struct rebind
00706 { typedef throw_allocator_random<_Tp1> other; };
00707
00708 throw_allocator_random() throw() { }
00709
00710 throw_allocator_random(const throw_allocator_random&) throw() { }
00711
00712 template<typename _Tp1>
00713 throw_allocator_random(const throw_allocator_random<_Tp1>&) throw() { }
00714
00715 ~throw_allocator_random() throw() { }
00716 };
00717
00718 _GLIBCXX_END_NAMESPACE
00719
00720 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00721
00722 # include <bits/functional_hash.h>
00723
00724 namespace std
00725 {
00726
00727 template<>
00728 struct hash<__gnu_cxx::throw_value_limit>
00729 : public std::unary_function<__gnu_cxx::throw_value_limit, size_t>
00730 {
00731 size_t
00732 operator()(const __gnu_cxx::throw_value_limit& __val) const
00733 {
00734 std::hash<std::size_t> h;
00735 size_t __result = h(__val._M_i);
00736 return __result;
00737 }
00738 };
00739
00740
00741 template<>
00742 struct hash<__gnu_cxx::throw_value_random>
00743 : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
00744 {
00745 size_t
00746 operator()(const __gnu_cxx::throw_value_random& __val) const
00747 {
00748 std::hash<std::size_t> h;
00749 size_t __result = h(__val._M_i);
00750 return __result;
00751 }
00752 };
00753 }
00754 #endif
00755
00756 #endif