1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** @file ext/vstring.h 43169691Skan * This file is a GNU extension to the Standard C++ Library. 44169691Skan * 45169691Skan * Contains an exception-throwing allocator, useful for testing 46169691Skan * exception safety. In addition, allocation addresses are stored and 47169691Skan * sanity checked. 48169691Skan */ 49169691Skan 50169691Skan/** 51169691Skan * @file throw_allocator.h 52169691Skan */ 53169691Skan 54169691Skan#ifndef _THROW_ALLOCATOR_H 55169691Skan#define _THROW_ALLOCATOR_H 1 56169691Skan 57169691Skan#include <cmath> 58169691Skan#include <map> 59169691Skan#include <set> 60169691Skan#include <string> 61169691Skan#include <ostream> 62169691Skan#include <stdexcept> 63169691Skan#include <utility> 64169691Skan#include <tr1/random> 65171827Skan#include <bits/functexcept.h> 66169691Skan 67169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 68169691Skan 69169691Skan class twister_rand_gen 70169691Skan { 71169691Skan public: 72169691Skan twister_rand_gen(unsigned int seed = 73169691Skan static_cast<unsigned int>(std::time(0))); 74169691Skan 75169691Skan void 76169691Skan init(unsigned int); 77169691Skan 78169691Skan double 79169691Skan get_prob(); 80169691Skan 81169691Skan private: 82169691Skan std::tr1::mt19937 _M_generator; 83169691Skan }; 84169691Skan 85169691Skan struct forced_exception_error : public std::exception 86169691Skan { }; 87169691Skan 88171827Skan // Substitute for concurrence_error object in the case of -fno-exceptions. 89171827Skan inline void 90171827Skan __throw_forced_exception_error() 91171827Skan { 92171827Skan#if __EXCEPTIONS 93171827Skan throw forced_exception_error(); 94171827Skan#else 95171827Skan __builtin_abort(); 96171827Skan#endif 97171827Skan } 98171827Skan 99169691Skan class throw_allocator_base 100169691Skan { 101169691Skan public: 102169691Skan void 103169691Skan init(unsigned long seed); 104169691Skan 105169691Skan static void 106169691Skan set_throw_prob(double throw_prob); 107169691Skan 108169691Skan static double 109169691Skan get_throw_prob(); 110169691Skan 111169691Skan static void 112169691Skan set_label(size_t l); 113169691Skan 114169691Skan static bool 115169691Skan empty(); 116169691Skan 117169691Skan struct group_throw_prob_adjustor 118169691Skan { 119169691Skan group_throw_prob_adjustor(size_t size) 120169691Skan : _M_throw_prob_orig(_S_throw_prob) 121169691Skan { 122169691Skan _S_throw_prob = 123169691Skan 1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1))); 124169691Skan } 125169691Skan 126169691Skan ~group_throw_prob_adjustor() 127169691Skan { _S_throw_prob = _M_throw_prob_orig; } 128169691Skan 129169691Skan private: 130169691Skan const double _M_throw_prob_orig; 131169691Skan }; 132169691Skan 133169691Skan struct zero_throw_prob_adjustor 134169691Skan { 135169691Skan zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob) 136169691Skan { _S_throw_prob = 0; } 137169691Skan 138169691Skan ~zero_throw_prob_adjustor() 139169691Skan { _S_throw_prob = _M_throw_prob_orig; } 140169691Skan 141169691Skan private: 142169691Skan const double _M_throw_prob_orig; 143169691Skan }; 144169691Skan 145169691Skan protected: 146169691Skan static void 147169691Skan insert(void*, size_t); 148169691Skan 149169691Skan static void 150169691Skan erase(void*, size_t); 151169691Skan 152169691Skan static void 153169691Skan throw_conditionally(); 154169691Skan 155169691Skan // See if a particular address and size has been allocated by this 156169691Skan // allocator. 157169691Skan static void 158169691Skan check_allocated(void*, size_t); 159169691Skan 160169691Skan // See if a given label has been allocated by this allocator. 161169691Skan static void 162169691Skan check_allocated(size_t); 163169691Skan 164169691Skan private: 165169691Skan typedef std::pair<size_t, size_t> alloc_data_type; 166169691Skan typedef std::map<void*, alloc_data_type> map_type; 167169691Skan typedef map_type::value_type entry_type; 168169691Skan typedef map_type::const_iterator const_iterator; 169169691Skan typedef map_type::const_reference const_reference; 170169691Skan 171169691Skan friend std::ostream& 172169691Skan operator<<(std::ostream&, const throw_allocator_base&); 173169691Skan 174169691Skan static entry_type 175169691Skan make_entry(void*, size_t); 176169691Skan 177169691Skan static void 178169691Skan print_to_string(std::string&); 179169691Skan 180169691Skan static void 181169691Skan print_to_string(std::string&, const_reference); 182169691Skan 183169691Skan static twister_rand_gen _S_g; 184169691Skan static map_type _S_map; 185169691Skan static double _S_throw_prob; 186169691Skan static size_t _S_label; 187169691Skan }; 188169691Skan 189169691Skan 190169691Skan template<typename T> 191169691Skan class throw_allocator : public throw_allocator_base 192169691Skan { 193169691Skan public: 194169691Skan typedef size_t size_type; 195169691Skan typedef ptrdiff_t difference_type; 196169691Skan typedef T value_type; 197169691Skan typedef value_type* pointer; 198169691Skan typedef const value_type* const_pointer; 199169691Skan typedef value_type& reference; 200169691Skan typedef const value_type& const_reference; 201169691Skan 202169691Skan 203169691Skan template<typename U> 204169691Skan struct rebind 205169691Skan { 206169691Skan typedef throw_allocator<U> other; 207169691Skan }; 208169691Skan 209169691Skan throw_allocator() throw() { } 210169691Skan 211169691Skan throw_allocator(const throw_allocator&) throw() { } 212169691Skan 213169691Skan template<typename U> 214169691Skan throw_allocator(const throw_allocator<U>&) throw() { } 215169691Skan 216169691Skan ~throw_allocator() throw() { } 217169691Skan 218169691Skan size_type 219169691Skan max_size() const throw() 220169691Skan { return std::allocator<value_type>().max_size(); } 221169691Skan 222169691Skan pointer 223169691Skan allocate(size_type num, std::allocator<void>::const_pointer hint = 0) 224169691Skan { 225169691Skan throw_conditionally(); 226169691Skan value_type* const a = std::allocator<value_type>().allocate(num, hint); 227169691Skan insert(a, sizeof(value_type) * num); 228169691Skan return a; 229169691Skan } 230169691Skan 231169691Skan void 232169691Skan construct(pointer p, const T& val) 233169691Skan { return std::allocator<value_type>().construct(p, val); } 234169691Skan 235169691Skan void 236169691Skan destroy(pointer p) 237169691Skan { std::allocator<value_type>().destroy(p); } 238169691Skan 239169691Skan void 240169691Skan deallocate(pointer p, size_type num) 241169691Skan { 242169691Skan erase(p, sizeof(value_type) * num); 243169691Skan std::allocator<value_type>().deallocate(p, num); 244169691Skan } 245169691Skan 246169691Skan void 247169691Skan check_allocated(pointer p, size_type num) 248169691Skan { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); } 249169691Skan 250169691Skan void 251169691Skan check_allocated(size_type label) 252169691Skan { throw_allocator_base::check_allocated(label); } 253169691Skan }; 254169691Skan 255169691Skan template<typename T> 256169691Skan inline bool 257169691Skan operator==(const throw_allocator<T>&, const throw_allocator<T>&) 258169691Skan { return true; } 259169691Skan 260169691Skan template<typename T> 261169691Skan inline bool 262169691Skan operator!=(const throw_allocator<T>&, const throw_allocator<T>&) 263169691Skan { return false; } 264169691Skan 265169691Skan std::ostream& 266169691Skan operator<<(std::ostream& os, const throw_allocator_base& alloc) 267169691Skan { 268169691Skan std::string error; 269169691Skan throw_allocator_base::print_to_string(error); 270169691Skan os << error; 271169691Skan return os; 272169691Skan } 273169691Skan 274169691Skan // XXX Should be in .cc. 275169691Skan twister_rand_gen:: 276169691Skan twister_rand_gen(unsigned int seed) : _M_generator(seed) { } 277169691Skan 278169691Skan void 279169691Skan twister_rand_gen:: 280169691Skan init(unsigned int seed) 281169691Skan { _M_generator.seed(seed); } 282169691Skan 283169691Skan double 284169691Skan twister_rand_gen:: 285169691Skan get_prob() 286169691Skan { 287169691Skan const double eng_min = _M_generator.min(); 288169691Skan const double eng_range = 289169691Skan static_cast<const double>(_M_generator.max() - eng_min); 290169691Skan 291169691Skan const double eng_res = 292169691Skan static_cast<const double>(_M_generator() - eng_min); 293169691Skan 294169691Skan const double ret = eng_res / eng_range; 295169691Skan _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1); 296169691Skan return ret; 297169691Skan } 298169691Skan 299169691Skan twister_rand_gen throw_allocator_base::_S_g; 300169691Skan 301169691Skan throw_allocator_base::map_type 302169691Skan throw_allocator_base::_S_map; 303169691Skan 304169691Skan double throw_allocator_base::_S_throw_prob; 305169691Skan 306169691Skan size_t throw_allocator_base::_S_label = 0; 307169691Skan 308169691Skan throw_allocator_base::entry_type 309169691Skan throw_allocator_base::make_entry(void* p, size_t size) 310169691Skan { return std::make_pair(p, alloc_data_type(_S_label, size)); } 311169691Skan 312169691Skan void 313169691Skan throw_allocator_base::init(unsigned long seed) 314169691Skan { _S_g.init(seed); } 315169691Skan 316169691Skan void 317169691Skan throw_allocator_base::set_throw_prob(double throw_prob) 318169691Skan { _S_throw_prob = throw_prob; } 319169691Skan 320169691Skan double 321169691Skan throw_allocator_base::get_throw_prob() 322169691Skan { return _S_throw_prob; } 323169691Skan 324169691Skan void 325169691Skan throw_allocator_base::set_label(size_t l) 326169691Skan { _S_label = l; } 327169691Skan 328169691Skan void 329169691Skan throw_allocator_base::insert(void* p, size_t size) 330169691Skan { 331169691Skan const_iterator found_it = _S_map.find(p); 332169691Skan if (found_it != _S_map.end()) 333169691Skan { 334169691Skan std::string error("throw_allocator_base::insert"); 335169691Skan error += "double insert!"; 336169691Skan error += '\n'; 337169691Skan print_to_string(error, make_entry(p, size)); 338169691Skan print_to_string(error, *found_it); 339171827Skan std::__throw_logic_error(error.c_str()); 340169691Skan } 341169691Skan _S_map.insert(make_entry(p, size)); 342169691Skan } 343169691Skan 344169691Skan bool 345169691Skan throw_allocator_base::empty() 346169691Skan { return _S_map.empty(); } 347169691Skan 348169691Skan void 349169691Skan throw_allocator_base::erase(void* p, size_t size) 350169691Skan { 351169691Skan check_allocated(p, size); 352169691Skan _S_map.erase(p); 353169691Skan } 354169691Skan 355169691Skan void 356169691Skan throw_allocator_base::check_allocated(void* p, size_t size) 357169691Skan { 358169691Skan const_iterator found_it = _S_map.find(p); 359169691Skan if (found_it == _S_map.end()) 360169691Skan { 361169691Skan std::string error("throw_allocator_base::check_allocated by value "); 362169691Skan error += "null erase!"; 363169691Skan error += '\n'; 364169691Skan print_to_string(error, make_entry(p, size)); 365171827Skan std::__throw_logic_error(error.c_str()); 366169691Skan } 367169691Skan 368169691Skan if (found_it->second.second != size) 369169691Skan { 370169691Skan std::string error("throw_allocator_base::check_allocated by value "); 371169691Skan error += "wrong-size erase!"; 372169691Skan error += '\n'; 373169691Skan print_to_string(error, make_entry(p, size)); 374169691Skan print_to_string(error, *found_it); 375171827Skan std::__throw_logic_error(error.c_str()); 376169691Skan } 377169691Skan } 378169691Skan 379169691Skan void 380169691Skan throw_allocator_base::check_allocated(size_t label) 381169691Skan { 382169691Skan std::string found; 383169691Skan const_iterator it = _S_map.begin(); 384169691Skan while (it != _S_map.end()) 385169691Skan { 386169691Skan if (it->second.first == label) 387169691Skan print_to_string(found, *it); 388169691Skan ++it; 389169691Skan } 390169691Skan 391169691Skan if (!found.empty()) 392169691Skan { 393169691Skan std::string error("throw_allocator_base::check_allocated by label "); 394169691Skan error += '\n'; 395169691Skan error += found; 396171827Skan std::__throw_logic_error(error.c_str()); 397169691Skan } 398169691Skan } 399169691Skan 400169691Skan void 401169691Skan throw_allocator_base::throw_conditionally() 402169691Skan { 403169691Skan if (_S_g.get_prob() < _S_throw_prob) 404171827Skan __throw_forced_exception_error(); 405169691Skan } 406169691Skan 407169691Skan void 408169691Skan throw_allocator_base::print_to_string(std::string& s) 409169691Skan { 410169691Skan const_iterator begin = throw_allocator_base::_S_map.begin(); 411169691Skan const_iterator end = throw_allocator_base::_S_map.end(); 412169691Skan for (; begin != end; ++begin) 413169691Skan print_to_string(s, *begin); 414169691Skan } 415169691Skan 416169691Skan void 417169691Skan throw_allocator_base::print_to_string(std::string& s, const_reference ref) 418169691Skan { 419169691Skan char buf[40]; 420169691Skan const char tab('\t'); 421169691Skan s += "address: "; 422169691Skan sprintf(buf, "%p", ref.first); 423169691Skan s += buf; 424169691Skan s += tab; 425169691Skan s += "label: "; 426259694Spfg sprintf(buf, "%lu", ref.second.first); 427169691Skan s += buf; 428169691Skan s += tab; 429169691Skan s += "size: "; 430259694Spfg sprintf(buf, "%lu", ref.second.second); 431169691Skan s += buf; 432169691Skan s += '\n'; 433169691Skan } 434169691Skan 435169691Skan_GLIBCXX_END_NAMESPACE 436169691Skan 437169691Skan#endif 438