// ICS 331 Assignment 4 Solution
// by David N. Chin
//
// N-way set-associative cache with either FIFO or LRU cache eviction policy,
// write-back and block size one

import java.util.*;

abstract public class Cache {
  // the maximum number of entries in the cache
  protected int size;
  // the associativity level of the cache
  protected int associativity;
  // the number of entries in each set of the cache
  protected  int slots;
  // the caches
  protected int caches[][];
  protected boolean valid[][];
  protected boolean dirty[][];
  // hit ratio statistics;
  protected int hits = 0, misses = 0;
  // print out every hit and miss
  boolean verbose = false;

  public Cache( int cacheSize, int cacheAssociativity )
  {
    size = cacheSize;
    associativity = cacheAssociativity;
    slots = size/associativity;
    caches = new int[slots][associativity];
    valid = new boolean[slots][associativity];
    dirty = new boolean[slots][associativity];
  }

  // Given an address and whether this is a memory write or read, look for 
  // the address in the cache.
  // If found, then return the subcache index where the data is stored.
  // Else if not found, add the address to the cache and return -1.
  // Also increment the number of hits or misses as appropriate.
  public int find( int address, boolean write ) {
    int tag = address / slots;
    int slotNum = address % slots;
    if( verbose ) System.out.println("address="+Integer.toHexString(address)+
				     ", tag="+tag+", slotNum="+slotNum);
    // check each entry in the cache slot
    for(int subcache=0; subcache < associativity; subcache++) {
      if( valid[slotNum][subcache] && // valid cache entries only
	  caches[slotNum][subcache] == tag ) {
	hits++;
	if( verbose ) System.out.println("hit on address "+Integer.toHexString(address));
	if( write ) dirty[slotNum][subcache] = true;
	return subcache;
      }
    }
    // not found in the cache
    if( ! write ) {
      misses++;
      if( verbose ) System.out.println("miss on address "+Integer.toHexString(address));
    }
    put( tag, slotNum, write );
    return -1;
  }

  // enter an address tag into the slotNum slot of the cache
  protected abstract void put( int tag, int slotNum, boolean write );

  // actually store the value into the cache at the given slotnum and subcache
  protected void store( int slotnum, int subcache, int value, boolean write ) {
    if( dirty[slotnum][subcache] ) {
      misses++;
      if( verbose ) System.out.println("miss (eviction) on address "+Integer.toHexString(caches[slotnum][subcache]*slots+slotnum));
    }
    caches[slotnum][subcache] = value;
    valid[slotnum][subcache] = true;
    dirty[slotnum][subcache] = write;
  }
  
  // print the cache statistics: hits, misses, and hit ratio
  public void printStats() {
    float ratio = (float)hits / (hits + misses);
    System.out.println( "hits: "+hits+", misses: "+misses+", hit ratio: "+ratio );
  }
} // class Cache