// -*- C++ -*-
#ifndef __STD_MEMORY 
#define __STD_MEMORY

/***************************************************************************
 *
 * memory - declarations for the Standard Library memory implementation
 *
 ***************************************************************************
 *    
 *  Copyright 2000 Compaq Computer Corporation
 *
 *  COMPAQ Registered in U.S. Patent and Trademark Office.
 *
 *  Confidential computer software. Valid license from Compaq required for
 *  possession, use or copying. Consistent with FAR 12.211 and 12.212,
 *  Commercial Computer Software, Computer Software Documentation, and
 *  Technical Data for Commercial Items are licensed to the U.S. Government
 *  under vendor's standard commercial license.
 *
 ****************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * 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.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/ 

#include <stdcomp>

#ifndef _RWSTD_NO_NEW_HEADER
#include <cstddef>
#include <cstdlib>
#include <cstdio>
#include <climits>
#else
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#endif //_RWSTD_NO_NEW_HEADER

#include <new>
#include <iterator>
#include <utility>
#include <rwstderr>

#ifdef _RWSTD_MULTI_THREAD
#include <stdmutex>
#endif

//
// Turn off the warnings under the MSVC compiler that
// say 'bool reserved for future use' and turn off warnings
// that say 'debug information truncated to 256 characters'
//
#ifdef _RWSTD_MSVC_BOOL_WARNING
#pragma warning ( disable : 4237 )
#endif
#if defined(_MSC_VER) && !defined(__BORLANDC__)
#pragma warning ( disable : 4786 )
#endif

#ifdef _RWSTD_NO_NEW_DECL
extern void _RWSTDExportFunc(*) operator new(size_t size, void* ptr);
#endif

#ifdef _RWSTD_NO_NEW_HEADER
#include <exception>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __cxx_header_defaults
#   endif
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#pragma __extern_prefix __save
#pragma __extern_prefix "CXXL$" 
#endif


#ifndef _RWSTD_NO_NAMESPACE
namespace _RWrwstd {
#endif

//
// Template used for empty base optimization
//
  template <class T , class Base>
  class _RWrw_basis : public Base
  {
    T _RWdata_;
  public:
    _RWrw_basis(const _RWrw_basis& b) : _RWdata_(b._RWdata_) {;}
    _RWrw_basis(const T& t, const Base& b) : Base(b), _RWdata_(t) {;}
    _RWrw_basis(int t, const Base& b) : Base(b), _RWdata_((T)t) {;}   // TEMP
    _RWrw_basis operator=(const T& t) { _RWdata_ = t; return *this; }
    _RWrw_basis operator=(int t) { _RWdata_ = (T)t; return *this; }   // TEMP
    _RWrw_basis operator=(const _RWrw_basis& r) 
    { _RWdata_ = r._RWdata_; return *this; }
    _RWrw_basis operator=(const Base& b) 
    { *this = _RWrw_basis<T,Base>(_RWdata_,b); return *this; }
    operator T() { return _RWdata_; }
    T data() const { return _RWdata_; }
  };

// Default buffer size for containers.    
#ifndef _RWSTD_CONTAINER_BUFFER_SIZE 
#define _RWSTD_CONTAINER_BUFFER_SIZE 1024
#endif

#ifndef _RWSTD_VECTOR_CONST_ENLARGE
  // Double buffer size every time new space is needed
  // This is the standard compliant method, resulting
  // in a linear increase in execution time for
  // individual additions to a container.
  // if _RWn is zero then  get initial buffer size from
  // _RWSTD_CONTAINER_BUFFER_SIZE.  Only vector calls 
  // this function with a non-zero value for cursize.  
  // Return new buffer size in bytes.
  // Third parameter not used.
  template <class T, class size>
  inline size _RWrw_allocation_size(T*,size cursize, size)
  {
    if (cursize) 
      return cursize*2;
    else
#if defined(__DECCXX) && !defined(__DECFIXCXXL1459)
      return (_RWSTD_CONTAINER_BUFFER_SIZE)*(1+((sizeof(T)-1)/_RWSTD_CONTAINER_BUFFER_SIZE)) / sizeof(T);
#else
#if defined(__DECCXX) && !defined(__DECFIXCXXL1077)
      return _RWSTD_CONTAINER_BUFFER_SIZE/sizeof(T);
#else
      return _RWSTD_CONTAINER_BUFFER_SIZE*sizeof(T);
#endif
#endif
  }
#else
  // Increment the buffer size by a set amount
  // indicated by _RWdelta (if _RWdelta is 0 then
  // get delta size from _RWSTD_CONTAINER_BUFFER_SIZE 
  // if _RWn is zero then  get initial buffer size from
  // _RWSTD_CONTAINER_BUFFER_SIZE.  Only vector calls 
  // this function with a non-zero value for cursize.  
  // Return new buffer size in bytes.
  template <class T, class size>
  inline size _RWrw_allocation_size(T*,size _RWn, size _RWdelta)
  {
    if (_RWn) 
      return _RWn + (_RWdelta ? 
#if defined(__DECCXX) && !defined(__DECFIXCXXL1459)
             _RWdelta : (_RWSTD_CONTAINER_BUFFER_SIZE)*(1+((sizeof(T)-1)/_RWSTD_CONTAINER_BUFFER_SIZE)) / sizeof(T));
#else
#if defined(__DECCXX) && !defined(__DECFIXCXXL1077)
             _RWdelta : _RWSTD_CONTAINER_BUFFER_SIZE/sizeof(T));
#else
             _RWdelta : _RWSTD_CONTAINER_BUFFER_SIZE*sizeof(T));
#endif
#endif
    else
#if defined(__DECCXX) && !defined(__DECFIXCXXL1459)
      return (_RWSTD_CONTAINER_BUFFER_SIZE)*(1+((sizeof(T)-1)/_RWSTD_CONTAINER_BUFFER_SIZE)) / sizeof(T);
#else
#if defined(__DECCXX) && !defined(__DECFIXCXXL1077)
      return _RWSTD_CONTAINER_BUFFER_SIZE/sizeof(T);
#else
      return _RWSTD_CONTAINER_BUFFER_SIZE*sizeof(T);
#endif
#endif
  }
#endif // _RWSTD_CONTAINER_CONST_ENLARGE



#if defined(_RWSTD_NO_DESTROY_NONBUILTIN)
  template <class T> struct __FS : public T
  {
    __FS() { ; }
    //
    // Calls destructor, but does not free the space.
    //
    void operator delete (void*) {;} 
  };
#endif // _RWSTD_NO_DESTROY_NONBUILTIN


#ifdef __TURBOC__
#pragma option -w-inl
#pragma option -w-par
#endif

  template <class T>
  inline void _RWdestroy (T* pointer)
  {
#if defined(_RWSTD_NO_DESTROY_NONBUILTIN)
    delete (__FS<T>*) (pointer);
#else
#if defined(_RWSTD_EXPLICIT_SCOPE_DESTROY)
    pointer->T::~T();
#else
    pointer->~T();
#endif // _RWSTD_EXPLICIT_SCOPE_DESTROY
#endif // _RWSTD_NO_DESTROY_NONBUILTIN
  }


#if defined(__DECCXX)
#pragma message disable uninit
#endif

  template <class T1, class T2>
  inline void _RWconstruct (T1* p, const T2& value)
  {
    new (p) T1(value);
  }

#if defined(__DECCXX)
#pragma message enable uninit
#endif

  template <class ForwardIterator> 
  _RWSTD_TRICKY_INLINE void _RWdestroy (ForwardIterator first, ForwardIterator last)
  {
    while (first != last)
      ++first;
  }


#if defined(_RWSTD_NO_DESTROY_BUILTIN) || defined(_RWSTD_NO_DESTROY_NONBUILTIN)
//
// Some specializations of STL destroy for builtin types.f
//
  inline void _RWdestroy (void*)             {;}
  inline void _RWdestroy (char*)             {;}
  inline void _RWdestroy (unsigned char*)    {;}
  inline void _RWdestroy (short*)            {;}
  inline void _RWdestroy (unsigned short*)   {;}
  inline void _RWdestroy (int*)              {;}
  inline void _RWdestroy (unsigned int*)     {;}
  inline void _RWdestroy (long*)             {;}
  inline void _RWdestroy (unsigned long*)    {;}
#if defined(__DECCXX) && !(defined(__STD_STRICT_ANSI) || defined(__STD_STRICT_ANSI_ERRORS)) && !defined(__DECFIXCXXL634)
  inline void _RWdestroy (long long*)             {;}
  inline void _RWdestroy (unsigned long long*)    {;}
#endif
  inline void _RWdestroy (float*)            {;}
  inline void _RWdestroy (double*)           {;}
  inline void _RWdestroy (void**)            {;}
  inline void _RWdestroy (char**)            {;}
  inline void _RWdestroy (unsigned char**)   {;}
  inline void _RWdestroy (short**)           {;}
  inline void _RWdestroy (unsigned short**)  {;}
  inline void _RWdestroy (int**)             {;}
  inline void _RWdestroy (unsigned int**)    {;}
  inline void _RWdestroy (long**)            {;}
  inline void _RWdestroy (unsigned long**)   {;}
#if defined(__DECCXX) && !(defined(__STD_STRICT_ANSI) || defined(__STD_STRICT_ANSI_ERRORS)) && !defined(__DECFIXCXXL634)
  inline void _RWdestroy (long long**)            {;}
  inline void _RWdestroy (unsigned long long**)   {;}
#endif
  inline void _RWdestroy (float**)           {;}
  inline void _RWdestroy (double**)          {;}
  inline void _RWdestroy (void***)           {;}
  inline void _RWdestroy (char***)           {;}
  inline void _RWdestroy (unsigned char***)  {;}
  inline void _RWdestroy (short***)          {;}
  inline void _RWdestroy (unsigned short***) {;}
  inline void _RWdestroy (int***)            {;}
  inline void _RWdestroy (unsigned int***)   {;}
  inline void _RWdestroy (long***)           {;}
  inline void _RWdestroy (unsigned long***)  {;}
#if defined(__DECCXX) && !(defined(__STD_STRICT_ANSI) || defined(__STD_STRICT_ANSI_ERRORS)) && !defined(__DECFIXCXXL634)
  inline void _RWdestroy (long long***)           {;}
  inline void _RWdestroy (unsigned long long***)  {;}
#endif
  inline void _RWdestroy (float***)          {;}
  inline void _RWdestroy (double***)         {;}
#ifndef _RWSTD_NO_BOOL
  inline void _RWdestroy (bool*)             {;}
  inline void _RWdestroy (bool**)            {;}
  inline void _RWdestroy (bool***)           {;}
#endif
#ifndef _RWSTD_NO_LONGDOUBLE
  inline void _RWdestroy (long double*)      {;}
  inline void _RWdestroy (long double**)     {;}
  inline void _RWdestroy (long double***)    {;}
#endif 
#ifndef _RWSTD_NO_OVERLOAD_WCHAR
  inline void _RWdestroy (wchar_t*)          {;}
  inline void _RWdestroy (wchar_t**)         {;}
  inline void _RWdestroy (wchar_t***)        {;}
#endif
#endif /*_RWSTD_NO_DESTROY_BUILTIN || _RWSTD_NO_DESTROY_NONBUILTIN*/

