#include <stdio.h>
#include <getopt.h>
#include <limits.h>
#include <stdlib.h>
#include "cachelab.h"

typedef struct {
  int valid;
  int last_use_time;
  long t;
} cache_line;

void cache(cache_line *set, int E, unsigned long t, int time_stamp, int *hits, int *misses, int *evictions) {
  for (int i = 0; i < E; i++) {
    if (set[i].valid && set[i].t == t) {
      set[i].last_use_time = time_stamp;
      (*hits)++;
      return;
    }
  }
  
  (*misses)++;
  int least_use_time = INT_MAX, least_used_id;
  for (int i = 0; i < E; i++) {
    if (!set[i].valid) {
      set[i].valid = 1;
      set[i].last_use_time = time_stamp;
      set[i].t = t;
      return;
    }
    if (set[i].last_use_time < least_use_time) {
      least_use_time = set[i].last_use_time;
      least_used_id = i;
    }
  }

  (*evictions)++;
  set[least_used_id].last_use_time = time_stamp;
  set[least_used_id].t = t;
}

int main(int argc, char *argv[]) {
  int s, E, b;
  char *trace;
  char op;
  while ((op = getopt(argc, argv, "s:E:b:t:")) != -1) {
    switch (op) {
    case 's':
      s = atoi(optarg);
      break;
    case 'E':
      E = atoi(optarg);
      break;
    case 'b':
      b = atoi(optarg);
      break;
    case 't':
      trace = optarg;
    }
  }
  int S = 1 << s;

  FILE *infile = fopen(trace, "r");
  char instr[1];
  unsigned long addr;
  cache_line **sets = (cache_line**) malloc(sizeof(cache_line*) * S);
  for (int i = 0; i < S; i++) {
    sets[i] = (cache_line*) malloc(sizeof(cache_line) * E);
    for (int j = 0; j < E; j++) {
      sets[i][j].valid = 0;
    }
  }
  int time_stamp = 0;
  int hits = 0, misses = 0, evictions = 0;
  while (fscanf(infile, "%s %lx,%*d", instr, &addr) != -1) {
    if (instr[0] == 'I') {
      continue;
    }
    cache(sets[(addr >> b) & (S - 1)], E, addr >> (s + b), time_stamp, &hits, &misses, &evictions);
    if (instr[0] == 'M') {
      hits++;
    }
    time_stamp++;
  }
  printSummary(hits, misses, evictions);
  return 0;
}