# Creating a cache manager

I am purely new to C++ memory management. Am I on the right path, or should I employ a different design strategy or a different memory manager policy (such as weak_ptr)?

#include <mutex>
#include <assert.h>
#include <iostream>
#include <unordered_map>
#include <memory>
#include <string>
#include <stdio.h>

//
// Requirements:
//  1: the bitmap could be used by multiple thread safely.(std::shared_ptr could?)
//    2: cache the bitmap and do not always increase memeory
struct Bitmap {
public:
Bitmap(const std::string& filePath) {
filePath_ = filePath;
printf("foo %x ctor %s\n", this, filePath_.c_str());
}
~Bitmap() {
printf("foo %x dtor %s\n", this, filePath_.c_str());
}
std::string filePath_;
};

struct BitmapCache {
public:
static std::shared_ptr<Bitmap> loadBitmap(const std::string& filePath) {
mutex_.lock();

//whether in the cache
auto iter = cache_.find(filePath);
if (iter != cache_.end()) {
if ((*iter).second) {
return (*iter).second;
} else {
std::shared_ptr<Bitmap> newPtr(new Bitmap(filePath));
(*iter).second = newPtr;
return newPtr;
}
}

//try remove unused elements if possible
if (cache_.size() >= kSlotThreshold) {
std::unordered_map<std::string,std::shared_ptr<Bitmap>>::iterator delIter = cache_.end();
for (auto iter = cache_.begin(); iter != cache_.end(); ++iter) {
auto& item = *iter;
if (item.second && item.second.use_count() == 1) {
delIter = iter;
break;
}
}
if (cache_.end() != delIter) {
(*delIter).second.reset();
cache_.erase(delIter);
}
}

//create new and insert to the cache
std::shared_ptr<Bitmap> newPtr(new Bitmap(filePath));
cache_.insert({filePath, newPtr});
mutex_.unlock();
return newPtr;
}
private:
static const int kSlotThreshold = 20;
static std::mutex mutex_;
static std::unordered_map<std::string,std::shared_ptr<Bitmap>> cache_;
};

/* static */
std::unordered_map<std::string,std::shared_ptr<Bitmap>> BitmapCache::cache_;

/* static */
std::mutex BitmapCache::mutex_;

int main()
{
//test for remove useless element
char buff[200] = {0};
std::vector<std::shared_ptr<Bitmap>> bmpVec(20);
for (int i = 0; i < 20; ++i) {
sprintf_s(buff, 200, "c:\\haha%d.bmp", i);
}
bmpVec[3].reset();

//test for multiple threading...(to be implemenetd)
return 0;
}

-

The major question you should be asking is "what am I going to do with these bitmaps"? Threading is an issue when you have multiple threads writing the same data - multiple threads reading the same data (and only reading it) don't cause such problems. Whether you are going about this the correct way or not depends heavily on the answer to that question.

However, some of this code can be cleaned up and improved somewhat, regardless of that answer.

Calling mutex_.lock() and then explicitly calling mutex_.unlock() is dangerous. If anything in between those calls throws an exception, then your mutex will never be unlocked, and you'll have a deadlock. Solving this is easy, and just requires using what is known as RAII (Resource Acquisition is Initialization). In this case, this is done by using a std::lock_guard:

  static std::shared_ptr<Bitmap> loadBitmap(const std::string& filePath) {
std::lock_guard<std::mutex> guard(mutex_);
...
} // mutex_ is unlocked as soon as it goes out of scope


This ensures that mutex_ will always be unlocked, no matter how the function exists (whether normally or through an exception).

You use auto in a few places, so you might as well simplify:

std::unordered_map<std::string,std::shared_ptr<Bitmap>>::iterator delIter = cache_.end();


to:

auto delIter = cache_.end();


The loadBitmap function itself has dubious design. It isn't just loading a bitmap, but is also trying to clean out the cache. Performing this second step should absolutely be broken out into a separate function:

void remove_from_cache()
{
if (cache_.size() >= kSlotThreshold) {
auto delIter = cache_.end();
for (auto iter = cache_.begin(); iter != cache_.end(); ++iter) {
auto& item = *iter;
if (item.second && item.second.use_count() == 1) {
delIter = iter;
break;
}
}
if (cache_.end() != delIter) {
(*delIter).second.reset();
cache_.erase(delIter);
}
}


The current cache size is very small (20 elements). If you expect this to remain small (< 1000 elements), you may want to consider using a std::vector instead. At this size, constants involved in the O(1) lookup for a hashmap dominate, and std::vector will (potentially) be quicker. If you expect many more lookups than insertions, a sorted vector could also work.

The reason I suggest is that this would make clearing out the cache much easier: using a std::vector (which would look something like std::vector<std::pair<std::string, std::shared_ptr<Bitmap>>> (which could really do with a using statement or 3)), then erasing values is simply:

using pair_t = std::pair<std::string, std::shared_ptr<Bitmap>>;
using container_t = std::vector<pair_t>;
container_t cache;

void remove_from_cache()
{
if(cache.size() > kSlotThreshold) {
cache.erase(std::remove_if(cache.begin(), cache.end(),
[](const pair_t& p) { return p.second.use_count() == 1; }),
cache.end());
}
}


Whether this removal algorithm is any good or not is up for some debate, you might want to look at something like an LRU (least recently used) cache instead - currently, there is no guarantee that your algorithm will remove things from the cache. Also, this would require a (very minor) change to your lookup code:

 auto iter = cache_.find(filePath);


would become:

 auto iter = std::find_if(cache.begin(), cache.end(),
[&](const pair_t& p) { return p.first == filePath; });


A few final small points:

Prefer to use std::make_shared instead of constructing the shared pointer directly, for example:

std::shared_ptr<Bitmap> newPtr(new Bitmap(filePath));


should be:

auto newPtr = std::make_shared<Bitmap>(filePath);


If you're defining a struct just to give things a scope to live in (and hence using static for everything), use a namespace instead.

-
Could you explain why should I prefer make_shared rather than direct constructing from the raw pointer? –  Jichao Jun 24 at 7:22
@Jichao See stackoverflow.com/questions/18301511/… for an explanation –  Yuushi Jun 24 at 7:26

Just a note to your mutex usage:

You have to be careful to make sure you always unlock your mutex on any code path otherwise you run into the danger of locking your cache forever potentially causing deadlocks which will be hard to track down.

Right now you have forgotten to unlock the mutex when you find the entry but the object is not set (you do return newPtr there).

Also if any code should throw an exception for any reason it will leave the mutex in a locked state.

To ensure your mutex is always unlocked you should use a lock_guard:

    static std::shared_ptr<Bitmap> loadBitmap(const std::string& filePath) {
std::lock_guard<std::mutex> lock(mutex_);

....
}


This way the mutex will automatically get unlocked when the lock guard goes out of scope (either via return or through an exception).

-