190075Sobrien// Allocators -*- C++ -*- 290075Sobrien 390075Sobrien// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 490075Sobrien// Free Software Foundation, Inc. 590075Sobrien// 690075Sobrien// This file is part of the GNU ISO C++ Library. This library is free 790075Sobrien// software; you can redistribute it and/or modify it under the 890075Sobrien// terms of the GNU General Public License as published by the 990075Sobrien// Free Software Foundation; either version 2, or (at your option) 1090075Sobrien// any later version. 1190075Sobrien 1290075Sobrien// This library is distributed in the hope that it will be useful, 1390075Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1490075Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1590075Sobrien// GNU General Public License for more details. 1690075Sobrien 1790075Sobrien// You should have received a copy of the GNU General Public License along 1890075Sobrien// with this library; see the file COPYING. If not, write to the Free 1990075Sobrien// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2090075Sobrien// USA. 2190075Sobrien 2290075Sobrien// As a special exception, you may use this file as part of a free software 2390075Sobrien// library without restriction. Specifically, if other files instantiate 24169689Skan// templates or use macros or inline functions from this file, or you compile 25169689Skan// this file and link it with other files to produce an executable, this 2690075Sobrien// file does not by itself cause the resulting executable to be covered by 2790075Sobrien// the GNU General Public License. This exception does not however 28117395Skan// invalidate any other reasons why the executable file might be covered by 2990075Sobrien// the GNU General Public License. 30169689Skan 31117395Skan/* 3290075Sobrien * Copyright (c) 1996-1997 33117395Skan * Silicon Graphics Computer Systems, Inc. 3490075Sobrien * 3590075Sobrien * Permission to use, copy, modify, distribute and sell this software 3690075Sobrien * and its documentation for any purpose is hereby granted without fee, 3790075Sobrien * provided that the above copyright notice appear in all copies and 3890075Sobrien * that both that copyright notice and this permission notice appear 3990075Sobrien * in supporting documentation. Silicon Graphics makes no 4090075Sobrien * representations about the suitability of this software for any 4190075Sobrien * purpose. It is provided "as is" without express or implied warranty. 4290075Sobrien */ 4390075Sobrien 4490075Sobrien/** @file ext/pool_allocator.h 4590075Sobrien * This file is a GNU extension to the Standard C++ Library. 4690075Sobrien */ 4790075Sobrien 4890075Sobrien#ifndef _POOL_ALLOCATOR_H 49117395Skan#define _POOL_ALLOCATOR_H 1 50117395Skan 51169689Skan#include <bits/c++config.h> 52117395Skan#include <cstdlib> 53117395Skan#include <new> 54117395Skan#include <bits/functexcept.h> 55117395Skan#include <ext/atomicity.h> 56117395Skan#include <ext/concurrence.h> 57117395Skan 58169689Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 5990075Sobrien 6090075Sobrien using std::size_t; 6190075Sobrien using std::ptrdiff_t; 6290075Sobrien 63169689Skan /** 64169689Skan * @brief Base class for __pool_alloc. 65169689Skan * 6690075Sobrien * @if maint 6790075Sobrien * Uses various allocators to fulfill underlying requests (and makes as 68117395Skan * few requests as possible when in default high-speed pool mode). 6990075Sobrien * 7090075Sobrien * Important implementation properties: 7190075Sobrien * 0. If globally mandated, then allocate objects from new 7290075Sobrien * 1. If the clients request an object of size > _S_max_bytes, the resulting 7390075Sobrien * object will be obtained directly from new 7490075Sobrien * 2. In all other cases, we allocate an object of size exactly 7590075Sobrien * _S_round_up(requested_size). Thus the client has enough size 7690075Sobrien * information that we can return the object to the proper free list 7790075Sobrien * without permanently losing part of the object. 7890075Sobrien * 7990075Sobrien * @endif 8090075Sobrien */ 8190075Sobrien class __pool_alloc_base 8290075Sobrien { 8390075Sobrien protected: 8490075Sobrien 8590075Sobrien enum { _S_align = 8 }; 8690075Sobrien enum { _S_max_bytes = 128 }; 8790075Sobrien enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align }; 8890075Sobrien 8990075Sobrien union _Obj 9090075Sobrien { 9190075Sobrien union _Obj* _M_free_list_link; 9290075Sobrien char _M_client_data[1]; // The client sees this. 9390075Sobrien }; 9490075Sobrien 9590075Sobrien static _Obj* volatile _S_free_list[_S_free_list_size]; 9690075Sobrien 9790075Sobrien // Chunk allocation state. 9890075Sobrien static char* _S_start_free; 9990075Sobrien static char* _S_end_free; 10090075Sobrien static size_t _S_heap_size; 10190075Sobrien 102132718Skan size_t 10390075Sobrien _M_round_up(size_t __bytes) 10490075Sobrien { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); } 105169689Skan 10690075Sobrien _Obj* volatile* 10790075Sobrien _M_get_free_list(size_t __bytes); 10890075Sobrien 109169689Skan __mutex& 110169689Skan _M_get_mutex(); 111169689Skan 11290075Sobrien // Returns an object of size __n, and optionally adds to size __n 11390075Sobrien // free list. 11490075Sobrien void* 11590075Sobrien _M_refill(size_t __n); 11690075Sobrien 11790075Sobrien // Allocates a chunk for nobjs of size size. nobjs may be reduced 118117395Skan // if it is inconvenient to allocate the requested number. 11990075Sobrien char* 12090075Sobrien _M_allocate_chunk(size_t __n, int& __nobjs); 12190075Sobrien }; 12290075Sobrien 12390075Sobrien 12490075Sobrien /// @brief class __pool_alloc. 12590075Sobrien template<typename _Tp> 12690075Sobrien class __pool_alloc : private __pool_alloc_base 12790075Sobrien { 12890075Sobrien private: 129169689Skan static _Atomic_word _S_force_new; 13090075Sobrien 13190075Sobrien public: 13290075Sobrien typedef size_t size_type; 13390075Sobrien typedef ptrdiff_t difference_type; 13490075Sobrien typedef _Tp* pointer; 135132718Skan typedef const _Tp* const_pointer; 13690075Sobrien typedef _Tp& reference; 13790075Sobrien typedef const _Tp& const_reference; 138169689Skan typedef _Tp value_type; 13990075Sobrien 14090075Sobrien template<typename _Tp1> 141169689Skan struct rebind 142169689Skan { typedef __pool_alloc<_Tp1> other; }; 14390075Sobrien 144169689Skan __pool_alloc() throw() { } 14590075Sobrien 14690075Sobrien __pool_alloc(const __pool_alloc&) throw() { } 14790075Sobrien 14890075Sobrien template<typename _Tp1> 14990075Sobrien __pool_alloc(const __pool_alloc<_Tp1>&) throw() { } 15090075Sobrien 151117395Skan ~__pool_alloc() throw() { } 15290075Sobrien 15390075Sobrien pointer 15490075Sobrien address(reference __x) const { return &__x; } 15590075Sobrien 15690075Sobrien const_pointer 15790075Sobrien address(const_reference __x) const { return &__x; } 15890075Sobrien 15990075Sobrien size_type 16090075Sobrien max_size() const throw() 16190075Sobrien { return size_t(-1) / sizeof(_Tp); } 16290075Sobrien 16390075Sobrien // _GLIBCXX_RESOLVE_LIB_DEFECTS 16490075Sobrien // 402. wrong new expression in [some_] allocator::construct 16590075Sobrien void 16690075Sobrien construct(pointer __p, const _Tp& __val) 16790075Sobrien { ::new(__p) _Tp(__val); } 16890075Sobrien 16990075Sobrien void 17090075Sobrien destroy(pointer __p) { __p->~_Tp(); } 17190075Sobrien 17290075Sobrien pointer 17390075Sobrien allocate(size_type __n, const void* = 0); 17490075Sobrien 17590075Sobrien void 17690075Sobrien deallocate(pointer __p, size_type __n); 17790075Sobrien }; 17890075Sobrien 17990075Sobrien template<typename _Tp> 180169689Skan inline bool 181169689Skan operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&) 18290075Sobrien { return true; } 18390075Sobrien 18490075Sobrien template<typename _Tp> 18590075Sobrien inline bool 18690075Sobrien operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&) 18790075Sobrien { return false; } 18890075Sobrien 18990075Sobrien template<typename _Tp> 190 _Atomic_word 191 __pool_alloc<_Tp>::_S_force_new; 192 193 template<typename _Tp> 194 _Tp* 195 __pool_alloc<_Tp>::allocate(size_type __n, const void*) 196 { 197 pointer __ret = 0; 198 if (__builtin_expect(__n != 0, true)) 199 { 200 if (__builtin_expect(__n > this->max_size(), false)) 201 std::__throw_bad_alloc(); 202 203 // If there is a race through here, assume answer from getenv 204 // will resolve in same direction. Inspired by techniques 205 // to efficiently support threading found in basic_string.h. 206 if (_S_force_new == 0) 207 { 208 if (std::getenv("GLIBCXX_FORCE_NEW")) 209 __atomic_add_dispatch(&_S_force_new, 1); 210 else 211 __atomic_add_dispatch(&_S_force_new, -1); 212 } 213 214 const size_t __bytes = __n * sizeof(_Tp); 215 if (__bytes > size_t(_S_max_bytes) || _S_force_new == 1) 216 __ret = static_cast<_Tp*>(::operator new(__bytes)); 217 else 218 { 219 _Obj* volatile* __free_list = _M_get_free_list(__bytes); 220 221 __scoped_lock sentry(_M_get_mutex()); 222 _Obj* __restrict__ __result = *__free_list; 223 if (__builtin_expect(__result == 0, 0)) 224 __ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes))); 225 else 226 { 227 *__free_list = __result->_M_free_list_link; 228 __ret = reinterpret_cast<_Tp*>(__result); 229 } 230 if (__builtin_expect(__ret == 0, 0)) 231 std::__throw_bad_alloc(); 232 } 233 } 234 return __ret; 235 } 236 237 template<typename _Tp> 238 void 239 __pool_alloc<_Tp>::deallocate(pointer __p, size_type __n) 240 { 241 if (__builtin_expect(__n != 0 && __p != 0, true)) 242 { 243 const size_t __bytes = __n * sizeof(_Tp); 244 if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new == 1) 245 ::operator delete(__p); 246 else 247 { 248 _Obj* volatile* __free_list = _M_get_free_list(__bytes); 249 _Obj* __q = reinterpret_cast<_Obj*>(__p); 250 251 __scoped_lock sentry(_M_get_mutex()); 252 __q ->_M_free_list_link = *__free_list; 253 *__free_list = __q; 254 } 255 } 256 } 257 258_GLIBCXX_END_NAMESPACE 259 260#endif 261