fifo cache의 변형

fifo 정책을 따르긴하지만 쫓겨나는 item을 알고 이후 처리가 필요하여 구현

key-value이긴하지만 key가 2개여서 pair로 묶음

Push()에 의해 쫓겨나는 item은 return됨

 

#include <iostream>
#include <list>
#include <unordered_map>
#include <utility>
#include <tuple>
#include <memory>
#include "gtest/gtest.h"

using namespace std;

struct PairHash
{
    template <class Key_1, class Key_2>
    std::size_t operator () (const std::pair<Key_1, Key_2> &p) const
    {
        return std::hash<Key_1>{}(p.first) ^ std::hash<Key_2>{}(p.second);
    }
};

template<typename Key_1, typename Key_2, typename Value>
class FifoCache
{
public:
    explicit FifoCache(size_t capacity) : capacity_(capacity)
    {
    }
    ~FifoCache(void)
    {
        ageList_.clear();
        map_.clear();
    }
    Value Push(const Key_1 k1, const Key_2 k2, const Value v)
    {
        Value victim = nullptr;
        if (ageList_.size() >= capacity_)
        {
            victim = _PopTheOldest();
        }

        _Push(k1, k2, v);

        return victim;
    }
    Value PopTheOldest(void)
    {
        if (!ageList_.size())
            return nullptr;

        return _PopTheOldest();
    }
    Value Remove(const Key_1 k1, const Key_2 k2)
    {
        return _Remove(k1, k2);
    }
    size_t GetSize(void) const
    {
        return ageList_.size();
    }
    size_t GetCapacity(void) const
    {
        return capacity_;
    }

private:
    void _Push(const Key_1 k1, const Key_2 k2, const Value v)
    {
        ageList_.push_back(std::make_tuple(k1, k2, v));
        map_.insert({std::make_pair(k1, k2), v});
    }
    Value _PopTheOldest(void)
    {
        auto itemPair = ageList_.front();
        ageList_.pop_front();
        map_.erase(std::make_pair(std::get<0>(itemPair), std::get<1>(itemPair)));
        return std::get<2>(itemPair);
    }
    Value _Remove(const Key_1 k1, const Key_2 k2)
    {
        Value v = nullptr;
        for (auto iter = ageList_.begin(); iter != ageList_.end(); ++iter)
        {
            if (std::get<0>(*iter) == k1 && std::get<1>(*iter) == k2)
            {
                v = std::get<2>(*iter);
                ageList_.erase(iter);
                break;
            }
        }
        map_.erase(std::make_pair(k1, k2));
        return v;
    }

    std::list<std::tuple<Key_1, Key_2, Value>> ageList_;
    std::unordered_map<std::pair<Key_1, Key_2>, Value, PairHash> map_;
    const size_t capacity_;
};

class Item
{
public:
    Item(const size_t i) : id(i) {}
    ~Item(void) = default;
    size_t GetId(void) const {
        return id;
    }
private:
    size_t id;
};

TEST(FifoCache, CheckCapacityAndSize)
{
    const size_t CACHE_SIZE = 5;
    FifoCache<int, int, std::shared_ptr<Item>> cache(CACHE_SIZE);

    EXPECT_EQ(cache.GetCapacity(), CACHE_SIZE);
    EXPECT_EQ(cache.GetSize(), 0);
}

TEST(FifoCache, AddSigleItem)
{
    const size_t CACHE_SIZE = 5;
    FifoCache<int, int, std::shared_ptr<Item>> cache(CACHE_SIZE);

    EXPECT_EQ(cache.Push(0, 0, std::make_shared<Item>(0)), nullptr);
    EXPECT_EQ(cache.GetSize(), 1);
}

TEST(FifoCache, AddMaximunItemsAndCheckReturn)
{
    const size_t CACHE_SIZE = 5;
    FifoCache<int, int, std::shared_ptr<Item>> cache(CACHE_SIZE);

    for (size_t i = 0; i < CACHE_SIZE; ++i)
    {
        EXPECT_EQ(cache.Push(0, 0, std::make_shared<Item>(i)), nullptr);
        EXPECT_EQ(cache.GetSize(), i + 1);
    }

    std::shared_ptr<Item> a = std::make_shared<Item>(CACHE_SIZE + 1);
    auto result = cache.Push(0, 0, a);
    EXPECT_EQ(result->GetId(), 0);

    std::shared_ptr<Item> b = std::make_shared<Item>(CACHE_SIZE + 2);
    result = cache.Push(0, 0, b);
    EXPECT_EQ(result->GetId(), 1);
}

TEST(FifoCache, PopTheOldestItem)
{
    const size_t CACHE_SIZE = 5;
    FifoCache<int, int, std::shared_ptr<Item>> cache(CACHE_SIZE);

    for (size_t i = 0; i < CACHE_SIZE - 2; ++i)
        EXPECT_EQ(cache.Push(0, 0, std::make_shared<Item>(i)), nullptr);
    EXPECT_EQ(cache.GetSize(), CACHE_SIZE - 2);

    auto result = cache.PopTheOldest();
    EXPECT_EQ(result->GetId(), 0);

    for (size_t i = 0; i < CACHE_SIZE - 2; ++i)
        EXPECT_EQ(cache.Push(0, 0, std::make_shared<Item>(i)), nullptr);
    EXPECT_EQ(cache.GetSize(), CACHE_SIZE);

    result = cache.PopTheOldest();
    EXPECT_EQ(result->GetId(), 1);
}

TEST(FifoCache, RemoveSpecificItem)
{
    const size_t CACHE_SIZE = 5;
    FifoCache<int, int, std::shared_ptr<Item>> cache(CACHE_SIZE);

    for (size_t i = 0; i < CACHE_SIZE; ++i)
        EXPECT_EQ(cache.Push(i, i, std::make_shared<Item>(i)), nullptr);
    EXPECT_EQ(cache.GetSize(), CACHE_SIZE);

    auto result = cache.Remove(1, 1);
    EXPECT_EQ(result->GetId(), 1);
    EXPECT_EQ(cache.GetSize(), CACHE_SIZE - 1);

    result = cache.Remove(1, 1);
    EXPECT_EQ(result, nullptr);
    EXPECT_EQ(cache.GetSize(), CACHE_SIZE - 1);

    result = cache.Remove(1, 2);
    EXPECT_EQ(result, nullptr);
    EXPECT_EQ(cache.GetSize(), CACHE_SIZE - 1);
}