欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-11 08:10:20
1.1 数组的特点 连续的内存空间分配并且顺序存储数据,使用之前需要先分配数组个数; 可以通过下标进行访问修改数据,时间复杂度为O(1); 空间效率不是很好,不能随意修改数组大小; 增删数据需要内存拷贝 1.2 链表的特点 内存空间分配是分散的,非连续的存储数据; 不能通过下标直接访问,查找的时间复 ......

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