smallmemalloc.h

随着计算机信息技术的飞速发展

#ifndef _TT_SMALL_MEMORY_ALLOCATE_H_
#define _TT_SMALL_MEMORY_ALLOCATE_H_

#ifndef BYTE
#define BYTE unsigned char
#endif

#ifndef UINT
#define UINT unsigned int
#endif

#ifndef DWORD
#define DWORD unsigned long
#endif

#include <vector>
using std::vector;

#define BIT_VALUE(Value, Pos)   ((Value>>Pos) & 0x01)
#define BIT_VALUE_1(Value, Pos) Value = 0x01<<Pos | Value
#define BIT_VALUE_0(Value, Pos) Value = ~(0x01<<Pos) & Value

#define SMA_MEMORYINFO_BYTELEN		4
#define SMA_INDEX_CLUSTER			1
#define SMA_INDEX_BEGIN_SECTOR		2
#define SMA_INDEX_SECTOR_NUM		3
#define SMA_MAX_SECTORS_PERALLOC	10

template<int SECTORS_IN_CLUSTER, int BYTES_IN_SECTOR>
class CSmallMemoryAlloc
{
public:
	static BYTE* Alloc(UINT lLen);
	static void  Free(BYTE* pMemory);

private:
	CSmallMemoryAlloc()
	{
		m_vClusters.push_back(new Cluster(m_vClusters.size()));
	};
	~CSmallMemoryAlloc()
	{
		for(int i=0; i<m_vClusters.size(); i++)
			delete m_vClusters[i];
		m_vClusters.clear();
	};
	static CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>* GetInstance();
	static void Release();

private:
	struct Cluster
	{
		Cluster(UINT nIndex)
		{
			nSelfIndex = nIndex;
			dwSign = 0;
			pMemory = new BYTE[SECTORS_IN_CLUSTER*BYTES_IN_SECTOR];
			pFirstFM = pMemory;
			nFirstFMIndex = 0;
		};
		~Cluster()
		{
			delete[] pMemory;
		};
		UINT  nSelfIndex;
		DWORD dwSign;
		BYTE* pMemory;
		BYTE* pFirstFM;
		UINT  nFirstFMIndex;

		bool IsPtrIn(BYTE* ptr)
		{
			return ptr>=pMemory && ptr<=(pMemory+(SECTORS_IN_CLUSTER-1)*BYTES_IN_SECTOR);
		};
		BYTE* AllocSectors(UINT nSectors)
		{
			if(pFirstFM == NULL || nSectors == 0 || nSectors > SECTORS_IN_CLUSTER)
				return NULL;
			UINT nFreeSectors=0;
			BYTE* pbyMemory = pFirstFM;
			for(UINT i=nFirstFMIndex; i< SECTORS_IN_CLUSTER; i++)
			{
				if(nFreeSectors == nSectors)
				{
					for(UINT j=0; j<nSectors; j++)
						BIT_VALUE_1(dwSign, (i-j-1));

					*pbyMemory     = 0xff;				//保留
					*(pbyMemory+SMA_INDEX_CLUSTER)		= (BYTE)nSelfIndex;	//Cluster的索引
					*(pbyMemory+SMA_INDEX_BEGIN_SECTOR) = (BYTE)i-nSectors; //开始扇区的索引
					*(pbyMemory+SMA_INDEX_SECTOR_NUM)	= (BYTE)nSectors;	//扇区数
					pbyMemory += SMA_MEMORYINFO_BYTELEN;
					memset(pbyMemory, 0, nSectors*BYTES_IN_SECTOR-SMA_MEMORYINFO_BYTELEN);
					
					UINT nOldIndex = nFirstFMIndex;
					while(BIT_VALUE(dwSign, nFirstFMIndex))
					{
						if(nFirstFMIndex == SECTORS_IN_CLUSTER-1)
						{
							nFirstFMIndex ++;
							pFirstFM = NULL;
							break;
						}
						nFirstFMIndex ++;
					}
					if(pFirstFM != NULL && nOldIndex != nFirstFMIndex)
						pFirstFM = pFirstFM + (nFirstFMIndex-nOldIndex)*BYTES_IN_SECTOR;
					return pbyMemory;
				}
				if(!BIT_VALUE(dwSign, i))
					nFreeSectors ++;
				else
				{
					nFreeSectors = 0;
					pbyMemory = pMemory+(i+1)*BYTES_IN_SECTOR;
				}
			}
			return NULL;
		};
		bool FreeSectors(BYTE* pbyMemory)
		{
			if(IsPtrIn(pbyMemory))
			{
				UINT nBegin, nLen;
				nBegin = *(pbyMemory-(SMA_MEMORYINFO_BYTELEN-SMA_INDEX_BEGIN_SECTOR));
				nLen = *(pbyMemory-(SMA_MEMORYINFO_BYTELEN-SMA_INDEX_SECTOR_NUM));
				for(int i=0; i<nLen; i++)
					BIT_VALUE_0(dwSign, (nBegin+i));

				if(nFirstFMIndex > nBegin)
				{
					nFirstFMIndex = nBegin;
					pFirstFM = pbyMemory-SMA_MEMORYINFO_BYTELEN;
				}
				return true;
			}
			return false;
		};
	};
	vector<Cluster*> m_vClusters;
	static CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>* m_pInstance;
};

