内存对象管理器（基于数组和链表实现）

1.1 数组的特点

• 连续的内存空间分配并且顺序存储数据，使用之前需要先分配数组个数；
• 可以通过下标进行访问修改数据，时间复杂度为o(1);
• 空间效率不是很好，不能随意修改数组大小；
• 增删数据需要内存拷贝

 

1.2 链表的特点

• 内存空间分配是分散的，非连续的存储数据；
• 不能通过下标直接访问，查找的时间复杂度为o(n);
• 增删元素，只需要改变前后指针；

1.3 基于数组和指针实现的对象管理器

结合了数组和链表的优点，可以o(1)查找元素，o(1)增删元素；

需要预分配内存；

 

 

2.代码实现（c++）

/**
*@file objallocator
*@author jasonxiong
*@date 2009-12-09
*@version 1.0
*@brief cobj对象分配类，即新版本的idxobj
*
*    （1）一般用于大型对象的内存分配
*/

#ifndef __obj_allocator_hpp__
#define __obj_allocator_hpp__

#include <stdio.h>

namespace serverlib
{

typedef enum enmobjalloctype
{
    eoat_alloc_by_self = 0,          //!<对象内存由objallocator自已动态分配
    eoat_alloc_by_shared_memory = 1, //!<对象内存由共享内存分配
} enmobjalloctype;

class cobj;

typedef enum enmidxuseflag
{
    eiuf_free = 0, //!<该对象未被使用
    eiuf_used = 1, //!<该对象已被使用
} enmidxuseflag;

//!索引类，仅在cobjallocator中使用，外层一般不用
class cidx
{
public:
    cidx();
    ~cidx();

public:
    //!初始化函数
    int initialize();

    //!将对象设置为未使用
    inline void setfree()
    {
        m_iuseflag = eiuf_free;
    }

    //!将对象设置为已使用
    inline void setused()
    {
        m_iuseflag = eiuf_used;
    }

    //!判断对象是否已被使用
    inline int isused() const
    {
        return m_iuseflag == eiuf_used;
    }

    //!获取所在链表下一个索引
    inline int getnextidx() const
    {
        return m_inextidx;
    }

    //!设置所在链表下一个索引
    inline void setnextidx(int iidx)
    {
        m_inextidx = iidx;
    }

    //!获取所在链表上一个索引
    inline int getprevidx() const
    {
        return m_iprevidx;
    }

    //!设置所在链表上一个索引
    inline void setprevidx(int iidx)
    {
        m_iprevidx = iidx;
    }

    //!获取指向的对象
    inline cobj *getattachedobj() const
    {
        return m_pattachedobj;
    }

    //!设置指向的对象
    inline void setattachedobj(cobj *pobj)
    {
        m_pattachedobj = pobj;
    }

private:
    int m_inextidx;       //!<对象索引块链表指针，指向后一个闲/忙索引
    int m_iprevidx;       //!<对象索引块链表指针，指向前一个闲/忙索引
    int m_iuseflag;       //!<该对象是否已经被使用标志
    cobj *m_pattachedobj; //!<所指向的对象指针
};

typedef cobj *(*function_createobj)(void *);

class cobjallocator
{
private:
    //默认构造函数，不允许上层自行调用
    cobjallocator();

public:
    cobjallocator(size_t uiobjsize, int iobjcount, function_createobj pfcreateobj);
    ~cobjallocator();

    /**
    *使用共享内存创建objallocator
    *@param[in] pszkeyfilename 共享内存attach的文件名
    *@param[in] uckeyprjid 共享内存的工程id
    *@param[in] uiobjsize 对象大小
    *@param[in] iobjcount 对象个数
    *@param[in]
    *@return 0 success
    */
    static cobjallocator *createbysharedmemory(const char *pszkeyfilename,
                                               const unsigned char uckeyprjid,
                                               size_t uiobjsize, int iobjcount, function_createobj pfcreateobj);

