leetcode

// 146. LRU Cache
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#define DEBUG_MODE 0
#define REALLY_DEBUG 0

/*
 * design a data structure that follows the constraints of a least recently used
 * cache (LRU). implete the 'LRUCache' class. the functions 'get' and 'put' must
 * each run in O(1) average time complexity
 */

typedef struct QNode {
  struct QNode *prev, *next;
  unsigned bucket;
  int key;
  int data;
} QNode;

typedef struct Queue {
  unsigned count;
  unsigned capacity;
  QNode *front, *rear;
} Queue;

typedef struct Hash {
  int capacity;
  QNode **array; // array of pointers, or pointer to a range of pointers.
} Hash;

typedef struct LRUCache {
  unsigned int capacity;
  Queue *queue;
  Hash *hash;

} LRUCache;

struct QNode *newQNode(unsigned bucket) {
  struct QNode *temp = malloc(sizeof(struct QNode));
  temp->bucket = bucket;
  temp->prev = temp->next = NULL;
  return temp;
}

struct Queue *createQueue(int capacity) {
  struct Queue *queue = malloc(sizeof(struct Queue));
  queue->count = 0;
  queue->capacity = capacity;
  queue->front = queue->rear = NULL;
  return queue;
}

struct Hash *createHash(int capacity) {
  struct Hash *hash = malloc(sizeof(struct Hash));
  hash->capacity = capacity;
  hash->array = malloc(sizeof(struct QNode) * hash->capacity);
  for (int i = 0; i < hash->capacity; i++) {
    hash->array[i] = NULL;
  }
  return hash;
}

unsigned int hashfunc(unsigned capacity, int key);
void Enqueue(struct LRUCache *cache, struct Queue *queue, struct Hash *hash,
             int value, int key);
int searchCache(struct LRUCache *cache, int key);

void deQueue(Queue *queue) { // we could have return QNode but how would affect
                             // memory mgmt?

  if (DEBUG_MODE) {
    QNode *n = queue->front;
    int c = 0;
    QNode *p = n->prev;
    while (n != NULL) {
      if (REALLY_DEBUG)
        printf("QueueNode %d data = %d  n->prev:%d, n->next:%d\n", c, n->data,
               n->prev != NULL, n->next != NULL);
      c++;
      n = n->next;
    }
    if (REALLY_DEBUG)
      printf("next queue node is NULL\n");
    if (p == NULL)
      if (REALLY_DEBUG)
        printf("Front's prev points to null\n");
  }
  if (queue->rear == NULL)
    return;
  if (queue->front == queue->rear) {
    queue->front = NULL;
    queue->rear = NULL;
    queue->count--;
    return;
  }
  // QNode* temp = queue->rear;
  // LL two or more

  queue->rear = queue->rear->prev; // could be front if size = 2. That's fine
  if (queue->rear)
    queue->rear->next =
        NULL; // orphan the remaining, no need for memory freeing until it runs

  queue->count--;
  return;
  // free(temp); // This creates an AddressSanitizer error heap-use-after-free.
}

void dehash(Queue *queue, Hash *hash, unsigned bucket,
            int key) { // sets hash to null. Doesn't free
  unsigned test_bucket = hashfunc(
      hash->capacity, key); // should be same as passed in. for checking
  if (test_bucket != bucket) {
    if (REALLY_DEBUG)
      printf(
          "Warning, hash values coming out differently in dehash function\n");
  }
  if (hash->array[bucket]) { // we have to be certain this is right bucket
                             // adjusted for collision
    if (hash->array[bucket]->key == key) { // double check for debug
      // QNode* tmp = hash->array[bucket];
      if (REALLY_DEBUG)
        printf("Goodbye to hash[%d] with data %d\n", bucket,
               hash->array[bucket]->data);
      hash->array[bucket] = NULL;
      // free(tmp);
    } else if (REALLY_DEBUG)
      printf("entry found in hash but keys don't match. No action taken.\n");
    return;
  }
}

unsigned getGoodBucket(Hash *hash, int key) {
  unsigned try_bucket = hashfunc(hash->capacity, key);
  int hc = hash->capacity;
  if (REALLY_DEBUG)
    printf("try bucket and key %d , %d\n", try_bucket, key);
  if (hash->array[try_bucket] == NULL)
    return try_bucket;
  unsigned original_try = try_bucket;
  int c = 0;
  while (hash->array[try_bucket] != NULL) { // spot is taken
    // try_bucket = ((try_bucket + 1)) % hash->capacity;  //THIS IS NOT WORKING
    // FOR SOME REASON, STAYING AT 1 1 1 1 1 1 1 1 1 1 if (try_bucket ==
    // original_try)
    if (REALLY_DEBUG)
      printf("Try bucket %d and original try %d\n", try_bucket, original_try);
    try_bucket++;
    if (try_bucket == hc)
      try_bucket = 0;
    if (c == hc) { // no space found (erroneously I think)
      if (REALLY_DEBUG)
        printf("Sorry no space found in hash for new node, looped through "
               "everything (but should be found as hash entry should have been "
               "dequeued\n");
      return -1;
    }
    c++;
  }
  return try_bucket; // hope this works no collisions.
}