#ifdef _RWSTD_LOCALIZED_ERRORS
  extern const unsigned int _RWSTDExport rwse_OutOfRange;
#else
  extern const char _RWSTDExportFunc(*) rwse_OutOfRange;
#endif // _RWSTD_LOCALIZED_ERRORS

#ifndef _RWSTD_NO_NAMESPACE
} // _RWrwstd namespace

namespace std {
#endif

//
// The default allocator.
//


#ifdef _RWSTD_ALLOCATOR

  template <class T> class allocator;

//
// void specialization of allocator
//
  _RWSTD_TEMPLATE
  class allocator<void> {  
  public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    typedef void        value_type;
   
    template <class U> 
    struct rebind { typedef allocator<U> other; };
    
#ifndef _RWSTD_NO_MULTI_DIM_ARRAY
    ~allocator()  _RWSTD_THROW_SPEC_NULL
    { ; }
#endif

  };


  template <class T>
  class allocator
  {
  public:
    typedef size_t     size_type;
    typedef ptrdiff_t  difference_type;
    typedef T*         pointer;
    typedef const T*   const_pointer;
    typedef T&         reference;
    typedef const T&   const_reference;
    typedef T          value_type;

    template <class U> struct rebind
    { typedef allocator<U> other; };

    allocator()  _RWSTD_THROW_SPEC_NULL
    { ; }

