aboutsummaryrefslogtreecommitdiff
path: root/lru_cache.c
diff options
context:
space:
mode:
Diffstat (limited to 'lru_cache.c')
-rw-r--r--lru_cache.c404
1 files changed, 404 insertions, 0 deletions
diff --git a/lru_cache.c b/lru_cache.c
new file mode 100644
index 0000000..f0c43a0
--- /dev/null
+++ b/lru_cache.c
@@ -0,0 +1,404 @@
+// 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);
+ }
+ }
+}