# mt_allocator.h

Go to the documentation of this file.

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