    allocator(const allocator&)  _RWSTD_THROW_SPEC_NULL
    { ; }

    template <class U>
    allocator(const allocator<U>&)  _RWSTD_THROW_SPEC_NULL
    { ; }

    template <class U>
    allocator<T>& operator=(const allocator<U>& a)  _RWSTD_THROW_SPEC_NULL
    { return *this; }
    
#ifndef _RWSTD_NO_MULTI_DIM_ARRAY
    ~allocator()  _RWSTD_THROW_SPEC_NULL
    { ; }
#endif

    pointer address(reference x) const
    { 
      return _RWSTD_STATIC_CAST(pointer,&x); 
    }
    const_pointer address(const_reference x) const
    { 
      return _RWSTD_STATIC_CAST(const_pointer,&x); 
    }

#if defined(__DECCXX) && !defined(__DECFIXCXXL949)
    pointer allocate(size_type n, allocator<void>::const_pointer = 0)
#else
    pointer allocate(size_type n, allocator<void>::const_pointer hint = 0)
#endif
    { 
      pointer tmp =
      _RWSTD_STATIC_CAST(pointer,(::operator 
                                  new(_RWSTD_STATIC_CAST(size_t,(n * sizeof(value_type))))));
      _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
      return tmp;
    }

    void deallocate(pointer p, size_type) 
    { 
#if defined(__DECCXX) && !defined(__DECFIXCXXL1657)
      if ( p )
#endif
      ::operator delete(p);
    }
    size_type max_size() const  _RWSTD_THROW_SPEC_NULL
    { 
#if defined(__DECCXX) && !defined(__DECFIXCXXL1079)
      return 1 > UINT_MAX/sizeof(T) ? size_type(1) : size_type(UINT_MAX/sizeof(T
));
#else
      return max(size_type(1), size_type(UINT_MAX/sizeof(T)));
#endif
    }
    inline void construct(pointer p, const T& val);

