FILE ALLOCATION

NAME:T.KRISHNA ANANTHI
IMPLEMENTATION OF FILE ALLOCATION
TECHNIQUES



#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct block
{
char name[20];
int status,size,id;
struct block * next;
struct block * file;
};
struct directory
{
char name[20];
int id,size;
struct directory * next;
};
struct indices
{
char name[20];
int ind[100],size;
struct indices * next;
};
void display(struct block * head)
{
struct block * q;
printf("\n\t\tMEMORY\n-------------------------------------\nBlock No.\tFile Name/Free\tSize\n-------------------------------------\n");
for(q=head->next;q!=NULL;q=q->next)
printf("%d\t\t%s\t\t%d\n",q->id,q->name,q->size);
printf("-------------------------------------\n");
}
void displaydirectory(struct directory * dir,struct block * head)
{
struct directory *d;
struct block *q;
printf("\nDIRECTORY ENTRIES\n");
for(d=dir->next;d!=NULL;d=d->next)
{
printf("\tName: %s\n\tSize: %d\n\tBlocks: %d",d->name,d->size,d->id);
for(q=head->next;q!=NULL;q=q->next)
if(q->id==d->id)
break;
for(q=q->file;q!=NULL;q=q->file)
printf("--->%d",q->id);
printf("\n");
}
}
void displayindex(struct indices * ind,struct block * head)
{
int i;
struct indices *in;
printf("Index:\n");
for(in=ind->next;in!=NULL;in=in->next)
{
printf("\tName: %s\n\tSize: %d\n\tBlocks: ",in->name,in->size);
for(i=0;in->ind[i]!=-1;i++)
printf("%d--->",in->ind[i]);
printf("\b\b\b\b \n");
}
}
void contiguous(struct block * head,struct directory * dir,char file[],int siz,int n,int blk)
{
int index,i,reqblk,tn,flag,temp;
struct block * q;
struct directory * d,*dt;
d=(struct directory *)malloc(sizeof(struct directory));
for(dt=dir;dt->next!=NULL;dt=dt->next); //moving to last of directory list
reqblk=siz/blk;
if(siz%blk!=0)
reqblk++;
tn=reqblk;
for(flag=0,i=0;i<100;i++)
{
index=rand()%n;
printf("random no: %d\n",index);
for(q=head->next;q!=NULL;q=q->next) //finding first free location;
if(q->id==index)
if(q->status==0)
{
index=q->id;
flag=1;
break;
}
if(flag==1)
{
temp=q->size;
for(q=q->next;q!=NULL&&temp<=siz;q=q->next)//finding whether req contiguous mem is available from index
{
if(q->status!=0 )
break;
else temp+=q->size;
}
if(temp>=siz)
{
for(q=head->next;q->id!=index;q=q->next);
d->id=q->id; //Making entry in directory structure
d->next=dt->next;
dt->next=d;
d->size=siz;
strcpy(d->name,file);
for(i=0;i<reqblk;i++,q=q->next) //allocating contiguous memory
{
strcpy(q->name,file);
q->status=1;
if(i!=reqblk-1)
q->file=q->next;
else q->file=NULL;
}
goto end;
}
flag=0;
}
}
if(flag!=1)
printf("No enough contiguous memory available !**!\n");
end: display(head);
displaydirectory(dir,head);
}
void linkedlist(struct block * head,struct directory * dir,char file[],int siz,int n,int blk)
{
int index,i,flag=0,temp=0;
struct block * q,*t;
struct directory *d,*dt;
d=(struct directory *)malloc(sizeof(struct directory));
for(dt=dir;dt->next!=NULL;dt=dt->next); //moving to last of directory list
for(q=head->next;q!=NULL;q=q->next)
if(q->status==0)
temp+=q->size; //finding the total free space at this moment
if(temp>=siz)flag=1;
if(flag==0){printf("Memory low\n");return;}
for(i=0;i<100&&flag==1;i++)
{
temp=0;
index=rand()%n;//printf("random no: %d\n",index);
for(q=head->next;q!=NULL;q=q->next) //finding first free location;
if(q->id==index)
if(q->status==0)
{
t=q;q->status=1; //allocating first block
strcpy(q->name,file);
temp=q->size;
index=q->id;
d->id=q->id; //Making entry in directory structure
d->next=dt->next;
dt->next=d;
d->size=siz;
strcpy(d->name,file);
break;
}
if(flag==1)
{
printf("Initial:%d\n",temp);
while(temp<siz)
{
index=rand()%n;printf("random no: %d---",index);printf("%d\n",temp);
for(q=head->next;q!=NULL;q=q->next)
if(q->id==index)
if(q->status==0)
{
strcpy(q->name,file);
q->status=1;
t->file=q;
t=q;
temp+=q->size;
}
}
goto end;
}
}
end: t->file=NULL;
display(head);
displaydirectory(dir,head);
}
void indexed(struct block * head,struct indices * ind,char file[],int siz,int n,int blk)
{
int index,i,flag,temp,j=0;
struct block * q;
struct indices * in,*in1;
in=(struct indices * )malloc(sizeof(struct indices));
for(in1=ind;in1->next!=NULL;in1=in1->next);
for(temp=0,q=head->next;q!=NULL;q=q->next)
if(q->status==0)
temp+=q->size;
if(temp>=siz)
flag=1;
if(flag==0){printf("Memory low\n");return;}
for(i=0;i<100&&flag==1;i++)
{
temp=0;
index=rand()%n;printf("random no: %d\n",index);
for(q=head->next;q!=NULL;q=q->next) //finding first free location;
if(q->id==index)
if(q->status==0)
{
q->status=1; //allocating first block
strcpy(q->name,file);
temp=q->size;
index=q->id;
in1->next=in;
in->size=siz; //making entry in index
in->next=NULL;
in->ind[j++]=q->id;
strcpy(in->name,file);
break;
}
if(flag==1)
{
printf("Initial:%d\n",temp);
while(temp<siz)
{
index=rand()%n;printf("random no: %d---",index);printf("%d\n",temp);
for(q=head->next;q!=NULL;q=q->next)
if(q->id==index)
if(q->status==0)
{
strcpy(q->name,file);
q->status=1;
in->ind[j++]=q->id;
temp+=q->size;
}
}
in->ind[j]=-1;
goto end;
}
}
end: display(head);
displayindex(ind,head);
}
int main()
{
struct block * head,*new,*t;
struct directory * d;
struct indices * ind;
int mem,n,blk,rem,i,ch,siz,c;
char fname[20];
printf("Size of memory: ");
scanf("%d",&mem);
printf("Size of a block: ");
scanf("%d",&blk);
n=mem/blk;
rem=mem-(blk*n);
while(1)
{
head=(struct block *)malloc(sizeof(struct block));
head->next=NULL;
d=(struct directory *)malloc(sizeof(struct directory));
d->next=NULL;
ind=(struct indices *)malloc(sizeof(struct indices));
ind->next=NULL;
printf("MENU:\n\t1.Contiguous\n\t2.Linked List\n\t3.Indexed\n\t4.Exit\nChoice: ");
scanf("%d",&ch);
if(ch==4)break;
for(i=0;i<n;i++)
{
for(t=head;t->next!=NULL;t=t->next);
new=(struct block *)malloc(sizeof(struct block));
strcpy(new->name,"FREE");
new->status=0;
new->id=i;
new->size=blk;
new->next=NULL;
t->next=new;
}
if(rem>0)
{
for(t=head;t->next!=NULL;t=t->next);
new=(struct block *)malloc(sizeof(struct block));
strcpy(new->name,"FREE");
new->status=0;
new->size=rem;
new->id=n++; //incrementing no. of blocks since rem>0
new->next=NULL;
t->next=new;
}display(head);
switch(ch)
{
case 1:
case 2:
case 3:
while(1)
{
printf("File Name: ");
scanf("%s",fname);
printf("Size: ");
scanf("%d",&siz);
switch(ch)
{
case 1:contiguous(head,d,fname,siz,n,blk);break;
case 2:linkedlist(head,d,fname,siz,n,blk);break;
case 3:indexed(head,ind,fname,siz,n,blk);break;
}
printf("Do u wish to continue(press 0 to exit):");
scanf("%d",&c);
if(c==0)break;
}break;
default:printf("Invalid selection!**!");
}
}
return 0;
}



