// cache.c

#include "CacheIterator.h"
#include "bool.h"
#include "cacheEntry.h"
#include "cache.h"
#include <limits.h>               // for LONG_MAX


// Create a cache that will hole up to maxSize worth of data, 
// that will take up 1<<hashTableBits worth of memory
Cache::Cache(long long maxSize, int hashTableBits) {
  Cache::hashTableBits = hashTableBits;
  cacheArray = new CacheEntry * [1 << hashTableBits];
  for (int i = 0; i < (1 << hashTableBits); i++) {
    // initialize cacheArray pointers to NULL
    cacheArray[i] = NULL;
  } 
  Cache::maxSize = maxSize;
  currentSize = 0; 
  highWater = (long long) (HIGH_WATER_RATIO*maxSize);
}

// Destructor
Cache::~Cache() {
  CacheEntry * next;
  CacheEntry * prev;

  for (int i = 0; i < (1 << hashTableBits); i++) {
    // delete all cache entries
    next = cacheArray[i];

    while (next != NULL) {
      prev = next;
      next = next->getNext();
      delete prev;
    }
  } 

  // delete cacheArray itself
  delete[] cacheArray;
}

// Process Request req in the cache and return the result as a 
// RequestType
SimulationResult Cache::processRequest(SquidRequest req) {
  long hash = hashBig(req.url);

  CacheEntry * cacheEntry = findEntry(hash);
  
  // If req.url is in cache...
  if (cacheEntry != NULL) {
    if (req.proxyResult == SquidRequest::hit) {
      // hit
      cacheEntry->setLastRequest(req.endTime);
      return simHit;
    }
    else if (req.proxyResult == SquidRequest::refreshMiss) {
      // refreshMiss: in cache, but stale
      cacheEntry->setLastRequest(req.endTime);
      int ret = considerCaching(hash, cacheEntry, req);
      if (ret < 0) return simError;
      if (ret > 0) return simUnknown;
      // cacheEntry->setLastRefresh(req.endTime);
      // cacheEntry->setSize(req.size); // size could change on refresh
      return simMiss; // refreshMiss is a miss.
    }
    else if (req.proxyResult == SquidRequest::refreshHit) {
      // refreshHit: in cache, not stale
      cacheEntry->setLastRequest(req.endTime);
      int ret = considerCaching(hash, cacheEntry, req);
      if (ret < 0) return simError;
      if (ret > 0) return simUnknown;
      return simMiss;
    }
    else if (req.proxyResult == SquidRequest::imsHit) {
      cacheEntry->setLastRequest(req.endTime);
      if (req.httpResult != SquidRequest::notModified &&
	  req.httpResult != SquidRequest::ok)
	return simUnknown;
      return simHit;
    }
    else if (req.proxyResult == SquidRequest::imsMiss) {
      cacheEntry->setLastRequest(req.endTime);
      int ret = considerCaching(hash, cacheEntry, req);
      if (ret < 0) return simError;
      if (ret > 0) return simUnknown;
      return simMiss;
    }
    else if (req.proxyResult == SquidRequest::miss) {
      // This happens when the real proxy has expired the entry, but
      // it's still in my cache.  I'll keep it in my cache, but call
      // it a simMiss.  Can also happen if original request had a 
      // no-cache header line.
      cacheEntry->setLastRequest(req.endTime);
      int ret = considerCaching(hash, cacheEntry, req);
      if (ret < 0) return simError;
      if (ret > 0) return simUnknown;
      return simMiss;
    }
    else if (req.proxyResult == SquidRequest::clientRefresh) {
      cacheEntry->setLastRequest(req.endTime);
      int ret = considerCaching(hash, cacheEntry, req);
      if (ret < 0) return simError;
      if (ret > 0) return simUnknown;
      return simMiss;
    }
    else if (req.proxyResult == SquidRequest::refFailHit) {
      // Because we had to go to the server, it's a miss.
      cacheEntry->setLastRequest(req.endTime);
      return simMiss;
    }
    else {
      // special cases
      printf("My cache got a hit, proxy got something unexpected.\n");
      return simUnknown;
    }
  }
  else {
    // miss
    int ret = considerCaching(hash, NULL, req);
    // printf("cache miss - ret = %d\n", ret);
    if (ret < 0) return simError;
    if (ret > 0) return simUnknown;
    // printf("cache miss returned simMiss\n");
    return simMiss;
  }
}


