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