SAMPLE INPUT AND OUTPUT:



[cs1041733@OSNPL-C31 ~]$ ./a
Size of memory: 100
Size of a block: 20
MENU:
1.Contiguous
2.Linked List
3.Indexed
4.Exit
Choice: 1



MEMORY
-------------------------------------
Block No.File Name/Free Size
-------------------------------------
0 FREE 20
1 FREE 20
2 FREE 20
3 FREE 20
4 FREE 20
-------------------------------------
File Name: new
Size: 22
random no: 3



MEMORY
-------------------------------------
Block No. File Name/Free Size
-------------------------------------
0 FREE 20
1 FREE 20
2 FREE 20
3 new 20
4 new 20
-------------------------------------



DIRECTORY ENTRIES
Name: new
Size: 22
Blocks: 3--->4
Do u wish to continue(press 0 to exit):1
File Name: new1
Size: 12
random no: 1



MEMORY
-------------------------------------
Block No. File Name/Free Size
-------------------------------------
0 FREE 20
1 new1 20
2 FREE 20
3 new 20
4 new 20
-------------------------------------



DIRECTORY ENTRIES
Name: new
Size: 22
Blocks: 3--->4
Name: new1
Size: 12
Blocks: 1
Do u wish to continue(press 0 to exit):0
MENU:
1.Contiguous
2.Linked List
3.Indexed
4.Exit
Choice: 2