template<int SECTORS_IN_CLUSTER, int BYTES_IN_SECTOR>
CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>* CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>::m_pInstance = NULL;

template<int SECTORS_IN_CLUSTER, int BYTES_IN_SECTOR>
CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>* CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>::GetInstance()
{
	if(!m_pInstance)
	{
		atexit(Release);
		m_pInstance = new CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>();
	}
	return m_pInstance;
}

template<int SECTORS_IN_CLUSTER, int BYTES_IN_SECTOR>
void CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>::Release()
{
	delete m_pInstance;
	m_pInstance = NULL;
}

template<int SECTORS_IN_CLUSTER, int BYTES_IN_SECTOR>
BYTE* CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>::Alloc(UINT lLen)
{
	if(lLen == 0)
		return NULL;
	if(lLen > SMA_MAX_SECTORS_PERALLOC*BYTES_IN_SECTOR)
		return new BYTE[lLen];
	CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>* pInstance = GetInstance();
	lLen += SMA_MEMORYINFO_BYTELEN;
	UINT nSectors = lLen/BYTES_IN_SECTOR;
	if(lLen % BYTES_IN_SECTOR > 0)
		nSectors ++;
	BYTE* bytMem = NULL;
	for(int i=0; i<pInstance->m_vClusters.size(); i++)
	{
		bytMem = pInstance->m_vClusters[i]->AllocSectors(nSectors);
		if(bytMem)
			return bytMem;
	}
	if(bytMem==NULL)
	{
		Cluster* pNewCluster = new Cluster(pInstance->m_vClusters.size());
		pInstance->m_vClusters.push_back(pNewCluster);
		return pNewCluster->AllocSectors(nSectors);
	}
	return NULL;
}

template<int SECTORS_IN_CLUSTER, int BYTES_IN_SECTOR>
void  CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>::Free(BYTE* pMemory)
{
	if(pMemory == NULL)
		return;
	CSmallMemoryAlloc<SECTORS_IN_CLUSTER, BYTES_IN_SECTOR>* pInstance = GetInstance();
	UINT nIndex = *(pMemory-(SMA_MEMORYINFO_BYTELEN-SMA_INDEX_CLUSTER));
	if(nIndex >=0 && nIndex < pInstance->m_vClusters.size())
	{
		if(pInstance->m_vClusters[nIndex]->FreeSectors(pMemory))
			return;
	}
	delete[] pMemory;
};

#endif