C++ Program to Implement LRU Cache

«
»
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.

  1. /*
  2.  * C++ Program to Implement LRU Cache
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cmath>
  7. using namespace std;
  8.  
  9. // A Queue Node (Queue is implemented using Doubly Linked List)
  10. typedef struct QNode
  11. {
  12.     QNode *prev, *next;
  13.     unsigned pageNumber;
  14. } QNode;
  15.  
  16. // A Queue (A FIFO collection of Queue Nodes)
  17. typedef struct Queue
  18. {
  19.     unsigned count;
  20.     unsigned numberOfFrames;
  21.     QNode *front, *rear;
  22. } Queue;
  23.  
  24. // A hash (Collection of pointers to Queue Nodes)
  25. typedef struct Hash
  26. {
  27.     int capacity;
  28.     QNode **array;
  29. } Hash;
  30.  
  31. // A utility function to create a new Queue Node.
  32. QNode* newQNode(unsigned pageNumber)
  33. {
  34.     QNode* temp = new QNode;
  35.     temp->pageNumber = pageNumber;
  36.     temp->prev = temp->next = NULL;
  37.     return temp;
  38. }
  39.  
  40. // A utility function to create an empty Queue.
  41. Queue* createQueue(int numberOfFrames)
  42. {
  43.     Queue* queue = new Queue;
  44.     queue->count = 0;
  45.     queue->front = queue->rear = NULL;
  46.     queue->numberOfFrames = numberOfFrames;
  47.     return queue;
  48. }
  49.  
  50. // A utility function to create an empty Hash of given capacity
  51. Hash* createHash(int capacity)
  52. {
  53.     Hash* hash = new Hash;
  54.     hash->capacity = capacity;
  55.     hash->array = new QNode* [hash->capacity];
  56.     int i;
  57.     for(i = 0; i < hash->capacity; ++i)
  58.         hash->array[i] = NULL;
  59.     return hash;
  60. }
  61.  
  62. // A function to check if there is slot available in memory
  63. int AreAllFramesFull(Queue* queue)
  64. {
  65.     return queue->count == queue->numberOfFrames;
  66. }
  67.  
  68. // A utility function to check if queue is empty
  69. int isQueueEmpty( Queue* queue )
  70. {
  71.     return queue->rear == NULL;
  72. }
  73.  
  74. // A utility function to delete a frame from queue
  75. void deQueue( Queue* queue )
  76. {
  77.     if (isQueueEmpty(queue))
  78.         return;
  79.     if (queue->front == queue->rear)
  80.         queue->front = NULL;
  81.     QNode* temp = queue->rear;
  82.     queue->rear = queue->rear->prev;
  83.     if (queue->rear)
  84.         queue->rear->next = NULL;
  85.     free(temp);
  86.     queue->count--;
  87. }
  88.  
  89. // A function to add a page with given 'pageNumber' to both queue and hash
  90. void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber)
  91. {
  92.     if (AreAllFramesFull(queue))
  93.     {
  94.         hash->array[queue->rear->pageNumber] = NULL;
  95.         deQueue(queue);
  96.     }
  97.     QNode* temp = newQNode(pageNumber);
  98.     temp->next = queue->front;
  99.     if (isQueueEmpty(queue))
  100.         queue->rear = queue->front = temp;
  101.     else
  102.     {
  103.         queue->front->prev = temp;
  104.         queue->front = temp;
  105.     }
  106.     hash->array[pageNumber] = temp;
  107.     queue->count++;
  108. }
  109.  
  110. // This function is called when a page with given 'pageNumber' is referenced
  111. // from cache (or memory).
  112. void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)
  113. {
  114.     QNode* reqPage = hash->array[pageNumber];
  115.     if (reqPage == NULL)
  116.         Enqueue(queue, hash, pageNumber);
  117.     else if (reqPage != queue->front)
  118.     {
  119.         reqPage->prev->next = reqPage->next;
  120.         if (reqPage->next)
  121.            reqPage->next->prev = reqPage->prev;
  122.         if (reqPage == queue->rear)
  123.         {
  124.            queue->rear = reqPage->prev;
  125.            queue->rear->next = NULL;
  126.         }
  127.         reqPage->next = queue->front;
  128.         reqPage->prev = NULL;
  129.         reqPage->next->prev = reqPage;
  130.         queue->front = reqPage;
  131.     }
  132. }
  133.  
  134. // Main
  135. int main()
  136. {
  137.     Queue* q = createQueue(4);
  138.     Hash* hash = createHash( 10 );
  139.     ReferencePage(q, hash, 1);
  140.     ReferencePage(q, hash, 2);
  141.     ReferencePage(q, hash, 3);
  142.     ReferencePage(q, hash, 1);
  143.     ReferencePage(q, hash, 4);
  144.     ReferencePage(q, hash, 5);
  145.     cout<<q->front->pageNumber<<"  ";
  146.     cout<<q->front->next->pageNumber<<"  ";
  147.     cout<<q->front->next->next->pageNumber<<"  ";
  148.     cout<<q->front->next->next->next->pageNumber<<"  ";
  149.     return 0;
  150. }

$ 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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.