template <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)();

#endif

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);

  }

};

#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

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG

template <int __inst>

void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;

#endif

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) { __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);

    }

}

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;

  }

};

// This implements allocators as specified in the C++ standard. 

//

// Note that standard-conforming allocators use many language features

// that are not yet widely implemented.  In particular, they rely on

// member templates, partial specialization, partial ordering of function

// templates, the typename keyword, and the use of the template keyword

// to refer to a template member of a dependent type.

#ifdef __STL_USE_STD_ALLOCATORS

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() __STL_NOTHROW {}

  allocator(const allocator&) __STL_NOTHROW {}

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

  ~allocator() __STL_NOTHROW {}

  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 __STL_NOTHROW

    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }

  void destroy(pointer __p) { __p->~_Tp(); }

};