STL内存管理的C实现

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

}