我們知道對于一個數據堆,有申請內存塊,釋放內存塊等操作.
應此我們給出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 閱讀(2119)
評論(3) 編輯 收藏 引用 所屬分類:
數據結構