Untitled

#pragma once

#include <vector>
#include <stdexcept>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <optional>

namespace shdb
{

template <class Key, class Value>
class ClockCache
{
private:
    enum FreeNext {
        FREENEXT_NOT_IN_BUFF = -1
    };

    struct CachedValue {
        Value value;

        int nextFree;
        int clockTimes;

        bool isLocked;
    };

    struct BufferDescriptor {
        int firstFreeIndex;
        int lastFreeIndex;
    };

    BufferDescriptor bufferDescriptor;

    std::vector<CachedValue> buffer;
    std::unordered_map<Key, int> hashTable;

    using HTABIt = typename std::unordered_map<Key, int>::iterator;

public:
    explicit ClockCache(const std::vector<Value>& free_values)
        : bufferDescriptor(0, free_values.size() - 1)
    {
        std::vector<CachedValue> _buffer(free_values.size());

        int last_index = free_values.size() - 1;
        int idx = 0;
        for (auto& value: free_values)
        {
            _buffer[idx] = CachedValue{value, nextFreeIndx(last_index, idx), 0, false};
            idx++;
        }
        buffer = _buffer;
    }

    std::pair<bool, Value> find(const Key & key)
    {
        std::pair<bool, Value> lookup_result;
        lookup_result.first = false;

        if (HTABIt it = hashTable.find(key); it != hashTable.end())
        {
            CachedValue& cached = buffer[it->second];
            if (cached.clockTimes < 5) {
                cached.clockTimes++;
            }

            lookup_result.first = true;
            lookup_result.second = cached.value;
        }
        return lookup_result;
    }

    Value put(const Key & key)
    {
        if (auto lookup = find(key); lookup.first)
        {
            return lookup.second;
        }

        int potentialFreeIndex = bufferDescriptor.firstFreeIndex;
        if (potentialFreeIndex != FREENEXT_NOT_IN_BUFF)
        {
            return insertByIndex(potentialFreeIndex, key);
        }

        bool clear = false;
        for (int clock = 0; clock < 5; ++clock && clear) {
            for (auto it = hashTable.cbegin(); it != hashTable.cend();)
            {
                CachedValue& cachedValue = buffer[it->second];
                if (cachedValue.clockTimes == 0 && !cachedValue.isLocked)
                {
                    int index = it->second;
                    auto cur = it++;

                    hashTable.erase(cur);

                    buffer[bufferDescriptor.lastFreeIndex].nextFree = index;

                    if (bufferDescriptor.firstFreeIndex == FREENEXT_NOT_IN_BUFF) {
                        bufferDescriptor.firstFreeIndex = bufferDescriptor.lastFreeIndex = index;
                    } else {
                        cachedValue.nextFree = FREENEXT_NOT_IN_BUFF;
                        bufferDescriptor.lastFreeIndex = index;
                    }
                    clear = true;
                } else
                {
                    cachedValue.clockTimes--;
                    it++;
                }
            }
        }
        put(key);
    }

    void lock(const Key & key)
    {
        if (HTABIt it = hashTable.find(key); it != hashTable.end())
        {
            CachedValue& cached = buffer[it->second];
            cached.isLocked = true;
        }
    }

    void unlock(const Key & key)
    {
        if (HTABIt it = hashTable.find(key); it != hashTable.end())
        {
            CachedValue& cached = buffer[it->second];
            cached.isLocked = false;
        }
    }

private:
    Value insertByIndex(int idx, const Key & key)
    {
        CachedValue& cachedValue = buffer[idx];

        bufferDescriptor.firstFreeIndex = cachedValue.nextFree;
        hashTable[key] = idx;

        cachedValue.clockTimes++;
        return cachedValue.value;
    }

    int nextFreeIndx(int max_buffer_index, int cur_indx)
    {
        if (max_buffer_index == cur_indx)
        {
            return FREENEXT_NOT_IN_BUFF;
        }
        return cur_indx + 1;
    }
};
}