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