1 // Allocators -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
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)
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.
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,
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.
31 * Copyright (c) 1996-1997
32 * Silicon Graphics Computer Systems, Inc.
34 * Permission to use, copy, modify, distribute and sell this software
35 * and its documentation for any purpose is hereby granted without fee,
36 * provided that the above copyright notice appear in all copies and
37 * that both that copyright notice and this permission notice appear
38 * in supporting documentation. Silicon Graphics makes no
39 * representations about the suitability of this software for any
40 * purpose. It is provided "as is" without express or implied warranty.
43 /** @file ext/pool_allocator.h
44 * This file is a GNU extension to the Standard C++ Library.
45 * You should only include this header if you are using GCC 3 or later.
47 #ifndef _POOL_ALLOCATOR_H
48 #define _POOL_ALLOCATOR_H 1
50 #include <bits/c++config.h>
52 #include <bits/functexcept.h>
53 #include <bits/atomicity.h>
54 #include <bits/concurrence.h>
60 * Uses various allocators to fulfill underlying requests (and makes as
61 * few requests as possible when in default high-speed pool mode).
63 * Important implementation properties:
64 * 0. If globally mandated, then allocate objects from new
65 * 1. If the clients request an object of size > _S_max_bytes, the resulting
66 * object will be obtained directly from new
67 * 2. In all other cases, we allocate an object of size exactly
68 * _S_round_up(requested_size). Thus the client has enough size
69 * information that we can return the object to the proper free list
70 * without permanently losing part of the object.
73 * (See @link Allocators allocators info @endlink for more.)
79 enum { _S_align = 8 };
80 enum { _S_max_bytes = 128 };
81 enum { _S_free_list_size = _S_max_bytes / _S_align };
85 union _Obj* _M_free_list_link;
86 char _M_client_data[1]; // The client sees this.
89 static _Obj* volatile _S_free_list[_S_free_list_size];
91 // Chunk allocation state.
92 static char* _S_start_free;
93 static char* _S_end_free;
94 static size_t _S_heap_size;
97 _M_round_up(size_t __bytes)
98 { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }
101 _M_get_free_list(size_t __bytes);
106 // Returns an object of size __n, and optionally adds to size __n
109 _M_refill(size_t __n);
111 // Allocates a chunk for nobjs of size size. nobjs may be reduced
112 // if it is inconvenient to allocate the requested number.
114 _M_allocate_chunk(size_t __n, int& __nobjs);
118 template<typename _Tp>
119 class __pool_alloc : private __pool_base
122 static _Atomic_word _S_force_new;
125 typedef size_t size_type;
126 typedef ptrdiff_t difference_type;
127 typedef _Tp* pointer;
128 typedef const _Tp* const_pointer;
129 typedef _Tp& reference;
130 typedef const _Tp& const_reference;
131 typedef _Tp value_type;
133 template<typename _Tp1>
135 { typedef __pool_alloc<_Tp1> other; };
137 __pool_alloc() throw() { }
139 __pool_alloc(const __pool_alloc&) throw() { }
141 template<typename _Tp1>
142 __pool_alloc(const __pool_alloc<_Tp1>&) throw() { }
144 ~__pool_alloc() throw() { }
147 address(reference __x) const { return &__x; }
150 address(const_reference __x) const { return &__x; }
153 max_size() const throw()
154 { return size_t(-1) / sizeof(_Tp); }
156 // _GLIBCXX_RESOLVE_LIB_DEFECTS
157 // 402. wrong new expression in [some_] allocator::construct
159 construct(pointer __p, const _Tp& __val)
160 { ::new(__p) _Tp(__val); }
163 destroy(pointer __p) { __p->~_Tp(); }
166 allocate(size_type __n, const void* = 0);
169 deallocate(pointer __p, size_type __n);
172 template<typename _Tp>
174 operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
177 template<typename _Tp>
179 operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
182 template<typename _Tp>
184 __pool_alloc<_Tp>::_S_force_new;
186 template<typename _Tp>
188 __pool_alloc<_Tp>::allocate(size_type __n, const void*)
193 if (__n <= max_size())
195 // If there is a race through here, assume answer from getenv
196 // will resolve in same direction. Inspired by techniques
197 // to efficiently support threading found in basic_string.h.
198 if (_S_force_new == 0)
200 if (getenv("GLIBCXX_FORCE_NEW"))
201 __atomic_add(&_S_force_new, 1);
203 __atomic_add(&_S_force_new, -1);
206 const size_t __bytes = __n * sizeof(_Tp);
207 if (__bytes > size_t(_S_max_bytes) || _S_force_new == 1)
208 __ret = static_cast<_Tp*>(::operator new(__bytes));
211 _Obj* volatile* __free_list = _M_get_free_list(__bytes);
213 lock sentry(_M_get_mutex());
214 _Obj* __restrict__ __result = *__free_list;
215 if (__builtin_expect(__result == 0, 0))
216 __ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes)));
219 *__free_list = __result->_M_free_list_link;
220 __ret = reinterpret_cast<_Tp*>(__result);
222 if (__builtin_expect(__ret == 0, 0))
223 std::__throw_bad_alloc();
227 std::__throw_bad_alloc();
232 template<typename _Tp>
234 __pool_alloc<_Tp>::deallocate(pointer __p, size_type __n)
238 const size_t __bytes = __n * sizeof(_Tp);
239 if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new == 1)
240 ::operator delete(__p);
243 _Obj* volatile* __free_list = _M_get_free_list(__bytes);
244 _Obj* __q = reinterpret_cast<_Obj*>(__p);
246 lock sentry(_M_get_mutex());
247 __q ->_M_free_list_link = *__free_list;
252 } // namespace __gnu_cxx