　　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 = );

    static void SetCallBackHandle(CallBackFunc cb);

private:

    static void* ReAllocate(size_t nSize);

    static void* ReAllocate(void *p, size_t nSize);

};

enum {ALIGN = };  // 小型区块的上调边界

enum {MAX_BYTES = }; // 小型区块的上限

enum {FREELISTNUM = MAX_BYTES/ALIGN}; // free-lists个数

// 空闲内存链表结构

union FreeList

{

    union FreeList *pFreeList;

    char client_data[];

};

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 ()

    {

        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 ()

    {

        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] = {  };

char* CSecondLevelAlloc::m_pStartFree = NULL;

char* CSecondLevelAlloc::m_pEndFree = NULL;

size_t CSecondLevelAlloc::m_nHeapSize = ;

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 - );

}

size_t CSecondLevelAlloc::Round_Up(int nBytes)

{

    return ((nBytes + ALIGN - ) & (~(ALIGN - )));

}

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 =  * nTotalBytes + Round_Up(m_nHeapSize >> );

        // 以下试着让内存池中的残余零头还有价值

        if (nBytesLeft > )

        {

            // 内存池内还有一些零头，先配给适当的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个区块

    char *pChunk = ChunkAlloc(nSize, nObjs);

    if ( == 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 = ; 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 == )

        {

            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 != )

        {

            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(){}

    A(size_t nSize)

    {

        DataAllocator::SetCallBackHandle(Func);

        m_nSize = nSize;

        m_ptr = DataAllocator::Allocate(nSize);

        for (int i = ; 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();

    A<int> b();

    a.~A();

    b.~A();

}

巴特西

STL空间配置器解析和实现

1. 一级空间配置器实现

1.1 接口

1.2 实现

2. 二级空间配置器实现

2.1 接口

2.2 实现

3. 配置器标准接口

4. 测试

最新文章

热门文章