williamr@2: /*
williamr@2:  *
williamr@2:  * Copyright (c) 1996,1997
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@2:  * Copyright (c) 1997
williamr@2:  * Moscow Center for SPARC Technology
williamr@2:  *
williamr@2:  * Copyright (c) 1999 
williamr@2:  * Boris Fomitchev
williamr@2:  *
williamr@2:  * This material is provided "as is", with absolutely no warranty expressed
williamr@2:  * or implied. Any use is at your own risk.
williamr@2:  *
williamr@2:  * Permission to use or copy this software for any purpose is hereby granted 
williamr@2:  * without fee, provided the above notices are retained on all copies.
williamr@2:  * Permission to modify the code and to distribute modified code is granted,
williamr@2:  * provided the above notices are retained, and a notice that the code was
williamr@2:  * modified is included with the above copyright notice.
williamr@2:  *
williamr@2:  */
williamr@2: #ifndef _STLP_ALLOC_C
williamr@2: #define _STLP_ALLOC_C
williamr@2: 
williamr@2: #ifdef __WATCOMC__
williamr@2: #pragma warning 13 9
williamr@2: #pragma warning 367 9
williamr@2: #pragma warning 368 9
williamr@2: #endif
williamr@2: 
williamr@2: #ifndef _STLP_INTERNAL_ALLOC_H
williamr@2: #  include <stl/_alloc.h>
williamr@2: #endif
williamr@2: 
williamr@2: # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
williamr@2: 
williamr@2: # ifdef _STLP_SGI_THREADS
williamr@2:   // We test whether threads are in use before locking.
williamr@2:   // Perhaps this should be moved into stl_threads.h, but that
williamr@2:   // probably makes it harder to avoid the procedure call when
williamr@2:   // it isn't needed.
williamr@2:     extern "C" {
williamr@2:       extern int __us_rsthread_malloc;
williamr@2:     }
williamr@2: # endif
williamr@2: 
williamr@2: 
williamr@2: // Specialised debug form of malloc which does not provide "false"
williamr@2: // memory leaks when run with debug CRT libraries.
williamr@2: #if defined(_STLP_MSVC) && (_STLP_MSVC>=1020 && defined(_STLP_DEBUG_ALLOC)) && ! defined (_STLP_WINCE)
williamr@2: #  include <crtdbg.h>
williamr@2: inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_malloc_dbg(__bytes, _CRT_BLOCK, __FILE__, __LINE__)); }
williamr@2: #else	// !_DEBUG
williamr@2: # ifdef _STLP_NODE_ALLOC_USE_MALLOC
williamr@2: #  include <cstdlib>
williamr@2: inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_STLP_VENDOR_CSTD::malloc(__bytes)); }
williamr@2: # else
williamr@2: inline void* __stlp_chunk_malloc(size_t __bytes) { return _STLP_STD::__stl_new(__bytes); }
williamr@2: # endif
williamr@2: #endif	// !_DEBUG
williamr@2: 
williamr@2: 
williamr@2: #define _S_FREELIST_INDEX(__bytes) ((__bytes-size_t(1))>>(int)_ALIGN_SHIFT)
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@2: #ifndef _STLP_NO_NODE_ALLOC
williamr@2: 
williamr@2: template <int __inst>
williamr@2: void *  _STLP_CALL __malloc_alloc<__inst>::_S_oom_malloc(size_t __n)
williamr@2: {
williamr@2:   __oom_handler_type __my_malloc_handler;
williamr@2:   void * __result;
williamr@2: 
williamr@2:   for (;;) {
williamr@2:     __my_malloc_handler = __oom_handler;
williamr@2:     if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
williamr@2:     (*__my_malloc_handler)();
williamr@2:     __result = malloc(__n);
williamr@2:     if (__result) return(__result);
williamr@2:   }
williamr@2: #if defined(_STLP_NEED_UNREACHABLE_RETURN)
williamr@2:   return 0;
williamr@2: #endif
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: template <class _Alloc>
williamr@2: void *  _STLP_CALL __debug_alloc<_Alloc>::allocate(size_t __n) {
williamr@2:   size_t __real_n = __n + __extra_before_chunk() + __extra_after_chunk();
williamr@2:   __alloc_header *__result = (__alloc_header *)__allocator_type::allocate(__real_n);
williamr@2:   memset((char*)__result, __shred_byte, __real_n*sizeof(value_type));
williamr@2:   __result->__magic = __magic;
williamr@2:   __result->__type_size = sizeof(value_type);
williamr@2:   __result->_M_size = (_STLP_UINT32_T)__n;
williamr@2:   return ((char*)__result) + (long)__extra_before;
williamr@2: }
williamr@2: 
williamr@2: template <class _Alloc>
williamr@2: void  _STLP_CALL
williamr@2: __debug_alloc<_Alloc>::deallocate(void *__p, size_t __n) {
williamr@2:   __alloc_header * __real_p = (__alloc_header*)((char *)__p -(long)__extra_before);
williamr@2:   // check integrity
williamr@2:   _STLP_VERBOSE_ASSERT(__real_p->__magic != __deleted_magic, _StlMsg_DBA_DELETED_TWICE)
williamr@2:   _STLP_VERBOSE_ASSERT(__real_p->__magic == __magic, _StlMsg_DBA_NEVER_ALLOCATED)
williamr@2:   _STLP_VERBOSE_ASSERT(__real_p->__type_size == 1,_StlMsg_DBA_TYPE_MISMATCH)
williamr@2:   _STLP_VERBOSE_ASSERT(__real_p->_M_size == __n, _StlMsg_DBA_SIZE_MISMATCH)
williamr@2:   // check pads on both sides
williamr@2:   unsigned char* __tmp;
williamr@2:   for (__tmp= (unsigned char*)(__real_p+1); __tmp < (unsigned char*)__p; __tmp++) {  
williamr@2:     _STLP_VERBOSE_ASSERT(*__tmp==__shred_byte, _StlMsg_DBA_UNDERRUN)
williamr@2:       }
williamr@2:   
williamr@2:   size_t __real_n= __n + __extra_before_chunk() + __extra_after_chunk();
williamr@2:   
williamr@2:   for (__tmp= ((unsigned char*)__p)+__n*sizeof(value_type); 
williamr@2:        __tmp < ((unsigned char*)__real_p)+__real_n ; __tmp++) {
williamr@2:     _STLP_VERBOSE_ASSERT(*__tmp==__shred_byte, _StlMsg_DBA_OVERRUN)
williamr@2:       }
williamr@2:   
williamr@2:   // that may be unfortunate, just in case
williamr@2:   __real_p->__magic=__deleted_magic;
williamr@2:   memset((char*)__p, __shred_byte, __n*sizeof(value_type));
williamr@2:   __allocator_type::deallocate(__real_p, __real_n);
williamr@2: }
williamr@2: 
williamr@2: #ifndef _STLP_NO_NODE_ALLOC
williamr@2: 
williamr@2: // # ifdef _STLP_THREADS
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: class _Node_Alloc_Lock {
williamr@2: public:
williamr@2:   _Node_Alloc_Lock() { 
williamr@2:     
williamr@2: #  ifdef _STLP_SGI_THREADS
williamr@2:     if (__threads && __us_rsthread_malloc)
williamr@2: #  else /* !_STLP_SGI_THREADS */
williamr@2:       if (__threads) 
williamr@2: #  endif
williamr@2:     	_S_lock._M_acquire_lock(); 
williamr@2:   }
williamr@2:   
williamr@2:   ~_Node_Alloc_Lock() {
williamr@2: #  ifdef _STLP_SGI_THREADS
williamr@2:     if (__threads && __us_rsthread_malloc)
williamr@2: #  else /* !_STLP_SGI_THREADS */
williamr@2:       if (__threads)
williamr@2: #  endif
williamr@2:         _S_lock._M_release_lock(); 
williamr@2:   }
williamr@2:   
williamr@2:   static _STLP_STATIC_MUTEX _S_lock;
williamr@2: };
williamr@2: 
williamr@2: // # endif  /* _STLP_THREADS */
williamr@2: 
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: void* _STLP_CALL
williamr@2: __node_alloc<__threads, __inst>::_M_allocate(size_t __n) {
williamr@2:   void*  __r;
williamr@2:   _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
williamr@2:   // #       ifdef _STLP_THREADS
williamr@2:   /*REFERENCED*/
williamr@2:   _Node_Alloc_Lock<__threads, __inst> __lock_instance;
williamr@2:   // #       endif
williamr@2:   // Acquire the lock here with a constructor call.
williamr@2:   // This ensures that it is released in exit or during stack
williamr@2:   // unwinding.
williamr@2:   if ( (__r  = *__my_free_list) != 0 ) {
williamr@2:     *__my_free_list = ((_Obj*)__r) -> _M_free_list_link;
williamr@2:   } else {
williamr@2:     __r = _S_refill(__n);
williamr@2:   }
williamr@2:   // lock is released here
williamr@2:   return __r;
williamr@2: }
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: void _STLP_CALL
williamr@2: __node_alloc<__threads, __inst>::_M_deallocate(void *__p, size_t __n) {
williamr@2:   _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
williamr@2:   // #       ifdef _STLP_THREADS
williamr@2:   /*REFERENCED*/
williamr@2:   _Node_Alloc_Lock<__threads, __inst> __lock_instance;
williamr@2:   // #       endif /* _STLP_THREADS */
williamr@2:   // acquire lock
williamr@2:   ((_Obj *)__p) -> _M_free_list_link = *__my_free_list;
williamr@2:   *__my_free_list = (_Obj *)__p;
williamr@2:   // lock is released here
williamr@2: }
williamr@2: 
williamr@2: /* We allocate memory in large chunks in order to avoid fragmenting     */
williamr@2: /* the malloc heap too much.                                            */
williamr@2: /* We assume that size is properly aligned.                             */
williamr@2: /* We hold the allocation lock.                                         */
williamr@2: template <bool __threads, int __inst>
williamr@2: char* _STLP_CALL
williamr@2: __node_alloc<__threads, __inst>::_S_chunk_alloc(size_t _p_size, 
williamr@2: 						int& __nobjs)
williamr@2: {
williamr@2:   char* __result;
williamr@2:   size_t __total_bytes = _p_size * __nobjs;
williamr@2:   size_t __bytes_left = _S_end_free - _S_start_free;
williamr@2: 
williamr@2:   if (__bytes_left >= __total_bytes) {
williamr@2:     __result = _S_start_free;
williamr@2:     _S_start_free += __total_bytes;
williamr@2:     return(__result);
williamr@2:   } else if (__bytes_left >= _p_size) {
williamr@2:     __nobjs = (int)(__bytes_left/_p_size);
williamr@2:     __total_bytes = _p_size * __nobjs;
williamr@2:     __result = _S_start_free;
williamr@2:     _S_start_free += __total_bytes;
williamr@2:     return(__result);
williamr@2:   } else {
williamr@2:     size_t __bytes_to_get = 
williamr@2:       2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
williamr@2:     // Try to make use of the left-over piece.
williamr@2:     if (__bytes_left > 0) {
williamr@2:       _Obj* _STLP_VOLATILE* __my_free_list =
williamr@2: 	_S_free_list + _S_FREELIST_INDEX(__bytes_left);
williamr@2: 
williamr@2:       ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
williamr@2:       *__my_free_list = (_Obj*)_S_start_free;
williamr@2:     }
williamr@2:     _S_start_free = (char*)__stlp_chunk_malloc(__bytes_to_get);
williamr@2:     if (0 == _S_start_free) {
williamr@2:       size_t __i;
williamr@2:       _Obj* _STLP_VOLATILE* __my_free_list;
williamr@2:       _Obj* __p;
williamr@2:       // Try to make do with what we have.  That can't
williamr@2:       // hurt.  We do not try smaller requests, since that tends
williamr@2:       // to result in disaster on multi-process machines.
williamr@2:       for (__i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {
williamr@2: 	__my_free_list = _S_free_list + _S_FREELIST_INDEX(__i);
williamr@2: 	__p = *__my_free_list;
williamr@2: 	if (0 != __p) {
williamr@2: 	  *__my_free_list = __p -> _M_free_list_link;
williamr@2: 	  _S_start_free = (char*)__p;
williamr@2: 	  _S_end_free = _S_start_free + __i;
williamr@2: 	  return(_S_chunk_alloc(_p_size, __nobjs));
williamr@2: 	  // Any leftover piece will eventually make it to the
williamr@2: 	  // right free list.
williamr@2: 	}
williamr@2:       }
williamr@2:       _S_end_free = 0;	// In case of exception.
williamr@2:       _S_start_free = (char*)__stlp_chunk_malloc(__bytes_to_get);
williamr@2:     /*
williamr@2:       (char*)malloc_alloc::allocate(__bytes_to_get);
williamr@2:       */
williamr@2: 
williamr@2:       // This should either throw an
williamr@2:       // exception or remedy the situation.  Thus we assume it
williamr@2:       // succeeded.
williamr@2:     }
williamr@2:     _S_heap_size += __bytes_to_get;
williamr@2:     _S_end_free = _S_start_free + __bytes_to_get;
williamr@2:     return(_S_chunk_alloc(_p_size, __nobjs));
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: /* Returns an object of size __n, and optionally adds to size __n free list.*/
williamr@2: /* We assume that __n is properly aligned.                                */
williamr@2: /* We hold the allocation lock.                                         */
williamr@2: template <bool __threads, int __inst>
williamr@2: void* _STLP_CALL
williamr@2: __node_alloc<__threads, __inst>::_S_refill(size_t __n)
williamr@2: {
williamr@2:   int __nobjs = 20;
williamr@2:   __n = _S_round_up(__n);
williamr@2:   char* __chunk = _S_chunk_alloc(__n, __nobjs);
williamr@2:   _Obj* _STLP_VOLATILE* __my_free_list;
williamr@2:   _Obj* __result;
williamr@2:   _Obj* __current_obj;
williamr@2:   _Obj* __next_obj;
williamr@2:   int __i;
williamr@2: 
williamr@2:   if (1 == __nobjs) return(__chunk);
williamr@2:   __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
williamr@2: 
williamr@2:   /* Build free list in chunk */
williamr@2:   __result = (_Obj*)__chunk;
williamr@2:   *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
williamr@2:   for (__i = 1; ; __i++) {
williamr@2:     __current_obj = __next_obj;
williamr@2:     __next_obj = (_Obj*)((char*)__next_obj + __n);
williamr@2:     if (__nobjs - 1 == __i) {
williamr@2:       __current_obj -> _M_free_list_link = 0;
williamr@2:       break;
williamr@2:     } else {
williamr@2:       __current_obj -> _M_free_list_link = __next_obj;
williamr@2:     }
williamr@2:   }
williamr@2:   return(__result);
williamr@2: }
williamr@2: 
williamr@2: # if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
williamr@2: // malloc_alloc out-of-memory handling
williamr@2: template <int __inst>
williamr@2: __oom_handler_type __malloc_alloc<__inst>::__oom_handler=(__oom_handler_type)0 ;
williamr@2: 
williamr@2: #ifdef _STLP_THREADS
williamr@2:     template <bool __threads, int __inst>
williamr@2:     _STLP_STATIC_MUTEX
williamr@2:     _Node_Alloc_Lock<__threads, __inst>::_S_lock _STLP_MUTEX_INITIALIZER;
williamr@2: #endif
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: _Node_alloc_obj * _STLP_VOLATILE
williamr@2: __node_alloc<__threads, __inst>::_S_free_list[_STLP_NFREELISTS]
williamr@2: = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
williamr@2: // The 16 zeros are necessary to make version 4.1 of the SunPro
williamr@2: // compiler happy.  Otherwise it appears to allocate too little
williamr@2: // space for the array.
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: char *__node_alloc<__threads, __inst>::_S_start_free = 0;
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: char *__node_alloc<__threads, __inst>::_S_end_free = 0;
williamr@2: 
williamr@2: template <bool __threads, int __inst>
williamr@2: size_t __node_alloc<__threads, __inst>::_S_heap_size = 0;
williamr@2: 
williamr@2: 
williamr@2: # else /* ( _STLP_STATIC_TEMPLATE_DATA > 0 ) */
williamr@2: 
williamr@2: __DECLARE_INSTANCE(__oom_handler_type, __malloc_alloc<0>::__oom_handler, =0);
williamr@2: 
williamr@2: # define _STLP_ALLOC_NOTHREADS __node_alloc<false, 0>
williamr@2: # define _STLP_ALLOC_THREADS   __node_alloc<true, 0>
williamr@2: # define _STLP_ALLOC_NOTHREADS_LOCK _Node_Alloc_Lock<false, 0>
williamr@2: # define _STLP_ALLOC_THREADS_LOCK   _Node_Alloc_Lock<true, 0>
williamr@2: 
williamr@2: __DECLARE_INSTANCE(char *, _STLP_ALLOC_NOTHREADS::_S_start_free,=0);
williamr@2: __DECLARE_INSTANCE(char *, _STLP_ALLOC_NOTHREADS::_S_end_free,=0);
williamr@2: __DECLARE_INSTANCE(size_t, _STLP_ALLOC_NOTHREADS::_S_heap_size,=0);
williamr@2: __DECLARE_INSTANCE(_Node_alloc_obj * _STLP_VOLATILE,
williamr@2:                    _STLP_ALLOC_NOTHREADS::_S_free_list[_STLP_NFREELISTS],
williamr@2:                    ={0});
williamr@2: __DECLARE_INSTANCE(char *, _STLP_ALLOC_THREADS::_S_start_free,=0);
williamr@2: __DECLARE_INSTANCE(char *, _STLP_ALLOC_THREADS::_S_end_free,=0);
williamr@2: __DECLARE_INSTANCE(size_t, _STLP_ALLOC_THREADS::_S_heap_size,=0);
williamr@2: __DECLARE_INSTANCE(_Node_alloc_obj * _STLP_VOLATILE,
williamr@2:                    _STLP_ALLOC_THREADS::_S_free_list[_STLP_NFREELISTS],
williamr@2:                    ={0});
williamr@2: // #   ifdef _STLP_THREADS
williamr@2: __DECLARE_INSTANCE(_STLP_STATIC_MUTEX,
williamr@2:                    _STLP_ALLOC_NOTHREADS_LOCK::_S_lock,
williamr@2:                    _STLP_MUTEX_INITIALIZER);
williamr@2: __DECLARE_INSTANCE(_STLP_STATIC_MUTEX,
williamr@2:                    _STLP_ALLOC_THREADS_LOCK::_S_lock,
williamr@2:                    _STLP_MUTEX_INITIALIZER);
williamr@2: // #   endif
williamr@2: 
williamr@2: # undef _STLP_ALLOC_THREADS
williamr@2: # undef _STLP_ALLOC_NOTHREADS
williamr@2: 
williamr@2: #  endif /* _STLP_STATIC_TEMPLATE_DATA */
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: # undef _S_FREELIST_INDEX
williamr@2: 
williamr@2: # endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
williamr@2: 
williamr@2: #endif /*  _STLP_ALLOC_C */
williamr@2: 
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End: