vcl_alloc.h

来自「DTMK软件开发包,此为开源软件,是一款很好的医学图像开发资源.」· C头文件 代码 · 共 805 行 · 第 1/2 页

      static vcl_size_t ROUND_UP(vcl_size_t bytes) { return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1)); }
     __PRIVATE:
      union obj;
      friend union obj;
      union obj {
        union obj * free_list_link;
        char client_data[1];    /* The client sees this.        */
      };
     private:
#     if defined ( __SUNPRO_CC ) || defined ( _AIX )
      static obj * __VOLATILE free_list[];
      // Specifying a size results in duplicate def for 4.1
#     else
      static obj * __VOLATILE free_list[__NFREELISTS];
#     endif
      static  vcl_size_t FREELIST_INDEX(vcl_size_t bytes) { return (((bytes) + __ALIGN-1)/__ALIGN - 1); }

      // Returns an object of size n, and optionally adds to size n free vcl_list.
      static void *refill(vcl_size_t n);
      // Allocates a chunk for nobjs of size size.  nobjs may be reduced
      // if it is inconvenient to allocate the requested number.
      static char *chunk_alloc(vcl_size_t size, int &nobjs);

      // Chunk allocation state.
      static char *start_free;
      static char *end_free;
      static vcl_size_t heap_size;

#     ifdef __STL_SGI_THREADS
      static volatile unsigned long __node_allocator_lock;
      static void __lock(volatile unsigned long *);
      static inline void __unlock(volatile unsigned long *);
#     endif

#     ifdef _PTHREADS
      static pthread_mutex_t __node_allocator_lock;
#     endif

#     ifdef __STL_WIN32THREADS
      static __stl_critical_section_wrapper __node_allocator_lock;
#     endif

      class lock
      {
       public:
        lock() { __NODE_ALLOCATOR_LOCK; }
       ~lock() { __NODE_ALLOCATOR_UNLOCK; }
      };
      friend class lock;

     public:
      // this one is needed for proper vcl_simple_alloc wrapping
      typedef char value_type;

      /* n must be > 0      */
      static void * allocate(vcl_size_t n)
      {
        obj * __VOLATILE * my_free_list;
        obj * __RESTRICT result;

        if (n > __MAX_BYTES) {
            return vcl_malloc_alloc::allocate(n);
        }
        my_free_list = free_list + FREELIST_INDEX(n);
        // Acquire the lock here with a constructor call.
        // This ensures that it is released in exit or during stack
        // unwinding.
            /*REFERENCED*/
#     if !defined (_NOTHREADS)
        lock lock_instance;
#     endif
        result = *my_free_list;
        if (result == 0) {
            void *r = refill(ROUND_UP(n));
            return r;
        }
        *my_free_list = result -> free_list_link;
        return result;
      };

      /* p may not be 0 */
      static void deallocate(void *p, vcl_size_t n)
      {
        obj *q = (obj *)p;
        obj * __VOLATILE * my_free_list;

        if (n > __MAX_BYTES) {
            vcl_malloc_alloc::deallocate(p, n);
            return;
        }
        my_free_list = free_list + FREELIST_INDEX(n);
        // acquire lock
#     if !defined (_NOTHREADS)
        /*REFERENCED*/
        lock lock_instance;
#     endif
        q -> free_list_link = *my_free_list;
        *my_free_list = q;
        // lock is released here
      }

      static void * reallocate(void *p, vcl_size_t old_sz, vcl_size_t new_sz);
    };

    typedef __alloc<__NODE_ALLOCATOR_THREADS, 0> node_alloc;
#       if defined ( __STL_DEBUG_ALLOC )
    typedef debug_alloc<node_alloc> vcl_alloc;
#       else
    typedef node_alloc vcl_alloc;
