]>
Commit | Line | Data |
---|---|---|
1399eca1 | 1 | // Bitmap Allocator. -*- C++ -*- |
009368db | 2 | |
aa118a03 | 3 | // Copyright (C) 2004-2014 Free Software Foundation, Inc. |
009368db DM |
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) |
009368db DM |
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. | |
009368db | 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/>. | |
009368db | 24 | |
1399eca1 DM |
25 | /** @file ext/bitmap_allocator.h |
26 | * This file is a GNU extension to the Standard C++ Library. | |
1399eca1 | 27 | */ |
009368db | 28 | |
1399eca1 | 29 | #ifndef _BITMAP_ALLOCATOR_H |
009368db DM |
30 | #define _BITMAP_ALLOCATOR_H 1 |
31 | ||
2e362c74 | 32 | #include <utility> // For std::pair. |
8fc81078 | 33 | #include <bits/functexcept.h> // For __throw_bad_alloc(). |
2e362c74 BK |
34 | #include <functional> // For greater_equal, and less_equal. |
35 | #include <new> // For operator new. | |
47bea7b8 | 36 | #include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT |
2e362c74 | 37 | #include <ext/concurrence.h> |
ca0f8fd1 | 38 | #include <bits/move.h> |
1399eca1 | 39 | |
4c10d7f0 DM |
40 | /** @brief The constant in the expression below is the alignment |
41 | * required in bytes. | |
42 | */ | |
a8155711 DM |
43 | #define _BALLOC_ALIGN_BYTES 8 |
44 | ||
12ffa228 BK |
45 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
46 | { | |
05a2763e MG |
47 | using std::size_t; |
48 | using std::ptrdiff_t; | |
49 | ||
78a53887 | 50 | namespace __detail |
1399eca1 | 51 | { |
12ffa228 | 52 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
4c10d7f0 DM |
53 | /** @class __mini_vector bitmap_allocator.h bitmap_allocator.h |
54 | * | |
55 | * @brief __mini_vector<> is a stripped down version of the | |
56 | * full-fledged std::vector<>. | |
57 | * | |
58 | * It is to be used only for built-in types or PODs. Notable | |
59 | * differences are: | |
60 | * | |
4c10d7f0 DM |
61 | * 1. Not all accessor functions are present. |
62 | * 2. Used ONLY for PODs. | |
63 | * 3. No Allocator template argument. Uses ::operator new() to get | |
64 | * memory, and ::operator delete() to free it. | |
65 | * Caveat: The dtor does NOT free the memory allocated, so this a | |
66 | * memory-leaking vector! | |
67 | */ | |
1399eca1 DM |
68 | template<typename _Tp> |
69 | class __mini_vector | |
009368db | 70 | { |
1399eca1 DM |
71 | __mini_vector(const __mini_vector&); |
72 | __mini_vector& operator=(const __mini_vector&); | |
73 | ||
74 | public: | |
75 | typedef _Tp value_type; | |
76 | typedef _Tp* pointer; | |
77 | typedef _Tp& reference; | |
78 | typedef const _Tp& const_reference; | |
05a2763e MG |
79 | typedef size_t size_type; |
80 | typedef ptrdiff_t difference_type; | |
1399eca1 DM |
81 | typedef pointer iterator; |
82 | ||
83 | private: | |
84 | pointer _M_start; | |
85 | pointer _M_finish; | |
86 | pointer _M_end_of_storage; | |
87 | ||
88 | size_type | |
89 | _M_space_left() const throw() | |
90 | { return _M_end_of_storage - _M_finish; } | |
91 | ||
92 | pointer | |
93 | allocate(size_type __n) | |
94 | { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); } | |
95 | ||
96 | void | |
97 | deallocate(pointer __p, size_type) | |
98 | { ::operator delete(__p); } | |
99 | ||
100 | public: | |
101 | // Members used: size(), push_back(), pop_back(), | |
102 | // insert(iterator, const_reference), erase(iterator), | |
103 | // begin(), end(), back(), operator[]. | |
104 | ||
a020110e PC |
105 | __mini_vector() |
106 | : _M_start(0), _M_finish(0), _M_end_of_storage(0) { } | |
009368db | 107 | |
1399eca1 DM |
108 | size_type |
109 | size() const throw() | |
110 | { return _M_finish - _M_start; } | |
009368db | 111 | |
1399eca1 DM |
112 | iterator |
113 | begin() const throw() | |
114 | { return this->_M_start; } | |
009368db | 115 | |
1399eca1 DM |
116 | iterator |
117 | end() const throw() | |
118 | { return this->_M_finish; } | |
009368db | 119 | |
1399eca1 DM |
120 | reference |
121 | back() const throw() | |
122 | { return *(this->end() - 1); } | |
009368db | 123 | |
1399eca1 DM |
124 | reference |
125 | operator[](const size_type __pos) const throw() | |
126 | { return this->_M_start[__pos]; } | |
127 | ||
128 | void | |
129 | insert(iterator __pos, const_reference __x); | |
130 | ||
131 | void | |
132 | push_back(const_reference __x) | |
133 | { | |
134 | if (this->_M_space_left()) | |
135 | { | |
136 | *this->end() = __x; | |
137 | ++this->_M_finish; | |
138 | } | |
139 | else | |
140 | this->insert(this->end(), __x); | |
141 | } | |
142 | ||
143 | void | |
144 | pop_back() throw() | |
145 | { --this->_M_finish; } | |
146 | ||
147 | void | |
148 | erase(iterator __pos) throw(); | |
009368db | 149 | |
1399eca1 DM |
150 | void |
151 | clear() throw() | |
152 | { this->_M_finish = this->_M_start; } | |
153 | }; | |
154 | ||
155 | // Out of line function definitions. | |
156 | template<typename _Tp> | |
157 | void __mini_vector<_Tp>:: | |
158 | insert(iterator __pos, const_reference __x) | |
009368db | 159 | { |
1399eca1 DM |
160 | if (this->_M_space_left()) |
161 | { | |
162 | size_type __to_move = this->_M_finish - __pos; | |
163 | iterator __dest = this->end(); | |
164 | iterator __src = this->end() - 1; | |
009368db | 165 | |
1399eca1 DM |
166 | ++this->_M_finish; |
167 | while (__to_move) | |
168 | { | |
169 | *__dest = *__src; | |
170 | --__dest; --__src; --__to_move; | |
171 | } | |
172 | *__pos = __x; | |
173 | } | |
174 | else | |
009368db | 175 | { |
1399eca1 DM |
176 | size_type __new_size = this->size() ? this->size() * 2 : 1; |
177 | iterator __new_start = this->allocate(__new_size); | |
178 | iterator __first = this->begin(); | |
179 | iterator __start = __new_start; | |
180 | while (__first != __pos) | |
009368db | 181 | { |
1399eca1 DM |
182 | *__start = *__first; |
183 | ++__start; ++__first; | |
009368db | 184 | } |
1399eca1 DM |
185 | *__start = __x; |
186 | ++__start; | |
187 | while (__first != this->end()) | |
188 | { | |
189 | *__start = *__first; | |
190 | ++__start; ++__first; | |
191 | } | |
192 | if (this->_M_start) | |
193 | this->deallocate(this->_M_start, this->size()); | |
194 | ||
195 | this->_M_start = __new_start; | |
196 | this->_M_finish = __start; | |
197 | this->_M_end_of_storage = this->_M_start + __new_size; | |
009368db | 198 | } |
009368db | 199 | } |
1399eca1 DM |
200 | |
201 | template<typename _Tp> | |
202 | void __mini_vector<_Tp>:: | |
203 | erase(iterator __pos) throw() | |
009368db | 204 | { |
1399eca1 | 205 | while (__pos + 1 != this->end()) |
009368db | 206 | { |
1399eca1 DM |
207 | *__pos = __pos[1]; |
208 | ++__pos; | |
009368db | 209 | } |
1399eca1 DM |
210 | --this->_M_finish; |
211 | } | |
009368db | 212 | |
009368db | 213 | |
1399eca1 DM |
214 | template<typename _Tp> |
215 | struct __mv_iter_traits | |
009368db | 216 | { |
1399eca1 DM |
217 | typedef typename _Tp::value_type value_type; |
218 | typedef typename _Tp::difference_type difference_type; | |
219 | }; | |
220 | ||
221 | template<typename _Tp> | |
222 | struct __mv_iter_traits<_Tp*> | |
009368db | 223 | { |
1399eca1 | 224 | typedef _Tp value_type; |
05a2763e | 225 | typedef ptrdiff_t difference_type; |
1399eca1 DM |
226 | }; |
227 | ||
228 | enum | |
229 | { | |
a81408c9 PC |
230 | bits_per_byte = 8, |
231 | bits_per_block = sizeof(size_t) * size_t(bits_per_byte) | |
1399eca1 DM |
232 | }; |
233 | ||
234 | template<typename _ForwardIterator, typename _Tp, typename _Compare> | |
235 | _ForwardIterator | |
236 | __lower_bound(_ForwardIterator __first, _ForwardIterator __last, | |
237 | const _Tp& __val, _Compare __comp) | |
009368db | 238 | { |
1399eca1 DM |
239 | typedef typename __mv_iter_traits<_ForwardIterator>::difference_type |
240 | _DistanceType; | |
241 | ||
242 | _DistanceType __len = __last - __first; | |
243 | _DistanceType __half; | |
244 | _ForwardIterator __middle; | |
245 | ||
246 | while (__len > 0) | |
009368db | 247 | { |
1399eca1 DM |
248 | __half = __len >> 1; |
249 | __middle = __first; | |
250 | __middle += __half; | |
251 | if (__comp(*__middle, __val)) | |
009368db | 252 | { |
1399eca1 DM |
253 | __first = __middle; |
254 | ++__first; | |
255 | __len = __len - __half - 1; | |
009368db DM |
256 | } |
257 | else | |
1399eca1 | 258 | __len = __half; |
009368db | 259 | } |
1399eca1 | 260 | return __first; |
009368db | 261 | } |
1399eca1 | 262 | |
4c10d7f0 DM |
263 | /** @brief The number of Blocks pointed to by the address pair |
264 | * passed to the function. | |
265 | */ | |
1399eca1 DM |
266 | template<typename _AddrPair> |
267 | inline size_t | |
268 | __num_blocks(_AddrPair __ap) | |
269 | { return (__ap.second - __ap.first) + 1; } | |
270 | ||
4c10d7f0 DM |
271 | /** @brief The number of Bit-maps pointed to by the address pair |
272 | * passed to the function. | |
273 | */ | |
1399eca1 | 274 | template<typename _AddrPair> |
a8155711 | 275 | inline size_t |
1399eca1 | 276 | __num_bitmaps(_AddrPair __ap) |
a81408c9 | 277 | { return __num_blocks(__ap) / size_t(bits_per_block); } |
1399eca1 DM |
278 | |
279 | // _Tp should be a pointer type. | |
280 | template<typename _Tp> | |
281 | class _Inclusive_between | |
282 | : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> | |
283 | { | |
284 | typedef _Tp pointer; | |
285 | pointer _M_ptr_value; | |
286 | typedef typename std::pair<_Tp, _Tp> _Block_pair; | |
287 | ||
288 | public: | |
289 | _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr) | |
290 | { } | |
291 | ||
292 | bool | |
293 | operator()(_Block_pair __bp) const throw() | |
294 | { | |
295 | if (std::less_equal<pointer>()(_M_ptr_value, __bp.second) | |
296 | && std::greater_equal<pointer>()(_M_ptr_value, __bp.first)) | |
297 | return true; | |
298 | else | |
299 | return false; | |
300 | } | |
301 | }; | |
302 | ||
303 | // Used to pass a Functor to functions by reference. | |
304 | template<typename _Functor> | |
305 | class _Functor_Ref | |
306 | : public std::unary_function<typename _Functor::argument_type, | |
307 | typename _Functor::result_type> | |
308 | { | |
309 | _Functor& _M_fref; | |
310 | ||
311 | public: | |
312 | typedef typename _Functor::argument_type argument_type; | |
313 | typedef typename _Functor::result_type result_type; | |
314 | ||
315 | _Functor_Ref(_Functor& __fref) : _M_fref(__fref) | |
316 | { } | |
317 | ||
318 | result_type | |
319 | operator()(argument_type __arg) | |
320 | { return _M_fref(__arg); } | |
321 | }; | |
322 | ||
4c10d7f0 DM |
323 | /** @class _Ffit_finder bitmap_allocator.h bitmap_allocator.h |
324 | * | |
325 | * @brief The class which acts as a predicate for applying the | |
326 | * first-fit memory allocation policy for the bitmap allocator. | |
327 | */ | |
1399eca1 DM |
328 | // _Tp should be a pointer type, and _Alloc is the Allocator for |
329 | // the vector. | |
330 | template<typename _Tp> | |
331 | class _Ffit_finder | |
332 | : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> | |
333 | { | |
334 | typedef typename std::pair<_Tp, _Tp> _Block_pair; | |
78a53887 | 335 | typedef typename __detail::__mini_vector<_Block_pair> _BPVector; |
1399eca1 DM |
336 | typedef typename _BPVector::difference_type _Counter_type; |
337 | ||
a8155711 DM |
338 | size_t* _M_pbitmap; |
339 | _Counter_type _M_data_offset; | |
1399eca1 DM |
340 | |
341 | public: | |
342 | _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0) | |
343 | { } | |
344 | ||
345 | bool | |
346 | operator()(_Block_pair __bp) throw() | |
347 | { | |
a8155711 DM |
348 | // Set the _rover to the last physical location bitmap, |
349 | // which is the bitmap which belongs to the first free | |
350 | // block. Thus, the bitmaps are in exact reverse order of | |
28dac70a | 351 | // the actual memory layout. So, we count down the bitmaps, |
a8155711 | 352 | // which is the same as moving up the memory. |
1399eca1 DM |
353 | |
354 | // If the used count stored at the start of the Bit Map headers | |
355 | // is equal to the number of Objects that the current Block can | |
356 | // store, then there is definitely no space for another single | |
357 | // object, so just return false. | |
a020110e | 358 | _Counter_type __diff = __detail::__num_bitmaps(__bp); |
1399eca1 | 359 | |
a8155711 | 360 | if (*(reinterpret_cast<size_t*> |
a020110e | 361 | (__bp.first) - (__diff + 1)) == __detail::__num_blocks(__bp)) |
1399eca1 DM |
362 | return false; |
363 | ||
a8155711 | 364 | size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1; |
1399eca1 DM |
365 | |
366 | for (_Counter_type __i = 0; __i < __diff; ++__i) | |
367 | { | |
368 | _M_data_offset = __i; | |
369 | if (*__rover) | |
370 | { | |
371 | _M_pbitmap = __rover; | |
372 | return true; | |
373 | } | |
374 | --__rover; | |
375 | } | |
376 | return false; | |
377 | } | |
009368db | 378 | |
a8155711 | 379 | size_t* |
1399eca1 DM |
380 | _M_get() const throw() |
381 | { return _M_pbitmap; } | |
382 | ||
a8155711 | 383 | _Counter_type |
1399eca1 | 384 | _M_offset() const throw() |
a81408c9 | 385 | { return _M_data_offset * size_t(bits_per_block); } |
1399eca1 DM |
386 | }; |
387 | ||
4c10d7f0 DM |
388 | /** @class _Bitmap_counter bitmap_allocator.h bitmap_allocator.h |
389 | * | |
390 | * @brief The bitmap counter which acts as the bitmap | |
391 | * manipulator, and manages the bit-manipulation functions and | |
392 | * the searching and identification functions on the bit-map. | |
393 | */ | |
1399eca1 DM |
394 | // _Tp should be a pointer type. |
395 | template<typename _Tp> | |
396 | class _Bitmap_counter | |
009368db | 397 | { |
a020110e PC |
398 | typedef typename |
399 | __detail::__mini_vector<typename std::pair<_Tp, _Tp> > _BPVector; | |
1399eca1 DM |
400 | typedef typename _BPVector::size_type _Index_type; |
401 | typedef _Tp pointer; | |
a020110e | 402 | |
1399eca1 | 403 | _BPVector& _M_vbp; |
a8155711 DM |
404 | size_t* _M_curr_bmap; |
405 | size_t* _M_last_bmap_in_block; | |
1399eca1 DM |
406 | _Index_type _M_curr_index; |
407 | ||
408 | public: | |
409 | // Use the 2nd parameter with care. Make sure that such an | |
410 | // entry exists in the vector before passing that particular | |
411 | // index to this ctor. | |
a8155711 | 412 | _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp) |
1399eca1 DM |
413 | { this->_M_reset(__index); } |
414 | ||
415 | void | |
a8155711 | 416 | _M_reset(long __index = -1) throw() |
1399eca1 DM |
417 | { |
418 | if (__index == -1) | |
419 | { | |
420 | _M_curr_bmap = 0; | |
421 | _M_curr_index = static_cast<_Index_type>(-1); | |
422 | return; | |
423 | } | |
009368db | 424 | |
1399eca1 | 425 | _M_curr_index = __index; |
a8155711 | 426 | _M_curr_bmap = reinterpret_cast<size_t*> |
1399eca1 | 427 | (_M_vbp[_M_curr_index].first) - 1; |
a8155711 | 428 | |
47bea7b8 | 429 | _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1); |
1399eca1 DM |
430 | |
431 | _M_last_bmap_in_block = _M_curr_bmap | |
432 | - ((_M_vbp[_M_curr_index].second | |
433 | - _M_vbp[_M_curr_index].first + 1) | |
a81408c9 | 434 | / size_t(bits_per_block) - 1); |
1399eca1 | 435 | } |
009368db | 436 | |
1399eca1 DM |
437 | // Dangerous Function! Use with extreme care. Pass to this |
438 | // function ONLY those values that are known to be correct, | |
439 | // otherwise this will mess up big time. | |
440 | void | |
a8155711 | 441 | _M_set_internal_bitmap(size_t* __new_internal_marker) throw() |
1399eca1 DM |
442 | { _M_curr_bmap = __new_internal_marker; } |
443 | ||
444 | bool | |
445 | _M_finished() const throw() | |
446 | { return(_M_curr_bmap == 0); } | |
447 | ||
448 | _Bitmap_counter& | |
449 | operator++() throw() | |
450 | { | |
451 | if (_M_curr_bmap == _M_last_bmap_in_block) | |
452 | { | |
453 | if (++_M_curr_index == _M_vbp.size()) | |
454 | _M_curr_bmap = 0; | |
455 | else | |
456 | this->_M_reset(_M_curr_index); | |
457 | } | |
458 | else | |
459 | --_M_curr_bmap; | |
460 | return *this; | |
461 | } | |
462 | ||
a8155711 | 463 | size_t* |
1399eca1 DM |
464 | _M_get() const throw() |
465 | { return _M_curr_bmap; } | |
466 | ||
467 | pointer | |
468 | _M_base() const throw() | |
469 | { return _M_vbp[_M_curr_index].first; } | |
009368db | 470 | |
a8155711 | 471 | _Index_type |
1399eca1 DM |
472 | _M_offset() const throw() |
473 | { | |
a81408c9 | 474 | return size_t(bits_per_block) |
a8155711 | 475 | * ((reinterpret_cast<size_t*>(this->_M_base()) |
1399eca1 DM |
476 | - _M_curr_bmap) - 1); |
477 | } | |
478 | ||
a8155711 | 479 | _Index_type |
1399eca1 DM |
480 | _M_where() const throw() |
481 | { return _M_curr_index; } | |
482 | }; | |
009368db | 483 | |
4c10d7f0 DM |
484 | /** @brief Mark a memory address as allocated by re-setting the |
485 | * corresponding bit in the bit-map. | |
486 | */ | |
1399eca1 | 487 | inline void |
a8155711 | 488 | __bit_allocate(size_t* __pbmap, size_t __pos) throw() |
009368db | 489 | { |
a8155711 | 490 | size_t __mask = 1 << __pos; |
1399eca1 DM |
491 | __mask = ~__mask; |
492 | *__pbmap &= __mask; | |
009368db | 493 | } |
009368db | 494 | |
4c10d7f0 DM |
495 | /** @brief Mark a memory address as free by setting the |
496 | * corresponding bit in the bit-map. | |
497 | */ | |
1399eca1 | 498 | inline void |
a8155711 | 499 | __bit_free(size_t* __pbmap, size_t __pos) throw() |
1399eca1 | 500 | { |
a8155711 | 501 | size_t __mask = 1 << __pos; |
1399eca1 DM |
502 | *__pbmap |= __mask; |
503 | } | |
12ffa228 BK |
504 | |
505 | _GLIBCXX_END_NAMESPACE_VERSION | |
78a53887 | 506 | } // namespace __detail |
009368db | 507 | |
12ffa228 BK |
508 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
509 | ||
4c10d7f0 DM |
510 | /** @brief Generic Version of the bsf instruction. |
511 | */ | |
a8155711 DM |
512 | inline size_t |
513 | _Bit_scan_forward(size_t __num) | |
514 | { return static_cast<size_t>(__builtin_ctzl(__num)); } | |
1399eca1 | 515 | |
4c10d7f0 DM |
516 | /** @class free_list bitmap_allocator.h bitmap_allocator.h |
517 | * | |
518 | * @brief The free list class for managing chunks of memory to be | |
519 | * given to and returned by the bitmap_allocator. | |
520 | */ | |
1399eca1 DM |
521 | class free_list |
522 | { | |
d0940d56 | 523 | public: |
2e362c74 | 524 | typedef size_t* value_type; |
78a53887 | 525 | typedef __detail::__mini_vector<value_type> vector_type; |
2e362c74 | 526 | typedef vector_type::iterator iterator; |
56acf88c | 527 | typedef __mutex __mutex_type; |
1399eca1 | 528 | |
d0940d56 | 529 | private: |
1399eca1 DM |
530 | struct _LT_pointer_compare |
531 | { | |
532 | bool | |
a8155711 DM |
533 | operator()(const size_t* __pui, |
534 | const size_t __cui) const throw() | |
1399eca1 | 535 | { return *__pui < __cui; } |
009368db DM |
536 | }; |
537 | ||
57b11c96 | 538 | #if defined __GTHREADS |
56acf88c | 539 | __mutex_type& |
57b11c96 BK |
540 | _M_get_mutex() |
541 | { | |
56acf88c | 542 | static __mutex_type _S_mutex; |
2e362c74 | 543 | return _S_mutex; |
57b11c96 | 544 | } |
009368db | 545 | #endif |
57b11c96 BK |
546 | |
547 | vector_type& | |
548 | _M_get_free_list() | |
549 | { | |
550 | static vector_type _S_free_list; | |
551 | return _S_free_list; | |
552 | } | |
4c10d7f0 DM |
553 | |
554 | /** @brief Performs validation of memory based on their size. | |
555 | * | |
556 | * @param __addr The pointer to the memory block to be | |
557 | * validated. | |
558 | * | |
93c66bc6 | 559 | * Validates the memory block passed to this function and |
4c10d7f0 DM |
560 | * appropriately performs the action of managing the free list of |
561 | * blocks by adding this block to the free list or deleting this | |
562 | * or larger blocks from the free list. | |
563 | */ | |
1399eca1 | 564 | void |
a8155711 | 565 | _M_validate(size_t* __addr) throw() |
009368db | 566 | { |
57b11c96 | 567 | vector_type& __free_list = _M_get_free_list(); |
a8155711 | 568 | const vector_type::size_type __max_size = 64; |
57b11c96 | 569 | if (__free_list.size() >= __max_size) |
009368db | 570 | { |
1399eca1 DM |
571 | // Ok, the threshold value has been reached. We determine |
572 | // which block to remove from the list of free blocks. | |
57b11c96 | 573 | if (*__addr >= *__free_list.back()) |
009368db | 574 | { |
1399eca1 DM |
575 | // Ok, the new block is greater than or equal to the |
576 | // last block in the list of free blocks. We just free | |
577 | // the new block. | |
0d6b41f2 | 578 | ::operator delete(static_cast<void*>(__addr)); |
009368db DM |
579 | return; |
580 | } | |
581 | else | |
582 | { | |
1399eca1 | 583 | // Deallocate the last block in the list of free lists, |
28dac70a | 584 | // and insert the new one in its correct position. |
57b11c96 BK |
585 | ::operator delete(static_cast<void*>(__free_list.back())); |
586 | __free_list.pop_back(); | |
009368db DM |
587 | } |
588 | } | |
589 | ||
1399eca1 | 590 | // Just add the block to the list of free lists unconditionally. |
a020110e | 591 | iterator __temp = __detail::__lower_bound |
57b11c96 | 592 | (__free_list.begin(), __free_list.end(), |
1399eca1 DM |
593 | *__addr, _LT_pointer_compare()); |
594 | ||
595 | // We may insert the new free list before _temp; | |
57b11c96 | 596 | __free_list.insert(__temp, __addr); |
009368db DM |
597 | } |
598 | ||
4c10d7f0 DM |
599 | /** @brief Decides whether the wastage of memory is acceptable for |
600 | * the current memory request and returns accordingly. | |
601 | * | |
602 | * @param __block_size The size of the block available in the free | |
603 | * list. | |
604 | * | |
605 | * @param __required_size The required size of the memory block. | |
606 | * | |
607 | * @return true if the wastage incurred is acceptable, else returns | |
608 | * false. | |
609 | */ | |
1399eca1 | 610 | bool |
a8155711 DM |
611 | _M_should_i_give(size_t __block_size, |
612 | size_t __required_size) throw() | |
009368db | 613 | { |
a8155711 | 614 | const size_t __max_wastage_percentage = 36; |
009368db | 615 | if (__block_size >= __required_size && |
1399eca1 DM |
616 | (((__block_size - __required_size) * 100 / __block_size) |
617 | < __max_wastage_percentage)) | |
009368db DM |
618 | return true; |
619 | else | |
620 | return false; | |
621 | } | |
622 | ||
623 | public: | |
4c10d7f0 DM |
624 | /** @brief This function returns the block of memory to the |
625 | * internal free list. | |
626 | * | |
627 | * @param __addr The pointer to the memory block that was given | |
628 | * by a call to the _M_get function. | |
629 | */ | |
1399eca1 | 630 | inline void |
a8155711 | 631 | _M_insert(size_t* __addr) throw() |
009368db DM |
632 | { |
633 | #if defined __GTHREADS | |
a020110e | 634 | __scoped_lock __bfl_lock(_M_get_mutex()); |
009368db | 635 | #endif |
1399eca1 DM |
636 | // Call _M_validate to decide what should be done with |
637 | // this particular free list. | |
a8155711 DM |
638 | this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1); |
639 | // See discussion as to why this is 1! | |
009368db DM |
640 | } |
641 | ||
4c10d7f0 DM |
642 | /** @brief This function gets a block of memory of the specified |
643 | * size from the free list. | |
644 | * | |
645 | * @param __sz The size in bytes of the memory required. | |
646 | * | |
647 | * @return A pointer to the new memory block of size at least | |
648 | * equal to that requested. | |
649 | */ | |
a8155711 DM |
650 | size_t* |
651 | _M_get(size_t __sz) throw(std::bad_alloc); | |
009368db | 652 | |
4c10d7f0 DM |
653 | /** @brief This function just clears the internal Free List, and |
654 | * gives back all the memory to the OS. | |
655 | */ | |
1399eca1 DM |
656 | void |
657 | _M_clear(); | |
009368db DM |
658 | }; |
659 | ||
009368db | 660 | |
1399eca1 DM |
661 | // Forward declare the class. |
662 | template<typename _Tp> | |
663 | class bitmap_allocator; | |
009368db | 664 | |
1399eca1 DM |
665 | // Specialize for void: |
666 | template<> | |
667 | class bitmap_allocator<void> | |
009368db | 668 | { |
1399eca1 DM |
669 | public: |
670 | typedef void* pointer; | |
671 | typedef const void* const_pointer; | |
009368db | 672 | |
1399eca1 DM |
673 | // Reference-to-void members are impossible. |
674 | typedef void value_type; | |
675 | template<typename _Tp1> | |
676 | struct rebind | |
677 | { | |
678 | typedef bitmap_allocator<_Tp1> other; | |
679 | }; | |
680 | }; | |
009368db | 681 | |
5b9daa7e BK |
682 | /** |
683 | * @brief Bitmap Allocator, primary template. | |
684 | * @ingroup allocators | |
685 | */ | |
1399eca1 DM |
686 | template<typename _Tp> |
687 | class bitmap_allocator : private free_list | |
009368db | 688 | { |
1399eca1 | 689 | public: |
2e362c74 BK |
690 | typedef size_t size_type; |
691 | typedef ptrdiff_t difference_type; | |
692 | typedef _Tp* pointer; | |
693 | typedef const _Tp* const_pointer; | |
694 | typedef _Tp& reference; | |
695 | typedef const _Tp& const_reference; | |
696 | typedef _Tp value_type; | |
56acf88c | 697 | typedef free_list::__mutex_type __mutex_type; |
2e362c74 | 698 | |
1399eca1 DM |
699 | template<typename _Tp1> |
700 | struct rebind | |
701 | { | |
702 | typedef bitmap_allocator<_Tp1> other; | |
703 | }; | |
009368db | 704 | |
1b5dc776 JW |
705 | #if __cplusplus >= 201103L |
706 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
707 | // 2103. propagate_on_container_move_assignment | |
708 | typedef std::true_type propagate_on_container_move_assignment; | |
709 | #endif | |
710 | ||
1399eca1 | 711 | private: |
a8155711 | 712 | template<size_t _BSize, size_t _AlignSize> |
1399eca1 DM |
713 | struct aligned_size |
714 | { | |
715 | enum | |
716 | { | |
717 | modulus = _BSize % _AlignSize, | |
718 | value = _BSize + (modulus ? _AlignSize - (modulus) : 0) | |
719 | }; | |
720 | }; | |
721 | ||
722 | struct _Alloc_block | |
723 | { | |
a8155711 DM |
724 | char __M_unused[aligned_size<sizeof(value_type), |
725 | _BALLOC_ALIGN_BYTES>::value]; | |
1399eca1 | 726 | }; |
009368db DM |
727 | |
728 | ||
1399eca1 | 729 | typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair; |
009368db | 730 | |
a020110e PC |
731 | typedef typename __detail::__mini_vector<_Block_pair> _BPVector; |
732 | typedef typename _BPVector::iterator _BPiter; | |
733 | ||
734 | template<typename _Predicate> | |
735 | static _BPiter | |
736 | _S_find(_Predicate __p) | |
737 | { | |
738 | _BPiter __first = _S_mem_blocks.begin(); | |
739 | while (__first != _S_mem_blocks.end() && !__p(*__first)) | |
740 | ++__first; | |
741 | return __first; | |
742 | } | |
009368db | 743 | |
47bea7b8 | 744 | #if defined _GLIBCXX_DEBUG |
1399eca1 DM |
745 | // Complexity: O(lg(N)). Where, N is the number of block of size |
746 | // sizeof(value_type). | |
747 | void | |
748 | _S_check_for_free_blocks() throw() | |
749 | { | |
a020110e PC |
750 | typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; |
751 | _BPiter __bpi = _S_find(_FFF()); | |
1399eca1 | 752 | |
47bea7b8 | 753 | _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end()); |
1399eca1 | 754 | } |
009368db DM |
755 | #endif |
756 | ||
4c10d7f0 DM |
757 | /** @brief Responsible for exponentially growing the internal |
758 | * memory pool. | |
759 | * | |
760 | * @throw std::bad_alloc. If memory can not be allocated. | |
761 | * | |
93c66bc6 | 762 | * Complexity: O(1), but internally depends upon the |
4c10d7f0 DM |
763 | * complexity of the function free_list::_M_get. The part where |
764 | * the bitmap headers are written has complexity: O(X),where X | |
765 | * is the number of blocks of size sizeof(value_type) within | |
766 | * the newly acquired block. Having a tight bound. | |
767 | */ | |
1399eca1 DM |
768 | void |
769 | _S_refill_pool() throw(std::bad_alloc) | |
770 | { | |
47bea7b8 | 771 | #if defined _GLIBCXX_DEBUG |
1399eca1 DM |
772 | _S_check_for_free_blocks(); |
773 | #endif | |
009368db | 774 | |
a81408c9 | 775 | const size_t __num_bitmaps = (_S_block_size |
78a53887 | 776 | / size_t(__detail::bits_per_block)); |
a8155711 | 777 | const size_t __size_to_allocate = sizeof(size_t) |
1399eca1 | 778 | + _S_block_size * sizeof(_Alloc_block) |
a8155711 | 779 | + __num_bitmaps * sizeof(size_t); |
1399eca1 | 780 | |
a020110e PC |
781 | size_t* __temp = |
782 | reinterpret_cast<size_t*>(this->_M_get(__size_to_allocate)); | |
1399eca1 | 783 | *__temp = 0; |
a8155711 | 784 | ++__temp; |
1399eca1 DM |
785 | |
786 | // The Header information goes at the Beginning of the Block. | |
787 | _Block_pair __bp = | |
788 | std::make_pair(reinterpret_cast<_Alloc_block*> | |
789 | (__temp + __num_bitmaps), | |
790 | reinterpret_cast<_Alloc_block*> | |
791 | (__temp + __num_bitmaps) | |
792 | + _S_block_size - 1); | |
793 | ||
794 | // Fill the Vector with this information. | |
795 | _S_mem_blocks.push_back(__bp); | |
009368db | 796 | |
a8155711 | 797 | for (size_t __i = 0; __i < __num_bitmaps; ++__i) |
a020110e | 798 | __temp[__i] = ~static_cast<size_t>(0); // 1 Indicates all Free. |
009368db | 799 | |
1399eca1 DM |
800 | _S_block_size *= 2; |
801 | } | |
009368db | 802 | |
1399eca1 | 803 | static _BPVector _S_mem_blocks; |
a8155711 | 804 | static size_t _S_block_size; |
a020110e | 805 | static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request; |
1399eca1 | 806 | static typename _BPVector::size_type _S_last_dealloc_index; |
009368db | 807 | #if defined __GTHREADS |
56acf88c | 808 | static __mutex_type _S_mut; |
009368db DM |
809 | #endif |
810 | ||
1399eca1 DM |
811 | public: |
812 | ||
4c10d7f0 DM |
813 | /** @brief Allocates memory for a single object of size |
814 | * sizeof(_Tp). | |
815 | * | |
816 | * @throw std::bad_alloc. If memory can not be allocated. | |
817 | * | |
93c66bc6 | 818 | * Complexity: Worst case complexity is O(N), but that |
4c10d7f0 DM |
819 | * is hardly ever hit. If and when this particular case is |
820 | * encountered, the next few cases are guaranteed to have a | |
821 | * worst case complexity of O(1)! That's why this function | |
822 | * performs very well on average. You can consider this | |
823 | * function to have a complexity referred to commonly as: | |
824 | * Amortized Constant time. | |
825 | */ | |
1399eca1 DM |
826 | pointer |
827 | _M_allocate_single_object() throw(std::bad_alloc) | |
828 | { | |
009368db | 829 | #if defined __GTHREADS |
a020110e | 830 | __scoped_lock __bit_lock(_S_mut); |
009368db | 831 | #endif |
71f9a9d1 | 832 | |
1399eca1 DM |
833 | // The algorithm is something like this: The last_request |
834 | // variable points to the last accessed Bit Map. When such a | |
835 | // condition occurs, we try to find a free block in the | |
836 | // current bitmap, or succeeding bitmaps until the last bitmap | |
837 | // is reached. If no free block turns up, we resort to First | |
838 | // Fit method. | |
839 | ||
840 | // WARNING: Do not re-order the condition in the while | |
841 | // statement below, because it relies on C++'s short-circuit | |
842 | // evaluation. The return from _S_last_request->_M_get() will | |
843 | // NOT be dereference able if _S_last_request->_M_finished() | |
844 | // returns true. This would inevitably lead to a NULL pointer | |
845 | // dereference if tinkered with. | |
846 | while (_S_last_request._M_finished() == false | |
847 | && (*(_S_last_request._M_get()) == 0)) | |
a020110e | 848 | _S_last_request.operator++(); |
009368db | 849 | |
1399eca1 DM |
850 | if (__builtin_expect(_S_last_request._M_finished() == true, false)) |
851 | { | |
852 | // Fall Back to First Fit algorithm. | |
a020110e | 853 | typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; |
1399eca1 | 854 | _FFF __fff; |
a020110e | 855 | _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff)); |
1399eca1 DM |
856 | |
857 | if (__bpi != _S_mem_blocks.end()) | |
858 | { | |
859 | // Search was successful. Ok, now mark the first bit from | |
860 | // the right as 0, meaning Allocated. This bit is obtained | |
861 | // by calling _M_get() on __fff. | |
a8155711 | 862 | size_t __nz_bit = _Bit_scan_forward(*__fff._M_get()); |
78a53887 | 863 | __detail::__bit_allocate(__fff._M_get(), __nz_bit); |
1399eca1 DM |
864 | |
865 | _S_last_request._M_reset(__bpi - _S_mem_blocks.begin()); | |
866 | ||
867 | // Now, get the address of the bit we marked as allocated. | |
868 | pointer __ret = reinterpret_cast<pointer> | |
869 | (__bpi->first + __fff._M_offset() + __nz_bit); | |
a8155711 DM |
870 | size_t* __puse_count = |
871 | reinterpret_cast<size_t*> | |
a020110e | 872 | (__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1); |
1399eca1 DM |
873 | |
874 | ++(*__puse_count); | |
875 | return __ret; | |
876 | } | |
877 | else | |
878 | { | |
879 | // Search was unsuccessful. We Add more memory to the | |
880 | // pool by calling _S_refill_pool(). | |
881 | _S_refill_pool(); | |
009368db | 882 | |
1399eca1 DM |
883 | // _M_Reset the _S_last_request structure to the first |
884 | // free block's bit map. | |
885 | _S_last_request._M_reset(_S_mem_blocks.size() - 1); | |
009368db | 886 | |
1399eca1 DM |
887 | // Now, mark that bit as allocated. |
888 | } | |
889 | } | |
009368db | 890 | |
1399eca1 DM |
891 | // _S_last_request holds a pointer to a valid bit map, that |
892 | // points to a free block in memory. | |
a8155711 | 893 | size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get()); |
78a53887 | 894 | __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit); |
1399eca1 DM |
895 | |
896 | pointer __ret = reinterpret_cast<pointer> | |
897 | (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit); | |
898 | ||
a8155711 DM |
899 | size_t* __puse_count = reinterpret_cast<size_t*> |
900 | (_S_mem_blocks[_S_last_request._M_where()].first) | |
a020110e | 901 | - (__detail:: |
a8155711 | 902 | __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1); |
1399eca1 DM |
903 | |
904 | ++(*__puse_count); | |
905 | return __ret; | |
906 | } | |
907 | ||
4c10d7f0 DM |
908 | /** @brief Deallocates memory that belongs to a single object of |
909 | * size sizeof(_Tp). | |
910 | * | |
93c66bc6 | 911 | * Complexity: O(lg(N)), but the worst case is not hit |
4c10d7f0 DM |
912 | * often! This is because containers usually deallocate memory |
913 | * close to each other and this case is handled in O(1) time by | |
914 | * the deallocate function. | |
915 | */ | |
1399eca1 DM |
916 | void |
917 | _M_deallocate_single_object(pointer __p) throw() | |
918 | { | |
009368db | 919 | #if defined __GTHREADS |
a020110e | 920 | __scoped_lock __bit_lock(_S_mut); |
009368db | 921 | #endif |
1399eca1 | 922 | _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p); |
009368db | 923 | |
1399eca1 DM |
924 | typedef typename _BPVector::iterator _Iterator; |
925 | typedef typename _BPVector::difference_type _Difference_type; | |
71f9a9d1 | 926 | |
1399eca1 | 927 | _Difference_type __diff; |
a8155711 | 928 | long __displacement; |
009368db | 929 | |
47bea7b8 | 930 | _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); |
009368db | 931 | |
a020110e PC |
932 | __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p); |
933 | if (__ibt(_S_mem_blocks[_S_last_dealloc_index])) | |
1399eca1 | 934 | { |
56acf88c PC |
935 | _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index |
936 | <= _S_mem_blocks.size() - 1); | |
009368db | 937 | |
1399eca1 DM |
938 | // Initial Assumption was correct! |
939 | __diff = _S_last_dealloc_index; | |
940 | __displacement = __real_p - _S_mem_blocks[__diff].first; | |
941 | } | |
942 | else | |
943 | { | |
a020110e | 944 | _Iterator _iter = _S_find(__ibt); |
a8155711 | 945 | |
47bea7b8 | 946 | _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end()); |
1399eca1 DM |
947 | |
948 | __diff = _iter - _S_mem_blocks.begin(); | |
949 | __displacement = __real_p - _S_mem_blocks[__diff].first; | |
950 | _S_last_dealloc_index = __diff; | |
951 | } | |
009368db | 952 | |
1399eca1 | 953 | // Get the position of the iterator that has been found. |
a81408c9 | 954 | const size_t __rotate = (__displacement |
78a53887 | 955 | % size_t(__detail::bits_per_block)); |
a8155711 DM |
956 | size_t* __bitmapC = |
957 | reinterpret_cast<size_t*> | |
958 | (_S_mem_blocks[__diff].first) - 1; | |
78a53887 | 959 | __bitmapC -= (__displacement / size_t(__detail::bits_per_block)); |
009368db | 960 | |
78a53887 | 961 | __detail::__bit_free(__bitmapC, __rotate); |
a8155711 DM |
962 | size_t* __puse_count = reinterpret_cast<size_t*> |
963 | (_S_mem_blocks[__diff].first) | |
a020110e | 964 | - (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1); |
1399eca1 | 965 | |
47bea7b8 | 966 | _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0); |
009368db | 967 | |
1399eca1 | 968 | --(*__puse_count); |
009368db | 969 | |
1399eca1 DM |
970 | if (__builtin_expect(*__puse_count == 0, false)) |
971 | { | |
972 | _S_block_size /= 2; | |
009368db | 973 | |
1399eca1 DM |
974 | // We can safely remove this block. |
975 | // _Block_pair __bp = _S_mem_blocks[__diff]; | |
976 | this->_M_insert(__puse_count); | |
977 | _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff); | |
978 | ||
979 | // Reset the _S_last_request variable to reflect the | |
980 | // erased block. We do this to protect future requests | |
981 | // after the last block has been removed from a particular | |
982 | // memory Chunk, which in turn has been returned to the | |
983 | // free list, and hence had been erased from the vector, | |
984 | // so the size of the vector gets reduced by 1. | |
985 | if ((_Difference_type)_S_last_request._M_where() >= __diff--) | |
986 | _S_last_request._M_reset(__diff); | |
987 | ||
988 | // If the Index into the vector of the region of memory | |
989 | // that might hold the next address that will be passed to | |
990 | // deallocated may have been invalidated due to the above | |
991 | // erase procedure being called on the vector, hence we | |
992 | // try to restore this invariant too. | |
993 | if (_S_last_dealloc_index >= _S_mem_blocks.size()) | |
994 | { | |
995 | _S_last_dealloc_index =(__diff != -1 ? __diff : 0); | |
47bea7b8 | 996 | _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); |
1399eca1 DM |
997 | } |
998 | } | |
999 | } | |
009368db | 1000 | |
1399eca1 | 1001 | public: |
7d9cb054 | 1002 | bitmap_allocator() _GLIBCXX_USE_NOEXCEPT |
1399eca1 | 1003 | { } |
009368db | 1004 | |
7d9cb054 | 1005 | bitmap_allocator(const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT |
1399eca1 | 1006 | { } |
71f9a9d1 | 1007 | |
1399eca1 | 1008 | template<typename _Tp1> |
7d9cb054 | 1009 | bitmap_allocator(const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT |
1399eca1 | 1010 | { } |
71f9a9d1 | 1011 | |
7d9cb054 | 1012 | ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT |
1399eca1 | 1013 | { } |
71f9a9d1 | 1014 | |
1399eca1 DM |
1015 | pointer |
1016 | allocate(size_type __n) | |
1017 | { | |
e762c6f4 | 1018 | if (__n > this->max_size()) |
a063e891 PC |
1019 | std::__throw_bad_alloc(); |
1020 | ||
1399eca1 DM |
1021 | if (__builtin_expect(__n == 1, true)) |
1022 | return this->_M_allocate_single_object(); | |
1023 | else | |
1024 | { | |
1025 | const size_type __b = __n * sizeof(value_type); | |
1026 | return reinterpret_cast<pointer>(::operator new(__b)); | |
1027 | } | |
1028 | } | |
71f9a9d1 | 1029 | |
1399eca1 DM |
1030 | pointer |
1031 | allocate(size_type __n, typename bitmap_allocator<void>::const_pointer) | |
1032 | { return allocate(__n); } | |
71f9a9d1 | 1033 | |
1399eca1 DM |
1034 | void |
1035 | deallocate(pointer __p, size_type __n) throw() | |
1036 | { | |
0d6b41f2 PC |
1037 | if (__builtin_expect(__p != 0, true)) |
1038 | { | |
1039 | if (__builtin_expect(__n == 1, true)) | |
1040 | this->_M_deallocate_single_object(__p); | |
1041 | else | |
1042 | ::operator delete(__p); | |
1043 | } | |
1399eca1 | 1044 | } |
71f9a9d1 | 1045 | |
1399eca1 | 1046 | pointer |
7d9cb054 | 1047 | address(reference __r) const _GLIBCXX_NOEXCEPT |
882b3d5c | 1048 | { return std::__addressof(__r); } |
71f9a9d1 | 1049 | |
1399eca1 | 1050 | const_pointer |
7d9cb054 | 1051 | address(const_reference __r) const _GLIBCXX_NOEXCEPT |
882b3d5c | 1052 | { return std::__addressof(__r); } |
009368db | 1053 | |
1399eca1 | 1054 | size_type |
7d9cb054 | 1055 | max_size() const _GLIBCXX_USE_NOEXCEPT |
a063e891 | 1056 | { return size_type(-1) / sizeof(value_type); } |
009368db | 1057 | |
734f5023 | 1058 | #if __cplusplus >= 201103L |
45ba8f9f JW |
1059 | template<typename _Up, typename... _Args> |
1060 | void | |
1061 | construct(_Up* __p, _Args&&... __args) | |
1062 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); } | |
1063 | ||
1064 | template<typename _Up> | |
1065 | void | |
1066 | destroy(_Up* __p) | |
1067 | { __p->~_Up(); } | |
1068 | #else | |
1399eca1 DM |
1069 | void |
1070 | construct(pointer __p, const_reference __data) | |
61fcb9fb PC |
1071 | { ::new((void *)__p) value_type(__data); } |
1072 | ||
1399eca1 DM |
1073 | void |
1074 | destroy(pointer __p) | |
1075 | { __p->~value_type(); } | |
45ba8f9f | 1076 | #endif |
1399eca1 | 1077 | }; |
009368db | 1078 | |
1399eca1 DM |
1079 | template<typename _Tp1, typename _Tp2> |
1080 | bool | |
1081 | operator==(const bitmap_allocator<_Tp1>&, | |
1082 | const bitmap_allocator<_Tp2>&) throw() | |
1083 | { return true; } | |
1084 | ||
1085 | template<typename _Tp1, typename _Tp2> | |
1086 | bool | |
1087 | operator!=(const bitmap_allocator<_Tp1>&, | |
1088 | const bitmap_allocator<_Tp2>&) throw() | |
1089 | { return false; } | |
009368db | 1090 | |
1399eca1 DM |
1091 | // Static member definitions. |
1092 | template<typename _Tp> | |
1093 | typename bitmap_allocator<_Tp>::_BPVector | |
1094 | bitmap_allocator<_Tp>::_S_mem_blocks; | |
009368db | 1095 | |
1399eca1 | 1096 | template<typename _Tp> |
a8155711 | 1097 | size_t bitmap_allocator<_Tp>::_S_block_size = |
78a53887 | 1098 | 2 * size_t(__detail::bits_per_block); |
009368db | 1099 | |
1399eca1 | 1100 | template<typename _Tp> |
a020110e | 1101 | typename bitmap_allocator<_Tp>::_BPVector::size_type |
1399eca1 | 1102 | bitmap_allocator<_Tp>::_S_last_dealloc_index = 0; |
009368db | 1103 | |
1399eca1 | 1104 | template<typename _Tp> |
a020110e PC |
1105 | __detail::_Bitmap_counter |
1106 | <typename bitmap_allocator<_Tp>::_Alloc_block*> | |
1399eca1 | 1107 | bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks); |
009368db DM |
1108 | |
1109 | #if defined __GTHREADS | |
1399eca1 | 1110 | template<typename _Tp> |
56acf88c | 1111 | typename bitmap_allocator<_Tp>::__mutex_type |
1399eca1 | 1112 | bitmap_allocator<_Tp>::_S_mut; |
009368db DM |
1113 | #endif |
1114 | ||
12ffa228 BK |
1115 | _GLIBCXX_END_NAMESPACE_VERSION |
1116 | } // namespace __gnu_cxx | |
009368db | 1117 | |
1399eca1 | 1118 | #endif |
009368db | 1119 |