libstdc++-v3/include/bits/stl_alloc.h

   1 // Allocators -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  * Copyright (c) 1996-1997
  32  * Silicon Graphics Computer Systems, Inc.
  33  *
  34  * Permission to use, copy, modify, distribute and sell this software
  35  * and its documentation for any purpose is hereby granted without fee,
  36  * provided that the above copyright notice appear in all copies and
  37  * that both that copyright notice and this permission notice appear
  38  * in supporting documentation.  Silicon Graphics makes no
  39  * representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied warranty.
  41  */
  42
  43 /** @file stl_alloc.h
  44  *  This is an internal header file, included by other library headers.
  45  *  You should not attempt to use it directly.
  46  */
  47
  48 #ifndef __GLIBCPP_INTERNAL_ALLOC_H
  49 #define __GLIBCPP_INTERNAL_ALLOC_H
  50
  51 /**
  52  *  @defgroup Allocators Memory Allocators
  53  *  @if maint
  54  *  stl_alloc.h implements some node allocators.  These are NOT the same as
  55  *  allocators in the C++ standard, nor in the original H-P STL.  They do not
  56  *  encapsulate different pointer types; we assume that there is only one
  57  *  pointer type.  The C++ standard allocators are intended to allocate
  58  *  individual objects, not pools or arenas.
  59  *
  60  *  In this file allocators are of two different styles:  "standard" and
  61  *  "SGI" (quotes included).  "Standard" allocators conform to 20.4.  "SGI"
  62  *  allocators differ in AT LEAST the following ways (add to this list as you
  63  *  discover them):
  64  *
  65  *   - "Standard" allocate() takes two parameters (n_count,hint=0) but "SGI"
  66  *     allocate() takes one paramter (n_size).
  67  *   - Likewise, "standard" deallocate()'s argument is a count, but in "SGI"
  68  *     is a byte size.
  69  *   - max_size(), construct(), and destroy() are missing in "SGI" allocators.
  70  *   - reallocate(p,oldsz,newsz) is added in "SGI", and behaves as
  71  *     if p=realloc(p,newsz).
  72  *
  73  *  "SGI" allocators may be wrapped in __allocator to convert the interface
  74  *  into a "standard" one.
  75  *  @endif
  76  *
  77  *  The canonical description of these classes is in docs/html/ext/howto.html
  78  *  or online at http://gcc.gnu.org/onlinedocs/libstdc++/ext/howto.html#3
  79 */
  80
  81 #include <cstddef>
  82 #include <cstdlib>
  83 #include <cstring>
  84 #include <cassert>
  85 #include <bits/functexcept.h>   // For __throw_bad_alloc
  86 #include <bits/stl_threads.h>
  87
  88 #include <bits/atomicity.h>
  89
  90 namespace std
  91 {
  92   /**
  93    *  @if maint
  94    *  A new-based allocator, as required by the standard.  Allocation and
  95    *  deallocation forward to global new and delete.  "SGI" style, minus
  96    *  reallocate().
  97    *  @endif
  98    *  (See @link Allocators allocators info @endlink for more.)
  99    */
 100   class __new_alloc
 101   {
 102   public:
 103     static void*
 104     allocate(size_t __n)
 105     { return ::operator new(__n); }
 106
 107     static void
 108     deallocate(void* __p, size_t)
 109     { ::operator delete(__p); }
 110   };
 111
 112
 113   /**
 114    *  @if maint
 115    *  A malloc-based allocator.  Typically slower than the
 116    *  __pool_alloc (below).  Typically thread-safe and more
 117    *  storage efficient.  The template argument is unused and is only present
 118    *  to permit multiple instantiations (but see __pool_alloc
 119    *  for caveats).  "SGI" style, plus __set_malloc_handler for OOM conditions.
 120    *  @endif
 121    *  (See @link Allocators allocators info @endlink for more.)
 122    */
 123   template<int __inst>
 124     class __malloc_alloc
 125     {
 126     private:
 127       static void* _S_oom_malloc(size_t);
 128       static void (* __malloc_alloc_oom_handler)();
 129
 130     public:
 131       static void*
 132       allocate(size_t __n)
 133       {
 134         void* __result = malloc(__n);
 135         if (__builtin_expect(__result == 0, 0))
 136           __result = _S_oom_malloc(__n);
 137         return __result;
 138       }
 139
 140       static void
 141       deallocate(void* __p, size_t /* __n */)
 142       { free(__p); }
 143
 144       static void (* __set_malloc_handler(void (*__f)()))()
 145       {
 146         void (* __old)() = __malloc_alloc_oom_handler;
 147         __malloc_alloc_oom_handler = __f;
 148         return __old;
 149       }
 150     };
 151
 152   // malloc_alloc out-of-memory handling
 153   template<int __inst>
 154     void (* __malloc_alloc<__inst>::__malloc_alloc_oom_handler)() = 0;
 155
 156   template<int __inst>
 157     void*
 158     __malloc_alloc<__inst>::
 159     _S_oom_malloc(size_t __n)
 160     {
 161       void (* __my_malloc_handler)();
 162       void* __result;
 163
 164       for (;;)
 165         {
 166           __my_malloc_handler = __malloc_alloc_oom_handler;
 167           if (__builtin_expect(__my_malloc_handler == 0, 0))
 168             __throw_bad_alloc();
 169           (*__my_malloc_handler)();
 170           __result = malloc(__n);
 171           if (__result)
 172             return __result;
 173         }
 174     }
 175
 176   // Should not be referenced within the library anymore.
 177   typedef __new_alloc                 __mem_interface;
 178
 179   /**
 180    *  @if maint
 181    *  This is used primarily (only?) in _Alloc_traits and other places to
 182    *  help provide the _Alloc_type typedef.  All it does is forward the
 183    *  requests after some minimal checking.
 184    *
 185    *  This is neither "standard"-conforming nor "SGI".  The _Alloc parameter
 186    *  must be "SGI" style.
 187    *  @endif
 188    *  (See @link Allocators allocators info @endlink for more.)
 189    */
 190   template<typename _Tp, typename _Alloc>
 191     class __simple_alloc
 192     {
 193     public:
 194       static _Tp*
 195       allocate(size_t __n)
 196       {
 197         _Tp* __ret = 0;
 198         if (__n)
 199           __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
 200         return __ret;
 201       }
 202
 203       static _Tp*
 204       allocate()
 205       { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
 206
 207       static void
 208       deallocate(_Tp* __p, size_t __n)
 209       { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
 210
 211       static void
 212       deallocate(_Tp* __p)
 213       { _Alloc::deallocate(__p, sizeof (_Tp)); }
 214     };
 215
 216
 217   /**
 218    *  @if maint
 219    *  An adaptor for an underlying allocator (_Alloc) to check the size
 220    *  arguments for debugging.  Errors are reported using assert; these
 221    *  checks can be disabled via NDEBUG, but the space penalty is still
 222    *  paid, therefore it is far better to just use the underlying allocator
 223    *  by itelf when no checking is desired.
 224    *
 225    *  "There is some evidence that this can confuse Purify." - SGI comment
 226    *
 227    *  This adaptor is "SGI" style.  The _Alloc parameter must also be "SGI".
 228    *  @endif
 229    *  (See @link Allocators allocators info @endlink for more.)
 230    */
 231   template<typename _Alloc>
 232     class __debug_alloc
 233     {
 234     private:
 235       // Size of space used to store size.  Note that this must be
 236       // large enough to preserve alignment.
 237       enum {_S_extra = 8};
 238
 239     public:
 240       static void*
 241       allocate(size_t __n)
 242       {
 243         char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
 244         *(size_t*)__result = __n;
 245         return __result + (int) _S_extra;
 246       }
 247
 248       static void
 249       deallocate(void* __p, size_t __n)
 250       {
 251         char* __real_p = (char*)__p - (int) _S_extra;
 252         assert(*(size_t*)__real_p == __n);
 253         _Alloc::deallocate(__real_p, __n + (int) _S_extra);
 254       }
 255     };
 256
 257
 258   /**
 259    *  @if maint
 260    *  Default node allocator.  "SGI" style.  Uses various allocators to
 261    *  fulfill underlying requests (and makes as few requests as possible
 262    *  when in default high-speed pool mode).
 263    *
 264    *  Important implementation properties:
 265    *  0. If globally mandated, then allocate objects from __new_alloc
 266    *  1. If the clients request an object of size > _MAX_BYTES, the resulting
 267    *     object will be obtained directly from __new_alloc
 268    *  2. In all other cases, we allocate an object of size exactly
 269    *     _S_round_up(requested_size).  Thus the client has enough size
 270    *     information that we can return the object to the proper free list
 271    *     without permanently losing part of the object.
 272    *
 273    *  The first template parameter specifies whether more than one thread may
 274    *  use this allocator.  It is safe to allocate an object from one instance
 275    *  of a default_alloc and deallocate it with another one.  This effectively
 276    *  transfers its ownership to the second one.  This may have undesirable
 277    *  effects on reference locality.
 278    *
 279    *  The second parameter is unused and serves only to allow the creation of
 280    *  multiple default_alloc instances.  Note that containers built on different
 281    *  allocator instances have different types, limiting the utility of this
 282    *  approach.  If you do not wish to share the free lists with the main
 283    *  default_alloc instance, instantiate this with a non-zero __inst.
 284    *
 285    *  @endif
 286    *  (See @link Allocators allocators info @endlink for more.)
 287    */
 288   template<bool __threads, int __inst>
 289     class __pool_alloc
 290     {
 291     private:
 292       enum {_ALIGN = 8};
 293       enum {_MAX_BYTES = 128};
 294       enum {_NFREELISTS = _MAX_BYTES / _ALIGN};
 295
 296       union _Obj
 297       {
 298         union _Obj* _M_free_list_link;
 299         char        _M_client_data[1];    // The client sees this.
 300       };
 301
 302       static _Obj* volatile         _S_free_list[_NFREELISTS];
 303
 304       // Chunk allocation state.
 305       static char*                  _S_start_free;
 306       static char*                  _S_end_free;
 307       static size_t                 _S_heap_size;
 308
 309       static _STL_mutex_lock        _S_lock;
 310       static _Atomic_word           _S_force_new;
 311
 312       static size_t
 313       _S_round_up(size_t __bytes)
 314       { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
 315
 316       static size_t
 317       _S_freelist_index(size_t __bytes)
 318       { return (((__bytes) + (size_t)_ALIGN - 1)/(size_t)_ALIGN - 1); }
 319
 320       // Returns an object of size __n, and optionally adds to size __n
 321       // free list.
 322       static void*
 323       _S_refill(size_t __n);
 324
 325       // Allocates a chunk for nobjs of size size.  nobjs may be reduced
 326       // if it is inconvenient to allocate the requested number.
 327       static char*
 328       _S_chunk_alloc(size_t __size, int& __nobjs);
 329
 330       // It would be nice to use _STL_auto_lock here.  But we need a
 331       // test whether threads are in use.
 332       struct _Lock
 333       {
 334         _Lock() { if (__threads) _S_lock._M_acquire_lock(); }
 335         ~_Lock() { if (__threads) _S_lock._M_release_lock(); }
 336       } __attribute__ ((__unused__));
 337       friend struct _Lock;
 338
 339     public:
 340       // __n must be > 0
 341       static void*
 342       allocate(size_t __n)
 343       {
 344         void* __ret = 0;
 345
 346         // If there is a race through here, assume answer from getenv
 347         // will resolve in same direction.  Inspired by techniques
 348         // to efficiently support threading found in basic_string.h.
 349         if (_S_force_new == 0)
 350           {
 351             if (getenv("GLIBCPP_FORCE_NEW"))
 352               __atomic_add(&_S_force_new, 1);
 353             else
 354               __atomic_add(&_S_force_new, -1);
 355             // Trust but verify...
 356             assert(_S_force_new != 0);
 357           }
 358
 359         if ((__n > (size_t) _MAX_BYTES) || (_S_force_new > 0))
 360           __ret = __new_alloc::allocate(__n);
 361         else
 362           {
 363             _Obj* volatile* __my_free_list = _S_free_list
 364               + _S_freelist_index(__n);
 365             // Acquire the lock here with a constructor call.  This
 366             // ensures that it is released in exit or during stack
 367             // unwinding.
 368             _Lock __lock_instance;
 369             _Obj* __restrict__ __result = *__my_free_list;
 370             if (__builtin_expect(__result == 0, 0))
 371               __ret = _S_refill(_S_round_up(__n));
 372             else
 373               {
 374                 *__my_free_list = __result -> _M_free_list_link;
 375                 __ret = __result;
 376               }
 377             if (__builtin_expect(__ret == 0, 0))
 378               __throw_bad_alloc();
 379           }
 380         return __ret;
 381       }
 382
 383       // __p may not be 0
 384       static void
 385       deallocate(void* __p, size_t __n)
 386       {
 387         if ((__n > (size_t) _MAX_BYTES) || (_S_force_new > 0))
 388           __new_alloc::deallocate(__p, __n);
 389         else
 390           {
 391             _Obj* volatile*  __my_free_list = _S_free_list
 392               + _S_freelist_index(__n);
 393             _Obj* __q = (_Obj*)__p;
 394
 395             // Acquire the lock here with a constructor call.  This
 396             // ensures that it is released in exit or during stack
 397             // unwinding.
 398             _Lock __lock_instance;
 399             __q -> _M_free_list_link = *__my_free_list;
 400             *__my_free_list = __q;
 401           }
 402       }
 403     };
 404
 405   template<bool __threads, int __inst> _Atomic_word
 406   __pool_alloc<__threads, __inst>::_S_force_new = 0;
 407
 408   template<bool __threads, int __inst>
 409     inline bool
 410     operator==(const __pool_alloc<__threads,__inst>&,
 411                const __pool_alloc<__threads,__inst>&)
 412     { return true; }
 413
 414   template<bool __threads, int __inst>
 415     inline bool
 416     operator!=(const __pool_alloc<__threads,__inst>&,
 417                const __pool_alloc<__threads,__inst>&)
 418     { return false; }
 419
 420
 421   // We allocate memory in large chunks in order to avoid fragmenting the
 422   // heap too much.  We assume that __size is properly aligned.  We hold
 423   // the allocation lock.
 424   template<bool __threads, int __inst>
 425     char*
 426     __pool_alloc<__threads, __inst>::
 427     _S_chunk_alloc(size_t __size, int& __nobjs)
 428     {
 429       char* __result;
 430       size_t __total_bytes = __size * __nobjs;
 431       size_t __bytes_left = _S_end_free - _S_start_free;
 432
 433       if (__bytes_left >= __total_bytes)
 434         {
 435           __result = _S_start_free;
 436           _S_start_free += __total_bytes;
 437           return __result ;
 438         }
 439       else if (__bytes_left >= __size)
 440         {
 441           __nobjs = (int)(__bytes_left/__size);
 442           __total_bytes = __size * __nobjs;
 443           __result = _S_start_free;
 444           _S_start_free += __total_bytes;
 445           return __result;
 446         }
 447       else
 448         {
 449           size_t __bytes_to_get =
 450             2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
 451           // Try to make use of the left-over piece.
 452           if (__bytes_left > 0)
 453             {
 454               _Obj* volatile* __my_free_list =
 455                 _S_free_list + _S_freelist_index(__bytes_left);
 456
 457               ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
 458               *__my_free_list = (_Obj*)_S_start_free;
 459             }
 460           _S_start_free = (char*) __new_alloc::allocate(__bytes_to_get);
 461           if (_S_start_free == 0)
 462             {
 463               size_t __i;
 464               _Obj* volatile* __my_free_list;
 465               _Obj* __p;
 466               // Try to make do with what we have.  That can't hurt.  We
 467               // do not try smaller requests, since that tends to result
 468               // in disaster on multi-process machines.
 469               __i = __size;
 470               for (; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN)
 471                 {
 472                   __my_free_list = _S_free_list + _S_freelist_index(__i);
 473                   __p = *__my_free_list;
 474                   if (__p != 0)
 475                     {
 476                       *__my_free_list = __p -> _M_free_list_link;
 477                       _S_start_free = (char*)__p;
 478                       _S_end_free = _S_start_free + __i;
 479                       return _S_chunk_alloc(__size, __nobjs);
 480                       // Any leftover piece will eventually make it to the
 481                       // right free list.
 482                     }
 483                 }
 484               _S_end_free = 0;        // In case of exception.
 485               _S_start_free = (char*)__new_alloc::allocate(__bytes_to_get);
 486               // This should either throw an exception or remedy the situation.
 487               // Thus we assume it succeeded.
 488             }
 489           _S_heap_size += __bytes_to_get;
 490           _S_end_free = _S_start_free + __bytes_to_get;
 491           return _S_chunk_alloc(__size, __nobjs);
 492         }
 493     }
 494
 495
 496   // Returns an object of size __n, and optionally adds to "size
 497   // __n"'s free list.  We assume that __n is properly aligned.  We
 498   // hold the allocation lock.
 499   template<bool __threads, int __inst>
 500     void*
 501     __pool_alloc<__threads, __inst>::_S_refill(size_t __n)
 502     {
 503       int __nobjs = 20;
 504       char* __chunk = _S_chunk_alloc(__n, __nobjs);
 505       _Obj* volatile* __my_free_list;
 506       _Obj* __result;
 507       _Obj* __current_obj;
 508       _Obj* __next_obj;
 509       int __i;
 510
 511       if (1 == __nobjs)
 512         return __chunk;
 513       __my_free_list = _S_free_list + _S_freelist_index(__n);
 514
 515       // Build free list in chunk.
 516       __result = (_Obj*)__chunk;
 517       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
 518       for (__i = 1; ; __i++)
 519         {
 520           __current_obj = __next_obj;
 521           __next_obj = (_Obj*)((char*)__next_obj + __n);
 522           if (__nobjs - 1 == __i)
 523             {
 524               __current_obj -> _M_free_list_link = 0;
 525               break;
 526             }
 527           else
 528             __current_obj -> _M_free_list_link = __next_obj;
 529         }
 530       return __result;
 531     }
 532
 533
 534   template<bool __threads, int __inst>
 535     _STL_mutex_lock
 536     __pool_alloc<__threads,__inst>::_S_lock __STL_MUTEX_INITIALIZER;
 537
 538   template<bool __threads, int __inst>
 539     char* __pool_alloc<__threads,__inst>::_S_start_free = 0;
 540
 541   template<bool __threads, int __inst>
 542     char* __pool_alloc<__threads,__inst>::_S_end_free = 0;
 543
 544   template<bool __threads, int __inst>
 545     size_t __pool_alloc<__threads,__inst>::_S_heap_size = 0;
 546
 547   template<bool __threads, int __inst>
 548     typename __pool_alloc<__threads,__inst>::_Obj* volatile
 549     __pool_alloc<__threads,__inst>::_S_free_list[_NFREELISTS];
 550
 551   typedef __pool_alloc<true,0>    __alloc;
 552   typedef __pool_alloc<false,0>   __single_client_alloc;
 553
 554
 555   /**
 556    *  @brief  The "standard" allocator, as per [20.4].
 557    *
 558    *  The private _Alloc is "SGI" style.  (See comments at the top
 559    *  of stl_alloc.h.)
 560    *
 561    *  The underlying allocator behaves as follows.
 562    *    - __pool_alloc is used via two typedefs
 563    *    - "__single_client_alloc" typedef does no locking for threads
 564    *    - "__alloc" typedef is threadsafe via the locks
 565    *    - __new_alloc is used for memory requests
 566    *
 567    *  (See @link Allocators allocators info @endlink for more.)
 568    */
 569   template<typename _Tp>
 570     class allocator
 571     {
 572       typedef __alloc _Alloc;          // The underlying allocator.
 573     public:
 574       typedef size_t     size_type;
 575       typedef ptrdiff_t  difference_type;
 576       typedef _Tp*       pointer;
 577       typedef const _Tp* const_pointer;
 578       typedef _Tp&       reference;
 579       typedef const _Tp& const_reference;
 580       typedef _Tp        value_type;
 581
 582       template<typename _Tp1>
 583         struct rebind
 584         { typedef allocator<_Tp1> other; };
 585
 586       allocator() throw() {}
 587       allocator(const allocator&) throw() {}
 588       template<typename _Tp1>
 589         allocator(const allocator<_Tp1>&) throw() {}
 590       ~allocator() throw() {}
 591
 592       pointer
 593       address(reference __x) const { return &__x; }
 594
 595       const_pointer
 596       address(const_reference __x) const { return &__x; }
 597
 598       // NB: __n is permitted to be 0.  The C++ standard says nothing
 599       // about what the return value is when __n == 0.
 600       _Tp*
 601       allocate(size_type __n, const void* = 0)
 602       {
 603         _Tp* __ret = 0;
 604         if (__n)
 605           {
 606             if (__n <= this->max_size())
 607               __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
 608             else
 609               __throw_bad_alloc();
 610           }
 611         return __ret;
 612       }
 613
 614       // __p is not permitted to be a null pointer.
 615       void
 616       deallocate(pointer __p, size_type __n)
 617       { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
 618
 619       size_type
 620       max_size() const throw() { return size_t(-1) / sizeof(_Tp); }
 621
 622       void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
 623       void destroy(pointer __p) { __p->~_Tp(); }
 624     };
 625
 626   template<>
 627     class allocator<void>
 628     {
 629     public:
 630       typedef size_t      size_type;
 631       typedef ptrdiff_t   difference_type;
 632       typedef void*       pointer;
 633       typedef const void* const_pointer;
 634       typedef void        value_type;
 635
 636       template<typename _Tp1>
 637         struct rebind
 638         { typedef allocator<_Tp1> other; };
 639     };
 640
 641
 642   template<typename _T1, typename _T2>
 643     inline bool
 644     operator==(const allocator<_T1>&, const allocator<_T2>&)
 645     { return true; }
 646
 647   template<typename _T1, typename _T2>
 648     inline bool
 649     operator!=(const allocator<_T1>&, const allocator<_T2>&)
 650     { return false; }
 651
 652
 653   /**
 654    *  @if maint
 655    *  Allocator adaptor to turn an "SGI" style allocator (e.g.,
 656    *  __alloc, __malloc_alloc) into a "standard" conforming
 657    *  allocator.  Note that this adaptor does *not* assume that all
 658    *  objects of the underlying alloc class are identical, nor does it
 659    *  assume that all of the underlying alloc's member functions are
 660    *  static member functions.  Note, also, that __allocator<_Tp,
 661    *  __alloc> is essentially the same thing as allocator<_Tp>.
 662    *  @endif
 663    *  (See @link Allocators allocators info @endlink for more.)
 664    */
 665   template<typename _Tp, typename _Alloc>
 666     struct __allocator
 667     {
 668       _Alloc __underlying_alloc;
 669
 670       typedef size_t    size_type;
 671       typedef ptrdiff_t difference_type;
 672       typedef _Tp*       pointer;
 673       typedef const _Tp* const_pointer;
 674       typedef _Tp&       reference;
 675       typedef const _Tp& const_reference;
 676       typedef _Tp        value_type;
 677
 678       template<typename _Tp1>
 679         struct rebind
 680         { typedef __allocator<_Tp1, _Alloc> other; };
 681
 682       __allocator() throw() {}
 683       __allocator(const __allocator& __a) throw()
 684       : __underlying_alloc(__a.__underlying_alloc) {}
 685
 686       template<typename _Tp1>
 687         __allocator(const __allocator<_Tp1, _Alloc>& __a) throw()
 688         : __underlying_alloc(__a.__underlying_alloc) {}
 689
 690       ~__allocator() throw() {}
 691
 692       pointer
 693       address(reference __x) const { return &__x; }
 694
 695       const_pointer
 696       address(const_reference __x) const { return &__x; }
 697
 698       // NB: __n is permitted to be 0.  The C++ standard says nothing
 699       // about what the return value is when __n == 0.
 700       _Tp*
 701       allocate(size_type __n, const void* = 0)
 702       {
 703         _Tp* __ret = 0;
 704         if (__n)
 705           __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
 706         return __ret;
 707       }
 708
 709       // __p is not permitted to be a null pointer.
 710       void
 711       deallocate(pointer __p, size_type __n)
 712       { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }
 713
 714       size_type
 715       max_size() const throw() { return size_t(-1) / sizeof(_Tp); }
 716
 717       void
 718       construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
 719
 720       void
 721       destroy(pointer __p) { __p->~_Tp(); }
 722     };
 723
 724   template<typename _Alloc>
 725     struct __allocator<void, _Alloc>
 726     {
 727       typedef size_t      size_type;
 728       typedef ptrdiff_t   difference_type;
 729       typedef void*       pointer;
 730       typedef const void* const_pointer;
 731       typedef void        value_type;
 732
 733       template<typename _Tp1>
 734         struct rebind
 735         { typedef __allocator<_Tp1, _Alloc> other; };
 736     };
 737
 738   template<typename _Tp, typename _Alloc>
 739     inline bool
 740     operator==(const __allocator<_Tp,_Alloc>& __a1,
 741                const __allocator<_Tp,_Alloc>& __a2)
 742     { return __a1.__underlying_alloc == __a2.__underlying_alloc; }
 743
 744   template<typename _Tp, typename _Alloc>
 745     inline bool
 746     operator!=(const __allocator<_Tp, _Alloc>& __a1,
 747                const __allocator<_Tp, _Alloc>& __a2)
 748     { return __a1.__underlying_alloc != __a2.__underlying_alloc; }
 749
 750
 751   //@{
 752   /** Comparison operators for all of the predifined SGI-style allocators.
 753    *  This ensures that __allocator<malloc_alloc> (for example) will work
 754    *  correctly.  As required, all allocators compare equal.
 755    */
 756   template<int inst>
 757     inline bool
 758     operator==(const __malloc_alloc<inst>&,
 759                const __malloc_alloc<inst>&)
 760     { return true; }
 761
 762   template<int __inst>
 763     inline bool
 764     operator!=(const __malloc_alloc<__inst>&,
 765                const __malloc_alloc<__inst>&)
 766     { return false; }
 767
 768   template<typename _Alloc>
 769     inline bool
 770     operator==(const __debug_alloc<_Alloc>&, const __debug_alloc<_Alloc>&)
 771     { return true; }
 772
 773   template<typename _Alloc>
 774     inline bool
 775     operator!=(const __debug_alloc<_Alloc>&, const __debug_alloc<_Alloc>&)
 776     { return false; }
 777   //@}
 778
 779
 780   /**
 781    *  @if maint
 782    *  Another allocator adaptor:  _Alloc_traits.  This serves two purposes.
 783    *  First, make it possible to write containers that can use either "SGI"
 784    *  style allocators or "standard" allocators.  Second, provide a mechanism
 785    *  so that containers can query whether or not the allocator has distinct
 786    *  instances.  If not, the container can avoid wasting a word of memory to
 787    *  store an empty object.  For examples of use, see stl_vector.h, etc, or
 788    *  any of the other classes derived from this one.
 789    *
 790    *  This adaptor uses partial specialization.  The general case of
 791    *  _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
 792    *  standard-conforming allocator, possibly with non-equal instances and
 793    *  non-static members.  (It still behaves correctly even if _Alloc has
 794    *  static member and if all instances are equal.  Refinements affect
 795    *  performance, not correctness.)
 796    *
 797    *  There are always two members:  allocator_type, which is a standard-
 798    *  conforming allocator type for allocating objects of type _Tp, and
 799    *  _S_instanceless, a static const member of type bool.  If
 800    *  _S_instanceless is true, this means that there is no difference
 801    *  between any two instances of type allocator_type.  Furthermore, if
 802    *  _S_instanceless is true, then _Alloc_traits has one additional
 803    *  member:  _Alloc_type.  This type encapsulates allocation and
 804    *  deallocation of objects of type _Tp through a static interface; it
 805    *  has two member functions, whose signatures are
 806    *
 807    *  -  static _Tp* allocate(size_t)
 808    *  -  static void deallocate(_Tp*, size_t)
 809    *
 810    *  The size_t parameters are "standard" style (see top of stl_alloc.h) in
 811    *  that they take counts, not sizes.
 812    *
 813    *  @endif
 814    *  (See @link Allocators allocators info @endlink for more.)
 815    */
 816   //@{
 817   // The fully general version.
 818   template<typename _Tp, typename _Allocator>
 819     struct _Alloc_traits
 820     {
 821       static const bool _S_instanceless = false;
 822       typedef typename _Allocator::template rebind<_Tp>::other allocator_type;
 823     };
 824
 825   template<typename _Tp, typename _Allocator>
 826     const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;
 827
 828   /// The version for the default allocator.
 829   template<typename _Tp, typename _Tp1>
 830     struct _Alloc_traits<_Tp, allocator<_Tp1> >
 831     {
 832       static const bool _S_instanceless = true;
 833       typedef __simple_alloc<_Tp, __alloc> _Alloc_type;
 834       typedef allocator<_Tp> allocator_type;
 835     };
 836   //@}
 837
 838   //@{
 839   /// Versions for the predefined "SGI" style allocators.
 840   template<typename _Tp, int __inst>
 841     struct _Alloc_traits<_Tp, __malloc_alloc<__inst> >
 842     {
 843       static const bool _S_instanceless = true;
 844       typedef __simple_alloc<_Tp, __malloc_alloc<__inst> > _Alloc_type;
 845       typedef __allocator<_Tp, __malloc_alloc<__inst> > allocator_type;
 846     };
 847
 848   template<typename _Tp, bool __threads, int __inst>
 849     struct _Alloc_traits<_Tp, __pool_alloc<__threads, __inst> >
 850     {
 851       static const bool _S_instanceless = true;
 852       typedef __simple_alloc<_Tp, __pool_alloc<__threads, __inst> >
 853       _Alloc_type;
 854       typedef __allocator<_Tp, __pool_alloc<__threads, __inst> >
 855       allocator_type;
 856     };
 857
 858   template<typename _Tp, typename _Alloc>
 859     struct _Alloc_traits<_Tp, __debug_alloc<_Alloc> >
 860     {
 861       static const bool _S_instanceless = true;
 862       typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type;
 863       typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type;
 864     };
 865   //@}
 866
 867   //@{
 868   /// Versions for the __allocator adaptor used with the predefined
 869   /// "SGI" style allocators.
 870   template<typename _Tp, typename _Tp1, int __inst>
 871     struct _Alloc_traits<_Tp,
 872                          __allocator<_Tp1, __malloc_alloc<__inst> > >
 873     {
 874       static const bool _S_instanceless = true;
 875       typedef __simple_alloc<_Tp, __malloc_alloc<__inst> > _Alloc_type;
 876       typedef __allocator<_Tp, __malloc_alloc<__inst> > allocator_type;
 877     };
 878
 879   template<typename _Tp, typename _Tp1, bool __thr, int __inst>
 880     struct _Alloc_traits<_Tp, __allocator<_Tp1, __pool_alloc<__thr, __inst> > >
 881     {
 882       static const bool _S_instanceless = true;
 883       typedef __simple_alloc<_Tp, __pool_alloc<__thr,__inst> >
 884       _Alloc_type;
 885       typedef __allocator<_Tp, __pool_alloc<__thr,__inst> >
 886       allocator_type;
 887     };
 888
 889   template<typename _Tp, typename _Tp1, typename _Alloc>
 890     struct _Alloc_traits<_Tp, __allocator<_Tp1, __debug_alloc<_Alloc> > >
 891     {
 892       static const bool _S_instanceless = true;
 893       typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type;
 894       typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type;
 895     };
 896   //@}
 897
 898   // Inhibit implicit instantiations for required instantiations,
 899   // which are defined via explicit instantiations elsewhere.
 900   // NB: This syntax is a GNU extension.
 901   extern template class allocator<char>;
 902   extern template class allocator<wchar_t>;
 903   extern template class __pool_alloc<true,0>;
 904 } // namespace std
 905
 906 #endif