1515981887637214.doc

fdcgvbdfgfdgdfgfdgdfgdfgdfgdfg

 author : Hou Jie (侯捷)
 date : 2015/11/11 
 compiler : DevC++ 5.61 (MinGW with GNU 4.9.2)

 說明:這是侯捷 E-learning video "C++內存管理" 的實例程式.

 filename : allocc.h
 取材自 SGI STL 2.91 <stl_alloc.h>, 移植至 C language.
#include <stdlib.h>  for malloc(),realloc()
#include <stddef.h>  for size_t
#include <memory.h>  for memcpy()
#define THROW_BAD_ALLOC   cerr << "out of memory" << endl; exit(1)
#define THROW_BAD_ALLOC   exit(1)———————————————-
 第1級配置器。
———————————————-

void (*oom_handler)() = 0;
void* oom_malloc(size_t n)
{
  void (*my_malloc_handler)();
  void* result;

  for (;;) {    不斷嘗試釋放、配置、再釋放、再配置…
    my_malloc_handler = oom_handler;
    if (0 == my_malloc_handler) { THROW_BAD_ALLOC; }
    (*my_malloc_handler)();    呼叫處理常式,企圖釋放記憶體
    result = malloc(n);        再次嘗試配置記憶體
    if (result) return(result);
  }
}

void* oom_realloc(void *p, size_t n)
{
  void (*my_malloc_handler)();
  void* result;
  for (;;) {    不斷嘗試釋放、配置、再釋放、再配置…
    my_malloc_handler = oom_handler;
    if (0 == my_malloc_handler) { THROW_BAD_ALLOC; }
    (*my_malloc_handler)();    呼叫處理常式,企圖釋放記憶體。
    result = realloc(p, n);    再次嘗試配置記憶體。
    if (result) return(result);
  }
}
void* malloc_allocate(size_t n)
{
  void *result = malloc(n);   直接使用 malloc()
  if (0 == result) result = oom_malloc(n);
  return result;
}
void malloc_deallocate(void* p, size_t n)
{
  free(p);  直接使用 free()
}
void* malloc_reallocate(void *p, size_t old_sz, size_t new_sz)
{
  void* result = realloc(p, new_sz); 直接使用 realloc()
  if (0 == result) result = oom_realloc(p, new_sz);
  return result;
}
void (*set_malloc_handler(void (*f)()))()
{ 類似 C++ 的 set_new_handler().
  void (*old)() = oom_handler;
  oom_handler = f;
  return(old);
}
———————————————-
第二級配置器
———————————————-
enum {ALIGN = 8};                        小區塊的上調邊界
enum {MAX_BYTES = 128};                  小區塊的上限
enum {NFREELISTS = MAX_BYTES/ALIGN}; free-lists 個數
 union obj {                   G291[o],CB5[x],VC6[x]
   union obj* free_list_link;  這麼寫在 VC6 和 CB5 中也可以,
 };                            但以後就得使用 "union obj" 而不能只寫 "obj"
typedef struct obj {
  struct obj* free_list_link;
} obj;
char*   start_free = 0;
char*   end_free = 0;
size_t  heap_size = 0;
obj* free_list[NFREELISTS]
     = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
size_t ROUND_UP(size_t bytes) {
    return (bytes) + ALIGN-1) & ~(ALIGN - 1;
}
size_t FREELIST_INDEX(size_t bytes) {
    return (bytes) + ALIGN-1)/ALIGN - 1);
}
———————————————-
 We allocate memory in large chunks in order to
 avoid fragmentingthe malloc heap too much.
 We assume that size is properly aligned.

 Allocates a chunk for nobjs of size "size".
 nobjs may be reduced if it is inconvenient to
 allocate the requested number.
———————————————-
char* chunk_alloc(size_t size, int& nobjs)  G291[o],VC6[x],CB5[x]
char* chunk_alloc(size_t size, int* nobjs)
{
  char* result;
  size_t total_bytes = size * (*nobjs);   原 nobjs 改為 (*nobjs)
  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;         原 nobjs 改為 (*nobjs)
      total_bytes = size * (*nobjs);      原 nobjs 改為 (*nobjs)
      result = start_free;
      start_free += total_bytes;
      return(result);
  } else {
      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) {
          int i;
          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 (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 list.
              }
          }
          end_free = 0;       In case of exception.
          start_free = (char*)malloc_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 list. We assume that n is properly aligned.
 We hold the allocation lock.
———————————————-
void* refill(size_t n)
{
    int nobjs = 20;
    char* chunk = chunk_alloc(n,&nobjs);
    obj* volatile *my_free_list;   obj my_free_list;
    obj* result;
    obj* current_obj;
    obj* next_obj;
    int i;

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

    Build free list in chunk
    result = (obj*)chunk;
    *my_free_list = next_obj = (obj*)(chunk + n);
    for (i=1;  ; ++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);
}
———————————————-

———————————————-
void* allocate(size_t n)  n must be > 0
{
  obj* volatile *my_free_list;    obj my_free_list;
  obj* result;

  if (n > (size_t)MAX_BYTES) {
      return(malloc_allocate(n));
  }

  my_free_list = free_list + FREELIST_INDEX(n);
  result = *my_free_list;
  if (result == 0) {
      void* r = refill(ROUND_UP(n));
      return r;
  }

  *my_free_list = result->free_list_link;
  return (result);
}
———————————————-

———————————————-
void deallocate(void *p, size_t n)  p may not be 0
{
  obj* q = (obj*)p;
  obj* volatile *my_free_list;   obj** my_free_list;

  if (n > (size_t) MAX_BYTES) {
      malloc_deallocate(p, n);
      return;
  }
  my_free_list = free_list + FREELIST_INDEX(n);
  q->free_list_link = *my_free_list;
  *my_free_list = q;
}
———————————————-

———————————————-
void* reallocate(void *p, size_t old_sz, size_t new_sz)
{
  void * result;
  size_t copy_sz;

  if (old_sz > (size_t) MAX_BYTES && new_sz > (size_t) 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;
  memcpy(result, p, copy_sz);
  deallocate(p, old_sz);
  return(result);
}
———————————————-