aboutsummaryrefslogtreecommitdiff
path: root/lru_cache.c
blob: f0c43a0bba6df45d1ca6ab9e47f83552c9b0608d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
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);
    }
  }
}