I need help with this C code, please use comments.

We are to ONLY edit the two files given (lru_cache.h and lru_cache.c) to implement a least-recently used replacement policy with cache. All the other files stay the same. If you run the Makefile given, it will give an output implementing a cache with random replacement policy using the files 'random_cache.h' and 'random_cache.c' . Thank You!

You can either get all the code files from here or copy and paste them:https://drive.google.com/file/d/1ZRCxFktbCJezhjbFI2aH6mStsMFXH1vm/view?usp=sharing

These are the instructions given:

It contains code that models storage with a cache, as in our last homework. You should be familiar with most of the code from last weeks homework. If you type make rand in bash, a simulator will be created that uses a cache with a random replacement policy. The code that implements a cache with a random replacement policy is in random_cache.h and random_cache.c.

Your job is to edit files lru_cache.h and lru_cache.c such that they implement a least-recently-used replacement policy. Do not modify any other files!

I will test your code by running the simulator, and also by running unit tests. When I run the simulator that uses the random replacement policy, I get:

hits: 73548; misses: 26452

When I run the simulator using my cache implementation with a least-recently-used replacement policy, I get (and you should get):

hits: 78399; misses: 21601

Files to edit:

lru_cache.c:

#include  #include "lru_cache.h" // // Your implementations of cache_new, cache_lookup, cache_insert, // and cache_clear go in this file. You must use a least-recently-used // cache replacement policy. // // return a new cache object CACHE *cache_new(int size) { // your code here } // return data element i if it is cached; else return -1 float cache_lookup(CACHE *cache, int i) { // your code here } // record in the cache that the ith data element has value x // LRU replacement policy is used void cache_insert(CACHE *cache, int i, float x) { // your code here } // clear the ith element of the cache void cache_clear(CACHE *cache, int i) { // your code here } 

lru_cache.h:

typedef struct cache { // // your code here // } CACHE; CACHE *cache_new(int size); float cache_lookup(CACHE *cache, int i); void cache_insert(CACHE *cache, int i, float x); void cache_clear(CACHE *cache, int i); 

The following files are for reference and should NOT be edited.

Makefile:

# the include file in cache_sim.c must be set to select cache implementation rand: cache_sim_rand ./cache_sim_rand cache_sim_rand: cache_sim.c random_cache.c sed 's/\#include.*cache\.h/\#include \"random_cache\.h/' cache_sim.c > temp.c gcc -o cache_sim_rand temp.c random_cache.c lru: cache_sim_lru ./cache_sim_lru cache_sim_lru: cache_sim.c lru_cache.c sed 's/\#include.*cache\.h/\#include \"lru_cache\.h/' cache_sim.c > temp.c gcc -o cache_sim_lru temp.c lru_cache.c hw8-solutions.tar: rm -f hw8-solutions.tar tar cf hw8-solutions.tar solutions chmod 600 hw8-solutions.tar clean: rm -f cache_sim_lru cache_sim_rand temp.c *~ 

random_cache.c:

#include  #include "random_cache.h" // // A simple cache for positive float values, with a random replacement policy // CACHE *cache_new(int size) { CACHE *cache = malloc(sizeof(CACHE)); cache->size = size; cache->addr = malloc(size * sizeof(int)); cache->data = malloc(size * sizeof(float)); // initialize cache int i; for (i = 0; i < cache->size; i++) { cache->addr[i] = -1; cache->data[i] = 0.0; } return cache; } // return data element i if it is cached; else return -1 float cache_lookup(CACHE *cache, int i) { // is data element i in cache? int j; for (j = 0; j < cache->size; j++) { if (cache->addr[j] == i) { // yes, cache hit return cache->data[j]; } } // cache miss return -1.0; } // record in the cache that the ith data element has value x // random replacement policy is used void cache_insert(CACHE *cache, int i, float x) { int j = rand() % cache->size; cache->addr[j] = i; cache->data[j] = x; } // clear the ith element of the cache void cache_clear(CACHE *cache, int i) { int j; for (j = 0; j < cache->size; j++) { if (cache->addr[j] == i) { cache->addr[j] = -1; break; } } } 

random_cache.h:

typedef struct cache { int size; // number of cache elements int *addr; // index of element float *data; // value of element } CACHE; CACHE *cache_new(int size); float cache_lookup(CACHE *cache, int i); void cache_insert(CACHE *cache, int i, float x); void cache_clear(CACHE *cache, int i); 

cache_sim.c:

#include  #include  #include "cache.h" // // A simple data store with cache // #define DATA_SIZE 1000 #define CACHE_SIZE 10 // // Data is stored in array data[] // float data[DATA_SIZE]; int nhits = 0; int nmisses = 0; CACHE *cache; // initialize the data array void init() { int i; // initialize data for (i = 0; i < DATA_SIZE; i++) { data[i] = ((float)i)/2.0; } // create cache cache = cache_new(CACHE_SIZE); } // get the ith data value float get(int i) { if (i < 0 || i >= DATA_SIZE) { fprintf(stderr, "get: no data element %d ", i); exit(EXIT_FAILURE); } float x = cache_lookup(cache, i); if (x >= 0) { // cache hit nhits++; return x; } else { // cache miss nmisses++; x = data[i]; // insert x into the cache cache_insert(cache, i, x); return data[i]; } } // set the ith data value to x void set(int i, float x) { if (i < 0 || i >= DATA_SIZE) { fprintf(stderr, "set: no data element %d ", i); exit(EXIT_FAILURE); } // clear cache entry cache_clear(cache, i); data[i] = x; } // simulate a lot of data accesses int main(int argc, char *argv[]) { // simulation parameters int num_accesses = 100000; int dist_size = 10; int move_size1[] = {-3,-2,-1,0,0,0,0,1,2,3}; int move_size2[] = {-5,-4,-3,-2,-1,1,2,3,4,5}; init(); int i,j,delta; j = 0; for (i = 0; i < num_accesses; i++) { // randomly get a new data element j to access, based // on a change from the last element that was accessed delta = move_size1[rand() % dist_size]; j += delta; if (j < 0) { j = 0; } else if (j >= DATA_SIZE) { j = DATA_SIZE - 1; } get(j); } printf("hits: %d; misses: %d ", nhits, nmisses); exit(0); }