// Returns 0 if it decided to cache or not cache the object,
// -1 if the request made no sense - it is an HTTP error.
// 1 if the function could not decide to cache or not.
int Cache::considerCaching(unsigned long hash, CacheEntry* cacheEntry, SquidRequest& req)
{
  //  printf("considerCaching - httpResult = %d\n", req.httpResult);

  if (req.httpResult == SquidRequest::ok || 
      req.httpResult == SquidRequest::notModified ||
      req.httpResult == SquidRequest::movedPermenently)
    {
      if (cacheEntry == NULL)
	{
	  addEntry(req.endTime, req.endTime, hash, req.size);
	}
      else
	{
	  cacheEntry->setLastRefresh(req.endTime);
	  currentSize += req.size - cacheEntry->getSize();
	  cacheEntry->setSize(req.size);
	}
      return 0;
    }
  else if (req.httpResult == SquidRequest::noContent ||
	   req.httpResult == SquidRequest::notFound ||
	   req.httpResult == SquidRequest::internalServerError ||
	   req.httpResult == SquidRequest::badRequest)
    {
      if (cacheEntry != NULL)
	deleteEntry(hash);
      return 0;
    }
  else if (req.httpResult == SquidRequest::unauthorized ||
	   req.httpResult == SquidRequest::movedTemporarily)
    {
      return 0;
    }
  else if (req.httpResult == 0)
    {
      // printf("Error: bad httpResult = 0\n");
      return -1;
    }
  else
    {
      // printf("Unknown: Couldn't decide to cache.\n");
      return 1;
    }
}


SimulationResult Cache::processRequest(DecRequest req)
{
  if (req.httpResult == DecRequest::ok)
    {
      long hash = req.urlHash;

      CacheEntry * cacheEntry = findEntry(hash);
      
      // If req.url is in cache...
      if(cacheEntry!=NULL) {
	unsigned long age = req.startTime - cacheEntry->getLastRefresh();
	unsigned long lmAge = cacheEntry->getLastRefresh() - cacheEntry->getLastModified();
	double lmFactor = lmAge == 0?5000/*infinity*/:(double)age / lmAge;
	
	if (lmFactor < 0.20)
	  {
	    return simHit;
	  }
	else
	  {
	    if (cacheEntry->getLastModified() >= req.lastModified)
	      {
		// We assume here the the server and proxy clocks are synced.
		cacheEntry->setLastRefresh(req.startTime);
		return simHit;
	      }
	    else
	      {
		cacheEntry->setLastModified(req.lastModified);
		cacheEntry->setLastRefresh(req.startTime);
		return simMiss;
	      }
	  }
      }
      else {
	// miss
	addEntry(req.startTime, req.startTime, hash, req.size, req.lastModified);
	return simMiss;
      }
    }

  return simUnknown;
}


// return NULL or entry
CacheEntry * Cache::findEntry(long hash) {
  int smallHash = hashSmall(hash);
  CacheEntry * result;
  if(cacheArray[smallHash]==NULL) {
    return NULL;
  }
  else {
    result = cacheArray[smallHash];
    while (result!=NULL && result->getHash()!=hash) {
      result = result->getNext();
    }
    return result;
  }
}

// adds the given entry to the cache
void Cache::addEntry(unsigned long lastRefresh, unsigned long lastRequest, unsigned long hash, int size, unsigned long lastModified) {
  CacheEntry * cacheEntry = new CacheEntry(lastRefresh, lastRequest, lastModified, hash, size);

  int smallHash = hashSmall(hash);
  
  cacheEntry->setNext(cacheArray[smallHash]);
  cacheArray[smallHash] = cacheEntry;

  currentSize += cacheEntry->getSize();
  while (currentSize >= highWater) { 
    clean();
  }
}

