#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Structure for a node in the doubly linked list (LRU order)
struct CacheNode {
int key;
int value;
struct CacheNode* prev;
struct CacheNode* next;
};
// Structure for a hash table entry (linked list for collision handling)
struct HashNode {
int key;
int value;
struct CacheNode* cachePtr; // Pointer to the corresponding LRU node
struct HashNode* next;
};
// Structure for the cache
struct Cache {
int capacity; // Maximum number of items
int size; // Current number of items
struct HashNode** hashTable; // Array of linked lists for hashing
struct CacheNode* lruHead; // Most recently used
struct CacheNode* lruTail; // Least recently used
};
// Function to create a cache node
struct CacheNode* createCacheNode(int key, int value) {
struct CacheNode* node = (struct CacheNode*)malloc(sizeof(struct CacheNode));
if (!node) {
printf("Memory allocation failed!\n");
exit(1);
}
node->key = key;
node->value = value;
node->prev = node->next = NULL;
return node;
}
// Function to create a hash node
struct HashNode* createHashNode(int key, int value, struct CacheNode* cachePtr) {
struct HashNode* node = (struct HashNode*)malloc(sizeof(struct HashNode));
if (!node) {
printf("Memory allocation failed!\n");
exit(1);
}
node->key = key;
node->value = value;
node->cachePtr = cachePtr;
node->next = NULL;
return node;
}
// Function to initialize the cache
struct Cache* createCache(int capacity) {
struct Cache* cache = (struct Cache*)malloc(sizeof(struct Cache));
if (!cache) {
printf("Memory allocation failed!\n");
exit(1);
}
cache->capacity = capacity;
cache->size = 0;
cache->lruHead = cache->lruTail = NULL;
// Initialize hash table (assuming keys are non-negative integers)
cache->hashTable = (struct HashNode**)calloc(capacity, sizeof(struct HashNode*));
if (!cache->hashTable) {
printf("Memory allocation failed!\n");
exit(1);
}
return cache;
}
// Hash function (simple modulo for demonstration)
unsigned int hashFunction(int key, int capacity) {
return key % capacity;
}
// Function to move a node to the front of the LRU list (most recently used)
void moveToFront(struct Cache* cache, struct CacheNode* node) {
if (node == cache->lruHead) {
return; // Already at front
}
// Remove node from current position
if (node->prev) {
node->prev->next = node->next;
}
if (node->next) {
node->next->prev = node->prev;
}
if (node == cache->lruTail) {
cache->lruTail = node->prev;
}
// Move to front
node->next = cache->lruHead;
node->prev = NULL;
if (cache->lruHead) {
cache->lruHead->prev = node;
}
cache->lruHead = node;
if (!cache->lruTail) {
cache->lruTail = node;
}
}
// Function to put a key-value pair in the cache
void put(struct Cache* cache, int key, int value) {
unsigned int index = hashFunction(key, cache->capacity);
// Check if key already exists
struct HashNode* current = cache->hashTable[index];
while (current) {
if (current->key == key) {
// Update value and move to front
current->value = value;
current->cachePtr->value = value;
moveToFront(cache, current->cachePtr);
printf("Updated key %d with value %d\n", key, value);
return;
}
current = current->next;
}
// If cache is full, remove the least recently used item
if (cache->size >= cache->capacity) {
// Remove from LRU list
struct CacheNode* lruNode = cache->lruTail;
int lruKey = lruNode->key;
cache->lruTail = lruNode->prev;
if (cache->lruTail) {
cache->lruTail->next = NULL;
} else {
cache->lruHead = NULL;
}
// Remove from hash table
index = hashFunction(lruKey, cache->capacity);
struct HashNode* prev = NULL;
current = cache->hashTable[index];
while (current && current->key != lruKey) {
prev = current;
current = current->next;
}
if (prev) {
prev->next = current->next;
} else {
cache->hashTable[index] = current->next;
}
free(current);
free(lruNode);
cache->size--;
printf("Evicted key %d\n", lruKey);
}
// Insert new key-value pair
struct CacheNode* cacheNode = createCacheNode(key, value);
moveToFront(cache, cacheNode);
struct HashNode* hashNode = createHashNode(key, value, cacheNode);
hashNode->next = cache->hashTable[index];
cache->hashTable[index] = hashNode;
cache->size++;
printf("Inserted key %d with value %d\n", key, value);
}
// Function to get the value for a key
int get(struct Cache* cache, int key) {
unsigned int index = hashFunction(key, cache->capacity);
struct HashNode* current = cache->hashTable[index];
while (current) {
if (current->key == key) {
moveToFront(cache, current->cachePtr);
printf("Retrieved key %d with value %d\n", key, current->value);
return current->value;
}
current = current->next;
}
printf("Key %d not found\n", key);
return -1; // Key not found
}
// Function to display the cache contents and LRU order
void displayCache(struct Cache* cache) {
printf("Cache Contents (Hash Table):\n");
for (int i = 0; i < cache->capacity; i++) {
printf("Index %d: ", i);
struct HashNode* current = cache->hashTable[i];
while (current) {
printf("(%d, %d) ", current->key, current->value);
current = current->next;
}
printf("\n");
}
printf("LRU Order (Most to Least Recent): ");
struct CacheNode* current = cache->lruHead;
while (current) {
printf("(%d, %d) ", current->key, current->value);
current = current->next;
}
printf("\n");
}
// Main function to test the cache
int main() {
struct Cache* cache = createCache(3); // Cache with capacity 3
// Test insertions
put(cache, 1, 100); // Insert (1, 100)
put(cache, 2, 200); // Insert (2, 200)
put(cache, 3, 300); // Insert (3, 300)
displayCache(cache);
// Test get
get(cache, 2); // Should move 2 to front
displayCache(cache);
// Test update
put(cache, 1, 150); // Update value of key 1
displayCache(cache);
// Test eviction
put(cache, 4, 400); // Should evict least recently used (3)
displayCache(cache);
// Test get for non-existent key
get(cache, 3); // Should return -1
return 0;
}
Output:
Comments
Post a Comment