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

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