stl_alloc.h

gcc3.2.1源代码

// Allocators -*- C++ -*-

// Copyright (C) 2001, 2002 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.

/*
 * Copyright (c) 1996-1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file stl_alloc.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef __GLIBCPP_INTERNAL_ALLOC_H
#define __GLIBCPP_INTERNAL_ALLOC_H

/**
 *  @defgroup Allocators Memory Allocators
 *  @if maint
 *  stl_alloc.h implements some node allocators.  These are NOT the same as
 *  allocators in the C++ standard, nor in the original H-P STL.  They do not
 *  encapsulate different pointer types; we assume that there is only one
 *  pointer type.  The C++ standard allocators are intended to allocate
 *  individual objects, not pools or arenas.
 *
 *  In this file allocators are of two different styles:  "standard" and
 *  "SGI" (quotes included).  "Standard" allocators conform to 20.4.  "SGI"
 *  allocators differ in AT LEAST the following ways (add to this list as you
 *  discover them):
 *
 *   - "Standard" allocate() takes two parameters (n_count,hint=0) but "SGI"
 *     allocate() takes one paramter (n_size).
 *   - Likewise, "standard" deallocate()'s argument is a count, but in "SGI"
 *     is a byte size.
 *   - max_size(), construct(), and destroy() are missing in "SGI" allocators.
 *   - reallocate(p,oldsz,newsz) is added in "SGI", and behaves as
 *     if p=realloc(p,newsz).
 *
 *  "SGI" allocators may be wrapped in __allocator to convert the interface
 *  into a "standard" one.
 *  @endif
 *
 *  The canonical description of these classes is in docs/html/ext/howto.html
 *  or online at http://gcc.gnu.org/onlinedocs/libstdc++/ext/howto.html#3
*/

#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <bits/functexcept.h>   // For __throw_bad_alloc
#include <bits/stl_threads.h>

namespace std
{
  /**
   *  @if maint
   *  A new-based allocator, as required by the standard.  Allocation and
   *  deallocation forward to global new and delete.  "SGI" style, minus
   *  reallocate().
   *  @endif
   *  (See @link Allocators allocators info @endlink for more.)
  */
  class __new_alloc 
  {
  public:
    static void* 
    allocate(size_t __n)
    { return ::operator new(__n); }
    
    static void 
    deallocate(void* __p, size_t)
    { ::operator delete(__p); }
  };
  

  /**
   *  @if maint
   *  A malloc-based allocator.  Typically slower than the
   *  __default_alloc_template (below).  Typically thread-safe and more
   *  storage efficient.  The template argument is unused and is only present
   *  to permit multiple instantiations (but see __default_alloc_template
   *  for caveats).  "SGI" style, plus __set_malloc_handler for OOM conditions.
   *  @endif
   *  (See @link Allocators allocators info @endlink for more.)
  */
  template <int __inst>
    class __malloc_alloc_template 
    {
    private:
      static void* _S_oom_malloc(size_t);
      static void* _S_oom_realloc(void*, size_t);
      static void (* __malloc_alloc_oom_handler)();
      
    public:
      static void* 
      allocate(size_t __n)
      {
	void* __result = malloc(__n);
	if (0 == __result) __result = _S_oom_malloc(__n);
	return __result;
      }

      static void 
      deallocate(void* __p, size_t /* __n */)
      { free(__p); }

      static void* 
      reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
      {
	void* __result = realloc(__p, __new_sz);
	if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
	return __result;
      }
      
      static void (* __set_malloc_handler(void (*__f)()))()
      {
	void (* __old)() = __malloc_alloc_oom_handler;
	__malloc_alloc_oom_handler = __f;
	return(__old);
      }
    };

  // malloc_alloc out-of-memory handling
  template <int __inst>
    void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;

  template <int __inst>
    void*
    __malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
    {
      void (* __my_malloc_handler)();
      void* __result;
      
      for (;;) 
	{
	  __my_malloc_handler = __malloc_alloc_oom_handler;
	  if (0 == __my_malloc_handler) 
	    std::__throw_bad_alloc();
	  (*__my_malloc_handler)();
	  __result = malloc(__n);
	  if (__result) 
	    return(__result);
	}
    }
  
