bitmap_allocator.h   [plain text]

// Bitmapped Allocator. -*- C++ -*-

// Copyright (C) 2004 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 2, 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.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.



#if !defined _BITMAP_ALLOCATOR_H
#define _BITMAP_ALLOCATOR_H 1

#include <cstddef>
//For std::size_t, and ptrdiff_t.
#include <utility>
//For std::pair.
#include <algorithm>
//std::find_if, and std::lower_bound.
#include <vector>
//For the free list of exponentially growing memory blocks. At max,
//size of the vector should be  not more than the number of bits in an
//integer or an unsigned integer.
#include <functional>
//For greater_equal, and less_equal.
#include <new>
//For operator new.
#include <bits/gthr.h>
//For __gthread_mutex_t, __gthread_mutex_lock and __gthread_mutex_unlock.
#include <ext/new_allocator.h>
//For __gnu_cxx::new_allocator for std::vector.

#include <cassert>
#define NDEBUG

//#define CHECK_FOR_ERRORS
//#define __CPU_HAS_BACKWARD_BRANCH_PREDICTION

namespace __gnu_cxx
{
  namespace {
#if defined __GTHREADS
    bool const __threads_enabled = __gthread_active_p();
#endif

  }

#if defined __GTHREADS
  class _Mutex {
    __gthread_mutex_t _M_mut;
    //Prevent Copying and assignment.
    _Mutex (_Mutex const&);
    _Mutex& operator= (_Mutex const&);
  public:
    _Mutex ()
    {
      if (__threads_enabled)
	{
#if !defined __GTHREAD_MUTEX_INIT
	  __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut);
#else
	  __gthread_mutex_t __mtemp = __GTHREAD_MUTEX_INIT;
	  _M_mut = __mtemp;
#endif
	}
    }
    ~_Mutex ()
    {
      //Gthreads does not define a Mutex Destruction Function.
    }
    __gthread_mutex_t *_M_get() { return &_M_mut; }
  };

  class _Lock {
    _Mutex* _M_pmt;
    bool _M_locked;
    //Prevent Copying and assignment.
    _Lock (_Lock const&);
    _Lock& operator= (_Lock const&);
  public:
    _Lock(_Mutex* __mptr)
      : _M_pmt(__mptr), _M_locked(false)
    { this->_M_lock(); }
    void _M_lock()
    {
      if (__threads_enabled)
	{
	  _M_locked = true;
	  __gthread_mutex_lock(_M_pmt->_M_get());
	}
    }
    void _M_unlock()
    {
      if (__threads_enabled)
	{
	  if (__builtin_expect(_M_locked, true))
	    {
	      __gthread_mutex_unlock(_M_pmt->_M_get());
	      _M_locked = false;
	    }
	}
    }
    ~_Lock() { this->_M_unlock(); }
  };
