支持HW团队,就支付宝领取下面的红包吧!(2018年3月31前,就几毛,也会几块,可以和其他红包叠加使用),你领取消费,HW有奖励。红包使用无条件限制,有条件请注意是不是有病毒。

小伙伴们,给大家发红包喽!人人可领,领完就能用。祝大家领取的红包金额大大大!#吱口令#长按复制此消息,打开支付宝就能领取!er1OEj73Uj

登入 注册 | 验证
| 搜索
HelloWorld论坛 : > 计算机科学、技术、教学> 编程专题> 开源免费项目> [原创]ACE内存分配——不定长数据,不定量个数分配(三)——平衡二叉树实现真正的不定长分配
 
 
 
 
 
 
类别:ACE 阅读:4145 评论:0 时间:五月 21, 2013, 5:48 p.m. 关键字:ACE AVL tree 内存 平衡二叉树

 

利用上一篇的平衡二叉树模板,实现动态不定长分配,如果有不对的地方请指正。

想法是这样的,内存管理的基本思路就是申请一块内存,来自己管理。不定长分配和定长分配的区别在于,定长是申请一块,大小小于一块大小就给予一个空闲块,释放就把空闲块加入空闲列表。而不定长是由很多定长的块组成。申请时,如果一块满足就分配一块,如果需要2块,就分配给连续的两块,以此类推。当释放的时候,要把相邻的空闲块并成大块。

所以不定长的分配,块有3种状态,1 空闲块开头的那一块。3使用块开头的那一块,0 使用,空闲连续的块。因此,块的状态我们用2个字节表示。

我们把申请的内存块,分成两部分,前面为数据头,连续存放快状态,后面为数据体,连续存放数据块。

数据头中存放连续块状态,用来模拟数据体连续块,实现数据释放后,快速合并连续块。平衡二叉树,用来快速查找,忙着请求的最小空闲块。平衡二叉树,存放的是状态为1的节点。

/***************************************************************
version:  1.0
date: 16/5/2013   17:04
FileName:     hwnet_variable_allocator.h
Author:       丁灵峰
Compiled on:   VC.net 2008
-------------------------------------------------------------
Description:
Modification history:
Other:

-------------------------------------------------------------
Copyright (C) 2010 - All Rights Reserved
***************************************************************

申请一块内存区域,m_pBuf,分为两部分:
前面是头部,m_pBufHead,两位表示一个节点,存放m_BufSum个。
后面是数据实体,m_MinBufSize大小,存放m_BufSum个。

其中头部和实体一一对应。
头部       实体
0        和前面连续使用的块
1        空闲块开头
3        使用块开头

****************************************************************/
#if (defined HW_ACE) && (defined HW_ACE_ALLOCATOR)  // 使用自定义内存管理
#ifndef _H_hwnet_variable_allocator_
#define _H_hwnet_variable_allocator_

#include "ace/Malloc.h"
#include <ace/Malloc_T.h>
#include <boost/shared_ptr.hpp>
#include "hwnet_avl_tree.h"

namespace hwnet
{
        class HW_Allocator
                : public ACE_New_Allocator
        {
        public:
                virtual size_t size (void)
                {
                        return 0;
                }
        };
        const size_t AvlDateNodeUnionSize = 128;
        template <class ACE_LOCK>
        class AvlDateNode
        {
        public:
                AvlDateNode<ACE_LOCK>(size_t iDataSum // 值
                )
                : m_Date(iDataSum) // 值
                , m_pFather(NULL) // 指向父节点的地址
                , m_pLchild(NULL) // 指向左儿子的地址
                , m_pRchild(NULL) // 指向右儿子的地址
                , m_pNode(NULL) // 指向等值节点的地址
                , m_ihgt(0)
                {
                        assert(m_Date);
                }
                ~AvlDateNode<ACE_LOCK>()
                {
                }
                static AvlDateNode<ACE_LOCK>* GetDateNode(void* ptr)
                {
                        if (ptr)
                        {
                                return (AvlDateNode<ACE_LOCK>*)(((char*)ptr) - (sizeof(AvlDateNode<ACE_LOCK>) - sizeof(char)*AvlDateNodeUnionSize));
                        }
                        return NULL;
                }
                /// Return the address of free memory.
                void* addr (void)
                {
                        return &m_bDate;
                }
                ///// Get the next AvlDateNode in a list.
                //AvlDateNode<ACE_LOCK> *get_next (void)
                //{
                //      return next_;
                //}

                ///// Set the next AvlDateNode.
                //void set_next (AvlDateNode<ACE_LOCK> *ptr)
                //{
                //      next_ = ptr;
                //}

