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

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