本文共 7312 字，大约阅读时间需要 24 分钟。
SGI STL有两级配置器：
第一级配置器的allocate() 和 realloc()都是在调用malloc() 和 realloc()不成功后，改调用oom_malloc() 和 oom_realloc()，后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存来完成任务，但如果“内存不足处理例程”未被客端设定，oom_malloc() 和 oom_realloc()便调用__THROW_BAD_ALLOC，丢出bad_alloc异常信息，或利用exit(1)终止程序；
第二级配置器多了一些机制，避免太多小额区块造成内存的碎片：
以下代码为简单实现：
第一级配置器头文件：malloc_alloc.h
#ifndef MALLOC_ALLOC_H#define MALLOC_ALLOC_H#includeclass malloc_alloc{private: //这两个函数处理内存不足的情况 static void* oom_malloc(size_t n); static void* oom_realloc(void* p, size_t n);public: static void* allocate(size_t n){ void* result = malloc(n); if (result == 0)result = oom_malloc(n); return result; } static void deallocate(void* p, size_t n){ free(p); //n 其实完全没有用上 } static void* reallocate(void* p, size_t old_sz, size_t new_sz){ void* result = realloc(p, new_sz); if (result == 0)result = oom_realloc(p, new_sz); return result; }};#endif
第一级配置器头文件：malloc_alloc.cpp
#include"malloc_alloc.h"#includevoid* malloc_alloc::oom_malloc(size_t n){ void* result = 0; int i = 0, j = 0; //不停的尝试释放，配置，再释放，再配置 for (; i < 100000; i++){ j = 0; while (j < 100000)j++; result = malloc(n); if (result)return result; } std::cout << "malloc error!" << std::endl; return 0;}void* malloc_alloc::oom_realloc(void* p, size_t n){ void* result = 0; int i = 0, j = 0; for (; i < 100000; i++){ j = 0; while (j < 100000)j++; result = realloc(p, n); if (result)return result; } std::cout << "realloc error!" << std::endl; return 0;}
第二级配置器头文件：memorypool.h
#ifndef _MEMORYPOOL_H#define _MEMORYPOOL_H#includeusing namespace std;enum {ALIGN = 8}; //小型区块的上调边界enum {MAX_BYTES = 128}; //小型区块的上限enum {NUMFREELISTS = MAX_BYTES / ALIGN}; //freelists个数//内存池class Alloc{private: //freelist的节点构造 union obj{ union obj* free_list_link; char client_data[1]; };private: //16个freelists static obj* volatile free_list[NUMFREELISTS]; //以下函数根据区块的大小，决定使用第n号free_list，n从0开始 static size_t FREELIST_INDEX(size_t bytes){ return ((bytes + ALIGN - 1) / ALIGN - 1); } //将bytes上调至8的倍数 static size_t ROUND_UP(size_t bytes){ return (((bytes)+ALIGN - 1) & ~(ALIGN - 1)); } //返回一个大小为n的对象，并可能加入大小为n的其他区块到free_list static void* refill(size_t n); //配置一大块区间，可容纳nobjs个大小为size的区块，如果修饰nobjs个区块无法满足， //nobjs可能会降低 static char* chunk_alloc(size_t size, int& nobjs); //区块的状态 static char* start_free; //内存池的起始地址 static char* end_free; //内存池的结束地址 static size_t heap_size; public: static void* allocate(size_t n); //分配指定大小的内存 static void deallocate(void* p, size_t n); //回收指定内存 static void* reallocate(void* p, size_t old_sz, size_t new_sz); //重新分配内存};#endif
第二级配置器头文件：alloc.cpp
#include"malloc_alloc.h"#include"memorypool.h"//static成员的初值设定char* Alloc::start_free = NULL;char* Alloc::end_free = NULL;size_t Alloc::heap_size = 0;Alloc::obj* volatile Alloc::free_list[NUMFREELISTS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };//分配内存void* Alloc::allocate(size_t n){ obj* volatile *my_free_list; obj* result; //大于128就调用malloc_alloc if (n > 128)return malloc_alloc::allocate(n); //寻找16个free_list中最合适的一个 my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list; if (result == 0){ //没有可用的free_list，准备重新填充free_list void* r = refill(ROUND_UP(n)); return r; } //调整free_list *my_free_list = result->free_list_link; return result;}//释放内存void Alloc::deallocate(void* p, size_t n){ obj* q = (obj*)p; obj* volatile* my_free_list; //大于128就调用malloc_deallocate if (n > 128){ malloc_alloc::deallocate(p, n); return; } //寻找对应的区块 my_free_list = free_list + FREELIST_INDEX(n); q->free_list_link = *my_free_list; *my_free_list = q;}//返回一个大小为n的对象，并且有时候会为适当的free_list增加节点，假设n已经适当上调至8的倍数void* Alloc::refill(size_t n){ int nobjs = 3; //调用chunk_alloc()，尝试取得nobjs个区块作为free_list的新节点，注意参数nobjs是pass by reference char* chunk = chunk_alloc(n, nobjs); obj* volatile* my_free_list; obj* result; obj *current_obj, *next_obj; int i; //如果只获得一个区块，这个区块就分配给调用者，free_list无新节点 if (nobjs == 1)return (chunk); //否则准备调整free_list，纳入新节点 my_free_list = free_list + FREELIST_INDEX(n); result = (obj*)chunk; //这一块准备返回给客户端 //以下导引free_list指向新分配的空间（取自内存池） *my_free_list = next_obj = (obj*)(chunk + n); //以下将free_list的各节点串接起来 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;}//内存池配置内存//调用chunk_alloc()，尝试取得nobjs个区块作为free_list的新节点//注意参数nobjs是pass by referencechar* Alloc::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); } else if (bytes_left >= size){ //内存池剩余空间不能满足总的需求量，但足够供应大于等于1个的区块 nobjs = bytes_left / size; total_bytes = size * nobjs; result = start_free; start_free += total_bytes; return result; } else{ //内存池剩余空间连一个区块的大小都无法提供s size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); //以下试着让内存池的残余零头还要利用价值 //首先寻找释放的free_list if (bytes_left > 0){ obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left); //调整free_list，将内存池中的剩余空间插入 ((obj*)start_free)->free_list_link = *my_free_list; *my_free_list = (obj*)start_free; } //配置heap空间，用来补充内存池 start_free = (char*)malloc(bytes_to_get); if (start_free == 0){ //heap空间不足，malloc失败 int i; obj* volatile *my_free_list, *p; //以下搜寻适当的free_list //所谓适当是指“尚有未用区块，且区块够大”的free_list for (i = size; i <= MAX_BYTES; i += ALIGN){ my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (p != 0){ *my_free_list = p->free_list_link; start_free = (char*)p; end_free = start_free + i; //递归调用自己，为了修正nobjs return (chunk_alloc(size, nobjs)); } } end_free = 0; start_free = (char*)malloc_alloc::allocate(bytes_to_get); } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; //递归调用自己，为了修正nobjs return (chunk_alloc(size, nobjs)); }} 测试文件：main.cpp
#include"memorypool.h"#includeint main(){ Alloc pool; int* p = (int*)pool.allocate(sizeof(int)* 10); if (p == 0)cout << "allocate error." << endl; for (int i = 0; i < 10; i++)p[i] = i; for (int i = 0; i < 10; i++)cout << p[i] << " "; cout << endl; pool.deallocate(p, 40); system("pause"); return 0;}
转载地址：http://baxei.baihongyu.com/