cramsave.h

此程序是一个模板类,主要改善大型数据的操作,效率很高,用的是静态链表的原理

//文件名:CRAMSave.h
/*  
                                    创建者:徐立
	                                创建日期:2007.08
	                                版权所有@仅供学习交流使用
*/


/*##########################[     模板使用说明     ]####################################

    该模板主要用来存储大量数据，它能够对存储的数据进行快速的遍历
	使用方法：
·将模板实例化：CRAMSave<DATATYPE> RAM;  DATATYPE是任意一种数据类型，假设这里的DATATAYPE为int
  则为：CRAMSave<int> RAM;

·增加一个对象：int* pTemData=NULL;
                          pTemData=RAM.GetNewObject();
						  ......          //用pTemData指针对增加的对象赋值
·删除一个对象:

·修改一个对象:

·对所有的对象进行遍历，有三种方法.比如要把所有对象的值设成0:
  第一种方法(建议使用,要用两个宏):
                          int *pTemData=NULL;
                          BEGIN_LOOP(RAM,pTemData,int)   //注意后面不要分号
						  *pTemData=0;
						  EDN_LOOP

  第二种方法(不建议使用,速度上要逊色很多):
                          for(int i=1;i<=RAM.GetTotalNum();i++)
						      {
							  pTemData=RAM.GetObject(i);
                              *pTemData=0;
							  }
 
  第三种方法(不建议使用,要求对模板结构比较熟悉,如果执意要使用,请参考第一种方法中的宏定义)









*/


#ifndef RAMSave_h 
#define RAMSave_h 1

#include "StdAfx.h"
#include <list>
using namespace std;
#define MAX_BLOCKNUM 16*256
//******************储存的基本单元***************//
//成员nIndex的值从1开始；
template<class T>
struct Node
{
	T Object;
	UINT nIndex;//该对象的编号
	UINT nNext;//指向标记。若紧挨着该对象的下一个对象被删除，nNext=2；若该对象后面连续有
	           //n个对象被删除，nNext=n+1；后面紧跟着没有对象删除，nNext=1；
  
  
};	
//***********************************************//


template<class DATATYPE>
class CRAMSave
{
public:
	CRAMSave();
	~CRAMSave();

	



public://………………常用函数……………………//

	         UINT GetTotalNum()const;//获得对象总个数；
	         UINT GetEachNum()const;//获得每块中存储的对象个数；
             UINT GetBlockNum()const;//获得块的个数
			 UINT GetLastNum()const;//获得最后一个数据块的对象数
			 UINT GetFactTotalNum()const;//获得实际对象总数
			 Node<DATATYPE> *GetBlockPtr(UINT blockNO);

             //功能：获取一个新对象
			 //参数：
	         //说明： 所获取的对象为空对象，要用户自己给新对象赋值
			 DATATYPE* GetNewObjectPtr();

             //功能：获得一个对象
		     //参数：（对象编号）
			 //说明：
			 DATATYPE* GetObjectPtr(UINT nIndex) ;

             //功能：删除一个对象
			 //参数：（对象编号）
			 //说明： 
			 BOOL DeleteObject(UINT nIndex);
			 
             //功能：删除一个对象
			 //参数：（对象指针）
			 //说明： 
			 BOOL DeleteObject(DATATYPE* pData);

			 //功能：获得一个新对象
			 //参数：（对象编号）
			 //说明：
             DATATYPE* operator[](UINT nIndex);
//…………………………………………………………………………//


public://………………非常用函数…………………………//

			 

			 //功能：获得一个包含对象的节点
		     //参数：（对象编号）
			 //说明：
			 //Node *GetNode(UINT nIndex) const;

             //功能：删除一个节点
			 //参数：（对象编号）
			 //说明： 
			// BOOL DeleteNode(UINT nIndex);


//………………………………………………………………………………//

protected:
	         BOOL _AddNewBlock();




private:
	//***********以下几个变量，被删除的对象算在内******************//
	UINT m_nBlockNum;//总的块数
    UINT m_nEachNum;//每块含有的对象个数,每块的最后一个对象是空的，包括最后一个对象
	UINT m_nLastNum;// 最后一块含有的对象个数；
	UINT m_nTotalNum;//所存储的对象总数，不包括每块的最后一个对象
    //***********************************************************************

private:
    UINT m_nFactTotalNum;//所存储的对象总数，不包括删除的对象和每块的最后一个对象
	Node<DATATYPE>* m_pBlockHead[MAX_BLOCKNUM];//主要用来存储每个数据块的首地址
    
	 


};



