/* * 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. *//* NOTE: This is an internal header file, included by other STL headers. *   You should not attempt to use it directly. */#ifndef __SGI_STL_INTERNAL_ALLOC_H#define __SGI_STL_INTERNAL_ALLOC_H#ifdef __SUNPRO_CC#  define __PRIVATE public   // Extra access restrictions prevent us from really making some things   // private.#else#  define __PRIVATE private#endif#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG#  define __USE_MALLOC#endif// This implements some standard node allocators.  These are// NOT the same as the allocators in the C++ draft standard or in// in the original STL.  They do not encapsulate different pointer// types; indeed we assume that there is only one pointer type.// The allocation primitives are intended to allocate individual objects,// not larger arenas as with the original STL allocators.#ifndef __THROW_BAD_ALLOC#  if defined(__STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS)#    include <stdio.h>#    include <stdlib.h>#    define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)#  else /* Standard conforming out-of-memory handling */#    include <new>#    define __THROW_BAD_ALLOC throw std::bad_alloc()#  endif#endif#include <stddef.h>#include <stdlib.h>#include <string.h>#include <assert.h>#ifndef __RESTRICT#  define __RESTRICT#endif#ifdef __STL_THREADS# include <stl_threads.h># define __NODE_ALLOCATOR_THREADS true# ifdef __STL_SGI_THREADS  // We test whether threads are in use before locking.  // Perhaps this should be moved into stl_threads.h, but that  // probably makes it harder to avoid the procedure call when  // it isn't needed.    extern "C" {      extern int __us_rsthread_malloc;    }	// The above is copied from malloc.h.  Including <malloc.h>	// would be cleaner but fails with certain levels of standard	// conformance.#   define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \                { _S_node_allocator_lock._M_acquire_lock(); }#   define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \                { _S_node_allocator_lock._M_release_lock(); }# else /* !__STL_SGI_THREADS */#   define __NODE_ALLOCATOR_LOCK \        { if (threads) _S_node_allocator_lock._M_acquire_lock(); }#   define __NODE_ALLOCATOR_UNLOCK \        { if (threads) _S_node_allocator_lock._M_release_lock(); }# endif#else//  Thread-unsafe#   define __NODE_ALLOCATOR_LOCK#   define __NODE_ALLOCATOR_UNLOCK#   define __NODE_ALLOCATOR_THREADS false#endif__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)#pragma set woff 1174#endif// Malloc-based allocator.  Typically slower than default alloc below.// Typically thread-safe and more storage efficient.#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG# ifdef __DECLARE_GLOBALS_HERE    void (* __malloc_alloc_oom_handler)() = 0;    // g++ 2.7.2 does not handle static template data members.# else    extern void (* __malloc_alloc_oom_handler)();# endif#endiftemplate <int __inst>class __malloc_alloc_template {private:  static void* _S_oom_malloc(size_t);  static void* _S_oom_realloc(void*, size_t);#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG  static void (* __malloc_alloc_oom_handler)();#endifpublic:  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#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUGtemplate <int __inst>void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;#endiftemplate <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) { __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) { __THROW_BAD_ALLOC; }        (*__my_malloc_handler)();        __result = realloc(__p, __n);        if (__result) return(__result);    }}typedef __malloc_alloc_template<0> malloc_alloc;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(void)      { 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)); }};// Allocator adaptor to check size arguments for debugging.// Reports errors using assert.  Checking can be disabled with// NDEBUG, but it's far better to just use the underlying allocator// instead when no checking is desired.// There is some evidence that this can confuse Purify.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_MALLOCtypedef malloc_alloc alloc;typedef malloc_alloc single_client_alloc;# else// Default node allocator.// With a reasonable compiler, this should be roughly as fast as the// original STL class-specific allocators, but with less fragmentation.// Default_alloc_template parameters are experimental and MAY// DISAPPEAR in the future.  Clients should just use alloc for now.//// Important implementation properties:// 1. If the client request an object of size > _MAX_BYTES, the resulting//    object will be obtained directly from malloc.// 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 unreferenced and serves only to allow the// creation of multiple default_alloc instances.// Node that containers built on different allocator instances have// different types, limiting the utility of this approach.#if defined(__SUNPRO_CC) || defined(__GNUC__)// breaks if we make these template class members:  enum {_ALIGN = 8};  enum {_MAX_BYTES = 128};  enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN#endiftemplate <bool threads, int inst>class __default_alloc_template {private:  // Really we should use static const int x = N  // instead of enum { x = N }, but few compilers accept the former.#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))    enum {_ALIGN = 8};    enum {_MAX_BYTES = 128};    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN# endif  static size_t  _S_round_up(size_t __bytes)     { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }__PRIVATE:  union _Obj {        union _Obj* _M_free_list_link;        char _M_client_data[1];    /* The client sees this.        */  };private:# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)    static _Obj* __STL_VOLATILE _S_free_list[];         // Specifying a size results in duplicate def for 4.1# else    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; # endif  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);  // Chunk allocation state.  static char* _S_start_free;  static char* _S_end_free;  static size_t _S_heap_size;# ifdef __STL_THREADS    static _STL_mutex_lock _S_node_allocator_lock;# endif    // It would be nice to use _STL_auto_lock here.  But we    // don't need the NULL check.  And we do need a test whether    // threads have actually been started.    class _Lock;    friend class _Lock;    class _Lock {        public:            _Lock() { __NODE_ALLOCATOR_LOCK; }            ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }    };public:  /* __n must be > 0      */  static void* allocate(size_t __n)  {    void* __ret = 0;    if (__n > (size_t) _MAX_BYTES) {      __ret = malloc_alloc::allocate(__n);    }    else {      _Obj* __STL_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.#     ifndef _NOTHREADS      /*REFERENCED*/      _Lock __lock_instance;#     endif      _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)      malloc_alloc::deallocate(__p, __n);    else {      _Obj* __STL_VOLATILE*  __my_free_list          = _S_free_list + _S_freelist_index(__n);      _Obj* __q = (_Obj*)__p;      // acquire lock#       ifndef _NOTHREADS      /*REFERENCED*/      _Lock __lock_instance;#       endif /* _NOTHREADS */      __q -> _M_free_list_link = *__my_free_list;      *__my_free_list = __q;      // lock is released here    }  }  static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);} ;typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;typedef __default_alloc_template<false, 0> single_client_alloc;template <bool __threads, int __inst>inline bool operator==(const __default_alloc_template<__threads, __inst>&,                       const __default_alloc_template<__threads, __inst>&){  return true;}# ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDERtemplate <bool __threads, int __inst>inline bool operator!=(const __default_alloc_template<__threads, __inst>&,                       const __default_alloc_template<__threads, __inst>&){  return false;}# endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER *//* We allocate memory in large chunks in order to avoid fragmenting     *//* the malloc heap 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);        // Try to make use of the left-over piece.