]>
Commit | Line | Data |
---|---|---|
1ff9402d BK |
1 | // Allocators -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2001-2019 Free Software Foundation, Inc. |
1ff9402d BK |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
1ff9402d BK |
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 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
1ff9402d | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
1ff9402d BK |
24 | |
25 | /* | |
26 | * Copyright (c) 1996-1997 | |
27 | * Silicon Graphics Computer Systems, Inc. | |
28 | * | |
29 | * Permission to use, copy, modify, distribute and sell this software | |
30 | * and its documentation for any purpose is hereby granted without fee, | |
31 | * provided that the above copyright notice appear in all copies and | |
32 | * that both that copyright notice and this permission notice appear | |
33 | * in supporting documentation. Silicon Graphics makes no | |
34 | * representations about the suitability of this software for any | |
35 | * purpose. It is provided "as is" without express or implied warranty. | |
36 | */ | |
37 | ||
56766e0d | 38 | /** @file ext/pool_allocator.h |
fa30fe72 | 39 | * This file is a GNU extension to the Standard C++ Library. |
1ff9402d | 40 | */ |
0aa06b18 | 41 | |
1ff9402d BK |
42 | #ifndef _POOL_ALLOCATOR_H |
43 | #define _POOL_ALLOCATOR_H 1 | |
44 | ||
a39c16dd | 45 | #include <bits/c++config.h> |
e55096f0 | 46 | #include <cstdlib> |
d38d4e5d | 47 | #include <new> |
fa30fe72 | 48 | #include <bits/functexcept.h> |
2e362c74 BK |
49 | #include <ext/atomicity.h> |
50 | #include <ext/concurrence.h> | |
ca0f8fd1 | 51 | #include <bits/move.h> |
1b5dc776 JW |
52 | #if __cplusplus >= 201103L |
53 | #include <type_traits> | |
54 | #endif | |
1ff9402d | 55 | |
12ffa228 BK |
56 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
57 | { | |
58 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
3cbc7af0 | 59 | |
05a2763e MG |
60 | using std::size_t; |
61 | using std::ptrdiff_t; | |
62 | ||
1ff9402d | 63 | /** |
6309eefc BK |
64 | * @brief Base class for __pool_alloc. |
65 | * | |
29d4adf4 PC |
66 | * Uses various allocators to fulfill underlying requests (and makes as |
67 | * few requests as possible when in default high-speed pool mode). | |
1ff9402d BK |
68 | * |
69 | * Important implementation properties: | |
d38d4e5d | 70 | * 0. If globally mandated, then allocate objects from new |
1ff9402d | 71 | * 1. If the clients request an object of size > _S_max_bytes, the resulting |
d38d4e5d | 72 | * object will be obtained directly from new |
1ff9402d BK |
73 | * 2. In all other cases, we allocate an object of size exactly |
74 | * _S_round_up(requested_size). Thus the client has enough size | |
75 | * information that we can return the object to the proper free list | |
76 | * without permanently losing part of the object. | |
1ff9402d | 77 | */ |
fa016245 | 78 | class __pool_alloc_base |
5f1a5ede | 79 | { |
2832d07b BK |
80 | protected: |
81 | ||
5f1a5ede PC |
82 | enum { _S_align = 8 }; |
83 | enum { _S_max_bytes = 128 }; | |
a9dd5a46 | 84 | enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align }; |
5f1a5ede PC |
85 | |
86 | union _Obj | |
87 | { | |
88 | union _Obj* _M_free_list_link; | |
89 | char _M_client_data[1]; // The client sees this. | |
90 | }; | |
91 | ||
2832d07b | 92 | static _Obj* volatile _S_free_list[_S_free_list_size]; |
838d4309 | 93 | |
5f1a5ede PC |
94 | // Chunk allocation state. |
95 | static char* _S_start_free; | |
96 | static char* _S_end_free; | |
2832d07b | 97 | static size_t _S_heap_size; |
5f1a5ede | 98 | |
2832d07b BK |
99 | size_t |
100 | _M_round_up(size_t __bytes) | |
5f1a5ede PC |
101 | { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); } |
102 | ||
5d51b87a JH |
103 | _GLIBCXX_CONST _Obj* volatile* |
104 | _M_get_free_list(size_t __bytes) throw (); | |
5f1a5ede | 105 | |
2e362c74 | 106 | __mutex& |
5d51b87a | 107 | _M_get_mutex() throw (); |
838d4309 | 108 | |
5f1a5ede PC |
109 | // Returns an object of size __n, and optionally adds to size __n |
110 | // free list. | |
2832d07b BK |
111 | void* |
112 | _M_refill(size_t __n); | |
5f1a5ede PC |
113 | |
114 | // Allocates a chunk for nobjs of size size. nobjs may be reduced | |
115 | // if it is inconvenient to allocate the requested number. | |
2832d07b BK |
116 | char* |
117 | _M_allocate_chunk(size_t __n, int& __nobjs); | |
5f1a5ede PC |
118 | }; |
119 | ||
5f1a5ede | 120 | |
5b9daa7e BK |
121 | /** |
122 | * @brief Allocator using a memory pool with a single lock. | |
123 | * @ingroup allocators | |
124 | */ | |
29d4adf4 | 125 | template<typename _Tp> |
fa016245 | 126 | class __pool_alloc : private __pool_alloc_base |
1ff9402d | 127 | { |
2832d07b BK |
128 | private: |
129 | static _Atomic_word _S_force_new; | |
130 | ||
29d4adf4 PC |
131 | public: |
132 | typedef size_t size_type; | |
133 | typedef ptrdiff_t difference_type; | |
134 | typedef _Tp* pointer; | |
135 | typedef const _Tp* const_pointer; | |
136 | typedef _Tp& reference; | |
137 | typedef const _Tp& const_reference; | |
138 | typedef _Tp value_type; | |
139 | ||
140 | template<typename _Tp1> | |
141 | struct rebind | |
142 | { typedef __pool_alloc<_Tp1> other; }; | |
143 | ||
1b5dc776 JW |
144 | #if __cplusplus >= 201103L |
145 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
146 | // 2103. propagate_on_container_move_assignment | |
147 | typedef std::true_type propagate_on_container_move_assignment; | |
148 | #endif | |
149 | ||
7d9cb054 | 150 | __pool_alloc() _GLIBCXX_USE_NOEXCEPT { } |
29d4adf4 | 151 | |
7d9cb054 | 152 | __pool_alloc(const __pool_alloc&) _GLIBCXX_USE_NOEXCEPT { } |
29d4adf4 PC |
153 | |
154 | template<typename _Tp1> | |
7d9cb054 | 155 | __pool_alloc(const __pool_alloc<_Tp1>&) _GLIBCXX_USE_NOEXCEPT { } |
29d4adf4 | 156 | |
7d9cb054 | 157 | ~__pool_alloc() _GLIBCXX_USE_NOEXCEPT { } |
29d4adf4 PC |
158 | |
159 | pointer | |
7d9cb054 PC |
160 | address(reference __x) const _GLIBCXX_NOEXCEPT |
161 | { return std::__addressof(__x); } | |
29d4adf4 PC |
162 | |
163 | const_pointer | |
7d9cb054 PC |
164 | address(const_reference __x) const _GLIBCXX_NOEXCEPT |
165 | { return std::__addressof(__x); } | |
29d4adf4 PC |
166 | |
167 | size_type | |
7d9cb054 | 168 | max_size() const _GLIBCXX_USE_NOEXCEPT |
29d4adf4 PC |
169 | { return size_t(-1) / sizeof(_Tp); } |
170 | ||
734f5023 | 171 | #if __cplusplus >= 201103L |
45ba8f9f JW |
172 | template<typename _Up, typename... _Args> |
173 | void | |
174 | construct(_Up* __p, _Args&&... __args) | |
175 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); } | |
176 | ||
177 | template<typename _Up> | |
178 | void | |
179 | destroy(_Up* __p) { __p->~_Up(); } | |
180 | #else | |
29d4adf4 PC |
181 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
182 | // 402. wrong new expression in [some_] allocator::construct | |
183 | void | |
184 | construct(pointer __p, const _Tp& __val) | |
61fcb9fb PC |
185 | { ::new((void *)__p) _Tp(__val); } |
186 | ||
29d4adf4 PC |
187 | void |
188 | destroy(pointer __p) { __p->~_Tp(); } | |
45ba8f9f | 189 | #endif |
29d4adf4 | 190 | |
d715f554 | 191 | _GLIBCXX_NODISCARD pointer |
29d4adf4 PC |
192 | allocate(size_type __n, const void* = 0); |
193 | ||
194 | void | |
195 | deallocate(pointer __p, size_type __n); | |
1ff9402d BK |
196 | }; |
197 | ||
29d4adf4 | 198 | template<typename _Tp> |
1ff9402d | 199 | inline bool |
29d4adf4 | 200 | operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&) |
1ff9402d BK |
201 | { return true; } |
202 | ||
29d4adf4 | 203 | template<typename _Tp> |
1ff9402d | 204 | inline bool |
29d4adf4 | 205 | operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&) |
1ff9402d BK |
206 | { return false; } |
207 | ||
2832d07b BK |
208 | template<typename _Tp> |
209 | _Atomic_word | |
210 | __pool_alloc<_Tp>::_S_force_new; | |
1ff9402d | 211 | |
29d4adf4 | 212 | template<typename _Tp> |
d715f554 | 213 | _GLIBCXX_NODISCARD _Tp* |
29d4adf4 | 214 | __pool_alloc<_Tp>::allocate(size_type __n, const void*) |
c37514ff | 215 | { |
29d4adf4 | 216 | pointer __ret = 0; |
a063e891 | 217 | if (__builtin_expect(__n != 0, true)) |
c37514ff | 218 | { |
e762c6f4 | 219 | if (__n > this->max_size()) |
a063e891 PC |
220 | std::__throw_bad_alloc(); |
221 | ||
ace4c2f0 JW |
222 | const size_t __bytes = __n * sizeof(_Tp); |
223 | ||
224 | #if __cpp_aligned_new | |
225 | if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__) | |
226 | { | |
227 | std::align_val_t __al = std::align_val_t(alignof(_Tp)); | |
228 | return static_cast<_Tp*>(::operator new(__bytes, __al)); | |
229 | } | |
230 | #endif | |
231 | ||
a063e891 PC |
232 | // If there is a race through here, assume answer from getenv |
233 | // will resolve in same direction. Inspired by techniques | |
234 | // to efficiently support threading found in basic_string.h. | |
235 | if (_S_force_new == 0) | |
c37514ff | 236 | { |
05a79eb6 | 237 | if (std::getenv("GLIBCXX_FORCE_NEW")) |
b7ee72de | 238 | __atomic_add_dispatch(&_S_force_new, 1); |
a063e891 | 239 | else |
b7ee72de | 240 | __atomic_add_dispatch(&_S_force_new, -1); |
a063e891 | 241 | } |
2832d07b | 242 | |
d4083c80 | 243 | if (__bytes > size_t(_S_max_bytes) || _S_force_new > 0) |
a063e891 PC |
244 | __ret = static_cast<_Tp*>(::operator new(__bytes)); |
245 | else | |
246 | { | |
247 | _Obj* volatile* __free_list = _M_get_free_list(__bytes); | |
248 | ||
2e362c74 | 249 | __scoped_lock sentry(_M_get_mutex()); |
a063e891 PC |
250 | _Obj* __restrict__ __result = *__free_list; |
251 | if (__builtin_expect(__result == 0, 0)) | |
252 | __ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes))); | |
29d4adf4 PC |
253 | else |
254 | { | |
a063e891 PC |
255 | *__free_list = __result->_M_free_list_link; |
256 | __ret = reinterpret_cast<_Tp*>(__result); | |
29d4adf4 | 257 | } |
e762c6f4 | 258 | if (__ret == 0) |
a063e891 | 259 | std::__throw_bad_alloc(); |
fa30fe72 | 260 | } |
c37514ff BK |
261 | } |
262 | return __ret; | |
263 | } | |
fa30fe72 | 264 | |
29d4adf4 | 265 | template<typename _Tp> |
c37514ff | 266 | void |
29d4adf4 | 267 | __pool_alloc<_Tp>::deallocate(pointer __p, size_type __n) |
c37514ff | 268 | { |
a063e891 | 269 | if (__builtin_expect(__n != 0 && __p != 0, true)) |
c37514ff | 270 | { |
ace4c2f0 JW |
271 | #if __cpp_aligned_new |
272 | if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__) | |
273 | { | |
274 | ::operator delete(__p, std::align_val_t(alignof(_Tp))); | |
275 | return; | |
276 | } | |
277 | #endif | |
29d4adf4 | 278 | const size_t __bytes = __n * sizeof(_Tp); |
d4083c80 | 279 | if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new > 0) |
29d4adf4 PC |
280 | ::operator delete(__p); |
281 | else | |
282 | { | |
2832d07b BK |
283 | _Obj* volatile* __free_list = _M_get_free_list(__bytes); |
284 | _Obj* __q = reinterpret_cast<_Obj*>(__p); | |
29d4adf4 | 285 | |
2e362c74 | 286 | __scoped_lock sentry(_M_get_mutex()); |
2832d07b | 287 | __q ->_M_free_list_link = *__free_list; |
29d4adf4 PC |
288 | *__free_list = __q; |
289 | } | |
c37514ff BK |
290 | } |
291 | } | |
3cbc7af0 | 292 | |
12ffa228 BK |
293 | _GLIBCXX_END_NAMESPACE_VERSION |
294 | } // namespace | |
1ff9402d | 295 | |
1ff9402d | 296 | #endif |