    inline void destroy(T* p);

  };



  template <class T>
  void allocator<T>::construct(pointer p, const T& val)
  {
    __RWSTD::_RWconstruct(p,val);
  }

  template <class T>
  void allocator<T>::destroy(T* p)
  {
     __RWSTD::_RWdestroy(p);
  }

#else

//
// Alternate allocator uses an interface class (allocator_interface)
// to get type safety.
//
  template <class T>
  class allocator
  { 
  public:
   
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*         pointer;
    typedef const T*   const_pointer;
    typedef T&         reference;
    typedef const T&   const_reference;
    typedef T          value_type;

    allocator()  _RWSTD_THROW_SPEC_NULL { ; }
    allocator(const allocator<T>&)  _RWSTD_THROW_SPEC_NULL
    { ; }
    allocator<T>& operator=(const allocator<T>&)  _RWSTD_THROW_SPEC_NULL
    { return *this; }

#ifndef _RWSTD_NO_MULTI_DIM_ARRAY
    ~allocator()  _RWSTD_THROW_SPEC_NULL { ; }
#endif

    void * allocate (size_type n, void *  = 0)
    { 
      void * tmp = _RWSTD_STATIC_CAST(void*,(::operator new(_RWSTD_STATIC_CAST(size_t,(n)))));
      _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
      return tmp;
    }
    
    void deallocate (void* p, size_type) 
    { 
      ::operator delete(p);
    }
    size_type max_size (size_type size) const
    { 
      return 1 > UINT_MAX/size ? size_type(1) : size_type(UINT_MAX/size);
    }
  };

  _RWSTD_TEMPLATE
  class allocator<void>
  { 
  public:
   
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef void*         pointer;
    typedef const void*   const_pointer;
    typedef void          value_type;

