URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc3/] [libstdc++-v3/] [include/] [ext/] [bitmap_allocator.h] - Rev 799
Go to most recent revision | Compare with Previous | Blame | View Log
// Bitmap Allocator. -*- C++ -*- // Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 3, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // <http://www.gnu.org/licenses/>. /** @file ext/bitmap_allocator.h * This file is a GNU extension to the Standard C++ Library. */ #ifndef _BITMAP_ALLOCATOR_H #define _BITMAP_ALLOCATOR_H 1 #include <cstddef> // For std::size_t, and ptrdiff_t. #include <bits/functexcept.h> // For __throw_bad_alloc(). #include <utility> // For std::pair. #include <functional> // For greater_equal, and less_equal. #include <new> // For operator new. #include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT #include <ext/concurrence.h> #include <bits/move.h> /** @brief The constant in the expression below is the alignment * required in bytes. */ #define _BALLOC_ALIGN_BYTES 8 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) using std::size_t; using std::ptrdiff_t; namespace __detail { /** @class __mini_vector bitmap_allocator.h bitmap_allocator.h * * @brief __mini_vector<> is a stripped down version of the * full-fledged std::vector<>. * * It is to be used only for built-in types or PODs. Notable * differences are: * * @detail * 1. Not all accessor functions are present. * 2. Used ONLY for PODs. * 3. No Allocator template argument. Uses ::operator new() to get * memory, and ::operator delete() to free it. * Caveat: The dtor does NOT free the memory allocated, so this a * memory-leaking vector! */ template<typename _Tp> class __mini_vector { __mini_vector(const __mini_vector&); __mini_vector& operator=(const __mini_vector&); public: typedef _Tp value_type; typedef _Tp* pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef pointer iterator; private: pointer _M_start; pointer _M_finish; pointer _M_end_of_storage; size_type _M_space_left() const throw() { return _M_end_of_storage - _M_finish; } pointer allocate(size_type __n) { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); } void deallocate(pointer __p, size_type) { ::operator delete(__p); } public: // Members used: size(), push_back(), pop_back(), // insert(iterator, const_reference), erase(iterator), // begin(), end(), back(), operator[]. __mini_vector() : _M_start(0), _M_finish(0), _M_end_of_storage(0) { } size_type size() const throw() { return _M_finish - _M_start; } iterator begin() const throw() { return this->_M_start; } iterator end() const throw() { return this->_M_finish; } reference back() const throw() { return *(this->end() - 1); } reference operator[](const size_type __pos) const throw() { return this->_M_start[__pos]; } void insert(iterator __pos, const_reference __x); void push_back(const_reference __x) { if (this->_M_space_left()) { *this->end() = __x; ++this->_M_finish; } else this->insert(this->end(), __x); } void pop_back() throw() { --this->_M_finish; } void erase(iterator __pos) throw(); void clear() throw() { this->_M_finish = this->_M_start; } }; // Out of line function definitions. template<typename _Tp> void __mini_vector<_Tp>:: insert(iterator __pos, const_reference __x) { if (this->_M_space_left()) { size_type __to_move = this->_M_finish - __pos; iterator __dest = this->end(); iterator __src = this->end() - 1; ++this->_M_finish; while (__to_move) { *__dest = *__src; --__dest; --__src; --__to_move; } *__pos = __x; } else { size_type __new_size = this->size() ? this->size() * 2 : 1; iterator __new_start = this->allocate(__new_size); iterator __first = this->begin(); iterator __start = __new_start; while (__first != __pos) { *__start = *__first; ++__start; ++__first; } *__start = __x; ++__start; while (__first != this->end()) { *__start = *__first; ++__start; ++__first; } if (this->_M_start) this->deallocate(this->_M_start, this->size()); this->_M_start = __new_start; this->_M_finish = __start; this->_M_end_of_storage = this->_M_start + __new_size; } } template<typename _Tp> void __mini_vector<_Tp>:: erase(iterator __pos) throw() { while (__pos + 1 != this->end()) { *__pos = __pos[1]; ++__pos; } --this->_M_finish; } template<typename _Tp> struct __mv_iter_traits { typedef typename _Tp::value_type value_type; typedef typename _Tp::difference_type difference_type; }; template<typename _Tp> struct __mv_iter_traits<_Tp*> { typedef _Tp value_type; typedef ptrdiff_t difference_type; }; enum { bits_per_byte = 8, bits_per_block = sizeof(size_t) * size_t(bits_per_byte) }; template<typename _ForwardIterator, typename _Tp, typename _Compare> _ForwardIterator __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val, _Compare __comp) { typedef typename __mv_iter_traits<_ForwardIterator>::value_type _ValueType; typedef typename __mv_iter_traits<_ForwardIterator>::difference_type _DistanceType; _DistanceType __len = __last - __first; _DistanceType __half; _ForwardIterator __middle; while (__len > 0) { __half = __len >> 1; __middle = __first; __middle += __half; if (__comp(*__middle, __val)) { __first = __middle; ++__first; __len = __len - __half - 1; } else __len = __half; } return __first; } /** @brief The number of Blocks pointed to by the address pair * passed to the function. */ template<typename _AddrPair> inline size_t __num_blocks(_AddrPair __ap) { return (__ap.second - __ap.first) + 1; } /** @brief The number of Bit-maps pointed to by the address pair * passed to the function. */ template<typename _AddrPair> inline size_t __num_bitmaps(_AddrPair __ap) { return __num_blocks(__ap) / size_t(bits_per_block); } // _Tp should be a pointer type. template<typename _Tp> class _Inclusive_between : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> { typedef _Tp pointer; pointer _M_ptr_value; typedef typename std::pair<_Tp, _Tp> _Block_pair; public: _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr) { } bool operator()(_Block_pair __bp) const throw() { if (std::less_equal<pointer>()(_M_ptr_value, __bp.second) && std::greater_equal<pointer>()(_M_ptr_value, __bp.first)) return true; else return false; } }; // Used to pass a Functor to functions by reference. template<typename _Functor> class _Functor_Ref : public std::unary_function<typename _Functor::argument_type, typename _Functor::result_type> { _Functor& _M_fref; public: typedef typename _Functor::argument_type argument_type; typedef typename _Functor::result_type result_type; _Functor_Ref(_Functor& __fref) : _M_fref(__fref) { } result_type operator()(argument_type __arg) { return _M_fref(__arg); } }; /** @class _Ffit_finder bitmap_allocator.h bitmap_allocator.h * * @brief The class which acts as a predicate for applying the * first-fit memory allocation policy for the bitmap allocator. */ // _Tp should be a pointer type, and _Alloc is the Allocator for // the vector. template<typename _Tp> class _Ffit_finder : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> { typedef typename std::pair<_Tp, _Tp> _Block_pair; typedef typename __detail::__mini_vector<_Block_pair> _BPVector; typedef typename _BPVector::difference_type _Counter_type; size_t* _M_pbitmap; _Counter_type _M_data_offset; public: _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0) { } bool operator()(_Block_pair __bp) throw() { // Set the _rover to the last physical location bitmap, // which is the bitmap which belongs to the first free // block. Thus, the bitmaps are in exact reverse order of // the actual memory layout. So, we count down the bitmaps, // which is the same as moving up the memory. // If the used count stored at the start of the Bit Map headers // is equal to the number of Objects that the current Block can // store, then there is definitely no space for another single // object, so just return false. _Counter_type __diff = __detail::__num_bitmaps(__bp); if (*(reinterpret_cast<size_t*> (__bp.first) - (__diff + 1)) == __detail::__num_blocks(__bp)) return false; size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1; for (_Counter_type __i = 0; __i < __diff; ++__i) { _M_data_offset = __i; if (*__rover) { _M_pbitmap = __rover; return true; } --__rover; } return false; } size_t* _M_get() const throw() { return _M_pbitmap; } _Counter_type _M_offset() const throw() { return _M_data_offset * size_t(bits_per_block); } }; /** @class _Bitmap_counter bitmap_allocator.h bitmap_allocator.h * * @brief The bitmap counter which acts as the bitmap * manipulator, and manages the bit-manipulation functions and * the searching and identification functions on the bit-map. */ // _Tp should be a pointer type. template<typename _Tp> class _Bitmap_counter { typedef typename __detail::__mini_vector<typename std::pair<_Tp, _Tp> > _BPVector; typedef typename _BPVector::size_type _Index_type; typedef _Tp pointer; _BPVector& _M_vbp; size_t* _M_curr_bmap; size_t* _M_last_bmap_in_block; _Index_type _M_curr_index; public: // Use the 2nd parameter with care. Make sure that such an // entry exists in the vector before passing that particular // index to this ctor. _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp) { this->_M_reset(__index); } void _M_reset(long __index = -1) throw() { if (__index == -1) { _M_curr_bmap = 0; _M_curr_index = static_cast<_Index_type>(-1); return; } _M_curr_index = __index; _M_curr_bmap = reinterpret_cast<size_t*> (_M_vbp[_M_curr_index].first) - 1; _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1); _M_last_bmap_in_block = _M_curr_bmap - ((_M_vbp[_M_curr_index].second - _M_vbp[_M_curr_index].first + 1) / size_t(bits_per_block) - 1); } // Dangerous Function! Use with extreme care. Pass to this // function ONLY those values that are known to be correct, // otherwise this will mess up big time. void _M_set_internal_bitmap(size_t* __new_internal_marker) throw() { _M_curr_bmap = __new_internal_marker; } bool _M_finished() const throw() { return(_M_curr_bmap == 0); } _Bitmap_counter& operator++() throw() { if (_M_curr_bmap == _M_last_bmap_in_block) { if (++_M_curr_index == _M_vbp.size()) _M_curr_bmap = 0; else this->_M_reset(_M_curr_index); } else --_M_curr_bmap; return *this; } size_t* _M_get() const throw() { return _M_curr_bmap; } pointer _M_base() const throw() { return _M_vbp[_M_curr_index].first; } _Index_type _M_offset() const throw() { return size_t(bits_per_block) * ((reinterpret_cast<size_t*>(this->_M_base()) - _M_curr_bmap) - 1); } _Index_type _M_where() const throw() { return _M_curr_index; } }; /** @brief Mark a memory address as allocated by re-setting the * corresponding bit in the bit-map. */ inline void __bit_allocate(size_t* __pbmap, size_t __pos) throw() { size_t __mask = 1 << __pos; __mask = ~__mask; *__pbmap &= __mask; } /** @brief Mark a memory address as free by setting the * corresponding bit in the bit-map. */ inline void __bit_free(size_t* __pbmap, size_t __pos) throw() { size_t __mask = 1 << __pos; *__pbmap |= __mask; } } // namespace __detail /** @brief Generic Version of the bsf instruction. */ inline size_t _Bit_scan_forward(size_t __num) { return static_cast<size_t>(__builtin_ctzl(__num)); } /** @class free_list bitmap_allocator.h bitmap_allocator.h * * @brief The free list class for managing chunks of memory to be * given to and returned by the bitmap_allocator. */ class free_list { public: typedef size_t* value_type; typedef __detail::__mini_vector<value_type> vector_type; typedef vector_type::iterator iterator; typedef __mutex __mutex_type; private: struct _LT_pointer_compare { bool operator()(const size_t* __pui, const size_t __cui) const throw() { return *__pui < __cui; } }; #if defined __GTHREADS __mutex_type& _M_get_mutex() { static __mutex_type _S_mutex; return _S_mutex; } #endif vector_type& _M_get_free_list() { static vector_type _S_free_list; return _S_free_list; } /** @brief Performs validation of memory based on their size. * * @param __addr The pointer to the memory block to be * validated. * * @detail Validates the memory block passed to this function and * appropriately performs the action of managing the free list of * blocks by adding this block to the free list or deleting this * or larger blocks from the free list. */ void _M_validate(size_t* __addr) throw() { vector_type& __free_list = _M_get_free_list(); const vector_type::size_type __max_size = 64; if (__free_list.size() >= __max_size) { // Ok, the threshold value has been reached. We determine // which block to remove from the list of free blocks. if (*__addr >= *__free_list.back()) { // Ok, the new block is greater than or equal to the // last block in the list of free blocks. We just free // the new block. ::operator delete(static_cast<void*>(__addr)); return; } else { // Deallocate the last block in the list of free lists, // and insert the new one in its correct position. ::operator delete(static_cast<void*>(__free_list.back())); __free_list.pop_back(); } } // Just add the block to the list of free lists unconditionally. iterator __temp = __detail::__lower_bound (__free_list.begin(), __free_list.end(), *__addr, _LT_pointer_compare()); // We may insert the new free list before _temp; __free_list.insert(__temp, __addr); } /** @brief Decides whether the wastage of memory is acceptable for * the current memory request and returns accordingly. * * @param __block_size The size of the block available in the free * list. * * @param __required_size The required size of the memory block. * * @return true if the wastage incurred is acceptable, else returns * false. */ bool _M_should_i_give(size_t __block_size, size_t __required_size) throw() { const size_t __max_wastage_percentage = 36; if (__block_size >= __required_size && (((__block_size - __required_size) * 100 / __block_size) < __max_wastage_percentage)) return true; else return false; } public: /** @brief This function returns the block of memory to the * internal free list. * * @param __addr The pointer to the memory block that was given * by a call to the _M_get function. */ inline void _M_insert(size_t* __addr) throw() { #if defined __GTHREADS __scoped_lock __bfl_lock(_M_get_mutex()); #endif // Call _M_validate to decide what should be done with // this particular free list. this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1); // See discussion as to why this is 1! } /** @brief This function gets a block of memory of the specified * size from the free list. * * @param __sz The size in bytes of the memory required. * * @return A pointer to the new memory block of size at least * equal to that requested. */ size_t* _M_get(size_t __sz) throw(std::bad_alloc); /** @brief This function just clears the internal Free List, and * gives back all the memory to the OS. */ void _M_clear(); }; // Forward declare the class. template<typename _Tp> class bitmap_allocator; // Specialize for void: template<> class bitmap_allocator<void> { public: typedef void* pointer; typedef const void* const_pointer; // Reference-to-void members are impossible. typedef void value_type; template<typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; }; }; /** * @brief Bitmap Allocator, primary template. * @ingroup allocators */ template<typename _Tp> class bitmap_allocator : private free_list { public: typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef const _Tp* const_pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef _Tp value_type; typedef free_list::__mutex_type __mutex_type; template<typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; }; private: template<size_t _BSize, size_t _AlignSize> struct aligned_size { enum { modulus = _BSize % _AlignSize, value = _BSize + (modulus ? _AlignSize - (modulus) : 0) }; }; struct _Alloc_block { char __M_unused[aligned_size<sizeof(value_type), _BALLOC_ALIGN_BYTES>::value]; }; typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair; typedef typename __detail::__mini_vector<_Block_pair> _BPVector; typedef typename _BPVector::iterator _BPiter; template<typename _Predicate> static _BPiter _S_find(_Predicate __p) { _BPiter __first = _S_mem_blocks.begin(); while (__first != _S_mem_blocks.end() && !__p(*__first)) ++__first; return __first; } #if defined _GLIBCXX_DEBUG // Complexity: O(lg(N)). Where, N is the number of block of size // sizeof(value_type). void _S_check_for_free_blocks() throw() { typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; _BPiter __bpi = _S_find(_FFF()); _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end()); } #endif /** @brief Responsible for exponentially growing the internal * memory pool. * * @throw std::bad_alloc. If memory can not be allocated. * * @detail Complexity: O(1), but internally depends upon the * complexity of the function free_list::_M_get. The part where * the bitmap headers are written has complexity: O(X),where X * is the number of blocks of size sizeof(value_type) within * the newly acquired block. Having a tight bound. */ void _S_refill_pool() throw(std::bad_alloc) { #if defined _GLIBCXX_DEBUG _S_check_for_free_blocks(); #endif const size_t __num_bitmaps = (_S_block_size / size_t(__detail::bits_per_block)); const size_t __size_to_allocate = sizeof(size_t) + _S_block_size * sizeof(_Alloc_block) + __num_bitmaps * sizeof(size_t); size_t* __temp = reinterpret_cast<size_t*>(this->_M_get(__size_to_allocate)); *__temp = 0; ++__temp; // The Header information goes at the Beginning of the Block. _Block_pair __bp = std::make_pair(reinterpret_cast<_Alloc_block*> (__temp + __num_bitmaps), reinterpret_cast<_Alloc_block*> (__temp + __num_bitmaps) + _S_block_size - 1); // Fill the Vector with this information. _S_mem_blocks.push_back(__bp); for (size_t __i = 0; __i < __num_bitmaps; ++__i) __temp[__i] = ~static_cast<size_t>(0); // 1 Indicates all Free. _S_block_size *= 2; } static _BPVector _S_mem_blocks; static size_t _S_block_size; static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request; static typename _BPVector::size_type _S_last_dealloc_index; #if defined __GTHREADS static __mutex_type _S_mut; #endif public: /** @brief Allocates memory for a single object of size * sizeof(_Tp). * * @throw std::bad_alloc. If memory can not be allocated. * * @detail Complexity: Worst case complexity is O(N), but that * is hardly ever hit. If and when this particular case is * encountered, the next few cases are guaranteed to have a * worst case complexity of O(1)! That's why this function * performs very well on average. You can consider this * function to have a complexity referred to commonly as: * Amortized Constant time. */ pointer _M_allocate_single_object() throw(std::bad_alloc) { #if defined __GTHREADS __scoped_lock __bit_lock(_S_mut); #endif // The algorithm is something like this: The last_request // variable points to the last accessed Bit Map. When such a // condition occurs, we try to find a free block in the // current bitmap, or succeeding bitmaps until the last bitmap // is reached. If no free block turns up, we resort to First // Fit method. // WARNING: Do not re-order the condition in the while // statement below, because it relies on C++'s short-circuit // evaluation. The return from _S_last_request->_M_get() will // NOT be dereference able if _S_last_request->_M_finished() // returns true. This would inevitably lead to a NULL pointer // dereference if tinkered with. while (_S_last_request._M_finished() == false && (*(_S_last_request._M_get()) == 0)) _S_last_request.operator++(); if (__builtin_expect(_S_last_request._M_finished() == true, false)) { // Fall Back to First Fit algorithm. typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; _FFF __fff; _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff)); if (__bpi != _S_mem_blocks.end()) { // Search was successful. Ok, now mark the first bit from // the right as 0, meaning Allocated. This bit is obtained // by calling _M_get() on __fff. size_t __nz_bit = _Bit_scan_forward(*__fff._M_get()); __detail::__bit_allocate(__fff._M_get(), __nz_bit); _S_last_request._M_reset(__bpi - _S_mem_blocks.begin()); // Now, get the address of the bit we marked as allocated. pointer __ret = reinterpret_cast<pointer> (__bpi->first + __fff._M_offset() + __nz_bit); size_t* __puse_count = reinterpret_cast<size_t*> (__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1); ++(*__puse_count); return __ret; } else { // Search was unsuccessful. We Add more memory to the // pool by calling _S_refill_pool(). _S_refill_pool(); // _M_Reset the _S_last_request structure to the first // free block's bit map. _S_last_request._M_reset(_S_mem_blocks.size() - 1); // Now, mark that bit as allocated. } } // _S_last_request holds a pointer to a valid bit map, that // points to a free block in memory. size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get()); __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit); pointer __ret = reinterpret_cast<pointer> (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit); size_t* __puse_count = reinterpret_cast<size_t*> (_S_mem_blocks[_S_last_request._M_where()].first) - (__detail:: __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1); ++(*__puse_count); return __ret; } /** @brief Deallocates memory that belongs to a single object of * size sizeof(_Tp). * * @detail Complexity: O(lg(N)), but the worst case is not hit * often! This is because containers usually deallocate memory * close to each other and this case is handled in O(1) time by * the deallocate function. */ void _M_deallocate_single_object(pointer __p) throw() { #if defined __GTHREADS __scoped_lock __bit_lock(_S_mut); #endif _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p); typedef typename _BPVector::iterator _Iterator; typedef typename _BPVector::difference_type _Difference_type; _Difference_type __diff; long __displacement; _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p); if (__ibt(_S_mem_blocks[_S_last_dealloc_index])) { _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index <= _S_mem_blocks.size() - 1); // Initial Assumption was correct! __diff = _S_last_dealloc_index; __displacement = __real_p - _S_mem_blocks[__diff].first; } else { _Iterator _iter = _S_find(__ibt); _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end()); __diff = _iter - _S_mem_blocks.begin(); __displacement = __real_p - _S_mem_blocks[__diff].first; _S_last_dealloc_index = __diff; } // Get the position of the iterator that has been found. const size_t __rotate = (__displacement % size_t(__detail::bits_per_block)); size_t* __bitmapC = reinterpret_cast<size_t*> (_S_mem_blocks[__diff].first) - 1; __bitmapC -= (__displacement / size_t(__detail::bits_per_block)); __detail::__bit_free(__bitmapC, __rotate); size_t* __puse_count = reinterpret_cast<size_t*> (_S_mem_blocks[__diff].first) - (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1); _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0); --(*__puse_count); if (__builtin_expect(*__puse_count == 0, false)) { _S_block_size /= 2; // We can safely remove this block. // _Block_pair __bp = _S_mem_blocks[__diff]; this->_M_insert(__puse_count); _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff); // Reset the _S_last_request variable to reflect the // erased block. We do this to protect future requests // after the last block has been removed from a particular // memory Chunk, which in turn has been returned to the // free list, and hence had been erased from the vector, // so the size of the vector gets reduced by 1. if ((_Difference_type)_S_last_request._M_where() >= __diff--) _S_last_request._M_reset(__diff); // If the Index into the vector of the region of memory // that might hold the next address that will be passed to // deallocated may have been invalidated due to the above // erase procedure being called on the vector, hence we // try to restore this invariant too. if (_S_last_dealloc_index >= _S_mem_blocks.size()) { _S_last_dealloc_index =(__diff != -1 ? __diff : 0); _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); } } } public: bitmap_allocator() throw() { } bitmap_allocator(const bitmap_allocator&) { } template<typename _Tp1> bitmap_allocator(const bitmap_allocator<_Tp1>&) throw() { } ~bitmap_allocator() throw() { } pointer allocate(size_type __n) { if (__n > this->max_size()) std::__throw_bad_alloc(); if (__builtin_expect(__n == 1, true)) return this->_M_allocate_single_object(); else { const size_type __b = __n * sizeof(value_type); return reinterpret_cast<pointer>(::operator new(__b)); } } pointer allocate(size_type __n, typename bitmap_allocator<void>::const_pointer) { return allocate(__n); } void deallocate(pointer __p, size_type __n) throw() { if (__builtin_expect(__p != 0, true)) { if (__builtin_expect(__n == 1, true)) this->_M_deallocate_single_object(__p); else ::operator delete(__p); } } pointer address(reference __r) const { return &__r; } const_pointer address(const_reference __r) const { return &__r; } size_type max_size() const throw() { return size_type(-1) / sizeof(value_type); } void construct(pointer __p, const_reference __data) { ::new((void *)__p) value_type(__data); } #ifdef __GXX_EXPERIMENTAL_CXX0X__ template<typename... _Args> void construct(pointer __p, _Args&&... __args) { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); } #endif void destroy(pointer __p) { __p->~value_type(); } }; template<typename _Tp1, typename _Tp2> bool operator==(const bitmap_allocator<_Tp1>&, const bitmap_allocator<_Tp2>&) throw() { return true; } template<typename _Tp1, typename _Tp2> bool operator!=(const bitmap_allocator<_Tp1>&, const bitmap_allocator<_Tp2>&) throw() { return false; } // Static member definitions. template<typename _Tp> typename bitmap_allocator<_Tp>::_BPVector bitmap_allocator<_Tp>::_S_mem_blocks; template<typename _Tp> size_t bitmap_allocator<_Tp>::_S_block_size = 2 * size_t(__detail::bits_per_block); template<typename _Tp> typename bitmap_allocator<_Tp>::_BPVector::size_type bitmap_allocator<_Tp>::_S_last_dealloc_index = 0; template<typename _Tp> __detail::_Bitmap_counter <typename bitmap_allocator<_Tp>::_Alloc_block*> bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks); #if defined __GTHREADS template<typename _Tp> typename bitmap_allocator<_Tp>::__mutex_type bitmap_allocator<_Tp>::_S_mut; #endif _GLIBCXX_END_NAMESPACE #endif
Go to most recent revision | Compare with Previous | Blame | View Log