#       endif
    typedef __alloc<false, 0> single_client_alloc;
    typedef __alloc<true, 0>  multithreaded_alloc;

    /* We allocate memory in large chunks in order to avoid fragmenting     */
    /* the malloc heap too much.                                            */
    /* We assume that size is properly aligned.                             */
    /* We hold the allocation lock.                                         */
    template <bool threads, int inst>
    char*
    __alloc<threads, inst>::chunk_alloc(vcl_size_t size, int& nobjs)
    {
      char * result;
      vcl_size_t total_bytes = size * nobjs;
      vcl_size_t bytes_left = end_free - start_free;

      if (bytes_left >= total_bytes)
      {
        result = start_free;
        start_free += total_bytes;
        return result;
      }
      else if (bytes_left >= size)
      {
          nobjs = bytes_left/size;
          total_bytes = size * nobjs;
          result = start_free;
          start_free += total_bytes;
          return result;
      }
      else
      {
        vcl_size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // Try to make use of the left-over piece.
        if (bytes_left > 0)
        {
          obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
          ((obj *)start_free) -> free_list_link = *my_free_list;
          *my_free_list = (obj *)start_free;
        }
        start_free = (char *)malloc(bytes_to_get);
        if (0 == start_free)
        {
          obj * __VOLATILE * my_free_list, *p;
          // Try to make do with what we have.  That can't
          // hurt.  We do not try smaller requests, since that tends
          // to result in disaster on multi-process machines.
          for (int i = size; i <= __MAX_BYTES; i += __ALIGN)
          {
            my_free_list = free_list + FREELIST_INDEX(i);
            p = *my_free_list;
            if (0 != p)
            {
              *my_free_list = p -> free_list_link;
              start_free = (char *)p;
              end_free = start_free + i;
              return chunk_alloc(size, nobjs);
              // Any leftover piece will eventually make it to the
              // right free vcl_list.
            }
          }
          start_free = (char *)vcl_malloc_alloc::allocate(bytes_to_get);
          // This should either throw an
          // exception or remedy the situation.  Thus we assume it
          // succeeded.
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return chunk_alloc(size, nobjs);
      }
    }

    /* Returns an object of size n, and optionally adds to size n free vcl_list.*/
    /* We assume that n is properly aligned.                                */
    /* We hold the allocation lock.                                         */
    template <bool threads, int inst>
    void* __alloc<threads, inst>::refill(vcl_size_t n)
    {
      int nobjs = 20;
      char * chunk = chunk_alloc(n, nobjs);
      obj * __VOLATILE * my_free_list;
      obj * result;
      obj * current_obj, * next_obj;
      int i;

      if (1 == nobjs) return chunk;
      my_free_list = free_list + FREELIST_INDEX(n);

      /* Build free vcl_list in chunk */
      result = (obj *)chunk;
      *my_free_list = next_obj = (obj *)(chunk + n);
      for (i = 1; true; i++)
      {
        current_obj = next_obj;
        next_obj = (obj *)((char *)next_obj + n);
        if (nobjs - 1 == i) { current_obj -> free_list_link = 0; break; }
        else { current_obj -> free_list_link = next_obj; }
      }
      return result;
    }

    template <bool threads, int inst>
    void*
    __alloc<threads, inst>::reallocate(void *p,
                                       vcl_size_t old_sz,
                                       vcl_size_t new_sz)
    {
      void * result;
      vcl_size_t copy_sz;

      if (old_sz > __MAX_BYTES && new_sz > __MAX_BYTES)
        return realloc(p, new_sz);
      if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;
      result = allocate(new_sz);
      copy_sz = new_sz > old_sz? old_sz : new_sz;
      vcl_memcpy(result, p, copy_sz);
      deallocate(p, old_sz);
      return result;
    }

#   ifdef __STL_SGI_THREADS
#    include <mutex.h>
#    include <vcl_ctime.h>
    // Somewhat generic lock implementations.  We need only test-and-set
    // and some way to sleep.  These should work with both SGI pthreads
    // and sproc threads.  They may be useful on other systems.
#    if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) || defined(__GNUC__)
#       define __test_and_set(l,v) test_and_set(l,v)
#    endif

    template <bool threads, int inst>
    void
    __alloc<threads, inst>::__lock(volatile unsigned long *lock)
    {
      const unsigned low_spin_max = 30;  // spin cycles if we suspect uniprocessor
      const unsigned high_spin_max = 1000; // spin cycles for multiprocessor
      static unsigned spin_max = low_spin_max;
      unsigned my_spin_max;
      static unsigned last_spins = 0;
      unsigned my_last_spins;
      static struct timespec ts = {0, 1000};
      unsigned junk;
#       define __ALLOC_PAUSE junk *= junk; junk *= junk; junk *= junk; junk *= junk
      if (!__test_and_set((unsigned long *)lock, 1)) return;
      my_spin_max = spin_max;
      my_last_spins = last_spins;
      for (int i = 0; i < my_spin_max; i++)
      {
        if (i < my_last_spins/2 || *lock) {
          __ALLOC_PAUSE;
          continue;
        }
        if (!__test_and_set((unsigned long *)lock, 1)) {
          // got it!
          // Spinning worked.  Thus we're probably not being scheduled
          // against the other process with which we were contending.
          // Thus it makes sense to spin longer the next time.
          last_spins = i;
          spin_max = high_spin_max;
          return;
        }
      }
      // We are probably being scheduled against the other process.  Sleep.
      spin_max = low_spin_max;
      for (;;) {
        if (!__test_and_set((unsigned long *)lock, 1)) return;
        nanosleep(&ts, 0);
      }
    }

    template <bool threads, int inst>
    inline void
    __alloc<threads, inst>::__unlock(volatile unsigned long *lock)
    {
#       if defined(__GNUC__) && __mips >= 3
      asm("sync");
      *lock = 0;
#       elif __mips >= 3 && (defined (_ABIN32) || defined(_ABI64))
      __lock_release(lock);
#       else
      *lock = 0;
      // This is not sufficient on many multiprocessors, since
      // writes to protected variables and the lock may be reordered.
#       endif
    }
#   endif /* ! __STL_SGI_THREADS */

#   if ( __STL_STATIC_TEMPLATE_DATA > 0 )

#    ifdef _PTHREADS
    template <bool threads, int inst>
    pthread_mutex_t
    __alloc<threads, inst>::__node_allocator_lock
    = PTHREAD_MUTEX_INITIALIZER;
#    endif

#     ifdef __STL_SGI_THREADS
    template <bool threads, int inst>
    volatile unsigned long
    __alloc<threads, inst>::__node_allocator_lock = 0;
#     endif

    template <bool threads, int inst>
    char *__alloc<threads, inst>::start_free = 0;

    template <bool threads, int inst>
    char *__alloc<threads, inst>::end_free = 0;

    template <bool threads, int inst>
    vcl_size_t __alloc<threads, inst>::heap_size = 0;

    template <bool threads, int inst>
    typename __alloc<threads, inst>::obj * __VOLATILE
    __alloc<threads, inst>::free_list[
#       if ! (defined ( __SUNPRO_CC ) || defined ( _AIX ))
          __alloc<threads, inst>::__NFREELISTS]
#       else
    __NFREELISTS]