#endif



  namespace __aux_balloc {
    static const unsigned int _Bits_Per_Byte = 8;
    static const unsigned int _Bits_Per_Block = sizeof(unsigned int) * _Bits_Per_Byte;

    template <typename _Addr_Pair_t>
    inline size_t __balloc_num_blocks (_Addr_Pair_t __ap)
    {
      return (__ap.second - __ap.first) + 1;
    }

    template <typename _Addr_Pair_t>
    inline size_t __balloc_num_bit_maps (_Addr_Pair_t __ap)
    {
      return __balloc_num_blocks(__ap) / _Bits_Per_Block;
    }

    //T 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); }
    };


    //T should be a pointer type, and A is the Allocator for the vector.
    template <typename _Tp, typename _Alloc>
    class _Ffit_finder 
      : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> {
      typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector;
      typedef typename _BPVector::difference_type _Counter_type;
      typedef typename std::pair<_Tp, _Tp> _Block_pair;

      unsigned int *_M_pbitmap;
      unsigned int _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 unsigned integer, which is the
	//bitmap to the first free block. Thus, the bitmaps are in exact
	//reverse order of the actual memory layout. So, we count down
	//the bimaps, 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 = __gnu_cxx::__aux_balloc::__balloc_num_bit_maps (__bp);

	assert (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) <= 
		__gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp));

	if (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) == 
	    __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp))
	  return false;

	unsigned int *__rover = reinterpret_cast<unsigned int*>(__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;
      }
    
      unsigned int *_M_get () { return _M_pbitmap; }
      unsigned int _M_offset () { return _M_data_offset * _Bits_Per_Block; }
    };
  
    //T should be a pointer type.
    template <typename _Tp, typename _Alloc>
    class _Bit_map_counter {
    
      typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector;
      typedef typename _BPVector::size_type _Index_type;
      typedef _Tp pointer;
    
      _BPVector& _M_vbp;
      unsigned int *_M_curr_bmap;
      unsigned int *_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.
      _Bit_map_counter (_BPVector& Rvbp, int __index = -1) 
	: _M_vbp(Rvbp)
      {
	this->_M_reset(__index);
      }
    
      void _M_reset (int __index = -1) throw()
      {
	if (__index == -1)
	  {
	    _M_curr_bmap = 0;
	    _M_curr_index = (_Index_type)-1;
	    return;
	  }

	_M_curr_index = __index;
	_M_curr_bmap = reinterpret_cast<unsigned int*>(_M_vbp[_M_curr_index].first) - 1;

	assert (__index <= (int)_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) / _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_bit_map (unsigned int *__new_internal_marker) throw()
      {
	_M_curr_bmap = __new_internal_marker;
      }
    
      bool _M_finished () const throw()
      {
	return (_M_curr_bmap == 0);
      }
    
      _Bit_map_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;
      }
    
      unsigned int *_M_get ()
      {
	return _M_curr_bmap;
      }
    
      pointer _M_base () { return _M_vbp[_M_curr_index].first; }
      unsigned int _M_offset ()
      {
	return _Bits_Per_Block * ((reinterpret_cast<unsigned int*>(this->_M_base()) - _M_curr_bmap) - 1);
      }
    
      unsigned int _M_where () { return _M_curr_index; }
    };
  }

  //Generic Version of the bsf instruction.
  typedef unsigned int _Bit_map_type;
  static inline unsigned int _Bit_scan_forward (register _Bit_map_type __num)
  {
    return static_cast<unsigned int>(__builtin_ctz(__num));
  }

  struct _OOM_handler {
    static std::new_handler _S_old_handler;
    static bool _S_handled_oom;
    typedef void (*_FL_clear_proc)(void);
    static _FL_clear_proc _S_oom_fcp;
    
    _OOM_handler (_FL_clear_proc __fcp)
    {
      _S_oom_fcp = __fcp;
      _S_old_handler = std::set_new_handler (_S_handle_oom_proc);
      _S_handled_oom = false;
    }

    static void _S_handle_oom_proc()
    {
      _S_oom_fcp();
      std::set_new_handler (_S_old_handler);
      _S_handled_oom = true;
    }

    ~_OOM_handler ()
    {
      if (!_S_handled_oom)
	std::set_new_handler (_S_old_handler);
    }
  };
  
  std::new_handler _OOM_handler::_S_old_handler;
  bool _OOM_handler::_S_handled_oom = false;
  _OOM_handler::_FL_clear_proc _OOM_handler::_S_oom_fcp = 0;
  

  class _BA_free_list_store {
    struct _LT_pointer_compare {
      template <typename _Tp>
      bool operator() (_Tp* __pt, _Tp const& __crt) const throw()
      {
	return *__pt < __crt;
      }
    };

#if defined __GTHREADS
    static _Mutex _S_bfl_mutex;
#endif
    static std::vector<unsigned int*> _S_free_list;
    typedef std::vector<unsigned int*>::iterator _FLIter;

    static void _S_validate_free_list(unsigned int *__addr) throw()
    {
      const unsigned int __max_size = 64;
      if (_S_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 >= *_S_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((void*)__addr);
	      return;
	    }
	  else
	    {
	      //Deallocate the last block in the list of free lists, and
	      //insert the new one in it's correct position.
	      operator delete((void*)_S_free_list.back());
	      _S_free_list.pop_back();
	    }
	}
	  
      //Just add the block to the list of free lists
      //unconditionally.
      _FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(), 
					*__addr, _LT_pointer_compare ());
      //We may insert the new free list before _temp;
      _S_free_list.insert(__temp, __addr);
    }

    static bool _S_should_i_give(unsigned int __block_size, unsigned int __required_size) throw()
    {
      const unsigned int __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:
    typedef _BA_free_list_store _BFL_type;

    static inline void _S_insert_free_list(unsigned int *__addr) throw()
    {
#if defined __GTHREADS
      _Lock __bfl_lock(&_S_bfl_mutex);
#endif
      //Call _S_validate_free_list to decide what should be done with this
      //particular free list.
      _S_validate_free_list(--__addr);
    }
    
    static unsigned int *_S_get_free_list(unsigned int __sz) throw (std::bad_alloc)
    {
#if defined __GTHREADS
      _Lock __bfl_lock(&_S_bfl_mutex);
#endif
      _FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(), 
					__sz, _LT_pointer_compare());
      if (__temp == _S_free_list.end() || !_S_should_i_give (**__temp, __sz))
	{
	  //We hold the lock because the OOM_Handler is a stateless
	  //entity.
	  _OOM_handler __set_handler(_BFL_type::_S_clear);
	  unsigned int *__ret_val = reinterpret_cast<unsigned int*>
	    (operator new (__sz + sizeof(unsigned int)));
	  *__ret_val = __sz;
	  return ++__ret_val;
	}
      else
	{
	  unsigned int* __ret_val = *__temp;
	  _S_free_list.erase (__temp);
	  return ++__ret_val;
	}
    }

    //This function just clears the internal Free List, and gives back
    //all the memory to the OS.
    static void _S_clear()
    {
#if defined __GTHREADS
      _Lock __bfl_lock(&_S_bfl_mutex);
#endif
      _FLIter __iter = _S_free_list.begin();
      while (__iter != _S_free_list.end())
	{
	  operator delete((void*)*__iter);
	  ++__iter;
	}
      _S_free_list.clear();
    }

  };