    /**
    *指定内存指针来创建cobjallocator
    *@param[in] pszmemoryaddress 指定的内存
    *@param[in] uimemorysize 内存大小
    *@param[in] uiobjsize 对象大小
    *@param[in] iobjcount 对象个数
    *@param[in] pfcreateobj 创建cobj对象的函数，默认可以用declare_dyn中的createobject
    *@return 0 success
    */
    static cobjallocator *createbygivenmemory(char *pszmemoryaddress, size_t uimemorysize,
                                              size_t uiobjsize, int iobjcount, function_createobj pfcreateobj);

    static size_t countsize(size_t uiobjsize, int iobjcount);

    static cobjallocator *resumebygivenmemory(char *pszmemoryaddress,
                                              size_t uimemorysize, size_t uiobjsize, int iobjcount, function_createobj pfcreateobj);

public:
    //!初始化函数，将数据清空
    int initialize();

    //!创建一个对象，成功返回对象id，失败返回小于0的值
    int createobject();

    //!创建一个对象, 并指定其id，成功返回对象id，失败返回小于0的值
    int createobjectbyid(int iid);

    //!根据对象id销毁一个对象，成功返回0
    int destroyobject(int iobjectid);

    //!根据objectid返回对象，必须保证该对象已被使用
    cobj *getobj(int iobjectid);

    //!根据objectid返回索引
    cidx *getidx(int iobjectid);

    //!获取已用对象链表头索引
    inline int getusedhead() const
    {
        return m_iusedheadidx;
    }

    //!获取空闲对象链表头索引
    inline int getfreehead() const
    {
        return m_ifreeheadidx;
    }

    //获取已用对象个数
    inline int getusedcount() const
    {
        return m_iusedcount;
    }

    //获取空闲对象个数
    inline int getfreecount() const
    {
        return m_iobjcount - m_iusedcount;
    }

    //!在接口返回错误时，调用这个函数获取错误号
    inline int geterrorno() const
    {
        return m_ierrorno;
    }

    //获取对象分配类型
    inline int getobjalloctype() const
    {
        return m_shobjalloctype;
    }

    //!获取下一个对象
    cobj *getnextobj(int iobjectid);

    //!设置对象初始化指针
    inline void setcreateobjfunc(function_createobj pfcreateobjfunc)
    {
        m_pfcreateobjfunc = pfcreateobjfunc;
    }

private:
    //!设置错误号
    inline void seterrorno(int ierrorno)
    {
        m_ierrorno = ierrorno;
    }

private:
    //这几个对象只有在构造函数时确定，后面不会更改
    short m_shobjalloctype;               //!<对象分配类型
    size_t m_uiobjsize;                   //!<单个对象
    int m_iobjcount;                      //!<最多分配的对象个数
    cidx *m_astidxs;                      //!<索引数组，用于管理对象链表
    cobj *m_pstobjbuffer;                 //!<分配的对象内存
    function_createobj m_pfcreateobjfunc; //!<在内存上创建cobj对象的函数，每个子类需要自己实现

    //以下的对象会更改，调用initialize初始化
    int m_ierrorno;     //!<错误码
    int m_ifreeheadidx; //!<空闲对象链表头索引
    int m_ifreetailidx; //!<空闲对象链表尾索引
    int m_iusedheadidx; //!<已用对象链表头索引
    int m_iusedcount;   //!<已用对象个数
};

//!基本对象类
class cobj
{
public:
    cobj() {}
    virtual ~cobj() {}

public:
    //!对象的初始化函数，在cobjallocator创建对象时会调用，所以子类一定要实现
    virtual int initialize() = 0;

    //!显示对象函数，可重载
    virtual int show() const
    {
        return 0;
    }

    //!获取对象id
    inline int getobjectid() const
    {
        return m_iobjectid;
    }

    //!设置对象id
    inline void setobjectid(int iobjectid)
    {
        m_iobjectid = iobjectid;
    }

    virtual int resume()
    {
        return 0;
    }

private:
    int m_iobjectid; //!对象id，即在cobjallocator中的数组下标

