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