void EnqueueNewNode(struct LRUCache *cache, struct Queue *queue,
                    struct Hash *hash, int value, int key) {
  // remember queue was just dequeueed
  QNode *temp = newQNode(0);
  temp->data = value; // obviously have to put the value in there
  temp->key = key;    // needed for handling hash collisions
  int goodBucket = getGoodBucket(hash, key);
  if (REALLY_DEBUG)
    printf("GoodBucket to hash index on %d\n", goodBucket);
  temp->bucket = goodBucket; // Get it a bucket
  temp->prev = NULL;         // because it will go at head
  temp->next = queue->front;

  // attach node
  if (queue->rear == NULL) { // should mean queue is empty but double check
    if (queue->front != NULL)
      if (REALLY_DEBUG)
        printf("Rear null but head not, error\n");
    queue->rear = temp;
    queue->front = temp;
  } else if (queue->front == queue->rear) {
    queue->front = temp;
    queue->front->next = queue->rear;
    queue->front->next->prev = queue->front;
  } else { // min capacity 3
    queue->front->prev = temp;
    queue->front = temp;
  }
  hash->array[goodBucket] = temp; // pass to hash
  queue->count++;
  return;
}

void MoveNodeToFront(struct LRUCache *cache, struct Queue *queue,
                     struct Hash *hash, int value, int key,
                     int bucket) {  // can happen on get requests
  QNode *tmp = hash->array[bucket]; // pointer to the node in question
  if (tmp == queue->front) { // Already at head, don't need to do anything.
    return;
  } else if (queue->front ==
             queue->rear) { // shouldn't be triggered based on above condition.
    if (REALLY_DEBUG)
      printf("This should never run. Should be handled by the above condition. "
             "Implying error\n");
    if (REALLY_DEBUG)
      printf("Q count should be 1. Queue count is %d\n", queue->count);
    return;
  } else // standard case
  { // if in hash, should(!!) also be in the queue. If not, VERY BAD. Not super
    // easy to check
    if (REALLY_DEBUG)
      printf("bucket is still %d and key is %d (1)\n", bucket, key);
    if (tmp == NULL)
      if (REALLY_DEBUG)
        printf("QNode not found in Enqueue function bucket\n");
    if (tmp->prev == NULL)
      if (REALLY_DEBUG)
        printf(
            "Temp previous is null but should not be (because not at head)\n");

    if (REALLY_DEBUG)
      printf("hash[bucket]->data is %d\n", tmp->data);

    tmp->prev->next = tmp->next;
    if (tmp != queue->rear)
      tmp->next->prev = tmp->prev; // SEG FAULT if tmp is rear!!
    if (tmp == queue->rear)
      queue->rear = tmp->prev;
    tmp->prev->next = tmp->next;
    queue->front->prev = tmp;
    tmp->next = queue->front;
    queue->front =
        tmp; // queue front could point to queue->rear, or to an intermediary
    queue->front->prev = NULL; // Now the node in question is right pointed
    return; // queue count doesn't change. we're done? Will it work?
  }
  return;
}

void Enqueue(struct LRUCache *cache, struct Queue *queue, struct Hash *hash,
             int value, int key) {
  int bucket = searchCache(
      cache, key); // bucket can be -1 not found or bucket where exists
  if (REALLY_DEBUG)
    printf("Enqueuing key %d and bucket is: %d\n", key, bucket);

  if (queue->count == queue->capacity && bucket < 0) {
    if (REALLY_DEBUG)
      printf("Ready to dequeue rear and add new node\n");
    unsigned hashbucket = queue->rear->bucket;
    deQueue(queue);
    dehash(queue, hash, hashbucket, hash->array[hashbucket]->key);
  }

  if (bucket == -1) {
    EnqueueNewNode(cache, queue, hash, value, key);
    return;
  } else if (bucket >= 0) { // explicitly double checked, existing in cache
    MoveNodeToFront(cache, queue, hash, value, key, bucket);
    return;
  }
}

unsigned int hashfunc(unsigned capacity, int key) {
  unsigned int provisional_bucket = (key * 353) % capacity;
  return provisional_bucket; // may need adjustment (linear probing)
}

