11573Srgrimes// -*- C++ -*- 21573Srgrimes 31573Srgrimes// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 41573Srgrimes// 51573Srgrimes// This file is part of the GNU ISO C++ Library. This library is free 61573Srgrimes// software; you can redistribute it and/or modify it under the terms 71573Srgrimes// of the GNU General Public License as published by the Free Software 81573Srgrimes// Foundation; either version 2, or (at your option) any later 91573Srgrimes// version. 101573Srgrimes 111573Srgrimes// This library is distributed in the hope that it will be useful, but 121573Srgrimes// WITHOUT ANY WARRANTY; without even the implied warranty of 131573Srgrimes// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 141573Srgrimes// General Public License for more details. 151573Srgrimes 161573Srgrimes// You should have received a copy of the GNU General Public License 171573Srgrimes// along with this library; see the file COPYING. If not, write to 181573Srgrimes// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 191573Srgrimes// MA 02111-1307, USA. 201573Srgrimes 211573Srgrimes// As a special exception, you may use this file as part of a free 221573Srgrimes// software library without restriction. Specifically, if other files 231573Srgrimes// instantiate templates or use macros or inline functions from this 241573Srgrimes// file, or you compile this file and link it with other files to 251573Srgrimes// produce an executable, this file does not by itself cause the 261573Srgrimes// resulting executable to be covered by the GNU General Public 271573Srgrimes// License. This exception does not however invalidate any other 281573Srgrimes// reasons why the executable file might be covered by the GNU General 291573Srgrimes// Public License. 301573Srgrimes 311573Srgrimes// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 321573Srgrimes 331573Srgrimes// Permission to use, copy, modify, sell, and distribute this software 341573Srgrimes// is hereby granted without fee, provided that the above copyright 351573Srgrimes// notice appears in all copies, and that both that copyright notice 3690039Sobrien// and this permission notice appear in supporting documentation. None 3790039Sobrien// of the above authors, nor IBM Haifa Research Laboratories, make any 381573Srgrimes// representation about the suitability of this software for any 391573Srgrimes// purpose. It is provided "as is" without express or implied 4012674Sdg// warranty. 411573Srgrimes 421573Srgrimes/** @file ext/vstring.h 43106055Swollman * This file is a GNU extension to the Standard C++ Library. 441573Srgrimes * 45237660Skib * Contains an exception-throwing allocator, useful for testing 461573Srgrimes * exception safety. In addition, allocation addresses are stored and 47103730Swollman * sanity checked. 48103730Swollman */ 49103730Swollman 506171Sbde/** 511573Srgrimes * @file throw_allocator.h 521573Srgrimes */ 53103730Swollman 54204347Sedwin#ifndef _THROW_ALLOCATOR_H 55237660Skib#define _THROW_ALLOCATOR_H 1 56103730Swollman 57103730Swollman#include <cmath> 58103730Swollman#include <map> 591573Srgrimes#include <set> 601573Srgrimes#include <string> 611573Srgrimes#include <ostream> 621573Srgrimes#include <stdexcept> 631573Srgrimes#include <utility> 641573Srgrimes#include <tr1/random> 651573Srgrimes#include <bits/functexcept.h> 661573Srgrimes 671573Srgrimes_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 681573Srgrimes 691573Srgrimes class twister_rand_gen 701573Srgrimes { 711573Srgrimes public: 721573Srgrimes twister_rand_gen(unsigned int seed = 731573Srgrimes static_cast<unsigned int>(std::time(0))); 741573Srgrimes 751573Srgrimes void 761573Srgrimes init(unsigned int); 77103730Swollman 78168718Spjd double 79103730Swollman get_prob(); 801573Srgrimes 8136577Smsmith private: 821573Srgrimes std::tr1::mt19937 _M_generator; 831573Srgrimes }; 841573Srgrimes 851573Srgrimes struct forced_exception_error : public std::exception 861573Srgrimes { }; 871573Srgrimes 881573Srgrimes // Substitute for concurrence_error object in the case of -fno-exceptions. 89103730Swollman inline void 90103730Swollman __throw_forced_exception_error() 91103730Swollman { 92103730Swollman#if __EXCEPTIONS 93103730Swollman throw forced_exception_error(); 94103730Swollman#else 95103730Swollman __builtin_abort(); 96103730Swollman#endif 97103730Swollman } 981573Srgrimes 991573Srgrimes class throw_allocator_base 1001573Srgrimes { 1011573Srgrimes public: 1021573Srgrimes void 1031573Srgrimes init(unsigned long seed); 1041573Srgrimes 105103730Swollman static void 106103730Swollman set_throw_prob(double throw_prob); 107103730Swollman 108103730Swollman static double 109103730Swollman get_throw_prob(); 110103730Swollman 111103730Swollman static void 112103730Swollman set_label(size_t l); 113103730Swollman 114176618Swollman static bool 115176618Swollman empty(); 116176618Swollman 117176618Swollman struct group_throw_prob_adjustor 118176618Swollman { 119176618Swollman group_throw_prob_adjustor(size_t size) 120176618Swollman : _M_throw_prob_orig(_S_throw_prob) 121176618Swollman { 122176618Swollman _S_throw_prob = 123176618Swollman 1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1))); 124176618Swollman } 125176618Swollman 126176618Swollman ~group_throw_prob_adjustor() 127176618Swollman { _S_throw_prob = _M_throw_prob_orig; } 128176618Swollman 129176618Swollman private: 130176618Swollman const double _M_throw_prob_orig; 131176618Swollman }; 132176618Swollman 133103730Swollman struct zero_throw_prob_adjustor 134103730Swollman { 1351573Srgrimes zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob) 136103730Swollman { _S_throw_prob = 0; } 1371573Srgrimes 1381573Srgrimes ~zero_throw_prob_adjustor() 1391573Srgrimes { _S_throw_prob = _M_throw_prob_orig; } 1401573Srgrimes 1411573Srgrimes private: 1421573Srgrimes const double _M_throw_prob_orig; 1431573Srgrimes }; 1441573Srgrimes 145103730Swollman protected: 1461573Srgrimes static void 147103730Swollman insert(void*, size_t); 1481573Srgrimes 149103730Swollman static void 1501573Srgrimes erase(void*, size_t); 151103730Swollman 1521573Srgrimes static void 153103730Swollman throw_conditionally(); 1541573Srgrimes 155103730Swollman // See if a particular address and size has been allocated by this 1561573Srgrimes // allocator. 157103730Swollman static void 1581573Srgrimes check_allocated(void*, size_t); 159103730Swollman 1601573Srgrimes // See if a given label has been allocated by this allocator. 161103730Swollman static void 162103730Swollman check_allocated(size_t); 163103730Swollman 164103730Swollman private: 165103730Swollman typedef std::pair<size_t, size_t> alloc_data_type; 166103730Swollman typedef std::map<void*, alloc_data_type> map_type; 1671573Srgrimes typedef map_type::value_type entry_type; 168103730Swollman typedef map_type::const_iterator const_iterator; 1691573Srgrimes typedef map_type::const_reference const_reference; 170103730Swollman 1711573Srgrimes friend std::ostream& 172103730Swollman operator<<(std::ostream&, const throw_allocator_base&); 1731573Srgrimes 174103730Swollman static entry_type 1751573Srgrimes make_entry(void*, size_t); 176103730Swollman 1771573Srgrimes static void 178103730Swollman print_to_string(std::string&); 1791573Srgrimes 180103730Swollman static void 1811573Srgrimes print_to_string(std::string&, const_reference); 182103730Swollman 183103730Swollman static twister_rand_gen _S_g; 184103730Swollman static map_type _S_map; 185103730Swollman static double _S_throw_prob; 186103730Swollman static size_t _S_label; 187103730Swollman }; 188168718Spjd 189168718Spjd 190103730Swollman template<typename T> 191103730Swollman class throw_allocator : public throw_allocator_base 192168718Spjd { 19334030Sdufault public: 19434030Sdufault typedef size_t size_type; 195106055Swollman typedef ptrdiff_t difference_type; 19634925Sdufault typedef T value_type; 19734925Sdufault typedef value_type* pointer; 198106055Swollman typedef const value_type* const_pointer; 199106055Swollman typedef value_type& reference; 200106055Swollman typedef const value_type& const_reference; 201106055Swollman 20234030Sdufault 203103730Swollman template<typename U> 20434030Sdufault struct rebind 205103730Swollman { 20634030Sdufault typedef throw_allocator<U> other; 207103730Swollman }; 20834030Sdufault 209103730Swollman throw_allocator() throw() { } 21034030Sdufault 211103730Swollman throw_allocator(const throw_allocator&) throw() { } 21234925Sdufault 21334925Sdufault template<typename U> 21434030Sdufault throw_allocator(const throw_allocator<U>&) throw() { } 215103730Swollman 216103730Swollman ~throw_allocator() throw() { } 217103730Swollman 21834030Sdufault size_type 219103730Swollman max_size() const throw() 22034925Sdufault { return std::allocator<value_type>().max_size(); } 22134925Sdufault 22234030Sdufault pointer 223103730Swollman allocate(size_type num, std::allocator<void>::const_pointer hint = 0) 224103730Swollman { 225103730Swollman throw_conditionally(); 22634030Sdufault value_type* const a = std::allocator<value_type>().allocate(num, hint); 227103730Swollman insert(a, sizeof(value_type) * num); 22834925Sdufault return a; 22934925Sdufault } 23034030Sdufault 231103730Swollman void 232103730Swollman construct(pointer p, const T& val) 233103730Swollman { return std::allocator<value_type>().construct(p, val); } 23434030Sdufault 235103730Swollman void 23634925Sdufault destroy(pointer p) 23734925Sdufault { std::allocator<value_type>().destroy(p); } 23834030Sdufault 239103730Swollman void 240103730Swollman deallocate(pointer p, size_type num) 241103730Swollman { 24234030Sdufault erase(p, sizeof(value_type) * num); 243103730Swollman std::allocator<value_type>().deallocate(p, num); 24434925Sdufault } 24534925Sdufault 24634030Sdufault void 247103730Swollman check_allocated(pointer p, size_type num) 248103730Swollman { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); } 249103730Swollman 250103730Swollman void 251103730Swollman check_allocated(size_type label) 252103730Swollman { throw_allocator_base::check_allocated(label); } 25334030Sdufault }; 254103730Swollman 25534030Sdufault template<typename T> 256103730Swollman inline bool 25734925Sdufault operator==(const throw_allocator<T>&, const throw_allocator<T>&) 25834925Sdufault { return true; } 25934030Sdufault 260103730Swollman template<typename T> 261103730Swollman inline bool 262103730Swollman operator!=(const throw_allocator<T>&, const throw_allocator<T>&) 26334030Sdufault { return false; } 264103730Swollman 26534925Sdufault std::ostream& 26634925Sdufault operator<<(std::ostream& os, const throw_allocator_base& alloc) 26734030Sdufault { 268103730Swollman std::string error; 269103730Swollman throw_allocator_base::print_to_string(error); 270103730Swollman os << error; 27134030Sdufault return os; 27234925Sdufault } 27334925Sdufault 274107000Sdougb // XXX Should be in .cc. 27534030Sdufault twister_rand_gen:: 27634925Sdufault twister_rand_gen(unsigned int seed) : _M_generator(seed) { } 27734925Sdufault 278107000Sdougb void 27934030Sdufault twister_rand_gen:: 28034925Sdufault init(unsigned int seed) 28134925Sdufault { _M_generator.seed(seed); } 282107000Sdougb 28334030Sdufault double 28434925Sdufault twister_rand_gen:: 28534925Sdufault get_prob() 28634030Sdufault { 28734030Sdufault const double eng_min = _M_generator.min(); 28834925Sdufault const double eng_range = 28934925Sdufault static_cast<const double>(_M_generator.max() - eng_min); 29034030Sdufault 29134030Sdufault const double eng_res = 29236577Smsmith static_cast<const double>(_M_generator() - eng_min); 29334925Sdufault 29434925Sdufault const double ret = eng_res / eng_range; 29534030Sdufault _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1); 29634030Sdufault return ret; 29734925Sdufault } 29834925Sdufault 29934030Sdufault twister_rand_gen throw_allocator_base::_S_g; 30034030Sdufault 30134925Sdufault throw_allocator_base::map_type 30234925Sdufault throw_allocator_base::_S_map; 30334030Sdufault 30434030Sdufault double throw_allocator_base::_S_throw_prob; 30534925Sdufault 30634925Sdufault size_t throw_allocator_base::_S_label = 0; 30734030Sdufault 30834030Sdufault throw_allocator_base::entry_type 30934925Sdufault throw_allocator_base::make_entry(void* p, size_t size) 31034925Sdufault { return std::make_pair(p, alloc_data_type(_S_label, size)); } 31134030Sdufault 31234030Sdufault void 31334925Sdufault throw_allocator_base::init(unsigned long seed) 31434925Sdufault { _S_g.init(seed); } 315168718Spjd 316168718Spjd void 317168718Spjd throw_allocator_base::set_throw_prob(double throw_prob) 318103730Swollman { _S_throw_prob = throw_prob; } 319103730Swollman 320103730Swollman double 321168718Spjd throw_allocator_base::get_throw_prob() 322100142Swollman { return _S_throw_prob; } 323103730Swollman 324103730Swollman void 325103730Swollman throw_allocator_base::set_label(size_t l) 326103730Swollman { _S_label = l; } 327103730Swollman 328103730Swollman void 329103730Swollman throw_allocator_base::insert(void* p, size_t size) 330103730Swollman { 331103730Swollman const_iterator found_it = _S_map.find(p); 332103730Swollman if (found_it != _S_map.end()) 333103730Swollman { 334103730Swollman std::string error("throw_allocator_base::insert"); 335103730Swollman error += "double insert!"; 336103730Swollman error += '\n'; 337103730Swollman print_to_string(error, make_entry(p, size)); 338103730Swollman print_to_string(error, *found_it); 339103730Swollman std::__throw_logic_error(error.c_str()); 340103730Swollman } 341103730Swollman _S_map.insert(make_entry(p, size)); 34287161Sjkoshy } 343103730Swollman 344103730Swollman bool 345103730Swollman throw_allocator_base::empty() 346103730Swollman { return _S_map.empty(); } 347103730Swollman 348103730Swollman void 349103730Swollman throw_allocator_base::erase(void* p, size_t size) 350103730Swollman { 351103730Swollman check_allocated(p, size); 352103730Swollman _S_map.erase(p); 353103730Swollman } 354103730Swollman 355103730Swollman void 356103730Swollman throw_allocator_base::check_allocated(void* p, size_t size) 357103730Swollman { 358103730Swollman const_iterator found_it = _S_map.find(p); 359103730Swollman if (found_it == _S_map.end()) 360103730Swollman { 361103730Swollman std::string error("throw_allocator_base::check_allocated by value "); 362103730Swollman error += "null erase!"; 363103730Swollman error += '\n'; 364103730Swollman print_to_string(error, make_entry(p, size)); 365103730Swollman std::__throw_logic_error(error.c_str()); 366103730Swollman } 367103730Swollman 368103730Swollman if (found_it->second.second != size) 369103730Swollman { 370268741Skib std::string error("throw_allocator_base::check_allocated by value "); 371268741Skib error += "wrong-size erase!"; 372268741Skib error += '\n'; 373268741Skib print_to_string(error, make_entry(p, size)); 374268741Skib print_to_string(error, *found_it); 375268741Skib std::__throw_logic_error(error.c_str()); 376268741Skib } 377268741Skib } 378103730Swollman 379103730Swollman void 380268741Skib throw_allocator_base::check_allocated(size_t label) 381103730Swollman { 382103730Swollman std::string found; 383103730Swollman const_iterator it = _S_map.begin(); 384103730Swollman while (it != _S_map.end()) 385103730Swollman { 386103730Swollman if (it->second.first == label) 387103730Swollman print_to_string(found, *it); 388103730Swollman ++it; 389103730Swollman } 390103730Swollman 391103730Swollman if (!found.empty()) 392103730Swollman { 393103730Swollman std::string error("throw_allocator_base::check_allocated by label "); 394103730Swollman error += '\n'; 395103730Swollman error += found; 396103730Swollman std::__throw_logic_error(error.c_str()); 397103730Swollman } 398103730Swollman } 399103730Swollman 400103730Swollman void 401103730Swollman throw_allocator_base::throw_conditionally() 402103730Swollman { 403103730Swollman if (_S_g.get_prob() < _S_throw_prob) 404103730Swollman __throw_forced_exception_error(); 405103730Swollman } 406103730Swollman 407103730Swollman void 408103730Swollman throw_allocator_base::print_to_string(std::string& s) 409103730Swollman { 410103730Swollman const_iterator begin = throw_allocator_base::_S_map.begin(); 411103730Swollman const_iterator end = throw_allocator_base::_S_map.end(); 412103730Swollman for (; begin != end; ++begin) 413103730Swollman print_to_string(s, *begin); 414103730Swollman } 415103730Swollman 416103730Swollman void 417103730Swollman throw_allocator_base::print_to_string(std::string& s, const_reference ref) 418103730Swollman { 419103730Swollman char buf[40]; 420103730Swollman const char tab('\t'); 421103730Swollman s += "address: "; 422103730Swollman snprintf(buf, sizeof buf, "%p", ref.first); 423103730Swollman s += buf; 424103730Swollman s += tab; 425103730Swollman s += "label: "; 426103730Swollman snprintf(buf, sizeof buf, "%u", ref.second.first); 427103730Swollman s += buf; 428103730Swollman s += tab; 429103730Swollman s += "size: "; 430103730Swollman snprintf(buf, sizeof buf, "%u", ref.second.second); 431103730Swollman s += buf; 432103730Swollman s += '\n'; 433103730Swollman } 434103730Swollman 435103730Swollman_GLIBCXX_END_NAMESPACE 436103730Swollman 437103730Swollman#endif 438103730Swollman