/*
数据结构C语言版 边界标识法
算法8.1(首次拟合法) P200
编译环境：Dev-C++ 4.9.9.2
日期：2011年2月9日
*/
#include <stdio.h>
#include <malloc.h>
// 边界标识法可利用空间表的结点结构
// head和foot分别是可利用空间表中结点的第一个字和最后一个字(WORD)
// 字类型
typedef struct WORD
{
union
{
struct WORD *llink; // 头部域，指向前驱结点
struct WORD *uplink; // 底部域，指向本结点头部
}a;
int tag; // 块标志，0：空闲，1：占用，头部和尾部均有
int size; // 头部域，块大小
struct WORD *rlink; // 头部域，指向后继结点
}WORD, head, foot, *Space; // *Space：可利用空间指针类型
// 带参数的宏定义，指向p所指结点的底部(最后一个字)
#define FootLoc(p) (p) + (p)->size-1
#define MAX 1000 // 可利用空间的大小(以WORD的字节数为单位)
#define e 10 // 块的最小尺寸-1(以WORD的字节数为单位)
/*
算法8.1(首次拟合法) P200
pav指向可利用空间的头部，若有不小于n的空闲块,则分配相应的存储块,
并返回其首地址;否则返回NULL.若分配后可利用空间表不空，则pav指向
表中刚分配过的结点的后继结点（另一可利用结点）。
*/
Space AllocBoundTag(Space *pav, int n)
{
Space p, f;
// 查找不小于n的空闲块, p->rlink == *p说明到了头指针了.
for(p = *pav; p && p->size < n && p->rlink != *pav; p = p->rlink)
;
if( !p || p->size < n) // 找不到，返回空指针
{
printf("分配失败！\n");
return NULL;
}
else // p指向找到的空闲块,进行切割
{
// 指向底部tail
f = FootLoc(p);
// pav指向*p结点的后继结点,p将要被分配出去了
*pav = p->rlink;
if(p->size - n <= e) // 整块分配，不保留<=e的剩余量
{
if(*pav == p) // 可利用空间表变为空表
*pav = NULL;
else // 在表中删除分配的结点
{
// pav指向p的前面一个结点
(*pav)->a.llink = p->a.llink;
// p的前面一个结点指向p的后面那个结点，其实这两步
// 就是将p从表中删除
p->a.llink->rlink = *pav;
}
// 修改分配结点的头部和底部标志
p->tag = f->tag = 1;
}
else // 分配该块的后n个字(高地址部分)
{
// 修改分配块的底部标志
f->tag = 1;
// 重置剩余块大小，这样将导致p的尾部发生变化，因为我们
// 是分配该块的后n个字(高地址部分)所以这样做的
p->size -= n;
// f指向新生成剩余块的底部
f = FootLoc(p);
// 设置剩余块底部标志为空闲
f->tag = 0;
// 尾部指向头部
f->a.uplink = p;
// 指向新分配块的头部
p = f + 1;
// 设置新分配块的头部
p->tag = 1;
//设置新分配块的头部
p->size = n;
}
// 返回分配块首地址
return p;
}
}
/*
边界标识法的回收算法
pav为可利用空间头指针，p为释放块头首地址
*/
void Reclaim(Space *pav,Space *p)
{
// (*p-1)为左邻块的底部，所以(*p-1)->a.uplink指向释放块的左邻块
// (空闲时)的头部地址也就是该块的首地址
Space s = (*p-1)->a.uplink;
// t指向释放块的右邻块(空闲时)的首地址
Space t = *p + (*p)->size;
// l指示释放块的左邻块是否空闲
int l = (*p-1)->tag;
// r指示释放块的右邻块是否空闲
int r = (*p+(*p)->size)->tag;
if(!*pav) // 可利用空间表为空
{
// 将释放块加入到pav所指的可利用空间表中
// 头部域的两个指针及pav均指向释放块
*pav = (*p)->a.llink = (*p)->rlink = *p;
// 修改头部域块标志为空闲
(*p)->tag = 0;
// 修改尾部域
(FootLoc(*p))->a.uplink = *p;
// 修改尾部域块标志为空闲
(FootLoc(*p))->tag = 0;
}
else // 可利用空间表不空
{
if(l == 1 && r == 1) // 左右邻区均为占用块
{
(*p)->tag = 0; // 修改头部域块标志为空闲
(FootLoc(*p))->a.uplink = *p; // 修改尾部域
(FootLoc(*p))->tag = 0;
// 将p所指结点(刚释放的结点)插在pav所指结点之前
(*pav)->a.llink->rlink = *p;
(*p)->a.llink = (*pav)->a.llink;
(*p)->rlink = *pav;
(*pav)->a.llink = *p;
// 修改pav,令刚释放的结点为下次分配时的最先查询的结点
*pav = *p;
}
else if(l == 0 && r == 1) // 左邻区为空闲块,右邻区为占用块
{
// 合并左邻块和释放块
// 左邻空闲块的头部地址，(*p-1)为左邻块的尾部
s=(*p-1)->a.uplink;
s->size += (*p)->size; // 设置新的空闲块大小
t = FootLoc(*p); // 设置新的空闲块底部
t->a.uplink = s;
t->tag = 0;
}
else if(l == 1 && r == 0) // 右邻区为空闲块,左邻区为占用块
{
// 合并右邻块和释放块
(*p)->tag = 0; // P为合并后的结点头部地址
(*p)->a.llink = t->a.llink; // p的前驱为原t的前驱
(*p)->a.llink->rlink = *p; // p的前驱的后继为p
(*p)->rlink = t->rlink; // p的后继为原t的后继
(*p)->rlink->a.llink = *p; // p的后继的前驱为p
(*p)->size += t->size; // 新的空闲块的大小
// 新结点底部(原t的底部)指针指向新结点的头部
(FootLoc(t))->a.uplink=*p;
// 可利用空间表的头指针指向t(t已不是空闲结点首地址了)
if(*pav == t)
// 修改pav,令刚释放的结点为下次分配时的最先查询的结点
*pav = *p;
}
else // 左右邻区均为空闲块
{
s->size+=(*p)->size+t->size; // 设置新结点的大小
t->a.llink->rlink=t->rlink; // 删去右邻空闲块结点
t->rlink->a.llink=t->a.llink;
// 新结点底部(原t的底部)指针指向其头部
(FootLoc(t))->a.uplink=s;
if(*pav == t) // 可利用空间表的头指针指向t(t已不是空闲结点首地址了)
*pav = s; // 修改pav,令刚释放的结点为下次分配时的最先查询的结点
}
}
*p = NULL; // 令刚释放的结点的指针为空
}
// 输出p所指的可利用空间表
void Print(Space p)
{
Space h, f;
printf("可利用空间表：\n");
if(p) // 可利用空间表不空
{
h = p; // h指向第一个结点的头部域(首地址)
f = FootLoc(h); // f指向第一个结点的底部域
do
{
printf("块的大小 = %d 块的首地址=%u ",
h->size, f->a.uplink); // 输出结点信息
// f(h的最后一个字即底部)的下一个字节即f+1就是邻块的首地址
printf("块标志=%d(0:空闲 1:占用) 邻块首地址=%u\n",
h->tag, f+1);
// 指向下一个结点的头部域(首地址)不知道等不等于f+1,下面我们来
// 检验下,使用printf打印地址
// printf("邻块首地址=%u\n",h); // 经过检验的确是这样 h等于f+1
h = h->rlink;
f = FootLoc(h); // f指向下一个结点的底部域
}while(h != p); // 没到循环链表的表尾
}
printf("\n");
}
// 输出p数组所指的已分配空间
void PrintUser(Space p[])
{
int i;
printf("已利用空间表：\n");
for(i = 0; i < MAX / e; i++)
if(p[i]) // 指针不为0(指向一个占用块)
{
printf("块%d的首地址=%u ",i,p[i]); // 输出结点信息
printf("块的大小=%d 块头标志=%d(0:空闲 1:占用)",
p[i]->size,p[i]->tag);
printf(" 块尾标志=%d\n", (FootLoc(p[i]))->tag);
}
printf("\n");
}
int main()
{
Space pav,// 空闲块指针
p;//中介用的指针
Space v[MAX / e] = {NULL}; // 占用块指针数组(初始化为空)
int n;
// 本次测试的内存块的大小以结构体WORD的字节数为单位来计的。
printf("结构体WORD实际占用的空间为%d个字节\n\n", sizeof(WORD));
// 申请大小为MAX*sizeof(WORD)个字节的空间，记住还多加了2个
// 分别是头尾结点。
p = (WORD*)malloc((MAX+2)*sizeof(WORD));
// 设置低址边界,以防查找左右邻块时出错,此时的p是整个块的开始
p->tag = 1;
// 初始化可利用的空间表
pav = p + 1; // 可利用空间表的表头
// 初始化可利用空间(一个整块),双重循环链表
pav->rlink = pav->a.llink = pav;
pav->tag = 0; //标志为0，空闲
pav->size = MAX;
p = FootLoc(pav); // p指向底部域
p->a.uplink = pav; //底部域p指向本结点头部pav
p->tag = 0; //标志为0，空闲
// 设置高址边界,以防查找左右邻块时出错,此时的p+1是整个块的尾部
(p+1)->tag = 1;
printf("初始化后:\n");
Print(pav);
//第一次分配
n = 300;
printf("分配%u个存储空间后:\n",n);
v[0] = AllocBoundTag(&pav,n); // 第一个占用块指针v[0]
Print(pav);
PrintUser(v);
n = 450;
printf("分配%u个存储空间后:\n",n);
v[1] = AllocBoundTag(&pav,n);
Print(pav);
PrintUser(v);
// 分配不成功的
n = 300;
printf("分配%u个存储空间:\n",n);
v[2] = AllocBoundTag(&pav,n);
Print(pav);
PrintUser(v);
// 分配整个块(250)
n = 242;
printf("分配%u个存储空间后(整块分配)，pav为:\n",n);
v[2] = AllocBoundTag(&pav,n);
Print(pav);
PrintUser(v);
printf("回收v[0](%d)后(当pav空时回收)，pav为:\n",v[0]->size);
Reclaim(&pav,&v[0]); // pav为空
Print(pav);
PrintUser(v);
printf("回收v[2](%d)后(左右邻区均为占用块),pav为:\n",v[2]->size);
Reclaim(&pav,&v[2]); // 左右邻区均为占用块
Print(pav);
PrintUser(v);
n = 270; // 查找空间足够大的块
printf("分配%u个存储空间后(查找空间足够大的块)，pav为:\n",n);
v[0] = AllocBoundTag(&pav,n);
Print(pav);
PrintUser(v);
n=30; // 在当前块上分配
printf("分配%u个存储空间后(在当前块上分配)，pav为:\n",n);
v[2] = AllocBoundTag(&pav,n);
Print(pav);
PrintUser(v);
printf("回收v[1](%d)后(右邻区为空闲块,左邻区为占用块)，pav为:\n",v[1]->size);
Reclaim(&pav,&v[1]); // 右邻区为空闲块,左邻区为占用块
Print(pav);
PrintUser(v);
printf("回收v[0](%d)后(左邻区为空闲块,右邻区为占用块)，pav为:\n",v[0]->size);
Reclaim(&pav,&v[0]); // 左邻区为空闲块,右邻区为占用块
Print(pav);
PrintUser(v);
printf("回收v[2](%d)后(左右邻区均为空闲块),pav为:\n",v[2]->size);
Reclaim(&pav,&v[2]); // 左右邻区均为空闲块
Print(pav);
PrintUser(v);
system("pause");
return 0;
}
/*
输出效果：
结构体WORD实际占用的空间为16个字节
初始化后:
可利用空间表：
块的大小 = 1000 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8876416
分配300个存储空间后:
可利用空间表：
块的大小 = 700 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8871616
已利用空间表：
块0的首地址=8871616 块的大小=300 块头标志=1(0:空闲 1:占用) 块尾标志=1
分配450个存储空间后:
可利用空间表：
块的大小 = 250 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8864416
已利用空间表：
块0的首地址=8871616 块的大小=300 块头标志=1(0:空闲 1:占用) 块尾标志=1
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
分配300个存储空间:
分配失败！
可利用空间表：
块的大小 = 250 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8864416
已利用空间表：
块0的首地址=8871616 块的大小=300 块头标志=1(0:空闲 1:占用) 块尾标志=1
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
分配242个存储空间后(整块分配)，pav为:
可利用空间表：
已利用空间表：
块0的首地址=8871616 块的大小=300 块头标志=1(0:空闲 1:占用) 块尾标志=1
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
块2的首地址=8860416 块的大小=250 块头标志=1(0:空闲 1:占用) 块尾标志=1
回收v[0](300)后(当pav空时回收)，pav为:
可利用空间表：
块的大小 = 300 块的首地址=8871616 块标志=0(0:空闲 1:占用) 邻块首地址=8876416
已利用空间表：
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
块2的首地址=8860416 块的大小=250 块头标志=1(0:空闲 1:占用) 块尾标志=1
回收v[2](250)后(左右邻区均为占用块),pav为:
可利用空间表：
块的大小 = 250 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8864416
块的大小 = 300 块的首地址=8871616 块标志=0(0:空闲 1:占用) 邻块首地址=8876416
已利用空间表：
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
分配270个存储空间后(查找空间足够大的块)，pav为:
可利用空间表：
块的大小 = 250 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8864416
块的大小 = 30 块的首地址=8871616 块标志=0(0:空闲 1:占用) 邻块首地址=8872096
已利用空间表：
块0的首地址=8872096 块的大小=270 块头标志=1(0:空闲 1:占用) 块尾标志=1
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
分配30个存储空间后(在当前块上分配)，pav为:
可利用空间表：
块的大小 = 30 块的首地址=8871616 块标志=0(0:空闲 1:占用) 邻块首地址=8872096
块的大小 = 220 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8863936
已利用空间表：
块0的首地址=8872096 块的大小=270 块头标志=1(0:空闲 1:占用) 块尾标志=1
块1的首地址=8864416 块的大小=450 块头标志=1(0:空闲 1:占用) 块尾标志=1
块2的首地址=8863936 块的大小=30 块头标志=1(0:空闲 1:占用) 块尾标志=1
回收v[1](450)后(右邻区为空闲块,左邻区为占用块)，pav为:
可利用空间表：
块的大小 = 480 块的首地址=8864416 块标志=0(0:空闲 1:占用) 邻块首地址=8872096
块的大小 = 220 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8863936
已利用空间表：
块0的首地址=8872096 块的大小=270 块头标志=1(0:空闲 1:占用) 块尾标志=1
块2的首地址=8863936 块的大小=30 块头标志=1(0:空闲 1:占用) 块尾标志=1
回收v[0](270)后(左邻区为空闲块,右邻区为占用块)，pav为:
可利用空间表：
块的大小 = 750 块的首地址=8864416 块标志=0(0:空闲 1:占用) 邻块首地址=8876416
块的大小 = 220 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8863936
已利用空间表：
块2的首地址=8863936 块的大小=30 块头标志=1(0:空闲 1:占用) 块尾标志=1
回收v[2](30)后(左右邻区均为空闲块),pav为:
可利用空间表：
块的大小 = 1000 块的首地址=8860416 块标志=0(0:空闲 1:占用) 邻块首地址=8876416
已利用空间表：
请按任意键继续. . .
*/