STL-空間配置器

// 二級(jí)空間配置器
template<bool threads,int inst>
class DefaultallocTemplate //二級(jí)空間配置器
{
public:
 enum{ ALIGN = 8 }; //基準(zhǔn)值對(duì)齊
 enum{ MAX_BYTES = 128 }; //最大字節(jié)
 enum{ FREELISTS = MAX_BYTES / ALIGN }; //自由鏈表大小
 union obj
 {
  union obj* listLink; //自由鏈表中指向下一個(gè)內(nèi)存塊的指針
  char clientData[1]; //調(diào)試用
 };
 static size_t FreeListIndex(size_t bytes) //得到所需內(nèi)存塊在自由鏈表中的下標(biāo)
 {
  return ((bytes + ALIGN - 1) / ALIGN - 1);
 }
 static size_t RoundUpNum(size_t bytes) //得到內(nèi)存塊大小的向上對(duì)齊數(shù)(8的倍數(shù))
 {
  return (bytes + ALIGN - 1)&~(ALIGN - 1);
 }
 static obj* FreeList[FREELISTS];  //維護(hù)自由鏈表
 static char* startFree;  //水位線（維護(hù)內(nèi)存池）
 static char* endFree;  //池底
 static size_t heapSize;

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

  if (FreeList[index]) //自由鏈表上有內(nèi)存塊
  {
   obj* ret = FreeList[index]; //取走當(dāng)前下標(biāo)的第一個(gè)給用戶(hù)
   FreeList[index] = ret->listLink;  //FreeList[index]指向下一個(gè)
  }
  else   //若自由鏈表沒(méi)有，則調(diào)用refill從內(nèi)存池填充自由鏈表并返回內(nèi)存池的第一個(gè)內(nèi)存塊
  {
   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直接交還給一級(jí)空間配置器釋放
   return MallocAllocTemplate<inst>::Deallocate(p, size);
  else //放回二級(jí)空間配置器的自由鏈表
  {
   size_t index = FreeListIndex(size);
   obj* tmp = (obj*)p;
   tmp->listLink = FreeList[index];
   Freelist[index] = tmp;
  }
 }

 
 //從內(nèi)存池拿出內(nèi)存填充自由鏈表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申請(qǐng)20個(gè)size大小的內(nèi)存塊
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1) //只分配到一個(gè)內(nèi)存
  {
   return chunk;
  }
 
  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //將剩余內(nèi)存塊掛到自由鏈表上
  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;
 }
 
 //從內(nèi)存池中分配大塊內(nèi)存
 static char* ChunkAlloc(size_t size, int& nobjs)
 {
  char* ret = NULL;
  size_t Leftbytes = endFree - startFree; //剩余的內(nèi)存塊
  size_t Needbytes = size * nobjs; //所總共需要的內(nèi)存塊
  if (Leftbytes >= Needbytes)
  {
   ret = startFree;
   startFree += Needbytes;
  }
  else if (Leftbytes >= size) //不夠分配總size大小，但是夠分配單個(gè)size大小的
  {
   ret = startFree;
   nobjs = Leftbytes / size;
   startFree += nobjs*size;
  }
  else     //一個(gè)內(nèi)存塊都分配不出來(lái)
  {
   if (Leftbytes > 0)
   {
    size_t index = FreeListIndex(Leftbytes);
    ((obj*)startFree)->listLink = FreeList[index];
    FreeList[index] = (obj*)startFree;
    startFree = NULL;
   }
   //向操作系統(tǒng)申請(qǐng)2倍Needbytes加上已分配的heapsize/8的內(nèi)存到內(nèi)存池
   size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4);
   startFree = (char*)malloc(getBytes);
   if (startFree == NULL) //從系統(tǒng)堆中分配內(nèi)存失敗
   {
    //到后面更大的自由鏈表中去取
    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);
     }
    }
    //山窮水盡
    //最后的一根救命稻草，找一級(jí)空間配置器分配內(nèi)存
    //（其他進(jìn)程歸還內(nèi)存，調(diào)用自定義的句柄處理函數(shù)釋放內(nèi)存）
    startFree = MallocAllocTemplate<inst>::Allocate(getBytes);
   }
   heapSize += getBytes; //從系統(tǒng)堆分配的總字節(jié)數(shù)（可以用于下次分配時(shí)進(jìn)行調(diào)節(jié)）
   endFree = startFree + getBytes;

   return ChunkAlloc(size, nobjs); //遞歸調(diào)用獲取內(nèi)存
  }
  return ret;
 }
};
template<bool threads, int inst>
typename DefaultAllocTemplate<threads, inst>::obj*
DefaultAllocTemplate<threads, inst>::FreeList[FREELISTSIZE] = { 0 };

template<bool threads, int inst>
char* DefaultAllocTemplate<threads, inst>::startFree = 0;

template<bool threads, int inst>
char* DefaultAllocTemplate<threads, inst>::endFree = 0;

template<bool threads, int inst>
size_t DefaultAllocTemplate<threads, inst>::heapSize = 0;

//從內(nèi)存池拿出內(nèi)存填充自由鏈表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申請(qǐng)20個(gè)size大小的內(nèi)存塊
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1)//只分配到一個(gè)內(nèi)存
  {
   return chunk;
  }
 
  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //將剩余內(nèi)存塊掛到自由鏈表上
  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;
 }

   return ChunkAlloc(size, nobjs); //遞歸調(diào)用獲取內(nèi)存
  }
  return ret;
 }