bitmap_allocator.h

linux下编程用 编译软件

// Bitmap Allocator. -*- C++ -*-

// Copyright (C) 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// 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.

/** @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

// For std::size_t, and ptrdiff_t.
#include <cstddef>

// For __throw_bad_alloc().
#include <bits/functexcept.h>

// For std::pair.
#include <utility>

// For greater_equal, and less_equal.
#include <functional>

// For operator new.
#include <new>

// For __gthread_mutex_t, __gthread_mutex_lock and __gthread_mutex_unlock.
#include <bits/gthr.h>

// Define this to enable error checking withing the allocator
// itself(to debug the allocator itself).
//#define _BALLOC_SANITY_CHECK

/** @brief The constant in the expression below is the alignment
 * required in bytes.
 */
#define _BALLOC_ALIGN_BYTES 8

#if defined _BALLOC_SANITY_CHECK
#include <cassert>
#define _BALLOC_ASSERT(_EXPR) assert(_EXPR)
#else
#define _BALLOC_ASSERT(_EXPR)
#endif


namespace __gnu_cxx
{
#if defined __GTHREADS
  namespace
  {
    /** @brief  If true, then the application being compiled will be
     *  using threads, so use mutexes as a synchronization primitive,
     *  else do no use any synchronization primitives.
     */
    bool const __threads_enabled = __gthread_active_p();
  }
#endif

#if defined __GTHREADS
  /** @class  _Mutex bitmap_allocator.h bitmap_allocator.h
   *
   *  @brief  _Mutex is an OO-Wrapper for __gthread_mutex_t. 
   *
   *  It does not allow you to copy or assign an already initialized
   *  mutex. This is used merely as a convenience for the locking
   *  classes.
   */
  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 bitmap_allocator.h bitmap_allocator.h
   *
   *  @brief  _Lock is a simple manual locking class which allows you to
   *  manually lock and unlock a mutex associated with the lock. 
   *
   *  There is no automatic locking or unlocking happening without the
   *  programmer's explicit instructions. This class unlocks the mutex
   *  ONLY if it has not been locked. However, this check does not
   *  apply for locking, and wayward use may cause dead-locks.
   */
  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)
    { }

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

  /** @class  _Auto_Lock bitmap_allocator.h bitmap_allocator.h
   *
   *  @brief  _Auto_Lock locks the associated mutex on construction, and
   *  unlocks on destruction.
   *
   *  There are no checks performed, and this class follows the RAII
   *  principle.
   */
  class _Auto_Lock 
  {
    _Mutex* _M_pmt;
    // Prevent Copying and assignment.
    _Auto_Lock(_Auto_Lock const&);
    _Auto_Lock& operator=(_Auto_Lock const&);

    void
    _M_lock()
    {
      if (__threads_enabled)
	__gthread_mutex_lock(_M_pmt->_M_get());
    }

    void
    _M_unlock()
    {
      if (__threads_enabled)
	__gthread_mutex_unlock(_M_pmt->_M_get());
    }

  public:
    _Auto_Lock(_Mutex* __mptr) : _M_pmt(__mptr)
    { this->_M_lock(); }

    ~_Auto_Lock() { this->_M_unlock(); }
  };
#endif 

  namespace balloc
  {
    /** @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 std::size_t size_type;
	typedef std::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)
	{ }

#if 0
	~__mini_vector()
	{
	  if (this->_M_start)
	    {
	      this->deallocate(this->_M_start, this->_M_end_of_storage 
			       - this->_M_start);
	    }
	}
#endif

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