stl_alloc.h

Go to the documentation of this file.
00001 // Allocators -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  * Copyright (c) 1996-1997
00032  * Silicon Graphics Computer Systems, Inc.
00033  *
00034  * Permission to use, copy, modify, distribute and sell this software
00035  * and its documentation for any purpose is hereby granted without fee,
00036  * provided that the above copyright notice appear in all copies and
00037  * that both that copyright notice and this permission notice appear
00038  * in supporting documentation.  Silicon Graphics makes no
00039  * representations about the suitability of this software for any
00040  * purpose.  It is provided "as is" without express or implied warranty.
00041  */
00042 
00043 /** @file stl_alloc.h
00044  *  This is an internal header file, included by other library headers.
00045  *  You should not attempt to use it directly.
00046  */
00047 
00048 #ifndef __GLIBCPP_INTERNAL_ALLOC_H
00049 #define __GLIBCPP_INTERNAL_ALLOC_H
00050 
00051 /**
00052  *  @defgroup Allocators Memory Allocators
00053  *  @if maint
00054  *  stl_alloc.h implements some node allocators.  These are NOT the same as
00055  *  allocators in the C++ standard, nor in the original H-P STL.  They do not
00056  *  encapsulate different pointer types; we assume that there is only one
00057  *  pointer type.  The C++ standard allocators are intended to allocate
00058  *  individual objects, not pools or arenas.
00059  *
00060  *  In this file allocators are of two different styles:  "standard" and
00061  *  "SGI" (quotes included).  "Standard" allocators conform to 20.4.  "SGI"
00062  *  allocators differ in AT LEAST the following ways (add to this list as you
00063  *  discover them):
00064  *
00065  *   - "Standard" allocate() takes two parameters (n_count,hint=0) but "SGI"
00066  *     allocate() takes one paramter (n_size).
00067  *   - Likewise, "standard" deallocate()'s argument is a count, but in "SGI"
00068  *     is a byte size.
00069  *   - max_size(), construct(), and destroy() are missing in "SGI" allocators.
00070  *   - reallocate(p,oldsz,newsz) is added in "SGI", and behaves as
00071  *     if p=realloc(p,newsz).
00072  *
00073  *  "SGI" allocators may be wrapped in __allocator to convert the interface
00074  *  into a "standard" one.
00075  *  @endif
00076  *
00077  *  @note The @c reallocate member functions have been deprecated for 3.2
00078  *        and will be removed in 3.4.  You must define @c _GLIBCPP_DEPRECATED
00079  *        to make this visible in 3.2; see c++config.h.
00080  *
00081  *  The canonical description of these classes is in docs/html/ext/howto.html
00082  *  or online at http://gcc.gnu.org/onlinedocs/libstdc++/ext/howto.html#3
00083 */
00084 
00085 #include <cstddef>
00086 #include <cstdlib>
00087 #include <cstring>
00088 #include <bits/functexcept.h>   // For __throw_bad_alloc
00089 #include <bits/stl_threads.h>
00090 
00091 #include <bits/atomicity.h>
00092 
00093 namespace std
00094 {
00095   /**
00096    *  @if maint
00097    *  A new-based allocator, as required by the standard.  Allocation and
00098    *  deallocation forward to global new and delete.  "SGI" style, minus
00099    *  reallocate().
00100    *  @endif
00101    *  (See @link Allocators allocators info @endlink for more.)
00102    */
00103   class __new_alloc
00104   {
00105   public:
00106     static void*
00107     allocate(size_t __n)
00108     { return ::operator new(__n); }
00109 
00110     static void
00111     deallocate(void* __p, size_t)
00112     { ::operator delete(__p); }
00113   };
00114 
00115 
00116   /**
00117    *  @if maint
00118    *  A malloc-based allocator.  Typically slower than the
00119    *  __default_alloc_template (below).  Typically thread-safe and more
00120    *  storage efficient.  The template argument is unused and is only present
00121    *  to permit multiple instantiations (but see __default_alloc_template
00122    *  for caveats).  "SGI" style, plus __set_malloc_handler for OOM conditions.
00123    *  @endif
00124    *  (See @link Allocators allocators info @endlink for more.)
00125    */
00126   template<int __inst>
00127     class __malloc_alloc_template
00128     {
00129     private:
00130       static void* _S_oom_malloc(size_t);
00131       static void* _S_oom_realloc(void*, size_t);
00132       static void (* __malloc_alloc_oom_handler)();
00133 
00134     public:
00135       static void*
00136       allocate(size_t __n)
00137       {
00138         void* __result = malloc(__n);
00139         if (__builtin_expect(__result == 0, 0))
00140       __result = _S_oom_malloc(__n);
00141         return __result;
00142       }
00143 
00144       static void
00145       deallocate(void* __p, size_t /* __n */)
00146       { free(__p); }
00147 
00148       static void*
00149       reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
00150       {
00151         void* __result = realloc(__p, __new_sz);
00152         if (__builtin_expect(__result == 0, 0))
00153           __result = _S_oom_realloc(__p, __new_sz);
00154         return __result;
00155       }
00156 
00157       static void (* __set_malloc_handler(void (*__f)()))()
00158       {
00159         void (* __old)() = __malloc_alloc_oom_handler;
00160         __malloc_alloc_oom_handler = __f;
00161         return __old;
00162       }
00163     };
00164 
00165   // malloc_alloc out-of-memory handling
00166   template<int __inst>
00167     void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
00168 
00169   template<int __inst>
00170     void*
00171     __malloc_alloc_template<__inst>::
00172     _S_oom_malloc(size_t __n)
00173     {
00174       void (* __my_malloc_handler)();
00175       void* __result;
00176 
00177       for (;;)
00178         {
00179           __my_malloc_handler = __malloc_alloc_oom_handler;
00180           if (__builtin_expect(__my_malloc_handler == 0, 0))
00181             __throw_bad_alloc();
00182           (*__my_malloc_handler)();
00183           __result = malloc(__n);
00184           if (__result)
00185             return __result;
00186         }
00187     }
00188 
00189   template<int __inst>
00190     void*
00191     __malloc_alloc_template<__inst>::
00192     _S_oom_realloc(void* __p, size_t __n)
00193     {
00194       void (* __my_malloc_handler)();
00195       void* __result;
00196 
00197       for (;;)
00198         {
00199           __my_malloc_handler = __malloc_alloc_oom_handler;
00200           if (__builtin_expect(__my_malloc_handler == 0, 0))
00201             __throw_bad_alloc();
00202           (*__my_malloc_handler)();
00203           __result = realloc(__p, __n);
00204           if (__result)
00205             return __result;
00206         }
00207     }
00208 
00209   // Should not be referenced within the library anymore.
00210   typedef __new_alloc                 __mem_interface;
00211 
00212   /**
00213    *  @if maint
00214    *  This is used primarily (only?) in _Alloc_traits and other places to
00215    *  help provide the _Alloc_type typedef.  All it does is forward the
00216    *  requests after some minimal checking.
00217    *
00218    *  This is neither "standard"-conforming nor "SGI".  The _Alloc parameter
00219    *  must be "SGI" style.
00220    *  @endif
00221    *  (See @link Allocators allocators info @endlink for more.)
00222    */
00223   template<typename _Tp, typename _Alloc>
00224     class __simple_alloc
00225     {
00226     public:
00227       static _Tp*
00228       allocate(size_t __n)
00229       {
00230     _Tp* __ret = 0;
00231     if (__n)
00232       __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
00233     return __ret;
00234       }
00235   
00236       static _Tp*
00237       allocate()
00238       { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
00239   
00240       static void
00241       deallocate(_Tp* __p, size_t __n)
00242       { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
00243   
00244       static void
00245       deallocate(_Tp* __p)
00246       { _Alloc::deallocate(__p, sizeof (_Tp)); }
00247     };
00248 
00249 
00250   /**
00251    *  @if maint
00252    *  An adaptor for an underlying allocator (_Alloc) to check the size
00253    *  arguments for debugging.
00254    *
00255    *  "There is some evidence that this can confuse Purify." - SGI comment
00256    *
00257    *  This adaptor is "SGI" style.  The _Alloc parameter must also be "SGI".
00258    *  @endif
00259    *  (See @link Allocators allocators info @endlink for more.)
00260    */
00261   template<typename _Alloc>
00262     class __debug_alloc
00263     {
00264     private:
00265       // Size of space used to store size.  Note that this must be
00266       // large enough to preserve alignment.
00267       enum {_S_extra = 8};
00268 
00269     public:
00270       static void*
00271       allocate(size_t __n)
00272       {
00273         char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
00274         *(size_t*)__result = __n;
00275         return __result + (int) _S_extra;
00276       }
00277 
00278       static void
00279       deallocate(void* __p, size_t __n)
00280       {
00281         char* __real_p = (char*)__p - (int) _S_extra;
00282         if (*(size_t*)__real_p != __n)
00283       abort();
00284         _Alloc::deallocate(__real_p, __n + (int) _S_extra);
00285       }
00286 
00287       static void*
00288       reallocate(void* __p, size_t __old_sz, size_t __new_sz)
00289       {
00290         char* __real_p = (char*)__p - (int) _S_extra;
00291         if (*(size_t*)__real_p != __old_sz)
00292       abort();
00293         char* __result = (char*) _Alloc::reallocate(__real_p, 
00294                             __old_sz + (int) _S_extra,
00295                             __new_sz + (int) _S_extra);
00296         *(size_t*)__result = __new_sz;
00297         return __result + (int) _S_extra;
00298       }
00299     };
00300 
00301 
00302   /**
00303    *  @if maint
00304    *  Default node allocator.  "SGI" style.  Uses various allocators to
00305    *  fulfill underlying requests (and makes as few requests as possible
00306    *  when in default high-speed pool mode).
00307    *
00308    *  Important implementation properties:
00309    *  0. If globally mandated, then allocate objects from __new_alloc
00310    *  1. If the clients request an object of size > _MAX_BYTES, the resulting
00311    *     object will be obtained directly from __new_alloc
00312    *  2. In all other cases, we allocate an object of size exactly
00313    *     _S_round_up(requested_size).  Thus the client has enough size
00314    *     information that we can return the object to the proper free list
00315    *     without permanently losing part of the object.
00316    *
00317    *  The first template parameter specifies whether more than one thread may
00318    *  use this allocator.  It is safe to allocate an object from one instance
00319    *  of a default_alloc and deallocate it with another one.  This effectively
00320    *  transfers its ownership to the second one.  This may have undesirable
00321    *  effects on reference locality.
00322    *
00323    *  The second parameter is unused and serves only to allow the creation of
00324    *  multiple default_alloc instances.  Note that containers built on different
00325    *  allocator instances have different types, limiting the utility of this
00326    *  approach.  If you do not wish to share the free lists with the main
00327    *  default_alloc instance, instantiate this with a non-zero __inst.
00328    *
00329    *  @endif
00330    *  (See @link Allocators allocators info @endlink for more.)
00331    */
00332   template<bool __threads, int __inst>
00333     class __default_alloc_template
00334     {
00335     private:
00336       enum {_ALIGN = 8};
00337       enum {_MAX_BYTES = 128};
00338       enum {_NFREELISTS = _MAX_BYTES / _ALIGN};
00339 
00340       union _Obj
00341       {
00342         union _Obj* _M_free_list_link;
00343         char        _M_client_data[1];    // The client sees this.
00344       };
00345 
00346       static _Obj* volatile         _S_free_list[_NFREELISTS];
00347 
00348       // Chunk allocation state.
00349       static char*                  _S_start_free;
00350       static char*                  _S_end_free;
00351       static size_t                 _S_heap_size;
00352 
00353       static _STL_mutex_lock        _S_node_allocator_lock;
00354 
00355       static size_t
00356       _S_round_up(size_t __bytes)
00357       { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
00358 
00359       static size_t
00360       _S_freelist_index(size_t __bytes)
00361       { return (((__bytes) + (size_t)_ALIGN - 1)/(size_t)_ALIGN - 1); }
00362 
00363       // Returns an object of size __n, and optionally adds to size __n
00364       // free list.
00365       static void*
00366       _S_refill(size_t __n);
00367 
00368       // Allocates a chunk for nobjs of size size.  nobjs may be reduced
00369       // if it is inconvenient to allocate the requested number.
00370       static char*
00371       _S_chunk_alloc(size_t __size, int& __nobjs);
00372 
00373       // It would be nice to use _STL_auto_lock here.  But we need a
00374       // test whether threads are in use.
00375       struct _Lock
00376       {
00377         _Lock() { if (__threads) _S_node_allocator_lock._M_acquire_lock(); }
00378         ~_Lock() { if (__threads) _S_node_allocator_lock._M_release_lock(); }
00379       } __attribute__ ((__unused__));
00380       friend struct _Lock;
00381 
00382       static _Atomic_word _S_force_new;
00383 
00384     public:
00385       // __n must be > 0
00386       static void*
00387       allocate(size_t __n)
00388       {
00389     void* __ret = 0;
00390 
00391     // If there is a race through here, assume answer from getenv
00392     // will resolve in same direction.  Inspired by techniques
00393     // to efficiently support threading found in basic_string.h.
00394     if (_S_force_new == 0)
00395       {
00396         if (getenv("GLIBCPP_FORCE_NEW"))
00397           __atomic_add(&_S_force_new, 1);
00398         else
00399           __atomic_add(&_S_force_new, -1);
00400       }
00401 
00402     if ((__n > (size_t) _MAX_BYTES) || (_S_force_new > 0))
00403       __ret = __new_alloc::allocate(__n);
00404     else
00405       {
00406         _Obj* volatile* __my_free_list = _S_free_list
00407           + _S_freelist_index(__n);
00408         // Acquire the lock here with a constructor call.  This
00409         // ensures that it is released in exit or during stack
00410         // unwinding.
00411         _Lock __lock_instance;
00412         _Obj* __restrict__ __result = *__my_free_list;
00413         if (__builtin_expect(__result == 0, 0))
00414           __ret = _S_refill(_S_round_up(__n));
00415         else
00416           {
00417         *__my_free_list = __result -> _M_free_list_link;
00418         __ret = __result;
00419           }     
00420         if (__builtin_expect(__ret == 0, 0))
00421           __throw_bad_alloc();
00422       }
00423     return __ret;
00424       }
00425 
00426       // __p may not be 0
00427       static void
00428       deallocate(void* __p, size_t __n)
00429       {
00430     if ((__n > (size_t) _MAX_BYTES) || (_S_force_new > 0))
00431       __new_alloc::deallocate(__p, __n);
00432     else
00433       {
00434         _Obj* volatile*  __my_free_list = _S_free_list
00435           + _S_freelist_index(__n);
00436         _Obj* __q = (_Obj*)__p;
00437 
00438         // Acquire the lock here with a constructor call.  This
00439         // ensures that it is released in exit or during stack
00440         // unwinding.
00441         _Lock __lock_instance;
00442         __q -> _M_free_list_link = *__my_free_list;
00443         *__my_free_list = __q;
00444       }
00445       }
00446 
00447       static void*
00448       reallocate(void* __p, size_t __old_sz, size_t __new_sz);
00449     };
00450 
00451   template<bool __threads, int __inst> _Atomic_word
00452   __default_alloc_template<__threads, __inst>::_S_force_new = 0;
00453 
00454   template<bool __threads, int __inst>
00455     inline bool
00456     operator==(const __default_alloc_template<__threads,__inst>&,
00457                const __default_alloc_template<__threads,__inst>&)
00458     { return true; }
00459 
00460   template<bool __threads, int __inst>
00461     inline bool
00462     operator!=(const __default_alloc_template<__threads,__inst>&,
00463                const __default_alloc_template<__threads,__inst>&)
00464     { return false; }
00465 
00466 
00467   // We allocate memory in large chunks in order to avoid fragmenting the
00468   // heap too much.  We assume that __size is properly aligned.  We hold
00469   // the allocation lock.
00470   template<bool __threads, int __inst>
00471     char*
00472     __default_alloc_template<__threads, __inst>::
00473     _S_chunk_alloc(size_t __size, int& __nobjs)
00474     {
00475       char* __result;
00476       size_t __total_bytes = __size * __nobjs;
00477       size_t __bytes_left = _S_end_free - _S_start_free;
00478 
00479       if (__bytes_left >= __total_bytes)
00480         {
00481           __result = _S_start_free;
00482           _S_start_free += __total_bytes;
00483           return __result ;
00484         }
00485       else if (__bytes_left >= __size)
00486         {
00487           __nobjs = (int)(__bytes_left/__size);
00488           __total_bytes = __size * __nobjs;
00489           __result = _S_start_free;
00490           _S_start_free += __total_bytes;
00491           return __result;
00492         }
00493       else
00494         {
00495           size_t __bytes_to_get =
00496             2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
00497           // Try to make use of the left-over piece.
00498           if (__bytes_left > 0)
00499             {
00500               _Obj* volatile* __my_free_list =
00501                 _S_free_list + _S_freelist_index(__bytes_left);
00502 
00503               ((_Obj*)(void*)_S_start_free) -> _M_free_list_link = *__my_free_list;
00504               *__my_free_list = (_Obj*)(void*)_S_start_free;
00505             }
00506           _S_start_free = (char*) __new_alloc::allocate(__bytes_to_get);
00507           if (_S_start_free == 0)
00508             {
00509               size_t __i;
00510               _Obj* volatile* __my_free_list;
00511               _Obj* __p;
00512               // Try to make do with what we have.  That can't hurt.  We
00513               // do not try smaller requests, since that tends to result
00514               // in disaster on multi-process machines.
00515               __i = __size;
00516               for (; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN)
00517                 {
00518                   __my_free_list = _S_free_list + _S_freelist_index(__i);
00519                   __p = *__my_free_list;
00520                   if (__p != 0)
00521                     {
00522                       *__my_free_list = __p -> _M_free_list_link;
00523                       _S_start_free = (char*)__p;
00524                       _S_end_free = _S_start_free + __i;
00525                       return _S_chunk_alloc(__size, __nobjs);
00526                       // Any leftover piece will eventually make it to the
00527                       // right free list.
00528                     }
00529                 }
00530               _S_end_free = 0;        // In case of exception.
00531               _S_start_free = (char*)__new_alloc::allocate(__bytes_to_get);
00532               // This should either throw an exception or remedy the situation.
00533               // Thus we assume it succeeded.
00534             }
00535           _S_heap_size += __bytes_to_get;
00536           _S_end_free = _S_start_free + __bytes_to_get;
00537           return _S_chunk_alloc(__size, __nobjs);
00538         }
00539     }
00540 
00541 
00542   // Returns an object of size __n, and optionally adds to "size
00543   // __n"'s free list.  We assume that __n is properly aligned.  We
00544   // hold the allocation lock.
00545   template<bool __threads, int __inst>
00546     void*
00547     __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
00548     {
00549       int __nobjs = 20;
00550       char* __chunk = _S_chunk_alloc(__n, __nobjs);
00551       _Obj* volatile* __my_free_list;
00552       _Obj* __result;
00553       _Obj* __current_obj;
00554       _Obj* __next_obj;
00555       int __i;
00556 
00557       if (1 == __nobjs)
00558         return __chunk;
00559       __my_free_list = _S_free_list + _S_freelist_index(__n);
00560 
00561       // Build free list in chunk.
00562       __result = (_Obj*)(void*)__chunk;
00563       *__my_free_list = __next_obj = (_Obj*)(void*)(__chunk + __n);
00564       for (__i = 1; ; __i++)
00565         {
00566       __current_obj = __next_obj;
00567           __next_obj = (_Obj*)(void*)((char*)__next_obj + __n);
00568       if (__nobjs - 1 == __i)
00569         {
00570           __current_obj -> _M_free_list_link = 0;
00571           break;
00572         }
00573       else
00574         __current_obj -> _M_free_list_link = __next_obj;
00575     }
00576       return __result;
00577     }
00578 
00579 
00580   template<bool threads, int inst>
00581     void*
00582     __default_alloc_template<threads, inst>::
00583     reallocate(void* __p, size_t __old_sz, size_t __new_sz)
00584     {
00585       void* __result;
00586       size_t __copy_sz;
00587 
00588       if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES)
00589         return(realloc(__p, __new_sz));
00590       if (_S_round_up(__old_sz) == _S_round_up(__new_sz))
00591         return(__p);
00592       __result = allocate(__new_sz);
00593       __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
00594       memcpy(__result, __p, __copy_sz);
00595       deallocate(__p, __old_sz);
00596       return __result;
00597     }
00598 
00599   template<bool __threads, int __inst>
00600     _STL_mutex_lock
00601     __default_alloc_template<__threads,__inst>::_S_node_allocator_lock
00602     __STL_MUTEX_INITIALIZER;
00603 
00604   template<bool __threads, int __inst>
00605     char* __default_alloc_template<__threads,__inst>::_S_start_free = 0;
00606 
00607   template<bool __threads, int __inst>
00608     char* __default_alloc_template<__threads,__inst>::_S_end_free = 0;
00609 
00610   template<bool __threads, int __inst>
00611     size_t __default_alloc_template<__threads,__inst>::_S_heap_size = 0;
00612 
00613   template<bool __threads, int __inst>
00614     typename __default_alloc_template<__threads,__inst>::_Obj* volatile
00615     __default_alloc_template<__threads,__inst>::_S_free_list[_NFREELISTS];
00616 
00617   typedef __default_alloc_template<true,0>    __alloc;
00618   typedef __default_alloc_template<false,0>   __single_client_alloc;
00619 
00620 
00621   /**
00622    *  @brief  The "standard" allocator, as per [20.4].
00623    *
00624    *  The private _Alloc is "SGI" style.  (See comments at the top
00625    *  of stl_alloc.h.)
00626    *
00627    *  The underlying allocator behaves as follows.
00628    *    - __default_alloc_template is used via two typedefs
00629    *    - "__single_client_alloc" typedef does no locking for threads
00630    *    - "__alloc" typedef is threadsafe via the locks
00631    *    - __new_alloc is used for memory requests
00632    *
00633    *  (See @link Allocators allocators info @endlink for more.)
00634    */
00635   template<typename _Tp>
00636     class allocator
00637     {
00638       typedef __alloc _Alloc;          // The underlying allocator.
00639     public:
00640       typedef size_t     size_type;
00641       typedef ptrdiff_t  difference_type;
00642       typedef _Tp*       pointer;
00643       typedef const _Tp* const_pointer;
00644       typedef _Tp&       reference;
00645       typedef const _Tp& const_reference;
00646       typedef _Tp        value_type;
00647 
00648       template<typename _Tp1>
00649         struct rebind
00650         { typedef allocator<_Tp1> other; };
00651 
00652       allocator() throw() {}
00653       allocator(const allocator&) throw() {}
00654       template<typename _Tp1>
00655         allocator(const allocator<_Tp1>&) throw() {}
00656       ~allocator() throw() {}
00657 
00658       pointer
00659       address(reference __x) const { return &__x; }
00660 
00661       const_pointer
00662       address(const_reference __x) const { return &__x; }
00663 
00664       // NB: __n is permitted to be 0.  The C++ standard says nothing
00665       // about what the return value is when __n == 0.
00666       _Tp*
00667       allocate(size_type __n, const void* = 0)
00668       {
00669     _Tp* __ret = 0;
00670     if (__n)
00671       {
00672         if (__n <= this->max_size())
00673           __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
00674         else
00675           __throw_bad_alloc();
00676       }
00677     return __ret;
00678       }
00679 
00680       // __p is not permitted to be a null pointer.
00681       void
00682       deallocate(pointer __p, size_type __n)
00683       { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
00684 
00685       size_type
00686       max_size() const throw() { return size_t(-1) / sizeof(_Tp); }
00687 
00688       void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
00689       void destroy(pointer __p) { __p->~_Tp(); }
00690     };
00691 
00692   template<>
00693     class allocator<void>
00694     {
00695     public:
00696       typedef size_t      size_type;
00697       typedef ptrdiff_t   difference_type;
00698       typedef void*       pointer;
00699       typedef const void* const_pointer;
00700       typedef void        value_type;
00701 
00702       template<typename _Tp1>
00703         struct rebind
00704         { typedef allocator<_Tp1> other; };
00705     };
00706 
00707 
00708   template<typename _T1, typename _T2>
00709     inline bool
00710     operator==(const allocator<_T1>&, const allocator<_T2>&)
00711     { return true; }
00712 
00713   template<typename _T1, typename _T2>
00714     inline bool
00715     operator!=(const allocator<_T1>&, const allocator<_T2>&)
00716     { return false; }
00717 
00718 
00719   /**
00720    *  @if maint
00721    *  Allocator adaptor to turn an "SGI" style allocator (e.g.,
00722    *  __alloc, __malloc_alloc_template) into a "standard" conforming
00723    *  allocator.  Note that this adaptor does *not* assume that all
00724    *  objects of the underlying alloc class are identical, nor does it
00725    *  assume that all of the underlying alloc's member functions are
00726    *  static member functions.  Note, also, that __allocator<_Tp,
00727    *  __alloc> is essentially the same thing as allocator<_Tp>.
00728    *  @endif
00729    *  (See @link Allocators allocators info @endlink for more.)
00730    */
00731   template<typename _Tp, typename _Alloc>
00732     struct __allocator
00733     {
00734       _Alloc __underlying_alloc;
00735       
00736       typedef size_t    size_type;
00737       typedef ptrdiff_t difference_type;
00738       typedef _Tp*       pointer;
00739       typedef const _Tp* const_pointer;
00740       typedef _Tp&       reference;
00741       typedef const _Tp& const_reference;
00742       typedef _Tp        value_type;
00743 
00744       template<typename _Tp1>
00745         struct rebind
00746         { typedef __allocator<_Tp1, _Alloc> other; };
00747 
00748       __allocator() throw() {}
00749       __allocator(const __allocator& __a) throw()
00750       : __underlying_alloc(__a.__underlying_alloc) {}
00751 
00752       template<typename _Tp1>
00753         __allocator(const __allocator<_Tp1, _Alloc>& __a) throw()
00754         : __underlying_alloc(__a.__underlying_alloc) {}
00755 
00756       ~__allocator() throw() {}
00757 
00758       pointer
00759       address(reference __x) const { return &__x; }
00760 
00761       const_pointer
00762       address(const_reference __x) const { return &__x; }
00763 
00764       // NB: __n is permitted to be 0.  The C++ standard says nothing
00765       // about what the return value is when __n == 0.
00766       _Tp*
00767       allocate(size_type __n, const void* = 0)
00768       {
00769     _Tp* __ret = 0;
00770     if (__n)
00771       __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
00772     return __ret;
00773       }
00774 
00775       // __p is not permitted to be a null pointer.
00776       void
00777       deallocate(pointer __p, size_type __n)
00778       { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }
00779       
00780       size_type
00781       max_size() const throw() { return size_t(-1) / sizeof(_Tp); }
00782       
00783       void
00784       construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
00785       
00786       void
00787       destroy(pointer __p) { __p->~_Tp(); }
00788     };
00789 
00790   template<typename _Alloc>
00791     struct __allocator<void, _Alloc>
00792     {
00793       typedef size_t      size_type;
00794       typedef ptrdiff_t   difference_type;
00795       typedef void*       pointer;
00796       typedef const void* const_pointer;
00797       typedef void        value_type;
00798 
00799       template<typename _Tp1>
00800         struct rebind
00801         { typedef __allocator<_Tp1, _Alloc> other; };
00802     };
00803 
00804   template<typename _Tp, typename _Alloc>
00805     inline bool
00806     operator==(const __allocator<_Tp,_Alloc>& __a1,
00807                const __allocator<_Tp,_Alloc>& __a2)
00808     { return __a1.__underlying_alloc == __a2.__underlying_alloc; }
00809 
00810   template<typename _Tp, typename _Alloc>
00811     inline bool
00812     operator!=(const __allocator<_Tp, _Alloc>& __a1,
00813                const __allocator<_Tp, _Alloc>& __a2)
00814     { return __a1.__underlying_alloc != __a2.__underlying_alloc; }
00815 
00816 
00817   //@{
00818   /** Comparison operators for all of the predifined SGI-style allocators.
00819    *  This ensures that __allocator<malloc_alloc> (for example) will work
00820    *  correctly.  As required, all allocators compare equal.
00821    */
00822   template<int inst>
00823     inline bool
00824     operator==(const __malloc_alloc_template<inst>&,
00825                const __malloc_alloc_template<inst>&)
00826     { return true; }
00827 
00828   template<int __inst>
00829     inline bool
00830     operator!=(const __malloc_alloc_template<__inst>&,
00831                const __malloc_alloc_template<__inst>&)
00832     { return false; }
00833 
00834   template<typename _Alloc>
00835     inline bool
00836     operator==(const __debug_alloc<_Alloc>&, const __debug_alloc<_Alloc>&)
00837     { return true; }
00838 
00839   template<typename _Alloc>
00840     inline bool
00841     operator!=(const __debug_alloc<_Alloc>&, const __debug_alloc<_Alloc>&)
00842     { return false; }
00843   //@}
00844 
00845 
00846   /**
00847    *  @if maint
00848    *  Another allocator adaptor:  _Alloc_traits.  This serves two purposes.
00849    *  First, make it possible to write containers that can use either "SGI"
00850    *  style allocators or "standard" allocators.  Second, provide a mechanism
00851    *  so that containers can query whether or not the allocator has distinct
00852    *  instances.  If not, the container can avoid wasting a word of memory to
00853    *  store an empty object.  For examples of use, see stl_vector.h, etc, or
00854    *  any of the other classes derived from this one.
00855    *
00856    *  This adaptor uses partial specialization.  The general case of
00857    *  _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
00858    *  standard-conforming allocator, possibly with non-equal instances and
00859    *  non-static members.  (It still behaves correctly even if _Alloc has
00860    *  static member and if all instances are equal.  Refinements affect
00861    *  performance, not correctness.)
00862    *
00863    *  There are always two members:  allocator_type, which is a standard-
00864    *  conforming allocator type for allocating objects of type _Tp, and
00865    *  _S_instanceless, a static const member of type bool.  If
00866    *  _S_instanceless is true, this means that there is no difference
00867    *  between any two instances of type allocator_type.  Furthermore, if
00868    *  _S_instanceless is true, then _Alloc_traits has one additional
00869    *  member:  _Alloc_type.  This type encapsulates allocation and
00870    *  deallocation of objects of type _Tp through a static interface; it
00871    *  has two member functions, whose signatures are
00872    *
00873    *  -  static _Tp* allocate(size_t)
00874    *  -  static void deallocate(_Tp*, size_t)
00875    *
00876    *  The size_t parameters are "standard" style (see top of stl_alloc.h) in
00877    *  that they take counts, not sizes.
00878    *
00879    *  @endif
00880    *  (See @link Allocators allocators info @endlink for more.)
00881    */
00882   //@{
00883   // The fully general version.
00884   template<typename _Tp, typename _Allocator>
00885     struct _Alloc_traits
00886     {
00887       static const bool _S_instanceless = false;
00888       typedef typename _Allocator::template rebind<_Tp>::other allocator_type;
00889     };
00890 
00891   template<typename _Tp, typename _Allocator>
00892     const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;
00893 
00894   /// The version for the default allocator.
00895   template<typename _Tp, typename _Tp1>
00896     struct _Alloc_traits<_Tp, allocator<_Tp1> >
00897     {
00898       static const bool _S_instanceless = true;
00899       typedef __simple_alloc<_Tp, __alloc> _Alloc_type;
00900       typedef allocator<_Tp> allocator_type;
00901     };
00902   //@}
00903 
00904   //@{
00905   /// Versions for the predefined "SGI" style allocators.
00906   template<typename _Tp, int __inst>
00907     struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> >
00908     {
00909       static const bool _S_instanceless = true;
00910       typedef __simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
00911       typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
00912     };
00913 
00914   template<typename _Tp, bool __threads, int __inst>
00915     struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> >
00916     {
00917       static const bool _S_instanceless = true;
00918       typedef __simple_alloc<_Tp, __default_alloc_template<__threads, __inst> >
00919       _Alloc_type;
00920       typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> >
00921       allocator_type;
00922     };
00923 
00924   template<typename _Tp, typename _Alloc>
00925     struct _Alloc_traits<_Tp, __debug_alloc<_Alloc> >
00926     {
00927       static const bool _S_instanceless = true;
00928       typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type;
00929       typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type;
00930     };
00931   //@}
00932 
00933   //@{
00934   /// Versions for the __allocator adaptor used with the predefined
00935   /// "SGI" style allocators.
00936   template<typename _Tp, typename _Tp1, int __inst>
00937     struct _Alloc_traits<_Tp,
00938                          __allocator<_Tp1, __malloc_alloc_template<__inst> > >
00939     {
00940       static const bool _S_instanceless = true;
00941       typedef __simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
00942       typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
00943     };
00944 
00945   template<typename _Tp, typename _Tp1, bool __thr, int __inst>
00946     struct _Alloc_traits<_Tp, __allocator<_Tp1, __default_alloc_template<__thr, __inst> > >
00947     {
00948       static const bool _S_instanceless = true;
00949       typedef __simple_alloc<_Tp, __default_alloc_template<__thr,__inst> >
00950       _Alloc_type;
00951       typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> >
00952       allocator_type;
00953     };
00954 
00955   template<typename _Tp, typename _Tp1, typename _Alloc>
00956     struct _Alloc_traits<_Tp, __allocator<_Tp1, __debug_alloc<_Alloc> > >
00957     {
00958       static const bool _S_instanceless = true;
00959       typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type;
00960       typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type;
00961     };
00962   //@}
00963 
00964   // Inhibit implicit instantiations for required instantiations,
00965   // which are defined via explicit instantiations elsewhere.
00966   // NB: This syntax is a GNU extension.
00967 #if _GLIBCPP_EXTERN_TEMPLATE
00968   extern template class allocator<char>;
00969   extern template class allocator<wchar_t>;
00970   extern template class __default_alloc_template<true,0>;
00971 #endif
00972 } // namespace std
00973 
00974 #endif

Generated on Thu Feb 10 23:22:58 2005 for libstdc++-v3 Source by  doxygen 1.4.0