1 // Bitmapped Allocator. -*- C++ -*-
3 // Copyright (C) 2004 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 #if !defined _BITMAP_ALLOCATOR_H
33 #define _BITMAP_ALLOCATOR_H 1
36 //For std::size_t, and ptrdiff_t.
40 //std::find_if, and std::lower_bound.
42 //For the free list of exponentially growing memory blocks. At max,
43 //size of the vector should be not more than the number of bits in an
44 //integer or an unsigned integer.
46 //For greater_equal, and less_equal.
49 #include <bits/gthr.h>
50 //For __gthread_mutex_t, __gthread_mutex_lock and __gthread_mutex_unlock.
51 #include <ext/new_allocator.h>
52 //For __gnu_cxx::new_allocator for std::vector.
57 //#define CHECK_FOR_ERRORS
58 //#define __CPU_HAS_BACKWARD_BRANCH_PREDICTION
63 #if defined __GTHREADS
64 bool const __threads_enabled = __gthread_active_p();
69 #if defined __GTHREADS
71 __gthread_mutex_t _M_mut;
72 //Prevent Copying and assignment.
73 _Mutex (_Mutex const&);
74 _Mutex& operator= (_Mutex const&);
78 if (__threads_enabled)
80 #if !defined __GTHREAD_MUTEX_INIT
81 __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut);
83 __gthread_mutex_t __mtemp = __GTHREAD_MUTEX_INIT;
90 //Gthreads does not define a Mutex Destruction Function.
92 __gthread_mutex_t *_M_get() { return &_M_mut; }
98 //Prevent Copying and assignment.
100 _Lock& operator= (_Lock const&);
102 _Lock(_Mutex* __mptr)
103 : _M_pmt(__mptr), _M_locked(false)
107 if (__threads_enabled)
110 __gthread_mutex_lock(_M_pmt->_M_get());
115 if (__threads_enabled)
117 if (__builtin_expect(_M_locked, true))
119 __gthread_mutex_unlock(_M_pmt->_M_get());
124 ~_Lock() { this->_M_unlock(); }
130 namespace __aux_balloc {
131 static const unsigned int _Bits_Per_Byte = 8;
132 static const unsigned int _Bits_Per_Block = sizeof(unsigned int) * _Bits_Per_Byte;
134 template <typename _Addr_Pair_t>
135 inline size_t __balloc_num_blocks (_Addr_Pair_t __ap)
137 return (__ap.second - __ap.first) + 1;
140 template <typename _Addr_Pair_t>
141 inline size_t __balloc_num_bit_maps (_Addr_Pair_t __ap)
143 return __balloc_num_blocks(__ap) / _Bits_Per_Block;
146 //T should be a pointer type.
147 template <typename _Tp>
148 class _Inclusive_between : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> {
150 pointer _M_ptr_value;
151 typedef typename std::pair<_Tp, _Tp> _Block_pair;
154 _Inclusive_between (pointer __ptr) : _M_ptr_value(__ptr) { }
155 bool operator () (_Block_pair __bp) const throw ()
157 if (std::less_equal<pointer> ()(_M_ptr_value, __bp.second) &&
158 std::greater_equal<pointer> ()(_M_ptr_value, __bp.first))
165 //Used to pass a Functor to functions by reference.
166 template <typename _Functor>
168 public std::unary_function<typename _Functor::argument_type, typename _Functor::result_type> {
172 typedef typename _Functor::argument_type argument_type;
173 typedef typename _Functor::result_type result_type;
175 _Functor_Ref (_Functor& __fref) : _M_fref(__fref) { }
176 result_type operator() (argument_type __arg) { return _M_fref (__arg); }
180 //T should be a pointer type, and A is the Allocator for the vector.
181 template <typename _Tp, typename _Alloc>
183 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> {
184 typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector;
185 typedef typename _BPVector::difference_type _Counter_type;
186 typedef typename std::pair<_Tp, _Tp> _Block_pair;
188 unsigned int *_M_pbitmap;
189 unsigned int _M_data_offset;
193 : _M_pbitmap (0), _M_data_offset (0)
196 bool operator() (_Block_pair __bp) throw()
198 //Set the _rover to the last unsigned integer, which is the
199 //bitmap to the first free block. Thus, the bitmaps are in exact
200 //reverse order of the actual memory layout. So, we count down
201 //the bimaps, which is the same as moving up the memory.
203 //If the used count stored at the start of the Bit Map headers
204 //is equal to the number of Objects that the current Block can
205 //store, then there is definitely no space for another single
206 //object, so just return false.
207 _Counter_type __diff = __gnu_cxx::__aux_balloc::__balloc_num_bit_maps (__bp);
209 assert (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) <=
210 __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp));
212 if (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) ==
213 __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp))
216 unsigned int *__rover = reinterpret_cast<unsigned int*>(__bp.first) - 1;
217 for (_Counter_type __i = 0; __i < __diff; ++__i)
219 _M_data_offset = __i;
222 _M_pbitmap = __rover;
230 unsigned int *_M_get () { return _M_pbitmap; }
231 unsigned int _M_offset () { return _M_data_offset * _Bits_Per_Block; }
234 //T should be a pointer type.
235 template <typename _Tp, typename _Alloc>
236 class _Bit_map_counter {
238 typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector;
239 typedef typename _BPVector::size_type _Index_type;
243 unsigned int *_M_curr_bmap;
244 unsigned int *_M_last_bmap_in_block;
245 _Index_type _M_curr_index;
248 //Use the 2nd parameter with care. Make sure that such an entry
249 //exists in the vector before passing that particular index to
251 _Bit_map_counter (_BPVector& Rvbp, int __index = -1)
254 this->_M_reset(__index);
257 void _M_reset (int __index = -1) throw()
262 _M_curr_index = (_Index_type)-1;
266 _M_curr_index = __index;
267 _M_curr_bmap = reinterpret_cast<unsigned int*>(_M_vbp[_M_curr_index].first) - 1;
269 assert (__index <= (int)_M_vbp.size() - 1);
271 _M_last_bmap_in_block = _M_curr_bmap -
272 ((_M_vbp[_M_curr_index].second - _M_vbp[_M_curr_index].first + 1) / _Bits_Per_Block - 1);
275 //Dangerous Function! Use with extreme care. Pass to this
276 //function ONLY those values that are known to be correct,
277 //otherwise this will mess up big time.
278 void _M_set_internal_bit_map (unsigned int *__new_internal_marker) throw()
280 _M_curr_bmap = __new_internal_marker;
283 bool _M_finished () const throw()
285 return (_M_curr_bmap == 0);
288 _Bit_map_counter& operator++ () throw()
290 if (_M_curr_bmap == _M_last_bmap_in_block)
292 if (++_M_curr_index == _M_vbp.size())
298 this->_M_reset (_M_curr_index);
308 unsigned int *_M_get ()
313 pointer _M_base () { return _M_vbp[_M_curr_index].first; }
314 unsigned int _M_offset ()
316 return _Bits_Per_Block * ((reinterpret_cast<unsigned int*>(this->_M_base()) - _M_curr_bmap) - 1);
319 unsigned int _M_where () { return _M_curr_index; }
323 //Generic Version of the bsf instruction.
324 typedef unsigned int _Bit_map_type;
325 static inline unsigned int _Bit_scan_forward (register _Bit_map_type __num)
327 return static_cast<unsigned int>(__builtin_ctz(__num));
330 struct _OOM_handler {
331 static std::new_handler _S_old_handler;
332 static bool _S_handled_oom;
333 typedef void (*_FL_clear_proc)(void);
334 static _FL_clear_proc _S_oom_fcp;
336 _OOM_handler (_FL_clear_proc __fcp)
339 _S_old_handler = std::set_new_handler (_S_handle_oom_proc);
340 _S_handled_oom = false;
343 static void _S_handle_oom_proc()
346 std::set_new_handler (_S_old_handler);
347 _S_handled_oom = true;
353 std::set_new_handler (_S_old_handler);
357 std::new_handler _OOM_handler::_S_old_handler;
358 bool _OOM_handler::_S_handled_oom = false;
359 _OOM_handler::_FL_clear_proc _OOM_handler::_S_oom_fcp = 0;
362 class _BA_free_list_store {
363 struct _LT_pointer_compare {
364 template <typename _Tp>
365 bool operator() (_Tp* __pt, _Tp const& __crt) const throw()
367 return *__pt < __crt;
371 #if defined __GTHREADS
372 static _Mutex _S_bfl_mutex;
374 static std::vector<unsigned int*> _S_free_list;
375 typedef std::vector<unsigned int*>::iterator _FLIter;
377 static void _S_validate_free_list(unsigned int *__addr) throw()
379 const unsigned int __max_size = 64;
380 if (_S_free_list.size() >= __max_size)
382 //Ok, the threshold value has been reached.
383 //We determine which block to remove from the list of free
385 if (*__addr >= *_S_free_list.back())
387 //Ok, the new block is greater than or equal to the last
388 //block in the list of free blocks. We just free the new
390 operator delete((void*)__addr);
395 //Deallocate the last block in the list of free lists, and
396 //insert the new one in it's correct position.
397 operator delete((void*)_S_free_list.back());
398 _S_free_list.pop_back();
402 //Just add the block to the list of free lists
404 _FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(),
405 *__addr, _LT_pointer_compare ());
406 //We may insert the new free list before _temp;
407 _S_free_list.insert(__temp, __addr);
410 static bool _S_should_i_give(unsigned int __block_size, unsigned int __required_size) throw()
412 const unsigned int __max_wastage_percentage = 36;
413 if (__block_size >= __required_size &&
414 (((__block_size - __required_size) * 100 / __block_size) < __max_wastage_percentage))
421 typedef _BA_free_list_store _BFL_type;
423 static inline void _S_insert_free_list(unsigned int *__addr) throw()
425 #if defined __GTHREADS
426 _Lock __bfl_lock(&_S_bfl_mutex);
428 //Call _S_validate_free_list to decide what should be done with this
429 //particular free list.
430 _S_validate_free_list(--__addr);
433 static unsigned int *_S_get_free_list(unsigned int __sz) throw (std::bad_alloc)
435 #if defined __GTHREADS
436 _Lock __bfl_lock(&_S_bfl_mutex);
438 _FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(),
439 __sz, _LT_pointer_compare());
440 if (__temp == _S_free_list.end() || !_S_should_i_give (**__temp, __sz))
442 //We hold the lock because the OOM_Handler is a stateless
444 _OOM_handler __set_handler(_BFL_type::_S_clear);
445 unsigned int *__ret_val = reinterpret_cast<unsigned int*>
446 (operator new (__sz + sizeof(unsigned int)));
452 unsigned int* __ret_val = *__temp;
453 _S_free_list.erase (__temp);
458 //This function just clears the internal Free List, and gives back
459 //all the memory to the OS.
460 static void _S_clear()
462 #if defined __GTHREADS
463 _Lock __bfl_lock(&_S_bfl_mutex);
465 _FLIter __iter = _S_free_list.begin();
466 while (__iter != _S_free_list.end())
468 operator delete((void*)*__iter);
471 _S_free_list.clear();
476 #if defined __GTHREADS
477 _Mutex _BA_free_list_store::_S_bfl_mutex;
479 std::vector<unsigned int*> _BA_free_list_store::_S_free_list;
481 template <typename _Tp> class bitmap_allocator;
482 // specialize for void:
483 template <> class bitmap_allocator<void> {
485 typedef void* pointer;
486 typedef const void* const_pointer;
487 // reference-to-void members are impossible.
488 typedef void value_type;
489 template <typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; };
492 template <typename _Tp> class bitmap_allocator : private _BA_free_list_store {
494 typedef size_t size_type;
495 typedef ptrdiff_t difference_type;
496 typedef _Tp* pointer;
497 typedef const _Tp* const_pointer;
498 typedef _Tp& reference;
499 typedef const _Tp& const_reference;
500 typedef _Tp value_type;
501 template <typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; };
504 static const unsigned int _Bits_Per_Byte = 8;
505 static const unsigned int _Bits_Per_Block = sizeof(unsigned int) * _Bits_Per_Byte;
507 static inline void _S_bit_allocate(unsigned int *__pbmap, unsigned int __pos) throw()
509 unsigned int __mask = 1 << __pos;
514 static inline void _S_bit_free(unsigned int *__pbmap, unsigned int __pos) throw()
516 unsigned int __mask = 1 << __pos;
520 static inline void *_S_memory_get(size_t __sz) throw (std::bad_alloc)
522 return operator new(__sz);
525 static inline void _S_memory_put(void *__vptr) throw ()
527 operator delete(__vptr);
530 typedef typename std::pair<pointer, pointer> _Block_pair;
531 typedef typename __gnu_cxx::new_allocator<_Block_pair> _BPVec_allocator_type;
532 typedef typename std::vector<_Block_pair, _BPVec_allocator_type> _BPVector;
535 #if defined CHECK_FOR_ERRORS
536 //Complexity: O(lg(N)). Where, N is the number of block of size
537 //sizeof(value_type).
538 static void _S_check_for_free_blocks() throw()
540 typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF;
542 typedef typename _BPVector::iterator _BPiter;
543 _BPiter __bpi = std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(),
544 __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff));
545 assert(__bpi == _S_mem_blocks.end());
550 //Complexity: O(1), but internally depends upon the complexity of
551 //the function _BA_free_list_store::_S_get_free_list. The part
552 //where the bitmap headers are written is of worst case complexity:
553 //O(X),where X is the number of blocks of size sizeof(value_type)
554 //within the newly acquired block. Having a tight bound.
555 static void _S_refill_pool() throw (std::bad_alloc)
557 #if defined CHECK_FOR_ERRORS
558 _S_check_for_free_blocks();
561 const unsigned int __num_bit_maps = _S_block_size / _Bits_Per_Block;
562 const unsigned int __size_to_allocate = sizeof(unsigned int) +
563 _S_block_size * sizeof(value_type) + __num_bit_maps*sizeof(unsigned int);
565 unsigned int *__temp =
566 reinterpret_cast<unsigned int*>(_BA_free_list_store::_S_get_free_list(__size_to_allocate));
570 //The Header information goes at the Beginning of the Block.
571 _Block_pair __bp = std::make_pair(reinterpret_cast<pointer>(__temp + __num_bit_maps),
572 reinterpret_cast<pointer>(__temp + __num_bit_maps)
573 + _S_block_size - 1);
575 //Fill the Vector with this information.
576 _S_mem_blocks.push_back(__bp);
578 unsigned int __bit_mask = 0; //0 Indicates all Allocated.
579 __bit_mask = ~__bit_mask; //1 Indicates all Free.
581 for (unsigned int __i = 0; __i < __num_bit_maps; ++__i)
582 __temp[__i] = __bit_mask;
584 //On some implementations, operator new might throw bad_alloc, or
585 //malloc might fail if the size passed is too large, therefore, we
586 //limit the size passed to malloc or operator new.
590 static _BPVector _S_mem_blocks;
591 static unsigned int _S_block_size;
592 static __gnu_cxx::__aux_balloc::_Bit_map_counter<pointer, _BPVec_allocator_type> _S_last_request;
593 static typename _BPVector::size_type _S_last_dealloc_index;
594 #if defined __GTHREADS
595 static _Mutex _S_mut;
598 //Complexity: Worst case complexity is O(N), but that is hardly ever
599 //hit. if and when this particular case is encountered, the next few
600 //cases are guaranteed to have a worst case complexity of O(1)!
601 //That's why this function performs very well on the average. you
602 //can consider this function to be having a complexity refrred to
603 //commonly as: Amortized Constant time.
604 static pointer _S_allocate_single_object()
606 #if defined __GTHREADS
607 _Lock __bit_lock(&_S_mut);
610 //The algorithm is something like this: The last_requst variable
611 //points to the last accessed Bit Map. When such a condition
612 //occurs, we try to find a free block in the current bitmap, or
613 //succeeding bitmaps until the last bitmap is reached. If no free
614 //block turns up, we resort to First Fit method.
616 //WARNING: Do not re-order the condition in the while statement
617 //below, because it relies on C++'s short-circuit
618 //evaluation. The return from _S_last_request->_M_get() will NOT
619 //be dereferenceable if _S_last_request->_M_finished() returns
620 //true. This would inevitibly lead to a NULL pointer dereference
622 while (_S_last_request._M_finished() == false && (*(_S_last_request._M_get()) == 0))
624 _S_last_request.operator++();
627 if (__builtin_expect(_S_last_request._M_finished() == true, false))
629 //Fall Back to First Fit algorithm.
630 typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF;
632 typedef typename _BPVector::iterator _BPiter;
633 _BPiter __bpi = std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(),
634 __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff));
636 if (__bpi != _S_mem_blocks.end())
638 //Search was successful. Ok, now mark the first bit from
639 //the right as 0, meaning Allocated. This bit is obtained
640 //by calling _M_get() on __fff.
641 unsigned int __nz_bit = _Bit_scan_forward(*__fff._M_get());
642 _S_bit_allocate(__fff._M_get(), __nz_bit);
644 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
646 //Now, get the address of the bit we marked as allocated.
647 pointer __ret_val = __bpi->first + __fff._M_offset() + __nz_bit;
648 unsigned int *__puse_count = reinterpret_cast<unsigned int*>(__bpi->first) -
649 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(*__bpi) + 1);
655 //Search was unsuccessful. We Add more memory to the pool
656 //by calling _S_refill_pool().
659 //_M_Reset the _S_last_request structure to the first free
661 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
663 //Now, mark that bit as allocated.
666 //_S_last_request holds a pointer to a valid bit map, that points
667 //to a free block in memory.
668 unsigned int __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
669 _S_bit_allocate(_S_last_request._M_get(), __nz_bit);
671 pointer __ret_val = _S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit;
673 unsigned int *__puse_count = reinterpret_cast<unsigned int*>
674 (_S_mem_blocks[_S_last_request._M_where()].first) -
675 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
680 //Complexity: O(lg(N)), but the worst case is hit quite often! I
681 //need to do something about this. I'll be able to work on it, only
682 //when I have some solid figures from a few real apps.
683 static void _S_deallocate_single_object(pointer __p) throw()
685 #if defined __GTHREADS
686 _Lock __bit_lock(&_S_mut);
689 typedef typename _BPVector::iterator _Iterator;
690 typedef typename _BPVector::difference_type _Difference_type;
692 _Difference_type __diff;
695 assert(_S_last_dealloc_index >= 0);
697 if (__gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)(_S_mem_blocks[_S_last_dealloc_index]))
699 assert(_S_last_dealloc_index <= _S_mem_blocks.size() - 1);
701 //Initial Assumption was correct!
702 __diff = _S_last_dealloc_index;
703 __displacement = __p - _S_mem_blocks[__diff].first;
707 _Iterator _iter = (std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(),
708 __gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)));
709 assert(_iter != _S_mem_blocks.end());
711 __diff = _iter - _S_mem_blocks.begin();
712 __displacement = __p - _S_mem_blocks[__diff].first;
713 _S_last_dealloc_index = __diff;
716 //Get the position of the iterator that has been found.
717 const unsigned int __rotate = __displacement % _Bits_Per_Block;
718 unsigned int *__bit_mapC = reinterpret_cast<unsigned int*>(_S_mem_blocks[__diff].first) - 1;
719 __bit_mapC -= (__displacement / _Bits_Per_Block);
721 _S_bit_free(__bit_mapC, __rotate);
722 unsigned int *__puse_count = reinterpret_cast<unsigned int*>
723 (_S_mem_blocks[__diff].first) -
724 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[__diff]) + 1);
726 assert(*__puse_count != 0);
730 if (__builtin_expect(*__puse_count == 0, false))
734 //We may safely remove this block.
735 _Block_pair __bp = _S_mem_blocks[__diff];
736 _S_insert_free_list(__puse_count);
737 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
739 //We reset the _S_last_request variable to reflect the erased
740 //block. We do this to protect future requests after the last
741 //block has been removed from a particular memory Chunk,
742 //which in turn has been returned to the free list, and
743 //hence had been erased from the vector, so the size of the
744 //vector gets reduced by 1.
745 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
747 _S_last_request._M_reset(__diff);
748 // assert(__diff >= 0);
751 //If the Index into the vector of the region of memory that
752 //might hold the next address that will be passed to
753 //deallocated may have been invalidated due to the above
754 //erase procedure being called on the vector, hence we try
755 //to restore this invariant too.
756 if (_S_last_dealloc_index >= _S_mem_blocks.size())
758 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
759 assert(_S_last_dealloc_index >= 0);
765 bitmap_allocator() throw()
768 bitmap_allocator(const bitmap_allocator&) { }
770 template <typename _Tp1> bitmap_allocator(const bitmap_allocator<_Tp1>&) throw()
773 ~bitmap_allocator() throw()
776 //Complexity: O(1), but internally the complexity depends upon the
777 //complexity of the function(s) _S_allocate_single_object and
779 pointer allocate(size_type __n)
781 if (__builtin_expect(__n == 1, true))
782 return _S_allocate_single_object();
784 return reinterpret_cast<pointer>(_S_memory_get(__n * sizeof(value_type)));
787 //Complexity: Worst case complexity is O(N) where N is the number of
788 //blocks of size sizeof(value_type) within the free lists that the
789 //allocator holds. However, this worst case is hit only when the
790 //user supplies a bogus argument to hint. If the hint argument is
791 //sensible, then the complexity drops to O(lg(N)), and in extreme
792 //cases, even drops to as low as O(1). So, if the user supplied
793 //argument is good, then this function performs very well.
794 pointer allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
796 return allocate(__n);
799 void deallocate(pointer __p, size_type __n) throw()
801 if (__builtin_expect(__n == 1, true))
802 _S_deallocate_single_object(__p);
807 pointer address(reference r) const { return &r; }
808 const_pointer address(const_reference r) const { return &r; }
810 size_type max_size(void) const throw() { return (size_type()-1)/sizeof(value_type); }
812 void construct (pointer p, const_reference __data)
814 ::new(p) value_type(__data);
817 void destroy (pointer p)
824 template <typename _Tp>
825 typename bitmap_allocator<_Tp>::_BPVector bitmap_allocator<_Tp>::_S_mem_blocks;
827 template <typename _Tp>
828 unsigned int bitmap_allocator<_Tp>::_S_block_size = bitmap_allocator<_Tp>::_Bits_Per_Block;
830 template <typename _Tp>
831 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
832 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
834 template <typename _Tp>
835 __gnu_cxx::__aux_balloc::_Bit_map_counter
836 <typename bitmap_allocator<_Tp>::pointer, typename bitmap_allocator<_Tp>::_BPVec_allocator_type>
837 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
839 #if defined __GTHREADS
840 template <typename _Tp>
842 bitmap_allocator<_Tp>::_S_mut;
845 template <typename _Tp1, typename _Tp2>
846 bool operator== (const bitmap_allocator<_Tp1>&, const bitmap_allocator<_Tp2>&) throw()
851 template <typename _Tp1, typename _Tp2>
852 bool operator!= (const bitmap_allocator<_Tp1>&, const bitmap_allocator<_Tp2>&) throw()
859 #endif //_BITMAP_ALLOCATOR_H