    allocator() _RWSTD_THROW_SPEC_NULL { ; }
    allocator(const allocator<void>&)  _RWSTD_THROW_SPEC_NULL
    { ; }
    allocator<void>& operator=(const allocator<void>&)  _RWSTD_THROW_SPEC_NULL
    { return *this; }
#ifndef _RWSTD_NO_MULTI_DIM_ARRAY
    ~allocator() _RWSTD_THROW_SPEC_NULL { ; }
#endif

    void * allocate (size_type n, void *  = 0)
    { 
      void * tmp = _RWSTD_STATIC_CAST(void*,(::operator new(_RWSTD_STATIC_CAST(size_t,(n)))));
      _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
      return tmp;
    }
    
    void deallocate (void* p, size_type) 
    { 
      ::operator delete(p);
    }
    size_type max_size (size_type size) const
    { 
      return 1 > UINT_MAX/size ? size_type(1) : size_type(UINT_MAX/size);
    }
  };

//
// allocator_interface provides all types and typed functions.  Memory
// allocated as raw bytes using the class provided by the Allocator
// template parameter.  allocator_interface casts appropriately.
//
// Multiple allocator_interface objects can attach to a single 
// allocator, thus allowing one allocator to allocate all storage
// for a container, regardless of how many types are involved.
//
// The only real restriction is that pointer and reference are
// hard coded as T* and T&.  Partial specialization would 
// get around this.
//
  template <class Allocator,class T>
  class allocator_interface 
  {
  public:
    typedef Allocator allocator_type;
    typedef T*         pointer;
    typedef const T*   const_pointer;      
    typedef T&         reference;
    typedef const T&   const_reference;
    typedef T          value_type;
    typedef _TYPENAME _RWSTD_ALLOC_SIZE_TYPE             size_type;
    typedef _TYPENAME _RWSTD_ALLOC_DIFF_TYPE             difference_type;
    typedef void*      void_pointer;
    typedef const void* const_void_pointer;



  protected:
    allocator_type         alloc_;

  public:
    allocator_interface()  _RWSTD_THROW_SPEC_NULL  { ; }
    allocator_interface(const Allocator& a)  _RWSTD_THROW_SPEC_NULL
    : alloc_(a) { ; }

    pointer address (T& x) 
    { 
      return _RWSTD_STATIC_CAST(pointer,&x); 
    }
  
    size_type max_size ()  const
    { 
      return alloc_.max_size(sizeof(T));
    }

    pointer allocate(size_type n, pointer p  = 0)
    {
      return _RWSTD_STATIC_CAST(pointer,alloc_.allocate(n*sizeof(T),p));
    }

    void deallocate(pointer p, size_type n)
    {
      alloc_.deallocate(p,n);
    }

    inline void construct(pointer p, const T& val);

    inline void destroy(T* p);

  };


  template <class Allocator, class T>
  inline void 
  allocator_interface<Allocator,T>::construct(pointer p, const T& val)
  {
     __RWSTD::_RWconstruct(p,val);
  }

  template <class Allocator, class T>
  inline void allocator_interface<Allocator,T>::destroy(T* p)
  {
     __RWSTD::_RWdestroy(p);
  }

  _RWSTD_TEMPLATE
  class allocator_interface<allocator<void>,void> 
  {
  public:
    typedef allocator<void> allocator_type;
    typedef void*         pointer;
    typedef const void*   const_pointer;      
    typedef void          value_type;
    typedef allocator<void>::size_type       size_type;
    typedef allocator<void>::difference_type difference_type;

  protected:
    allocator_type         alloc_;

  public:
    allocator_interface()  _RWSTD_THROW_SPEC_NULL { ; }
    allocator_interface(const allocator<void>& a) _RWSTD_THROW_SPEC_NULL
    : alloc_(a) { ; }

    size_type max_size ()  const
    { 
      return alloc_.max_size(1);
    }

    pointer allocate(size_type n, pointer  = 0)
    {
      return _RWSTD_STATIC_CAST(pointer,alloc_.allocate(n));
    }

