stl_alloc.h

gcc3.2.1源代码

	  // Try to make use of the left-over piece.
	  if (__bytes_left > 0) 
	    {
	      _Obj* volatile* __my_free_list =
		_S_free_list + _S_freelist_index(__bytes_left);
	      
	      ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
	      *__my_free_list = (_Obj*)_S_start_free;
	    }
	  _S_start_free = (char*) __mem_interface::allocate(__bytes_to_get);
	  if (0 == _S_start_free) 
	    {
	      size_t __i;
	      _Obj* volatile* __my_free_list;
	      _Obj* __p;
	      // Try to make do with what we have.  That can't hurt.  We
	      // do not try smaller requests, since that tends to result
	      // in disaster on multi-process machines.
	      __i = __size;
	      for (; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) 
		{
		  __my_free_list = _S_free_list + _S_freelist_index(__i);
		  __p = *__my_free_list;
		  if (0 != __p) 
		    {
		      *__my_free_list = __p -> _M_free_list_link;
		      _S_start_free = (char*)__p;
		      _S_end_free = _S_start_free + __i;
		      return(_S_chunk_alloc(__size, __nobjs));
		      // Any leftover piece will eventually make it to the
		      // right free list.
		    }
		}
	      _S_end_free = 0;	// In case of exception.
	      _S_start_free = (char*)__mem_interface::allocate(__bytes_to_get);
	      // This should either throw an exception or remedy the situation.
	      // Thus we assume it succeeded.
	    }
	  _S_heap_size += __bytes_to_get;
	  _S_end_free = _S_start_free + __bytes_to_get;
	  return(_S_chunk_alloc(__size, __nobjs));
	}
    }
  
  
  // Returns an object of size __n, and optionally adds to "size
  // __n"'s free list.  We assume that __n is properly aligned.  We
  // hold the allocation lock.
  template<bool __threads, int __inst>
    void*
    __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
    {
      int __nobjs = 20;
      char* __chunk = _S_chunk_alloc(__n, __nobjs);
      _Obj* volatile* __my_free_list;
      _Obj* __result;
      _Obj* __current_obj;
      _Obj* __next_obj;
      int __i;
      
      if (1 == __nobjs) return(__chunk);
      __my_free_list = _S_free_list + _S_freelist_index(__n);
      
      /* Build free list in chunk */
      __result = (_Obj*)__chunk;
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
      for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
	  __current_obj -> _M_free_list_link = 0;
	  break;
        } else {
	  __current_obj -> _M_free_list_link = __next_obj;
        }
      }
      return(__result);
    }


  template<bool threads, int inst>
    void*
    __default_alloc_template<threads, inst>::reallocate(void* __p, 
							size_t __old_sz,
							size_t __new_sz)
    {
      void* __result;
      size_t __copy_sz;
      
      if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
        return(realloc(__p, __new_sz));
      }
      if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
      __result = allocate(__new_sz);
      __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
      memcpy(__result, __p, __copy_sz);
      deallocate(__p, __old_sz);
      return(__result);
    }
  
  template<bool __threads, int __inst>
  _STL_mutex_lock
  __default_alloc_template<__threads, __inst>::_S_node_allocator_lock
  __STL_MUTEX_INITIALIZER;
  
  template<bool __threads, int __inst>
  char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
  
  template<bool __threads, int __inst>
  char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
  
  template<bool __threads, int __inst>
  size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;
  
  template<bool __threads, int __inst>
  typename __default_alloc_template<__threads, __inst>::_Obj* volatile
  __default_alloc_template<__threads, __inst>::_S_free_list[_NFREELISTS];
  
  typedef __default_alloc_template<true, 0>    __alloc;
  typedef __default_alloc_template<false, 0>   __single_client_alloc;


#endif /* ! __USE_MALLOC */


/**
 *  This is a "standard" allocator, as per [20.4].  The private _Alloc is
 *  "SGI" style.  (See comments at the top of stl_alloc.h.)
 *
 *  The underlying allocator behaves as follows.
 *  - if __USE_MALLOC then
 *    - thread safety depends on malloc and is entirely out of our hands
 *    - __malloc_alloc_template is used for memory requests
 *  - else (the default)
 *    - __default_alloc_template is used via two typedefs
 *    - "__single_client_alloc" typedef does no locking for threads
 *    - "__alloc" typedef is threadsafe via the locks
 *    - __new_alloc is used for memory requests
 *
 *  (See @link Allocators allocators info @endlink for more.)
*/
template <class _Tp>
class allocator
{
  typedef __alloc _Alloc;          // The underlying allocator.
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 <class _Tp1> struct rebind {
    typedef allocator<_Tp1> other;
  };

