bitmap_allocator.h

mingw32.rar

    }
    
    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