jeudi 4 février 2021

LRU Cache Implementation in C++

I am learning C++ by implementing small design problems. I have tried to implement LRU cache and the implementation that I have attached here works fine.

However, I am not sure whether my code is in line with C++ best practices. For eg. Unnecessary use of ref, pointers and const.

Please suggest how to make this code production grade.

PS: This is my first question. All suggestions are welcome.

Main.cpp

/******************************************************************************

Implement LRU Cache

*******************************************************************************/
#include "unordered_map"
#include "string"

#include "Page.h"
#include "Disk.h"
#include "Cache.h"

int main()
{
    Disk disk(10);
    Cache cache(disk, 2);
    
    cache.getPage(1);
    cache.getPage(2);
    disk.writePage(2, "Hello");
    cache.getPage(2);
    cache.getPage(1);
    cache.getPage(3);

    return 0;
}

Page.h

struct Page {
    int id;
    std::string content;
    
    Page* prev;
    Page* next;
    
    Page(int id): 
        id(id), 
        content("---"),
        prev(nullptr),
        next(nullptr)
    {
        
    }
    
    int getId()
    {
        return id;
    }
    
    std::string& getContent()
    {
        return content;
    }
    
    void setContent(const std::string& newContent)
    {
        content = newContent;
    }
};

Disk.h

class Disk {
    Page** pageAr = nullptr;
    size_t pageCount = 0;
    
    public:
    
    Disk(size_t pageCount): pageCount(pageCount)
    {
        pageAr = new Page*[pageCount];
        for(int i=0; i<pageCount; ++i)
        {
            pageAr[i] = new Page(i);
        }
    }
    
    Page* readPage(int pageIndex) {
        printf("Reading page %d from DISK\n", pageIndex);
        return pageAr[pageIndex];
    }
    
    void writePage(int pageIndex, const std::string& newContent)
    {
        printf("Updating page %d on DISK to %s\n", pageIndex, newContent.c_str());
        Page* pg = pageAr[pageIndex];
        pg->setContent(newContent);
    }
    
    ~Disk()
    {
        for(int i=0; i<pageCount; i++)
        {
            delete pageAr[i];
        }
        delete [] pageAr;
        pageAr = nullptr;
        pageCount = 0;
    }
};

Cache.h

class Cache {
    Disk& disk;
    size_t cacheSize;
    Page* pageQueueStart;
    Page* pageQueueEnd;
    std::unordered_map<int, Page*> pageTable;
    
    
    void addPage(Page* p)
    {
        p->prev = nullptr;
        p->next = pageQueueStart;
        if(pageQueueStart != nullptr)
            pageQueueStart->prev = p;
        pageQueueStart = p;
        
        if(pageQueueEnd == nullptr)
            pageQueueEnd = p;
            
        pageTable[p->getId()] = p;
    }
    
    void removePage(Page* p)
    {
        if(p->prev != nullptr)
        {
            p->prev->next = p->next;
        }
        else
        {
            pageQueueStart = p->next;    
        }
        
        if(p->next != nullptr)
        {
            p->next->prev = p->prev;
        }
        else
        {
            pageQueueEnd = p->prev;
        }
        
        p->prev = nullptr;
        p->next = nullptr;
        
        pageTable.erase(p->getId());
    }
    
    void removeLeastRecentlyUsedPage()
    {
        printf("Remove Page %d from CACHE\n", pageQueueEnd->getId());
        if(pageQueueEnd->prev)
            pageQueueEnd->prev->next = nullptr;
        pageQueueEnd->prev = nullptr;
        pageQueueEnd->next = nullptr;
        
        pageTable.erase(pageQueueEnd->getId());
    }
    
    public:
    Cache(Disk& disk, size_t cacheSize): 
        disk(disk),
        cacheSize(cacheSize),
        pageQueueStart(nullptr), 
        pageQueueEnd(nullptr)
    {
        
    }
    
    Page* getPage(int pageIndex)
    {
        printf("Reading page %d from CACHE\n", pageIndex);
        if(pageTable.find(pageIndex) == pageTable.end())
        {
            printf("\tMISS\n");
            Page* pageFromDisk = disk.readPage(pageIndex);
            if(pageTable.size() >= cacheSize)
                removeLeastRecentlyUsedPage();
            
            addPage(pageFromDisk);
        }
        else
        {
            printf("\tHIT\n");
            Page* pageFromCache = pageTable[pageIndex];
            
            removePage(pageFromCache);
            addPage(pageFromCache);
        }
        
        printf("Page content : %s\n", pageTable[pageIndex]->getContent().c_str());
        return pageTable[pageIndex];
    }
    
    ~Cache()
    {
        pageQueueStart = nullptr;
        pageQueueEnd = nullptr;
    }
};

Aucun commentaire:

Enregistrer un commentaire