libstdc++-v3/bits/stl_alloc.h

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