继上篇
《简单堆结构的实现》之后修改了下代码,使内存的分配效率更高.
首先将HeapApplyed和HeapUsed包含进一个结构体HEAPATTR,各占1位.
1 struct HEAPATTR
2 {
3 BYTE HeapApplyed : 1;
4 BYTE HeapUsed : 1;
5 }*HeapAttr;
然后添加了一个HeapCurrent变量用于提高检索速度.
1 int HeapCurrent;
相应的构造函数和析构函数修改为.
1 Heap(const int Size = 1024 * 300)
2 : HeapLength(Size),HeapCurrent(0),HeapLeft(Size)
3 {
4 HeapData = new CHAR[HeapLength];
5 HeapAttr = new HEAPATTR[HeapLength];
6 memset(HeapData,0,HeapLength);
7 memset(HeapAttr,0,HeapLength);
8 }
9
10 ~Heap()
11 {
12 delete[] HeapData;
13 delete[] HeapAttr;
14 }
注意:一个HEAPATTR结构占1个字节,实际上使用的只有2位,编译器自动为其补齐6位形成1字节(既然只有TRUE和FALSE没理由要用HeapLength*2字节
)
修改GetEmptyAddr算法,使其提升效率.
1 CHAR* GetEmptyAddr(const int Size)
2 {
3 int Left = 0;
4 for(int i=HeapCurrent;i<HeapLength;i++)
5 {
6 if(HeapAttr[i].HeapApplyed && !HeapAttr[i].HeapUsed) Left++;
7 else Left = 0;
8 if(Left == Size) return HeapData + i - Left + 1;
9 }
10 if(HeapCurrent > 0 && HeapCurrent > Size)
11 {
12 Left = 0;
13 for(int i=0;i<HeapCurrent;i++)
14 {
15 if(HeapAttr[i].HeapApplyed && !HeapAttr[i].HeapUsed) Left++;
16 else Left = 0;
17 if(Left == Size) return HeapData + i - Left + 1;
18 }
19 }
20 return 0;
21 }
同时也将GetEmptyLeft修改为.
1 inline int GetEmptyLeft(int Size)
2 {
3 int Left = 0;
4 for(int i=HeapCurrent;i<HeapLength;i++)
5 {
6 if(!HeapAttr[i].HeapApplyed) Left++;
7 else Left = 0;
8 if(Left == Size) return i - Left + 1;
9 }
10 if(HeapCurrent > 0 && HeapCurrent > Size)
11 {
12 Left = 0;
13 for(int i=0;i<HeapCurrent;i++)
14 {
15 if(!HeapAttr[i].HeapApplyed) Left++;
16 else Left = 0;
17 if(Left == Size) return i - Left + 1;
18 }
19 }
20 return 0;
21 }
添加DumpFile函数生成Dump文件.
1 BOOL DumpFile(CHAR* FileName)
2 {
3 FILE* fp = fopen(FileName,"wt+");
4 fwrite(HeapData,HeapLength,sizeof(CHAR),fp);
5 fclose(fp);
6 return TRUE;
7 }
最后给出
完整代码
posted on 2011-02-22 17:29
lwch 阅读(1895)
评论(1) 编辑 收藏 引用 所属分类:
数据结构