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);
}