// deletes the entry specified by hash from the cache
void Cache::deleteEntry(unsigned long hash) {
  // printf("Cache::deleteEntry: deleting %lx\n", hash);

  CacheEntry * entry = NULL;
  CacheEntry * prev = NULL;
  int smallHash = hashSmall(hash);

  entry = cacheArray[smallHash];

  if(entry==NULL) {
    return; // hash is not in cache
  }

  while (entry!=NULL && entry->getHash()!=hash) {
    prev = entry;
    entry = entry->getNext();
  }

  if(entry == NULL) { // hash is not in cache
    return;
  }

  if(prev == NULL) {  // hash is only item in this cache line
    currentSize -= entry->getSize();
    cacheArray[smallHash] = NULL;
    delete entry;
    return;
  }

  // hash is somewhere in list of cache items
  currentSize -= entry->getSize();
  prev->setNext(entry->getNext());
  delete entry;
  return;
}


// cleans the cache
void Cache::clean() {
  // printf("Cache::clean: size before is %ld\n", currentSize);

  // A set of the 8 oldest cache items seen so far.  oldiesAge[i] and
  // oldiesHash[i] are the age and hash of the oldest item.
  // The array is not sorted, so we track the youngestOldie (who is
  // the one we're always comparing against) for efficiency.
  long oldiesAge[8];
  unsigned long oldiesHash[8];
  long youngestOldie = 0;

  // Initialize oldiesAge.
  int i;
  for (i = 0; i < 8; i++)
    {
      oldiesAge[i] = LONG_MAX;
    }
  
  // The number of entries we've seen since we last deleted entries.
  long entriesSeen = 0;

  // Iterate through the cache.
  CacheIterator cacheIter(this);

  while (cacheIter.moveNext())
    {
      CacheEntry* current = cacheIter.getCurrent();

      // If current is older than the youngest oldie, add replace
      // the youngest oldie with the current.
      if (oldiesAge[youngestOldie] > current->getLastRequest())
	{
	  oldiesAge[youngestOldie] = current->getLastRequest();
	  oldiesHash[youngestOldie] = current->getHash();

	  // Determine who the youngest oldie is again.
	  int i;
	  for (i = 0; i < 8; i++)
	    {
	      if (oldiesAge[youngestOldie] < oldiesAge[i])
		  youngestOldie = i;
	    }
	}

      entriesSeen++;

      // If we've seen 256 entries, delete the 8 oldest.
      if (entriesSeen == 256)
	{
	  int i;
	  for (i = 0; i < 8; i++)
	    {
	      deleteEntry(oldiesHash[i]);
	      oldiesAge[i] = LONG_MAX;
	    }

	  entriesSeen = 0;
	}
    }

  for (i = 0; i < 8; i++)
    {
      if (oldiesAge[i] != LONG_MAX) 
	deleteEntry(oldiesHash[i]);
      oldiesAge[i] = LONG_MAX;
    }

  // printf("Cache::clean: size after is %ld\n", currentSize);
}


// calculates a 64 bit hash from a url
// For each character, xors that character into the hash, and rotates
// the hash left one bit.
unsigned long Cache::hashBig(char * urlString) {
  // printf("hashBig: %s\n", urlString);
  long ret = 0;
  char *p = urlString;
  while (*p != 0)
    {
      ret = ret ^ *p;
      // I use ^ instead of | in case >> does sign extension (I can't remember)
      ret = (ret << 31) ^ (ret >> 1);  
      p++;
    }

  //  printf("Hash of %lx for %s\n", ret, urlString);
  return ret;
}


// calculates a 32 bit hash with hashTableBits sig. digits from a long
// Chops hash into hashTableBits-sized chunks and xors them all.
unsigned int Cache::hashSmall(unsigned long hash) {
  // printf("hashSmall: %lx\n", hash);
  //  printf("hashSmall: converted %lx ", hash);

  int ret = 0;

  while (hash > 0)
    {
      int newPart = hash & ((1L << hashTableBits)-1);
      //      printf("xoring %x onto %x.\n", newPart, ret);
      ret ^= newPart;
      hash >>= hashTableBits;
    }

  //  printf("to %x.\n", ret);

  return ret;
}


long long Cache::getCurrentSize()
{
  return currentSize;
}
