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