/* Problem 2--Cache Simulation
   There was nothing hard about this problem.  All you had to do was
   emulate the cache, just as the problem described.  Of course, if you
   are unfamiliar with the "least recently used" strategy, this problem
   may have been a bit confusing. */
#include <stdio.h>
#include <stdlib.h>

typedef struct CS {

 int bsz, tsz, bct, l[100], sz, t;
} CS;

typedef struct CT {

 int sz, mmt;
 CS C[3];
} CT;

int main (int argc, char **argv);
int Read (FILE *in, CT *C);
int Access (CT *C, int a);

int main (int argc, char **argv) {

  FILE *in, *out;
  int cs, r, t, ct, i, a;
  CT C;

 in = fopen ("prob2.in","r");
 out = fopen ("prob2.out","w");
 cs = 0;
 for (;;) { /* Read in a cache definition */
 if (Read (in,&C)) break;
  t = 0;
  fscanf (in,"%d",&ct); /* Number of accesses */
  i = 0;
  for (;;) {
  if (i==ct) break;
   fscanf (in,"%d",&a);
   t += Access (&C,a); /* Process each access */
   i++;
  }
  fprintf (out,"Case %d: total time = %d nanoseconds\n",++cs,t);
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* Read reads cache definition C from in.  It returns true, if there
   is no more cache definition in the file, false otherwise. */
int Read (FILE *in, CT *C) {

  int done, i;

 fscanf (in,"%d",&C->sz);
 if (C->sz==0) {
  done = 1;
 } else {
  done = 0;
  i = 0;
  for (;;) {
  if (i==C->sz) break;
   fscanf (in,"%d %d %d",&C->C[i].bsz,&C->C[i].tsz,&C->C[i].t);
   C->C[i].bct = C->C[i].tsz/C->C[i].bsz;
   C->C[i].sz = 0; /* Nothing has been put in the cache yet. */
   i++;
  }
  fscanf (in,"%d",&C->mmt); /* Time to access from main memory */
 }
 return done;
}

/* Access emulates the cache, pulling the reference from the earliest
   cache it can.  It returns the time it takes to perform the
   operation. */
int Access (CT *C, int a) {

  int t, i, j, found;

 t = i = found = 0;
 for (;;) { /* go through the cache levels one at a time */
 if (i==C->sz || found) break;
  j = 0;
  for (;;) {
  if (j==C->C[i].sz || found) break;
   if (a >= C->C[i].l[j] && a < C->C[i].l[j] + C->C[i].bsz) {
    found = 1; /* found the memory location in cache i. */
   } else {
   }
   j++;
  }
  if (found) { /* remove the reference from the cache */
   C->C[i].sz--;
   j--;
   for (;;) {
   if (j==C->C[i].sz) break;
    C->C[i].l[j] = C->C[i].l[j+1];
    j++;
   }
  } else {
  }
  i++;
 }
 if (!found) { /* had to access main memory */
  t = C->mmt;
 } else {
 }
 for (;;) { /* go back through all the levels of the cache and enter */
  i--; /* this memory into the most recently used location */
  t += C->C[i].t;
  if (C->C[i].sz < C->C[i].bct) { /* Cache is not yet full */
   C->C[i].l[C->C[i].sz] = a/C->C[i].bsz*C->C[i].bsz;
   C->C[i].sz++;
  } else { /* Cache is full so I have to bump the least recently used */
   j = 0;
   for (;;) {
   if (j==C->C[i].sz-1) break;
    C->C[i].l[j] = C->C[i].l[j+1];
    j++;
   }
   C->C[i].l[j] = a/C->C[i].bsz*C->C[i].bsz;
  }
 if (i==0) break;
 }
 return t;
}