libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the terms 00008 // of the GNU General Public License as published by the Free Software 00009 // Foundation; either version 3, or (at your option) any later 00010 // version. 00011 00012 // This library is distributed in the hope that it will be useful, but 00013 // WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 // General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00027 00028 // Permission to use, copy, modify, sell, and distribute this software 00029 // is hereby granted without fee, provided that the above copyright 00030 // notice appears in all copies, and that both that copyright notice 00031 // and this permission notice appear in supporting documentation. None 00032 // of the above authors, nor IBM Haifa Research Laboratories, make any 00033 // representation about the suitability of this software for any 00034 // purpose. It is provided "as is" without express or implied 00035 // warranty. 00036 00037 /** @file ext/throw_allocator.h 00038 * This file is a GNU extension to the Standard C++ Library. 00039 * 00040 * Contains two exception-generating types (throw_value, throw_allocator) 00041 * intended to be used as value and allocator types while testing 00042 * exception safety in templatized containers and algorithms. The 00043 * allocator has additional log and debug features. The exception 00044 * generated is of type forced_exception_error. 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 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00068 { 00069 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00070 00071 /** 00072 * @brief Thown by exception safety machinery. 00073 * @ingroup exceptions 00074 */ 00075 struct forced_error : public std::exception 00076 { }; 00077 00078 // Substitute for forced_error object when -fno-exceptions. 00079 inline void 00080 __throw_forced_error() 00081 { 00082 #if __EXCEPTIONS 00083 throw forced_error(); 00084 #else 00085 __builtin_abort(); 00086 #endif 00087 } 00088 00089 00090 /** 00091 * @brief Base class for checking address and label information 00092 * about allocations. Create a std::map between the allocated 00093 * address (void*) and a datum for annotations, which are a pair of 00094 * numbers corresponding to label and allocated size. 00095 */ 00096 struct annotate_base 00097 { 00098 annotate_base() 00099 { 00100 label(); 00101 map(); 00102 } 00103 00104 static void 00105 set_label(size_t l) 00106 { label() = l; } 00107 00108 static size_t 00109 get_label() 00110 { return label(); } 00111 00112 void 00113 insert(void* p, size_t size) 00114 { 00115 if (!p) 00116 { 00117 std::string error("annotate_base::insert null insert!\n"); 00118 log_to_string(error, make_entry(p, size)); 00119 std::__throw_logic_error(error.c_str()); 00120 } 00121 00122 const_iterator found = map().find(p); 00123 if (found != map().end()) 00124 { 00125 std::string error("annotate_base::insert double insert!\n"); 00126 log_to_string(error, make_entry(p, size)); 00127 log_to_string(error, *found); 00128 std::__throw_logic_error(error.c_str()); 00129 } 00130 00131 map().insert(make_entry(p, size)); 00132 } 00133 00134 void 00135 erase(void* p, size_t size) 00136 { 00137 check_allocated(p, size); 00138 map().erase(p); 00139 } 00140 00141 // See if a particular address and allocation size has been saved. 00142 inline void 00143 check_allocated(void* p, size_t size) 00144 { 00145 const_iterator found = map().find(p); 00146 if (found == map().end()) 00147 { 00148 std::string error("annotate_base::check_allocated by value " 00149 "null erase!\n"); 00150 log_to_string(error, make_entry(p, size)); 00151 std::__throw_logic_error(error.c_str()); 00152 } 00153 00154 if (found->second.second != size) 00155 { 00156 std::string error("annotate_base::check_allocated by value " 00157 "wrong-size erase!\n"); 00158 log_to_string(error, make_entry(p, size)); 00159 log_to_string(error, *found); 00160 std::__throw_logic_error(error.c_str()); 00161 } 00162 } 00163 00164 // See if a given label has been allocated. 00165 inline void 00166 check_allocated(size_t label) 00167 { 00168 const_iterator beg = map().begin(); 00169 const_iterator end = map().end(); 00170 std::string found; 00171 while (beg != end) 00172 { 00173 if (beg->second.first == label) 00174 log_to_string(found, *beg); 00175 ++beg; 00176 } 00177 00178 if (!found.empty()) 00179 { 00180 std::string error("annotate_base::check_allocated by label\n"); 00181 error += found; 00182 std::__throw_logic_error(error.c_str()); 00183 } 00184 } 00185 00186 private: 00187 typedef std::pair<size_t, size_t> data_type; 00188 typedef std::map<void*, data_type> map_type; 00189 typedef map_type::value_type entry_type; 00190 typedef map_type::const_iterator const_iterator; 00191 typedef map_type::const_reference const_reference; 00192 00193 friend std::ostream& 00194 operator<<(std::ostream&, const annotate_base&); 00195 00196 entry_type 00197 make_entry(void* p, size_t size) 00198 { return std::make_pair(p, data_type(get_label(), size)); } 00199 00200 void 00201 log_to_string(std::string& s, const_reference ref) const 00202 { 00203 char buf[40]; 00204 const char tab('\t'); 00205 s += "label: "; 00206 unsigned long l = static_cast<unsigned long>(ref.second.first); 00207 __builtin_sprintf(buf, "%lu", l); 00208 s += buf; 00209 s += tab; 00210 s += "size: "; 00211 l = static_cast<unsigned long>(ref.second.second); 00212 __builtin_sprintf(buf, "%lu", l); 00213 s += buf; 00214 s += tab; 00215 s += "address: "; 00216 __builtin_sprintf(buf, "%p", ref.first); 00217 s += buf; 00218 s += '\n'; 00219 } 00220 00221 static size_t& 00222 label() 00223 { 00224 static size_t _S_label(std::numeric_limits<size_t>::max()); 00225 return _S_label; 00226 } 00227 00228 static map_type& 00229 map() 00230 { 00231 static map_type _S_map; 00232 return _S_map; 00233 } 00234 }; 00235 00236 inline std::ostream& 00237 operator<<(std::ostream& os, const annotate_base& __b) 00238 { 00239 std::string error; 00240 typedef annotate_base base_type; 00241 base_type::const_iterator beg = __b.map().begin(); 00242 base_type::const_iterator end = __b.map().end(); 00243 for (; beg != end; ++beg) 00244 __b.log_to_string(error, *beg); 00245 return os << error; 00246 } 00247 00248 00249 /** 00250 * @brief Base struct for condition policy. 00251 * 00252 * Requires a public member function with the signature 00253 * void throw_conditionally() 00254 */ 00255 struct condition_base 00256 { 00257 virtual ~condition_base() { }; 00258 }; 00259 00260 00261 /** 00262 * @brief Base class for incremental control and throw. 00263 */ 00264 struct limit_condition : public condition_base 00265 { 00266 // Scope-level adjustor objects: set limit for throw at the 00267 // beginning of a scope block, and restores to previous limit when 00268 // object is destroyed on exiting the block. 00269 struct adjustor_base 00270 { 00271 private: 00272 const size_t _M_orig; 00273 00274 public: 00275 adjustor_base() : _M_orig(limit()) { } 00276 00277 virtual 00278 ~adjustor_base() { set_limit(_M_orig); } 00279 }; 00280 00281 /// Never enter the condition. 00282 struct never_adjustor : public adjustor_base 00283 { 00284 never_adjustor() { set_limit(std::numeric_limits<size_t>::max()); } 00285 }; 00286 00287 /// Always enter the condition. 00288 struct always_adjustor : public adjustor_base 00289 { 00290 always_adjustor() { set_limit(count()); } 00291 }; 00292 00293 /// Enter the nth condition. 00294 struct limit_adjustor : public adjustor_base 00295 { 00296 limit_adjustor(const size_t __l) { set_limit(__l); } 00297 }; 00298 00299 // Increment _S_count every time called. 00300 // If _S_count matches the limit count, throw. 00301 static void 00302 throw_conditionally() 00303 { 00304 if (count() == limit()) 00305 __throw_forced_error(); 00306 ++count(); 00307 } 00308 00309 static size_t& 00310 count() 00311 { 00312 static size_t _S_count(0); 00313 return _S_count; 00314 } 00315 00316 static size_t& 00317 limit() 00318 { 00319 static size_t _S_limit(std::numeric_limits<size_t>::max()); 00320 return _S_limit; 00321 } 00322 00323 // Zero the throw counter, set limit to argument. 00324 static void 00325 set_limit(const size_t __l) 00326 { 00327 limit() = __l; 00328 count() = 0; 00329 } 00330 }; 00331 00332 00333 /** 00334 * @brief Base class for random probability control and throw. 00335 */ 00336 struct random_condition : public condition_base 00337 { 00338 // Scope-level adjustor objects: set probability for throw at the 00339 // beginning of a scope block, and restores to previous 00340 // probability when object is destroyed on exiting the block. 00341 struct adjustor_base 00342 { 00343 private: 00344 const double _M_orig; 00345 00346 public: 00347 adjustor_base() : _M_orig(probability()) { } 00348 00349 virtual ~adjustor_base() 00350 { set_probability(_M_orig); } 00351 }; 00352 00353 /// Group condition. 00354 struct group_adjustor : public adjustor_base 00355 { 00356 group_adjustor(size_t size) 00357 { set_probability(1 - std::pow(double(1 - probability()), 00358 double(0.5 / (size + 1)))); 00359 } 00360 }; 00361 00362 /// Never enter the condition. 00363 struct never_adjustor : public adjustor_base 00364 { 00365 never_adjustor() { set_probability(0); } 00366 }; 00367 00368 /// Always enter the condition. 00369 struct always_adjustor : public adjustor_base 00370 { 00371 always_adjustor() { set_probability(1); } 00372 }; 00373 00374 random_condition() 00375 { 00376 probability(); 00377 engine(); 00378 } 00379 00380 static void 00381 set_probability(double __p) 00382 { probability() = __p; } 00383 00384 static void 00385 throw_conditionally() 00386 { 00387 if (generate() < probability()) 00388 __throw_forced_error(); 00389 } 00390 00391 void 00392 seed(unsigned long __s) 00393 { engine().seed(__s); } 00394 00395 private: 00396 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00397 typedef std::uniform_real_distribution<double> distribution_type; 00398 typedef std::mt19937 engine_type; 00399 #else 00400 typedef std::tr1::uniform_real<double> distribution_type; 00401 typedef std::tr1::mt19937 engine_type; 00402 #endif 00403 00404 static double 00405 generate() 00406 { 00407 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00408 const distribution_type distribution(0, 1); 00409 static auto generator = std::bind(distribution, engine()); 00410 #else 00411 // Use variate_generator to get normalized results. 00412 typedef std::tr1::variate_generator<engine_type, distribution_type> gen_t; 00413 distribution_type distribution(0, 1); 00414 static gen_t generator(engine(), distribution); 00415 #endif 00416 00417 double random = generator(); 00418 if (random < distribution.min() || random > distribution.max()) 00419 { 00420 std::string __s("random_condition::generate"); 00421 __s += "\n"; 00422 __s += "random number generated is: "; 00423 char buf[40]; 00424 __builtin_sprintf(buf, "%f", random); 00425 __s += buf; 00426 std::__throw_out_of_range(__s.c_str()); 00427 } 00428 00429 return random; 00430 } 00431 00432 static double& 00433 probability() 00434 { 00435 static double _S_p; 00436 return _S_p; 00437 } 00438 00439 static engine_type& 00440 engine() 00441 { 00442 static engine_type _S_e; 00443 return _S_e; 00444 } 00445 }; 00446 00447 00448 /** 00449 * @brief Class with exception generation control. Intended to be 00450 * used as a value_type in templatized code. 00451 * 00452 * Note: Destructor not allowed to throw. 00453 */ 00454 template<typename _Cond> 00455 struct throw_value_base : public _Cond 00456 { 00457 typedef _Cond condition_type; 00458 00459 using condition_type::throw_conditionally; 00460 00461 std::size_t _M_i; 00462 00463 #ifndef _GLIBCXX_IS_AGGREGATE 00464 throw_value_base() : _M_i(0) 00465 { throw_conditionally(); } 00466 00467 throw_value_base(const throw_value_base& __v) : _M_i(__v._M_i) 00468 { throw_conditionally(); } 00469 00470 explicit throw_value_base(const std::size_t __i) : _M_i(__i) 00471 { throw_conditionally(); } 00472 #endif 00473 00474 throw_value_base& 00475 operator=(const throw_value_base& __v) 00476 { 00477 throw_conditionally(); 00478 _M_i = __v._M_i; 00479 return *this; 00480 } 00481 00482 throw_value_base& 00483 operator++() 00484 { 00485 throw_conditionally(); 00486 ++_M_i; 00487 return *this; 00488 } 00489 }; 00490 00491 template<typename _Cond> 00492 inline void 00493 swap(throw_value_base<_Cond>& __a, throw_value_base<_Cond>& __b) 00494 { 00495 typedef throw_value_base<_Cond> throw_value; 00496 throw_value::throw_conditionally(); 00497 throw_value orig(__a); 00498 __a = __b; 00499 __b = orig; 00500 } 00501 00502 // General instantiable types requirements. 00503 template<typename _Cond> 00504 inline bool 00505 operator==(const throw_value_base<_Cond>& __a, 00506 const throw_value_base<_Cond>& __b) 00507 { 00508 typedef throw_value_base<_Cond> throw_value; 00509 throw_value::throw_conditionally(); 00510 bool __ret = __a._M_i == __b._M_i; 00511 return __ret; 00512 } 00513 00514 template<typename _Cond> 00515 inline bool 00516 operator<(const throw_value_base<_Cond>& __a, 00517 const throw_value_base<_Cond>& __b) 00518 { 00519 typedef throw_value_base<_Cond> throw_value; 00520 throw_value::throw_conditionally(); 00521 bool __ret = __a._M_i < __b._M_i; 00522 return __ret; 00523 } 00524 00525 // Numeric algorithms instantiable types requirements. 00526 template<typename _Cond> 00527 inline throw_value_base<_Cond> 00528 operator+(const throw_value_base<_Cond>& __a, 00529 const throw_value_base<_Cond>& __b) 00530 { 00531 typedef throw_value_base<_Cond> throw_value; 00532 throw_value::throw_conditionally(); 00533 throw_value __ret(__a._M_i + __b._M_i); 00534 return __ret; 00535 } 00536 00537 template<typename _Cond> 00538 inline throw_value_base<_Cond> 00539 operator-(const throw_value_base<_Cond>& __a, 00540 const throw_value_base<_Cond>& __b) 00541 { 00542 typedef throw_value_base<_Cond> throw_value; 00543 throw_value::throw_conditionally(); 00544 throw_value __ret(__a._M_i - __b._M_i); 00545 return __ret; 00546 } 00547 00548 template<typename _Cond> 00549 inline throw_value_base<_Cond> 00550 operator*(const throw_value_base<_Cond>& __a, 00551 const throw_value_base<_Cond>& __b) 00552 { 00553 typedef throw_value_base<_Cond> throw_value; 00554 throw_value::throw_conditionally(); 00555 throw_value __ret(__a._M_i * __b._M_i); 00556 return __ret; 00557 } 00558 00559 00560 /// Type throwing via limit condition. 00561 struct throw_value_limit : public throw_value_base<limit_condition> 00562 { 00563 typedef throw_value_base<limit_condition> base_type; 00564 00565 #ifndef _GLIBCXX_IS_AGGREGATE 00566 throw_value_limit() { } 00567 00568 throw_value_limit(const throw_value_limit& __other) 00569 : base_type(__other._M_i) { } 00570 00571 explicit throw_value_limit(const std::size_t __i) : base_type(__i) { } 00572 #endif 00573 }; 00574 00575 /// Type throwing via random condition. 00576 struct throw_value_random : public throw_value_base<random_condition> 00577 { 00578 typedef throw_value_base<random_condition> base_type; 00579 00580 #ifndef _GLIBCXX_IS_AGGREGATE 00581 throw_value_random() { } 00582 00583 throw_value_random(const throw_value_random& __other) 00584 : base_type(__other._M_i) { } 00585 00586 00587 explicit throw_value_random(const std::size_t __i) : base_type(__i) { } 00588 #endif 00589 }; 00590 00591 00592 /** 00593 * @brief Allocator class with logging and exception generation control. 00594 * Intended to be used as an allocator_type in templatized code. 00595 * @ingroup allocators 00596 * 00597 * Note: Deallocate not allowed to throw. 00598 */ 00599 template<typename _Tp, typename _Cond> 00600 class throw_allocator_base 00601 : public annotate_base, public _Cond 00602 { 00603 public: 00604 typedef size_t size_type; 00605 typedef ptrdiff_t difference_type; 00606 typedef _Tp value_type; 00607 typedef value_type* pointer; 00608 typedef const value_type* const_pointer; 00609 typedef value_type& reference; 00610 typedef const value_type& const_reference; 00611 00612 private: 00613 typedef _Cond condition_type; 00614 00615 std::allocator<value_type> _M_allocator; 00616 00617 using condition_type::throw_conditionally; 00618 00619 public: 00620 size_type 00621 max_size() const _GLIBCXX_USE_NOEXCEPT 00622 { return _M_allocator.max_size(); } 00623 00624 pointer 00625 address(reference __x) const _GLIBCXX_NOEXCEPT 00626 { return std::__addressof(__x); } 00627 00628 const_pointer 00629 address(const_reference __x) const _GLIBCXX_NOEXCEPT 00630 { return std::__addressof(__x); } 00631 00632 pointer 00633 allocate(size_type __n, std::allocator<void>::const_pointer hint = 0) 00634 { 00635 if (__n > this->max_size()) 00636 std::__throw_bad_alloc(); 00637 00638 throw_conditionally(); 00639 pointer const a = _M_allocator.allocate(__n, hint); 00640 insert(a, sizeof(value_type) * __n); 00641 return a; 00642 } 00643 00644 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00645 template<typename _Up, typename... _Args> 00646 void 00647 construct(_Up* __p, _Args&&... __args) 00648 { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); } 00649 00650 template<typename _Up> 00651 void 00652 destroy(_Up* __p) 00653 { _M_allocator.destroy(__p); } 00654 #else 00655 void 00656 construct(pointer __p, const value_type& val) 00657 { return _M_allocator.construct(__p, val); } 00658 00659 void 00660 destroy(pointer __p) 00661 { _M_allocator.destroy(__p); } 00662 #endif 00663 00664 void 00665 deallocate(pointer __p, size_type __n) 00666 { 00667 erase(__p, sizeof(value_type) * __n); 00668 _M_allocator.deallocate(__p, __n); 00669 } 00670 00671 void 00672 check_allocated(pointer __p, size_type __n) 00673 { 00674 size_type __t = sizeof(value_type) * __n; 00675 annotate_base::check_allocated(__p, __t); 00676 } 00677 00678 void 00679 check_allocated(size_type __n) 00680 { annotate_base::check_allocated(__n); } 00681 }; 00682 00683 template<typename _Tp, typename _Cond> 00684 inline bool 00685 operator==(const throw_allocator_base<_Tp, _Cond>&, 00686 const throw_allocator_base<_Tp, _Cond>&) 00687 { return true; } 00688 00689 template<typename _Tp, typename _Cond> 00690 inline bool 00691 operator!=(const throw_allocator_base<_Tp, _Cond>&, 00692 const throw_allocator_base<_Tp, _Cond>&) 00693 { return false; } 00694 00695 /// Allocator throwing via limit condition. 00696 template<typename _Tp> 00697 struct throw_allocator_limit 00698 : public throw_allocator_base<_Tp, limit_condition> 00699 { 00700 template<typename _Tp1> 00701 struct rebind 00702 { typedef throw_allocator_limit<_Tp1> other; }; 00703 00704 throw_allocator_limit() _GLIBCXX_USE_NOEXCEPT { } 00705 00706 throw_allocator_limit(const throw_allocator_limit&) 00707 _GLIBCXX_USE_NOEXCEPT { } 00708 00709 template<typename _Tp1> 00710 throw_allocator_limit(const throw_allocator_limit<_Tp1>&) 00711 _GLIBCXX_USE_NOEXCEPT { } 00712 00713 ~throw_allocator_limit() _GLIBCXX_USE_NOEXCEPT { } 00714 }; 00715 00716 /// Allocator throwing via random condition. 00717 template<typename _Tp> 00718 struct throw_allocator_random 00719 : public throw_allocator_base<_Tp, random_condition> 00720 { 00721 template<typename _Tp1> 00722 struct rebind 00723 { typedef throw_allocator_random<_Tp1> other; }; 00724 00725 throw_allocator_random() _GLIBCXX_USE_NOEXCEPT { } 00726 00727 throw_allocator_random(const throw_allocator_random&) 00728 _GLIBCXX_USE_NOEXCEPT { } 00729 00730 template<typename _Tp1> 00731 throw_allocator_random(const throw_allocator_random<_Tp1>&) 00732 _GLIBCXX_USE_NOEXCEPT { } 00733 00734 ~throw_allocator_random() _GLIBCXX_USE_NOEXCEPT { } 00735 }; 00736 00737 _GLIBCXX_END_NAMESPACE_VERSION 00738 } // namespace 00739 00740 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00741 00742 # include <bits/functional_hash.h> 00743 00744 namespace std _GLIBCXX_VISIBILITY(default) 00745 { 00746 /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit. 00747 template<> 00748 struct hash<__gnu_cxx::throw_value_limit> 00749 : public std::unary_function<__gnu_cxx::throw_value_limit, size_t> 00750 { 00751 size_t 00752 operator()(const __gnu_cxx::throw_value_limit& __val) const 00753 { 00754 std::hash<std::size_t> __h; 00755 size_t __result = __h(__val._M_i); 00756 return __result; 00757 } 00758 }; 00759 00760 /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit. 00761 template<> 00762 struct hash<__gnu_cxx::throw_value_random> 00763 : public std::unary_function<__gnu_cxx::throw_value_random, size_t> 00764 { 00765 size_t 00766 operator()(const __gnu_cxx::throw_value_random& __val) const 00767 { 00768 std::hash<std::size_t> __h; 00769 size_t __result = __h(__val._M_i); 00770 return __result; 00771 } 00772 }; 00773 } // end namespace std 00774 #endif 00775 00776 #endif