        public:
                size_t m_Date;//值
                union
                {
                        struct
                        {
                                size_t m_ihgt;//以此节点为根的树的高度
                                AvlDateNode<ACE_LOCK>* m_pFather;//指向父节点的地址
                                AvlDateNode<ACE_LOCK>* m_pLchild;//指向左儿子的地址
                                AvlDateNode<ACE_LOCK>* m_pRchild;//指向右儿子的地址
                                AvlDateNode<ACE_LOCK>* m_pNode;//指向等值节点的地址
                        };
                        char m_bDate[AvlDateNodeUnionSize];
                };
        };
        // 不定长数据申请 AVL树实现
        template <class ACE_LOCK>
        class AVLTreeVariableAllocator
                : public HW_Allocator
        {
                static const size_t TYPE_NULL = 0x0;
                static const size_t TYPE_EMPTY = 0x1;
                static const size_t TYPE_USED = 0x3;
        public:
#ifdef HW32
                // 32位编译
                static const long s_iHeadSum=16;
#else
                // 64位编译
                static const long s_iHeadSum=32;
#endif // HW32
                AVLTreeVariableAllocator(
                        char* pBufHead
                        , char* pBufBody
                        , size_t BufSum // 一次申请个数
                        , size_t MinBufSize // 最小数据内存
                        , size_t MenLeng // 单位数据内存大小,几个零,二进制
                        )
                        : m_pBuf(pBufBody) // 实际数据
                        , m_BufSum(BufSum) // 一次申请个数
                        , m_BufSize(MinBufSize) // 单位数据内存大小
                        , m_MenLeng(MenLeng) //  单位数据内存大小,几个零,二进制
                        , m_pBufHead(NULL) // 数据头,快速合并空闲空间
                        , m_uSimBuf(BufSum) // 空闲内存数量
                {
#ifdef HW32
                        // 32位编译
                        m_pBufHead = (boost::uint32_t*)pBufHead;
#else
                        // 64位编译
                        m_pBufHead = (boost::uint64_t*)pBufHead;
#endif // HW32
                        if (pBufHead && m_pBuf)
                        {
                                ACE_OS::memset (pBufHead, 0, (size_t)pBufBody - (size_t)pBufHead);
                                // 初始化头
                                this->SetHead(0, TYPE_EMPTY);
                                // 根节点
                                avlTree.Insert(new (m_pBuf) AvlDateNode<ACE_LOCK>(m_BufSum));
                        }
                        else
                        {
                                m_uSimBuf = 0;
                        }
                }
                ~AVLTreeVariableAllocator()
                {
                }
                virtual void *malloc (size_t nbytes)
                {
                        // 规范大小为 m_MinBufSize 的整数倍
                        size_t iSize = (ACE_MALLOC_ROUNDUP ((nbytes + (sizeof(AvlDateNode<ACE_LOCK>) - sizeof(char)*AvlDateNodeUnionSize)), m_BufSize)) >> m_MenLeng;
                        ACE_GUARD_RETURN (ACE_LOCK, monitor, this->m_lock, NULL);
                        AvlDateNode<ACE_LOCK>* pNode = avlTree.FindLessOrGreater(iSize);//查找
                        if (pNode != NULL)
                        {
                                avlTree.Delete(pNode);
                                size_t iPose = ((size_t)pNode - (size_t)m_pBuf) >> m_MenLeng;
                                this->SetHead(iPose, TYPE_USED);
                                if (pNode->m_Date == iSize)
                                {
                                }
                                else // pNode->m_Date > iSize
                                {
                                        size_t iPoseEx = (((size_t)pNode - (size_t)m_pBuf) >> m_MenLeng) + iSize;
                                        this->SetHead(iPoseEx, TYPE_EMPTY);
                                        avlTree.Insert(new (m_pBuf + (iPoseEx << m_MenLeng)) AvlDateNode<ACE_LOCK>(pNode->m_Date - iSize));
#ifdef _DEBUG
                                        AvlDateNode<ACE_LOCK>* pNodeAft = (AvlDateNode<ACE_LOCK>*)(m_pBuf + (iPoseEx << m_MenLeng));
#endif // _DEBUG
                                        pNode->m_Date = iSize;
                                }
                                m_uSimBuf -= iSize;
                                //std::cout << avlTree.size() << "  " << m_uSimBuf << "AA  ";
                                //avlTree.Traversal();
                                return pNode->addr();
                        }
                        return NULL;
                }
                virtual void *calloc (size_t nbytes, char initial_value = '\0')
                {
                        void* ptr = malloc(nbytes);
                        if (ptr)
                        {
                                ACE_OS::memset (ptr, initial_value, nbytes);
                        }

                        return ptr;
                }
                virtual void *calloc (size_t n_elem, size_t elem_size, char initial_value = '\0')
                {
                        return calloc (n_elem * elem_size, initial_value);
                }
                virtual void free (void* ptr)
                {
                        assert(m_BufSum - m_uSimBuf > 0);
                        ACE_GUARD (ACE_LOCK, monitor, this->m_lock);
                        if (ptr)
                        {
                                AvlDateNode<ACE_LOCK>* pNode = AvlDateNode<ACE_LOCK>::GetDateNode(ptr);
                                m_uSimBuf += pNode->m_Date;
                                size_t iPose = ((size_t)pNode - (size_t)m_pBuf) >> m_MenLeng;
                                this->SetHead(iPose, TYPE_EMPTY);
                                size_t iPoseEx = iPose+pNode->m_Date;
                                // 并下一个
                                if ((iPoseEx < m_BufSum) && (this->GetHead(iPoseEx) == TYPE_EMPTY))
                                {
                                        AvlDateNode<ACE_LOCK>* pNodePre = (AvlDateNode<ACE_LOCK>*)(m_pBuf + (iPoseEx << m_MenLeng));
                                        avlTree.Delete(pNodePre);
                                        pNode->m_Date += pNodePre->m_Date;
                                        this->SetHead(iPoseEx, TYPE_NULL);
                                        //std::cout << "并下一个  ";
                                }
                                // 并前一个
                                iPoseEx = iPose;
                                for (;iPoseEx>0;)
                                {
                                        iPoseEx--;
                                        size_t iVule = this->GetHead(iPoseEx);
                                        if (iVule != TYPE_NULL)
                                        {
                                                if (iVule == TYPE_EMPTY)
                                                {
                                                        AvlDateNode<ACE_LOCK>* pNodeAft = (AvlDateNode<ACE_LOCK>*)(m_pBuf + (iPoseEx << m_MenLeng));
                                                        avlTree.Delete(pNodeAft);
                                                        this->SetHead(iPose, TYPE_NULL);
                                                        pNodeAft->m_Date += pNode->m_Date;
                                                        pNode = pNodeAft;
                                                        //std::cout << "并前一个  ";
                                                }
                                                break;
                                        }
                                }
                                avlTree.Insert(pNode);
                                //std::cout << avlTree.size() << "  " << m_uSimBuf << "AA  ";
                                //avlTree.Traversal();
                        }
                        return ;
                }
                size_t size()
                {
                        return m_uSimBuf;
                }
        protected:
#ifdef HW32
                // 32位编译
                void SetHead(size_t iPose, boost::uint32_t iValue)
#else
                // 64位编译
                void SetHead(size_t iPose, boost::uint64_t iValue)
#endif // HW32
                {
                        if ((0 <= iPose) && (iPose < m_BufSum))
                        {
                                iValue <<= ((iPose  & (s_iHeadSum - 1)) << 1);
#ifdef HW32
                                // 32位编译
                                boost::uint32_t iValueEx = (boost::uint32_t)0X3 << ((iPose & (s_iHeadSum - 1)) << 1);
#else
                                // 64位编译
                                boost::uint64_t iValueEx = (boost::uint64_t)0X3 << ((iPose & (s_iHeadSum - 1)) << 1);
#endif // HW32
                                iValueEx = ~iValueEx;
#ifdef HW32
                                // 32位编译
                                m_pBufHead [(iPose & ~(s_iHeadSum - 1)) >> 4] &= iValueEx;
                                m_pBufHead [(iPose & ~(s_iHeadSum - 1)) >> 4] |= iValue;
#else
                                // 64位编译
                                m_pBufHead [(iPose & ~(s_iHeadSum - 1)) >> 5] &= iValueEx;
                                m_pBufHead [(iPose & ~(s_iHeadSum - 1)) >> 5] |= iValue;
#endif // HW32
                        }
                }
                size_t GetHead(size_t iPose)
                {
                        if ((0 <= iPose) && (iPose < m_BufSum))
                        {
#ifdef HW32
                                // 32位编译
                                boost::uint32_t iValue = (boost::uint32_t)0X3 << ((iPose & (s_iHeadSum - 1)) << 1);
#else
                                // 64位编译
                                boost::uint64_t iValue = (boost::uint64_t)0X3 << ((iPose & (s_iHeadSum - 1)) << 1);
#endif // HW32
#ifdef HW32
                                // 32位编译
                                iValue = m_pBufHead [(iPose & ~(s_iHeadSum - 1)) >> 4] & iValue;
#else
                                // 64位编译
                                iValue = m_pBufHead [(iPose & ~(s_iHeadSum - 1)) >> 5] & iValue;
#endif // HW32
                                return iValue >> ((iPose & (s_iHeadSum - 1)) << 1);
                        }
                        return 2;
                }
        private:
                ACE_LOCK m_lock;
                size_t m_BufSum; // 一次申请个数
                size_t m_BufSize; // 单位数据内存大小
                size_t m_MenLeng; // 单位数据内存大小,几个零,二进制
#ifdef HW32
                // 32位编译
                boost::uint32_t* m_pBufHead; // 数据头,快速合并空闲空间
#else
                // 64位编译
                boost::uint64_t* m_pBufHead; // 数据头,快速合并空闲空间
#endif // HW32
                char* m_pBuf; // 实际数据
                AVLTree<AvlDateNode<ACE_LOCK>, size_t> avlTree; // 平衡二叉树
                size_t m_uSimBuf; // 空闲内存数量
        };
}
#endif // #ifndef _H_hwnet_variable_allocator_
#endif // HW_ACE HW_ACE_ALLOCATOR  //使用自定义内存管理

 

[挂载人]初学MPEG [审核人]初学MPEG 推荐

个人签名--------------------------------------------------------------------------------

Please Login (or Sign Up) to leave a comment