#       endif
     = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
    // The 16 zeros are necessary to make version 4.1 of the SunPro
    // compiler happy.  Otherwise it appears to allocate too little
    // space for the array.

#       ifdef __STL_WIN32THREADS
    template <bool threads, int inst>
    __stl_critical_section_wrapper
    __alloc<threads, inst>::__node_allocator_lock;
#       endif
#     else /* ( __STL_STATIC_TEMPLATE_DATA > 0 ) */
    __DECLARE_INSTANCE(char *, single_client_alloc::start_free,0);
    __DECLARE_INSTANCE(char *, single_client_alloc::end_free,0);
    __DECLARE_INSTANCE(vcl_size_t, single_client_alloc::heap_size,0);
#       if defined ( __SUNPRO_CC ) || defined ( _AIX )
    __DECLARE_INSTANCE(single_client_alloc::obj * __VOLATILE,
                       single_client_alloc::free_list[__NFREELISTS],
                       {0});
#       else
    __DECLARE_INSTANCE(single_client_alloc::obj * __VOLATILE,
                       single_client_alloc::free_list[single_client_alloc::__NFREELISTS],
                       {0});
#       endif
    __DECLARE_INSTANCE(char *, multithreaded_alloc::start_free,0);
    __DECLARE_INSTANCE(char *, multithreaded_alloc::end_free,0);
    __DECLARE_INSTANCE(vcl_size_t, multithreaded_alloc::heap_size,0);
#       if defined ( __SUNPRO_CC ) || defined ( _AIX )
    __DECLARE_INSTANCE(multithreaded_alloc::obj * __VOLATILE,
                       multithreaded_alloc::free_list[__NFREELISTS],
                       {0});
#       else
    __DECLARE_INSTANCE(multithreaded_alloc::obj * __VOLATILE,
                       multithreaded_alloc::free_list[multithreaded_alloc::__NFREELISTS],
                       {0});
#       endif
#       ifdef __STL_WIN32THREADS
          __DECLARE_INSTANCE(__stl_critical_section_wrapper,
                             single_client_alloc::__node_allocator_lock,
                             __stl_critical_section_wrapper());
          __DECLARE_INSTANCE(__stl_critical_section_wrapper,
                             multithreaded_alloc::__node_allocator_lock,
                             __stl_critical_section_wrapper());
#       endif
#       ifdef _PTHREADS
           __DECLARE_INSTANCE(pthread_mutex_t,
                              single_client_alloc::__node_allocator_lock,
                              PTHREAD_MUTEX_INITIALIZER);
           __DECLARE_INSTANCE(pthread_mutex_t,
                              multithreaded_alloc::__node_allocator_lock,
                              PTHREAD_MUTEX_INITIALIZER);
#       endif
#       ifdef __STL_SGI_THREADS
           __DECLARE_INSTANCE(volatile unsigned long,
                              single_client_alloc::__node_allocator_lock,
                              0);
           __DECLARE_INSTANCE(volatile unsigned long,
                              multithreaded_alloc::__node_allocator_lock,
                              0);
#       endif

#   endif /* __STL_STATIC_TEMPLATE_DATA */

#  endif /* ! __STL_USE_MALLOC */
# endif /* ! __STL_USE_NEWALLOC */

# if defined ( __STL_USE_DEFALLOC )
#  include "vcl_defalloc.h"
# endif

// A dummy symbol to avoid missing symbol warnings from ranlib
void vcl_alloc_dummy_to_avoid_ranlib_warning() {}

#endif // vcl_emulation_alloc_h