    friend int cobjallocator::initialize(); //!<在这个函数中需要直接赋值m_iobjectid，所以设为友元
};

#define declare_dyn                                               \
public:                                                           \
    void *operator new(size_t uisize, const void *pthis) throw(); \
    static cobj *createobject(void *pmem);

#define implement_dyn(class_name)                                            \
    void *class_name::operator new(size_t uisize, const void *pthis) throw() \
    {                                                                        \
        if (!pthis)                                                          \
        {                                                                    \
            return null;                                                     \
        }                                                                    \
                                                                             \
        return (void *)pthis;                                                \
    }                                                                        \
                                                                             \
    cobj *class_name::createobject(void *pmem)                               \
    {                                                                        \
        return (cobj *)new (pmem) class_name;                                \
    }

} // namespace serverlib

#endif //__obj_allocator_hpp__
///:~


/**
*@file objallocator.cpp
*@author jasonxiong
*@date 2009-12-14
*@version 1.0
*@brief 对象分配类的实现文件
*
*
*/

#include <assert.h>

#include "errordef.hpp"
#include "objallocator.hpp"
#include "sharedmemory.hpp"

using namespace serverlib;

cidx::cidx()
{
    initialize();
}

cidx::~cidx()
{
}

int cidx::initialize()
{
    m_inextidx = -1;
    m_iprevidx = -1;
    m_iuseflag = 0;
    m_pattachedobj = null;

    return 0;
}

cobjallocator::cobjallocator()
{
}

//void* cobjallocator::operator new(unsigned int uisize, const void* pthis) throw()
//{
//    if(!pthis)
//    {
//        return null;
//    }
//
//    return (void*)pthis;
//}

cobjallocator::cobjallocator(size_t uiobjsize, int iobjcount, function_createobj pfcreateobj)
{
    __assert_and_log(uiobjsize > 0 && iobjcount > 0 && pfcreateobj);

    m_shobjalloctype = eoat_alloc_by_self;
    m_iobjcount = iobjcount;
    m_uiobjsize = uiobjsize;
    m_pfcreateobjfunc = pfcreateobj;

    m_astidxs = new cidx[m_iobjcount];
    size_t uiobjmemorysize = uiobjsize * iobjcount;
    char *pstobjmem = new char[uiobjmemorysize];
    m_pstobjbuffer = (cobj *)pstobjmem;

    __assert_and_log(m_astidxs && m_pstobjbuffer);

    initialize();
}

size_t cobjallocator::countsize(size_t uiobjsize, int iobjcount)
{
    return sizeof(cobjallocator) + uiobjsize * iobjcount + iobjcount * sizeof(cidx);
}

cobjallocator *cobjallocator::createbygivenmemory(char *pszmemoryaddress, size_t uimemorysize, size_t uiobjsize,
                                                  int iobjcount, function_createobj pfcreateobj)
{
    if (pszmemoryaddress == null || uiobjsize <= 0 || iobjcount <= 0 || pfcreateobj == null)
    {
        tracesvr("%p, %d, %d, %p.\n", pszmemoryaddress, (int)uiobjsize, iobjcount, pfcreateobj);
        return null;
    }

    size_t uisharedmemorysize = sizeof(cobjallocator) + uiobjsize * iobjcount +
                                iobjcount * sizeof(cidx);

    if (uisharedmemorysize > uimemorysize)
    {
        tracesvr("objallocator: alloc size %lu > sh size %lu.\n", (unsigned long)uisharedmemorysize, (unsigned long)uimemorysize);
        return null;
    }

    //在指定的内存地址上分配cobjallocator
    cobjallocator *pstobjallocator = (cobjallocator *)pszmemoryaddress;

    if (!pstobjallocator)
    {
        tracesvr("objallocator: pstobjallocator is null.\n");
        return null;
    }

    pstobjallocator->m_uiobjsize = uiobjsize;
    pstobjallocator->m_iobjcount = iobjcount;
    pstobjallocator->m_pfcreateobjfunc = pfcreateobj;
    pstobjallocator->m_shobjalloctype = eoat_alloc_by_shared_memory;
    pstobjallocator->m_astidxs = (cidx *)((unsigned char *)pszmemoryaddress + sizeof(cobjallocator));
    pstobjallocator->m_pstobjbuffer = (cobj *)((unsigned char *)pszmemoryaddress + sizeof(cobjallocator) + iobjcount * sizeof(cidx));

    pstobjallocator->initialize();

    return pstobjallocator;
}