template<class DATATYPE>
CRAMSave<DATATYPE>::CRAMSave()
{
  m_nBlockNum=0;
  m_nTotalNum=0;
  m_nFactTotalNum=0;
  m_nEachNum=UINT(64*1024/sizeof(Node<DATATYPE>));
  m_nLastNum=0;
  
  for (int i=0;i<MAX_BLOCKNUM;i++) 
  {
     m_pBlockHead[i]=NULL;
  }
  if(!_AddNewBlock())
  {
     ASSERT(NULL);
	  AfxMessageBox("哈哈!怎么受伤的总是你!为电脑加点内存吧! 程序将中断运行!");
  }
}

template<class DATATYPE>
CRAMSave<DATATYPE>::~CRAMSave()
{
 for (int i=0;i<m_nBlockNum;i++) 
 {
	 delete []m_pBlockHead[i];
 }
}

template<class DATATYPE>
UINT CRAMSave<DATATYPE>::GetBlockNum() const
{
	return m_nBlockNum;
}

template<class DATATYPE>
UINT CRAMSave<DATATYPE>::GetEachNum() const
{
	return m_nEachNum;
}

template<class DATATYPE>
UINT CRAMSave<DATATYPE>::GetTotalNum() const
{
	return m_nTotalNum;
}

template<class DATATYPE>
UINT CRAMSave<DATATYPE>::GetFactTotalNum() const
{
	return m_nFactTotalNum;
}

template<class DATATYPE>
UINT CRAMSave<DATATYPE>::GetLastNum() const
{
	return m_nLastNum;
}

template<class DATATYPE>
Node<DATATYPE>* CRAMSave<DATATYPE>::GetBlockPtr(UINT blockNO)
{
	ASSERT(blockNO>0&&blockNO<=m_nBlockNum);
	if (blockNO<0||blockNO>m_nBlockNum) 
    return NULL;
	return m_pBlockHead[blockNO-1];
}

template<class DATATYPE>
BOOL CRAMSave<DATATYPE>::_AddNewBlock()
{
	Node<DATATYPE>* pTemBlock=NULL;
  pTemBlock=new Node<DATATYPE>[m_nEachNum];
  if (pTemBlock) 
  {
	    for (int i=0;i<m_nEachNum;i++) 
		{
         pTemBlock[i].nIndex=0;
	     pTemBlock[i].nNext=0;
		}
		//pTemBlock[m_nEachNum-1]=0;//特殊处理，每块最后一个对象存储的偏移量为0（主要是为了防止指针溢出）
        m_pBlockHead[m_nBlockNum]=pTemBlock;
	    m_nBlockNum++;
	    return TRUE;
  }
  else return FALSE;
}

template<class DATATYPE>
DATATYPE* CRAMSave<DATATYPE>::GetNewObjectPtr()
{
  Node<DATATYPE>* pTemBlock=NULL;
  m_nTotalNum++;
  m_nFactTotalNum++;
  if (m_nLastNum<m_nEachNum-1)
  {
    pTemBlock=m_pBlockHead[m_nBlockNum-1];
	ASSERT(pTemBlock);
	pTemBlock[m_nLastNum].nIndex=m_nTotalNum;
    pTemBlock[m_nLastNum].nNext=1;
	m_nLastNum++;
	return &(pTemBlock[m_nLastNum-1].Object);
  }
  else
  {
	  if(_AddNewBlock())
	  {
	m_nLastNum=1;
	pTemBlock=m_pBlockHead[m_nBlockNum-1];
	ASSERT(pTemBlock);
	pTemBlock[0].nIndex=m_nTotalNum;
	return &(pTemBlock[0].Object);

	  }

	   ASSERT(NULL);
	  AfxMessageBox("内存不足耶! 程序将要中断运行!");
	  exit(1);
  }
  
}



template<class DATATYPE>
DATATYPE* CRAMSave<DATATYPE>::GetObjectPtr(UINT nIndex)      
{
	if (nIndex<1||nIndex>m_nTotalNum)
	{
	    ASSERT(NULL);
		return NULL;
	}
	UINT BlockNO=1;
	UINT EachNO=1;
	UINT ntemVar=0;
	ntemVar=UINT(nIndex/m_nEachNum);
	EachNO=nIndex-ntemVar*m_nEachNum;
	if (0==EachNO) //若刚好是某块的最后一个对象
		return NULL;
	Node<DATATYPE>* pTemBlock=NULL;
	pTemBlock=m_pBlockHead[ntemVar];
	if (0==pTemBlock[EachNO-1].nIndex) 
    return NULL;
	return &(pTemBlock[EachNO-1].Object);

}

