SGI STL 内存池

// mem_pool.h

#ifndef mem_pool_h
#define mem_pool_h

#pragma once

#define ALIGN     512
#define MAX_BLOCK_SIZE   20 * 1024
#define BLOCK_LIST_NUM   MAX_BLOCK_SIZE / ALIGN

class mem_pool
{
 CRITICAL_SECTION alloc_lock;
 union obj{
  union obj* free_list_link;
  char client_data[1];
 };
 obj* free_list [BLOCK_LIST_NUM];

 static inline size_t round_up(size_t bytes){
  return (bytes + ALIGN - 1) & ~(ALIGN - 1);
 }

 static inline size_t free_list_index(size_t bytes){
  return (bytes + ALIGN - 1) / ALIGN - 1;
 }

 char* start_free;
 char* end_free;
 size_t heap_size;

 char* chunk_alloc(size_t size, int& nobjs);
 void* refill(size_t n);
public:
 mem_pool(void);
 ~mem_pool(void);

 void* allocate(size_t n);
 void deallocate(void* p, size_t n);
 inline size_t mem_size(){return heap_size;}
};

#endif

// mem_pool.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "mem_pool.h"

mem_pool::mem_pool(void){
 InitializeCriticalSection(&alloc_lock);
 heap_size = 0;
 start_free = 0;
 end_free = 0;
 memset(free_list, 0, sizeof(free_list));
}

mem_pool::~mem_pool(void){
 DeleteCriticalSection(&alloc_lock);
}

char* mem_pool::chunk_alloc(size_t size, int& nobjs){
 char* result;
 size_t total_bytes = size * nobjs;
 size_t bytes_left = end_free - start_free;

 if(bytes_left >= total_bytes){
  result = start_free;
  start_free += total_bytes;
  return result;
 }

 if(bytes_left >= size){
  nobjs = bytes_left / size;
  total_bytes = size * nobjs;
  result = start_free;
  start_free += total_bytes;
  return result;
 }

 if(bytes_left > 0){
  obj **my_free_list = free_list + free_list_index(bytes_left);
  ((obj*) start_free)->free_list_link = *my_free_list;
  *my_free_list = (obj*) start_free;
 }

 size_t bytes_to_get = 2 * total_bytes + round_up(heap_size >> 4);
 start_free = (char *) malloc(bytes_to_get);

 if(start_free != 0){
  heap_size += bytes_to_get;
  end_free = start_free + bytes_to_get;
  return chunk_alloc(size, nobjs);
 }

 int i = free_list_index(size) + 1;
 obj **my_free_list, *p;
 for(; i < BLOCK_LIST_NUM;  ++i){
  my_free_list = free_list + i;
  p = *my_free_list;

  if(0 != p){
   *my_free_list = p->free_list_link;
   start_free = (char *) p;
   end_free = start_free + (i + 1) * ALIGN;
   return chunk_alloc(size, nobjs);
  }
 }

 end_free = 0;
 return 0;
}

void* mem_pool::refill(size_t n){
 int nobjs = 20;
 char* chunk = chunk_alloc(n, nobjs);
 obj** my_free_list;
 obj* result;
 obj *current_obj, *next_obj;
 int i;

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

 result = (obj *) chunk;
 -- nobjs;
 *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 == i){
   current_obj->free_list_link = 0;
   break;
  }
  current_obj->free_list_link = next_obj;
 }

 return result;
}

void* mem_pool::allocate(size_t n){
 obj** my_free_list;
 obj* result;

 if(n <= 0) return 0;
 if(n > MAX_BLOCK_SIZE)
  return malloc(n);

 EnterCriticalSection(&alloc_lock);
 try{
  my_free_list = free_list + free_list_index(n);
  result = *my_free_list;
  if(result == 0){
   result = (obj *) refill(round_up(n));
  }else{
   *my_free_list = result->free_list_link;
  }
 }catch(...){
  result = 0;
 }
 LeaveCriticalSection(&alloc_lock);

 return result;
}

void mem_pool::deallocate(void* p, size_t n){
 obj *q = (obj *)p;
 obj** my_free_list;

 if(n > MAX_BLOCK_SIZE){
  free(p);
  return;
 }

 my_free_list = free_list + free_list_index(n);

 EnterCriticalSection(&alloc_lock);
 q->free_list_link = *my_free_list;
 *my_free_list = q;
 LeaveCriticalSection(&alloc_lock);