HTK代码阅读之内存管理 - flywithyou
本文原帖地址：http://xs.langlang.cc/yuedu/yuedu1000_2.htm，加了一些说明，在此向原作者（陈国平）表示感谢。
一、 HTK内存管理概述
C语言编程中，遇到的关于内存分配和释放的问题主要有如下两个方面。
第一是指针维护问题。试想，你写的一个程序执行了一系列内存空间分配（通常是由malloc函数完成）操作，为了能够在以后适当的时候（通常是你不再需要那些内存时）可以将分配的内存空间释放（通常是由free函数完成），你必须小心谨慎的维护好这些指向分配的内存空间的指针。有经验的程序员大概都会有这样的感受，维护这些指针并非易事！特别是当程序比较复杂时，尤为如此。如果你一不小心（其实这很容易）丢掉了某些指针，那么操作系统将无法回收那些内存（这便是我们常说的内存泄漏问题），除非你的程序死了。
第二就是关于内存分配释放操作本身。如果你的程序会相当频繁的执行malloc和free函数，那么程序将会费去大量的CPU时间来执行它们。
为了解决以上两个问题，尽可能的提高内存利用率，HTK设计了一个内存管理子系统，利用自定义的堆结构（Heap）来进行内存分配和释放。HTK内存分配和释放的主要思想是一次向操作系统要大一些的内存块，然后在将它分成小块供上层程序使用，不需要时只需释放那个大内存块。
HTK把堆结构分为三大类：
1. M-HEAPS：元素大小固定，new/free操作执行次序无限制，可全局重置(global reset)。
2. M-STACK：元素大小可变，最后分配的空间必须先释放，可全局重置。最常用
3. C-HEAPS：元素大小可变，new/free操作执行次序无限制，全局重置无效（直接使用malloc和free函数）。最不常用
二、数据结构
1. 堆数据结构定义
typedef enum{MHEAP,MSTAK,CHEAP} HEAPTYPE; // 堆类型定义
typedef unsigned char* ByteP; // 无符号字符（8位）指针
typedef void* Ptr;
typedef struct _Block *BlockP;
/* MHEAP和MSTAK块数据结构定义 */
typedef struct _Block{ /* MHEAP ,MSTACK */
size_t numFree; /* 空闲元素数目 ,空闲字节数 */
size_t firstFree; /* 第一个空闲元素索引 ,栈顶索引 */
size_t numElem; /* 块分配元素的个数 ,块分配的字节数 */
ByteP used; /* 指向元素分配表指针,1bit/元素 ,不使用 */
Ptr data; /* 指向数据区指针 ,指向数据区指针 */
BlockP next; /* 指向下一个块指针 ,指向下一个块指针 */
}Block;
/* 堆数据结构定义 */
typedef struct{ /* MHEAP ,MSTACK */
char* name; /* 堆的名称 ,堆的名称 */
HEAPTYPE type; /* 堆的类型 ,堆的类型 */
float growf; /* 增长因子 ,增长因子 */
size_t elemSize; /* 元素大小 ,总是1 */
size_t minElem; /**/没啥作用
size_t maxElem; /* 每个块最大允许分配的元素个数 ,每个块最大允许分配的字节数 */
size_t curElem; /* 当前块元素个数 ,当前块字节个数 */
size_t totUsed; /* 该堆所有块已使用的元素总个数 , 该堆所有块以使用的字节总个数 */
size_t totAlloc; /* 该堆所有块分配的元素总数 , 该堆所有块分配的字节总数 */
BlockP heap; /* 指向当前块的指针 ,指向当前块的指针 */也是最新的block，因为最新申请的block都要放在最前面
Boolean protectStk; /* 仅适用于MSTAK */用于实现后进先出原则，见tips
}MemHeap;
2. 堆数据结构框图
M-Heaps内存堆结构示意图
同一个M-Heaps内存堆中分配的元素大小都是一样的。堆结构中的块指针成员变量heap指向数据块链的头。
数据块链中的每个块分配的内存区大小由（字节）计算得到。
每个块中的BYTE型指针成员变量used指向记录元素使用状态的表数据结构，表中第i位记录数据区中第i个元素的使用状态：1表示使用中、0表示空闲。
每个块中的firstFree成员变量的值表示数据区中第一个空闲元素的标号。
每个块中的numFree成员变量的值记录所在块中空闲元素的个数。如果numFree为0表示块满，这时firstFree=numElem。
M-Stack内存堆结构示意图
三、算法
1. 接口描述
TIPS1：如果堆的类型是MHEAP，每次申请内存New只能给你elemSize大小的一块内存，即使你指定申请大小，也会被忽略，主要用于特定情况的内存申请（比如同样大小的数据结构），大部分情况下还是使用MSTACK类型的堆，这个堆的elemSize大小为1，可以申请指定大小的内存。
TIPS2：MSTACK类型，有一个后分配的空间必须先释放的原则：这个原则有两个实现方式：第一，通过设置x->protectStk标记为true。这样每次在MSTACK堆中申请内存（通过GetElem操作），都会在firstfree下移4bytes处记录最新申请内存的地址。这样在dispose某一块内存比如p时，会检查当前块中是否有p，如果有，p是否与firstfree下移4bytes处得值pp相等，如果相等，说明p确实是最新申请的内存， 如果不是，说明是之前申请的内存，根据stack原则，是不能被dispose的；第二，如果没有设置protectStk，那么只能靠用户自己维护这个原则，反正在dispose的时候，是严格按照后进先出原则的。A。当前块必然是最新分配内存的所在块。B。当前块内部也是按照最新分配的在最上面原则
TIPS3：使用方法：
1 CreateHeap创建并注册堆到headlist
2New分配内存，dispose释放内存
3 ResetHeap 清空堆
4 DeleteHeap删除并注销堆从headlist
1. 定义：Export–>void InitMem(void)
说明：初始化全局MSTAK堆变量gstack和全局CHEAP堆变量gcheap。该函数必须在调用任何其它堆操作函数前调用。
参数：无
返回值：无
2. 定义：Export–>void CreateHeap(MemHeap
*x , char *name , HeapType type , size_t elemSize , float growf , size_t
numElem , size_t maxElem)
说明：创建一个名称为name、类型为type的内存堆，elemSize指定内存堆中元素的大小，numElem指定块中元素默认个数。如果，内存堆的类型是MSTAK或CHEAP，则elemSize必须为1。此函数并没有创建任何真正的内存块block，New的时候，发现没有内存或内存不够的时候才创建block，创建block之后更新x->curElem.这个函数指定的numElem只是初始化x的curElem，和minElem，别的没啥用。
参数： x： 指向给定的内存堆
[In,Out]
name： 堆的名称
[In]
type： 堆类型
[In]
elemSize： 对于MHEAP表示堆的每个块中元素的大小，对于
MSTAK和CHEAP，elemSize必须设为1
[In]
growf：
numElem： 堆的每个块默认分配的元素个数
[In]
maxElem： 堆的每个块最大允许分配的元素个数
[In]
返回值：无
5. 定义：Export–>Ptr New(MemHeap *x , size_t size)
说明：从内存堆x中分配一大小为size的新元素并返回其指针。如果x类型为MHEAP则忽略参数size(见tips，如果size大小不等于elemsize,会报错)。如果分配失败，程序将会异常退出，所以返回值永远不会为NULL。
参数： x： 指向给定的内存堆
[In,Out]
size： 指定分配的元素大小
[In]
返回值：返回指向新分配的元素的指针
7. 定义：void* GetElem(BlockP p , size_t elemSize , HeapType type)
说明：如果type为MHEAP则从块p中返回一空闲元素指针，并将其在使用状态表中的对应项置1。如果type为MSTAK则从块p中返回一大小为elemSize字节数的区域指针，并对块p中firstFree和numFree变量进行相应的修改。
参数： p： 指向给定的块
[In]
elemSize： 元素大小
[In]
type： 所属堆的类型
[In]
返回值：如果成功，则返回大小为elemSize字节数的数据区，否则返回
NULL。
8. 定义：BlockP AllocBlock(size_t size , size_t num , HeapType
type)
说明：分配一个数据区大小为size*num字节数的块，在进行必要的初始化后，返回该块的指针。
参数： size： 元素大小
[In]
num： 元素个数
[In]
type： 所属堆的类型
[In]
返回值：如果分配成功，则返回块指针，否则程序异常退出。
9. 定义：size_t Mround(size_t size)
说明：返回大小>=size并且整除FWORD（8）的值。
参数：
size 输入大小
[In]
返回值：返回计算的大小
10. 定义：Export–>Ptr CNew(MemHeap *x , size_t size)
说明：从内存堆x中分配一大小为size的新元素清0后返回其指针。如果x类型为MHEAP则忽略参数size。如果分配失败，程序将会异常退出，所以返回值永远不会为NULL。
参数： x： 指向给定的内存堆
[In,Out]
size： 指定分配的元素大小
[In]
返回值： 返回指向新分配的元素的指针
3. 定义：Export–>void ResetHeap(MemHeap *x)
说明：释放内存堆x中所有元素，对CHEAP内存堆无效。对MHEAP类型，释放所有block，回归x的初始状态，对MSTACK类型，释放除第一个block之外的所有block，第一个block的数据区内存也不释放，但都标记为未使用（即firstfree=0）
参数： x： 指向给定的内存堆
[In,Out]
返回值：无
4. 定义：Export–>void DeleteHeap(MemHeap *x)
说明：释放内存堆x中所有元素，对CHEAP内存堆无效。并删除内存堆x。（MSTACK类型的最后一个block也会释放），x从headlist里面去除（UnRecordHeap）
参数： x： 指向给定的内存堆
[In,Out]
返回值：无
11. 定义：Export–>void Dispose(MemHeap* x , void *p)
说明：从内存堆x中释放元素p；只是标记为未使用，不释放。但是如果标记完之后发现此block的内存都未被使用，则释放该block；
参数：
x 指向给定的内存堆
[In,Out]
p 元素指针
[In]
返回值： 无
6. 定义：void BlockRecorder(BlockP *p , int n)
说明：对于MHEAP堆，从块p向后搜索有n个以上（包括n个）元素的块，并将其移至块链表头。对于MSTAK堆，从块p向后搜索有n个以上（包括n个）字节数的块，并将其移至块链表头。
参数：
p 指向给定的块
[In,Out]
n 对于MHEAP，表示元素个数；对于MSTAK，表示字节
数。
[In]
返回值：无
2. 接口实现
1. 内存堆创建算法CreateHeap
void CreateHeap(MemHeap *x, char *name, HeapType type, size_t elemSize,
float growf, size_t numElem, size_t
maxElem)
{
// 一致性检查
if (growf < 0.0) //growf必须大于等于0
HError(5170, “CreateHeap: -ve grow factor in heap
%s”,name);
if (numElem>maxElem) //默认的元素个数不能大于最大允许的元素个数
HError(5170,”CreateHeap: init num elem > max elem in heap
%s”,name);
if (elemSize <= 0) //元素大小必须大于0
HError(5170,”CreateHeap: elem size = %u in heap
%s”,elemSize,name);
if (type == MSTAK && elemSize !=1) //MSTAK的elemSize必须为1
HError(5170,”CreateHeap: elem size = %u in MSTAK heap
%s”,elemSize,name);
x->name = (char *)malloc(strlen(name)+1); //为内存堆名称分配内存
strcpy(x->name, name);
x->type
=
type;
x->growf
=
growf;
x->elemSize = elemSize;
x->maxElem = maxElem;
x->curElem = x->minElem = numElem;
x->totUsed = x->totAlloc = 0;
x->heap = NULL;
x->protectStk =
(x==&gstack)? FALSE : protectStaks;
RecordHeap(x); //记录内存堆x
if (trace&T_TOP)
{
switch (type)
{
case MHEAP:
c=\’M\’; break;
case MSTAK: c=\’S\’;
break;
case CHEAP: c=\’C\’;
break;
}
printf(“HMem: Create Heap %s[%c] %u %.1f %u %u\n”, name,
c,
elemSize, growf, numElem, maxElem);
}
}
1. 内存堆的Trace
为了跟踪内存堆的使用情况，HTK使用一个叫MemHeapRec的数据结构来记录创建的内存堆。MemHeapRec的数据结构如下所示：
typedef struct
_MemHeapRec {
MemHeap *heap;
// 指向内存堆的指针
struct _MemHeapRec *next;
// 指向下一个MemHeapRec
} MemHeapRec;
static MemHeapRec
*heapList = NULL; //全局变量, MemHeapRec链表
MemHeapRec主要通过RecordHeap和UnRecordHeap两个函数来完成内存堆的记录和擦除操作。算法描述如下：
static void RecordHeap(MemHeap *x) //将内存堆x加入到heapList链表中
{
MemHeapRec *p;
if (( p = (MemHeapRec *)malloc(sizeof(MemHeapRec))) == NULL)
HError(5105,”RecordHeap: Cannot allocate memory
for MemHeapRec”);
p->heap = x;
//将p插入到heapList链表头前
p->next = heapList;
heapList = p;
}
static void UnRecordHeap(MemHeap *x) //从heapList中擦除内存堆x记录
{
MemHeapRec *p, *q;
p = heapList;
q = NULL;
// 从heapList链头向后寻找内存堆x
while (p != NULL &&
p->heap != x)
{
q = p;
p = p->next;
}
if (p == NULL)
HError(5171,”UnRecordHeap: heap %s not found”,x->name); //没有找到
//将p从heapList中摘除
if (p == heapList)
heapList = p->next;
else
q->next = p->next;
free(p); //释放p
}
2. 内存堆重置算法ResetHeap
将p从heapList中摘除
void ResetHeap(MemHeap *x)
{
BlockP cur,next;
switch(x->type)
{
case MHEAP:
if
(trace&T_TOP)
printf(“HMem: ResetHeap %s[M]\n”, x->name);
cur = x->heap; //cur指向块链表头
//删除所有的块
while (cur != NULL)
{
next =
cur->next;
free(cur->data); //释放cur块数据区内存
free(cur->used); //释放cur块元素使用状态表内存
free(cur); //释放cur块
cur =
next; //cur指向下一个块
}
x->curElem =
x->minElem;
x->totAlloc = 0;
x->heap =
NULL;
break;
case MSTAK:
if (trace&T_TOP)
printf(“HMem: ResetHeap %s[S]\n”,
x->name);
cur=x->heap; //cur指向块链表头
if (cur != NULL)
{
// 删掉除第一个块以外的所有块
while (cur->next != NULL)
{
next = cur->next;
x->totAlloc = x->totAlloc-cur->numElem;
free(cur->data);
free(cur);
cur = next;
}
x->heap = cur;
}
x->curElem = x->minElem;
if (cur != NULL)
{
cur->numFree = cur->numElem;
cur->firstFree = 0;
}
break;
case CHEAP:
HError(5172,”ResetHeap: cannot reset C heap”);
}
x->totUsed = 0;
}
3. 内存堆删除算法DeleteHeap
void DeleteHeap(MemHeap *x) //删除指定的内存堆x
{
if (x->type == CHEAP)
HError(5172,”DeleteHeap: cant delete C Heap %s”,x->name);
ResetHeap(x); //释放所有的数据块
if (x->heap != NULL)
{
free(x->heap->data);
free(x->heap);
}
if (trace&T_TOP)
printf(“HMem:
DeleteHeap %s\n”, x->name);
UnRecordHeap(x); //擦除内存堆x的Trace
free(x->name); //释放分配的名称内存
}
4. 从内存堆分配空间的算法New、CNew
static BlockP AllocBlock(size_t size, size_t num, HeapType type) //分配块
{
BlockP p;
ByteP c;
int i;
if (trace&T_TOP)
printf(“HMem:
AllocBlock of %u bytes\n”, num*size);
if ((p = (BlockP)
malloc(sizeof(Block))) == NULL) //分配块空间
HError(5105,”AllocBlock: Cannot allocate Block”);
if ((p->data = (void
*)malloc(size*num)) == NULL) //分配块的数据区空间
HError(5105,”AllocBlock: Cannot allocate block data of %u
bytes”,size*num);
switch (type)
{
case MHEAP:
if ((p->used =
(ByteP)malloc((num+7)/8)) == NULL)//分配使用状态表空间
HError(5105,
“AllocBlock: Cannot allocate block used array”);
//使用状态表中所有项赋0
for (i=0,c=p->used; i
< (num+7)/8; i++,c++)
*c = 0;
break;
case MSTAK:
p->used = NULL;
break;
default:
HError(5190,”AllocBlock: bad type %d”,type);
}
p->numElem = p->numFree
= num;
p->firstFree = 0;
p->next = NULL;
return p;
}
AllocBlock分配的MHEAP块示意图
//BlockReorder: 从块p向后寻找第一个有>=n个空闲元素的块，并将其移至块链表头
static void BlockReorder(BlockP *p, int n)
{
BlockP head, cur, prev;
if (p == NULL)
return;
head = cur = *p;
prev = NULL;
while (cur != NULL)
{
if (cur->numFree
>= n)
{
//找到，那么就将其移至块链表头
if (prev !=
NULL)
{
prev->next = cur->next;
cur->next = head;
}
*p = cur;
return;
}
prev = cur;
cur = cur->next;
}
}
//GetElem: 从块中分配新元素
static void *GetElem(BlockP p, size_t elemSize, HeapType type)
{
int i,index;
if (p == NULL)
return NULL;
switch (type)
{
case MHEAP:
if (p->numFree == 0)
return NULL;
index = p->firstFree; //第一个空闲元素索引号
p->used[p->firstFree/8] |= 1<<(p->firstFree&7); //使用状态表中对应位置1
p->numFree–;
//在使用状态表中寻找下一个空闲块
if (p->numFree >
0)
{
for
(i=p->firstFree+1; i<p->numElem;i++)
{
if
((p->used[i/8] & (1 <<(i&7))) == 0)
{
p->firstFree = i;
break;
}
}
}
else
p->firstFree = p->numElem; //firstFree=最大元素索引号+1
return (void
*)((ByteP)p->data+index*elemSize); //返回分配的数据区指针
case MSTAK:
//从栈顶取elemSize字节数的区域
if (p->numFree <
elemSize)
return NULL;
index = p->firstFree;
p->firstFree +=
elemSize;
p->numFree =
p->numFree – elemSize;
return (void
*)((ByteP)p->data + index); //返回分配的数据区指针
default:
HError(5190,”GetElem: bad type %d”, type);
}
return NULL;
}
#define FWORD 8
// size of a full word = 基本的分配量
size_t MRound(size_t size)
{
return ((size % FWORD) == 0) ?
size : (size/FWORD + 1) * FWORD;
}
void *New(MemHeap *x, size_t size) //返回从内存堆x分配大小为size的新元素指针
{
void *q;
BlockP newp;
size_t num,bytes,*ip,chdr;
Boolean noSpace;
Ptr *pp;
//一致性检查
if (x->elemSize <= 0)//堆X尚未被初始化（没有createheap，否则elemSize不会小于0）
HError(5174, “New:
heap %s not initialised”,
(x->name==NULL)
? “Unnamed” : x->name);
switch(x->type)
{
case MHEAP:
//如果能从现有的块中找到空闲元素，则返回其指针。否则，就分配一个数据
//区大小由curElem，growf以及maxElem决定的新块。
if (size != 0 &&
size != x->elemSize) //检查size的合法性，MHEAP类型，每次只能申请elemSize大小的内存
HError(5173,”New: MHEAP req for %u size elem from heap %s size %u”,
size , x->name ,
x->elemSize);
noSpace = x->totUsed
== x->totAlloc; //totUsed和totAlloc分别记录堆X的所有block的总计已使用内存和已分配内存字节大小，如果totUsed==totAlloc说明x的所有block的内存都已被使用，没有空闲元素
if (noSpace || (q =
GetElem(x->heap , x->elemSize , x->type)) == NULL)
{
if (!noSpace)//如果x还有空间
BlockReorder(&(x->heap), 1); //从块x->heap 向后寻找第一个有>=n个空闲元素的块，并将其移至块链表头，n永远都得是1
if (noSpace
|| (q = GetElem(x->heap, x->elemSize, x->type)) == NULL)//如果x没有空间，则分配一个新块。现在x->heap应该有空间了？？
{
num =
(size_t) ((double)x->curElem * (x->growf + 1.0) + 0.5);
if
(num > x->maxElem)
num = x->maxElem;
newp = AllocBlock(x->elemSize, num, x->type); //分配新块
x->totAlloc += num;
x->curElem = num;
//将新分配的块置于块链表头
newp->next = x->heap;
x->heap = newp;
if
((q=GetElem(x->heap, x->elemSize, x->type)) == NULL)
HError(5191,”New: null elem but just made block in heap %s”,
x->name);
}
}
x->totUsed++;
if (trace&T_MHP)
printf(“HMem: %s[M] %u bytes at %p allocated\n”, x->name, size,
q);
return q;
case CHEAP:
chdr =
MRound(sizeof(size_t)); //多分配chdr个字节
q = malloc(size+chdr); //直接使用malloc分配
if (q==NULL)
HError(5105,”New: memory exhausted”);
x->totUsed += size;
x->totAlloc +=
size+chdr;
//在起始部分中记录分配的空间大小
ip = (size_t *)q;
*ip = size;
if
(trace&T_CHP)
printf(“HMem: %s[C] %u+%u bytes at %p allocated\n”, x->name, chdr,
size, q);
return
(Ptr)((ByteP)q+chdr);
case MSTAK:
if (x->protectStk)
size +=
sizeof(Ptr);
size = MRound(size); //size必须是8的整数倍
if ((q = GetElem(x->heap,
size, x->type)) == NULL)
{
//空间不够，加入一个新块。这里为什么不像MHEAP那样查找后面的block有没有空间？
bytes =
(size_t)((double)x->curElem * (x->growf + 1.0) + 0.5);
if (bytes
> x->maxElem)
bytes
= x->maxElem;
x->curElem = bytes;
if (bytes < size)
bytes
= size;
bytes =
MRound(bytes);
newp =
AllocBlock(1, bytes, x->type);
x->totAlloc
+= bytes;
//新分配的块置于块链表头
newp->next = x->heap;
x->heap =
newp;
if
((q=GetElem(x->heap, size, x->type)) == NULL)
HError(5191,”New: null elem but just made block in heap %s”,
x->name);
}
x->totUsed += size;
if (trace&T_STK)
printf(“HMem: %s[S] %u bytes at %p allocated\n”, x->name, size,
q);
if (x->protectStk)
{
pp = (Ptr
*)((long)q + size – sizeof(Ptr));
*pp = q;
}
return q;
}
return NULL;
}
C-Heaps内存分配示意图
//返回从内存堆x分配大小为size的新元素指针，新分配的空间已清0
Ptr CNew (MemHeap *x, size_t size)
{
void *ptr;
ptr = New (x, size);
if (x->type == MHEAP
&& size ==0)
size = x->elemSize;
memset (ptr, 0, size);
return ptr;
}
5. 从内存堆删除空间的算法Dispose
void Dispose(MemHeap *x, void *p) //从内存堆x中释放p
{
BlockP head , cur , prev;
Boolean found = FALSE;
ByteP bp;
size_t size,chdr;
size_t num,index, *ip;
Ptr *pp;
if (x->totUsed == 0)
HError(5105 ,
“Dispose: heap %s is empty” , x->name);
switch(x->type)
{
case MHEAP:
/*
从块链表头向后搜索块,如果data=<p<=data+(numElem-1)*elemSize，表
示p指向的空间是由这个块的分配的，则计算索引号，使用状态表中相
应位置0。
*/
head = x->heap;
cur=head;
prev=NULL;
size = x->elemSize;
while (cur != NULL
&& !found)
{
num =
cur->numElem;
found =
cur->data <= p &&
(((void*)((ByteP)cur->data+(num-1)*size)) >= p);
if (!found)
{
prev=cur;
cur=cur->next;
}
}
if (cur == NULL)
HError(5175,”Dispose: Item to free in MHEAP %s not
found”,x->name);
index =
((size_t)p-(size_t)cur->data)/size; //计算索引号
cur->used[index/8]
&= ~(1 <<(index&7));
if (index <
cur->firstFree)
cur->firstFree
= index;
cur->numFree++;
x->totUsed–;
if (cur->numFree ==
cur->numElem)
{
//释放整个块
if (cur !=
head)
prev->next = cur->next;
else
head =
cur->next;
x->heap =
head;
x->totAlloc -= cur->numElem;
free(cur->data);
free(cur->used);
free(cur);
}
if (trace&T_MHP)
printf(“HMem: %s[M] %u bytes at %p de-allocated\n”, x->name, size,
p);
return;
case MSTAK:
// 与MHEAP同样的方法先确定p所在的块
cur = x->heap;
if (x->protectStk)
{
if
(cur->firstFree > 0 ) // s-top in current block
pp =
(Ptr *)((size_t)cur->data+cur->firstFree-sizeof(Ptr));
else
{
// s-top in
previous block
if
(cur->next == NULL)
HError(5175,”Dispose: empty stack”);
pp =
(Ptr *)((size_t)cur->next->data+cur->next->firstFree-sizeof(Ptr));
}
if (*pp !=
p)
HError(-5175,”Dispose: violation of stack discipline in %s [%p !=
%p]”,
x->name,
*pp, p);
}// if
(x->protectStk)
while (cur != NULL
&& !found)
{
// check current block
num =
cur->numElem;
found =
cur->data <= p &&
(((void*)((ByteP)cur->data+num)) > p);
if (!found)
{
// p不在当前块中，所以删除该块
x->heap = cur->next;
x->totAlloc -= cur->numElem;
x->totUsed -= cur->firstFree;
free(cur->data);
free(cur);
cur =
x->heap;
if (trace&T_STK)
printf(“HMem: deleleting block in %s[S]\n”, x->name);
}
}
if (!found)
HError(5175,”Dispose: Item to free in MSTAK %s not found”,
x->name);
size =
((ByteP)cur->data + cur->firstFree) – (ByteP)p; //分配数据区的实际大小
if (size < 0)
HError( 5175
, “Dispose: item to free in MSTAK %s is above stack top”,
x->name);
cur->firstFree -=
size;
cur->numFree += size;
x->totUsed -=
size;
if (trace&T_STK)
printf(“HMem: %s[S] %u bytes at %p de-allocated\n”, x->name, size,
p);
return;
case CHEAP:
chdr =
MRound(sizeof(size_t));
bp = (ByteP)p-chdr;
ip = (size_t *)bp;
x->totAlloc -= (*ip +
chdr);
x->totUsed -=
*ip;
free(bp);
if (trace&T_CHP)
printf(“HMem: %s[C] %u+%u bytes at %p de-allocated\n”,
x->name, chdr, *ip, bp);
return;
}
}