cobjallocator *cobjallocator::resumebygivenmemory(char *pszmemoryaddress,
                                                  size_t uimemorysize, size_t uiobjsize, int iobjcount, function_createobj pfcreateobj)
{
    if ((null == pszmemoryaddress) || (uiobjsize <= 0) || (iobjcount <= 0))
    {
        return null;
    }

    size_t uisharedmemorysize = sizeof(cobjallocator) + uiobjsize * iobjcount + sizeof(cidx) * iobjcount;

    if (uisharedmemorysize > uimemorysize)
    {
        return null;
    }

    cobjallocator *pstobjallocator = (cobjallocator *)pszmemoryaddress;

    if ((pstobjallocator->m_uiobjsize != uiobjsize) || (pstobjallocator->m_iobjcount != iobjcount))
    {
        return null;
    }

    pstobjallocator->m_shobjalloctype = eoat_alloc_by_shared_memory;
    pstobjallocator->m_astidxs = (cidx *)((unsigned char *)pszmemoryaddress + sizeof(cobjallocator));
    pstobjallocator->m_pstobjbuffer = (cobj *)((unsigned char *)pszmemoryaddress + sizeof(cobjallocator) + iobjcount * sizeof(cidx));

    int i;

    // 重新绑定obj和idx
    for (i = 0; i < iobjcount; ++i)
    {
        // 调用placement-new, 恢复类的虚函数表.
        cobj *pstobj = (*pfcreateobj)((unsigned char *)pstobjallocator->m_pstobjbuffer + uiobjsize * i);

        __assert_and_log(pstobj->getobjectid() == i);

        pstobjallocator->m_astidxs[i].setattachedobj(pstobj);
    }

    pstobjallocator->setcreateobjfunc(pfcreateobj);
    return pstobjallocator;
}

cobjallocator *cobjallocator::createbysharedmemory(const char *pszkeyfilename, const unsigned char uckeyprjid,
                                                   size_t uiobjsize, int iobjcount, function_createobj pfcreateobj)
{
    if (pszkeyfilename == null || uiobjsize <= 0 || iobjcount <= 0 || pfcreateobj == null)
    {
        return null;
    }

    csharedmemory stsharedmemory;
    size_t uisharedmemorysize = sizeof(cobjallocator) + uiobjsize * iobjcount +
                                iobjcount * sizeof(cidx);

    int iret = stsharedmemory.createshmsegment(pszkeyfilename, uckeyprjid,
                                               (int)uisharedmemorysize);

    if (iret)
    {
        return null;
    }

    //在共享内存的地址上分配cobjallocator
    cobjallocator *pstobjallocator = (cobjallocator *)stsharedmemory.getfreememoryaddress();

    if (!pstobjallocator)
    {
        return null;
    }

    pstobjallocator->m_uiobjsize = uiobjsize;
    pstobjallocator->m_iobjcount = iobjcount;
    pstobjallocator->m_pfcreateobjfunc = pfcreateobj;
    pstobjallocator->m_shobjalloctype = eoat_alloc_by_shared_memory;
    pstobjallocator->m_astidxs = (cidx *)((unsigned char *)stsharedmemory.getfreememoryaddress() + sizeof(cobjallocator));
    pstobjallocator->m_pstobjbuffer = (cobj *)((unsigned char *)stsharedmemory.getfreememoryaddress() +
                                               sizeof(cobjallocator) + iobjcount * sizeof(cidx));

    return pstobjallocator;
}

cobjallocator::~cobjallocator()
{
    if (m_shobjalloctype == eoat_alloc_by_self)
    {
        if (m_astidxs)
        {
            delete[] m_astidxs;
            m_astidxs = null;
        }

        if (m_pstobjbuffer)
        {
            char *pstobjmem = (char *)m_pstobjbuffer;
            delete[] pstobjmem;
            m_pstobjbuffer = null;
        }
    }
}

