STL-空间配置器

// 二级空间配置器
template
class DefaultallocTemplate //二级空间配置器
{
public:
 enum{ ALIGN = 8 }; //基准值对齐
 enum{ MAX_BYTES = 128 }; //最大字节
 enum{ FREELISTS = MAX_BYTES / ALIGN }; //自由链表大小
 union obj
 {
  union obj* listLink; //自由链表中指向下一个内存块的指针
  char clientData[1]; //调试用
 };
 static size_t FreeListIndex(size_t bytes) //得到所需内存块在自由链表中的下标
 {
  return ((bytes + ALIGN - 1) / ALIGN - 1);
 }
 static size_t RoundUpNum(size_t bytes) //得到内存块大小的向上对齐数(8的倍数)
 {
  return (bytes + ALIGN - 1)&~(ALIGN - 1);
 }
 static obj* FreeList[FREELISTS];  //维护自由链表
 static char* startFree;  //水位线（维护内存池）
 static char* endFree;  //池底
 static size_t heapSize;

 static void* Allocate(size_t size)
 {
  if (size > MAX_BYTES)
  {
   return MallocAllocTemplate::Allocate(size);
  }
  void* ret = NULL;
  size_t index = FreeListIndex(size);

  if (FreeList[index]) //自由链表上有内存块
  {
   obj* ret = FreeList[index]; //取走当前下标的第一个给用户
   FreeList[index] = ret->listLink;  //FreeList[index]指向下一个
  }
  else   //若自由链表没有，则调用refill从内存池填充自由链表并返回内存池的第一个内存块
  {
   return Refill(RoundUpNum(size));
  }
  return ret;
 }

 static void* Reallocate(void* p, size_t oldsize, size_t newsize)
 {
  void* ret = NULL;
  if (oldsize > (size_t)MAX_BYTES&&newsize > (size_t)MAX_BYTES)
   return (realloc(p, newsize));
  if (RoundUpNum(oldsize) == RoundUpNum(newsize))
   return p;
  ret = Allocate(newsize);
  size_t copysize = oldsize > newsize ? newsize : oldsize;
  memcopy(ret, p, copysize);
  DeAllocate(p, oldsize);
  return ret;
 }
 static void Deallocate(void* p, size_t size)
 {
  if (size> MAX_BYTES) //如果大于MAX_BYTES直接交还给一级空间配置器释放
   return MallocAllocTemplate::Deallocate(p, size);
  else //放回二级空间配置器的自由链表
  {
   size_t index = FreeListIndex(size);
   obj* tmp = (obj*)p;
   tmp->listLink = FreeList[index];
   Freelist[index] = tmp;
  }
 }

 
 //从内存池拿出内存填充自由链表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申请20个size大小的内存块
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1) //只分配到一个内存
  {
   return chunk;
  }
 
  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //将剩余内存块挂到自由链表上
  FreeList[index] = cur;
  for (int i = 1; i < nobjs-1; ++i)
  {
   next=(obj*)((char*)cur +size);
   cur->listLink = next;
   cur = next;
  }
  cur->listLink = NULL;
  return chunk;
 }
 
 //从内存池中分配大块内存
 static char* ChunkAlloc(size_t size, int& nobjs)
 {
  char* ret = NULL;
  size_t Leftbytes = endFree - startFree; //剩余的内存块
  size_t Needbytes = size * nobjs; //所总共需要的内存块
  if (Leftbytes >= Needbytes)
  {
   ret = startFree;
   startFree += Needbytes;
  }
  else if (Leftbytes >= size) //不够分配总size大小，但是够分配单个size大小的
  {
   ret = startFree;
   nobjs = Leftbytes / size;
   startFree += nobjs*size;
  }
  else     //一个内存块都分配不出来
  {
   if (Leftbytes > 0)
   {
    size_t index = FreeListIndex(Leftbytes);
    ((obj*)startFree)->listLink = FreeList[index];
    FreeList[index] = (obj*)startFree;
    startFree = NULL;
   }
   //向操作系统申请2倍Needbytes加上已分配的heapsize/8的内存到内存池
   size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4);
   startFree = (char*)malloc(getBytes);
   if (startFree == NULL) //从系统堆中分配内存失败
   {
    //到后面更大的自由链表中去取
    for (int i = size; i < MAX_BYTES; i += ALIGN)
    {
     size_t index = FreeList[FreeListIndex(i)];
     if (FreeList[index])
     {
      startFree = FreeList[index];
      FreeList[index] = FreeList[index]->listLink;
      endFree = startFree + size;
      return ChunkAlloc(size, nobjs);
     }
    }
    //山穷水尽
    //最后的一根救命稻草，找一级空间配置器分配内存
    //（其他进程归还内存，调用自定义的句柄处理函数释放内存）
    startFree = MallocAllocTemplate::Allocate(getBytes);
   }
   heapSize += getBytes; //从系统堆分配的总字节数（可以用于下次分配时进行调节）
   endFree = startFree + getBytes;

   return ChunkAlloc(size, nobjs); //递归调用获取内存
  }
  return ret;
 }
};
template
typename DefaultAllocTemplate::obj*
DefaultAllocTemplate::FreeList[FREELISTSIZE] = { 0 };

template
char* DefaultAllocTemplate::startFree = 0;

template
char* DefaultAllocTemplate::endFree = 0;

template
size_t DefaultAllocTemplate::heapSize = 0;

//从内存池拿出内存填充自由链表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申请20个size大小的内存块
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1)//只分配到一个内存
  {
   return chunk;
  }
 
  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //将剩余内存块挂到自由链表上
  FreeList[index] = cur;
  for (int i = 1; i < nobjs-1; ++i)
  {
   next=(obj*)((char*)cur +size);
   cur->listLink = next;
   cur = next;
  }
  cur->listLink = NULL;
  return chunk;
 }