  template <int __inst>
    void* 
    __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
    { 
      void (* __my_malloc_handler)();
      void* __result;
      
      for (;;) 
	{
	  __my_malloc_handler = __malloc_alloc_oom_handler;
	  if (0 == __my_malloc_handler) 
	    std::__throw_bad_alloc();
	  (*__my_malloc_handler)();
	  __result = realloc(__p, __n);
	  if (__result) 
	    return(__result);
	}
    }


// Determines the underlying allocator choice for the node allocator.
#ifdef __USE_MALLOC
  typedef __malloc_alloc_template<0>  __mem_interface;
#else
  typedef __new_alloc                 __mem_interface;
#endif


  /**
   *  @if maint
   *  This is used primarily (only?) in _Alloc_traits and other places to
   *  help provide the _Alloc_type typedef.
   *
   *  This is neither "standard"-conforming nor "SGI".  The _Alloc parameter
   *  must be "SGI" style.
   *  @endif
   *  (See @link Allocators allocators info @endlink for more.)
  */
  template<class _Tp, class _Alloc>
  class __simple_alloc
  {
  public:
    static _Tp* allocate(size_t __n)
    { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }

    static _Tp* allocate()
    { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }

    static void deallocate(_Tp* __p, size_t __n)
    { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }

    static void deallocate(_Tp* __p)
    { _Alloc::deallocate(__p, sizeof (_Tp)); }
  };


  /**
   *  @if maint
   *  An adaptor for an underlying allocator (_Alloc) to check the size
   *  arguments for debugging.  Errors are reported using assert; these
   *  checks can be disabled via NDEBUG, but the space penalty is still
   *  paid, therefore it is far better to just use the underlying allocator
   *  by itelf when no checking is desired.
   *
   *  "There is some evidence that this can confuse Purify." - SGI comment
   *
   *  This adaptor is "SGI" style.  The _Alloc parameter must also be "SGI".
   *  @endif
   *  (See @link Allocators allocators info @endlink for more.)
  */
  template <class _Alloc>
  class __debug_alloc
  {
  private:
    enum {_S_extra = 8};  // Size of space used to store size.  Note that this
                          // must be large enough to preserve alignment.
  
  public:
  
    static void* allocate(size_t __n)
    {
      char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
      *(size_t*)__result = __n;
      return __result + (int) _S_extra;
    }
  
    static void deallocate(void* __p, size_t __n)
    {
      char* __real_p = (char*)__p - (int) _S_extra;
      assert(*(size_t*)__real_p == __n);
      _Alloc::deallocate(__real_p, __n + (int) _S_extra);
    }
  
    static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
    {
      char* __real_p = (char*)__p - (int) _S_extra;
      assert(*(size_t*)__real_p == __old_sz);
      char* __result = (char*)
        _Alloc::reallocate(__real_p, __old_sz + (int) _S_extra,
                                     __new_sz + (int) _S_extra);
      *(size_t*)__result = __new_sz;
      return __result + (int) _S_extra;
    }
  };


#ifdef __USE_MALLOC

typedef __mem_interface __alloc;
typedef __mem_interface __single_client_alloc;

#else


/**
 *  @if maint
 *  Default node allocator.  "SGI" style.  Uses __mem_interface for its
 *  underlying requests (and makes as few requests as possible).
 *  **** Currently __mem_interface is always __new_alloc, never __malloc*.
 * 
 *  Important implementation properties:
 *  1. If the clients request an object of size > _MAX_BYTES, the resulting
 *     object will be obtained directly from the underlying __mem_interface.
 *  2. In all other cases, we allocate an object of size exactly
 *     _S_round_up(requested_size).  Thus the client has enough size
 *     information that we can return the object to the proper free list
 *     without permanently losing part of the object.
 * 
 *  The first template parameter specifies whether more than one thread may
 *  use this allocator.  It is safe to allocate an object from one instance
 *  of a default_alloc and deallocate it with another one.  This effectively
 *  transfers its ownership to the second one.  This may have undesirable
 *  effects on reference locality.
 *
 *  The second parameter is unused and serves only to allow the creation of
 *  multiple default_alloc instances.  Note that containers built on different
 *  allocator instances have different types, limiting the utility of this
 *  approach.  If you do not wish to share the free lists with the main
 *  default_alloc instance, instantiate this with a non-zero __inst.
 *
 *  @endif
 *  (See @link Allocators allocators info @endlink for more.)
*/
template<bool __threads, int __inst>
  class __default_alloc_template
  {
  private:
    enum {_ALIGN = 8};
    enum {_MAX_BYTES = 128};
    enum {_NFREELISTS = _MAX_BYTES / _ALIGN};
    
    union _Obj 
    {
      union _Obj* _M_free_list_link;
      char        _M_client_data[1];    // The client sees this.
    };

    static _Obj* volatile 	_S_free_list[_NFREELISTS]; 

    // Chunk allocation state.
    static char* 		_S_start_free;
    static char* 		_S_end_free;
    static size_t 		_S_heap_size;
    
    static _STL_mutex_lock 	_S_node_allocator_lock;

    static size_t
    _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

    static size_t 
    _S_freelist_index(size_t __bytes)
    { return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1); }

    // Returns an object of size __n, and optionally adds to size __n
    // free list.
    static void* 
    _S_refill(size_t __n);

    // Allocates a chunk for nobjs of size size.  nobjs may be reduced
    // if it is inconvenient to allocate the requested number.
    static char* 
    _S_chunk_alloc(size_t __size, int& __nobjs);
    
    // It would be nice to use _STL_auto_lock here.  But we need a
    // test whether threads are in use.
    class _Lock 
    {
    public:
      _Lock() { if (__threads) _S_node_allocator_lock._M_acquire_lock(); }
      ~_Lock() { if (__threads) _S_node_allocator_lock._M_release_lock(); }
    } __attribute__ ((__unused__));
    friend class _Lock;
    
  public:
    // __n must be > 0
    static void* 
    allocate(size_t __n)
    {
      void* __ret = 0;
      
      if (__n > (size_t) _MAX_BYTES) 
	__ret = __mem_interface::allocate(__n);
      else 
	{
	  _Obj* volatile* __my_free_list = _S_free_list 
	    + _S_freelist_index(__n);
	  // Acquire the lock here with a constructor call.  This
	  // ensures that it is released in exit or during stack
	  // unwinding.
	  _Lock __lock_instance;
	  _Obj* __restrict__ __result = *__my_free_list;
	  if (__result == 0)
	    __ret = _S_refill(_S_round_up(__n));
	  else 
	    {
	      *__my_free_list = __result -> _M_free_list_link;
	      __ret = __result;
	    }
	}
      return __ret;
    };

    // __p may not be 0
    static void 
    deallocate(void* __p, size_t __n)
    {
      if (__n > (size_t) _MAX_BYTES)
	__mem_interface::deallocate(__p, __n);
      else 
	{
	  _Obj* volatile*  __my_free_list
	    = _S_free_list + _S_freelist_index(__n);
	  _Obj* __q = (_Obj*)__p;
	  
	  // Acquire the lock here with a constructor call.  This ensures that
	  // it is released in exit or during stack unwinding.
	  _Lock __lock_instance;
	  __q -> _M_free_list_link = *__my_free_list;
	  *__my_free_list = __q;
	}
    }
    
    static void* 
    reallocate(void* __p, size_t __old_sz, size_t __new_sz);
  };


  template<bool __threads, int __inst>
    inline bool 
    operator==(const __default_alloc_template<__threads, __inst>&,
	       const __default_alloc_template<__threads, __inst>&)
    { return true; }

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


  // We allocate memory in large chunks in order to avoid fragmenting the
  // malloc heap (or whatever __mem_interface is using) too much.  We assume
  // that __size is properly aligned.  We hold the allocation lock.
  template<bool __threads, int __inst>
    char*
    __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 
								int& __nobjs)
    {
      char* __result;
      size_t __total_bytes = __size * __nobjs;
      size_t __bytes_left = _S_end_free - _S_start_free;
      
      if (__bytes_left >= __total_bytes) 
      {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
      } 
      else if (__bytes_left >= __size) 
	{
	  __nobjs = (int)(__bytes_left/__size);
	  __total_bytes = __size * __nobjs;
	  __result = _S_start_free;
	  _S_start_free += __total_bytes;
	  return(__result);
	} 
      else 
	{
	  size_t __bytes_to_get = 
	    2 * __total_bytes + _S_round_up(_S_heap_size >> 4);