template<class DATATYPE>
BOOL CRAMSave<DATATYPE>::DeleteObject(UINT nIndex)    
{
	if (nIndex<1||nIndex>m_nTotalNum)
	return FALSE;

//	UINT BlockNO=1;
	UINT EachNO=1;
	UINT ntemVar=0;
	ntemVar=UINT(nIndex/m_nEachNum);
	EachNO=nIndex-ntemVar*m_nEachNum;
	if (0==EachNO) //若刚好是某块的最后一个对象
		return TRUE;
    Node<DATATYPE>* pTemBlock=NULL;
	pTemBlock=m_pBlockHead[ntemVar];
	if (0==pTemBlock[EachNO-1].nIndex) return TRUE;//若该对象已经被删除
   pTemBlock[EachNO-1].nIndex=0;
	for (UINT i=2;i<EachNO+1;i++)//往左边开始追溯
	{
		if (0==pTemBlock[EachNO-i].nIndex)//若前一个对象已经被删除
		{
		  pTemBlock[EachNO-i].nNext=pTemBlock[EachNO-i].nNext+pTemBlock[EachNO-1].nNext;
          continue;
		}
		else
		{
         pTemBlock[EachNO-i].nNext=pTemBlock[EachNO-i].nNext+pTemBlock[EachNO-1].nNext;
		 break;
		}

	}	
   m_nFactTotalNum--;
   return TRUE;

}

template<class DATATYPE>
BOOL CRAMSave<DATATYPE>::DeleteObject(DATATYPE* pData)    
{

	   UINT index=0;
       Node<DATATYPE>* pTemBlock=NULL;
       for (UINT i=0;i<m_nBlockNum;i++ ) 
	   {
         pTemBlock=m_pBlockHead[i];
          if (0==pTemBlock->nNext)
			pTemBlock=pTemBlock+pTemBlock->nNext;
          while (0!=pTemBlock->nNext)
		  {
           if (pData==&(pTemBlock->Object)) 
		   { 
            index=pTemBlock->nIndex;
			break;
           }
           pTemBlock=pTemBlock+pTemBlock->nNext;
		  }
		  if(index!=0)
			  break;
	   }
     DeleteObject(index);
	 return TRUE;


	
  	


}


template<class DATATYPE>
DATATYPE* CRAMSave<DATATYPE>::operator[](UINT nIndex) 
{
	if (nIndex<1||nIndex>m_nTotalNum)
	{
        //AfxMessageBox("所要找的对象不存在！  将返回一个空对象");
		return NULL;
	}
	UINT BlockNO=1;
	UINT EachNO=1;
	UINT ntemVar=0;
	ntemVar=UINT(nIndex/m_nEachNum);
	EachNO=nIndex-ntemVar*m_nEachNum;
	if (0==EachNO) //若刚好是某块的最后一个对象
		return NULL;
	Node<DATATYPE>* pTemBlock=NULL;
	pTemBlock=m_pBlockHead[ntemVar];
	if (0==pTemBlock[EachNO-1].nIndex) 
    return NULL;
	return &(pTemBlock[EachNO-1].Object);
}
			

	
//参数说明:(CRAMSave对象，DATATYPE类型的指针,DATATYPE类型)

#define BEGING_LOOP(RAM,pData,DATATYPE)   \
	   Node<DATATYPE>* pTemBlockMarco=NULL;\
       for (UINT nLoopVarMarco=1;nLoopVarMarco<=RAM.GetBlockNum();nLoopVarMarco++ ) {\
        pTemBlockMarco=RAM.GetBlockPtr(nLoopVarMarco);\
        if (0==pTemBlockMarco->nNext)\
			pTemBlockMarco=pTemBlockMarco+pTemBlockMarco->nNext;\
          while (0!=pTemBlockMarco->nNext){pData=&(pTemBlockMarco->Object);

          

#define END_LOOP pTemBlockMarco=pTemBlockMarco+pTemBlockMarco->nNext;\
        }\
	   }
	 
	    

	 




	




#endif

/*
在后面的宏定义中如果写成
RAM.GetpBlock()=*(RAM.GetIterator());会报错
定义一个中间变量即可解决

如果直接在宏其中定义：Node* pp;也会报错
所以先要把Ｎｏｄｅ　定义在ＣＲＡＭＳａｖｅ的外面，再在宏中定义：Node<DataType> *pp;即可

注意：宏定义时一定不能有空行

内存开辟时，计算机自动按4字节对齐。如果一个对象大小为m，指针加一，地址上移动m；指针变量的大小是4个字节


















  */