特别声明:
建议使用google游览器,火狐也可以
论坛处于测试阶段,一切资料都为测试资料,在论坛正式运行的时候,会尽量保存网友的劳动成果!
HelloWorld论坛秉持互惠互利,共同学习与进步,一个人的梦想大家实现的理想,一直坚持着,望广大网友多多支持,提供宝贵意见
来论坛做什么?
可以先转载你平时学习查找的资料(先论坛查找),自己可以写写体会
把平时碰到的问题,如何解决可以先记录在论坛,以备后来的人学习
可以和会员一起参加一些开源项目的学习,汉化,推广,甚至可以加入团队
|
|
利用上一篇的平衡二叉树模板,实现动态不定长分配,如果有不对的地方请指正。 想法是这样的,内存管理的基本思路就是申请一块内存,来自己管理。不定长分配和定长分配的区别在于,定长是申请一块,大小小于一块大小就给予一个空闲块,释放就把空闲块加入空闲列表。而不定长是由很多定长的块组成。申请时,如果一块满足就分配一块,如果需要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 |