contrib/gcc-4.0/libstdc++-v3/include/ext/mt_allocator.h

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