MEMORY
-------------------------------------
Block No.File Name/Free Size
-------------------------------------
0 FREE 20
1 FREE 20
2 FREE 20
3 FREE 20
4 FREE 20
-------------------------------------
File Name: new3
Size: 40
random no: 2
Initial:20
random no: 0---20



MEMORY
-------------------------------------
Block No.File Name/Free Size
-------------------------------------
0 new3 20
1 FREE 20
2 new3 20
3 FREE 20
4 FREE 20
-------------------------------------



DIRECTORY ENTRIES
Name: new3
Size: 40
Blocks: 2--->0
Do u wish to continue(press 0 to exit):1
File Name: new4
Size: 22
random no: 3
Initial:20
random no: 0---20
random no: 1---20



MEMORY
-------------------------------------
Block No.File Name/Free Size
-------------------------------------
0 new3 20
1 new4 20
2 new3 20
3 new4 20
4 FREE 20
-------------------------------------



DIRECTORY ENTRIES
Name: new3
Size: 40
Blocks: 2--->0
Name: new4
Size: 22
Blocks: 3--->1
Do u wish to continue(press 0 to exit):0
MENU:
1.Contiguous
2.Linked List
3.Indexed
4.Exit
Choice: 3



MEMORY
-------------------------------------
Block No. File Name/Free Size
-------------------------------------
0 FREE 20
1 FREE 20
2 FREE 20
3 FREE 20
4 FREE 20
-------------------------------------
File Name: anu
Size: 33
random no: 2
Initial:20
random no: 4---20



MEMORY
-------------------------------------
Block No. File Name/Free Size
-------------------------------------
0 FREE 20
1 FREE 20
2 anu 20
3 FREE 20
4 anu 20
-------------------------------------
Index:
Name: anu
Size: 33
Blocks: 2--->4
Do u wish to continue(press 0 to exit):1
File Name: abi
Size: 22
random no: 1
Initial:20
random no: 2---20
random no: 2---20
random no: 0---20



MEMORY
-------------------------------------
Block No. File Name/Free Size
-------------------------------------
0 abi 20
1 abi 20
2 anu 20
3 FREE 20
4 anu 20
-------------------------------------
Index:
Name: anu
Size: 33
Blocks: 2--->4
Name: abi
Size: 22
Blocks: 1--->0
Do u wish to continue(press 0 to exit):1
File Name: achu
Size: 7
random no: 4
Initial:0
random no: 3---0



MEMORY
-------------------------------------
Block No.File Name/Free Size
-------------------------------------
0 abi 20
1 abi 20
2 anu 20
3 achu 20
4 anu 20
-------------------------------------
Index:
Name: anu
Size: 33
Blocks: 2--->4
Name: abi
Size: 22
Blocks: 1--->0
Do u wish to continue(press 0 to exit):0
MENU:
1.Contiguous
2.Linked List
3.Indexed
4.Exit
Choice:4