#if defined __GTHREADS
  _Mutex _BA_free_list_store::_S_bfl_mutex;
#endif
  std::vector<unsigned int*> _BA_free_list_store::_S_free_list;

  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; };
  };

  template <typename _Tp> class bitmap_allocator : private _BA_free_list_store {
  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;
    template <typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; };

  private:
    static const unsigned int _Bits_Per_Byte = 8;
    static const unsigned int _Bits_Per_Block = sizeof(unsigned int) * _Bits_Per_Byte;

    static inline void _S_bit_allocate(unsigned int *__pbmap, unsigned int __pos) throw()
    {
      unsigned int __mask = 1 << __pos;
      __mask = ~__mask;
      *__pbmap &= __mask;
    }
  
    static inline void _S_bit_free(unsigned int *__pbmap, unsigned int __pos) throw()
    {
      unsigned int __mask = 1 << __pos;
      *__pbmap |= __mask;
    }

    static inline void *_S_memory_get(size_t __sz) throw (std::bad_alloc)
    {
      return operator new(__sz);
    }

    static inline void _S_memory_put(void *__vptr) throw ()
    {
      operator delete(__vptr);
    }

    typedef typename std::pair<pointer, pointer> _Block_pair;
    typedef typename __gnu_cxx::new_allocator<_Block_pair> _BPVec_allocator_type;
    typedef typename std::vector<_Block_pair, _BPVec_allocator_type> _BPVector;


#if defined CHECK_FOR_ERRORS
    //Complexity: O(lg(N)). Where, N is the number of block of size
    //sizeof(value_type).
    static void _S_check_for_free_blocks() throw()
    {
      typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF;
      _FFF __fff;
      typedef typename _BPVector::iterator _BPiter;
      _BPiter __bpi = std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(), 
				   __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff));
      assert(__bpi == _S_mem_blocks.end());
    }
