/*
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1997
 * Moscow Center for SPARC Technology
 *
 * Copyright (c) 1999 
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted 
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

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


// 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 __STLPORT_CSTDDEF
#  include <cstddef>
# endif
# ifndef __STLPORT_CSTDLIB
#  include <cstdlib>
# endif
# ifndef __STLPORT_CSTRING
#  include <cstring>
# endif

# ifndef __THROW_BAD_ALLOC
#  if !defined(__STL_USE_EXCEPTIONS)
# if !defined (__STLPORT_CSTDIO)
#  include <cstdio>
# endif
# if !defined (__STLPORT_CSTDLIB)
#  include <cstdlib>
# endif
#   define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
#  else /* !defined(__STL_USE_EXCEPTIONS) */
#   define __THROW_BAD_ALLOC throw bad_alloc()
#  endif /* !defined(__STL_USE_EXCEPTIONS) */
# endif   /* __THROW_BAD_ALLOC */

# ifndef __STLPORT_NEW
#  include <new>
# endif

#if defined (__STL_THREADS) && ! defined (__SGI_STL_INTERNAL_THREADS_H)
# include <stl_threads.h>
#endif

#ifndef __TYPE_TRAITS_H
# include <type_traits.h>
#endif

#ifndef __SGI_STL_INTERNAL_CONSTRUCT_H
# include <stl_construct.h>
#endif

#ifndef __ALLOC
#   define __ALLOC __sgi_alloc
#endif

# ifndef __RESTRICT
#  define __RESTRICT
# endif

# if defined ( __STL_USE_ABBREVS )
// ugliness is intentional - to reduce conflicts probability
#  define __malloc_alloc   M__A
#  define __node_alloc     D__A
#  define __new_alloc      N__A
#  define __debug_alloc    G__A
# endif

#ifdef __STL_THREADS
# 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

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endif
#if defined(__IBMCPP__)
// supress EDC3130: A constant is being used as a conditional expression
#pragma info(nocnd)
#endif

__STL_BEGIN_NAMESPACE

template <class _Tp, class _Alloc>
struct __STLPORT_EXPORT_TEMPLATE __allocator;

// Malloc-based allocator.  Typically slower than default alloc below.
// Typically thread-safe and more storage efficient.

typedef void (* __oom_handler_type)();

template <int __inst>
class __STLPORT_EXPORT_TEMPLATE __malloc_alloc;

template <int __inst>
class __STLPORT_EXPORT_TEMPLATE __malloc_alloc {
private:

  static void* _S_oom_malloc(size_t);
  static void* _S_oom_realloc(void*, size_t);

  static __oom_handler_type __oom_handler;

public:
  // this one is needed for proper simple_alloc wrapping
  typedef char value_type;

# if defined (__STL_MEMBER_TEMPLATE_CLASSES)
  template <class _Tp1> struct rebind {
    typedef __allocator<_Tp1, __malloc_alloc<__inst> > other;
  };
# endif

  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((char*)__p);
    }
# if 0
  static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
    {
      void* __result = realloc((char*)__p, __new_sz);
      if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
      return __result;
    }
# endif
  static __oom_handler_type set_malloc_handler(__oom_handler_type __f)
    {
      __oom_handler_type __old = __oom_handler;
      __oom_handler = __f;
      return(__old);
    }
    
};


// New-based allocator.  Typically slower than default alloc below.
// Typically thread-safe and more storage efficient.
class __new_alloc {
public:
  // this one is needed for proper simple_alloc wrapping
  typedef char value_type;

# if defined (__STL_MEMBER_TEMPLATE_CLASSES)
  template <class _Tp1> struct rebind {
    typedef __allocator<_Tp1, __new_alloc > other;
  };
# endif

  static void*  allocate(size_t __n) { 
    return __stl_new(__n);
  }

# if 0
  static void*  reallocate(void *__p, size_t __old_sz, size_t __new_sz) {
    void* __result = allocate(__new_sz);
    size_t __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
    memcpy(__result, __p, __copy_sz);
    deallocate(__p, __old_sz);
    return __result;
  }
# endif
  static void deallocate(void* __p, size_t) { 
    __stl_delete(__p);
  }
};


# ifdef __STL_DEBUG_ALLOC
// 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.
// This adaptor can only be applied to raw allocators

template <class _Alloc>
class __debug_alloc : public _Alloc {
public:
  typedef _Alloc __allocator_type;
  typedef typename _Alloc::value_type value_type;
private:
  struct __alloc_header {
    size_t __magic: 16;
    size_t __type_size:16;
    __STL_UINT32_T _M_size;
  }; // that is 8 bytes for sure
  // Sunpro CC has bug on enums, so extra_before/after set explicitly
  enum { __pad=8, __magic=0xdeba, __deleted_magic = 0xdebd,
	 __shred_byte= __STL_SHRED_BYTE
  };

  enum { __extra_before = 16, __extra_after = 8 };
  // Size of space used to store size.  Note
  // that this must be large enough to preserve
  // alignment.
  static size_t __extra_before_chunk() {
    return (long)__extra_before/sizeof(value_type)+
      (size_t)((long)__extra_before%sizeof(value_type)>0);
  }
  static size_t __extra_after_chunk() {
    return (long)__extra_before/sizeof(value_type)+
      (size_t)((long)__extra_after%sizeof(value_type)>0);
  }
public:

# if defined (__STL_MEMBER_TEMPLATE_CLASSES)
  template <class _Tp1> struct rebind {
    typedef __allocator< _Tp1, __debug_alloc<_Alloc> > other;
  };
# endif

  __debug_alloc(const _Alloc&);
  __debug_alloc() {}
  ~__debug_alloc() {}
  static void * allocate(size_t);
  static void   deallocate(void *, size_t);
# if 0
  static void * reallocate(void *, size_t, size_t); 
# endif
};

# endif /* __STL_DEBUG_ALLOC */


// 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(__OS400__)
enum {_ALIGN = 16, _ALIGN_SHIFT=4, _MAX_BYTES = 256};
#  define  _NFREELISTS 16
# else
enum {_ALIGN = 8, _ALIGN_SHIFT=3, _MAX_BYTES = 128};
// SunPro CC 4.0.1 has bug on enums
//  enum {_NFREELISTS = _MAX_BYTES/_ALIGN};
#  define  _NFREELISTS 16
# endif /* __OS400__ */

#define _S_FREELIST_INDEX(__bytes) ((__bytes-size_t(1))>>(int)_ALIGN_SHIFT)

union _Node_alloc_obj;

union _Node_alloc_obj {
  union _Node_alloc_obj * _M_free_list_link;
  char __M_client_data[1];    /* The client sees this.        */
};

template <bool __threads, int __inst>
class __STLPORT_EXPORT_TEMPLATE __node_alloc {
  __PRIVATE:
  static size_t
  _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t)_ALIGN-1) & ~((size_t)_ALIGN - 1)); }

  typedef _Node_alloc_obj _Obj;
private:
  static _Obj * __STL_VOLATILE _S_free_list[_NFREELISTS]; 
  static  inline size_t _S_freelist_index(size_t __bytes) {