libstdc++
mt_allocator.h
Go to the documentation of this file.
00001 // MT-optimized allocator -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file ext/mt_allocator.h
00027  *  This file is a GNU extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _MT_ALLOCATOR_H
00031 #define _MT_ALLOCATOR_H 1
00032 
00033 #include <new>
00034 #include <cstdlib>
00035 #include <bits/functexcept.h>
00036 #include <ext/atomicity.h>
00037 #include <bits/move.h>
00038 
00039 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00040 {
00041 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00042 
00043   using std::size_t;
00044   using std::ptrdiff_t;
00045 
00046   typedef void (*__destroy_handler)(void*);
00047 
00048   /// Base class for pool object.
00049   struct __pool_base
00050   {
00051     // Using short int as type for the binmap implies we are never
00052     // caching blocks larger than 32768 with this allocator.
00053     typedef unsigned short int _Binmap_type;
00054 
00055     // Variables used to configure the behavior of the allocator,
00056     // assigned and explained in detail below.
00057     struct _Tune
00058      {
00059       // Compile time constants for the default _Tune values.
00060       enum { _S_align = 8 };
00061       enum { _S_max_bytes = 128 };
00062       enum { _S_min_bin = 8 };
00063       enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
00064       enum { _S_max_threads = 4096 };
00065       enum { _S_freelist_headroom = 10 };
00066 
00067       // Alignment needed.
00068       // NB: In any case must be >= sizeof(_Block_record), that
00069       // is 4 on 32 bit machines and 8 on 64 bit machines.
00070       size_t    _M_align;
00071       
00072       // Allocation requests (after round-up to power of 2) below
00073       // this value will be handled by the allocator. A raw new/
00074       // call will be used for requests larger than this value.
00075       // NB: Must be much smaller than _M_chunk_size and in any
00076       // case <= 32768.
00077       size_t    _M_max_bytes; 
00078 
00079       // Size in bytes of the smallest bin.
00080       // NB: Must be a power of 2 and >= _M_align (and of course
00081       // much smaller than _M_max_bytes).
00082       size_t    _M_min_bin;
00083 
00084       // In order to avoid fragmenting and minimize the number of
00085       // new() calls we always request new memory using this
00086       // value. Based on previous discussions on the libstdc++
00087       // mailing list we have chosen the value below.
00088       // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
00089       // NB: At least one order of magnitude > _M_max_bytes. 
00090       size_t    _M_chunk_size;
00091 
00092       // The maximum number of supported threads. For
00093       // single-threaded operation, use one. Maximum values will
00094       // vary depending on details of the underlying system. (For
00095       // instance, Linux 2.4.18 reports 4070 in
00096       // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports
00097       // 65534)
00098       size_t    _M_max_threads;
00099 
00100       // Each time a deallocation occurs in a threaded application
00101       // we make sure that there are no more than
00102       // _M_freelist_headroom % of used memory on the freelist. If
00103       // the number of additional records is more than
00104       // _M_freelist_headroom % of the freelist, we move these
00105       // records back to the global pool.
00106       size_t    _M_freelist_headroom;
00107       
00108       // Set to true forces all allocations to use new().
00109       bool  _M_force_new; 
00110       
00111       explicit
00112       _Tune()
00113       : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),
00114       _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads), 
00115       _M_freelist_headroom(_S_freelist_headroom), 
00116       _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)
00117       { }
00118 
00119       explicit
00120       _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk, 
00121         size_t __maxthreads, size_t __headroom, bool __force) 
00122       : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),
00123       _M_chunk_size(__chunk), _M_max_threads(__maxthreads),
00124       _M_freelist_headroom(__headroom), _M_force_new(__force)
00125       { }
00126     };
00127     
00128     struct _Block_address
00129     {
00130       void*             _M_initial;
00131       _Block_address*       _M_next;
00132     };
00133     
00134     const _Tune&
00135     _M_get_options() const
00136     { return _M_options; }
00137 
00138     void
00139     _M_set_options(_Tune __t)
00140     { 
00141       if (!_M_init)
00142     _M_options = __t;
00143     }
00144 
00145     bool
00146     _M_check_threshold(size_t __bytes)
00147     { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }
00148 
00149     size_t
00150     _M_get_binmap(size_t __bytes)
00151     { return _M_binmap[__bytes]; }
00152 
00153     size_t
00154     _M_get_align()
00155     { return _M_options._M_align; }
00156 
00157     explicit 
00158     __pool_base() 
00159     : _M_options(_Tune()), _M_binmap(0), _M_init(false) { }
00160 
00161     explicit 
00162     __pool_base(const _Tune& __options)
00163     : _M_options(__options), _M_binmap(0), _M_init(false) { }
00164 
00165   private:
00166     explicit 
00167     __pool_base(const __pool_base&);
00168 
00169     __pool_base&
00170     operator=(const __pool_base&);
00171 
00172   protected:
00173     // Configuration options.
00174     _Tune               _M_options;
00175     
00176     _Binmap_type*       _M_binmap;
00177 
00178     // Configuration of the pool object via _M_options can happen
00179     // after construction but before initialization. After
00180     // initialization is complete, this variable is set to true.
00181     bool            _M_init;
00182   };
00183 
00184 
00185   /**
00186    *  @brief  Data describing the underlying memory pool, parameterized on
00187    *  threading support.
00188    */
00189   template<bool _Thread>
00190     class __pool;
00191 
00192   /// Specialization for single thread.
00193   template<>
00194     class __pool<false> : public __pool_base
00195     {
00196     public:
00197       union _Block_record
00198       {
00199     // Points to the block_record of the next free block.
00200     _Block_record*          _M_next;
00201       };
00202 
00203       struct _Bin_record
00204       {
00205     // An "array" of pointers to the first free block.
00206     _Block_record**         _M_first;
00207 
00208     // A list of the initial addresses of all allocated blocks.
00209     _Block_address*             _M_address;
00210       };
00211       
00212       void
00213       _M_initialize_once()
00214       {
00215     if (__builtin_expect(_M_init == false, false))
00216       _M_initialize();
00217       }
00218 
00219       void
00220       _M_destroy() throw();
00221 
00222       char* 
00223       _M_reserve_block(size_t __bytes, const size_t __thread_id);
00224     
00225       void
00226       _M_reclaim_block(char* __p, size_t __bytes) throw ();
00227     
00228       size_t 
00229       _M_get_thread_id() { return 0; }
00230       
00231       const _Bin_record&
00232       _M_get_bin(size_t __which)
00233       { return _M_bin[__which]; }
00234       
00235       void
00236       _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)
00237       { }
00238 
00239       explicit __pool() 
00240       : _M_bin(0), _M_bin_size(1) { }
00241 
00242       explicit __pool(const __pool_base::_Tune& __tune) 
00243       : __pool_base(__tune), _M_bin(0), _M_bin_size(1) { }
00244 
00245     private:
00246       // An "array" of bin_records each of which represents a specific
00247       // power of 2 size. Memory to this "array" is allocated in
00248       // _M_initialize().
00249       _Bin_record*       _M_bin;
00250       
00251       // Actual value calculated in _M_initialize().
00252       size_t                    _M_bin_size;     
00253 
00254       void
00255       _M_initialize();
00256   };
00257  
00258 #ifdef __GTHREADS
00259   /// Specialization for thread enabled, via gthreads.h.
00260   template<>
00261     class __pool<true> : public __pool_base
00262     {
00263     public:
00264       // Each requesting thread is assigned an id ranging from 1 to
00265       // _S_max_threads. Thread id 0 is used as a global memory pool.
00266       // In order to get constant performance on the thread assignment
00267       // routine, we keep a list of free ids. When a thread first
00268       // requests memory we remove the first record in this list and
00269       // stores the address in a __gthread_key. When initializing the
00270       // __gthread_key we specify a destructor. When this destructor
00271       // (i.e. the thread dies) is called, we return the thread id to
00272       // the front of this list.
00273       struct _Thread_record
00274       {
00275     // Points to next free thread id record. NULL if last record in list.
00276     _Thread_record*         _M_next;
00277     
00278     // Thread id ranging from 1 to _S_max_threads.
00279     size_t                          _M_id;
00280       };
00281       
00282       union _Block_record
00283       {
00284     // Points to the block_record of the next free block.
00285     _Block_record*          _M_next;
00286     
00287     // The thread id of the thread which has requested this block.
00288     size_t                          _M_thread_id;
00289       };
00290       
00291       struct _Bin_record
00292       {
00293     // An "array" of pointers to the first free block for each
00294     // thread id. Memory to this "array" is allocated in
00295     // _S_initialize() for _S_max_threads + global pool 0.
00296     _Block_record**         _M_first;
00297     
00298     // A list of the initial addresses of all allocated blocks.
00299     _Block_address*             _M_address;
00300 
00301     // An "array" of counters used to keep track of the amount of
00302     // blocks that are on the freelist/used for each thread id.
00303     // - Note that the second part of the allocated _M_used "array"
00304     //   actually hosts (atomic) counters of reclaimed blocks:  in
00305     //   _M_reserve_block and in _M_reclaim_block those numbers are
00306     //   subtracted from the first ones to obtain the actual size
00307     //   of the "working set" of the given thread.
00308     // - Memory to these "arrays" is allocated in _S_initialize()
00309     //   for _S_max_threads + global pool 0.
00310     size_t*             _M_free;
00311     size_t*                 _M_used;
00312     
00313     // Each bin has its own mutex which is used to ensure data
00314     // integrity while changing "ownership" on a block.  The mutex
00315     // is initialized in _S_initialize().
00316     __gthread_mutex_t*              _M_mutex;
00317       };
00318       
00319       // XXX GLIBCXX_ABI Deprecated
00320       void
00321       _M_initialize(__destroy_handler);
00322 
00323       void
00324       _M_initialize_once()
00325       {
00326     if (__builtin_expect(_M_init == false, false))
00327       _M_initialize();
00328       }
00329 
00330       void
00331       _M_destroy() throw();
00332 
00333       char* 
00334       _M_reserve_block(size_t __bytes, const size_t __thread_id);
00335     
00336       void
00337       _M_reclaim_block(char* __p, size_t __bytes) throw ();
00338     
00339       const _Bin_record&
00340       _M_get_bin(size_t __which)
00341       { return _M_bin[__which]; }
00342       
00343       void
00344       _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block, 
00345              size_t __thread_id)
00346       {
00347     if (__gthread_active_p())
00348       {
00349         __block->_M_thread_id = __thread_id;
00350         --__bin._M_free[__thread_id];
00351         ++__bin._M_used[__thread_id];
00352       }
00353       }
00354 
00355       // XXX GLIBCXX_ABI Deprecated
00356       _GLIBCXX_CONST void 
00357       _M_destroy_thread_key(void*) throw ();
00358 
00359       size_t 
00360       _M_get_thread_id();
00361 
00362       explicit __pool() 
00363       : _M_bin(0), _M_bin_size(1), _M_thread_freelist(0) 
00364       { }
00365 
00366       explicit __pool(const __pool_base::_Tune& __tune) 
00367       : __pool_base(__tune), _M_bin(0), _M_bin_size(1), 
00368     _M_thread_freelist(0) 
00369       { }
00370 
00371     private:
00372       // An "array" of bin_records each of which represents a specific
00373       // power of 2 size. Memory to this "array" is allocated in
00374       // _M_initialize().
00375       _Bin_record*      _M_bin;
00376 
00377       // Actual value calculated in _M_initialize().
00378       size_t                    _M_bin_size;
00379 
00380       _Thread_record*       _M_thread_freelist;
00381       void*         _M_thread_freelist_initial;
00382 
00383       void
00384       _M_initialize();
00385     };
00386 #endif
00387 
00388   template<template <bool> class _PoolTp, bool _Thread>
00389     struct __common_pool
00390     {
00391       typedef _PoolTp<_Thread>      pool_type;
00392       
00393       static pool_type&
00394       _S_get_pool()
00395       { 
00396     static pool_type _S_pool;
00397     return _S_pool;
00398       }
00399     };
00400 
00401   template<template <bool> class _PoolTp, bool _Thread>
00402     struct __common_pool_base;
00403 
00404   template<template <bool> class _PoolTp>
00405     struct __common_pool_base<_PoolTp, false> 
00406     : public __common_pool<_PoolTp, false>
00407     {
00408       using  __common_pool<_PoolTp, false>::_S_get_pool;
00409 
00410       static void
00411       _S_initialize_once()
00412       {
00413     static bool __init;
00414     if (__builtin_expect(__init == false, false))
00415       {
00416         _S_get_pool()._M_initialize_once(); 
00417         __init = true;
00418       }
00419       }
00420     };
00421 
00422 #ifdef __GTHREADS
00423   template<template <bool> class _PoolTp>
00424     struct __common_pool_base<_PoolTp, true>
00425     : public __common_pool<_PoolTp, true>
00426     {
00427       using  __common_pool<_PoolTp, true>::_S_get_pool;
00428       
00429       static void
00430       _S_initialize() 
00431       { _S_get_pool()._M_initialize_once(); }
00432 
00433       static void
00434       _S_initialize_once()
00435       { 
00436     static bool __init;
00437     if (__builtin_expect(__init == false, false))
00438       {
00439         if (__gthread_active_p())
00440           {
00441         // On some platforms, __gthread_once_t is an aggregate.
00442         static __gthread_once_t __once = __GTHREAD_ONCE_INIT;
00443         __gthread_once(&__once, _S_initialize);
00444           }
00445 
00446         // Double check initialization. May be necessary on some
00447         // systems for proper construction when not compiling with
00448         // thread flags.
00449         _S_get_pool()._M_initialize_once(); 
00450         __init = true;
00451       }
00452       }
00453     };
00454 #endif
00455 
00456   /// Policy for shared __pool objects.
00457   template<template <bool> class _PoolTp, bool _Thread>
00458     struct __common_pool_policy : public __common_pool_base<_PoolTp, _Thread>
00459     {
00460       template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp, 
00461            bool _Thread1 = _Thread>
00462         struct _M_rebind
00463         { typedef __common_pool_policy<_PoolTp1, _Thread1> other; };
00464 
00465       using  __common_pool_base<_PoolTp, _Thread>::_S_get_pool;
00466       using  __common_pool_base<_PoolTp, _Thread>::_S_initialize_once;
00467   };
00468  
00469 
00470   template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
00471     struct __per_type_pool
00472     {
00473       typedef _Tp           value_type;
00474       typedef _PoolTp<_Thread>      pool_type;
00475       
00476       static pool_type&
00477       _S_get_pool()
00478       { 
00479     // Sane defaults for the _PoolTp.
00480     typedef typename pool_type::_Block_record _Block_record;
00481     const static size_t __a = (__alignof__(_Tp) >= sizeof(_Block_record)
00482                    ? __alignof__(_Tp) : sizeof(_Block_record));
00483 
00484     typedef typename __pool_base::_Tune _Tune;
00485     static _Tune _S_tune(__a, sizeof(_Tp) * 64,
00486                  sizeof(_Tp) * 2 >= __a ? sizeof(_Tp) * 2 : __a,
00487                  sizeof(_Tp) * size_t(_Tune::_S_chunk_size),
00488                  _Tune::_S_max_threads,
00489                  _Tune::_S_freelist_headroom,
00490                  std::getenv("GLIBCXX_FORCE_NEW") ? true : false);
00491     static pool_type _S_pool(_S_tune);
00492     return _S_pool;
00493       }
00494     };
00495 
00496   template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
00497     struct __per_type_pool_base;
00498 
00499   template<typename _Tp, template <bool> class _PoolTp>
00500     struct __per_type_pool_base<_Tp, _PoolTp, false> 
00501     : public __per_type_pool<_Tp, _PoolTp, false> 
00502     {
00503       using  __per_type_pool<_Tp, _PoolTp, false>::_S_get_pool;
00504 
00505       static void
00506       _S_initialize_once()
00507       {
00508     static bool __init;
00509     if (__builtin_expect(__init == false, false))
00510       {
00511         _S_get_pool()._M_initialize_once(); 
00512         __init = true;
00513       }
00514       }
00515     };
00516 
00517  #ifdef __GTHREADS
00518  template<typename _Tp, template <bool> class _PoolTp>
00519     struct __per_type_pool_base<_Tp, _PoolTp, true> 
00520     : public __per_type_pool<_Tp, _PoolTp, true> 
00521     {
00522       using  __per_type_pool<_Tp, _PoolTp, true>::_S_get_pool;
00523 
00524       static void
00525       _S_initialize() 
00526       { _S_get_pool()._M_initialize_once(); }
00527 
00528       static void
00529       _S_initialize_once()
00530       { 
00531     static bool __init;
00532     if (__builtin_expect(__init == false, false))
00533       {
00534         if (__gthread_active_p())
00535           {
00536         // On some platforms, __gthread_once_t is an aggregate.
00537         static __gthread_once_t __once = __GTHREAD_ONCE_INIT;
00538         __gthread_once(&__once, _S_initialize);
00539           }
00540 
00541         // Double check initialization. May be necessary on some
00542         // systems for proper construction when not compiling with
00543         // thread flags.
00544         _S_get_pool()._M_initialize_once(); 
00545         __init = true;
00546       }
00547       }
00548     };
00549 #endif
00550 
00551   /// Policy for individual __pool objects.
00552   template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
00553     struct __per_type_pool_policy 
00554     : public __per_type_pool_base<_Tp, _PoolTp, _Thread>
00555     {
00556       template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp, 
00557            bool _Thread1 = _Thread>
00558         struct _M_rebind
00559         { typedef __per_type_pool_policy<_Tp1, _PoolTp1, _Thread1> other; };
00560 
00561       using  __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_get_pool;
00562       using  __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_initialize_once;
00563   };
00564 
00565 
00566   /// Base class for _Tp dependent member functions.
00567   template<typename _Tp>
00568     class __mt_alloc_base 
00569     {
00570     public:
00571       typedef size_t                    size_type;
00572       typedef ptrdiff_t                 difference_type;
00573       typedef _Tp*                      pointer;
00574       typedef const _Tp*                const_pointer;
00575       typedef _Tp&                      reference;
00576       typedef const _Tp&                const_reference;
00577       typedef _Tp                       value_type;
00578 
00579       pointer
00580       address(reference __x) const
00581       { return std::__addressof(__x); }
00582 
00583       const_pointer
00584       address(const_reference __x) const
00585       { return std::__addressof(__x); }
00586 
00587       size_type
00588       max_size() const throw() 
00589       { return size_t(-1) / sizeof(_Tp); }
00590 
00591       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00592       // 402. wrong new expression in [some_] allocator::construct
00593       void 
00594       construct(pointer __p, const _Tp& __val) 
00595       { ::new((void *)__p) _Tp(__val); }
00596 
00597 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00598       template<typename... _Args>
00599         void
00600         construct(pointer __p, _Args&&... __args)
00601     { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
00602 #endif
00603 
00604       void 
00605       destroy(pointer __p) { __p->~_Tp(); }
00606     };
00607 
00608 #ifdef __GTHREADS
00609 #define __thread_default true
00610 #else
00611 #define __thread_default false
00612 #endif
00613 
00614   /**
00615    *  @brief  This is a fixed size (power of 2) allocator which - when
00616    *  compiled with thread support - will maintain one freelist per
00617    *  size per thread plus a @a global one. Steps are taken to limit
00618    *  the per thread freelist sizes (by returning excess back to
00619    *  the @a global list).
00620    *  @ingroup allocators
00621    *
00622    *  Further details:
00623    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch32.html
00624    */
00625   template<typename _Tp, 
00626        typename _Poolp = __common_pool_policy<__pool, __thread_default> >
00627     class __mt_alloc : public __mt_alloc_base<_Tp>
00628     {
00629     public:
00630       typedef size_t                        size_type;
00631       typedef ptrdiff_t                     difference_type;
00632       typedef _Tp*                          pointer;
00633       typedef const _Tp*                    const_pointer;
00634       typedef _Tp&                          reference;
00635       typedef const _Tp&                    const_reference;
00636       typedef _Tp                           value_type;
00637       typedef _Poolp                __policy_type;
00638       typedef typename _Poolp::pool_type    __pool_type;
00639 
00640       template<typename _Tp1, typename _Poolp1 = _Poolp>
00641         struct rebind
00642         { 
00643       typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
00644       typedef __mt_alloc<_Tp1, pol_type> other;
00645     };
00646 
00647       __mt_alloc() throw() { }
00648 
00649       __mt_alloc(const __mt_alloc&) throw() { }
00650 
00651       template<typename _Tp1, typename _Poolp1>
00652         __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>&) throw() { }
00653 
00654       ~__mt_alloc() throw() { }
00655 
00656       pointer
00657       allocate(size_type __n, const void* = 0);
00658 
00659       void
00660       deallocate(pointer __p, size_type __n);
00661 
00662       const __pool_base::_Tune
00663       _M_get_options()
00664       { 
00665     // Return a copy, not a reference, for external consumption.
00666     return __policy_type::_S_get_pool()._M_get_options();
00667       }
00668       
00669       void
00670       _M_set_options(__pool_base::_Tune __t)
00671       { __policy_type::_S_get_pool()._M_set_options(__t); }
00672     };
00673 
00674   template<typename _Tp, typename _Poolp>
00675     typename __mt_alloc<_Tp, _Poolp>::pointer
00676     __mt_alloc<_Tp, _Poolp>::
00677     allocate(size_type __n, const void*)
00678     {
00679       if (__n > this->max_size())
00680     std::__throw_bad_alloc();
00681 
00682       __policy_type::_S_initialize_once();
00683 
00684       // Requests larger than _M_max_bytes are handled by operator
00685       // new/delete directly.
00686       __pool_type& __pool = __policy_type::_S_get_pool();
00687       const size_t __bytes = __n * sizeof(_Tp);
00688       if (__pool._M_check_threshold(__bytes))
00689     {
00690       void* __ret = ::operator new(__bytes);
00691       return static_cast<_Tp*>(__ret);
00692     }
00693       
00694       // Round up to power of 2 and figure out which bin to use.
00695       const size_t __which = __pool._M_get_binmap(__bytes);
00696       const size_t __thread_id = __pool._M_get_thread_id();
00697       
00698       // Find out if we have blocks on our freelist.  If so, go ahead
00699       // and use them directly without having to lock anything.
00700       char* __c;
00701       typedef typename __pool_type::_Bin_record _Bin_record;
00702       const _Bin_record& __bin = __pool._M_get_bin(__which);
00703       if (__bin._M_first[__thread_id])
00704     {
00705       // Already reserved.
00706       typedef typename __pool_type::_Block_record _Block_record;
00707       _Block_record* __block = __bin._M_first[__thread_id];
00708       __bin._M_first[__thread_id] = __block->_M_next;
00709       
00710       __pool._M_adjust_freelist(__bin, __block, __thread_id);
00711       __c = reinterpret_cast<char*>(__block) + __pool._M_get_align();
00712     }
00713       else
00714     {
00715       // Null, reserve.
00716       __c = __pool._M_reserve_block(__bytes, __thread_id);
00717     }
00718       return static_cast<_Tp*>(static_cast<void*>(__c));
00719     }
00720   
00721   template<typename _Tp, typename _Poolp>
00722     void
00723     __mt_alloc<_Tp, _Poolp>::
00724     deallocate(pointer __p, size_type __n)
00725     {
00726       if (__builtin_expect(__p != 0, true))
00727     {
00728       // Requests larger than _M_max_bytes are handled by
00729       // operators new/delete directly.
00730       __pool_type& __pool = __policy_type::_S_get_pool();
00731       const size_t __bytes = __n * sizeof(_Tp);
00732       if (__pool._M_check_threshold(__bytes))
00733         ::operator delete(__p);
00734       else
00735         __pool._M_reclaim_block(reinterpret_cast<char*>(__p), __bytes);
00736     }
00737     }
00738   
00739   template<typename _Tp, typename _Poolp>
00740     inline bool
00741     operator==(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
00742     { return true; }
00743   
00744   template<typename _Tp, typename _Poolp>
00745     inline bool
00746     operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
00747     { return false; }
00748 
00749 #undef __thread_default
00750 
00751 _GLIBCXX_END_NAMESPACE_VERSION
00752 } // namespace
00753 
00754 #endif