int cobjallocator::initialize()
{
    if (m_pstobjbuffer == null || m_astidxs == null)
    {
        seterrorno(een_obj_allocator__null_pointer);

        return -1;
    }

    if (m_iobjcount <= 0)
    {
        seterrorno(een_obj_allocator__invalid_obj_count);

        return -2;
    }

    //初始化索引数组
    int i;
    for (i = 0; i < m_iobjcount; ++i)
    {
        m_astidxs[i].initialize();
        m_astidxs[i].setprevidx(i - 1);
        m_astidxs[i].setnextidx(i + 1);
    }

    m_astidxs[m_iobjcount - 1].setnextidx(-1);

    //初始化对象数组
    for (i = 0; i < m_iobjcount; ++i)
    {
        cobj *pstobj = (*m_pfcreateobjfunc)((unsigned char *)m_pstobjbuffer + m_uiobjsize * i);
        pstobj->m_iobjectid = i;
        m_astidxs[i].setattachedobj(pstobj);
    }

    m_ierrorno = 0;
    m_ifreeheadidx = 0;
    m_ifreetailidx = m_iobjcount - 1;
    m_iusedheadidx = -1;
    m_iusedcount = 0;

    return 0;
}

int cobjallocator::createobject()
{
    if (m_pstobjbuffer == null || m_astidxs == null)
    {
        seterrorno(een_obj_allocator__null_pointer);
        return -1;
    }

    if (m_iusedcount >= m_iobjcount)
    {
        seterrorno(een_obj_allocator__obj_is_full);
        return -2;
    }

    if (m_ifreeheadidx < 0 || m_ifreeheadidx >= m_iobjcount)
    {
        seterrorno(een_obj_allocator__invalid_obj_index);
        return -3;
    }

    //修改空闲链表
    int icuridx = m_ifreeheadidx;
    m_ifreeheadidx = m_astidxs[m_ifreeheadidx].getnextidx();

    if (m_ifreeheadidx >= 0)
    {
        m_astidxs[m_ifreeheadidx].setprevidx(-1);
    }

    if (icuridx == m_ifreetailidx)
    {
        m_ifreetailidx = -1;
    }

    //挂到使用链表
    m_astidxs[icuridx].setused();
    m_astidxs[icuridx].setnextidx(m_iusedheadidx);
    m_astidxs[icuridx].setprevidx(-1);

    if (m_iusedheadidx >= 0)
    {
        m_astidxs[m_iusedheadidx].setprevidx(icuridx);
    }

    //初始化对象
    m_iusedheadidx = icuridx;

    cobj *pstobj = m_astidxs[icuridx].getattachedobj();
    if (null == pstobj)
    {
        seterrorno(een_obj_allocator__null_pointer);
        return -4;
    }

#ifdef obj_memset_on_create
    memset(pstobj, 0, m_uiobjsize);
    (*m_pfcreateobjfunc)((unsigned char *)pstobj);
    pstobj->setobjectid(icuridx);
#endif

    pstobj->initialize();
    ++m_iusedcount;

    __assert_and_log(pstobj->getobjectid() == icuridx);

    return icuridx;
}

int cobjallocator::createobjectbyid(int iid)
{
    if (m_pstobjbuffer == null || m_astidxs == null)
    {
        seterrorno(een_obj_allocator__null_pointer);

        return -1;
    }

    if (iid < 0 || iid >= m_iobjcount)
    {
        seterrorno(een_obj_allocator__invalid_obj_index);

        return -2;
    }

    if (m_astidxs[iid].isused())
    {
        seterrorno(een_obj_allocator__invalid_obj_index);

        return -3;
    }

    //修改空闲链表
    int icuridx = iid;
    int iprevidx = m_astidxs[icuridx].getprevidx();
    int inextidx = m_astidxs[icuridx].getnextidx();

    if (iprevidx >= 0)
    {
        m_astidxs[iprevidx].setnextidx(inextidx);
    }

    if (inextidx >= 0)
    {
        m_astidxs[inextidx].setprevidx(iprevidx);
    }

    if (icuridx == m_ifreeheadidx)
    {
        m_ifreeheadidx = inextidx;
    }

    if (icuridx == m_ifreetailidx)
    {
        m_ifreetailidx = -1;
    }

    //挂到使用链表
    m_astidxs[icuridx].setused();
    m_astidxs[icuridx].setnextidx(m_iusedheadidx);
    m_astidxs[icuridx].setprevidx(-1);

    if (m_iusedheadidx >= 0)
    {
        m_astidxs[m_iusedheadidx].setprevidx(icuridx);
    }

    m_iusedheadidx = icuridx; // add by cary

    cobj *pstobj = m_astidxs[icuridx].getattachedobj();

#ifdef obj_memset_on_create
    memset(pstobj, 0, m_uiobjsize);
    (*m_pfcreateobjfunc)((unsigned char *)pstobj);
    pstobj->setobjectid(icuridx);
#endif

    pstobj->initialize();
    ++m_iusedcount;

    __assert_and_log(pstobj->getobjectid() == icuridx);

    return icuridx;
}

