1132720Skan// MT-optimized allocator -*- C++ -*- 2132720Skan 3169691Skan// Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 4132720Skan// 5132720Skan// This file is part of the GNU ISO C++ Library. This library is free 6132720Skan// software; you can redistribute it and/or modify it under the 7132720Skan// terms of the GNU General Public License as published by the 8132720Skan// Free Software Foundation; either version 2, or (at your option) 9132720Skan// any later version. 10132720Skan 11132720Skan// This library is distributed in the hope that it will be useful, 12132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14132720Skan// GNU General Public License for more details. 15132720Skan 16132720Skan// You should have received a copy of the GNU General Public License along 17132720Skan// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19132720Skan// USA. 20132720Skan 21132720Skan// As a special exception, you may use this file as part of a free software 22132720Skan// library without restriction. Specifically, if other files instantiate 23132720Skan// templates or use macros or inline functions from this file, or you compile 24132720Skan// this file and link it with other files to produce an executable, this 25132720Skan// file does not by itself cause the resulting executable to be covered by 26132720Skan// the GNU General Public License. This exception does not however 27132720Skan// invalidate any other reasons why the executable file might be covered by 28132720Skan// the GNU General Public License. 29132720Skan 30132720Skan/** @file ext/mt_allocator.h 31132720Skan * This file is a GNU extension to the Standard C++ Library. 32132720Skan */ 33132720Skan 34132720Skan#ifndef _MT_ALLOCATOR_H 35132720Skan#define _MT_ALLOCATOR_H 1 36132720Skan 37132720Skan#include <new> 38132720Skan#include <cstdlib> 39132720Skan#include <bits/functexcept.h> 40169691Skan#include <ext/atomicity.h> 41132720Skan 42169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 43132720Skan 44169691Skan using std::size_t; 45169691Skan using std::ptrdiff_t; 46132720Skan 47169691Skan typedef void (*__destroy_handler)(void*); 48132720Skan 49169691Skan /// @brief Base class for pool object. 50169691Skan struct __pool_base 51169691Skan { 52169691Skan // Using short int as type for the binmap implies we are never 53169691Skan // caching blocks larger than 32768 with this allocator. 54169691Skan typedef unsigned short int _Binmap_type; 55132720Skan 56169691Skan // Variables used to configure the behavior of the allocator, 57169691Skan // assigned and explained in detail below. 58169691Skan struct _Tune 59169691Skan { 60169691Skan // Compile time constants for the default _Tune values. 61169691Skan enum { _S_align = 8 }; 62169691Skan enum { _S_max_bytes = 128 }; 63169691Skan enum { _S_min_bin = 8 }; 64169691Skan enum { _S_chunk_size = 4096 - 4 * sizeof(void*) }; 65169691Skan enum { _S_max_threads = 4096 }; 66169691Skan enum { _S_freelist_headroom = 10 }; 67132720Skan 68169691Skan // Alignment needed. 69169691Skan // NB: In any case must be >= sizeof(_Block_record), that 70169691Skan // is 4 on 32 bit machines and 8 on 64 bit machines. 71169691Skan size_t _M_align; 72169691Skan 73169691Skan // Allocation requests (after round-up to power of 2) below 74169691Skan // this value will be handled by the allocator. A raw new/ 75169691Skan // call will be used for requests larger than this value. 76169691Skan // NB: Must be much smaller than _M_chunk_size and in any 77169691Skan // case <= 32768. 78169691Skan size_t _M_max_bytes; 79132720Skan 80169691Skan // Size in bytes of the smallest bin. 81169691Skan // NB: Must be a power of 2 and >= _M_align (and of course 82169691Skan // much smaller than _M_max_bytes). 83169691Skan size_t _M_min_bin; 84132720Skan 85169691Skan // In order to avoid fragmenting and minimize the number of 86169691Skan // new() calls we always request new memory using this 87169691Skan // value. Based on previous discussions on the libstdc++ 88169691Skan // mailing list we have choosen the value below. 89169691Skan // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html 90169691Skan // NB: At least one order of magnitude > _M_max_bytes. 91169691Skan size_t _M_chunk_size; 92132720Skan 93169691Skan // The maximum number of supported threads. For 94169691Skan // single-threaded operation, use one. Maximum values will 95169691Skan // vary depending on details of the underlying system. (For 96169691Skan // instance, Linux 2.4.18 reports 4070 in 97169691Skan // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports 98169691Skan // 65534) 99169691Skan size_t _M_max_threads; 100132720Skan 101169691Skan // Each time a deallocation occurs in a threaded application 102169691Skan // we make sure that there are no more than 103169691Skan // _M_freelist_headroom % of used memory on the freelist. If 104169691Skan // the number of additional records is more than 105169691Skan // _M_freelist_headroom % of the freelist, we move these 106169691Skan // records back to the global pool. 107169691Skan size_t _M_freelist_headroom; 108169691Skan 109169691Skan // Set to true forces all allocations to use new(). 110169691Skan bool _M_force_new; 111169691Skan 112169691Skan explicit 113169691Skan _Tune() 114169691Skan : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin), 115169691Skan _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads), 116169691Skan _M_freelist_headroom(_S_freelist_headroom), 117169691Skan _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false) 118169691Skan { } 119132720Skan 120169691Skan explicit 121169691Skan _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk, 122169691Skan size_t __maxthreads, size_t __headroom, bool __force) 123169691Skan : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin), 124169691Skan _M_chunk_size(__chunk), _M_max_threads(__maxthreads), 125169691Skan _M_freelist_headroom(__headroom), _M_force_new(__force) 126169691Skan { } 127169691Skan }; 128169691Skan 129169691Skan struct _Block_address 130169691Skan { 131169691Skan void* _M_initial; 132169691Skan _Block_address* _M_next; 133169691Skan }; 134169691Skan 135169691Skan const _Tune& 136169691Skan _M_get_options() const 137169691Skan { return _M_options; } 138132720Skan 139169691Skan void 140169691Skan _M_set_options(_Tune __t) 141169691Skan { 142169691Skan if (!_M_init) 143169691Skan _M_options = __t; 144169691Skan } 145132720Skan 146169691Skan bool 147169691Skan _M_check_threshold(size_t __bytes) 148169691Skan { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; } 149132720Skan 150169691Skan size_t 151169691Skan _M_get_binmap(size_t __bytes) 152169691Skan { return _M_binmap[__bytes]; } 153132720Skan 154169691Skan const size_t 155169691Skan _M_get_align() 156169691Skan { return _M_options._M_align; } 157132720Skan 158169691Skan explicit 159169691Skan __pool_base() 160169691Skan : _M_options(_Tune()), _M_binmap(NULL), _M_init(false) { } 161132720Skan 162169691Skan explicit 163169691Skan __pool_base(const _Tune& __options) 164169691Skan : _M_options(__options), _M_binmap(NULL), _M_init(false) { } 165132720Skan 166169691Skan private: 167169691Skan explicit 168169691Skan __pool_base(const __pool_base&); 169132720Skan 170169691Skan __pool_base& 171169691Skan operator=(const __pool_base&); 172132720Skan 173169691Skan protected: 174169691Skan // Configuration options. 175169691Skan _Tune _M_options; 176169691Skan 177169691Skan _Binmap_type* _M_binmap; 178132720Skan 179169691Skan // Configuration of the pool object via _M_options can happen 180169691Skan // after construction but before initialization. After 181169691Skan // initialization is complete, this variable is set to true. 182169691Skan bool _M_init; 183169691Skan }; 184132720Skan 185132720Skan 186169691Skan /** 187169691Skan * @brief Data describing the underlying memory pool, parameterized on 188169691Skan * threading support. 189169691Skan */ 190169691Skan template<bool _Thread> 191169691Skan class __pool; 192132720Skan 193169691Skan /// Specialization for single thread. 194169691Skan template<> 195169691Skan class __pool<false> : public __pool_base 196169691Skan { 197169691Skan public: 198169691Skan union _Block_record 199169691Skan { 200169691Skan // Points to the block_record of the next free block. 201169691Skan _Block_record* _M_next; 202169691Skan }; 203132720Skan 204169691Skan struct _Bin_record 205169691Skan { 206169691Skan // An "array" of pointers to the first free block. 207169691Skan _Block_record** _M_first; 208132720Skan 209169691Skan // A list of the initial addresses of all allocated blocks. 210169691Skan _Block_address* _M_address; 211169691Skan }; 212169691Skan 213169691Skan void 214169691Skan _M_initialize_once() 215169691Skan { 216169691Skan if (__builtin_expect(_M_init == false, false)) 217169691Skan _M_initialize(); 218132720Skan } 219132720Skan 220169691Skan void 221169691Skan _M_destroy() throw(); 222132720Skan 223169691Skan char* 224169691Skan _M_reserve_block(size_t __bytes, const size_t __thread_id); 225169691Skan 226169691Skan void 227169691Skan _M_reclaim_block(char* __p, size_t __bytes); 228169691Skan 229169691Skan size_t 230169691Skan _M_get_thread_id() { return 0; } 231169691Skan 232169691Skan const _Bin_record& 233169691Skan _M_get_bin(size_t __which) 234169691Skan { return _M_bin[__which]; } 235169691Skan 236169691Skan void 237169691Skan _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t) 238169691Skan { } 239169691Skan 240169691Skan explicit __pool() 241169691Skan : _M_bin(NULL), _M_bin_size(1) { } 242169691Skan 243169691Skan explicit __pool(const __pool_base::_Tune& __tune) 244169691Skan : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1) { } 245169691Skan 246169691Skan private: 247169691Skan // An "array" of bin_records each of which represents a specific 248169691Skan // power of 2 size. Memory to this "array" is allocated in 249169691Skan // _M_initialize(). 250169691Skan _Bin_record* _M_bin; 251169691Skan 252169691Skan // Actual value calculated in _M_initialize(). 253169691Skan size_t _M_bin_size; 254169691Skan 255169691Skan void 256169691Skan _M_initialize(); 257169691Skan }; 258169691Skan 259169691Skan#ifdef __GTHREADS 260169691Skan /// Specialization for thread enabled, via gthreads.h. 261169691Skan template<> 262169691Skan class __pool<true> : public __pool_base 263169691Skan { 264169691Skan public: 265132720Skan // Each requesting thread is assigned an id ranging from 1 to 266132720Skan // _S_max_threads. Thread id 0 is used as a global memory pool. 267132720Skan // In order to get constant performance on the thread assignment 268132720Skan // routine, we keep a list of free ids. When a thread first 269132720Skan // requests memory we remove the first record in this list and 270132720Skan // stores the address in a __gthread_key. When initializing the 271132720Skan // __gthread_key we specify a destructor. When this destructor 272132720Skan // (i.e. the thread dies) is called, we return the thread id to 273132720Skan // the front of this list. 274132720Skan struct _Thread_record 275132720Skan { 276169691Skan // Points to next free thread id record. NULL if last record in list. 277169691Skan _Thread_record* _M_next; 278169691Skan 279132720Skan // Thread id ranging from 1 to _S_max_threads. 280169691Skan size_t _M_id; 281132720Skan }; 282169691Skan 283132720Skan union _Block_record 284132720Skan { 285132720Skan // Points to the block_record of the next free block. 286169691Skan _Block_record* _M_next; 287169691Skan 288132720Skan // The thread id of the thread which has requested this block. 289169691Skan size_t _M_thread_id; 290132720Skan }; 291169691Skan 292132720Skan struct _Bin_record 293132720Skan { 294132720Skan // An "array" of pointers to the first free block for each 295169691Skan // thread id. Memory to this "array" is allocated in 296169691Skan // _S_initialize() for _S_max_threads + global pool 0. 297169691Skan _Block_record** _M_first; 298169691Skan 299169691Skan // A list of the initial addresses of all allocated blocks. 300169691Skan _Block_address* _M_address; 301132720Skan 302132720Skan // An "array" of counters used to keep track of the amount of 303132720Skan // blocks that are on the freelist/used for each thread id. 304169691Skan // - Note that the second part of the allocated _M_used "array" 305169691Skan // actually hosts (atomic) counters of reclaimed blocks: in 306169691Skan // _M_reserve_block and in _M_reclaim_block those numbers are 307169691Skan // subtracted from the first ones to obtain the actual size 308169691Skan // of the "working set" of the given thread. 309169691Skan // - Memory to these "arrays" is allocated in _S_initialize() 310169691Skan // for _S_max_threads + global pool 0. 311169691Skan size_t* _M_free; 312169691Skan size_t* _M_used; 313169691Skan 314132720Skan // Each bin has its own mutex which is used to ensure data 315132720Skan // integrity while changing "ownership" on a block. The mutex 316132720Skan // is initialized in _S_initialize(). 317169691Skan __gthread_mutex_t* _M_mutex; 318132720Skan }; 319169691Skan 320169691Skan // XXX GLIBCXX_ABI Deprecated 321169691Skan void 322169691Skan _M_initialize(__destroy_handler); 323132720Skan 324169691Skan void 325169691Skan _M_initialize_once() 326169691Skan { 327169691Skan if (__builtin_expect(_M_init == false, false)) 328169691Skan _M_initialize(); 329169691Skan } 330169691Skan 331169691Skan void 332169691Skan _M_destroy() throw(); 333169691Skan 334169691Skan char* 335169691Skan _M_reserve_block(size_t __bytes, const size_t __thread_id); 336169691Skan 337169691Skan void 338169691Skan _M_reclaim_block(char* __p, size_t __bytes); 339169691Skan 340169691Skan const _Bin_record& 341169691Skan _M_get_bin(size_t __which) 342169691Skan { return _M_bin[__which]; } 343169691Skan 344169691Skan void 345259705Spfg _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block_record, 346169691Skan size_t __thread_id) 347169691Skan { 348169691Skan if (__gthread_active_p()) 349169691Skan { 350259705Spfg __block_record->_M_thread_id = __thread_id; 351169691Skan --__bin._M_free[__thread_id]; 352169691Skan ++__bin._M_used[__thread_id]; 353169691Skan } 354169691Skan } 355169691Skan 356169691Skan // XXX GLIBCXX_ABI Deprecated 357169691Skan void 358169691Skan _M_destroy_thread_key(void*); 359169691Skan 360169691Skan size_t 361169691Skan _M_get_thread_id(); 362169691Skan 363169691Skan explicit __pool() 364169691Skan : _M_bin(NULL), _M_bin_size(1), _M_thread_freelist(NULL) 365169691Skan { } 366169691Skan 367169691Skan explicit __pool(const __pool_base::_Tune& __tune) 368169691Skan : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1), 369169691Skan _M_thread_freelist(NULL) 370169691Skan { } 371169691Skan 372169691Skan private: 373132720Skan // An "array" of bin_records each of which represents a specific 374132720Skan // power of 2 size. Memory to this "array" is allocated in 375169691Skan // _M_initialize(). 376169691Skan _Bin_record* _M_bin; 377132720Skan 378169691Skan // Actual value calculated in _M_initialize(). 379169691Skan size_t _M_bin_size; 380169691Skan 381169691Skan _Thread_record* _M_thread_freelist; 382169691Skan void* _M_thread_freelist_initial; 383169691Skan 384169691Skan void 385169691Skan _M_initialize(); 386132720Skan }; 387169691Skan#endif 388132720Skan 389169691Skan template<template <bool> class _PoolTp, bool _Thread> 390169691Skan struct __common_pool 391132720Skan { 392169691Skan typedef _PoolTp<_Thread> pool_type; 393132720Skan 394169691Skan static pool_type& 395169691Skan _S_get_pool() 396169691Skan { 397169691Skan static pool_type _S_pool; 398169691Skan return _S_pool; 399169691Skan } 400169691Skan }; 401132720Skan 402169691Skan template<template <bool> class _PoolTp, bool _Thread> 403169691Skan struct __common_pool_base; 404132720Skan 405169691Skan template<template <bool> class _PoolTp> 406169691Skan struct __common_pool_base<_PoolTp, false> 407169691Skan : public __common_pool<_PoolTp, false> 408169691Skan { 409169691Skan using __common_pool<_PoolTp, false>::_S_get_pool; 410169691Skan 411169691Skan static void 412169691Skan _S_initialize_once() 413169691Skan { 414169691Skan static bool __init; 415169691Skan if (__builtin_expect(__init == false, false)) 416169691Skan { 417169691Skan _S_get_pool()._M_initialize_once(); 418169691Skan __init = true; 419169691Skan } 420169691Skan } 421169691Skan }; 422169691Skan 423132720Skan#ifdef __GTHREADS 424169691Skan template<template <bool> class _PoolTp> 425169691Skan struct __common_pool_base<_PoolTp, true> 426169691Skan : public __common_pool<_PoolTp, true> 427169691Skan { 428169691Skan using __common_pool<_PoolTp, true>::_S_get_pool; 429169691Skan 430169691Skan static void 431169691Skan _S_initialize() 432169691Skan { _S_get_pool()._M_initialize_once(); } 433132720Skan 434169691Skan static void 435169691Skan _S_initialize_once() 436169691Skan { 437169691Skan static bool __init; 438169691Skan if (__builtin_expect(__init == false, false)) 439169691Skan { 440169691Skan if (__gthread_active_p()) 441169691Skan { 442169691Skan // On some platforms, __gthread_once_t is an aggregate. 443169691Skan static __gthread_once_t __once = __GTHREAD_ONCE_INIT; 444169691Skan __gthread_once(&__once, _S_initialize); 445169691Skan } 446132720Skan 447169691Skan // Double check initialization. May be necessary on some 448169691Skan // systems for proper construction when not compiling with 449169691Skan // thread flags. 450169691Skan _S_get_pool()._M_initialize_once(); 451169691Skan __init = true; 452169691Skan } 453169691Skan } 454169691Skan }; 455132720Skan#endif 456132720Skan 457169691Skan /// @brief Policy for shared __pool objects. 458169691Skan template<template <bool> class _PoolTp, bool _Thread> 459169691Skan struct __common_pool_policy : public __common_pool_base<_PoolTp, _Thread> 460132720Skan { 461169691Skan template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp, 462169691Skan bool _Thread1 = _Thread> 463169691Skan struct _M_rebind 464169691Skan { typedef __common_pool_policy<_PoolTp1, _Thread1> other; }; 465132720Skan 466169691Skan using __common_pool_base<_PoolTp, _Thread>::_S_get_pool; 467169691Skan using __common_pool_base<_PoolTp, _Thread>::_S_initialize_once; 468169691Skan }; 469169691Skan 470169691Skan 471169691Skan template<typename _Tp, template <bool> class _PoolTp, bool _Thread> 472169691Skan struct __per_type_pool 473169691Skan { 474169691Skan typedef _Tp value_type; 475169691Skan typedef _PoolTp<_Thread> pool_type; 476132720Skan 477169691Skan static pool_type& 478169691Skan _S_get_pool() 479169691Skan { 480169691Skan // Sane defaults for the _PoolTp. 481169691Skan typedef typename pool_type::_Block_record _Block_record; 482169691Skan const static size_t __a = (__alignof__(_Tp) >= sizeof(_Block_record) 483169691Skan ? __alignof__(_Tp) : sizeof(_Block_record)); 484132720Skan 485169691Skan typedef typename __pool_base::_Tune _Tune; 486169691Skan static _Tune _S_tune(__a, sizeof(_Tp) * 64, 487169691Skan sizeof(_Tp) * 2 >= __a ? sizeof(_Tp) * 2 : __a, 488169691Skan sizeof(_Tp) * size_t(_Tune::_S_chunk_size), 489169691Skan _Tune::_S_max_threads, 490169691Skan _Tune::_S_freelist_headroom, 491169691Skan std::getenv("GLIBCXX_FORCE_NEW") ? true : false); 492169691Skan static pool_type _S_pool(_S_tune); 493169691Skan return _S_pool; 494169691Skan } 495169691Skan }; 496132720Skan 497169691Skan template<typename _Tp, template <bool> class _PoolTp, bool _Thread> 498169691Skan struct __per_type_pool_base; 499132720Skan 500169691Skan template<typename _Tp, template <bool> class _PoolTp> 501169691Skan struct __per_type_pool_base<_Tp, _PoolTp, false> 502169691Skan : public __per_type_pool<_Tp, _PoolTp, false> 503169691Skan { 504169691Skan using __per_type_pool<_Tp, _PoolTp, false>::_S_get_pool; 505169691Skan 506169691Skan static void 507169691Skan _S_initialize_once() 508169691Skan { 509169691Skan static bool __init; 510169691Skan if (__builtin_expect(__init == false, false)) 511169691Skan { 512169691Skan _S_get_pool()._M_initialize_once(); 513169691Skan __init = true; 514169691Skan } 515169691Skan } 516169691Skan }; 517169691Skan 518169691Skan #ifdef __GTHREADS 519169691Skan template<typename _Tp, template <bool> class _PoolTp> 520169691Skan struct __per_type_pool_base<_Tp, _PoolTp, true> 521169691Skan : public __per_type_pool<_Tp, _PoolTp, true> 522169691Skan { 523169691Skan using __per_type_pool<_Tp, _PoolTp, true>::_S_get_pool; 524169691Skan 525169691Skan static void 526169691Skan _S_initialize() 527169691Skan { _S_get_pool()._M_initialize_once(); } 528169691Skan 529169691Skan static void 530169691Skan _S_initialize_once() 531169691Skan { 532169691Skan static bool __init; 533169691Skan if (__builtin_expect(__init == false, false)) 534169691Skan { 535169691Skan if (__gthread_active_p()) 536169691Skan { 537169691Skan // On some platforms, __gthread_once_t is an aggregate. 538169691Skan static __gthread_once_t __once = __GTHREAD_ONCE_INIT; 539169691Skan __gthread_once(&__once, _S_initialize); 540169691Skan } 541169691Skan 542169691Skan // Double check initialization. May be necessary on some 543169691Skan // systems for proper construction when not compiling with 544169691Skan // thread flags. 545169691Skan _S_get_pool()._M_initialize_once(); 546169691Skan __init = true; 547169691Skan } 548169691Skan } 549169691Skan }; 550132720Skan#endif 551169691Skan 552169691Skan /// @brief Policy for individual __pool objects. 553169691Skan template<typename _Tp, template <bool> class _PoolTp, bool _Thread> 554169691Skan struct __per_type_pool_policy 555169691Skan : public __per_type_pool_base<_Tp, _PoolTp, _Thread> 556169691Skan { 557169691Skan template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp, 558169691Skan bool _Thread1 = _Thread> 559169691Skan struct _M_rebind 560169691Skan { typedef __per_type_pool_policy<_Tp1, _PoolTp1, _Thread1> other; }; 561169691Skan 562169691Skan using __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_get_pool; 563169691Skan using __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_initialize_once; 564169691Skan }; 565169691Skan 566169691Skan 567169691Skan /// @brief Base class for _Tp dependent member functions. 568132720Skan template<typename _Tp> 569169691Skan class __mt_alloc_base 570132720Skan { 571169691Skan public: 572169691Skan typedef size_t size_type; 573169691Skan typedef ptrdiff_t difference_type; 574169691Skan typedef _Tp* pointer; 575169691Skan typedef const _Tp* const_pointer; 576169691Skan typedef _Tp& reference; 577169691Skan typedef const _Tp& const_reference; 578169691Skan typedef _Tp value_type; 579132720Skan 580169691Skan pointer 581169691Skan address(reference __x) const 582169691Skan { return &__x; } 583132720Skan 584169691Skan const_pointer 585169691Skan address(const_reference __x) const 586169691Skan { return &__x; } 587132720Skan 588169691Skan size_type 589169691Skan max_size() const throw() 590169691Skan { return size_t(-1) / sizeof(_Tp); } 591132720Skan 592169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 593169691Skan // 402. wrong new expression in [some_] allocator::construct 594169691Skan void 595169691Skan construct(pointer __p, const _Tp& __val) 596169691Skan { ::new(__p) _Tp(__val); } 597132720Skan 598169691Skan void 599169691Skan destroy(pointer __p) { __p->~_Tp(); } 600169691Skan }; 601169691Skan 602132720Skan#ifdef __GTHREADS 603169691Skan#define __thread_default true 604169691Skan#else 605169691Skan#define __thread_default false 606169691Skan#endif 607132720Skan 608169691Skan /** 609169691Skan * @brief This is a fixed size (power of 2) allocator which - when 610169691Skan * compiled with thread support - will maintain one freelist per 611169691Skan * size per thread plus a "global" one. Steps are taken to limit 612169691Skan * the per thread freelist sizes (by returning excess back to 613169691Skan * the "global" list). 614169691Skan * 615169691Skan * Further details: 616169691Skan * http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html 617169691Skan */ 618169691Skan template<typename _Tp, 619169691Skan typename _Poolp = __common_pool_policy<__pool, __thread_default> > 620169691Skan class __mt_alloc : public __mt_alloc_base<_Tp> 621169691Skan { 622169691Skan public: 623169691Skan typedef size_t size_type; 624169691Skan typedef ptrdiff_t difference_type; 625169691Skan typedef _Tp* pointer; 626169691Skan typedef const _Tp* const_pointer; 627169691Skan typedef _Tp& reference; 628169691Skan typedef const _Tp& const_reference; 629169691Skan typedef _Tp value_type; 630169691Skan typedef _Poolp __policy_type; 631169691Skan typedef typename _Poolp::pool_type __pool_type; 632132720Skan 633169691Skan template<typename _Tp1, typename _Poolp1 = _Poolp> 634169691Skan struct rebind 635169691Skan { 636169691Skan typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type; 637169691Skan typedef __mt_alloc<_Tp1, pol_type> other; 638169691Skan }; 639132720Skan 640169691Skan __mt_alloc() throw() { } 641132720Skan 642169691Skan __mt_alloc(const __mt_alloc&) throw() { } 643132720Skan 644169691Skan template<typename _Tp1, typename _Poolp1> 645169691Skan __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>&) throw() { } 646132720Skan 647169691Skan ~__mt_alloc() throw() { } 648132720Skan 649169691Skan pointer 650169691Skan allocate(size_type __n, const void* = 0); 651132720Skan 652169691Skan void 653169691Skan deallocate(pointer __p, size_type __n); 654132720Skan 655169691Skan const __pool_base::_Tune 656169691Skan _M_get_options() 657169691Skan { 658169691Skan // Return a copy, not a reference, for external consumption. 659169691Skan return __policy_type::_S_get_pool()._M_get_options(); 660169691Skan } 661169691Skan 662169691Skan void 663169691Skan _M_set_options(__pool_base::_Tune __t) 664169691Skan { __policy_type::_S_get_pool()._M_set_options(__t); } 665169691Skan }; 666132720Skan 667169691Skan template<typename _Tp, typename _Poolp> 668169691Skan typename __mt_alloc<_Tp, _Poolp>::pointer 669169691Skan __mt_alloc<_Tp, _Poolp>:: 670169691Skan allocate(size_type __n, const void*) 671132720Skan { 672169691Skan if (__builtin_expect(__n > this->max_size(), false)) 673169691Skan std::__throw_bad_alloc(); 674132720Skan 675169691Skan __policy_type::_S_initialize_once(); 676169691Skan 677169691Skan // Requests larger than _M_max_bytes are handled by operator 678169691Skan // new/delete directly. 679169691Skan __pool_type& __pool = __policy_type::_S_get_pool(); 680169691Skan const size_t __bytes = __n * sizeof(_Tp); 681169691Skan if (__pool._M_check_threshold(__bytes)) 682169691Skan { 683169691Skan void* __ret = ::operator new(__bytes); 684169691Skan return static_cast<_Tp*>(__ret); 685169691Skan } 686169691Skan 687169691Skan // Round up to power of 2 and figure out which bin to use. 688169691Skan const size_t __which = __pool._M_get_binmap(__bytes); 689169691Skan const size_t __thread_id = __pool._M_get_thread_id(); 690169691Skan 691169691Skan // Find out if we have blocks on our freelist. If so, go ahead 692169691Skan // and use them directly without having to lock anything. 693169691Skan char* __c; 694169691Skan typedef typename __pool_type::_Bin_record _Bin_record; 695169691Skan const _Bin_record& __bin = __pool._M_get_bin(__which); 696169691Skan if (__bin._M_first[__thread_id]) 697169691Skan { 698169691Skan // Already reserved. 699169691Skan typedef typename __pool_type::_Block_record _Block_record; 700259705Spfg _Block_record* __block_record = __bin._M_first[__thread_id]; 701259705Spfg __bin._M_first[__thread_id] = __block_record->_M_next; 702169691Skan 703259705Spfg __pool._M_adjust_freelist(__bin, __block_record, __thread_id); 704259705Spfg __c = reinterpret_cast<char*>(__block_record) + __pool._M_get_align(); 705169691Skan } 706169691Skan else 707169691Skan { 708169691Skan // Null, reserve. 709169691Skan __c = __pool._M_reserve_block(__bytes, __thread_id); 710169691Skan } 711169691Skan return static_cast<_Tp*>(static_cast<void*>(__c)); 712132720Skan } 713169691Skan 714169691Skan template<typename _Tp, typename _Poolp> 715132720Skan void 716169691Skan __mt_alloc<_Tp, _Poolp>:: 717169691Skan deallocate(pointer __p, size_type __n) 718132720Skan { 719169691Skan if (__builtin_expect(__p != 0, true)) 720169691Skan { 721169691Skan // Requests larger than _M_max_bytes are handled by 722169691Skan // operators new/delete directly. 723169691Skan __pool_type& __pool = __policy_type::_S_get_pool(); 724169691Skan const size_t __bytes = __n * sizeof(_Tp); 725169691Skan if (__pool._M_check_threshold(__bytes)) 726169691Skan ::operator delete(__p); 727169691Skan else 728169691Skan __pool._M_reclaim_block(reinterpret_cast<char*>(__p), __bytes); 729169691Skan } 730132720Skan } 731169691Skan 732169691Skan template<typename _Tp, typename _Poolp> 733132720Skan inline bool 734169691Skan operator==(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&) 735132720Skan { return true; } 736132720Skan 737169691Skan template<typename _Tp, typename _Poolp> 738132720Skan inline bool 739169691Skan operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&) 740132720Skan { return false; } 741132720Skan 742169691Skan#undef __thread_default 743132720Skan 744169691Skan_GLIBCXX_END_NAMESPACE 745132720Skan 746132720Skan#endif 747