STL内存管理的C实现-阿里云开发者社区

STL内存管理的C实现

2012-01-10 616

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： //STL 内存管理器的C实现 #include stdio.h> #include stdlib.h> #define __ALIGN 8 //小型区块上调边界 #define __MAX_BYTES 128 //小型区块大小的上限 ...

//STL 内存管理器的C实现
#include stdio.h>
#include stdlib.h>
#define __ALIGN 8 //小型区块上调边界
#define __MAX_BYTES 128 //小型区块大小的上限
#define __NFREELISTS (__ALIGN/__MAX_BYTES) //free-lists的个数
typedef union obj{
union obj *free_list_link;
char client_data[1];
}obj;
obj *free_list[__NFREELISTS];
char *start_free; //mempool开始位置
char *end_free; //mempool结束位置
size_t heapsize;
size_t ROUND_UP(size_t bytes);
size_t FREELIST_INDEX(size_t bytes);
void *stl_malloc(size_t nbytes);
void stl_free(void *p, size_t nbytes);
void *refill(size_t n);
char *chunk_alloc(size_t bytes, size_t *nobjs);
int main(){
int len= 65;
void *ptr = stl_malloc(len);
printf("%p\n", ptr);
stl_free(ptr, len);
return 0;
}
//将bytes上调到__ALIGN的倍数
size_t ROUND_UP(size_t bytes){
return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
}
//返回bytes所对应的freelist索引号
size_t FREELIST_INDEX(size_t bytes){
return ((bytes + __ALIGN - 1) / __ALIGN - 1);
}
void *stl_malloc(size_t nbytes){
if(nbytes > 128){
return malloc(nbytes);
}
obj **my_free_list;
obj *result;
my_free_list = free_list + FREELIST_INDEX(nbytes);
result = *my_free_list;
if(result == NULL){
void *r = refill(ROUND_UP(nbytes));
return r;
}
//取出空闲块
*my_free_list = result->free_list_link;
return result;
}
void stl_free(void *p, size_t nbytes){
obj *q = (obj *)p;
obj **my_free_list;
if(nbytes > (size_t)__MAX_BYTES){
free(p);
return;
}
my_free_list = free_list + FREELIST_INDEX(nbytes);
q->free_list_link = *my_free_list;
*my_free_list = q;
}
void *refill(size_t n){
//默认从内存池取得20个块，多个块构成一个chunk
size_t nobjs = 20; //值-结果参数
char *chunk = chunk_alloc(n, &nobjs);
if(!chunk){
return NULL;
}
obj **my_free_list;
obj *result, *cur_obj, *next_obj;
int i;
//内存池空间告急仅返回一个块，则直接返回给用户
if(nobjs == 1){
return chunk;
}
//否则准备向free_list中纳入新的节点
my_free_list = free_list + FREELIST_INDEX(n);
//以下在chunk的连续空间上建立free_list
result = (obj *)chunk; //此块返回给用户
*my_free_list = next_obj = (obj *)(chunk + n);
for(i = 1; ; i++){
cur_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if(nobjs - 1 == i){
cur_obj->free_list_link = NULL;
break;
}else{
cur_obj->free_list_link = next_obj;
}
}
return result;
}
//从内存池取连续的块空间
char *chunk_alloc(size_t bytes, size_t *nobjs){
char *result;
size_t total_bytes = bytes * (*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 >= bytes){
//不够分配全部的，但是还可以分配一个或多个块
*nobjs = bytes_left/bytes;
total_bytes = *nobjs * bytes;
result = start_free;
start_free += total_bytes;
return result;
}else{
//内存池黔驴技穷了，连一个块的空间都没有了
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heapsize >> 4);
if(bytes_left > 0){
//内存池中还有一些零头，先配给适当的free-list
obj **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(start_free == NULL){
//看看更大块的free_list有无可用块
int i;
obj **my_free_list, *p;
for(i = bytes; i = __MAX_BYTES; i += __ALIGN){
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if(p){
*my_free_list = p->free_list_link;
start_free = (char *)p;
end_free = start_free + i;
//递归调用自己，按新的状态重新分配，并修正nobjs;
return chunk_alloc(bytes, nobjs);
}
}
//实在没有空间了
end_free = 0;
return NULL;
}
heapsize += bytes_to_get;
end_free = start_free + bytes_to_get;
return chunk_alloc(bytes, nobjs);
}
}

文章标签：

C++

STL内存管理的C实现

热门文章

最新文章

相关电子书