-
Notifications
You must be signed in to change notification settings - Fork 0
/
WorstFit.cpp
185 lines (167 loc) · 4.71 KB
/
WorstFit.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/*
This code is created by Mehul Patni in c++
Last Updated Date : 20/05/2019
This is Implementation of Worst Fit strategy used in memory management of computers.
*/
#include<iostream>
using namespace std;
struct node{ // Defining Structures.
int size;
int mem;
struct node *next;
};
struct node *head;
struct node *FreeList;
struct node *Allocated;
void SortedInsert(struct node** head, struct node* newNode);
void InsertSort(struct node** head);
void push(struct node **head, int a, int b){ // Inserting nodes into the Linked List.
struct node *newnode = new node;
newnode->mem = a;
newnode->size = b;
newnode->next = *head;
*head = newnode;
}
void deleteNode(struct node **head_ref, int key) // Deleting node which have size == 0 i.e., you are allocating all the size of free list into allocated list.
{
struct node* temp = *head_ref, *prev;
if (temp != NULL && temp->size == key)
{
*head_ref = temp->next; // Changed head
return;
}
while (temp != NULL && temp->size != key)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
}
void traversal(struct node *current) // For traversal of all nodes present in the Linked List.
{
struct node *ptr;
ptr = current;
cout<<"List is :-\n";
while(ptr != NULL){
cout<<ptr->mem<<" : "<<ptr->size<<" -> ";
ptr = ptr->next;
}
cout<<" NULL\n";
}
// In the WorstFit, the partition is allocated which has highest memory block size.
void worstfit(struct node **temp1, struct node **temp2, int a) // This is the First Fit Strategy which is implemented using Linked List.
{
struct node *ptr1 = *temp1;
struct node *ptr2 = *temp2;
struct node *ptr3 = *temp1;
int worstfit = -1;
while(ptr1 != NULL){
if(ptr1->size >= a){
if(worstfit == -1)
worstfit = ptr1->size;
else if(worstfit < ptr1->size)
worstfit = ptr1->size;
}
ptr1 = ptr1->next;
}
if(worstfit != -1){
while(ptr3 != NULL){
if(ptr3->size == worstfit)
{
if(ptr3->size == a)
{
push(&ptr2,ptr3->mem,a);
InsertSort(&ptr2);
deleteNode(temp1, ptr3->size);
}
else
{
push(&ptr2,ptr3->mem,a);
InsertSort(&ptr2);
ptr3->mem +=a;
ptr3->size -= a;
}
break;
}
ptr3 = ptr3->next;
}
cout<<"----------FREE LIST ------------";
traversal(*temp1);
cout<<"----------ALLOCATED LIST ------------";
traversal(ptr2);
}
else{
cout<<"Such huge Size cannot be accomodated\n";
}
}
void SortedInsert(struct node** head, struct node* newNode)
{
struct node dummy;
struct node* current = &dummy;
dummy.next = *head;
while (current->next != NULL && current->next->mem < newNode->mem)
current = current->next;
newNode->next = current->next;
current->next = newNode;
*head = dummy.next;
}
void InsertSort(struct node** head) // This is for sorting the Linked List in increasing order.
{
struct node* result = NULL; // build the answer here
struct node* current = *head; // iterate over the original list
struct node* next;
while (current != NULL)
{
// tricky - note the next pointer before we change it
next = current->next;
SortedInsert(&result, current);
current = next;
}
*head = result;
}
int main()
{
char ch = 'y';
int a,b;
cout<<"----------FREE LIST ------------\nCan contain 0-512 memory block.\n";
while(ch == 'y' || ch == 'Y'){ // Creating FreeList Linked List.
cout<<"Enter the Starting address and the size of the node in the Free list --> ";
cin>>a>>b;
push(&FreeList,a,b);
cout<<"Do you want to enter more nodes in the Free list?(y/n) ";
cin>>ch;
}
struct node *head = FreeList;
InsertSort(&head);
traversal(head);
int s;
cout<<"----------ALLOCATED LIST ------------\n";
struct node *ptr;
ptr = head;
if(head->mem != 0) // Remaining memeory block is assigned to Allocated list.
push(&Allocated,0,head->mem);
while(head->next != NULL){
s = head->next->mem - head->mem -head->size;
if(s>0)
{
push(&Allocated, head->mem +head->size, head->next->mem - head->mem - head->size);
}
head = head->next;
if(head->next == NULL && head->mem+head->size < 512)
push(&Allocated,head->mem+head->size,512-(head->mem+head->size));
}
struct node *head1 = Allocated;
InsertSort(&head1);
traversal(head1);
ch = 'y';
cout<<"\n";
while(ch == 'y' || ch == 'Y'){ // For allocating space from Freelist.
cout<<"Enter the size of the node you want to be allocated in the memory --> ";
cin>>a;
worstfit(&ptr, &head1, a);
cout<<"Do you want to enter more nodes??";
cin>>ch;
}
return 0;
}