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 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 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 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 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 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 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 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 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 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 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 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 williamr@2: __oom_handler_type __malloc_alloc<__inst>::__oom_handler=(__oom_handler_type)0 ; williamr@2: williamr@2: #ifdef _STLP_THREADS williamr@2: template 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 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 williamr@2: char *__node_alloc<__threads, __inst>::_S_start_free = 0; williamr@2: williamr@2: template williamr@2: char *__node_alloc<__threads, __inst>::_S_end_free = 0; williamr@2: williamr@2: template 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 williamr@2: # define _STLP_ALLOC_THREADS __node_alloc williamr@2: # define _STLP_ALLOC_NOTHREADS_LOCK _Node_Alloc_Lock williamr@2: # define _STLP_ALLOC_THREADS_LOCK _Node_Alloc_Lock 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: