特别声明：
建议使用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 |
个人签名--------------------------------------------------------------------------------