libstdc++-v3/include/ext/throw_allocator.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /** @file ext/vstring.h
  43  *  This file is a GNU extension to the Standard C++ Library.
  44  *
  45  *  Contains an exception-throwing allocator, useful for testing
  46  *  exception safety. In addition, allocation addresses are stored and
  47  *  sanity checked.
  48  */
  49
  50 /**
  51  * @file throw_allocator.h
  52  */
  53
  54 #ifndef _THROW_ALLOCATOR_H
  55 #define _THROW_ALLOCATOR_H 1
  56
  57 #include <cmath>
  58 #include <map>
  59 #include <set>
  60 #include <string>
  61 #include <ostream>
  62 #include <stdexcept>
  63 #include <utility>
  64 #include <tr1/random>
  65
  66 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  67
  68   class twister_rand_gen
  69   {
  70   public:
  71     twister_rand_gen(unsigned int seed =
  72                      static_cast<unsigned int>(std::time(0)));
  73
  74     void
  75     init(unsigned int);
  76
  77     double
  78     get_prob();
  79
  80   private:
  81     std::tr1::mt19937 _M_generator;
  82   };
  83
  84
  85   struct forced_exception_error : public std::exception
  86   { };
  87
  88   class throw_allocator_base
  89   {
  90   public:
  91     void
  92     init(unsigned long seed);
  93
  94     static void
  95     set_throw_prob(double throw_prob);
  96
  97     static double
  98     get_throw_prob();
  99
 100     static void
 101     set_label(size_t l);
 102
 103     static bool
 104     empty();
 105
 106     struct group_throw_prob_adjustor
 107     {
 108       group_throw_prob_adjustor(size_t size)
 109       : _M_throw_prob_orig(_S_throw_prob)
 110       {
 111         _S_throw_prob =
 112           1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
 113       }
 114
 115       ~group_throw_prob_adjustor()
 116       { _S_throw_prob = _M_throw_prob_orig; }
 117
 118     private:
 119       const double _M_throw_prob_orig;
 120     };
 121
 122     struct zero_throw_prob_adjustor
 123     {
 124       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
 125       { _S_throw_prob = 0; }
 126
 127       ~zero_throw_prob_adjustor()
 128       { _S_throw_prob = _M_throw_prob_orig; }
 129
 130     private:
 131       const double _M_throw_prob_orig;
 132     };
 133
 134   protected:
 135     static void
 136     insert(void*, size_t);
 137
 138     static void
 139     erase(void*, size_t);
 140
 141     static void
 142     throw_conditionally();
 143
 144     // See if a particular address and size has been allocated by this
 145     // allocator.
 146     static void
 147     check_allocated(void*, size_t);
 148
 149     // See if a given label has been allocated by this allocator.
 150     static void
 151     check_allocated(size_t);
 152
 153   private:
 154     typedef std::pair<size_t, size_t>           alloc_data_type;
 155     typedef std::map<void*, alloc_data_type>    map_type;
 156     typedef map_type::value_type                entry_type;
 157     typedef map_type::const_iterator            const_iterator;
 158     typedef map_type::const_reference           const_reference;
 159
 160     friend std::ostream&
 161     operator<<(std::ostream&, const throw_allocator_base&);
 162
 163     static entry_type
 164     make_entry(void*, size_t);
 165
 166     static void
 167     print_to_string(std::string&);
 168
 169     static void
 170     print_to_string(std::string&, const_reference);
 171
 172     static twister_rand_gen     _S_g;
 173     static map_type             _S_map;
 174     static double               _S_throw_prob;
 175     static size_t               _S_label;
 176   };
 177
 178
 179   template<typename T>
 180     class throw_allocator : public throw_allocator_base
 181     {
 182     public:
 183       typedef size_t                            size_type;
 184       typedef ptrdiff_t                         difference_type;
 185       typedef T                                 value_type;
 186       typedef value_type*                       pointer;
 187       typedef const value_type*                 const_pointer;
 188       typedef value_type&                       reference;
 189       typedef const value_type&                 const_reference;
 190
 191
 192       template<typename U>
 193       struct rebind
 194       {
 195         typedef throw_allocator<U> other;
 196       };
 197
 198       throw_allocator() throw() { }
 199
 200       throw_allocator(const throw_allocator&) throw() { }
 201
 202       template<typename U>
 203       throw_allocator(const throw_allocator<U>&) throw() { }
 204
 205       ~throw_allocator() throw() { }
 206
 207       size_type
 208       max_size() const throw()
 209       { return std::allocator<value_type>().max_size(); }
 210
 211       pointer
 212       allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
 213       {
 214         throw_conditionally();
 215         value_type* const a = std::allocator<value_type>().allocate(num, hint);
 216         insert(a, sizeof(value_type) * num);
 217         return a;
 218       }
 219
 220       void
 221       construct(pointer p, const T& val)
 222       { return std::allocator<value_type>().construct(p, val); }
 223
 224       void
 225       destroy(pointer p)
 226       { std::allocator<value_type>().destroy(p); }
 227
 228       void
 229       deallocate(pointer p, size_type num)
 230       {
 231         erase(p, sizeof(value_type) * num);
 232         std::allocator<value_type>().deallocate(p, num);
 233       }
 234
 235       void
 236       check_allocated(pointer p, size_type num)
 237       { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
 238
 239       void
 240       check_allocated(size_type label)
 241       { throw_allocator_base::check_allocated(label); }
 242     };
 243
 244   template<typename T>
 245     inline bool
 246     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
 247     { return true; }
 248
 249   template<typename T>
 250     inline bool
 251     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
 252     { return false; }
 253
 254   std::ostream&
 255   operator<<(std::ostream& os, const throw_allocator_base& alloc)
 256   {
 257     std::string error;
 258     throw_allocator_base::print_to_string(error);
 259     os << error;
 260     return os;
 261   }
 262
 263   // XXX Should be in .cc.
 264   twister_rand_gen::
 265   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
 266
 267   void
 268   twister_rand_gen::
 269   init(unsigned int seed)
 270   { _M_generator.seed(seed); }
 271
 272   double
 273   twister_rand_gen::
 274   get_prob()
 275   {
 276     const double eng_min = _M_generator.min();
 277     const double eng_range =
 278       static_cast<const double>(_M_generator.max() - eng_min);
 279
 280     const double eng_res =
 281       static_cast<const double>(_M_generator() - eng_min);
 282
 283     const double ret = eng_res / eng_range;
 284     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
 285     return ret;
 286   }
 287
 288   twister_rand_gen throw_allocator_base::_S_g;
 289
 290   throw_allocator_base::map_type
 291   throw_allocator_base::_S_map;
 292
 293   double throw_allocator_base::_S_throw_prob;
 294
 295   size_t throw_allocator_base::_S_label = 0;
 296
 297   throw_allocator_base::entry_type
 298   throw_allocator_base::make_entry(void* p, size_t size)
 299   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
 300
 301   void
 302   throw_allocator_base::init(unsigned long seed)
 303   { _S_g.init(seed); }
 304
 305   void
 306   throw_allocator_base::set_throw_prob(double throw_prob)
 307   { _S_throw_prob = throw_prob; }
 308
 309   double
 310   throw_allocator_base::get_throw_prob()
 311   { return _S_throw_prob; }
 312
 313   void
 314   throw_allocator_base::set_label(size_t l)
 315   { _S_label = l; }
 316
 317   void
 318   throw_allocator_base::insert(void* p, size_t size)
 319   {
 320     const_iterator found_it = _S_map.find(p);
 321     if (found_it != _S_map.end())
 322       {
 323         std::string error("throw_allocator_base::insert");
 324         error += "double insert!";
 325         error += '\n';
 326         print_to_string(error, make_entry(p, size));
 327         print_to_string(error, *found_it);
 328         throw std::logic_error(error);
 329       }
 330     _S_map.insert(make_entry(p, size));
 331   }
 332
 333   bool
 334   throw_allocator_base::empty()
 335   { return _S_map.empty(); }
 336
 337   void
 338   throw_allocator_base::erase(void* p, size_t size)
 339   {
 340     check_allocated(p, size);
 341     _S_map.erase(p);
 342   }
 343
 344   void
 345   throw_allocator_base::check_allocated(void* p, size_t size)
 346   {
 347     const_iterator found_it = _S_map.find(p);
 348     if (found_it == _S_map.end())
 349       {
 350         std::string error("throw_allocator_base::check_allocated by value ");
 351         error += "null erase!";
 352         error += '\n';
 353         print_to_string(error, make_entry(p, size));
 354         throw std::logic_error(error);
 355       }
 356
 357     if (found_it->second.second != size)
 358       {
 359         std::string error("throw_allocator_base::check_allocated by value ");
 360         error += "wrong-size erase!";
 361         error += '\n';
 362         print_to_string(error, make_entry(p, size));
 363         print_to_string(error, *found_it);
 364         throw std::logic_error(error);
 365       }
 366   }
 367
 368   void
 369   throw_allocator_base::check_allocated(size_t label)
 370   {
 371     std::string found;
 372     const_iterator it = _S_map.begin();
 373     while (it != _S_map.end())
 374       {
 375         if (it->second.first == label)
 376           print_to_string(found, *it);
 377         ++it;
 378       }
 379
 380     if (!found.empty())
 381       {
 382         std::string error("throw_allocator_base::check_allocated by label ");
 383         error += '\n';
 384         error += found;
 385         throw std::logic_error(error);
 386       }
 387   }
 388
 389   void
 390   throw_allocator_base::throw_conditionally()
 391   {
 392     if (_S_g.get_prob() < _S_throw_prob)
 393       throw forced_exception_error();
 394   }
 395
 396   void
 397   throw_allocator_base::print_to_string(std::string& s)
 398   {
 399     const_iterator begin = throw_allocator_base::_S_map.begin();
 400     const_iterator end = throw_allocator_base::_S_map.end();
 401     for (; begin != end; ++begin)
 402       print_to_string(s, *begin);
 403   }
 404
 405   void
 406   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
 407   {
 408     char buf[40];
 409     const char tab('\t');
 410     s += "address: ";
 411     sprintf(buf, "%p", ref.first);
 412     s += buf;
 413     s += tab;
 414     s += "label: ";
 415     sprintf(buf, "%u", ref.second.first);
 416     s += buf;
 417     s += tab;
 418     s += "size: ";
 419     sprintf(buf, "%u", ref.second.second);
 420     s += buf;
 421     s += '\n';
 422   }
 423
 424 _GLIBCXX_END_NAMESPACE
 425
 426 #endif