contrib/libstdc++/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 #include <bits/functexcept.h>
  66
  67 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  68
  69   class twister_rand_gen
  70   {
  71   public:
  72     twister_rand_gen(unsigned int seed =
  73                      static_cast<unsigned int>(std::time(0)));
  74
  75     void
  76     init(unsigned int);
  77
  78     double
  79     get_prob();
  80
  81   private:
  82     std::tr1::mt19937 _M_generator;
  83   };
  84
  85   struct forced_exception_error : public std::exception
  86   { };
  87
  88   // Substitute for concurrence_error object in the case of -fno-exceptions.
  89   inline void
  90   __throw_forced_exception_error()
  91   {
  92 #if __EXCEPTIONS
  93     throw forced_exception_error();
  94 #else
  95     __builtin_abort();
  96 #endif
  97   }
  98
  99   class throw_allocator_base
 100   {
 101   public:
 102     void
 103     init(unsigned long seed);
 104
 105     static void
 106     set_throw_prob(double throw_prob);
 107
 108     static double
 109     get_throw_prob();
 110
 111     static void
 112     set_label(size_t l);
 113
 114     static bool
 115     empty();
 116
 117     struct group_throw_prob_adjustor
 118     {
 119       group_throw_prob_adjustor(size_t size)
 120       : _M_throw_prob_orig(_S_throw_prob)
 121       {
 122         _S_throw_prob =
 123           1 - ::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
 124       }
 125
 126       ~group_throw_prob_adjustor()
 127       { _S_throw_prob = _M_throw_prob_orig; }
 128
 129     private:
 130       const double _M_throw_prob_orig;
 131     };
 132
 133     struct zero_throw_prob_adjustor
 134     {
 135       zero_throw_prob_adjustor() : _M_throw_prob_orig(_S_throw_prob)
 136       { _S_throw_prob = 0; }
 137
 138       ~zero_throw_prob_adjustor()
 139       { _S_throw_prob = _M_throw_prob_orig; }
 140
 141     private:
 142       const double _M_throw_prob_orig;
 143     };
 144
 145   protected:
 146     static void
 147     insert(void*, size_t);
 148
 149     static void
 150     erase(void*, size_t);
 151
 152     static void
 153     throw_conditionally();
 154
 155     // See if a particular address and size has been allocated by this
 156     // allocator.
 157     static void
 158     check_allocated(void*, size_t);
 159
 160     // See if a given label has been allocated by this allocator.
 161     static void
 162     check_allocated(size_t);
 163
 164   private:
 165     typedef std::pair<size_t, size_t>           alloc_data_type;
 166     typedef std::map<void*, alloc_data_type>    map_type;
 167     typedef map_type::value_type                entry_type;
 168     typedef map_type::const_iterator            const_iterator;
 169     typedef map_type::const_reference           const_reference;
 170
 171     friend std::ostream&
 172     operator<<(std::ostream&, const throw_allocator_base&);
 173
 174     static entry_type
 175     make_entry(void*, size_t);
 176
 177     static void
 178     print_to_string(std::string&);
 179
 180     static void
 181     print_to_string(std::string&, const_reference);
 182
 183     static twister_rand_gen     _S_g;
 184     static map_type             _S_map;
 185     static double               _S_throw_prob;
 186     static size_t               _S_label;
 187   };
 188
 189
 190   template<typename T>
 191     class throw_allocator : public throw_allocator_base
 192     {
 193     public:
 194       typedef size_t                            size_type;
 195       typedef ptrdiff_t                         difference_type;
 196       typedef T                                 value_type;
 197       typedef value_type*                       pointer;
 198       typedef const value_type*                 const_pointer;
 199       typedef value_type&                       reference;
 200       typedef const value_type&                 const_reference;
 201
 202
 203       template<typename U>
 204       struct rebind
 205       {
 206         typedef throw_allocator<U> other;
 207       };
 208
 209       throw_allocator() throw() { }
 210
 211       throw_allocator(const throw_allocator&) throw() { }
 212
 213       template<typename U>
 214       throw_allocator(const throw_allocator<U>&) throw() { }
 215
 216       ~throw_allocator() throw() { }
 217
 218       size_type
 219       max_size() const throw()
 220       { return std::allocator<value_type>().max_size(); }
 221
 222       pointer
 223       allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
 224       {
 225         throw_conditionally();
 226         value_type* const a = std::allocator<value_type>().allocate(num, hint);
 227         insert(a, sizeof(value_type) * num);
 228         return a;
 229       }
 230
 231       void
 232       construct(pointer p, const T& val)
 233       { return std::allocator<value_type>().construct(p, val); }
 234
 235       void
 236       destroy(pointer p)
 237       { std::allocator<value_type>().destroy(p); }
 238
 239       void
 240       deallocate(pointer p, size_type num)
 241       {
 242         erase(p, sizeof(value_type) * num);
 243         std::allocator<value_type>().deallocate(p, num);
 244       }
 245
 246       void
 247       check_allocated(pointer p, size_type num)
 248       { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
 249
 250       void
 251       check_allocated(size_type label)
 252       { throw_allocator_base::check_allocated(label); }
 253     };
 254
 255   template<typename T>
 256     inline bool
 257     operator==(const throw_allocator<T>&, const throw_allocator<T>&)
 258     { return true; }
 259
 260   template<typename T>
 261     inline bool
 262     operator!=(const throw_allocator<T>&, const throw_allocator<T>&)
 263     { return false; }
 264
 265   std::ostream&
 266   operator<<(std::ostream& os, const throw_allocator_base& alloc)
 267   {
 268     std::string error;
 269     throw_allocator_base::print_to_string(error);
 270     os << error;
 271     return os;
 272   }
 273
 274   // XXX Should be in .cc.
 275   twister_rand_gen::
 276   twister_rand_gen(unsigned int seed) : _M_generator(seed)  { }
 277
 278   void
 279   twister_rand_gen::
 280   init(unsigned int seed)
 281   { _M_generator.seed(seed); }
 282
 283   double
 284   twister_rand_gen::
 285   get_prob()
 286   {
 287     const double eng_min = _M_generator.min();
 288     const double eng_range =
 289       static_cast<const double>(_M_generator.max() - eng_min);
 290
 291     const double eng_res =
 292       static_cast<const double>(_M_generator() - eng_min);
 293
 294     const double ret = eng_res / eng_range;
 295     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
 296     return ret;
 297   }
 298
 299   twister_rand_gen throw_allocator_base::_S_g;
 300
 301   throw_allocator_base::map_type
 302   throw_allocator_base::_S_map;
 303
 304   double throw_allocator_base::_S_throw_prob;
 305
 306   size_t throw_allocator_base::_S_label = 0;
 307
 308   throw_allocator_base::entry_type
 309   throw_allocator_base::make_entry(void* p, size_t size)
 310   { return std::make_pair(p, alloc_data_type(_S_label, size)); }
 311
 312   void
 313   throw_allocator_base::init(unsigned long seed)
 314   { _S_g.init(seed); }
 315
 316   void
 317   throw_allocator_base::set_throw_prob(double throw_prob)
 318   { _S_throw_prob = throw_prob; }
 319
 320   double
 321   throw_allocator_base::get_throw_prob()
 322   { return _S_throw_prob; }
 323
 324   void
 325   throw_allocator_base::set_label(size_t l)
 326   { _S_label = l; }
 327
 328   void
 329   throw_allocator_base::insert(void* p, size_t size)
 330   {
 331     const_iterator found_it = _S_map.find(p);
 332     if (found_it != _S_map.end())
 333       {
 334         std::string error("throw_allocator_base::insert");
 335         error += "double insert!";
 336         error += '\n';
 337         print_to_string(error, make_entry(p, size));
 338         print_to_string(error, *found_it);
 339         std::__throw_logic_error(error.c_str());
 340       }
 341     _S_map.insert(make_entry(p, size));
 342   }
 343
 344   bool
 345   throw_allocator_base::empty()
 346   { return _S_map.empty(); }
 347
 348   void
 349   throw_allocator_base::erase(void* p, size_t size)
 350   {
 351     check_allocated(p, size);
 352     _S_map.erase(p);
 353   }
 354
 355   void
 356   throw_allocator_base::check_allocated(void* p, size_t size)
 357   {
 358     const_iterator found_it = _S_map.find(p);
 359     if (found_it == _S_map.end())
 360       {
 361         std::string error("throw_allocator_base::check_allocated by value ");
 362         error += "null erase!";
 363         error += '\n';
 364         print_to_string(error, make_entry(p, size));
 365         std::__throw_logic_error(error.c_str());
 366       }
 367
 368     if (found_it->second.second != size)
 369       {
 370         std::string error("throw_allocator_base::check_allocated by value ");
 371         error += "wrong-size erase!";
 372         error += '\n';
 373         print_to_string(error, make_entry(p, size));
 374         print_to_string(error, *found_it);
 375         std::__throw_logic_error(error.c_str());
 376       }
 377   }
 378
 379   void
 380   throw_allocator_base::check_allocated(size_t label)
 381   {
 382     std::string found;
 383     const_iterator it = _S_map.begin();
 384     while (it != _S_map.end())
 385       {
 386         if (it->second.first == label)
 387           print_to_string(found, *it);
 388         ++it;
 389       }
 390
 391     if (!found.empty())
 392       {
 393         std::string error("throw_allocator_base::check_allocated by label ");
 394         error += '\n';
 395         error += found;
 396         std::__throw_logic_error(error.c_str());
 397       }
 398   }
 399
 400   void
 401   throw_allocator_base::throw_conditionally()
 402   {
 403     if (_S_g.get_prob() < _S_throw_prob)
 404       __throw_forced_exception_error();
 405   }
 406
 407   void
 408   throw_allocator_base::print_to_string(std::string& s)
 409   {
 410     const_iterator begin = throw_allocator_base::_S_map.begin();
 411     const_iterator end = throw_allocator_base::_S_map.end();
 412     for (; begin != end; ++begin)
 413       print_to_string(s, *begin);
 414   }
 415
 416   void
 417   throw_allocator_base::print_to_string(std::string& s, const_reference ref)
 418   {
 419     char buf[40];
 420     const char tab('\t');
 421     s += "address: ";
 422     sprintf(buf, "%p", ref.first);
 423     s += buf;
 424     s += tab;
 425     s += "label: ";
 426     sprintf(buf, "%u", ref.second.first);
 427     s += buf;
 428     s += tab;
 429     s += "size: ";
 430     sprintf(buf, "%u", ref.second.second);
 431     s += buf;
 432     s += '\n';
 433   }
 434
 435 _GLIBCXX_END_NAMESPACE
 436
 437 #endif