int searchCache(struct LRUCache *cache, int key) {
  // look in hash for item of "key"; double check key=key in case of collision
  unsigned test_bucket = hashfunc(cache->capacity, key);
  if (REALLY_DEBUG)
    printf("test bucket %d\n ", test_bucket); // 9
  if (cache->hash->array[test_bucket] != NULL) {
    if (cache->hash->array[test_bucket]->key == key) {
      return test_bucket; // simplest case, returns location
    } else {              // linear probe time
      int cap = cache->capacity;
      unsigned original_test_bucket = test_bucket;
      while (cache->hash->array[test_bucket] != NULL) {
        test_bucket = ((test_bucket + 1) % cap);
        if (test_bucket ==
            original_test_bucket) { // back to start, avoid infinite looping
          if (REALLY_DEBUG)
            printf("Probed hash, object not found. returning -1\n");
          return -1; // returns -1
        }
        if (cache->hash->array[test_bucket] != NULL &&
            cache->hash->array[test_bucket]->key == key)
          return test_bucket;
      }
    }
  } else { // just have else for good measure. Simply not found in array
    return -1;
  }
  return -1;
}
// Declarations
void freeQueue(Queue *queue);
void freeHash(Hash *hash);
void freeQNode(QNode *qnode);
void printQueueData(LRUCache *cache, char *op);

struct LRUCache *lRUCacheCreate(int capacity) {
  struct LRUCache *cache = malloc(sizeof(struct LRUCache));
  cache->capacity = capacity;
  cache->queue = createQueue(capacity);
  cache->hash = createHash(capacity);
  return cache;
} // THIS IS WHERE THE ERROR HAPPEN(ED) -- fixed- (sort of), but not understood

int lRUCacheGet(struct LRUCache *obj, int key) {
  if (REALLY_DEBUG)
    printf("\nGetting key %d\n", key);
  int location = searchCache(obj, key);
  if (location >= 0) { // found, else searchCache returns -1
    // printf("location found at %d\n", location);  // PRINTF
    struct QNode *tempNode =
        obj->hash->array[location]; // found in hash  SEG FAULT HERE!!
    int tempData = tempNode->data;  // Preserve Data before enqeueing
    Enqueue(obj, obj->queue, obj->hash, tempData,
            key); // TODO redundantly recalculates hash. Should be separate
                  // funtion "reorder" or "move_to_head"?
    return tempData;
  } else {
    return location; // is -1 already
  }
}

void lRUCachePut(struct LRUCache *obj, int key, int value) {
  int bucket = searchCache(obj, key); // already checks that key is right
  if (bucket >= 0) {
    int existing_value = obj->hash->array[bucket]->data;
    if (value != existing_value) {
      obj->hash->array[bucket]->data = value;
    }
    MoveNodeToFront(obj, obj->queue, obj->hash, value, key, bucket);
    return;
  }
  // unsigned bucket = hashfunc(obj->capacity, key); // gets original bucket
  if (REALLY_DEBUG)
    printf("\nPutting key %d value %d\n", key, value);
  Enqueue(obj, obj->queue, obj->hash, value,
          key); // also dequeues/dehashes, adds to hash, moves to front
}

void lRUCacheFree(struct LRUCache *obj) {
  freeQueue(obj->queue);
  freeHash(obj->hash);
  free(obj);
  return;
}

void freeQueue(struct Queue *queue) {
  struct QNode *curr = queue->front;
  while (curr) {
    QNode *tmp = curr;
    curr = curr->next;
    free(tmp);
  }
  free(queue);
}
void freeHash(
    Hash *hash) { // if you free the nodes associated with the hash in the
                  // linked list, you also free them in the hash right? Because
                  // they're pointed at. They'll point at null or rather out of
                  // range things (seg fault territory?)
  free(hash);
}
void freeQNode(QNode *qnode);

void printQueueData(LRUCache *cache, char *op) {
  QNode *n = cache->queue->front;
  int c = 0;
  QNode *p = n->prev;
  while (n != NULL) {
    printf("QC:%d ", cache->queue->capacity);
    printf("QueueNode %d k:%d data = %d  n->prev:%d, n->next:%d\n", c, n->key,
           n->data, n->prev != NULL, n->next != NULL);
    c++;
    n = n->next;
  }
  if (p == NULL)
    printf("Front's prev points to null. ");
  printf("next queue node is NULL\n");
  QNode *r = cache->queue->rear;
  if (r)
    printf("Queue Rear exists:%d and its data: %d\n", r != NULL, r->data);
}

void printCurrentState(LRUCache *cache, char *op) {
  if (DEBUG_MODE) {
    printf("\nCURRENT STATE after %s::::::::::\n", op);
    printf("cache has capacity of %d\n", cache->capacity);
    printQueueData(cache, op);
    for (int i = 0; i < cache->capacity; i++) {
      if (cache->hash->array[i] != NULL)
        printf("Hashtable[%d] = %d\n", i, cache->hash->array[i]->data);
    }
  }
}