int cobjallocator::destroyobject(int iobjectid)
{
    if (m_pstobjbuffer == null || m_astidxs == null)
    {
        seterrorno(een_obj_allocator__null_pointer);

        return -1;
    }

    if (iobjectid >= m_iobjcount || iobjectid < 0 || m_iobjcount <= 0)
    {
        seterrorno(een_obj_allocator__invalid_obj_index);

        return -2;
    }

    if (!m_astidxs[iobjectid].isused())
    {
        seterrorno(een_obj_allocator__destroy_free_obj);

        return -3;
    }

    //从已用链表中删除
    int icuridx = iobjectid;
    int iprevidx = m_astidxs[icuridx].getprevidx();
    int inextidx = m_astidxs[icuridx].getnextidx();

    if (iprevidx >= 0)
    {
        m_astidxs[iprevidx].setnextidx(inextidx);
    }

    if (inextidx >= 0)
    {
        m_astidxs[inextidx].setprevidx(iprevidx);
    }

    if (icuridx == m_iusedheadidx)
    {
        m_iusedheadidx = inextidx;
    }

    //挂入空闲链表尾部
    m_astidxs[iobjectid].setfree();
    m_astidxs[iobjectid].setprevidx(m_ifreetailidx);
    m_astidxs[iobjectid].setnextidx(-1);

    if (m_ifreeheadidx == -1)
    {
        m_ifreeheadidx = icuridx;
    }

    if (m_ifreetailidx >= 0)
    {
        m_astidxs[m_ifreetailidx].setnextidx(icuridx);
    }

    m_ifreetailidx = icuridx;
    --m_iusedcount;

    return 0;
}

cobj *cobjallocator::getobj(int iobjectid)
{
    if (m_pstobjbuffer == null || m_astidxs == null)
    {
        seterrorno(een_obj_allocator__null_pointer);

        return null;
    }

    if (iobjectid < 0 || iobjectid >= m_iobjcount)
    {
        seterrorno(een_obj_allocator__invalid_obj_index);

        return null;
    }

    if (!m_astidxs[iobjectid].isused())
    {
        seterrorno(een_obj_allocator__get_free_obj);

        return null;
    }

    return m_astidxs[iobjectid].getattachedobj();
}

cidx *cobjallocator::getidx(int iobjectid)
{
    if (m_pstobjbuffer == null || m_astidxs == null)
    {
        seterrorno(een_obj_allocator__null_pointer);

        return null;
    }

    if (iobjectid < 0 || iobjectid >= m_iobjcount)
    {
        seterrorno(een_obj_allocator__invalid_obj_index);

        return null;
    }

    if (!m_astidxs[iobjectid].isused())
    {
        seterrorno(een_obj_allocator__get_free_obj);

        return null;
    }

    return &m_astidxs[iobjectid];
}

cobj *cobjallocator::getnextobj(int iobjectid)
{
    cidx *pidx = getidx(iobjectid);

    if (!pidx)
    {
        return null;
    }

    int inextobjidx = pidx->getnextidx();

    return getobj(inextobjidx);
}

 

源码地址：https://github.com/dai543103/serverframework-1/blob/master/001_serverlib/baselibs/objallocator.hpp