STL空间配置器的强大和借鉴作用不言而喻，查阅资料，发现了Dawn_sf已经对其有了极其深入和详细的描述，所以决定偷下懒借用其内容，只提供自己实现STL空间配置器的源码，具体解析内容参考：
（一）STL — 浅析一级空间配置器
（二）STL — 浅析二级空间配置器
1. 一级空间配置器实现
1.1 接口
// 完全解析STL空间配置器
/***** 一级配置区 ****************************/
// 1. 采用mallo/relloc/free申请和释放内存
// 2. 处理内存申请失败的处理
// (1)设置set_new_handle，若为NULL抛出__THROW_BAD_ALLOC;
// (2)尝试重复申请
/**********************************************/
#pragma once
class CFirstLevelAlloc;
class CSecondLevelAlloc;
#ifdef _CHUNK_ALLOC
typedef CFirstLevelAlloc SelfAlloc;
#else
typedef CSecondLevelAlloc SelfAlloc;
#endif
typedef void(*CallBackFunc)();
class CFirstLevelAlloc
{
public:
CFirstLevelAlloc();
static CallBackFunc m_CallBackFunc;
static void* Allocate(size_t nSize);
static void* Allocate(void *p, size_t nSize);
static void Deallocate(void *p, size_t nSize = 0);
static void SetCallBackHandle(CallBackFunc cb);
private:
static void* ReAllocate(size_t nSize);
static void* ReAllocate(void *p, size_t nSize);
};
enum {ALIGN = 8}; // 小型区块的上调边界
enum {MAX_BYTES = 128}; // 小型区块的上限
enum {FREELISTNUM = MAX_BYTES/ALIGN}; // free-lists个数
// 空闲内存链表结构
union FreeList
{
union FreeList *pFreeList;
char client_data[1];
};
1.2 实现
#include "stdio.h"
#include "alloc_define.h"
#include <stdlib.h>
#include <iostream>
using namespace std;
CallBackFunc CFirstLevelAlloc::m_CallBackFunc = NULL;
CFirstLevelAlloc::CFirstLevelAlloc()
{
}
void* CFirstLevelAlloc::Allocate(size_t nSize)
{
void *result = malloc(nSize);
if (NULL == result)
{
result = ReAllocate(nSize);
}
return result;
}
void* CFirstLevelAlloc::Allocate(void *p, size_t nSize)
{
void *result = realloc(p, nSize);
if (NULL == result)
{
result = ReAllocate(p, nSize);
}
return result;
}
void* CFirstLevelAlloc::ReAllocate(size_t nSize)
{
while (1)
{
if (NULL == m_CallBackFunc)
{
cout << "bad alloc!" << endl;
return NULL;
}
else
{
m_CallBackFunc();
void *result = Allocate(nSize);
if (result)
{
return result;
}
}
}
}
void* CFirstLevelAlloc::ReAllocate(void *p, size_t nSize)
{
while (1)
{
if (NULL == m_CallBackFunc)
{
cout << "bad alloc!" << endl;
return NULL;
}
else
{
m_CallBackFunc();
void *result = Allocate(p, nSize);
if (result)
{
return result;
}
}
}
}
void CFirstLevelAlloc::Deallocate(void *p, size_t nSize)
{
free(p);
}
void CFirstLevelAlloc::SetCallBackHandle(CallBackFunc cb)
{
m_CallBackFunc = cb;
}
2. 二级空间配置器实现
2.1 接口
class CSecondLevelAlloc
{
public:
CSecondLevelAlloc();
static void* Allocate(size_t nSize);
static void Deallocate(void *p, size_t nSize);
static void SetCallBackHandle(CallBackFunc cb);
private:
static size_t FreeListIndex(int nBytes); // 根据区块大小得到freelist索引
static size_t Round_Up(int nBytes); // 将bytes按内存对齐上调至ALIGN的倍数
static char *ChunkAlloc(size_t nSize, int& nObjs);
static void* Refill(size_t nSize);
private:
static FreeList *m_pFreeList[FREELISTNUM];
static char *m_pStartFree;
static char *m_pEndFree;
static size_t m_nHeapSize;
};
2.2 实现
FreeList* CSecondLevelAlloc::m_pFreeList[FREELISTNUM] = { 0 };
char* CSecondLevelAlloc::m_pStartFree = NULL;
char* CSecondLevelAlloc::m_pEndFree = NULL;
size_t CSecondLevelAlloc::m_nHeapSize = 0;
CSecondLevelAlloc::CSecondLevelAlloc()
{
}
void* CSecondLevelAlloc::Allocate(size_t nSize)
{
// 首先判断nSize，若大于128则调用一级配置器，否则调用二级配置器
if (nSize > (size_t)MAX_BYTES)
{
cout << "调用1级配置器配置内存空间,空间大小：" << nSize << endl;
return (CFirstLevelAlloc::Allocate(nSize));
}
cout << "调用2级配置器配置内存空间,空间大小：" << nSize << endl;
FreeList **pFreeList = m_pFreeList + FreeListIndex(nSize);
if (*pFreeList == NULL)
{
return Refill(Round_Up(nSize));
}
FreeList *p = *pFreeList;
*pFreeList = p->pFreeList;
return p;
}
void CSecondLevelAlloc::Deallocate(void *p, size_t nSize)
{
// 首先判断nSize，若大于128则调用一级配置器，否则调用二级配置器
if (nSize > MAX_BYTES)
{
cout << "调用1级配置器释放内存空间,空间大小：" << nSize << endl;
return CFirstLevelAlloc::Deallocate(p);
}
cout << "调用2级配置器释放内存空间,空间大小：" << nSize << endl;
FreeList **pFreeList = m_pFreeList + FreeListIndex(Round_Up(nSize));
((FreeList*)p)->pFreeList = *pFreeList;
*pFreeList = (FreeList*)p;
}
size_t CSecondLevelAlloc::FreeListIndex(int nBytes)
{
return ((nBytes + ALIGN) / ALIGN - 1);
}
size_t CSecondLevelAlloc::Round_Up(int nBytes)
{
return ((nBytes + ALIGN - 1) & (~(ALIGN - 1)));
}
char* CSecondLevelAlloc::ChunkAlloc(size_t nSize, int& nObjs)
{
char *pResult = NULL;
size_t nTotalBytes = nSize * nObjs;
size_t nBytesLeft = m_pEndFree - m_pStartFree;
if (nBytesLeft >= nTotalBytes)
{
// 内存池剩余空间完全满足需求量
pResult = m_pStartFree;
m_pStartFree += nTotalBytes;
return pResult;
}
else if (nBytesLeft >= nSize)
{
// 内存池剩余空间不能完全满足需求量，但足够供应一个或一个以上的区块
nObjs = nBytesLeft / nSize;
pResult = m_pStartFree;
m_pStartFree += (nObjs * nSize);
return pResult;
}
else
{
// 内存池剩余空间连一个区块的大小都无法提供,就调用malloc申请内存，新申请的空间是需求量的两倍
// 与随着配置次数增加的附加量，在申请之前，将内存池的残余内存回收
size_t nBytesToGet = 2 * nTotalBytes + Round_Up(m_nHeapSize >> 4);
// 以下试着让内存池中的残余零头还有价值
if (nBytesLeft > 0)
{
// 内存池内还有一些零头，先配给适当的freelist
// 首先寻找适当的freelist
FreeList *pFreeList = m_pFreeList[FreeListIndex(nBytesLeft)];
// 调整freelist,将内存池中的残余空间编入
((FreeList*)m_pStartFree)->pFreeList = pFreeList;
pFreeList = (FreeList*)m_pStartFree;
}
// 配置heap空间
m_pStartFree = (char *)malloc(nBytesToGet);
if (NULL == m_pStartFree)
{
//如果没有申请成功，如果free_list当中有比n大的内存块，这个时候将free_list中的内存块释放出来.
//然后将这些内存编入自己的free_list的下标当中.调整nobjs.
int i;
FreeList **pFreeList, *p;
for (i = nSize; i < MAX_BYTES; i += ALIGN)
{
pFreeList = m_pFreeList+FreeListIndex(i);
p = *pFreeList;
if (NULL != p)
{
// freelist内尚有未用区块
// 调整freelist以释放未用区块
*pFreeList = p->pFreeList;
m_pStartFree = (char *)p;
m_pEndFree = m_pStartFree + i;
// 调整自己，为了修正nobjs
return (ChunkAlloc(nSize, nObjs));
}
}
m_pEndFree = NULL; // 如果出现意外（山穷水尽，到处都没有内存可用）
// 调用1级配置器，看out-of-range机制能不能出点力
m_pStartFree = (char*)CFirstLevelAlloc::Allocate(nBytesToGet);
}
m_nHeapSize += nBytesToGet;
m_pEndFree = m_pStartFree + nBytesToGet;
return (ChunkAlloc(nSize, nObjs));
}
}
// 当freelist中没有可用的区块了时，就调用ReFill重新填充空间
// 新的空间将取自内存池，缺省为20个新节点
// 但万一内存池空间不足，获得的节点数可能小于20
void* CSecondLevelAlloc::Refill(size_t nSize)
{
int nObjs = 20; // 默认每个链表组右20个区块
char *pChunk = ChunkAlloc(nSize, nObjs);
if (1 == nObjs)
{
// 如果获得一个区块，这个区块就分配给调用者，freelist无新节点
return pChunk;
}
// 若有多余的区块，则将其添加到对应索引的freelist中
FreeList **pFreeList = m_pFreeList + FreeListIndex(nSize);
FreeList *pResult = (FreeList *)pChunk; // 这一块准备返回给客户端
FreeList *pCurrent = NULL;
FreeList *pNext = NULL;
*pFreeList = pNext = (FreeList*)(pChunk + nSize);
for (int i = 1; i < nObjs; i++)
{
pCurrent = pNext;
pNext = (FreeList*)((int)pNext + nSize);
pCurrent->pFreeList = pNext;
}
pCurrent->pFreeList = NULL;
return pResult;
}
void CSecondLevelAlloc::SetCallBackHandle(CallBackFunc cb)
{
CFirstLevelAlloc::m_CallBackFunc = cb;
}
3. 配置器标准接口
#pragma once
#include "alloc_define.h"
template<typename T, typename Alloc = SelfAlloc>
class CSimpleAlloc
{
public:
static T* Allocate(size_t n)
{
if (n == 0)
{
return NULL;
}
return (T *)Alloc::Allocate(n * sizeof(T));
}
static T* Allocate(void)
{
return (T *)Alloc::Allocate(sizeof(T));
}
static void Deallocate(T *p, size_t n)
{
if (n != 0)
{
Alloc::Deallocate(p, n * sizeof(T));
}
}
static void Deallocate(T *p)
{
Alloc::Deallocate(p, sizeof(T));
}
static void SetCallBackHandle(CallBackFunc cb)
{
Alloc::SetCallBackHandle(cb);
}
};
4. 测试
#include "stdio.h"
#include<iostream>
using namespace std;
#include"stl_test.h"
#include "simple_alloc.h"
#include<vector>
void Func()
{
cout << "调用回调函数处理内存不足的情况" << endl;
// 为了防止死循环，该函数应该加上一个判断条件如果它本次没有清理出空间，那么就抛出异常
}
template <class T, class Alloc = SelfAlloc>
class A
{
public:
A() :m_ptr(NULL), m_nSize(0){}
A(size_t nSize)
{
DataAllocator::SetCallBackHandle(Func);
m_nSize = nSize;
m_ptr = DataAllocator::Allocate(nSize);
for (int i = 0; i < (int)nSize; i++)
{
m_ptr[i] = i;
cout << m_ptr[i] << " ";
}
cout << endl;
}
~A()
{
DataAllocator::Deallocate(m_ptr, m_nSize);
}
private:
T *m_ptr;
size_t m_nSize;
typedef CSimpleAlloc<T, Alloc> DataAllocator;
};
void main()
{
A<int> a(11);
A<int> b(50);
a.~A();
b.~A();
}