#endif


    //Complexity: O(1), but internally depends upon the complexity of
    //the function _BA_free_list_store::_S_get_free_list. The part
    //where the bitmap headers are written is of worst case complexity:
    //O(X),where X is the number of blocks of size sizeof(value_type)
    //within the newly acquired block. Having a tight bound.
    static void _S_refill_pool() throw (std::bad_alloc)
    {
#if defined CHECK_FOR_ERRORS
      _S_check_for_free_blocks();
#endif

      const unsigned int __num_bit_maps = _S_block_size / _Bits_Per_Block;
      const unsigned int __size_to_allocate = sizeof(unsigned int) + 
	_S_block_size * sizeof(value_type) + __num_bit_maps*sizeof(unsigned int);

      unsigned int *__temp = 
	reinterpret_cast<unsigned int*>(_BA_free_list_store::_S_get_free_list(__size_to_allocate));
      *__temp = 0;
      ++__temp;

      //The Header information goes at the Beginning of the Block.
      _Block_pair __bp = std::make_pair(reinterpret_cast<pointer>(__temp + __num_bit_maps), 
				       reinterpret_cast<pointer>(__temp + __num_bit_maps) 
					+ _S_block_size - 1);

      //Fill the Vector with this information.
      _S_mem_blocks.push_back(__bp);

      unsigned int __bit_mask = 0; //0 Indicates all Allocated.
      __bit_mask = ~__bit_mask; //1 Indicates all Free.

      for (unsigned int __i = 0; __i < __num_bit_maps; ++__i)
	__temp[__i] = __bit_mask;

      //On some implementations, operator new might throw bad_alloc, or
      //malloc might fail if the size passed is too large, therefore, we
      //limit the size passed to malloc or operator new.
      _S_block_size *= 2;
    }

    static _BPVector _S_mem_blocks;
    static unsigned int _S_block_size;
    static __gnu_cxx::__aux_balloc::_Bit_map_counter<pointer, _BPVec_allocator_type> _S_last_request;
    static typename _BPVector::size_type _S_last_dealloc_index;
#if defined __GTHREADS
    static _Mutex _S_mut;