  allocator() throw() {}
  allocator(const allocator&) throw() {}
  template <class _Tp1> allocator(const allocator<_Tp1>&) throw() {}
  ~allocator() throw() {}

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

  // __n is permitted to be 0.  The C++ standard says nothing about what
  // the return value is when __n == 0.
  _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 
                    : 0;
  }

  // __p is not permitted to be a null pointer.
  void deallocate(pointer __p, size_type __n)
    { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }

  size_type max_size() const throw() 
    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  void destroy(pointer __p) { __p->~_Tp(); }
};

template<>
class allocator<void> {
public:
  typedef size_t      size_type;
  typedef ptrdiff_t   difference_type;
  typedef void*       pointer;
  typedef const void* const_pointer;
  typedef void        value_type;

  template <class _Tp1> struct rebind {
    typedef allocator<_Tp1> other;
  };
};


template <class _T1, class _T2>
inline bool operator==(const allocator<_T1>&, const allocator<_T2>&) 
{
  return true;
}

template <class _T1, class _T2>
inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&)
{
  return false;
}


/**
 *  @if maint
 *  Allocator adaptor to turn an "SGI" style allocator (e.g., __alloc,
 *  __malloc_alloc_template) into a "standard" conforming allocator.  Note
 *  that this adaptor does *not* assume that all objects of the underlying
 *  alloc class are identical, nor does it assume that all of the underlying
 *  alloc's member functions are static member functions.  Note, also, that
 *  __allocator<_Tp, __alloc> is essentially the same thing as allocator<_Tp>.
 *  @endif
 *  (See @link Allocators allocators info @endlink for more.)
*/
template <class _Tp, class _Alloc>
struct __allocator
{
  _Alloc __underlying_alloc;

  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 <class _Tp1> struct rebind {
    typedef __allocator<_Tp1, _Alloc> other;
  };

  __allocator() throw() {}
  __allocator(const __allocator& __a) throw()
    : __underlying_alloc(__a.__underlying_alloc) {}
  template <class _Tp1> 
  __allocator(const __allocator<_Tp1, _Alloc>& __a) throw()
    : __underlying_alloc(__a.__underlying_alloc) {}
  ~__allocator() throw() {}

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

  // __n is permitted to be 0.
  _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 
        ? static_cast<_Tp*>(__underlying_alloc.allocate(__n * sizeof(_Tp))) 
        : 0;
  }

  // __p is not permitted to be a null pointer.
  void deallocate(pointer __p, size_type __n)
    { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }

  size_type max_size() const throw() 
    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  void destroy(pointer __p) { __p->~_Tp(); }
};

template <class _Alloc>
class __allocator<void, _Alloc> {
  typedef size_t      size_type;
  typedef ptrdiff_t   difference_type;
  typedef void*       pointer;
  typedef const void* const_pointer;
  typedef void        value_type;

  template <class _Tp1> struct rebind {
    typedef __allocator<_Tp1, _Alloc> other;
  };
};

template <class _Tp, class _Alloc>
inline bool operator==(const __allocator<_Tp, _Alloc>& __a1,
                       const __allocator<_Tp, _Alloc>& __a2)
{
  return __a1.__underlying_alloc == __a2.__underlying_alloc;
}

template <class _Tp, class _Alloc>
inline bool operator!=(const __allocator<_Tp, _Alloc>& __a1,
                       const __allocator<_Tp, _Alloc>& __a2)
{
  return __a1.__underlying_alloc != __a2.__underlying_alloc;
}


//@{
/** Comparison operators for all of the predifined SGI-style allocators.
 *  This ensures that __allocator<malloc_alloc> (for example) will work
 *  correctly.  As required, all allocators compare equal.
*/
template <int inst>
inline bool operator==(const __malloc_alloc_template<inst>&,
                       const __malloc_alloc_template<inst>&)
{
  return true;
}

template <int __inst>
inline bool operator!=(const __malloc_alloc_template<__inst>&,
                       const __malloc_alloc_template<__inst>&)
{
  return false;
}

template <class _Alloc>
inline bool operator==(const __debug_alloc<_Alloc>&,
                       const __debug_alloc<_Alloc>&) {
  return true;
}

