我们知道对于一个数据堆,有申请内存块,释放内存块等操作.
应此我们给出3个数组,分别为内存堆,标记数组,使用是否数组和一个变量用于表示内存堆内剩余空间数.
1 CHAR HeapData[HEAP_LENGTH];
2 CHAR HeapApplyed[HEAP_LENGTH];
3 CHAR HeapUsed[HEAP_LENGTH];
4
5 int HeapLeft; // 剩余Heap大小
初始化时将3个数组全部设为0.
1 memset(HeapData,0,HEAP_LENGTH);
2 memset(HeapApplyed,0,HEAP_LENGTH);
3 memset(HeapUsed,0,HEAP_LENGTH);
然后我们需要一个New操作来申请一块尚未使用的内存块.
1 CHAR* New(const int Size)
2 {
3 if(Size > HeapLeft) throw HEAP_OVERFLOW;
4 int iEmpty = GetEmptyLeft(Size);
5
6 memset(HeapApplyed + iEmpty,1,Size); // 将内存块标记
7
8 HeapLeft -= Size;
9 return HeapData + iEmpty;
10 }
一个Free操作来释放一个内存块.
1 BOOL Free(const int Offset,const int Size)
2 {
3 if(!Apply(Offset,Size)) throw HEAP_NOTAPPLY;
4 memset(HeapApplyed + Offset,0,Size); // 设置为未标记
5 memset(HeapUsed + Offset,0,Size); // 标记为未使用
6 HeapLeft += Size;
7 return TRUE;
8 }
一个GetEmptyAddr操作来获得第一个符合指定大小的空闲内存卡块.
1 CHAR* GetEmptyAddr(const int Size)
2 {
3 for(int i=0;i<HEAP_LENGTH;i++)
4 if(HeapApplyed[i] && !HeapUsed[i]) // 已标记并未使用
5 {
6 BOOL bContinue = FALSE;
7 for(int j=i;j<Size;j++)
8 if(!HeapApplyed[j] || HeapUsed[j]) // 未标记或已使用
9 {
10 bContinue = TRUE;
11 break;
12 }
13 if(bContinue) continue;
14 return HeapData + i;
15 }
16 return 0;
17 }
和一个SetData操作来设置数据.
1 BOOL SetData(const int Offset,const Type* Data,const int Size)
2 {
3 if(!Apply(Offset,Size)) throw HEAP_NOTAPPLY;
4 memcpy(HeapData + Offset,Data,Size); // 拷贝数据
5 memset(HeapUsed + Offset,1,Size); // 标记为已使用
6 return TRUE;
7 }
最后我们来测试一下这个堆结构.
1 try
2 {
3 Heap<CHAR> heap;
4 heap.New(9000);
5
6 int i = 1000;
7 heap.Free(0,100);
8 printf("EmptyAddr:%X\n",heap.GetEmptyAddr(sizeof(int)));
9
10 int* Addr1 = (int*)heap.GetEmptyAddr(sizeof(int));
11 heap.SetData((CHAR*)Addr1 - *heap,(CHAR*)&i,sizeof(int));
12
13 printf("The Data In Heap:%d\n",*Addr1);
14
15 heap.New(100);
16 printf("EmptyAddr:%X\n",heap.GetEmptyAddr(sizeof(int)));
17
18 CHAR str[] = "aaaaa";
19 CHAR* Addr2 = heap.GetEmptyAddr(strlen(str));
20 heap.SetData(Addr2 - *heap,str,strlen(str));
21
22 printf("The Data In Heap:%s\n",Addr2);
23
24 printf("EmptyAddr:%X\n",heap.GetEmptyAddr(sizeof(int)));
25 }
26 catch(int i)
27 {
28 switch(i)
29 {
30 case HEAP_OVERFLOW:
31 printf("堆溢出\n");
32 break;
33 case HEAP_NOTAPPLY:
34 printf("错误的地址\n");
35 break;
36 }
37 }
测试结果:
1 EmptyAddr:4EFB0
2 The Data In Heap:1000
3 EmptyAddr:4EF4C
4 The Data In Heap:aaaaa
5 EmptyAddr:4EF51
下面给出
完整代码
posted on 2011-02-15 20:59
lwch 阅读(2063)
评论(3) 编辑 收藏 引用 所属分类:
数据结构