1 // Bitmap 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.
30 /** @file ext/bitmap_allocator.h
31 * This file is a GNU extension to the Standard C++ Library.
32 * You should only include this header if you are using GCC 3 or later.
35 #ifndef _BITMAP_ALLOCATOR_H
36 #define _BITMAP_ALLOCATOR_H 1
38 // For std::size_t, and ptrdiff_t.
44 // For greater_equal, and less_equal.
50 // For __gthread_mutex_t, __gthread_mutex_lock and __gthread_mutex_unlock.
51 #include <bits/gthr.h>
53 // Define this to enable error checking withing the allocator
54 // itself(to debug the allocator itself).
55 //#define _BALLOC_SANITY_CHECK
57 #if defined _BALLOC_SANITY_CHECK
59 #define _BALLOC_ASSERT(_EXPR) assert(_EXPR)
61 #define _BALLOC_ASSERT(_EXPR)
67 #if defined __GTHREADS
70 // If true, then the application being compiled will be using
71 // threads, so use mutexes as a synchronization primitive, else do
72 // no use any synchronization primitives.
73 bool const __threads_enabled
= __gthread_active_p();
77 #if defined __GTHREADS
78 // _Mutex is an OO-Wrapper for __gthread_mutex_t. It does not allow
79 // you to copy or assign an already initialized mutex. This is used
80 // merely as a convenience for the locking classes.
83 __gthread_mutex_t _M_mut
;
85 // Prevent Copying and assignment.
86 _Mutex(_Mutex
const&);
87 _Mutex
& operator=(_Mutex
const&);
92 if (__threads_enabled
)
94 #if !defined __GTHREAD_MUTEX_INIT
95 __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut
);
97 __gthread_mutex_t __mtemp
= __GTHREAD_MUTEX_INIT
;
105 // Gthreads does not define a Mutex Destruction Function.
109 _M_get() { return &_M_mut
; }
112 // _Lock is a simple manual lokcing class which allows you to
113 // manually lock and unlock a mutex associated with the lock. There
114 // is not automatic locking or unlocking happening without the
115 // programmer's explicit instructions. This class unlocks the mutex
116 // ONLY if it has not been locked. However, this check does not
117 // apply for lokcing, and wayward use may cause dead-locks.
123 // Prevent Copying and assignment.
125 _Lock
& operator=(_Lock
const&);
128 _Lock(_Mutex
* __mptr
)
129 : _M_pmt(__mptr
), _M_locked(false)
135 if (__threads_enabled
)
138 __gthread_mutex_lock(_M_pmt
->_M_get());
145 if (__threads_enabled
)
147 if (__builtin_expect(_M_locked
, true))
149 __gthread_mutex_unlock(_M_pmt
->_M_get());
158 // _Auto_Lock locks the associated mutex on construction, and
159 // unlocks on it's destruction. There are no checks performed, and
160 // this calss follows the RAII principle.
164 // Prevent Copying and assignment.
165 _Auto_Lock(_Auto_Lock
const&);
166 _Auto_Lock
& operator=(_Auto_Lock
const&);
171 if (__threads_enabled
)
172 __gthread_mutex_lock(_M_pmt
->_M_get());
178 if (__threads_enabled
)
179 __gthread_mutex_unlock(_M_pmt
->_M_get());
183 _Auto_Lock(_Mutex
* __mptr
) : _M_pmt(__mptr
)
186 ~_Auto_Lock() { this->_M_unlock(); }
192 // __mini_vector<> is to be used only for built-in types or
193 // PODs. It is a stripped down version of the full-fledged
194 // std::vector<>. Noteable differences are:
196 // 1. Not all accessor functions are present.
197 // 2. Used ONLY for PODs.
198 // 3. No Allocator template argument. Uses ::operator new() to get
199 // memory, and ::operator delete() to free it.
200 template<typename _Tp
>
203 __mini_vector(const __mini_vector
&);
204 __mini_vector
& operator=(const __mini_vector
&);
207 typedef _Tp value_type
;
208 typedef _Tp
* pointer
;
209 typedef _Tp
& reference
;
210 typedef const _Tp
& const_reference
;
211 typedef std::size_t size_type
;
212 typedef std::ptrdiff_t difference_type
;
213 typedef pointer iterator
;
218 pointer _M_end_of_storage
;
221 _M_space_left() const throw()
222 { return _M_end_of_storage
- _M_finish
; }
225 allocate(size_type __n
)
226 { return static_cast<pointer
>(::operator new(__n
* sizeof(_Tp
))); }
229 deallocate(pointer __p
, size_type
)
230 { ::operator delete(__p
); }
233 // Members used: size(), push_back(), pop_back(),
234 // insert(iterator, const_reference), erase(iterator),
235 // begin(), end(), back(), operator[].
237 __mini_vector() : _M_start(0), _M_finish(0),
245 this->deallocate(this->_M_start
, this->_M_end_of_storage
252 { return _M_finish
- _M_start
; }
255 begin() const throw()
256 { return this->_M_start
; }
260 { return this->_M_finish
; }
264 { return *(this->end() - 1); }
267 operator[](const size_type __pos
) const throw()
268 { return this->_M_start
[__pos
]; }
271 insert(iterator __pos
, const_reference __x
);
274 push_back(const_reference __x
)
276 if (this->_M_space_left())
282 this->insert(this->end(), __x
);
287 { --this->_M_finish
; }
290 erase(iterator __pos
) throw();
294 { this->_M_finish
= this->_M_start
; }
297 // Out of line function definitions.
298 template<typename _Tp
>
299 void __mini_vector
<_Tp
>::
300 insert(iterator __pos
, const_reference __x
)
302 if (this->_M_space_left())
304 size_type __to_move
= this->_M_finish
- __pos
;
305 iterator __dest
= this->end();
306 iterator __src
= this->end() - 1;
312 --__dest
; --__src
; --__to_move
;
318 size_type __new_size
= this->size() ? this->size() * 2 : 1;
319 iterator __new_start
= this->allocate(__new_size
);
320 iterator __first
= this->begin();
321 iterator __start
= __new_start
;
322 while (__first
!= __pos
)
325 ++__start
; ++__first
;
329 while (__first
!= this->end())
332 ++__start
; ++__first
;
335 this->deallocate(this->_M_start
, this->size());
337 this->_M_start
= __new_start
;
338 this->_M_finish
= __start
;
339 this->_M_end_of_storage
= this->_M_start
+ __new_size
;
343 template<typename _Tp
>
344 void __mini_vector
<_Tp
>::
345 erase(iterator __pos
) throw()
347 while (__pos
+ 1 != this->end())
356 template<typename _Tp
>
357 struct __mv_iter_traits
359 typedef typename
_Tp::value_type value_type
;
360 typedef typename
_Tp::difference_type difference_type
;
363 template<typename _Tp
>
364 struct __mv_iter_traits
<_Tp
*>
366 typedef _Tp value_type
;
367 typedef std::ptrdiff_t difference_type
;
373 bits_per_block
= sizeof(unsigned int) * bits_per_byte
376 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
378 __lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
379 const _Tp
& __val
, _Compare __comp
)
381 typedef typename __mv_iter_traits
<_ForwardIterator
>::value_type
383 typedef typename __mv_iter_traits
<_ForwardIterator
>::difference_type
386 _DistanceType __len
= __last
- __first
;
387 _DistanceType __half
;
388 _ForwardIterator __middle
;
395 if (__comp(*__middle
, __val
))
399 __len
= __len
- __half
- 1;
407 template<typename _InputIterator
, typename _Predicate
>
408 inline _InputIterator
409 __find_if(_InputIterator __first
, _InputIterator __last
, _Predicate __p
)
411 while (__first
!= __last
&& !__p(*__first
))
416 template<typename _AddrPair
>
418 __num_blocks(_AddrPair __ap
)
419 { return (__ap
.second
- __ap
.first
) + 1; }
421 template<typename _AddrPair
>
423 __num_bitmaps(_AddrPair __ap
)
424 { return __num_blocks(__ap
) / bits_per_block
; }
426 // _Tp should be a pointer type.
427 template<typename _Tp
>
428 class _Inclusive_between
429 : public std::unary_function
<typename
std::pair
<_Tp
, _Tp
>, bool>
432 pointer _M_ptr_value
;
433 typedef typename
std::pair
<_Tp
, _Tp
> _Block_pair
;
436 _Inclusive_between(pointer __ptr
) : _M_ptr_value(__ptr
)
440 operator()(_Block_pair __bp
) const throw()
442 if (std::less_equal
<pointer
>()(_M_ptr_value
, __bp
.second
)
443 && std::greater_equal
<pointer
>()(_M_ptr_value
, __bp
.first
))
450 // Used to pass a Functor to functions by reference.
451 template<typename _Functor
>
453 : public std::unary_function
<typename
_Functor::argument_type
,
454 typename
_Functor::result_type
>
459 typedef typename
_Functor::argument_type argument_type
;
460 typedef typename
_Functor::result_type result_type
;
462 _Functor_Ref(_Functor
& __fref
) : _M_fref(__fref
)
466 operator()(argument_type __arg
)
467 { return _M_fref(__arg
); }
470 // _Tp should be a pointer type, and _Alloc is the Allocator for
472 template<typename _Tp
>
474 : public std::unary_function
<typename
std::pair
<_Tp
, _Tp
>, bool>
476 typedef typename
std::pair
<_Tp
, _Tp
> _Block_pair
;
477 typedef typename
balloc::__mini_vector
<_Block_pair
> _BPVector
;
478 typedef typename
_BPVector::difference_type _Counter_type
;
480 unsigned int* _M_pbitmap
;
481 unsigned int _M_data_offset
;
484 _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
488 operator()(_Block_pair __bp
) throw()
490 // Set the _rover to the last unsigned integer, which is the
491 // bitmap to the first free block. Thus, the bitmaps are in exact
492 // reverse order of the actual memory layout. So, we count down
493 // the bimaps, which is the same as moving up the memory.
495 // If the used count stored at the start of the Bit Map headers
496 // is equal to the number of Objects that the current Block can
497 // store, then there is definitely no space for another single
498 // object, so just return false.
499 _Counter_type __diff
=
500 __gnu_cxx::balloc::__num_bitmaps(__bp
);
502 if (*reinterpret_cast<unsigned int*>
503 (reinterpret_cast<char*>(__bp
.first
) - (sizeof(unsigned int) *
505 == __gnu_cxx::balloc::__num_blocks(__bp
))
508 unsigned int* __rover
= reinterpret_cast<unsigned int*>(__bp
.first
) - 1;
510 for (_Counter_type __i
= 0; __i
< __diff
; ++__i
)
512 _M_data_offset
= __i
;
515 _M_pbitmap
= __rover
;
525 _M_get() const throw()
526 { return _M_pbitmap
; }
529 _M_offset() const throw()
530 { return _M_data_offset
* bits_per_block
; }
535 // _Tp should be a pointer type.
536 template<typename _Tp
>
537 class _Bitmap_counter
539 typedef typename
balloc::__mini_vector
<typename
std::pair
<_Tp
, _Tp
> >
541 typedef typename
_BPVector::size_type _Index_type
;
545 unsigned int* _M_curr_bmap
;
546 unsigned int* _M_last_bmap_in_block
;
547 _Index_type _M_curr_index
;
550 // Use the 2nd parameter with care. Make sure that such an
551 // entry exists in the vector before passing that particular
552 // index to this ctor.
553 _Bitmap_counter(_BPVector
& Rvbp
, int __index
= -1) : _M_vbp(Rvbp
)
554 { this->_M_reset(__index
); }
557 _M_reset(int __index
= -1) throw()
562 _M_curr_index
= static_cast<_Index_type
>(-1);
566 _M_curr_index
= __index
;
567 _M_curr_bmap
= reinterpret_cast<unsigned int*>
568 (_M_vbp
[_M_curr_index
].first
) - 1;
570 _BALLOC_ASSERT(__index
<= (int)_M_vbp
.size() - 1);
572 _M_last_bmap_in_block
= _M_curr_bmap
573 - ((_M_vbp
[_M_curr_index
].second
574 - _M_vbp
[_M_curr_index
].first
+ 1)
575 / bits_per_block
- 1);
578 // Dangerous Function! Use with extreme care. Pass to this
579 // function ONLY those values that are known to be correct,
580 // otherwise this will mess up big time.
582 _M_set_internal_bitmap(unsigned int* __new_internal_marker
) throw()
583 { _M_curr_bmap
= __new_internal_marker
; }
586 _M_finished() const throw()
587 { return(_M_curr_bmap
== 0); }
592 if (_M_curr_bmap
== _M_last_bmap_in_block
)
594 if (++_M_curr_index
== _M_vbp
.size())
597 this->_M_reset(_M_curr_index
);
605 _M_get() const throw()
606 { return _M_curr_bmap
; }
609 _M_base() const throw()
610 { return _M_vbp
[_M_curr_index
].first
; }
613 _M_offset() const throw()
615 return bits_per_block
616 * ((reinterpret_cast<unsigned int*>(this->_M_base())
617 - _M_curr_bmap
) - 1);
621 _M_where() const throw()
622 { return _M_curr_index
; }
626 __bit_allocate(unsigned int* __pbmap
, unsigned int __pos
) throw()
628 unsigned int __mask
= 1 << __pos
;
634 __bit_free(unsigned int* __pbmap
, unsigned int __pos
) throw()
636 unsigned int __mask
= 1 << __pos
;
639 } // namespace balloc
641 // Generic Version of the bsf instruction.
643 _Bit_scan_forward(register unsigned int __num
)
644 { return static_cast<unsigned int>(__builtin_ctz(__num
)); }
648 typedef unsigned int* value_type
;
649 typedef balloc::__mini_vector
<value_type
> vector_type
;
650 typedef vector_type::iterator iterator
;
652 struct _LT_pointer_compare
655 operator()(const unsigned int* __pui
, const unsigned int __cui
) const throw()
656 { return *__pui
< __cui
; }
659 #if defined __GTHREADS
660 static _Mutex _S_bfl_mutex
;
662 static vector_type _S_free_list
;
665 _M_validate(unsigned int* __addr
) throw()
667 const unsigned int __max_size
= 64;
668 if (_S_free_list
.size() >= __max_size
)
670 // Ok, the threshold value has been reached. We determine
671 // which block to remove from the list of free blocks.
672 if (*__addr
>= *_S_free_list
.back())
674 // Ok, the new block is greater than or equal to the
675 // last block in the list of free blocks. We just free
677 operator delete(static_cast<void*>(__addr
));
682 // Deallocate the last block in the list of free lists,
683 // and insert the new one in it's correct position.
684 operator delete(static_cast<void*>(_S_free_list
.back()));
685 _S_free_list
.pop_back();
689 // Just add the block to the list of free lists unconditionally.
690 iterator __temp
= __gnu_cxx::balloc::__lower_bound
691 (_S_free_list
.begin(), _S_free_list
.end(),
692 *__addr
, _LT_pointer_compare());
694 // We may insert the new free list before _temp;
695 _S_free_list
.insert(__temp
, __addr
);
699 _M_should_i_give(unsigned int __block_size
,
700 unsigned int __required_size
) throw()
702 const unsigned int __max_wastage_percentage
= 36;
703 if (__block_size
>= __required_size
&&
704 (((__block_size
- __required_size
) * 100 / __block_size
)
705 < __max_wastage_percentage
))
713 _M_insert(unsigned int* __addr
) throw()
715 #if defined __GTHREADS
716 _Auto_Lock
__bfl_lock(&_S_bfl_mutex
);
718 // Call _M_validate to decide what should be done with
719 // this particular free list.
720 this->_M_validate(reinterpret_cast<unsigned int*>
721 (reinterpret_cast<char*>(__addr
)
722 - sizeof(unsigned int)));
726 _M_get(unsigned int __sz
) throw(std::bad_alloc
);
728 // This function just clears the internal Free List, and gives back
729 // all the memory to the OS.
735 // Forward declare the class.
736 template<typename _Tp
>
737 class bitmap_allocator
;
739 // Specialize for void:
741 class bitmap_allocator
<void>
744 typedef void* pointer
;
745 typedef const void* const_pointer
;
747 // Reference-to-void members are impossible.
748 typedef void value_type
;
749 template<typename _Tp1
>
752 typedef bitmap_allocator
<_Tp1
> other
;
756 template<typename _Tp
>
757 class bitmap_allocator
: private free_list
760 typedef std::size_t size_type
;
761 typedef std::ptrdiff_t difference_type
;
762 typedef _Tp
* pointer
;
763 typedef const _Tp
* const_pointer
;
764 typedef _Tp
& reference
;
765 typedef const _Tp
& const_reference
;
766 typedef _Tp value_type
;
767 template<typename _Tp1
>
770 typedef bitmap_allocator
<_Tp1
> other
;
774 template<unsigned int _BSize
, unsigned int _AlignSize
>
779 modulus
= _BSize
% _AlignSize
,
780 value
= _BSize
+ (modulus
? _AlignSize
- (modulus
) : 0)
786 char __M_unused
[aligned_size
<sizeof(value_type
), 8>::value
];
790 typedef typename
std::pair
<_Alloc_block
*, _Alloc_block
*> _Block_pair
;
793 balloc::__mini_vector
<_Block_pair
> _BPVector
;
795 #if defined _BALLOC_SANITY_CHECK
796 // Complexity: O(lg(N)). Where, N is the number of block of size
797 // sizeof(value_type).
799 _S_check_for_free_blocks() throw()
802 __gnu_cxx::balloc::_Ffit_finder
<_Alloc_block
*> _FFF
;
804 typedef typename
_BPVector::iterator _BPiter
;
806 __gnu_cxx::balloc::__find_if
807 (_S_mem_blocks
.begin(), _S_mem_blocks
.end(),
808 __gnu_cxx::balloc::_Functor_Ref
<_FFF
>(__fff
));
810 _BALLOC_ASSERT(__bpi
== _S_mem_blocks
.end());
814 // Complexity: O(1), but internally depends upon the complexity
815 // of the function free_list::_M_get. The
816 // part where the bitmap headers are written is of worst case
817 // complexity: O(X),where X is the number of blocks of size
818 // sizeof(value_type) within the newly acquired block. Having a
821 _S_refill_pool() throw(std::bad_alloc
)
823 #if defined _BALLOC_SANITY_CHECK
824 _S_check_for_free_blocks();
827 const unsigned int __num_bitmaps
= _S_block_size
/ balloc::bits_per_block
;
828 const unsigned int __size_to_allocate
= sizeof(unsigned int)
829 + _S_block_size
* sizeof(_Alloc_block
)
830 + __num_bitmaps
* sizeof(unsigned int);
832 unsigned int* __temp
=
833 reinterpret_cast<unsigned int*>(this->_M_get(__size_to_allocate
));
836 __temp
= reinterpret_cast<unsigned int*>
837 (reinterpret_cast<char*>(__temp
) + sizeof(unsigned int));
839 // The Header information goes at the Beginning of the Block.
841 std::make_pair(reinterpret_cast<_Alloc_block
*>
842 (__temp
+ __num_bitmaps
),
843 reinterpret_cast<_Alloc_block
*>
844 (__temp
+ __num_bitmaps
)
845 + _S_block_size
- 1);
847 // Fill the Vector with this information.
848 _S_mem_blocks
.push_back(__bp
);
850 unsigned int __bit_mask
= 0; // 0 Indicates all Allocated.
851 __bit_mask
= ~__bit_mask
; // 1 Indicates all Free.
853 for (unsigned int __i
= 0; __i
< __num_bitmaps
; ++__i
)
854 __temp
[__i
] = __bit_mask
;
860 static _BPVector _S_mem_blocks
;
861 static unsigned int _S_block_size
;
862 static __gnu_cxx::balloc::
863 _Bitmap_counter
<_Alloc_block
*> _S_last_request
;
864 static typename
_BPVector::size_type _S_last_dealloc_index
;
865 #if defined __GTHREADS
866 static _Mutex _S_mut
;
871 // Complexity: Worst case complexity is O(N), but that is hardly
872 // ever hit. if and when this particular case is encountered,
873 // the next few cases are guaranteed to have a worst case
874 // complexity of O(1)! That's why this function performs very
875 // well on the average. you can consider this function to be
876 // having a complexity referred to commonly as: Amortized
879 _M_allocate_single_object() throw(std::bad_alloc
)
881 #if defined __GTHREADS
882 _Auto_Lock
__bit_lock(&_S_mut
);
885 // The algorithm is something like this: The last_request
886 // variable points to the last accessed Bit Map. When such a
887 // condition occurs, we try to find a free block in the
888 // current bitmap, or succeeding bitmaps until the last bitmap
889 // is reached. If no free block turns up, we resort to First
892 // WARNING: Do not re-order the condition in the while
893 // statement below, because it relies on C++'s short-circuit
894 // evaluation. The return from _S_last_request->_M_get() will
895 // NOT be dereference able if _S_last_request->_M_finished()
896 // returns true. This would inevitably lead to a NULL pointer
897 // dereference if tinkered with.
898 while (_S_last_request
._M_finished() == false
899 && (*(_S_last_request
._M_get()) == 0))
901 _S_last_request
.operator++();
904 if (__builtin_expect(_S_last_request
._M_finished() == true, false))
906 // Fall Back to First Fit algorithm.
908 __gnu_cxx::balloc::_Ffit_finder
<_Alloc_block
*> _FFF
;
910 typedef typename
_BPVector::iterator _BPiter
;
912 __gnu_cxx::balloc::__find_if
913 (_S_mem_blocks
.begin(), _S_mem_blocks
.end(),
914 __gnu_cxx::balloc::_Functor_Ref
<_FFF
>(__fff
));
916 if (__bpi
!= _S_mem_blocks
.end())
918 // Search was successful. Ok, now mark the first bit from
919 // the right as 0, meaning Allocated. This bit is obtained
920 // by calling _M_get() on __fff.
921 unsigned int __nz_bit
= _Bit_scan_forward(*__fff
._M_get());
922 balloc::__bit_allocate(__fff
._M_get(), __nz_bit
);
924 _S_last_request
._M_reset(__bpi
- _S_mem_blocks
.begin());
926 // Now, get the address of the bit we marked as allocated.
927 pointer __ret
= reinterpret_cast<pointer
>
928 (__bpi
->first
+ __fff
._M_offset() + __nz_bit
);
929 unsigned int* __puse_count
= reinterpret_cast<unsigned int*>
930 (reinterpret_cast<char*>
931 (__bpi
->first
) - (sizeof(unsigned int) *
932 (__gnu_cxx::balloc::__num_bitmaps(*__bpi
)+1)));
939 // Search was unsuccessful. We Add more memory to the
940 // pool by calling _S_refill_pool().
943 // _M_Reset the _S_last_request structure to the first
944 // free block's bit map.
945 _S_last_request
._M_reset(_S_mem_blocks
.size() - 1);
947 // Now, mark that bit as allocated.
951 // _S_last_request holds a pointer to a valid bit map, that
952 // points to a free block in memory.
953 unsigned int __nz_bit
= _Bit_scan_forward(*_S_last_request
._M_get());
954 balloc::__bit_allocate(_S_last_request
._M_get(), __nz_bit
);
956 pointer __ret
= reinterpret_cast<pointer
>
957 (_S_last_request
._M_base() + _S_last_request
._M_offset() + __nz_bit
);
959 unsigned int* __puse_count
= reinterpret_cast<unsigned int*>
960 (reinterpret_cast<char*>
961 (_S_mem_blocks
[_S_last_request
._M_where()].first
)
962 - (sizeof(unsigned int) *
964 __num_bitmaps(_S_mem_blocks
[_S_last_request
._M_where()])+1)));
970 // Complexity: O(lg(N)), but the worst case is hit quite often!
971 // I need to do something about this. I'll be able to work on
972 // it, only when I have some solid figures from a few real apps.
974 _M_deallocate_single_object(pointer __p
) throw()
976 #if defined __GTHREADS
977 _Auto_Lock
__bit_lock(&_S_mut
);
979 _Alloc_block
* __real_p
= reinterpret_cast<_Alloc_block
*>(__p
);
981 typedef typename
_BPVector::iterator _Iterator
;
982 typedef typename
_BPVector::difference_type _Difference_type
;
984 _Difference_type __diff
;
987 _BALLOC_ASSERT(_S_last_dealloc_index
>= 0);
990 if (__gnu_cxx::balloc::_Inclusive_between
<_Alloc_block
*>
992 (_S_mem_blocks
[_S_last_dealloc_index
]))
994 _BALLOC_ASSERT(_S_last_dealloc_index
<= _S_mem_blocks
.size() - 1);
996 // Initial Assumption was correct!
997 __diff
= _S_last_dealloc_index
;
998 __displacement
= __real_p
- _S_mem_blocks
[__diff
].first
;
1003 __gnu_cxx::balloc::__find_if(_S_mem_blocks
.begin(),
1004 _S_mem_blocks
.end(),
1006 _Inclusive_between
<_Alloc_block
*>(__real_p
));
1007 _BALLOC_ASSERT(_iter
!= _S_mem_blocks
.end());
1009 __diff
= _iter
- _S_mem_blocks
.begin();
1010 __displacement
= __real_p
- _S_mem_blocks
[__diff
].first
;
1011 _S_last_dealloc_index
= __diff
;
1014 // Get the position of the iterator that has been found.
1015 const unsigned int __rotate
= __displacement
% balloc::bits_per_block
;
1016 unsigned int* __bitmapC
=
1017 reinterpret_cast<unsigned int*>(_S_mem_blocks
[__diff
].first
) - 1;
1018 __bitmapC
-= (__displacement
/ balloc::bits_per_block
);
1020 balloc::__bit_free(__bitmapC
, __rotate
);
1021 unsigned int* __puse_count
= reinterpret_cast<unsigned int*>
1022 (reinterpret_cast<char*>
1023 (_S_mem_blocks
[__diff
].first
)
1024 - (sizeof(unsigned int) *
1025 (__gnu_cxx::balloc::__num_bitmaps(_S_mem_blocks
[__diff
])+1)));
1027 _BALLOC_ASSERT(*__puse_count
!= 0);
1031 if (__builtin_expect(*__puse_count
== 0, false))
1035 // We can safely remove this block.
1036 // _Block_pair __bp = _S_mem_blocks[__diff];
1037 this->_M_insert(__puse_count
);
1038 _S_mem_blocks
.erase(_S_mem_blocks
.begin() + __diff
);
1040 // Reset the _S_last_request variable to reflect the
1041 // erased block. We do this to protect future requests
1042 // after the last block has been removed from a particular
1043 // memory Chunk, which in turn has been returned to the
1044 // free list, and hence had been erased from the vector,
1045 // so the size of the vector gets reduced by 1.
1046 if ((_Difference_type
)_S_last_request
._M_where() >= __diff
--)
1047 _S_last_request
._M_reset(__diff
);
1049 // If the Index into the vector of the region of memory
1050 // that might hold the next address that will be passed to
1051 // deallocated may have been invalidated due to the above
1052 // erase procedure being called on the vector, hence we
1053 // try to restore this invariant too.
1054 if (_S_last_dealloc_index
>= _S_mem_blocks
.size())
1056 _S_last_dealloc_index
=(__diff
!= -1 ? __diff
: 0);
1057 _BALLOC_ASSERT(_S_last_dealloc_index
>= 0);
1063 bitmap_allocator() throw()
1066 bitmap_allocator(const bitmap_allocator
&)
1069 template<typename _Tp1
>
1070 bitmap_allocator(const bitmap_allocator
<_Tp1
>&) throw()
1073 ~bitmap_allocator() throw()
1076 // Complexity: O(1), but internally the complexity depends upon the
1077 // complexity of the function(s) _S_allocate_single_object and
1080 allocate(size_type __n
)
1082 if (__builtin_expect(__n
== 1, true))
1083 return this->_M_allocate_single_object();
1086 const size_type __b
= __n
* sizeof(value_type
);
1087 return reinterpret_cast<pointer
>(::operator new(__b
));
1092 allocate(size_type __n
, typename bitmap_allocator
<void>::const_pointer
)
1093 { return allocate(__n
); }
1096 deallocate(pointer __p
, size_type __n
) throw()
1098 if (__builtin_expect(__n
== 1, true))
1099 this->_M_deallocate_single_object(__p
);
1101 ::operator delete(__p
);
1105 address(reference __r
) const
1109 address(const_reference __r
) const
1113 max_size() const throw()
1114 { return (size_type()-1)/sizeof(value_type
); }
1117 construct(pointer __p
, const_reference __data
)
1118 { ::new(__p
) value_type(__data
); }
1121 destroy(pointer __p
)
1122 { __p
->~value_type(); }
1125 template<typename _Tp1
, typename _Tp2
>
1127 operator==(const bitmap_allocator
<_Tp1
>&,
1128 const bitmap_allocator
<_Tp2
>&) throw()
1131 template<typename _Tp1
, typename _Tp2
>
1133 operator!=(const bitmap_allocator
<_Tp1
>&,
1134 const bitmap_allocator
<_Tp2
>&) throw()
1137 // Static member definitions.
1138 template<typename _Tp
>
1139 typename bitmap_allocator
<_Tp
>::_BPVector
1140 bitmap_allocator
<_Tp
>::_S_mem_blocks
;
1142 template<typename _Tp
>
1143 unsigned int bitmap_allocator
<_Tp
>::_S_block_size
= balloc::bits_per_block
;
1145 template<typename _Tp
>
1146 typename
__gnu_cxx::bitmap_allocator
<_Tp
>::_BPVector::size_type
1147 bitmap_allocator
<_Tp
>::_S_last_dealloc_index
= 0;
1149 template<typename _Tp
>
1150 __gnu_cxx::balloc::_Bitmap_counter
1151 <typename bitmap_allocator
<_Tp
>::_Alloc_block
*>
1152 bitmap_allocator
<_Tp
>::_S_last_request(_S_mem_blocks
);
1154 #if defined __GTHREADS
1155 template<typename _Tp
>
1157 bitmap_allocator
<_Tp
>::_S_mut
;
1165 // LocalWords: namespace GTHREADS bool const gthread endif Mutex mutex