当free list中没有可用区块时，调用refill()为free list填充空间，新的空间取自内存池（由chunk_alloc()完成）。如果内存池不够，则malloc之，如果系统heap空间也不够，chunk_alloc()就寻找还有空闲区块的free list并将其内存充公，如果还是不够就调用第一级配置器。第一级配置器有实现new-handler机制，内存不够会抛出异常。
#ifndef _DEFAULT_ALLOC_H
#define _DEFAULT_ALLOC_H
namespace Chenstl{
//使用内存池以减少碎片
class default_alloc {
private:
enum { ALIGN = 8};
enum { MAX_BYTES = 128 };
enum { NFREELISTS = 16 };
//static const int ALIGN = 8;
//static const int MAX_BYTES = 128;
//static const int NFREELISTS = 16; //MAX_BYTES/ALIGN
union obj { //free-lists的节点构造
union obj *next;
char client[1];
};
//freelist
static obj *free_list[NFREELISTS];
static char *start_free; //内存池的起始位置
static char *end_free; //内存池的终止位置
static size_t heap_size;
private:
//将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes) {
return ((bytes +ALIGN - 1) & ~(ALIGN - 1));
}
//获取合适的区块在freelist中的位置
static size_t FREELIST_INDEX(size_t __bytes) {
return (((__bytes)+(size_t)ALIGN - 1) / (size_t)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);
public:
static void *allocate(size_t n);
static void deallocate(void *p, size_t n);
static void *realloc(void *p, size_t old_sz, size_t new_sz);
};
}
#endif
default_alloc.h
---------------------------------------------------------
#include "default_alloc.h"
#include "malloc_alloc.h"
using namespace Chenstl;
default_alloc::obj *default_alloc::free_list[NFREELISTS]
= { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
char *default_alloc::start_free = 0; //内存池的起始位置
char *default_alloc::end_free = 0; //内存池的终止位置
size_t default_alloc::heap_size = 0;
void *default_alloc::allocate(size_t n)
{
obj *result = 0;
obj **my_free_list = 0;
if (n > MAX_BYTES)
return malloc_alloc::allocate(n);
//寻找free lists中合适的一个
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(0 == result)
{//没有找到可用的freelist，从内存池里取出空间
return refill(ROUND_UP(n));
}
//调整freelist
*my_free_list = result->next;
return result;
}
void default_alloc::deallocate(void *p, size_t n)
{
}
//返回一个大小为n的对象，并可能加入大小为n的其他区块到freelist
//在ANSI c中，void *不允许进行加减操作，所以chunk用char *
void *default_alloc::refill(size_t n)
{
int objs = 20;
char *chunk = chunk_alloc(n, objs);
obj *next, *current;
obj *result;
obj **my_free_list;
if (1 == objs) //只取出一个区块
return chunk;
my_free_list = free_list + FREELIST_INDEX(n);
result = (obj *)chunk; //这一块返回给客户端
//将freellist指向分配的区域
*my_free_list = next = (obj *)chunk + n;
for (int i = 1;; i++)
{
current = next;
next = (obj *)((char *)next + n); //这里注意不能直接用next+n
if (i == objs - 1)
{
current->next = 0;
break;
}
else
current->next = next;
}
return result;
}