Data Structures Locality of Reference Link List (Using C++) Note ** Not an advan
ID: 3859363 • Letter: D
Question
Data Structures
Locality of Reference
Link List
(Using C++)
Note ** Not an advanced programmer so please make code understandable
Thanks! :)
A new idea has come to light in which an attempt is promoted to make a program run a little faster. Since memory is way away from the CPU it behooves use to keep the active variables closer to the CPU (in a buffer) and try to cut down on the number of trips all the way to memory to get data the CPU is needing. This project has been assigned to you. Should you accept and should you succeed you will then receive appropriate compensation (a grade).
The problem is to keep active variables closer to the CPU where the variables will be kept in a buffer. When the CPU needs the data from a variable, the first place to look is in the buffer. If found that variable’s value is returned and that variable becomes the most recently used variable. If the variable is not found, then the variable’s value is fetched form memory then is added to the buffer, again becoming the most recently used variable. Now the buffer is only so big and will hold only so many variables at a time, so when the buffer is full and you add a new variable to the buffer, then an old variable needs to fall off (out of) the buffer. The variable that falls out represents a less recently used variable it leaves the buffer.
Your effort (your program) is to manage the buffer. You are to write a program that will input a stream of accessed variables simulating the variables accessed in a running program. The buffer will be implemented as a link list. Any variable accessed must first be determined if the variable is in the buffer. If so move the variable to front of list to represent most recently used. The variables at the end of the list are the less recently used. Any variable not found in the list will be placed/added at the front of the list. At all times the buffer cannot exceed its limits.
You are to simulate different buffer sizes to see if the larger buffer size really saves much on the true memory access. So have your program test with buffer sizes of 4, 5, 6, 7, and 8, the max number of variables in the buffer . Run your program, reading through the data 5 times, one for each buffer size to test. Keep up with the number of times you have to access true memory (ie the number of times a variable is added to the buffer). Be sure not to exceed the buffer size with the number of variables in the list. Print out the buffer size and the number of memory accesses required to simulate this intermediate storage. On end of file for each buffer size tested, print out the current variables in the buffer at the time all variables have been read/input from the file.
The Data Structure we are implementing is called a ‘self-organizing list’ in which we have a list and on each access to a node in the list, the list is reorganized as new variables are encountered.
INPUT: Your input file for the variable stream is “LinkL Var Stream.txt”. (**Input Below**)
OUTPUT: Buffer size, number of memory accesses and the last list of variables remaining in the buffer.
Explanation / Answer
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct List{
char var[50];
struct List *next;
}List;
void memory(List *p,char *input,int buf_size,int *memory_access)
{
List *temp=malloc(sizeof(List));
List *temp1=malloc(sizeof(List));
List *prev=malloc(sizeof(List));
prev=NULL;
temp1=p;
int presence=0;
strcpy(temp->var,input);
if(temp1==NULL)
{
temp->next=NULL;
p=temp;
return;
}
else
{
int length=0;
while(temp1->next!=NULL && length<=buf_size)
{
prev=temp1;
if(strcmp(temp1->var,temp->var)==0)
{
temp->next=p;
p=temp;
presence=1;
return;
}
temp1=temp1->next;
length=length+1;
}
if(strcmp(temp1->var,temp->var)==0)
{
temp->next=p;
p=temp;
presence=1;
return;
}
else if(length<=buf_size)
{
temp->next=NULL;
temp1->next=temp;
return;
}
else if(presence==0)
{
prev->next=NULL;
temp->next=p;
p=temp;
*memory_access=*memory_access+1;
return;
}
return;
}
}
void print(List *head)
{
List *temp=malloc(sizeof(List));
while(temp!=NULL)
{
printf("%s ",temp->var);
temp=temp->next;
}
}
int main()
{
int buf_size=0;
printf("Enter Buffer Size:");
scanf("%d",&buf_size);
char line[1024];
char *token;
token=(char *)malloc(sizeof(char)*100);
int memory_access=0;
List *head=malloc(sizeof(head));
FILE* file = fopen("Stream.txt", "r");
memset(line, '', sizeof(line));
while (fgets(line, sizeof(line), file))
{
line[strlen(line)-1]=0;
token=strtok(line," ");
while(token!=NULL)
{
memory(head,token,buf_size,&memory_access);
token=strtok(line," ");
}
memset(line, '', sizeof(line));
}
fclose(file);
printf("Buffer Size=%d, Memory Access=%d ", buf_size,memory_access);
printf("Buffer Elements:");
print(head);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.