内存的连续分配与回收算法 - c++编程基础

// 回收区尾部：tag
if (NULL == pav)
{
pav = p;
p->leftLink = p; // 回收区头部：leftLink
p->rightLink = p; // 回收区头部：rightLink
}
else
{
// 将p插到pav之前（双向链表的插入操作）
p->rightLink = pav; // 回收区头部：rightLink
p->leftLink = pav->leftLink; // 回收区头部：leftLink
pav->leftLink->rightLink = p; // pav的前驱头部：rightLink
pav->leftLink = p; // pav的头部：leftLink

pav = p; // 令刚释放的结点为下次分配时的最先查询的结点
}
}

// 2、前空闲，后作业
void Recycle_FA(Word *&p)
{
unsigned int n = p->size; // 释放块的大小
Word *s = (p - 1)->upLink; // 左邻空闲区的头部地址
s->size += n; // 设置新的空闲块大小
Word *f = p + n - 1; // 设置新的空闲块底部
f->upLink = s;
f->tag = FREE;
}

// 3、前作业，后空闲
void Recycle_AF(Word *&p)
{
Word *t = p + p->size; // t指向右邻空闲区的头部
FootLoc(t)->upLink = p; // 右邻空闲区头部：upLink
p->size += t->size; // 回收区头部：size
p->tag = FREE; // 回收区头部：tag
p->leftLink = t->leftLink; // 回收区头部：leftLink
t->leftLink->rightLink = p; // 原来右邻区的前驱头部：rightLink
p->rightLink = t->rightLink;// 回收区头部：rightLink
t->rightLink->leftLink = p; // 原来右邻区的后继头部：leftLink
}

// 4、前后相邻区都是空闲区
void Recycle_FF(Word *&p)
{
unsigned int n = p->size; // 回收区大小
Word *s = (p - 1)->upLink; // 指向左邻块，即新结点头部
Word *t = p + p->size; // 指向右邻块
s->size += n + t->size; // 设置新结点大小

// 删除右邻空闲块结点（双向链表的删除操作）
t->leftLink->rightLink = t->rightLink; // s不一定等于t->leftLink
t->rightLink->leftLink = t->leftLink;

FootLoc(t)->upLink = s; // 新结点尾部：upLink指向其头部
}

// 释放首地址为p的作业（头部中含该作业的大小信息）
void Recycle(Word *&pav, Word *p)
{
if (!(memory <= p && p < memory + MEMORY_SIZE))
{
cout << "释放区首地址越界！" << endl;
return;
}

Word *low = p - 1; // 与其低地址紧邻的内存区的底部地址
Word *high = p + p->size; // 与其高地址紧邻的内存区的头部地址
State lowTag = low->tag;
State highTag = high->tag;
if (low < memory) // 当p是内存的第一块时
{

lowTag = ALLOC;
}
if (high >= memory + MEMORY_SIZE) // 当p是内存的最后一块时
{
highTag = ALLOC;
}

// 前后相邻区都是作业
if (ALLOC == lowTag && ALLOC == highTag)
{
Recycle_AA(pav, p);
}
// 前空闲，后作业
else if (FREE == lowTag && ALLOC == highTag)
{
Recycle_FA(p);
}
// 前作业，后空闲
else if (ALLOC == lowTag && FREE == highTag)
{
Recycle_AF(p);
}
// 前后相邻区都是空闲区
else if (FREE == lowTag && FREE == highTag)
{
Recycle_FF(p);
}
}

// 输出内存中各区的信息
void PrintMInfo(map &jobAddrToName)
{
cout << "\n************************************" << endl;
cout << "起址\t大小\t状态\t（作业名）" << endl;
for (Word *p = memory; p < memory + MEMORY_SIZE; p += p->size)
{
cout << p - memory << "\t"
<< p->size << "\t"
<< p->tag << "\t"
<< (p->tag == ALLOC jobAddrToName[p] : "（空闲）")
<< endl;
}
cout << "************************************\n" << endl;
}

int Flag(const string &option)
{
if (option == "1") return 1;
if (option == "2") return 2;
if (option == "3") return 3;
return 0;
}

int main(int argc, char **argv)
{
freopen("cin.txt", "r", stdin);
map jobNameToAddr; // 根据作业名得到它的地址
map jobAddrToName; // 根据作业地址得到它的名称
Word *pav = NULL; // pav为查询指针
Initiate(pav);
string option;
do
{
PrintMInfo(jobAddrToName);
cout << "请选择：1、分配内存 2、回收内存 3、退出" << endl;
cin >> option;
switch (Flag(option))
{
case 1:
{ // 防止error C2374：初始化操作由“case”标签跳过
cout << "请输入作业名和作业大小：" << endl;
Job myJob;
cin >> myJob.name >> myJ

内存的连续分配与回收算法(二)