libstdc++-v3/include/ext/mt_allocator.h

   1 // MT-optimized allocator -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file ext/mt_allocator.h
  31  *  This file is a GNU extension to the Standard C++ Library.
  32  *  You should only include this header if you are using GCC 3 or later.
  33  */
  34
  35 #ifndef _MT_ALLOCATOR_H
  36 #define _MT_ALLOCATOR_H 1
  37
  38 #include <new>
  39 #include <cstdlib>
  40 #include <bits/functexcept.h>
  41 #include <bits/gthr.h>
  42 #include <bits/atomicity.h>
  43
  44 namespace __gnu_cxx
  45 {
  46   /**
  47    *  This is a fixed size (power of 2) allocator which - when
  48    *  compiled with thread support - will maintain one freelist per
  49    *  size per thread plus a "global" one. Steps are taken to limit
  50    *  the per thread freelist sizes (by returning excess back to
  51    *  "global").
  52    *
  53    *  Further details:
  54    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html
  55    */
  56   typedef void (*__destroy_handler)(void*);
  57   typedef void (*__create_handler)(void);
  58
  59   struct __pool_base
  60   {
  61     // Using short int as type for the binmap implies we are never
  62     // caching blocks larger than 65535 with this allocator.
  63     typedef unsigned short int _Binmap_type;
  64
  65     // Variables used to configure the behavior of the allocator,
  66     // assigned and explained in detail below.
  67     struct _Tune
  68     {
  69       // Compile time constants for the default _Tune values.
  70       enum { _S_align = 8 };
  71       enum { _S_max_bytes = 128 };
  72       enum { _S_min_bin = 8 };
  73       enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
  74       enum { _S_max_threads = 4096 };
  75       enum { _S_freelist_headroom = 10 };
  76
  77       // Alignment needed.
  78       // NB: In any case must be >= sizeof(_Block_record), that
  79       // is 4 on 32 bit machines and 8 on 64 bit machines.
  80       size_t    _M_align;
  81
  82       // Allocation requests (after round-up to power of 2) below
  83       // this value will be handled by the allocator. A raw new/
  84       // call will be used for requests larger than this value.
  85       size_t    _M_max_bytes;
  86
  87       // Size in bytes of the smallest bin.
  88       // NB: Must be a power of 2 and >= _M_align.
  89       size_t    _M_min_bin;
  90
  91       // In order to avoid fragmenting and minimize the number of
  92       // new() calls we always request new memory using this
  93       // value. Based on previous discussions on the libstdc++
  94       // mailing list we have choosen the value below.
  95       // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
  96       size_t    _M_chunk_size;
  97
  98       // The maximum number of supported threads. For
  99       // single-threaded operation, use one. Maximum values will
 100       // vary depending on details of the underlying system. (For
 101       // instance, Linux 2.4.18 reports 4070 in
 102       // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports
 103       // 65534)
 104       size_t    _M_max_threads;
 105
 106       // Each time a deallocation occurs in a threaded application
 107       // we make sure that there are no more than
 108       // _M_freelist_headroom % of used memory on the freelist. If
 109       // the number of additional records is more than
 110       // _M_freelist_headroom % of the freelist, we move these
 111       // records back to the global pool.
 112       size_t    _M_freelist_headroom;
 113
 114       // Set to true forces all allocations to use new().
 115       bool      _M_force_new;
 116
 117       explicit
 118       _Tune()
 119       : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),
 120       _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads),
 121       _M_freelist_headroom(_S_freelist_headroom),
 122       _M_force_new(getenv("GLIBCXX_FORCE_NEW") ? true : false)
 123       { }
 124
 125       explicit
 126       _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk,
 127             size_t __maxthreads, size_t __headroom, bool __force)
 128       : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),
 129       _M_chunk_size(__chunk), _M_max_threads(__maxthreads),
 130       _M_freelist_headroom(__headroom), _M_force_new(__force)
 131       { }
 132
 133       bool
 134       is_default() const
 135       {
 136         bool __ret = true;
 137         __ret &= _M_align == _S_align;
 138         __ret &= _M_max_bytes == _S_max_bytes;
 139         __ret &= _M_min_bin == _S_min_bin;
 140         __ret &= _M_chunk_size == _S_chunk_size;
 141         __ret &= _M_max_threads == _S_max_threads;
 142         __ret &= _M_freelist_headroom == _S_freelist_headroom;
 143         return __ret;
 144       }
 145     };
 146
 147     struct _Block_address
 148     {
 149       void*                     _M_initial;
 150       _Block_address*           _M_next;
 151     };
 152
 153     const _Tune&
 154     _M_get_options() const
 155     { return _M_options; }
 156
 157     void
 158     _M_set_options(_Tune __t)
 159     {
 160       if (!_M_init)
 161         _M_options = __t;
 162     }
 163
 164     bool
 165     _M_check_threshold(size_t __bytes)
 166     { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }
 167
 168     size_t
 169     _M_get_binmap(size_t __bytes)
 170     { return _M_binmap[__bytes]; }
 171
 172     const size_t
 173     _M_get_align()
 174     { return _M_options._M_align; }
 175
 176     explicit __pool_base()
 177     : _M_options(_Tune()), _M_binmap(NULL), _M_init(false) { }
 178
 179     explicit __pool_base(const _Tune& __tune)
 180     : _M_options(__tune), _M_binmap(NULL), _M_init(false) { }
 181
 182   protected:
 183     // Configuration options.
 184     _Tune                       _M_options;
 185
 186     _Binmap_type*               _M_binmap;
 187
 188     // We need to create the initial lists and set up some variables
 189     // before we can answer to the first request for memory.
 190     bool                        _M_init;
 191   };
 192
 193   // Data describing the underlying memory pool, parameterized on
 194   // threading support.
 195   template<bool _Thread>
 196     class __pool;
 197
 198   template<>
 199     class __pool<true>;
 200
 201   template<>
 202     class __pool<false>;
 203
 204
 205 #ifdef __GTHREADS
 206   // Specialization for thread enabled, via gthreads.h.
 207   template<>
 208     class __pool<true> : public __pool_base
 209     {
 210     public:
 211       // Each requesting thread is assigned an id ranging from 1 to
 212       // _S_max_threads. Thread id 0 is used as a global memory pool.
 213       // In order to get constant performance on the thread assignment
 214       // routine, we keep a list of free ids. When a thread first
 215       // requests memory we remove the first record in this list and
 216       // stores the address in a __gthread_key. When initializing the
 217       // __gthread_key we specify a destructor. When this destructor
 218       // (i.e. the thread dies) is called, we return the thread id to
 219       // the front of this list.
 220       struct _Thread_record
 221       {
 222         // Points to next free thread id record. NULL if last record in list.
 223         _Thread_record* volatile        _M_next;
 224
 225         // Thread id ranging from 1 to _S_max_threads.
 226         size_t                          _M_id;
 227       };
 228
 229       union _Block_record
 230       {
 231         // Points to the block_record of the next free block.
 232         _Block_record* volatile         _M_next;
 233
 234         // The thread id of the thread which has requested this block.
 235         size_t                          _M_thread_id;
 236       };
 237
 238       struct _Bin_record
 239       {
 240         // An "array" of pointers to the first free block for each
 241         // thread id. Memory to this "array" is allocated in
 242         // _S_initialize() for _S_max_threads + global pool 0.
 243         _Block_record** volatile        _M_first;
 244
 245         // A list of the initial addresses of all allocated blocks.
 246         _Block_address*                 _M_address;
 247
 248         // An "array" of counters used to keep track of the amount of
 249         // blocks that are on the freelist/used for each thread id.
 250         // Memory to these "arrays" is allocated in _S_initialize() for
 251         // _S_max_threads + global pool 0.
 252         size_t* volatile                _M_free;
 253         size_t* volatile                _M_used;
 254
 255         // Each bin has its own mutex which is used to ensure data
 256         // integrity while changing "ownership" on a block.  The mutex
 257         // is initialized in _S_initialize().
 258         __gthread_mutex_t*              _M_mutex;
 259       };
 260
 261       void
 262       _M_initialize(__destroy_handler __d);
 263
 264       void
 265       _M_initialize_once(__create_handler __c)
 266       {
 267         // Although the test in __gthread_once() would suffice, we
 268         // wrap test of the once condition in our own unlocked
 269         // check. This saves one function call to pthread_once()
 270         // (which itself only tests for the once value unlocked anyway
 271         // and immediately returns if set)
 272         if (__builtin_expect(_M_init == false, false))
 273           {
 274             if (__gthread_active_p())
 275               __gthread_once(&_M_once, __c);
 276             if (!_M_init)
 277               __c();
 278           }
 279       }
 280
 281       void
 282       _M_destroy() throw();
 283
 284       char*
 285       _M_reserve_block(size_t __bytes, const size_t __thread_id);
 286
 287       void
 288       _M_reclaim_block(char* __p, size_t __bytes);
 289
 290       const _Bin_record&
 291       _M_get_bin(size_t __which)
 292       { return _M_bin[__which]; }
 293
 294       void
 295       _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block,
 296                          size_t __thread_id)
 297       {
 298         if (__gthread_active_p())
 299           {
 300             __block->_M_thread_id = __thread_id;
 301             --__bin._M_free[__thread_id];
 302             ++__bin._M_used[__thread_id];
 303           }
 304       }
 305
 306       void
 307       _M_destroy_thread_key(void* __freelist_pos);
 308
 309       size_t
 310       _M_get_thread_id();
 311
 312       explicit __pool()
 313       : _M_bin(NULL), _M_bin_size(1), _M_thread_freelist(NULL)
 314       {
 315         // On some platforms, __gthread_once_t is an aggregate.
 316         __gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
 317         _M_once = __tmp;
 318       }
 319
 320       explicit __pool(const __pool_base::_Tune& __tune)
 321       : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1),
 322       _M_thread_freelist(NULL)
 323       {
 324         // On some platforms, __gthread_once_t is an aggregate.
 325         __gthread_once_t __tmp = __GTHREAD_ONCE_INIT;
 326         _M_once = __tmp;
 327       }
 328
 329       ~__pool() { }
 330
 331     private:
 332       // An "array" of bin_records each of which represents a specific
 333       // power of 2 size. Memory to this "array" is allocated in
 334       // _M_initialize().
 335       _Bin_record* volatile     _M_bin;
 336
 337       // Actual value calculated in _M_initialize().
 338       size_t                    _M_bin_size;
 339
 340       __gthread_once_t          _M_once;
 341
 342       _Thread_record*           _M_thread_freelist;
 343       void*                     _M_thread_freelist_initial;
 344     };
 345 #endif
 346
 347   // Specialization for single thread.
 348   template<>
 349     class __pool<false> : public __pool_base
 350     {
 351     public:
 352       union _Block_record
 353       {
 354         // Points to the block_record of the next free block.
 355         _Block_record* volatile         _M_next;
 356       };
 357
 358       struct _Bin_record
 359       {
 360         // An "array" of pointers to the first free block.
 361         _Block_record** volatile        _M_first;
 362
 363         // A list of the initial addresses of all allocated blocks.
 364         _Block_address*                 _M_address;
 365       };
 366
 367       void
 368       _M_initialize_once()
 369       {
 370         if (__builtin_expect(_M_init == false, false))
 371           _M_initialize();
 372       }
 373
 374       void
 375       _M_destroy() throw();
 376
 377       char*
 378       _M_reserve_block(size_t __bytes, const size_t __thread_id);
 379
 380       void
 381       _M_reclaim_block(char* __p, size_t __bytes);
 382
 383       size_t
 384       _M_get_thread_id() { return 0; }
 385
 386       const _Bin_record&
 387       _M_get_bin(size_t __which)
 388       { return _M_bin[__which]; }
 389
 390       void
 391       _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)
 392       { }
 393
 394       explicit __pool()
 395       : _M_bin(NULL), _M_bin_size(1) { }
 396
 397       explicit __pool(const __pool_base::_Tune& __tune)
 398       : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1) { }
 399
 400       ~__pool() { }
 401
 402     private:
 403       // An "array" of bin_records each of which represents a specific
 404       // power of 2 size. Memory to this "array" is allocated in
 405       // _M_initialize().
 406       _Bin_record* volatile     _M_bin;
 407
 408       // Actual value calculated in _M_initialize().
 409       size_t                    _M_bin_size;
 410
 411       void
 412       _M_initialize();
 413   };
 414
 415   template<bool _Thread>
 416     struct __common_pool_policy
 417     {
 418       typedef __pool<_Thread> __pool_type;
 419
 420       template<typename _Tp1, bool _Thread1 = _Thread>
 421         struct _M_rebind;
 422
 423       template<typename _Tp1>
 424         struct _M_rebind<_Tp1, true>
 425         { typedef __common_pool_policy<true> other; };
 426
 427       template<typename _Tp1>
 428         struct _M_rebind<_Tp1, false>
 429         { typedef __common_pool_policy<false> other; };
 430
 431       static __pool_type&
 432       _S_get_pool()
 433       {
 434         static __pool_type _S_pool;
 435         return _S_pool;
 436       }
 437
 438       static void
 439       _S_initialize_once()
 440       {
 441         static bool __init;
 442         if (__builtin_expect(__init == false, false))
 443           {
 444             _S_get_pool()._M_initialize_once();
 445             __init = true;
 446           }
 447       }
 448     };
 449
 450   template<>
 451     struct __common_pool_policy<true>;
 452
 453 #ifdef __GTHREADS
 454   template<>
 455     struct __common_pool_policy<true>
 456     {
 457       typedef __pool<true> __pool_type;
 458
 459       template<typename _Tp1, bool _Thread1 = true>
 460         struct _M_rebind;
 461
 462       template<typename _Tp1>
 463         struct _M_rebind<_Tp1, true>
 464         { typedef __common_pool_policy<true> other; };
 465
 466       template<typename _Tp1>
 467         struct _M_rebind<_Tp1, false>
 468         { typedef __common_pool_policy<false> other; };
 469
 470       static __pool_type&
 471       _S_get_pool()
 472       {
 473         static __pool_type _S_pool;
 474         return _S_pool;
 475       }
 476
 477       static void
 478       _S_destroy_thread_key(void* __freelist_pos)
 479       { _S_get_pool()._M_destroy_thread_key(__freelist_pos); }
 480
 481       static void
 482       _S_initialize()
 483       { _S_get_pool()._M_initialize(_S_destroy_thread_key); }
 484
 485       static void
 486       _S_initialize_once()
 487       {
 488         static bool __init;
 489         if (__builtin_expect(__init == false, false))
 490           {
 491             _S_get_pool()._M_initialize_once(_S_initialize);
 492             __init = true;
 493           }
 494       }
 495    };
 496 #endif
 497
 498
 499   template<typename _Tp, bool _Thread>
 500     struct __per_type_pool_policy
 501     {
 502       typedef __pool<_Thread> __pool_type;
 503
 504       template<typename _Tp1, bool _Thread1 = _Thread>
 505         struct _M_rebind;
 506
 507       template<typename _Tp1>
 508         struct _M_rebind<_Tp1, false>
 509         { typedef __per_type_pool_policy<_Tp1, false> other; };
 510
 511       template<typename _Tp1>
 512         struct _M_rebind<_Tp1, true>
 513         { typedef __per_type_pool_policy<_Tp1, true> other; };
 514
 515       // Avoid static initialization ordering issues.
 516       static __pool_type&
 517       _S_get_pool()
 518       {
 519         // Sane defaults for the __pool_type.
 520         const static size_t __align = __alignof__(_Tp) >= sizeof(typename __pool_type::_Block_record) ? __alignof__(_Tp) : sizeof(typename __pool_type::_Block_record);
 521         static __pool_base::_Tune _S_tune(__align, sizeof(_Tp) * 128, (sizeof(_Tp) * 2) >= __align ? sizeof(_Tp) * 2 : __align, __pool_type::_Tune::_S_chunk_size, __pool_type::_Tune::_S_max_threads, __pool_type::_Tune::_S_freelist_headroom, getenv("GLIBCXX_FORCE_NEW") ? true : false);
 522         static __pool_type _S_pool(_S_tune);
 523         return _S_pool;
 524       }
 525
 526       static void
 527       _S_initialize_once()
 528       {
 529         static bool __init;
 530         if (__builtin_expect(__init == false, false))
 531           {
 532             _S_get_pool()._M_initialize_once();
 533             __init = true;
 534           }
 535       }
 536     };
 537
 538   template<typename _Tp>
 539     struct __per_type_pool_policy<_Tp, true>;
 540
 541 #ifdef __GTHREADS
 542   template<typename _Tp>
 543     struct __per_type_pool_policy<_Tp, true>
 544     {
 545       typedef __pool<true> __pool_type;
 546
 547       template<typename _Tp1, bool _Thread1 = true>
 548         struct _M_rebind;
 549
 550       template<typename _Tp1>
 551         struct _M_rebind<_Tp1, false>
 552         { typedef __per_type_pool_policy<_Tp1, false> other; };
 553
 554       template<typename _Tp1>
 555         struct _M_rebind<_Tp1, true>
 556         { typedef __per_type_pool_policy<_Tp1, true> other; };
 557
 558       // Avoid static initialization ordering issues.
 559       static __pool_type&
 560       _S_get_pool( )
 561       {
 562         // Sane defaults for the __pool_type.
 563         const static size_t __align = __alignof__(_Tp) >= sizeof(typename __pool_type::_Block_record) ? __alignof__(_Tp) : sizeof(typename __pool_type::_Block_record);
 564         static __pool_base::_Tune _S_tune(__align, sizeof(_Tp) * 128, (sizeof(_Tp) * 2) >= __align ? sizeof(_Tp) * 2 : __align, __pool_type::_Tune::_S_chunk_size, __pool_type::_Tune::_S_max_threads, __pool_type::_Tune::_S_freelist_headroom, getenv("GLIBCXX_FORCE_NEW") ? true : false);
 565         static __pool_type _S_pool(_S_tune);
 566         return _S_pool;
 567       }
 568
 569       static void
 570       _S_destroy_thread_key(void* __freelist_pos)
 571       { _S_get_pool()._M_destroy_thread_key(__freelist_pos); }
 572
 573       static void
 574       _S_initialize()
 575       { _S_get_pool()._M_initialize(_S_destroy_thread_key); }
 576
 577       static void
 578       _S_initialize_once()
 579       {
 580         static bool __init;
 581         if (__builtin_expect(__init == false, false))
 582           {
 583             _S_get_pool()._M_initialize_once(_S_initialize);
 584             __init = true;
 585           }
 586       }
 587     };
 588 #endif
 589
 590   template<typename _Tp>
 591     class __mt_alloc_base
 592     {
 593     public:
 594       typedef size_t                    size_type;
 595       typedef ptrdiff_t                 difference_type;
 596       typedef _Tp*                      pointer;
 597       typedef const _Tp*                const_pointer;
 598       typedef _Tp&                      reference;
 599       typedef const _Tp&                const_reference;
 600       typedef _Tp                       value_type;
 601
 602       pointer
 603       address(reference __x) const
 604       { return &__x; }
 605
 606       const_pointer
 607       address(const_reference __x) const
 608       { return &__x; }
 609
 610       size_type
 611       max_size() const throw()
 612       { return size_t(-1) / sizeof(_Tp); }
 613
 614       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 615       // 402. wrong new expression in [some_] allocator::construct
 616       void
 617       construct(pointer __p, const _Tp& __val)
 618       { ::new(__p) _Tp(__val); }
 619
 620       void
 621       destroy(pointer __p) { __p->~_Tp(); }
 622     };
 623
 624 #ifdef __GTHREADS
 625 #define __default_policy __common_pool_policy<true>
 626 #else
 627 #define __default_policy __common_pool_policy<false>
 628 #endif
 629
 630   template<typename _Tp, typename _Poolp = __default_policy>
 631     class __mt_alloc : public __mt_alloc_base<_Tp>, _Poolp
 632     {
 633     public:
 634       typedef size_t                            size_type;
 635       typedef ptrdiff_t                         difference_type;
 636       typedef _Tp*                              pointer;
 637       typedef const _Tp*                        const_pointer;
 638       typedef _Tp&                              reference;
 639       typedef const _Tp&                        const_reference;
 640       typedef _Tp                               value_type;
 641       typedef _Poolp                            __policy_type;
 642       typedef typename _Poolp::__pool_type      __pool_type;
 643
 644       template<typename _Tp1, typename _Poolp1 = _Poolp>
 645         struct rebind
 646         {
 647           typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
 648           typedef __mt_alloc<_Tp1, pol_type> other;
 649         };
 650
 651       __mt_alloc() throw()
 652       { __policy_type::_S_get_pool(); }
 653
 654       __mt_alloc(const __mt_alloc&) throw()
 655       { __policy_type::_S_get_pool(); }
 656
 657       template<typename _Tp1, typename _Poolp1>
 658         __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>& obj) throw()
 659         { __policy_type::_S_get_pool(); }
 660
 661       ~__mt_alloc() throw() { }
 662
 663       pointer
 664       allocate(size_type __n, const void* = 0);
 665
 666       void
 667       deallocate(pointer __p, size_type __n);
 668
 669       const __pool_base::_Tune
 670       _M_get_options()
 671       {
 672         // Return a copy, not a reference, for external consumption.
 673         return __pool_base::_Tune(this->_S_get_pool()._M_get_options());
 674       }
 675
 676       void
 677       _M_set_options(__pool_base::_Tune __t)
 678       { this->_S_get_pool()._M_set_options(__t); }
 679     };
 680
 681   template<typename _Tp, typename _Poolp>
 682     typename __mt_alloc<_Tp, _Poolp>::pointer
 683     __mt_alloc<_Tp, _Poolp>::
 684     allocate(size_type __n, const void*)
 685     {
 686       this->_S_initialize_once();
 687
 688       if (__builtin_expect(__n > this->max_size(), false))
 689         std::__throw_bad_alloc();
 690
 691       // Requests larger than _M_max_bytes are handled by operator
 692       // new/delete directly.
 693       __pool_type& __pool = this->_S_get_pool();
 694       const size_t __bytes = __n * sizeof(_Tp);
 695       if (__pool._M_check_threshold(__bytes))
 696         {
 697           void* __ret = ::operator new(__bytes);
 698           return static_cast<_Tp*>(__ret);
 699         }
 700
 701       // Round up to power of 2 and figure out which bin to use.
 702       const size_t __which = __pool._M_get_binmap(__bytes);
 703       const size_t __thread_id = __pool._M_get_thread_id();
 704
 705       // Find out if we have blocks on our freelist.  If so, go ahead
 706       // and use them directly without having to lock anything.
 707       char* __c;
 708       typedef typename __pool_type::_Bin_record _Bin_record;
 709       const _Bin_record& __bin = __pool._M_get_bin(__which);
 710       if (__bin._M_first[__thread_id])
 711         {
 712           // Already reserved.
 713           typedef typename __pool_type::_Block_record _Block_record;
 714           _Block_record* __block = __bin._M_first[__thread_id];
 715           __bin._M_first[__thread_id] = __block->_M_next;
 716
 717           __pool._M_adjust_freelist(__bin, __block, __thread_id);
 718           __c = reinterpret_cast<char*>(__block) + __pool._M_get_align();
 719         }
 720       else
 721         {
 722           // Null, reserve.
 723           __c = __pool._M_reserve_block(__bytes, __thread_id);
 724         }
 725       return static_cast<_Tp*>(static_cast<void*>(__c));
 726     }
 727
 728   template<typename _Tp, typename _Poolp>
 729     void
 730     __mt_alloc<_Tp, _Poolp>::
 731     deallocate(pointer __p, size_type __n)
 732     {
 733       if (__builtin_expect(__p != 0, true))
 734         {
 735           // Requests larger than _M_max_bytes are handled by
 736           // operators new/delete directly.
 737           __pool_type& __pool = this->_S_get_pool();
 738           const size_t __bytes = __n * sizeof(_Tp);
 739           if (__pool._M_check_threshold(__bytes))
 740             ::operator delete(__p);
 741           else
 742             __pool._M_reclaim_block(reinterpret_cast<char*>(__p), __bytes);
 743         }
 744     }
 745
 746   template<typename _Tp, typename _Poolp>
 747     inline bool
 748     operator==(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
 749     { return true; }
 750
 751   template<typename _Tp, typename _Poolp>
 752     inline bool
 753     operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
 754     { return false; }
 755
 756 #undef __default_policy
 757 } // namespace __gnu_cxx
 758
 759 #endif