home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _alloc.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  12KB  |  371 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1996,1997
  4.  * Silicon Graphics Computer Systems, Inc.
  5.  *
  6.  * Copyright (c) 1997
  7.  * Moscow Center for SPARC Technology
  8.  *
  9.  * Copyright (c) 1999 
  10.  * Boris Fomitchev
  11.  *
  12.  * This material is provided "as is", with absolutely no warranty expressed
  13.  * or implied. Any use is at your own risk.
  14.  *
  15.  * Permission to use or copy this software for any purpose is hereby granted 
  16.  * without fee, provided the above notices are retained on all copies.
  17.  * Permission to modify the code and to distribute modified code is granted,
  18.  * provided the above notices are retained, and a notice that the code was
  19.  * modified is included with the above copyright notice.
  20.  *
  21.  */
  22. #ifndef _STLP_ALLOC_C
  23. #define _STLP_ALLOC_C
  24.  
  25. #ifdef __WATCOMC__
  26. #pragma warning 13 9
  27. #pragma warning 367 9
  28. #pragma warning 368 9
  29. #endif
  30.  
  31. #ifndef _STLP_INTERNAL_ALLOC_H
  32. #  include <stl/_alloc.h>
  33. #endif
  34.  
  35. # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
  36.  
  37. # ifdef _STLP_SGI_THREADS
  38.   // We test whether threads are in use before locking.
  39.   // Perhaps this should be moved into stl_threads.h, but that
  40.   // probably makes it harder to avoid the procedure call when
  41.   // it isn't needed.
  42.     extern "C" {
  43.       extern int __us_rsthread_malloc;
  44.     }
  45. # endif
  46.  
  47.  
  48. // Specialised debug form of malloc which does not provide "false"
  49. // memory leaks when run with debug CRT libraries.
  50. #if defined(_STLP_MSVC) && (_STLP_MSVC>=1020 && defined(_STLP_DEBUG_ALLOC)) && ! defined (_STLP_WINCE)
  51. #  include <crtdbg.h>
  52. inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_malloc_dbg(__bytes, _CRT_BLOCK, __FILE__, __LINE__)); }
  53. #else    // !_DEBUG
  54. # ifdef _STLP_NODE_ALLOC_USE_MALLOC
  55. #  include <cstdlib>
  56. inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_STLP_VENDOR_CSTD::malloc(__bytes)); }
  57. # else
  58. inline void* __stlp_chunk_malloc(size_t __bytes) { return _STLP_STD::__stl_new(__bytes); }
  59. # endif
  60. #endif    // !_DEBUG
  61.  
  62.  
  63. #define _S_FREELIST_INDEX(__bytes) ((__bytes-size_t(1))>>(int)_ALIGN_SHIFT)
  64.  
  65. _STLP_BEGIN_NAMESPACE
  66.  
  67. template <int __inst>
  68. void *  _STLP_CALL __malloc_alloc<__inst>::_S_oom_malloc(size_t __n)
  69. {
  70.   __oom_handler_type __my_malloc_handler;
  71.   void * __result;
  72.  
  73.   for (;;) {
  74.     __my_malloc_handler = __oom_handler;
  75.     if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
  76.     (*__my_malloc_handler)();
  77.     __result = malloc(__n);
  78.     if (__result) return(__result);
  79.   }
  80. #if defined(_STLP_NEED_UNREACHABLE_RETURN)
  81.   return 0;
  82. #endif
  83.  
  84. }
  85.  
  86. template <class _Alloc>
  87. void *  _STLP_CALL __debug_alloc<_Alloc>::allocate(size_t __n) {
  88.   size_t __real_n = __n + __extra_before_chunk() + __extra_after_chunk();
  89.   __alloc_header *__result = (__alloc_header *)__allocator_type::allocate(__real_n);
  90.   memset((char*)__result, __shred_byte, __real_n*sizeof(value_type));
  91.   __result->__magic = __magic;
  92.   __result->__type_size = sizeof(value_type);
  93.   __result->_M_size = (_STLP_UINT32_T)__n;
  94.   return ((char*)__result) + (long)__extra_before;
  95. }
  96.  
  97. template <class _Alloc>
  98. void  _STLP_CALL
  99. __debug_alloc<_Alloc>::deallocate(void *__p, size_t __n) {
  100.   __alloc_header * __real_p = (__alloc_header*)((char *)__p -(long)__extra_before);
  101.   // check integrity
  102.   _STLP_VERBOSE_ASSERT(__real_p->__magic != __deleted_magic, _StlMsg_DBA_DELETED_TWICE)
  103.   _STLP_VERBOSE_ASSERT(__real_p->__magic == __magic, _StlMsg_DBA_NEVER_ALLOCATED)
  104.   _STLP_VERBOSE_ASSERT(__real_p->__type_size == 1,_StlMsg_DBA_TYPE_MISMATCH)
  105.   _STLP_VERBOSE_ASSERT(__real_p->_M_size == __n, _StlMsg_DBA_SIZE_MISMATCH)
  106.   // check pads on both sides
  107.   unsigned char* __tmp;
  108.   for (__tmp= (unsigned char*)(__real_p+1); __tmp < (unsigned char*)__p; __tmp++) {  
  109.     _STLP_VERBOSE_ASSERT(*__tmp==__shred_byte, _StlMsg_DBA_UNDERRUN)
  110.       }
  111.   
  112.   size_t __real_n= __n + __extra_before_chunk() + __extra_after_chunk();
  113.   
  114.   for (__tmp= ((unsigned char*)__p)+__n*sizeof(value_type); 
  115.        __tmp < ((unsigned char*)__real_p)+__real_n ; __tmp++) {
  116.     _STLP_VERBOSE_ASSERT(*__tmp==__shred_byte, _StlMsg_DBA_OVERRUN)
  117.       }
  118.   
  119.   // that may be unfortunate, just in case
  120.   __real_p->__magic=__deleted_magic;
  121.   memset((char*)__p, __shred_byte, __n*sizeof(value_type));
  122.   __allocator_type::deallocate(__real_p, __real_n);
  123. }
  124.  
  125. // # ifdef _STLP_THREADS
  126.  
  127. template <bool __threads, int __inst>
  128. class _Node_Alloc_Lock {
  129. public:
  130.   _Node_Alloc_Lock() { 
  131.     
  132. #  ifdef _STLP_SGI_THREADS
  133.     if (__threads && __us_rsthread_malloc)
  134. #  else /* !_STLP_SGI_THREADS */
  135.       if (__threads) 
  136. #  endif
  137.         _S_lock._M_acquire_lock(); 
  138.   }
  139.   
  140.   ~_Node_Alloc_Lock() {
  141. #  ifdef _STLP_SGI_THREADS
  142.     if (__threads && __us_rsthread_malloc)
  143. #  else /* !_STLP_SGI_THREADS */
  144.       if (__threads)
  145. #  endif
  146.         _S_lock._M_release_lock(); 
  147.   }
  148.   
  149.   static _STLP_STATIC_MUTEX _S_lock;
  150. };
  151.  
  152. // # endif  /* _STLP_THREADS */
  153.  
  154.  
  155. template <bool __threads, int __inst>
  156. void* _STLP_CALL
  157. __node_alloc<__threads, __inst>::_M_allocate(size_t __n) {
  158.   void*  __r;
  159.   _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  160.   // #       ifdef _STLP_THREADS
  161.   /*REFERENCED*/
  162.   _Node_Alloc_Lock<__threads, __inst> __lock_instance;
  163.   // #       endif
  164.   // Acquire the lock here with a constructor call.
  165.   // This ensures that it is released in exit or during stack
  166.   // unwinding.
  167.   if ( (__r  = *__my_free_list) != 0 ) {
  168.     *__my_free_list = ((_Obj*)__r) -> _M_free_list_link;
  169.   } else {
  170.     __r = _S_refill(__n);
  171.   }
  172.   // lock is released here
  173.   return __r;
  174. }
  175.  
  176. template <bool __threads, int __inst>
  177. void _STLP_CALL
  178. __node_alloc<__threads, __inst>::_M_deallocate(void *__p, size_t __n) {
  179.   _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  180.   // #       ifdef _STLP_THREADS
  181.   /*REFERENCED*/
  182.   _Node_Alloc_Lock<__threads, __inst> __lock_instance;
  183.   // #       endif /* _STLP_THREADS */
  184.   // acquire lock
  185.   ((_Obj *)__p) -> _M_free_list_link = *__my_free_list;
  186.   *__my_free_list = (_Obj *)__p;
  187.   // lock is released here
  188. }
  189.  
  190. /* We allocate memory in large chunks in order to avoid fragmenting     */
  191. /* the malloc heap too much.                                            */
  192. /* We assume that size is properly aligned.                             */
  193. /* We hold the allocation lock.                                         */
  194. template <bool __threads, int __inst>
  195. char* _STLP_CALL
  196. __node_alloc<__threads, __inst>::_S_chunk_alloc(size_t _p_size, 
  197.                         int& __nobjs)
  198. {
  199.   char* __result;
  200.   size_t __total_bytes = _p_size * __nobjs;
  201.   size_t __bytes_left = _S_end_free - _S_start_free;
  202.  
  203.   if (__bytes_left >= __total_bytes) {
  204.     __result = _S_start_free;
  205.     _S_start_free += __total_bytes;
  206.     return(__result);
  207.   } else if (__bytes_left >= _p_size) {
  208.     __nobjs = (int)(__bytes_left/_p_size);
  209.     __total_bytes = _p_size * __nobjs;
  210.     __result = _S_start_free;
  211.     _S_start_free += __total_bytes;
  212.     return(__result);
  213.   } else {
  214.     size_t __bytes_to_get = 
  215.       2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
  216.     // Try to make use of the left-over piece.
  217.     if (__bytes_left > 0) {
  218.       _Obj* _STLP_VOLATILE* __my_free_list =
  219.     _S_free_list + _S_FREELIST_INDEX(__bytes_left);
  220.  
  221.       ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
  222.       *__my_free_list = (_Obj*)_S_start_free;
  223.     }
  224.     _S_start_free = (char*)__stlp_chunk_malloc(__bytes_to_get);
  225.     if (0 == _S_start_free) {
  226.       size_t __i;
  227.       _Obj* _STLP_VOLATILE* __my_free_list;
  228.       _Obj* __p;
  229.       // Try to make do with what we have.  That can't
  230.       // hurt.  We do not try smaller requests, since that tends
  231.       // to result in disaster on multi-process machines.
  232.       for (__i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {
  233.     __my_free_list = _S_free_list + _S_FREELIST_INDEX(__i);
  234.     __p = *__my_free_list;
  235.     if (0 != __p) {
  236.       *__my_free_list = __p -> _M_free_list_link;
  237.       _S_start_free = (char*)__p;
  238.       _S_end_free = _S_start_free + __i;
  239.       return(_S_chunk_alloc(_p_size, __nobjs));
  240.       // Any leftover piece will eventually make it to the
  241.       // right free list.
  242.     }
  243.       }
  244.       _S_end_free = 0;    // In case of exception.
  245.       _S_start_free = (char*)__stlp_chunk_malloc(__bytes_to_get);
  246.     /*
  247.       (char*)malloc_alloc::allocate(__bytes_to_get);
  248.       */
  249.  
  250.       // This should either throw an
  251.       // exception or remedy the situation.  Thus we assume it
  252.       // succeeded.
  253.     }
  254.     _S_heap_size += __bytes_to_get;
  255.     _S_end_free = _S_start_free + __bytes_to_get;
  256.     return(_S_chunk_alloc(_p_size, __nobjs));
  257.   }
  258. }
  259.  
  260.  
  261. /* Returns an object of size __n, and optionally adds to size __n free list.*/
  262. /* We assume that __n is properly aligned.                                */
  263. /* We hold the allocation lock.                                         */
  264. template <bool __threads, int __inst>
  265. void* _STLP_CALL
  266. __node_alloc<__threads, __inst>::_S_refill(size_t __n)
  267. {
  268.   int __nobjs = 20;
  269.   __n = _S_round_up(__n);
  270.   char* __chunk = _S_chunk_alloc(__n, __nobjs);
  271.   _Obj* _STLP_VOLATILE* __my_free_list;
  272.   _Obj* __result;
  273.   _Obj* __current_obj;
  274.   _Obj* __next_obj;
  275.   int __i;
  276.  
  277.   if (1 == __nobjs) return(__chunk);
  278.   __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  279.  
  280.   /* Build free list in chunk */
  281.   __result = (_Obj*)__chunk;
  282.   *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
  283.   for (__i = 1; ; __i++) {
  284.     __current_obj = __next_obj;
  285.     __next_obj = (_Obj*)((char*)__next_obj + __n);
  286.     if (__nobjs - 1 == __i) {
  287.       __current_obj -> _M_free_list_link = 0;
  288.       break;
  289.     } else {
  290.       __current_obj -> _M_free_list_link = __next_obj;
  291.     }
  292.   }
  293.   return(__result);
  294. }
  295.  
  296. # if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
  297. // malloc_alloc out-of-memory handling
  298. template <int __inst>
  299. __oom_handler_type __malloc_alloc<__inst>::__oom_handler=(__oom_handler_type)0 ;
  300.  
  301. // #ifdef _STLP_THREADS
  302.     template <bool __threads, int __inst>
  303.     _STLP_STATIC_MUTEX
  304.     _Node_Alloc_Lock<__threads, __inst>::_S_lock _STLP_MUTEX_INITIALIZER;
  305. // #endif
  306.  
  307. template <bool __threads, int __inst>
  308. _Node_alloc_obj * _STLP_VOLATILE
  309. __node_alloc<__threads, __inst>::_S_free_list[_STLP_NFREELISTS]
  310. = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  311. // The 16 zeros are necessary to make version 4.1 of the SunPro
  312. // compiler happy.  Otherwise it appears to allocate too little
  313. // space for the array.
  314.  
  315. template <bool __threads, int __inst>
  316. char *__node_alloc<__threads, __inst>::_S_start_free = 0;
  317.  
  318. template <bool __threads, int __inst>
  319. char *__node_alloc<__threads, __inst>::_S_end_free = 0;
  320.  
  321. template <bool __threads, int __inst>
  322. size_t __node_alloc<__threads, __inst>::_S_heap_size = 0;
  323.  
  324.  
  325. # else /* ( _STLP_STATIC_TEMPLATE_DATA > 0 ) */
  326.  
  327. __DECLARE_INSTANCE(__oom_handler_type, __malloc_alloc<0>::__oom_handler, =0);
  328.  
  329. # define _STLP_ALLOC_NOTHREADS __node_alloc<false, 0>
  330. # define _STLP_ALLOC_THREADS   __node_alloc<true, 0>
  331. # define _STLP_ALLOC_NOTHREADS_LOCK _Node_Alloc_Lock<false, 0>
  332. # define _STLP_ALLOC_THREADS_LOCK   _Node_Alloc_Lock<true, 0>
  333.  
  334. __DECLARE_INSTANCE(char *, _STLP_ALLOC_NOTHREADS::_S_start_free,=0);
  335. __DECLARE_INSTANCE(char *, _STLP_ALLOC_NOTHREADS::_S_end_free,=0);
  336. __DECLARE_INSTANCE(size_t, _STLP_ALLOC_NOTHREADS::_S_heap_size,=0);
  337. __DECLARE_INSTANCE(_Node_alloc_obj * _STLP_VOLATILE,
  338.                    _STLP_ALLOC_NOTHREADS::_S_free_list[_STLP_NFREELISTS],
  339.                    ={0});
  340. __DECLARE_INSTANCE(char *, _STLP_ALLOC_THREADS::_S_start_free,=0);
  341. __DECLARE_INSTANCE(char *, _STLP_ALLOC_THREADS::_S_end_free,=0);
  342. __DECLARE_INSTANCE(size_t, _STLP_ALLOC_THREADS::_S_heap_size,=0);
  343. __DECLARE_INSTANCE(_Node_alloc_obj * _STLP_VOLATILE,
  344.                    _STLP_ALLOC_THREADS::_S_free_list[_STLP_NFREELISTS],
  345.                    ={0});
  346. // #   ifdef _STLP_THREADS
  347. __DECLARE_INSTANCE(_STLP_STATIC_MUTEX,
  348.                    _STLP_ALLOC_NOTHREADS_LOCK::_S_lock,
  349.                    _STLP_MUTEX_INITIALIZER);
  350. __DECLARE_INSTANCE(_STLP_STATIC_MUTEX,
  351.                    _STLP_ALLOC_THREADS_LOCK::_S_lock,
  352.                    _STLP_MUTEX_INITIALIZER);
  353. // #   endif
  354.  
  355. # undef _STLP_ALLOC_THREADS
  356. # undef _STLP_ALLOC_NOTHREADS
  357.  
  358. #  endif /* _STLP_STATIC_TEMPLATE_DATA */
  359.  
  360. _STLP_END_NAMESPACE
  361.  
  362. # undef _S_FREELIST_INDEX
  363.  
  364. # endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
  365.  
  366. #endif /*  _STLP_ALLOC_C */
  367.  
  368. // Local Variables:
  369. // mode:C++
  370. // End:
  371.