    void deallocate(pointer p, size_type n)
    {
      alloc_.deallocate(p,n);
    }      
  };

#endif  // _RWSTD_ALLOCATOR

// 
// Allocator globals
//
  template <class T, class U>
  inline bool operator==(const allocator<T>&, const allocator<U>&)  _RWSTD_THROW_SPEC_NULL
  {
    return true;
  }

#ifndef _RWSTD_NO_NAMESPACE
  template <class T, class U>
  inline bool operator!=(const allocator<T>&, const allocator<U>&)  _RWSTD_THROW_SPEC_NULL
  {
    return false;
  }
#endif

//
// Raw storage iterator.
//

  template <class OutputIterator, class T>
  class raw_storage_iterator
#if defined(__DECCXX) && !defined(__DECFIXCXXL1201)
    : public iterator<output_iterator_tag,void,void,void,void>
#else
    : public iterator<output_iterator_tag,T,ptrdiff_t,T*,T&>
#endif
  {
  protected:
    OutputIterator iter;

  public:
    typedef OutputIterator iterator_type;
    typedef T element_type;

    _EXPLICIT raw_storage_iterator (OutputIterator x) : iter(x) {}
    raw_storage_iterator<OutputIterator, T>& operator* () { return *this; }
    raw_storage_iterator<OutputIterator, T>& operator= (const T& element)
    {
#if defined(__DECCXX) && !defined(__DECFIXCXXL1284)
       ::new(&(*iter)) T(element);
#else
       *iter = element;
#endif
      return *this;
    }
    raw_storage_iterator<OutputIterator, T>& operator++ ()
    {
      ++iter; return *this;
    }
    raw_storage_iterator<OutputIterator, T> operator++ (int)
    {
      raw_storage_iterator<OutputIterator, T> tmp = *this;
      ++iter;
      return tmp;
    }
  };


//
// Temporary buffers
//

#if defined(_RWSTD_FAST_TEMP_BUF) && !defined(__DEC_DYN_ALLOC) && !defined(__DECFIXCXXL1114)

#if defined(_RWSTD_SHARED_LIB) && !defined (_RWSTD_MULTI_THREAD)
#error Cannot use fast temporary buffer in this configuration
#endif
#if defined(_RWSTDDLL) && defined (__WIN16__)
#error Cannot use fast temporary buffer in this configuration
#endif

#ifndef _RWstl_buffer_size
#define _RWstl_buffer_size 16384  /* 16k */
#endif

#ifndef _RWSTD_NO_NAMESPACE
}

namespace _RWrwstd {
#endif

  extern char _RWSTDExport stl_temp_buffer[_RWstl_buffer_size];

#ifdef _RWSTD_MULTI_THREAD
  extern _RWSTDMutex _RWSTDExport stl_temp_buffer_mutex;
  extern bool       _RWSTDExport stl_temp_buffer_being_used;
#endif

#ifndef _RWSTD_NO_NAMESPACE
} // End of _RWrwstd namespace

namespace std {
#endif

  template <class T>
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  inline pair<T*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len)
#else
  inline pair<T*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len, T*)
#endif
  {
    while (len > _RWstl_buffer_size / sizeof(T))
    {
      T* tmp = _RWSTD_STATIC_CAST(T*,( ::operator new(_RWSTD_STATIC_CAST(unsigned int,len) * sizeof(T))));
      if (tmp)
      {
        pair<T*, ptrdiff_t> result(tmp, len);
        return result;
      }
      len = len / 2;
    }
    
#ifdef _RWSTD_MULTI_THREAD
    _RWSTDGuard guard(__RWSTD::stl_temp_buffer_mutex);

    if (__RWSTD::stl_temp_buffer_being_used)
    {
      T* tmp = _RWSTD_STATIC_CAST(T*,(   ::operator new(_RWSTD_STATIC_CAST(unsigned int,len) * sizeof(T))));
      pair<T*,ptrdiff_t> result(tmp, len);
      return result;
    }
    else
    {
      __RWSTD::stl_temp_buffer_being_used = true;
      pair<T*, ptrdiff_t> result(_RWSTD_STATIC_CAST(T*,
                                 _RWSTD_STATIC_CAST(void*,__RWSTD::stl_temp_buffer)), 
                                 _RWSTD_STATIC_CAST(ptrdiff_t,(_RWstl_buffer_size / sizeof(T))));
      return result;
    }
#else
    pair<T*, ptrdiff_t> result(_RWSTD_STATIC_CAST(T*,
                               _RWSTD_STATIC_CAST(void*,__RWSTD::stl_temp_buffer)), 
                               _RWSTD_STATIC_CAST(ptrdiff_t,(_RWstl_buffer_size / sizeof(T))));
    return result;
#endif /*_RWSTD_MULTI_THREAD*/
  }

  template <class T>
  inline void return_temporary_buffer (T* p)
  {
#ifdef _RWSTD_MULTI_THREAD
    _RWSTDGuard guard(__RWSTD::stl_temp_buffer_mutex);

    if (_RWSTD_STATIC_CAST(char*,
                           _RWSTD_STATIC_CAST(void*,p)) != __RWSTD::stl_temp_buffer) 
      ::operator delete(p);
    else
      __RWSTD::stl_temp_buffer_being_used = false;
#else
    if (_RWSTD_STATIC_CAST(char*,
                           _RWSTD_STATIC_CAST(void*,p)) != __RWSTD::stl_temp_buffer) 
      ::operator delete(p);
#endif /*_RWSTD_MULTI_THREAD*/
  }

#else

  template <class T>
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  inline pair<T*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len)
#else
  inline pair<T*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len, T*)
#endif
  {
    T* tmp = _RWSTD_STATIC_CAST(T*,(   ::operator new(len * sizeof(T))));
    pair<T*,ptrdiff_t> result(tmp, len);
    return result;
  }

  template <class T>
  inline void return_temporary_buffer (T* p)
  {
    ::operator delete(p);
  }

#endif /*_RWSTD_FAST_TEMP_BUF*/


//
// Specialized algorithms.
//

  template <class InputIterator, class ForwardIterator>
  _RWSTD_TRICKY_INLINE ForwardIterator uninitialized_copy (InputIterator first, InputIterator last,
                                                           ForwardIterator result)
  {
    ForwardIterator start = result;
#ifndef _RWSTD_NO_EXCEPTIONS
    try {
      while (first != last) 
         __RWSTD::_RWconstruct(result++, *first++);
    } catch(...) {
       __RWSTD::_RWdestroy(start,result);
      throw;
    }
#else
    while (first != last) 
       __RWSTD::_RWconstruct(result++, *first++);
#endif // _RWSTD_NO_EXCEPTIONS

    return result;
  }

  template <class ForwardIterator, class T>
  _RWSTD_TRICKY_INLINE void uninitialized_fill (ForwardIterator first, ForwardIterator last,
                                                const T& x)
  {
    ForwardIterator start = first;
#ifndef _RWSTD_NO_EXCEPTIONS
    try {
      while (first != last) 
         __RWSTD::_RWconstruct(first++, x);
    } catch(...) {
       __RWSTD::_RWdestroy(start,first);
      throw;
    }
#else
    while (first != last) 
       __RWSTD::_RWconstruct(first++, x);
#endif // _RWSTD_NO_EXCEPTIONS
  }

  template <class ForwardIterator, class Size, class T>
  _RWSTD_TRICKY_INLINE void uninitialized_fill_n (ForwardIterator first, Size n, const T& x)
  {
    ForwardIterator start = first;
#ifndef _RWSTD_NO_EXCEPTIONS
    try {
      while (n--) 
         __RWSTD::_RWconstruct(first++, x);
    } catch(...) {
       __RWSTD::_RWdestroy(start,first);
      throw;
    }
#else
    while (n--) 
       __RWSTD::_RWconstruct(first++, x);
#endif // _RWSTD_NO_EXCEPTIONS
  }


//
// Template auto_ptr holds onto a pointer obtained via new and deletes that
// object when it itself is destroyed (such as when leaving block scope).
//
// It can be used to make calls to new() exception safe.
//

#if defined(__DECCXX) && !defined(__DECFIXCXXL1076)

template <class X> class auto_ptr;

#ifndef _RWSTD_NO_MEM_CLASS_TEMPLATES
    template <class Y> class auto_ptr_ref 
    {
    public:
#if defined(__DECCXX) && !defined(__DECFIXCXXL1080)
      auto_ptr<Y>& p;
#else
      const auto_ptr<Y>& p;
#endif
      auto_ptr_ref(auto_ptr<Y>& a): p(a) { }
    };
#endif    

#endif

  template<class X> class auto_ptr
  {
#if defined(__DECCXX) && !defined(__DECFIXCXXL1076)
#else
#ifndef _RWSTD_NO_MEM_CLASS_TEMPLATES
    template <class Y> class auto_ptr_ref 
    {
    public:
#if defined(__DECCXX) && !defined(__DECFIXCXXL1080)
      auto_ptr<Y>& p;
#else
      const auto_ptr<Y>& p;
#endif
      auto_ptr_ref(const auto_ptr<Y>& a) { p = a; }
    };
#endif    
#endif // CXXL 1076

  public:
    typedef X element_type;

    //
    // construct/copy/destroy
    //
    _EXPLICIT auto_ptr (X* p = 0)  _RWSTD_THROW_SPEC_NULL
     : the_p(p)
    { ; }

    auto_ptr (auto_ptr<X>& a)  _RWSTD_THROW_SPEC_NULL
     :  the_p((_RWSTD_CONST_CAST(auto_ptr<X>&,a)).release()) 
    { ; }

    auto_ptr<X>& operator= (auto_ptr<X>& rhs)  _RWSTD_THROW_SPEC_NULL
    { 
      reset(rhs.release());
      return *this;
    }

#if defined(__DECCXX) && !defined(__DECFIXCXXL1076)
     auto_ptr& operator=(auto_ptr_ref<X> r) throw()
    { 
      reset(r.p.release());
      return *this;
    }
#endif

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template <class Y>
    auto_ptr (auto_ptr<Y>& a)  _RWSTD_THROW_SPEC_NULL
     : the_p((_RWSTD_CONST_CAST(auto_ptr<Y>&,a)).release()) 
    { ; }

    template <class Y>
    auto_ptr<X>& operator= (auto_ptr<Y>& rhs)  _RWSTD_THROW_SPEC_NULL
    { 
      reset(rhs.release());
      return *this;
    }
#endif

#if defined(__DECCXX) && !defined(__DECFIXCXXL941)
    ~auto_ptr () _RWSTD_THROW_SPEC_NULL { delete the_p; }
#else
    ~auto_ptr () { delete the_p; }
#endif
    //
    // members
    //
    X& operator*  ()  const _RWSTD_THROW_SPEC_NULL { return *the_p;   }
    X* operator-> ()  const _RWSTD_THROW_SPEC_NULL { return the_p;    }
    X* get        ()  const _RWSTD_THROW_SPEC_NULL { return the_p;    }

    X* release    ()  _RWSTD_THROW_SPEC_NULL
    { 
      X* tmp = the_p;
      the_p = 0; 
      return tmp; 
    }

    void reset (X* p = 0) _RWSTD_THROW_SPEC_NULL
    { 
      if (the_p != p)
      {
        delete the_p;
        the_p = p;
      }
    }

#ifndef _RWSTD_NO_MEM_CLASS_TEMPLATES
#if defined(__DECCXX) && !defined(__DECFIXCXXL1180)
    auto_ptr(auto_ptr_ref<X> r) _RWSTD_THROW_SPEC_NULL: the_p(r.p.release())
#else
    auto_ptr(auto_ptr_ref<X> r) _RWSTD_THROW_SPEC_NULL
#endif
    {
#if defined(__DECCXX) && !defined(__DECFIXCXXL1180)
#else
      reset(r.p.release());
#endif
    }
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template <class Y> operator auto_ptr_ref<Y>() _RWSTD_THROW_SPEC_NULL
    {
      return auto_ptr_ref<Y>(*this);
    }
    template <class Y> operator auto_ptr<Y>() _RWSTD_THROW_SPEC_NULL
    {  
      auto_ptr<Y> tmp;
      tmp.reset(release());
      return tmp;
    }
#endif // _RWSTD_NO_MEMBER_TEMPLATES
#endif // _RWSTD_NO_MEM_CLASS_TEMPLATES

  private:
    X* the_p;
  };


#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#   pragma __extern_prefix __restore
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif /*__STD_MEMORY*/
