C++ Programming Code Examples

C++ > Data Structures Code Examples

C++ Program to Implement LRU Cache



C++ Program to Implement LRU Cache

This C++ Program demonstrates the implementation of 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;

    }