template <class _Alloc>
inline bool operator!=(const __debug_alloc<_Alloc>&,
                       const __debug_alloc<_Alloc>&) {
  return false;
}
//@}


/**
 *  @if maint
 *  Another allocator adaptor:  _Alloc_traits.  This serves two purposes.
 *  First, make it possible to write containers that can use either "SGI"
 *  style allocators or "standard" allocators.  Second, provide a mechanism
 *  so that containers can query whether or not the allocator has distinct
 *  instances.  If not, the container can avoid wasting a word of memory to
 *  store an empty object.  For examples of use, see stl_vector.h, etc, or
 *  any of the other classes derived from this one.
 *
 *  This adaptor uses partial specialization.  The general case of
 *  _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
 *  standard-conforming allocator, possibly with non-equal instances and
 *  non-static members.  (It still behaves correctly even if _Alloc has
 *  static member and if all instances are equal.  Refinements affect
 *  performance, not correctness.)
 *
 *  There are always two members:  allocator_type, which is a standard-
 *  conforming allocator type for allocating objects of type _Tp, and
 *  _S_instanceless, a static const member of type bool.  If
 *  _S_instanceless is true, this means that there is no difference
 *  between any two instances of type allocator_type.  Furthermore, if
 *  _S_instanceless is true, then _Alloc_traits has one additional
 *  member:  _Alloc_type.  This type encapsulates allocation and
 *  deallocation of objects of type _Tp through a static interface; it
 *  has two member functions, whose signatures are
 *
 *  -  static _Tp* allocate(size_t)
 *  -  static void deallocate(_Tp*, size_t)
 *
 *  The size_t parameters are "standard" style (see top of stl_alloc.h) in
 *  that they take counts, not sizes.
 *
 *  @endif
 *  (See @link Allocators allocators info @endlink for more.)
*/
//@{
// The fully general version.
template <class _Tp, class _Allocator>
struct _Alloc_traits
{
  static const bool _S_instanceless = false;
  typedef typename _Allocator::template rebind<_Tp>::other allocator_type;
};

template <class _Tp, class _Allocator>
const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;

/// The version for the default allocator.
template <class _Tp, class _Tp1>
struct _Alloc_traits<_Tp, allocator<_Tp1> >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __alloc> _Alloc_type;
  typedef allocator<_Tp> allocator_type;
};
//@}

//@{
/// Versions for the predefined "SGI" style allocators.
template <class _Tp, int __inst>
struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
  typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
};

#ifndef __USE_MALLOC
template <class _Tp, bool __threads, int __inst>
struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __default_alloc_template<__threads, __inst> > 
          _Alloc_type;
  typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> > 
          allocator_type;
};
#endif

template <class _Tp, class _Alloc>
struct _Alloc_traits<_Tp, __debug_alloc<_Alloc> >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type;
  typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type;
};
//@}

//@{
/// Versions for the __allocator adaptor used with the predefined "SGI" style allocators.
template <class _Tp, class _Tp1, int __inst>
struct _Alloc_traits<_Tp, 
                     __allocator<_Tp1, __malloc_alloc_template<__inst> > >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
  typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
};

#ifndef __USE_MALLOC
template <class _Tp, class _Tp1, bool __thr, int __inst>
struct _Alloc_traits<_Tp, 
                      __allocator<_Tp1, 
                                  __default_alloc_template<__thr, __inst> > >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __default_alloc_template<__thr,__inst> > 
          _Alloc_type;
  typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> > 
          allocator_type;
};
#endif

template <class _Tp, class _Tp1, class _Alloc>
struct _Alloc_traits<_Tp, __allocator<_Tp1, __debug_alloc<_Alloc> > >
{
  static const bool _S_instanceless = true;
  typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type;
  typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type;
};
//@}

  // Inhibit implicit instantiations for required instantiations,
  // which are defined via explicit instantiations elsewhere.  
  // NB: This syntax is a GNU extension.
  extern template class allocator<char>;
  extern template class allocator<wchar_t>;
#ifdef __USE_MALLOC
  extern template class __malloc_alloc_template<0>;
#else
  extern template class __default_alloc_template<true, 0>;
#endif
} // namespace std

#endif /* __GLIBCPP_INTERNAL_ALLOC_H */

// Local Variables:
// mode:C++
// End: