stl_alloc.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

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

// Copyright (C) 2001, 2002, 2003 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
 *
 *  @note The @c reallocate member functions have been deprecated for 3.2
 *        and will be removed in 3.4.  You must define @c _GLIBCPP_DEPRECATED
 *        to make this visible in 3.2; see c++config.h.
 *
 *  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 <bits/functexcept.h>   // For __throw_bad_alloc
#include <bits/stl_threads.h>

#include <bits/atomicity.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 (__builtin_expect(__result == 0, 0))
	  __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 (__builtin_expect(__result == 0, 0))
          __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 (__builtin_expect(__my_malloc_handler == 0, 0))
            __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 (__builtin_expect(__my_malloc_handler == 0, 0))
            __throw_bad_alloc();
          (*__my_malloc_handler)();
          __result = realloc(__p, __n);
          if (__result)
            return __result;
        }
    }

  // Should not be referenced within the library anymore.
  typedef __new_alloc                 __mem_interface;

  /**
   *  @if maint
   *  This is used primarily (only?) in _Alloc_traits and other places to
   *  help provide the _Alloc_type typedef.  All it does is forward the
   *  requests after some minimal checking.
   *
   *  This is neither "standard"-conforming nor "SGI".  The _Alloc parameter
   *  must be "SGI" style.
   *  @endif
   *  (See @link Allocators allocators info @endlink for more.)
   */
  template<typename _Tp, typename _Alloc>
    class __simple_alloc
    {
    public:
      static _Tp*
      allocate(size_t __n)
      {
	_Tp* __ret = 0;
	if (__n)
	  __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)));
	return __ret;
      }
  
      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.
   *
   *  "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<typename _Alloc>
    class __debug_alloc
    {
    private:
      // Size of space used to store size.  Note that this must be
      // large enough to preserve alignment.
      enum {_S_extra = 8};

    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;
        if (*(size_t*)__real_p != __n)
	  abort();
        _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;
        if (*(size_t*)__real_p != __old_sz)
	  abort();
        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;
      }
    };


  /**
   *  @if maint
   *  Default node allocator.  "SGI" style.  Uses various allocators to
   *  fulfill underlying requests (and makes as few requests as possible
   *  when in default high-speed pool mode).
   *
   *  Important implementation properties:
   *  0. If globally mandated, then allocate objects from __new_alloc
   *  1. If the clients request an object of size > _MAX_BYTES, the resulting
   *     object will be obtained directly from __new_alloc
   *  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