#endif

    //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 the average. you
    //can consider this function to be having a complexity refrred to
    //commonly as: Amortized Constant time.
    static pointer _S_allocate_single_object()
    {
#if defined __GTHREADS
      _Lock __bit_lock(&_S_mut);
#endif

      //The algorithm is something like this: The last_requst 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 dereferenceable if _S_last_request->_M_finished() returns
      //true. This would inevitibly 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 __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF;
	  _FFF __fff;
	  typedef typename _BPVector::iterator _BPiter;
	  _BPiter __bpi = std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(), 
				      __gnu_cxx::__aux_balloc::_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.
	      unsigned int __nz_bit = _Bit_scan_forward(*__fff._M_get());
	      _S_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_val = __bpi->first + __fff._M_offset() + __nz_bit;
	      unsigned int *__puse_count = reinterpret_cast<unsigned int*>(__bpi->first) - 
		(__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(*__bpi) + 1);
	      ++(*__puse_count);
	      return __ret_val;
	    }
	  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.
      unsigned int __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
      _S_bit_allocate(_S_last_request._M_get(), __nz_bit);

      pointer __ret_val = _S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit;

      unsigned int *__puse_count = reinterpret_cast<unsigned int*>
	(_S_mem_blocks[_S_last_request._M_where()].first) - 
	(__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
      ++(*__puse_count);
      return __ret_val;
    }

    //Complexity: O(lg(N)), but the worst case is hit quite often! I
    //need to do something about this. I'll be able to work on it, only
    //when I have some solid figures from a few real apps.
    static void _S_deallocate_single_object(pointer __p) throw()
    {
#if defined __GTHREADS
      _Lock __bit_lock(&_S_mut);
#endif

      typedef typename _BPVector::iterator _Iterator;
      typedef typename _BPVector::difference_type _Difference_type;

      _Difference_type __diff;
      int __displacement;

      assert(_S_last_dealloc_index >= 0);

      if (__gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)(_S_mem_blocks[_S_last_dealloc_index]))
	{
	  assert(_S_last_dealloc_index <= _S_mem_blocks.size() - 1);

	  //Initial Assumption was correct!
	  __diff = _S_last_dealloc_index;
	  __displacement = __p - _S_mem_blocks[__diff].first;
	}
      else
	{
	  _Iterator _iter = (std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(), 
					  __gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)));
	  assert(_iter != _S_mem_blocks.end());

	  __diff = _iter - _S_mem_blocks.begin();
	  __displacement = __p - _S_mem_blocks[__diff].first;
	  _S_last_dealloc_index = __diff;
	}

      //Get the position of the iterator that has been found.
      const unsigned int __rotate = __displacement % _Bits_Per_Block;
      unsigned int *__bit_mapC = reinterpret_cast<unsigned int*>(_S_mem_blocks[__diff].first) - 1;
      __bit_mapC -= (__displacement / _Bits_Per_Block);
      
      _S_bit_free(__bit_mapC, __rotate);
      unsigned int *__puse_count = reinterpret_cast<unsigned int*>
	(_S_mem_blocks[__diff].first) - 
	(__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[__diff]) + 1);

      assert(*__puse_count != 0);

      --(*__puse_count);

      if (__builtin_expect(*__puse_count == 0, false))
	{
	  _S_block_size /= 2;
	  
	  //We may safely remove this block.
	  _Block_pair __bp = _S_mem_blocks[__diff];
	  _S_insert_free_list(__puse_count);
	  _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);

	  //We 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);
	      //	      assert(__diff >= 0);
	    }

	  //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);
	      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()
    { }

    //Complexity: O(1), but internally the complexity depends upon the
    //complexity of the function(s) _S_allocate_single_object and
    //_S_memory_get.
    pointer allocate(size_type __n)
    {
      if (__builtin_expect(__n == 1, true))
	return _S_allocate_single_object();
      else
	return reinterpret_cast<pointer>(_S_memory_get(__n * sizeof(value_type)));
    }

    //Complexity: Worst case complexity is O(N) where N is the number of
    //blocks of size sizeof(value_type) within the free lists that the
    //allocator holds. However, this worst case is hit only when the
    //user supplies a bogus argument to hint. If the hint argument is
    //sensible, then the complexity drops to O(lg(N)), and in extreme
    //cases, even drops to as low as O(1). So, if the user supplied
    //argument is good, then this function performs very well.
    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(__n == 1, true))
	_S_deallocate_single_object(__p);
      else
	_S_memory_put(__p);
    }

    pointer address(reference r) const { return &r; }
    const_pointer address(const_reference r) const { return &r; }

    size_type max_size(void) const throw() { return (size_type()-1)/sizeof(value_type); }

    void construct (pointer p, const_reference __data)
    {
      ::new(p) value_type(__data);
    }

    void destroy (pointer p)
    {
      p->~value_type();
    }

  };

  template <typename _Tp>
  typename bitmap_allocator<_Tp>::_BPVector bitmap_allocator<_Tp>::_S_mem_blocks;

  template <typename _Tp>
  unsigned int bitmap_allocator<_Tp>::_S_block_size = bitmap_allocator<_Tp>::_Bits_Per_Block;

  template <typename _Tp>
  typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type 
  bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;

  template <typename _Tp>
  __gnu_cxx::__aux_balloc::_Bit_map_counter 
  <typename bitmap_allocator<_Tp>::pointer, typename bitmap_allocator<_Tp>::_BPVec_allocator_type> 
  bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);

#if defined __GTHREADS
  template <typename _Tp>
  __gnu_cxx::_Mutex
  bitmap_allocator<_Tp>::_S_mut;
#endif

  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;
  }
}


#endif //_BITMAP_ALLOCATOR_H