Caching

Here we are caching "int" "pageNumber" in cache. in queueNode.
Objects can be saved instead of "int" and Caches can be maintained and objects can be removed from Cache based on policy. that we need to define in our saved "Object".

Here I have given Java Implementation of LRUCache. Soon I will be back with another policy cache.

public class LRUCache {
    Queue queue; Hash hash;

    public LRUCache(int numberOfFrames, int capacity) {
        queue = new Queue(numberOfFrames);
        hash = new Hash(capacity);
    }

    public static void main(String[] args) {
        // Let cache can hold 4 pages & 10 different pages        // can be requested (numbered from 0 to 9)        LRUCache cache = new LRUCache(4, 10);
        cache.referencePage(1);        cache.referencePage(2);
        cache.referencePage(3);        cache.referencePage(1);
        cache.referencePage(4);        cache.referencePage(5);
        cache.queue.print();
    }

    class QNode {
        QNode prev, next;
        int pageNumber;
        QNode(int pageNumber) { this.pageNumber = pageNumber; }
    }

    class Queue {
        int count, numberOfFrames;
        QNode front, rear;
        Queue(int numberOfFrames) { this.numberOfFrames = numberOfFrames; }

        void print() {
            QNode temp = front;
            while (temp != null) {
                // Let us print cache frames after the above referenced pages                System.out.println(temp.pageNumber);  temp = temp.next;
            } } }

    class Hash {
        int capacity;
        QNode array[];

        Hash(int capacity) { this.capacity = capacity;
            array = new QNode[capacity];
        } }

    boolean areAllFramesFull(Queue queue) {
        return queue.count == queue.numberOfFrames;
    }

    boolean isQueueEmpty(Queue queue) { return queue.rear == null; }

    void deQueue(Queue queue) {
        if (isQueueEmpty(queue)) return;
        // if this is the only node in list, then change front        if (queue.front == queue.rear) queue.front = null;
        queue.rear = queue.rear.prev;
        if (queue.rear != null) queue.rear.next = null;
        queue.count--;
    }

    void enQueue(Queue queue, Hash hash, int pageNumber) {
        if (areAllFramesFull(queue)) {
            hash.array[queue.rear.pageNumber] = null;
            deQueue(queue);
        }
        QNode temp = new QNode(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++;
    } 
    
    void referencePage(int pageNumber) {
        QNode reqPage = hash.array[pageNumber];
        // the page is no3t in cache, bring it        if (reqPage == null) enQueue(queue, hash, pageNumber);
            // page is there and not at front, change pointer        else if (reqPage != queue.front) {
            // Unlink rquested page from its current location in queue.            reqPage.prev.next = reqPage.next;
            if (reqPage.next != null) reqPage.next.prev = reqPage.prev;
            // If the requested page is rear, then change rear as this node will be moved to front            if (reqPage == queue.rear) {
                queue.rear = reqPage.prev;
                queue.rear.next = null; }
            // Put the requested page before current front            reqPage.next = queue.front;  reqPage.prev = null;
            // Change prev of current front            reqPage.next.prev = reqPage; 
            // Change front to the requested page            queue.front = reqPage;
        } } }