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