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.
34 #ifndef _BITMAP_ALLOCATOR_H
35 #define _BITMAP_ALLOCATOR_H 1
37 // For std::size_t, and ptrdiff_t.
40 // For __throw_bad_alloc().
41 #include <bits/functexcept.h>
46 // For greater_equal, and less_equal.
52 // For __gthread_mutex_t, __gthread_mutex_lock and __gthread_mutex_unlock.
53 #include <bits/gthr.h>
55 // Define this to enable error checking withing the allocator
56 // itself(to debug the allocator itself).
57 //#define _BALLOC_SANITY_CHECK
59 // The constant in the expression below is the alignment required in
61 #define _BALLOC_ALIGN_BYTES 8
63 #if defined _BALLOC_SANITY_CHECK
65 #define _BALLOC_ASSERT(_EXPR) assert(_EXPR)
67 #define _BALLOC_ASSERT(_EXPR)
73 #if defined __GTHREADS
76 // If true, then the application being compiled will be using
77 // threads, so use mutexes as a synchronization primitive, else do
78 // no use any synchronization primitives.
79 bool const __threads_enabled
= __gthread_active_p();
83 #if defined __GTHREADS
84 // _Mutex is an OO-Wrapper for __gthread_mutex_t. It does not allow
85 // you to copy or assign an already initialized mutex. This is used
86 // merely as a convenience for the locking classes.
89 __gthread_mutex_t _M_mut
;
91 // Prevent Copying and assignment.
92 _Mutex(_Mutex
const&);
93 _Mutex
& operator=(_Mutex
const&);
98 if (__threads_enabled
)
100 #if !defined __GTHREAD_MUTEX_INIT
101 __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut
);
103 __gthread_mutex_t __mtemp
= __GTHREAD_MUTEX_INIT
;
111 // Gthreads does not define a Mutex Destruction Function.
115 _M_get() { return &_M_mut
; }
118 // _Lock is a simple manual lokcing class which allows you to
119 // manually lock and unlock a mutex associated with the lock. There
120 // is not automatic locking or unlocking happening without the
121 // programmer's explicit instructions. This class unlocks the mutex
122 // ONLY if it has not been locked. However, this check does not
123 // apply for lokcing, and wayward use may cause dead-locks.
129 // Prevent Copying and assignment.
131 _Lock
& operator=(_Lock
const&);
134 _Lock(_Mutex
* __mptr
)
135 : _M_pmt(__mptr
), _M_locked(false)
141 if (__threads_enabled
)
144 __gthread_mutex_lock(_M_pmt
->_M_get());
151 if (__threads_enabled
)
153 if (__builtin_expect(_M_locked
, true))
155 __gthread_mutex_unlock(_M_pmt
->_M_get());
164 // _Auto_Lock locks the associated mutex on construction, and
165 // unlocks on it's destruction. There are no checks performed, and
166 // this calss follows the RAII principle.
170 // Prevent Copying and assignment.
171 _Auto_Lock(_Auto_Lock
const&);
172 _Auto_Lock
& operator=(_Auto_Lock
const&);
177 if (__threads_enabled
)
178 __gthread_mutex_lock(_M_pmt
->_M_get());
184 if (__threads_enabled
)
185 __gthread_mutex_unlock(_M_pmt
->_M_get());
189 _Auto_Lock(_Mutex
* __mptr
) : _M_pmt(__mptr
)
192 ~_Auto_Lock() { this->_M_unlock(); }
198 // __mini_vector<> is to be used only for built-in types or
199 // PODs. It is a stripped down version of the full-fledged
200 // std::vector<>. Noteable differences are:
202 // 1. Not all accessor functions are present.
203 // 2. Used ONLY for PODs.
204 // 3. No Allocator template argument. Uses ::operator new() to get
205 // memory, and ::operator delete() to free it.
206 template<typename _Tp
>
209 __mini_vector(const __mini_vector
&);
210 __mini_vector
& operator=(const __mini_vector
&);
213 typedef _Tp value_type
;
214 typedef _Tp
* pointer
;
215 typedef _Tp
& reference
;
216 typedef const _Tp
& const_reference
;
217 typedef std::size_t size_type
;
218 typedef std::ptrdiff_t difference_type
;
219 typedef pointer iterator
;
224 pointer _M_end_of_storage
;
227 _M_space_left() const throw()
228 { return _M_end_of_storage
- _M_finish
; }
231 allocate(size_type __n
)
232 { return static_cast<pointer
>(::operator new(__n
* sizeof(_Tp
))); }
235 deallocate(pointer __p
, size_type
)
236 { ::operator delete(__p
); }
239 // Members used: size(), push_back(), pop_back(),
240 // insert(iterator, const_reference), erase(iterator),
241 // begin(), end(), back(), operator[].
243 __mini_vector() : _M_start(0), _M_finish(0),
252 this->deallocate(this->_M_start
, this->_M_end_of_storage
260 { return _M_finish
- _M_start
; }
263 begin() const throw()
264 { return this->_M_start
; }
268 { return this->_M_finish
; }
272 { return *(this->end() - 1); }
275 operator[](const size_type __pos
) const throw()
276 { return this->_M_start
[__pos
]; }
279 insert(iterator __pos
, const_reference __x
);
282 push_back(const_reference __x
)
284 if (this->_M_space_left())
290 this->insert(this->end(), __x
);
295 { --this->_M_finish
; }
298 erase(iterator __pos
) throw();
302 { this->_M_finish
= this->_M_start
; }
305 // Out of line function definitions.
306 template<typename _Tp
>
307 void __mini_vector
<_Tp
>::
308 insert(iterator __pos
, const_reference __x
)
310 if (this->_M_space_left())
312 size_type __to_move
= this->_M_finish
- __pos
;
313 iterator __dest
= this->end();
314 iterator __src
= this->end() - 1;
320 --__dest
; --__src
; --__to_move
;
326 size_type __new_size
= this->size() ? this->size() * 2 : 1;
327 iterator __new_start
= this->allocate(__new_size
);
328 iterator __first
= this->begin();
329 iterator __start
= __new_start
;
330 while (__first
!= __pos
)
333 ++__start
; ++__first
;
337 while (__first
!= this->end())
340 ++__start
; ++__first
;
343 this->deallocate(this->_M_start
, this->size());
345 this->_M_start
= __new_start
;
346 this->_M_finish
= __start
;
347 this->_M_end_of_storage
= this->_M_start
+ __new_size
;
351 template<typename _Tp
>
352 void __mini_vector
<_Tp
>::
353 erase(iterator __pos
) throw()
355 while (__pos
+ 1 != this->end())
364 template<typename _Tp
>
365 struct __mv_iter_traits
367 typedef typename
_Tp::value_type value_type
;
368 typedef typename
_Tp::difference_type difference_type
;
371 template<typename _Tp
>
372 struct __mv_iter_traits
<_Tp
*>
374 typedef _Tp value_type
;
375 typedef std::ptrdiff_t difference_type
;
381 bits_per_block
= sizeof(size_t) * bits_per_byte
384 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
386 __lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
387 const _Tp
& __val
, _Compare __comp
)
389 typedef typename __mv_iter_traits
<_ForwardIterator
>::value_type
391 typedef typename __mv_iter_traits
<_ForwardIterator
>::difference_type
394 _DistanceType __len
= __last
- __first
;
395 _DistanceType __half
;
396 _ForwardIterator __middle
;
403 if (__comp(*__middle
, __val
))
407 __len
= __len
- __half
- 1;
415 template<typename _InputIterator
, typename _Predicate
>
416 inline _InputIterator
417 __find_if(_InputIterator __first
, _InputIterator __last
, _Predicate __p
)
419 while (__first
!= __last
&& !__p(*__first
))
424 template<typename _AddrPair
>
426 __num_blocks(_AddrPair __ap
)
427 { return (__ap
.second
- __ap
.first
) + 1; }
429 template<typename _AddrPair
>
431 __num_bitmaps(_AddrPair __ap
)
432 { return __num_blocks(__ap
) / bits_per_block
; }
434 // _Tp should be a pointer type.
435 template<typename _Tp
>
436 class _Inclusive_between
437 : public std::unary_function
<typename
std::pair
<_Tp
, _Tp
>, bool>
440 pointer _M_ptr_value
;
441 typedef typename
std::pair
<_Tp
, _Tp
> _Block_pair
;
444 _Inclusive_between(pointer __ptr
) : _M_ptr_value(__ptr
)
448 operator()(_Block_pair __bp
) const throw()
450 if (std::less_equal
<pointer
>()(_M_ptr_value
, __bp
.second
)
451 && std::greater_equal
<pointer
>()(_M_ptr_value
, __bp
.first
))
458 // Used to pass a Functor to functions by reference.
459 template<typename _Functor
>
461 : public std::unary_function
<typename
_Functor::argument_type
,
462 typename
_Functor::result_type
>
467 typedef typename
_Functor::argument_type argument_type
;
468 typedef typename
_Functor::result_type result_type
;
470 _Functor_Ref(_Functor
& __fref
) : _M_fref(__fref
)
474 operator()(argument_type __arg
)
475 { return _M_fref(__arg
); }
478 // _Tp should be a pointer type, and _Alloc is the Allocator for
480 template<typename _Tp
>
482 : public std::unary_function
<typename
std::pair
<_Tp
, _Tp
>, bool>
484 typedef typename
std::pair
<_Tp
, _Tp
> _Block_pair
;
485 typedef typename
balloc::__mini_vector
<_Block_pair
> _BPVector
;
486 typedef typename
_BPVector::difference_type _Counter_type
;
489 _Counter_type _M_data_offset
;
492 _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
496 operator()(_Block_pair __bp
) throw()
498 // Set the _rover to the last physical location bitmap,
499 // which is the bitmap which belongs to the first free
500 // block. Thus, the bitmaps are in exact reverse order of
501 // the actual memory layout. So, we count down the bimaps,
502 // which is the same as moving up the memory.
504 // If the used count stored at the start of the Bit Map headers
505 // is equal to the number of Objects that the current Block can
506 // store, then there is definitely no space for another single
507 // object, so just return false.
508 _Counter_type __diff
=
509 __gnu_cxx::balloc::__num_bitmaps(__bp
);
511 if (*(reinterpret_cast<size_t*>
512 (__bp
.first
) - (__diff
+ 1))
513 == __gnu_cxx::balloc::__num_blocks(__bp
))
516 size_t* __rover
= reinterpret_cast<size_t*>(__bp
.first
) - 1;
518 for (_Counter_type __i
= 0; __i
< __diff
; ++__i
)
520 _M_data_offset
= __i
;
523 _M_pbitmap
= __rover
;
533 _M_get() const throw()
534 { return _M_pbitmap
; }
537 _M_offset() const throw()
538 { return _M_data_offset
* bits_per_block
; }
543 // _Tp should be a pointer type.
544 template<typename _Tp
>
545 class _Bitmap_counter
547 typedef typename
balloc::__mini_vector
<typename
std::pair
<_Tp
, _Tp
> >
549 typedef typename
_BPVector::size_type _Index_type
;
553 size_t* _M_curr_bmap
;
554 size_t* _M_last_bmap_in_block
;
555 _Index_type _M_curr_index
;
558 // Use the 2nd parameter with care. Make sure that such an
559 // entry exists in the vector before passing that particular
560 // index to this ctor.
561 _Bitmap_counter(_BPVector
& Rvbp
, long __index
= -1) : _M_vbp(Rvbp
)
562 { this->_M_reset(__index
); }
565 _M_reset(long __index
= -1) throw()
570 _M_curr_index
= static_cast<_Index_type
>(-1);
574 _M_curr_index
= __index
;
575 _M_curr_bmap
= reinterpret_cast<size_t*>
576 (_M_vbp
[_M_curr_index
].first
) - 1;
578 _BALLOC_ASSERT(__index
<= (long)_M_vbp
.size() - 1);
580 _M_last_bmap_in_block
= _M_curr_bmap
581 - ((_M_vbp
[_M_curr_index
].second
582 - _M_vbp
[_M_curr_index
].first
+ 1)
583 / bits_per_block
- 1);
586 // Dangerous Function! Use with extreme care. Pass to this
587 // function ONLY those values that are known to be correct,
588 // otherwise this will mess up big time.
590 _M_set_internal_bitmap(size_t* __new_internal_marker
) throw()
591 { _M_curr_bmap
= __new_internal_marker
; }
594 _M_finished() const throw()
595 { return(_M_curr_bmap
== 0); }
600 if (_M_curr_bmap
== _M_last_bmap_in_block
)
602 if (++_M_curr_index
== _M_vbp
.size())
605 this->_M_reset(_M_curr_index
);
613 _M_get() const throw()
614 { return _M_curr_bmap
; }
617 _M_base() const throw()
618 { return _M_vbp
[_M_curr_index
].first
; }
621 _M_offset() const throw()
623 return bits_per_block
624 * ((reinterpret_cast<size_t*>(this->_M_base())
625 - _M_curr_bmap
) - 1);
629 _M_where() const throw()
630 { return _M_curr_index
; }
634 __bit_allocate(size_t* __pbmap
, size_t __pos
) throw()
636 size_t __mask
= 1 << __pos
;
642 __bit_free(size_t* __pbmap
, size_t __pos
) throw()
644 size_t __mask
= 1 << __pos
;
647 } // namespace balloc
649 // Generic Version of the bsf instruction.
651 _Bit_scan_forward(size_t __num
)
652 { return static_cast<size_t>(__builtin_ctzl(__num
)); }
656 typedef size_t* value_type
;
657 typedef balloc::__mini_vector
<value_type
> vector_type
;
658 typedef vector_type::iterator iterator
;
660 struct _LT_pointer_compare
663 operator()(const size_t* __pui
,
664 const size_t __cui
) const throw()
665 { return *__pui
< __cui
; }
668 #if defined __GTHREADS
669 static _Mutex _S_bfl_mutex
;
671 static vector_type _S_free_list
;
674 _M_validate(size_t* __addr
) throw()
676 const vector_type::size_type __max_size
= 64;
677 if (_S_free_list
.size() >= __max_size
)
679 // Ok, the threshold value has been reached. We determine
680 // which block to remove from the list of free blocks.
681 if (*__addr
>= *_S_free_list
.back())
683 // Ok, the new block is greater than or equal to the
684 // last block in the list of free blocks. We just free
686 ::operator delete(static_cast<void*>(__addr
));
691 // Deallocate the last block in the list of free lists,
692 // and insert the new one in it's correct position.
693 ::operator delete(static_cast<void*>(_S_free_list
.back()));
694 _S_free_list
.pop_back();
698 // Just add the block to the list of free lists unconditionally.
699 iterator __temp
= __gnu_cxx::balloc::__lower_bound
700 (_S_free_list
.begin(), _S_free_list
.end(),
701 *__addr
, _LT_pointer_compare());
703 // We may insert the new free list before _temp;
704 _S_free_list
.insert(__temp
, __addr
);
708 _M_should_i_give(size_t __block_size
,
709 size_t __required_size
) throw()
711 const size_t __max_wastage_percentage
= 36;
712 if (__block_size
>= __required_size
&&
713 (((__block_size
- __required_size
) * 100 / __block_size
)
714 < __max_wastage_percentage
))
722 _M_insert(size_t* __addr
) throw()
724 #if defined __GTHREADS
725 _Auto_Lock
__bfl_lock(&_S_bfl_mutex
);
727 // Call _M_validate to decide what should be done with
728 // this particular free list.
729 this->_M_validate(reinterpret_cast<size_t*>(__addr
) - 1);
730 // See discussion as to why this is 1!
734 _M_get(size_t __sz
) throw(std::bad_alloc
);
736 // This function just clears the internal Free List, and gives back
737 // all the memory to the OS.
743 // Forward declare the class.
744 template<typename _Tp
>
745 class bitmap_allocator
;
747 // Specialize for void:
749 class bitmap_allocator
<void>
752 typedef void* pointer
;
753 typedef const void* const_pointer
;
755 // Reference-to-void members are impossible.
756 typedef void value_type
;
757 template<typename _Tp1
>
760 typedef bitmap_allocator
<_Tp1
> other
;
764 template<typename _Tp
>
765 class bitmap_allocator
: private free_list
768 typedef std::size_t size_type
;
769 typedef std::ptrdiff_t difference_type
;
770 typedef _Tp
* pointer
;
771 typedef const _Tp
* const_pointer
;
772 typedef _Tp
& reference
;
773 typedef const _Tp
& const_reference
;
774 typedef _Tp value_type
;
775 template<typename _Tp1
>
778 typedef bitmap_allocator
<_Tp1
> other
;
782 template<size_t _BSize
, size_t _AlignSize
>
787 modulus
= _BSize
% _AlignSize
,
788 value
= _BSize
+ (modulus
? _AlignSize
- (modulus
) : 0)
794 char __M_unused
[aligned_size
<sizeof(value_type
),
795 _BALLOC_ALIGN_BYTES
>::value
];
799 typedef typename
std::pair
<_Alloc_block
*, _Alloc_block
*> _Block_pair
;
802 balloc::__mini_vector
<_Block_pair
> _BPVector
;
804 #if defined _BALLOC_SANITY_CHECK
805 // Complexity: O(lg(N)). Where, N is the number of block of size
806 // sizeof(value_type).
808 _S_check_for_free_blocks() throw()
811 __gnu_cxx::balloc::_Ffit_finder
<_Alloc_block
*> _FFF
;
813 typedef typename
_BPVector::iterator _BPiter
;
815 __gnu_cxx::balloc::__find_if
816 (_S_mem_blocks
.begin(), _S_mem_blocks
.end(),
817 __gnu_cxx::balloc::_Functor_Ref
<_FFF
>(__fff
));
819 _BALLOC_ASSERT(__bpi
== _S_mem_blocks
.end());
823 // Complexity: O(1), but internally depends upon the complexity
824 // of the function free_list::_M_get. The
825 // part where the bitmap headers are written is of worst case
826 // complexity: O(X),where X is the number of blocks of size
827 // sizeof(value_type) within the newly acquired block. Having a
830 _S_refill_pool() throw(std::bad_alloc
)
832 #if defined _BALLOC_SANITY_CHECK
833 _S_check_for_free_blocks();
836 const size_t __num_bitmaps
= _S_block_size
/ balloc::bits_per_block
;
837 const size_t __size_to_allocate
= sizeof(size_t)
838 + _S_block_size
* sizeof(_Alloc_block
)
839 + __num_bitmaps
* sizeof(size_t);
842 reinterpret_cast<size_t*>
843 (this->_M_get(__size_to_allocate
));
847 // The Header information goes at the Beginning of the Block.
849 std::make_pair(reinterpret_cast<_Alloc_block
*>
850 (__temp
+ __num_bitmaps
),
851 reinterpret_cast<_Alloc_block
*>
852 (__temp
+ __num_bitmaps
)
853 + _S_block_size
- 1);
855 // Fill the Vector with this information.
856 _S_mem_blocks
.push_back(__bp
);
858 size_t __bit_mask
= 0; // 0 Indicates all Allocated.
859 __bit_mask
= ~__bit_mask
; // 1 Indicates all Free.
861 for (size_t __i
= 0; __i
< __num_bitmaps
; ++__i
)
862 __temp
[__i
] = __bit_mask
;
868 static _BPVector _S_mem_blocks
;
869 static size_t _S_block_size
;
870 static __gnu_cxx::balloc::
871 _Bitmap_counter
<_Alloc_block
*> _S_last_request
;
872 static typename
_BPVector::size_type _S_last_dealloc_index
;
873 #if defined __GTHREADS
874 static _Mutex _S_mut
;
879 // Complexity: Worst case complexity is O(N), but that is hardly
880 // ever hit. if and when this particular case is encountered,
881 // the next few cases are guaranteed to have a worst case
882 // complexity of O(1)! That's why this function performs very
883 // well on the average. you can consider this function to be
884 // having a complexity referred to commonly as: Amortized
887 _M_allocate_single_object() throw(std::bad_alloc
)
889 #if defined __GTHREADS
890 _Auto_Lock
__bit_lock(&_S_mut
);
893 // The algorithm is something like this: The last_request
894 // variable points to the last accessed Bit Map. When such a
895 // condition occurs, we try to find a free block in the
896 // current bitmap, or succeeding bitmaps until the last bitmap
897 // is reached. If no free block turns up, we resort to First
900 // WARNING: Do not re-order the condition in the while
901 // statement below, because it relies on C++'s short-circuit
902 // evaluation. The return from _S_last_request->_M_get() will
903 // NOT be dereference able if _S_last_request->_M_finished()
904 // returns true. This would inevitably lead to a NULL pointer
905 // dereference if tinkered with.
906 while (_S_last_request
._M_finished() == false
907 && (*(_S_last_request
._M_get()) == 0))
909 _S_last_request
.operator++();
912 if (__builtin_expect(_S_last_request
._M_finished() == true, false))
914 // Fall Back to First Fit algorithm.
916 __gnu_cxx::balloc::_Ffit_finder
<_Alloc_block
*> _FFF
;
918 typedef typename
_BPVector::iterator _BPiter
;
920 __gnu_cxx::balloc::__find_if
921 (_S_mem_blocks
.begin(), _S_mem_blocks
.end(),
922 __gnu_cxx::balloc::_Functor_Ref
<_FFF
>(__fff
));
924 if (__bpi
!= _S_mem_blocks
.end())
926 // Search was successful. Ok, now mark the first bit from
927 // the right as 0, meaning Allocated. This bit is obtained
928 // by calling _M_get() on __fff.
929 size_t __nz_bit
= _Bit_scan_forward(*__fff
._M_get());
930 balloc::__bit_allocate(__fff
._M_get(), __nz_bit
);
932 _S_last_request
._M_reset(__bpi
- _S_mem_blocks
.begin());
934 // Now, get the address of the bit we marked as allocated.
935 pointer __ret
= reinterpret_cast<pointer
>
936 (__bpi
->first
+ __fff
._M_offset() + __nz_bit
);
937 size_t* __puse_count
=
938 reinterpret_cast<size_t*>
940 - (__gnu_cxx::balloc::__num_bitmaps(*__bpi
) + 1);
947 // Search was unsuccessful. We Add more memory to the
948 // pool by calling _S_refill_pool().
951 // _M_Reset the _S_last_request structure to the first
952 // free block's bit map.
953 _S_last_request
._M_reset(_S_mem_blocks
.size() - 1);
955 // Now, mark that bit as allocated.
959 // _S_last_request holds a pointer to a valid bit map, that
960 // points to a free block in memory.
961 size_t __nz_bit
= _Bit_scan_forward(*_S_last_request
._M_get());
962 balloc::__bit_allocate(_S_last_request
._M_get(), __nz_bit
);
964 pointer __ret
= reinterpret_cast<pointer
>
965 (_S_last_request
._M_base() + _S_last_request
._M_offset() + __nz_bit
);
967 size_t* __puse_count
= reinterpret_cast<size_t*>
968 (_S_mem_blocks
[_S_last_request
._M_where()].first
)
969 - (__gnu_cxx::balloc::
970 __num_bitmaps(_S_mem_blocks
[_S_last_request
._M_where()]) + 1);
976 // Complexity: O(lg(N)), but the worst case is hit quite often!
977 // I need to do something about this. I'll be able to work on
978 // it, only when I have some solid figures from a few real apps.
980 _M_deallocate_single_object(pointer __p
) throw()
982 #if defined __GTHREADS
983 _Auto_Lock
__bit_lock(&_S_mut
);
985 _Alloc_block
* __real_p
= reinterpret_cast<_Alloc_block
*>(__p
);
987 typedef typename
_BPVector::iterator _Iterator
;
988 typedef typename
_BPVector::difference_type _Difference_type
;
990 _Difference_type __diff
;
993 _BALLOC_ASSERT(_S_last_dealloc_index
>= 0);
996 if (__gnu_cxx::balloc::_Inclusive_between
<_Alloc_block
*>
998 (_S_mem_blocks
[_S_last_dealloc_index
]))
1000 _BALLOC_ASSERT(_S_last_dealloc_index
<= _S_mem_blocks
.size() - 1);
1002 // Initial Assumption was correct!
1003 __diff
= _S_last_dealloc_index
;
1004 __displacement
= __real_p
- _S_mem_blocks
[__diff
].first
;
1010 __find_if(_S_mem_blocks
.begin(),
1011 _S_mem_blocks
.end(),
1013 _Inclusive_between
<_Alloc_block
*>(__real_p
));
1015 _BALLOC_ASSERT(_iter
!= _S_mem_blocks
.end());
1017 __diff
= _iter
- _S_mem_blocks
.begin();
1018 __displacement
= __real_p
- _S_mem_blocks
[__diff
].first
;
1019 _S_last_dealloc_index
= __diff
;
1022 // Get the position of the iterator that has been found.
1023 const size_t __rotate
= __displacement
% balloc::bits_per_block
;
1025 reinterpret_cast<size_t*>
1026 (_S_mem_blocks
[__diff
].first
) - 1;
1027 __bitmapC
-= (__displacement
/ balloc::bits_per_block
);
1029 balloc::__bit_free(__bitmapC
, __rotate
);
1030 size_t* __puse_count
= reinterpret_cast<size_t*>
1031 (_S_mem_blocks
[__diff
].first
)
1032 - (__gnu_cxx::balloc::__num_bitmaps(_S_mem_blocks
[__diff
]) + 1);
1034 _BALLOC_ASSERT(*__puse_count
!= 0);
1038 if (__builtin_expect(*__puse_count
== 0, false))
1042 // We can safely remove this block.
1043 // _Block_pair __bp = _S_mem_blocks[__diff];
1044 this->_M_insert(__puse_count
);
1045 _S_mem_blocks
.erase(_S_mem_blocks
.begin() + __diff
);
1047 // Reset the _S_last_request variable to reflect the
1048 // erased block. We do this to protect future requests
1049 // after the last block has been removed from a particular
1050 // memory Chunk, which in turn has been returned to the
1051 // free list, and hence had been erased from the vector,
1052 // so the size of the vector gets reduced by 1.
1053 if ((_Difference_type
)_S_last_request
._M_where() >= __diff
--)
1054 _S_last_request
._M_reset(__diff
);
1056 // If the Index into the vector of the region of memory
1057 // that might hold the next address that will be passed to
1058 // deallocated may have been invalidated due to the above
1059 // erase procedure being called on the vector, hence we
1060 // try to restore this invariant too.
1061 if (_S_last_dealloc_index
>= _S_mem_blocks
.size())
1063 _S_last_dealloc_index
=(__diff
!= -1 ? __diff
: 0);
1064 _BALLOC_ASSERT(_S_last_dealloc_index
>= 0);
1070 bitmap_allocator() throw()
1073 bitmap_allocator(const bitmap_allocator
&)
1076 template<typename _Tp1
>
1077 bitmap_allocator(const bitmap_allocator
<_Tp1
>&) throw()
1080 ~bitmap_allocator() throw()
1083 // Complexity: O(1), but internally the complexity depends upon the
1084 // complexity of the function(s) _S_allocate_single_object and
1087 allocate(size_type __n
)
1089 if (__builtin_expect(__n
> this->max_size(), false))
1090 std::__throw_bad_alloc();
1092 if (__builtin_expect(__n
== 1, true))
1093 return this->_M_allocate_single_object();
1096 const size_type __b
= __n
* sizeof(value_type
);
1097 return reinterpret_cast<pointer
>(::operator new(__b
));
1102 allocate(size_type __n
, typename bitmap_allocator
<void>::const_pointer
)
1103 { return allocate(__n
); }
1106 deallocate(pointer __p
, size_type __n
) throw()
1108 if (__builtin_expect(__p
!= 0, true))
1110 if (__builtin_expect(__n
== 1, true))
1111 this->_M_deallocate_single_object(__p
);
1113 ::operator delete(__p
);
1118 address(reference __r
) const
1122 address(const_reference __r
) const
1126 max_size() const throw()
1127 { return size_type(-1) / sizeof(value_type
); }
1130 construct(pointer __p
, const_reference __data
)
1131 { ::new(__p
) value_type(__data
); }
1134 destroy(pointer __p
)
1135 { __p
->~value_type(); }
1138 template<typename _Tp1
, typename _Tp2
>
1140 operator==(const bitmap_allocator
<_Tp1
>&,
1141 const bitmap_allocator
<_Tp2
>&) throw()
1144 template<typename _Tp1
, typename _Tp2
>
1146 operator!=(const bitmap_allocator
<_Tp1
>&,
1147 const bitmap_allocator
<_Tp2
>&) throw()
1150 // Static member definitions.
1151 template<typename _Tp
>
1152 typename bitmap_allocator
<_Tp
>::_BPVector
1153 bitmap_allocator
<_Tp
>::_S_mem_blocks
;
1155 template<typename _Tp
>
1156 size_t bitmap_allocator
<_Tp
>::_S_block_size
=
1157 2 * balloc::bits_per_block
;
1159 template<typename _Tp
>
1160 typename
__gnu_cxx::bitmap_allocator
<_Tp
>::_BPVector::size_type
1161 bitmap_allocator
<_Tp
>::_S_last_dealloc_index
= 0;
1163 template<typename _Tp
>
1164 __gnu_cxx::balloc::_Bitmap_counter
1165 <typename bitmap_allocator
<_Tp
>::_Alloc_block
*>
1166 bitmap_allocator
<_Tp
>::_S_last_request(_S_mem_blocks
);
1168 #if defined __GTHREADS
1169 template<typename _Tp
>
1171 bitmap_allocator
<_Tp
>::_S_mut
;
1179 // LocalWords: namespace GTHREADS bool const gthread endif Mutex mutex