2
\$\begingroup\$

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, or missing inline function, namespaces or macros.

Please suggest how to make this code production grade.

PS: This is my first question. All suggestions around the question detailing 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;
    }
};
```
\$\endgroup\$
2
  • 3
    \$\begingroup\$ To those that down voted this question or voted to close, please leave a comment why you down voted or voted to close. As far as I can tell this is a valid question for code review. \$\endgroup\$ – pacmaninbw Feb 5 at 13:46
  • \$\begingroup\$ I don't have time now to write a proper review, but object caches likely benefit from std::weak_ptr - you might want to keep a collection (perhaps a std::unordered_map) of weak pointers, which you can convert to shared pointer before giving out. Worth reading about, anyway. \$\endgroup\$ – Toby Speight Feb 10 at 13:42
2
\$\begingroup\$

Some preliminary observations to get you started:

Allocation

Since Disk and Cache aren't memory management classes, do not write your own memory management code, since C++ memory management is error-prone. Instead, use standard library facilities like std::vector whenever possible.

Move semantics

This always copies the argument:

void setContent(const std::string& newContent)
{
    content = newContent;
}

Take a std::string and use std::move instead.

Encapsulation

When a class is all-public, you don't need getters and setters. Therefore, Page should either be simply

struct Page {
    int id;
    std::string content{"---"};
    Page* prev;
    Page* next;
};

or have private data members and proper encapsulation.

Miscellaneous

Headers from the standard library are usually delimited with <> instead of "". Moreover, header files should be self-contained and include the necessary header files, rather than rely on the source file to include them beforehand. (Multiple inclusions of the same header will be elided by the compiler.) You are also missing some #includes, such as <cstddef> and <cstdio>.

Names from the C standard library should still be qualified as std:: in C++.

\$\endgroup\$
2
\$\begingroup\$

Few things I noticed

Const correctness

It is good practice to make methods as getters const

Setting values in a destructor

No reason that I am aware of to do pageAr = nullptr; pageCount = 0; during destruction.

Range-based for loop

They are less error-prone (you can't mess up with indices) so I would suggest using them if possible

Miscellaneous

std::string& getContent()
{
    return content;
}

It is better to return const std::string& because it seems that it is not intended to give a possibility to alter content using this getter

\$\endgroup\$
2
\$\begingroup\$

When I see pointers in a class and/or struct in my mind comes e serious potential for memory leaks unless a careful implementation has been considered. Since you would like comments on how to make this code closer to a production-level code, avoiding memory leaks is definitely a very important aspect.

I will explain myself using an example:

Let's say a teammate in the company you work with, uses your user-defined datatypes (Page, Disk, Cache), and at some point in the code he writes, he passes an object which is an instance of some of your datatypes to a function (a fairly innocent action). If he pass the object by value, then probably the whole production code is in serious trouble. Because passing-by-value any datatype (built-in or user-defined) invokes a copy operation of the object, as defined by the class declaration. Since you do not explicitly create your own copy constructor, the default one will be used which will result in copies of the pointers of the class, and this is prone to segmentation-fault. The reason is because you are going to have the same pointer (memory address) belong to two different objects. Once the function call finishes, the object in the class will be destroyed and will dereference the pointers that the object in the main code hold. Afterward, once the whole program exits, those pointers will be dereferenced again (or at least will be attempted to) and this is undefined behavior, which could break the whole runtime.

So, since you have pointers in your classes or structs make sure to learn how to write at least correctly the copy constructor and copy assignment operators.

That was not the end of the story. Sometimes in your code, you may have heavy objects and do not want to copy them around for performance reasons. This means that except from copy you may also want to check how to implement the move constructor.

Fortunately, there is a way to avoid writing all the stuff yourself. One good option is to use std::vector which handles the above correctly and efficiently. Otherwise, you can make your own implementation using pointers but check out how to do it correctly!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.