看侯捷老师的《STL源码剖析》有一段时间了，打算自己整理一下思路，试着实现一下。主要目的有两个：1、巩固自己对源码的理解，让自己更加深刻的体会其中各种机制的奥妙。2、通过实现这些优秀的算法，来提高自己的“内功”修养。
关于空间配置器，首先作以下几点说明：
1、空间配置器即为程序分配存储空间。这里的存储空间包括内存，也包括磁盘或者其它辅助存储介质。
2、C++一般使用new算式进行存储空间配置。使用delete操作符释放分配的内存。其中的new算式内含两个阶段操作：（1）、调用：：operator new配置内存；（2）、调用Foo：：Foo（）构造对象内容。delete也包含两阶段操作：（1）、调用Foo：：~Foo（）将对象析构；（2）、调用：：operator delete释放内存。
3、在SGI STL中，空间配置器分为两级。第一级配置器直接使用malloc()与free()。第二级配置器则是情况采用不同的策略：当配置空间大于128kb时，采用第一级配置器。当需要分配的空间小于128时，则采用内存池的方式。其目的是为了降低额外负担，减少内存碎片。当然，如果你愿意的话也可以自己为容器写一个空间配置器，在创建的容器时，显示指定即可。不过在写空间配置器时，必须使用标准的接口，否则就无法使用。
好了，废话不多说，直接上代码：
以下是一级配置器的头文件，具体实现代码注释非常详细，这里不再赘述。
#ifndef SRC_FRISTCONFIGURATOR_H_#define SRC_FRISTCONFIGURATOR_H_#include "comm.h"/*一级配置器，采用malloc、free、realloc等实际操作内存*/class CFristConfigurator{public: CFristConfigurator(); virtual ~CFristConfigurator(); /*分配内存，该函数内将会直接调用malloc函数*/ static void *Allocate(size_t uiSzie); /*重新分配内存。该函数中将会直接调用realloc函数*/ static void *Reallocate(void *pOld, size_t uiOldSize, size_t uiNewSize); /*撤销分配的内存。这里的参数n只是预留参数*/ static void Dellocate(void *p, size_t n); /*设置历程函数指针。用户可以通过这个函数去设置历程*/ static void (*SetMallocAllocOomHandler(void (*vpFunc)()))();private: /*当malloc失败后，将会调用这个函数继续分配空间*/ static void *OomMalloc(size_t uiSize); /*当realloc调用失败后，会调用该函数继续分配空间*/ static void *OomRealloc(void *pOld, size_t uiNewSize); /*该指针用于保存空间分配失败的例程函数指针。用它可以实现C++的new handler机制*/ static void (*ms_pMmallocAllocOomHandler)();};#endif
以下是一级配置器代码。需要注意的是处理例程是需要使用者自己编写，而非系统编写。处理例程有其固定的模式。
1 #include "FristConfigurator.h" 2 #include3 4 //这里将函数指针设置为0，等待客户端去设置。这里的处理例程都是由客户端编写并指定的 5 void (*CFristConfigurator::ms_pMmallocAllocOomHandler)() = 0; 6 7 CFristConfigurator::CFristConfigurator() { 8 // TODO Auto-generated constructor stub 9 10 } 11 12 CFristConfigurator::~CFristConfigurator() { 13 // TODO Auto-generated destructor stub 14 } 15 16 void *CFristConfigurator::Allocate(size_t uiSize) 17 { 18 void *vpResult = malloc(uiSize); //一级配置器，直接调用函数malloc 19 if(0 == vpResult) 20 { 21 vpResult = OomMalloc(uiSize); //如果配置失败，则直接调用另一个函数配置 22 } 23 24 return vpResult; 25 } 26 27 void *CFristConfigurator::Reallocate(void *vpOld, size_t uiOldSize, size_t uiNewSize) 28 { 29 void *vpResult = realloc(vpOld, uiNewSize);//一级配置器，直接调用realloc 30 if(0 == vpResult) 31 { 32 vpResult = OomRealloc(vpOld, uiNewSize);//当realloc分配失败后会调用另外一个函数去重复分配 33 } 34 35 return vpResult; 36 } 37 38 void CFristConfigurator::Dellocate(void *p, size_t uiStandby = 0)//uiStandby参数是一个备用参数 39 { 40 free(p);//一级配置器直接调用free 41 } 42 43 void (*CFristConfigurator::SetMallocAllocOomHandler(void (*vpFunc)()))() 44 { 45 void (*vpOldFunc)() = ms_pMmallocAllocOomHandler;//保存原来的处理例程 46 ms_pMmallocAllocOomHandler = vpFunc; 47 return vpOldFunc;//将原来的处理例程返回给客户端，以便保存 48 } 49 50 void *CFristConfigurator::OomMalloc(size_t uiSize) 51 { 52 void (*vpMyMmallocAllocOomHandler)(); 53 void *vpResult; 54 55 while(1)//这里会一直重复配置空间。不断尝试释放、配置、再释放、再配置...直到配置成功为止 56 { 57 vpMyMmallocAllocOomHandler = ms_pMmallocAllocOomHandler; 58 if(0 == vpMyMmallocAllocOomHandler)//如果客户端没有设置处理例程，则将抛出异常 59 { 60 //抛出异常 61 } 62 /*之前想的是：如果这里没有分配成功，则说明在非常短的时间内不会分配到内存， 63 *在这里稍作睡眠，可以将该进程调出CPU，让CPU运行其它进程，CPU也可以不用 64 *做“无谓的”循环，提高效率。但是这样做是不正确的，原因是：这里根本不知道 65 *调用这里的程序的紧急性是不是如果很高，这里的睡眠虽然让整个系统有一点效 66 *率的提高，但是这样做很可能会让调用这个函数的程序失去处理其它事件的机会， 67 *从而达不到想要的结果。因此这里做睡眠是相当错误的选择。事实上，在 68 *vpMyMmallocAllocOomHandler指向的函数中，也会去企图释放掉一些内存，这 69 *可比睡眠方式好得多（记录下来自己曾经的想法）*/ 70 //usleep(1); 71 //这里使用vpMyMmallocAllocOomHandler而不是使用ms_pMmallocAllocOomHandler 72 //调用处理例程，个人认为是出于对程序指针的保护。以免原来函数指针被修改 73 (*vpMyMmallocAllocOomHandler)();//调用处理历程，企图从其它地方释放内存 74 vpResult = malloc(uiSize); 75 if(0 != vpResult) 76 { 77 return vpResult; 78 } 79 } 80 81 return 0;//纯属为了消除警告 82 } 83 84 void *CFristConfigurator::OomRealloc(void *vpOld, size_t uiNewSize) 85 { 86 void (*vpMyMmallocAllocOomHandler)(); 87 void *vpResult; 88 while(1) 89 { 90 vpMyMmallocAllocOomHandler = ms_pMmallocAllocOomHandler; 91 if(0 == vpMyMmallocAllocOomHandler) 92 { 93 //抛出异常 94 } 95 (*vpMyMmallocAllocOomHandler)(); 96 vpResult = realloc(vpOld, uiNewSize); 97 if(0 != vpResult) 98 { 99 return vpResult;100 }101 }102 return 0;103 }
以下是二级配置器的头文件：
1 #ifndef SRC_DEFAULTALLOCTEMPLATE_H_ 2 #define SRC_DEFAULTALLOCTEMPLATE_H_ 3 4 #include "comm.h" 5 #include "Global.h" 6 7 enum {enALIGN = 8}; //小型区块的上调边界 8 enum {enMAX_BYTES = 128}; //小型区块的上限 9 enum {enNFREELISTS = enMAX_BYTES / enALIGN}; //free-list个数（每个上调边界一个free-list）。10 11 /*这个共用体为每个小额内存块的结构。这种定义方法将不会为了维护链表12 *所必须的指针而造成浪费。这个小小的技巧节省下来的内存是相当可观的*/13 union unObj14 {15 union unObj * FreeListLink;16 char cCloendData[1];17 };18 19 /*二级配置：为了减少小额区块造成的内存碎片，以及减轻内存配置时的额外负担，20 *SIG使用了二级配置器。以下是二级配置器类的定义*/21 /*template //这里的threads参数是用于多线程，inst没有使用。为了书写简便，故将其注释*/22 class CDefaultAllocTemplate {23 public:24 CDefaultAllocTemplate();25 virtual ~CDefaultAllocTemplate();26 27 /*空间配置函数*/28 static void *Allocate(size_t uiSize);29 30 /*空间释放函数*/31 static void Deallocate(void *p, size_t uiSize);32 33 /*填充free-list函数*/34 static void *Reallocate(void *p, size_t uiOldSize, size_t uiNewSize);35 36 private:37 38 /*为了便于管理，将小额区块的内存需求量上调为8的倍数*/39 static size_t RoundUp(size_t uiBytes)40 {41 return (((uiBytes) + enALIGN - 1) & ~(enALIGN - 1));42 }43 44 /*这个函数将会确定使用哪个free-list*/45 static size_t FreeListIndex(size_t uiBytes)46 {47 size_t ret2 = (((uiBytes) + enALIGN - 1) / enALIGN - 1);48 // size_t ret = (RoundUp(uiBytes) / enALIGN - 1);49 return ret2;50 }51 52 /*当free-list不足时，将调用该函数为free-list重新填充。如果内存池只能提供一个块，53 *那么将会把这一个块返回给调用者，而free-list得不到填充*/54 static void *Refill(size_t uiSize);55 56 /*配置一个大空间，即内存池。内存池的作用是为free-list填充元素*/57 static char *ChunkAlloc(size_t uiSize, int &iNobjs);58 59 private:60 /*用于存放16个free-list*/61 static unObj * volatile ms_pFreeList[enNFREELISTS];62 63 /*内存起始地址，只在ChunkAlloc函数中变化*/64 static char *ms_cpStartFree;65 66 /*内存结束地址，只在ChunkAlloc函数中变化*/67 static char *ms_cpEndFree;68 69 /*记录内存池中分配内存空间的大小*/70 static size_t uiHeapSize;71 };72 73 74 #endif
二级配置器的源文件
1 #include "DefaultAllocTemplate.h" 2 #include "FristConfigurator.h" 3 4 5 /*为类中的静态成员变量初始化*/ 6 unObj * volatile CDefaultAllocTemplate::ms_pFreeList[enNFREELISTS] = 7 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 8 char *CDefaultAllocTemplate::ms_cpStartFree = 0; 9 char *CDefaultAllocTemplate::ms_cpEndFree = 0; 10 size_t CDefaultAllocTemplate::uiHeapSize = 0; 11 12 CDefaultAllocTemplate::CDefaultAllocTemplate() { 13 // TODO Auto-generated constructor stub 14 } 15 16 CDefaultAllocTemplate::~CDefaultAllocTemplate() { 17 // TODO Auto-generated destructor stub 18 } 19 20 void *CDefaultAllocTemplate::Allocate(size_t uiSize) 21 { 22 unObj * volatile *pMyFreeList; 23 unObj *pResult; 24 25 if(uiSize > enMAX_BYTES) //当需要分配的内存大于128时，调用一级配置器 26 { 27 return CFristConfigurator::Allocate(uiSize); 28 } 29 30 /*得到需要使用的free-list*/ 31 pMyFreeList = ms_pFreeList + CDefaultAllocTemplate::FreeListIndex(uiSize); 32 pResult = *pMyFreeList; 33 if(0 == *pMyFreeList) 34 { 35 //没有找到，需要重新装填free-list,装填后分配 36 void *pRet = Refill(RoundUp(uiSize)); 37 return pRet; 38 } 39 else 40 { 41 *pMyFreeList = pResult->FreeListLink;//取出一块内存后需要调整链表 42 return (pResult); 43 } 44 } 45 46 void CDefaultAllocTemplate::Deallocate(void *pFree, size_t uiSize) 47 { 48 unObj *pFreeObj = (unObj *)pFree; 49 unObj *volatile *pMyFreeList; 50 51 if(uiSize > enMAX_BYTES)//如果要释放的空间大于enMAX_BYTES，则直接调用一级配置器的释放函数 52 { 53 CFristConfigurator::Dellocate(pFree, uiSize); 54 return ; 55 } 56 else 57 { 58 pMyFreeList = ms_pFreeList + FreeListIndex(uiSize);//确定使用的free-list 59 pFreeObj->FreeListLink = *pMyFreeList;//将内存块回收到free-list中 60 *pMyFreeList = pFreeObj; 61 } 62 } 63 64 void *CDefaultAllocTemplate::Refill(size_t uiSize) 65 { 66 int iNobjs = 20;//填充个数默认设置为20，当内存池空间不足时，可能会小于20个 67 68 /*为free-list填充空间，最终填充个数存放在参数iNobjs中.其返回值将会当作申请的块返回给调用者*/ 69 char *cpChunk = ChunkAlloc(uiSize, iNobjs); 70 71 unObj *volatile *pMyFreeList; 72 unObj *pResult; 73 unObj *pCurrentObj, *pNextObj; 74 75 if(1 == iNobjs)//如果只有一个块，将会把这个块返回给调用者 76 { 77 return cpChunk; 78 } 79 else//大于一个块时，将会调整free-list，纳入新的块 80 { 81 pMyFreeList= ms_pFreeList + FreeListIndex(uiSize);//确定需要调整的free-list 82 pResult = (unObj *)cpChunk;//这一块将会返回给调用者 83 84 /*将剩下的块添加到free-list中*/ 85 /*每一个块大小是uiSize,这里相当于跳过第一个块。其他的将会添加到free-list中。 86 *这里实质上是将一整块内存当作链表操作。目的是为了管理内存*/ 87 *pMyFreeList = pNextObj = (unObj *)(cpChunk + uiSize); 88 for(int i = 1; ; i++) 89 { 90 pCurrentObj = pNextObj; 91 pNextObj = (unObj *)((char *)(pNextObj + uiSize));//指向下一个块内存 92 if(iNobjs - 1 == i)//将剩下所有块都添加到free-list中 93 { 94 pCurrentObj->FreeListLink = 0; 95 break; 96 } 97 else//没有添加完，继续添加 98 { 99 pCurrentObj->FreeListLink = pNextObj;100 }101 }102 }103 104 return pResult;105 }106 107 char *CDefaultAllocTemplate::ChunkAlloc(size_t uiSize, int &iNobjs)108 {109 char *cpResult;110 size_t uiTotal = uiSize * iNobjs;//需要分配的内存空间111 size_t uiResidue = ms_cpEndFree - ms_cpStartFree;//内存池中剩余空间112 113 114 if(uiResidue >= uiTotal)//如果内存池中的内存完全满足需要，则直接补充115 {116 cpResult = ms_cpStartFree;//分配内存空间117 ms_cpStartFree += uiTotal;//调整内存池的起始地址118 return cpResult;119 }120 else if(uiResidue >= uiSize)//内存池中内存量不足，但能分配一些块121 {122 iNobjs = uiResidue / uiSize;//能够分配的块数123 cpResult = ms_cpStartFree;//尽其所能分配一定量的空间124 ms_cpStartFree += iNobjs * uiSize;//调整内存池中起始地址125 return cpResult;126 }127 else//内存池中剩余量连一块都不能分配128 {129 /*如果内存池中还有残存空间，则将剩余的空间全部利用，分配到free-list中*/130 if(uiResidue > 0)131 {132 /*FreeListIndex函数会计算出内分配的最大块，若内存池剩余量为enMAX_BYTES，则应该为第一种情况133 *因此这样计算添加哪个free-list非常合理的*/134 unObj * volatile * pMyFreeList = ms_pFreeList + FreeListIndex(uiResidue);135 136 /*调整free-list*/137 ((unObj *)(ms_cpStartFree))->FreeListLink = *pMyFreeList;138 *pMyFreeList = (unObj *)(ms_cpStartFree);139 }140 141 /*计算此次需要分配的内存空间大小*/142 size_t uiBytes = 2 * uiTotal + RoundUp(uiHeapSize >> 4);143 144 /*这里直接使用ms_cpStartFree指针去保存分配的内存，原来分配的内存块没有指针指向，以后没法free，会不会造成内存泄漏？145 *答案是不会。原来内存池中所有的内存已经全部存放在free-list中了。在SGI STL中还有全局函数destroy()，该函数第二版接146 *受frist和last两个迭代器，能够将[frist, last)范围内的所有对象析构。在适当的时候系统会调用这个函数释放这些内存（这147 *句只是我自己的猜测）。即使不调用这个函数，*/148 ms_cpStartFree = (char *)malloc(uiBytes);//调用malloc分配内存149 if(0 == ms_cpStartFree)//malloc调用失败。即堆空间没内存可以分配了150 {151 unObj * volatile *pMyFeeList, *pP;152 153 /*以下的代码将会把原来free-list中所有没有被分配的内存释放出来，试图满足调用者的需求*/154 for(int i = 0; i <= enMAX_BYTES; i += enALIGN)155 {156 pMyFeeList = ms_pFreeList + FreeListIndex(i);157 pP = *pMyFeeList;158 if(0 != pP)159 {160 *pMyFeeList = pP->FreeListLink;161 ms_cpStartFree = (char *)pP;162 ms_cpEndFree = ms_cpStartFree + i;163 164 /*递归调用自己，目的是1、为了修正iNobjs。2、释放了free-list，递归看看是够满足需求。165 *这里递归调用的结果可能有两个：166 *1、找到合适的空间，满足了调用者的需求。167 *2、无论如何都找不到合适的空间了，当调用第一级配置器时，抛出异常*/168 return (ChunkAlloc(uiSize, iNobjs));169 }170 }171 ms_cpEndFree = 0;172 173 /*已经没有任何内存可以使用了,只有看一级配置器中的out-of-memory机制能不能挤出内存来。174 *如果客户端没有设置处理例程，这无疑将会抛出异常或者直接暴力结束程序*/175 ms_cpStartFree = (char *)CFristConfigurator::Allocate(uiSize);176 }177 uiHeapSize += uiBytes;178 ms_cpEndFree = ms_cpStartFree + uiTotal;179 180 /*递归调用自己，目的是为了修正iNobjs。181 *因为调用malloc为内存池补充以后，到底补充了多少，之前并不知道。也就是说，程序之前并不知道补充以后能分配182 *多少块。因此这调用的目的不仅是修正iNobjs。还要调整内存池,为调用者返回分配的内存块*/183 return (ChunkAlloc(uiSize, iNobjs));184 }185 186 187 return cpResult;188 } 配置器仅仅做到这些是不够的，还需要为使用者提供统一的接口。其接口如下
1 /* 2 * AllocatorInterface.h 3 * 4 * Created on: 2015-11-20 5 * Author: zxtp 6 */ 7 8 #ifndef SRC_ALLOCATORINTERFACE_H_ 9 #define SRC_ALLOCATORINTERFACE_H_10 11 #include "DefaultAllocTemplate.h"12 13 /*配置器接口，里面的各个成员函数都仅仅是调用其它配置函数*/14 template15 class AllocatorInterface {16 public:17 AllocatorInterface();18 virtual ~AllocatorInterface();19 20 /*分配uiNum个对象的存储空间*/21 static T *Allocate(size_t uiNum)22 {23 return 0 == uiNum?0:(T*)CDefaultAllocTemplate::Allocate(uiNum * sizeof(T));24 };25 26 /*分配一个对象的存储空间*/27 static T* Allocate(void )28 {29 return (T*)CDefaultAllocTemplate::Allocate(sizeof(T));30 };31 32 /*销毁uiNum个对象的存储空间*/33 static void Deallocate(T* pP, size_t uiNum)34 {35 if(0 != uiNum)36 {37 CDefaultAllocTemplate::Deallocate(pP, uiNum * sizeof(T));38 }39 };40 41 /*销毁一个对象的存储空间*/42 static void Deallocate(T *pP)43 {44 if(0 != *pP)45 {46 CDefaultAllocTemplate::Deallocate(pP, sizeof(T));47 }48 }49 };50 51 #endif /* SRC_ALLOCATORINTERFACE_H_ */