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