This C++ Program demonstrates the implementation of LRU Cache.
Here is source code of the C++ Program to demonstrate the implementation of LRU Cache. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C++ Program to Implement LRU Cache
*/
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
// A Queue Node (Queue is implemented using Doubly Linked List)
typedef struct QNode
{
QNode *prev, *next;
unsigned pageNumber;
} QNode;
// A Queue (A FIFO collection of Queue Nodes)
typedef struct Queue
{
unsigned count;
unsigned numberOfFrames;
QNode *front, *rear;
} Queue;
// A hash (Collection of pointers to Queue Nodes)
typedef struct Hash
{
int capacity;
QNode **array;
} Hash;
// A utility function to create a new Queue Node.
QNode* newQNode(unsigned pageNumber)
{
QNode* temp = new QNode;
temp->pageNumber = pageNumber;
temp->prev = temp->next = NULL;
return temp;
}
// A utility function to create an empty Queue.
Queue* createQueue(int numberOfFrames)
{
Queue* queue = new Queue;
queue->count = 0;
queue->front = queue->rear = NULL;
queue->numberOfFrames = numberOfFrames;
return queue;
}
// A utility function to create an empty Hash of given capacity
Hash* createHash(int capacity)
{
Hash* hash = new Hash;
hash->capacity = capacity;
hash->array = new QNode* [hash->capacity];
int i;
for(i = 0; i < hash->capacity; ++i)
hash->array[i] = NULL;
return hash;
}
// A function to check if there is slot available in memory
int AreAllFramesFull(Queue* queue)
{
return queue->count == queue->numberOfFrames;
}
// A utility function to check if queue is empty
int isQueueEmpty( Queue* queue )
{
return queue->rear == NULL;
}
// A utility function to delete a frame from queue
void deQueue( Queue* queue )
{
if (isQueueEmpty(queue))
return;
if (queue->front == queue->rear)
queue->front = NULL;
QNode* temp = queue->rear;
queue->rear = queue->rear->prev;
if (queue->rear)
queue->rear->next = NULL;
free(temp);
queue->count--;
}
// A function to add a page with given 'pageNumber' to both queue and hash
void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber)
{
if (AreAllFramesFull(queue))
{
hash->array[queue->rear->pageNumber] = NULL;
deQueue(queue);
}
QNode* temp = newQNode(pageNumber);
temp->next = queue->front;
if (isQueueEmpty(queue))
queue->rear = queue->front = temp;
else
{
queue->front->prev = temp;
queue->front = temp;
}
hash->array[pageNumber] = temp;
queue->count++;
}
// This function is called when a page with given 'pageNumber' is referenced
// from cache (or memory).
void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)
{
QNode* reqPage = hash->array[pageNumber];
if (reqPage == NULL)
Enqueue(queue, hash, pageNumber);
else if (reqPage != queue->front)
{
reqPage->prev->next = reqPage->next;
if (reqPage->next)
reqPage->next->prev = reqPage->prev;
if (reqPage == queue->rear)
{
queue->rear = reqPage->prev;
queue->rear->next = NULL;
}
reqPage->next = queue->front;
reqPage->prev = NULL;
reqPage->next->prev = reqPage;
queue->front = reqPage;
}
}
// Main
int main()
{
Queue* q = createQueue(4);
Hash* hash = createHash( 10 );
ReferencePage(q, hash, 1);
ReferencePage(q, hash, 2);
ReferencePage(q, hash, 3);
ReferencePage(q, hash, 1);
ReferencePage(q, hash, 4);
ReferencePage(q, hash, 5);
cout<<q->front->pageNumber<<" ";
cout<<q->front->next->pageNumber<<" ";
cout<<q->front->next->next->pageNumber<<" ";
cout<<q->front->next->next->next->pageNumber<<" ";
return 0;
}
$ g++ lru.cpp $ a.out 5 4 1 3 ------------------ (program exited with code: 1) Press return to continue
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Related Posts:
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Computer Science MCQs