WILL

#include <stdio.h>
#include <string.h>

using namespace std;

struct row { int valid; int tag; int timeStamp; };
struct row *firstRow = NULL;
struct row cache[5000];
int maxCacheIndex;
int testing_sequence[] = { 0, 4, 8, 12, 16, 20, 24,
                          28, 32, 36, 40, 44, 48, 52,
                          56, 60, 64, 68, 72, 76, 80,
                          0, 4, 8, 12, 16, 71, 3, 41,
                          81, 39, 38, 71, 15, 39, 11,
                          51, 57, 41 };
int cacheNum = 0;

int testing_size = sizeof(testing_sequence)/sizeof(int);

int evictCacheLine(int k, int index) {
    int firstTime = cache[k*index].timeStamp;
    int indexTrack = k*index;
    int rowIdx = 0;
    for ( rowIdx = k*index; rowIdx < k*index + k; rowIdx++ ) {
        if ( cache[rowIdx].timeStamp < firstTime ) {
            firstTime = cache[rowIdx].timeStamp;
            indexTrack = rowIdx;
        }
    }
}

int isHitOrMissForDirectMapped( int tag, int index );
int isHitOrMissForSetAssoc( int k, int tag, int index );

int isHitOrMissForDirectMapped( int tag, int index ) {
    int isHit = 0;
    // For direct-mapped, index is the cache line number.
    if ( cache[index].valid && cache[index].tag == tag ) {
      isHit = true;
    }
    else {
      isHit = false;
    cache[index].valid = 1;
    cache[index].tag = tag;
    }

    return isHit;
}

int isHitOrMissForSetAssoc( int k, int tag, int index ) {
    int isHit = 0;  // Initialize isHit to default value:  false
    int rowIdx = 0;
    // For set associative, index is the set number.
    for ( rowIdx = k*index; rowIdx < k*index + k; rowIdx++ ) {
      if ( cache[rowIdx].valid && cache[rowIdx].tag == tag ) {
        isHit = true;
        break;
      }
    }
    // Now, isHit has value true if and only if we found a hit.
    if (isHit) {
        return 1; // return true
    }
    // Else search for cache line with valid field == 0 (false)
    for ( rowIdx = k*index; rowIdx < k*index + k; rowIdx++ ) {
      if ( cache[rowIdx].valid == 0 ) {
          cache[rowIdx].valid = 1;
          cache[rowIdx].timeStamp = cacheNum;
          cache[rowIdx].tag = tag;
          cacheNum++;
          break;
      }
    }
    int temp;
    // If we didn't find a cache line with valid field false, then evict cache line
    if (rowIdx >= k*index + k) { // if failed to find invalid cache line
        temp = evictCacheLine( k, index );
        cache[temp].timeStamp = cacheNum;
        cacheNum++;
        cache[temp].valid = 1;
        cache[temp].tag = tag;
    }

    return isHit;
}

int directMappedCache( int s, int l) {
    int x = 0;
    int tag, index, answer, offset;
    for (x = 0; x < testing_size; x++) {
        int address = testing_sequence[x];
        tag = address/s;
        index = address/l;
        offset = address % l;
        // We declared isHitOrMissForDirectMapped above.  But we define it below.
        answer = isHitOrMissForDirectMapped( tag, index );
        if (answer)
        printf("%d: HIT (Tag/Set#/Offset: %d/%d/%d)\n", address, tag, index, offset);
        else
        printf("%d: MISS (Tag/Set#/Offset: %d/%d/%d)\n", address, tag, index, offset);
    }
    return 0;  // The fnc main returns 0 for success.  Anything else is error number.
}

int setAssociateCache( int s, int l, int n ) {
    int x;
    int k = s/n;
    int numberOfSets = s/l/n;
    int tag, index, offset, answer;
    for (x = 0; x < testing_size; x++) {
        int address = testing_sequence[x];
        tag = address/k;
        index = (address/l) % numberOfSets;
        offset = address % l;
        // We declared isHitOrMissForDirectMapped above.  But we define it below.
      answer = isHitOrMissForSetAssoc( k, tag, index );
      if (answer) {
        printf("%d: HIT (Tag/Set#/Offset: %d/%d/%d)\n", address, tag, index, offset);
      }
      else {
        printf("%d: MISS (Tag/Set#/Offset: %d/%d/%d)\n", address, tag, index, offset);
      }
    }

    return 0;  // The fnc main returns 0 for success.  Anything else is error number.
}

int main() {
    printf( "Test 1\n");
    directMappedCache( 128, 8 );

    memset( cache, 0, 5000 );
    printf( "Test 2\n" );
    setAssociateCache( 64, 8, 2 );

    memset( cache, 0, 5000 );
    printf( "Test 3\n" );
    directMappedCache( 128, 16 );

    memset( cache, 0, 5000 );
    printf( "Test 4\n" );
    setAssociateCache( 64, 8, 8 );
}