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