eviction_segmented_lru.h

#ifndef CACHEMERE_EVICTION_SEGMENTED_LRU_H
#define CACHEMERE_EVICTION_SEGMENTED_LRU_H
 
#include <list>
 
#include <absl/container/flat_hash_map.h>
 
#include "cachemere/item.h"
 
namespace cachemere::policy {
 
template<typename Key, typename KeyHash, typename Value> class EvictionSegmentedLRU
{
private:
    using KeyRef    = std::reference_wrapper<const Key>;
    using KeyRefIt  = typename std::list<KeyRef>::iterator;
    using KeyRefMap = absl::flat_hash_map<KeyRef, KeyRefIt, KeyHash, std::equal_to<Key>>;
 
public:
    using CacheItem = cachemere::Item<Value>;
 
    //         evicted.
    class VictimIterator
    {
    public:
        using KeyRefReverseIt = typename std::list<KeyRef>::const_reverse_iterator;
 
        VictimIterator(const KeyRefReverseIt& probation_iterator, const KeyRefReverseIt& probation_end_iterator, const KeyRefReverseIt& protected_iterator);
 
        const Key&      operator*() const;
        VictimIterator& operator++();
        VictimIterator  operator++(int);
        bool            operator==(const VictimIterator& other) const;
        bool            operator!=(const VictimIterator& other) const;
 
    private:
        KeyRefReverseIt m_probation_iterator;
        KeyRefReverseIt m_probation_end_iterator;
        KeyRefReverseIt m_protected_iterator;
        bool            m_done_with_probation;
    };
 
    void clear();
 
    void set_protected_segment_size(size_t size);
 
    void on_insert(const Key& key, const CacheItem& item);
 
    void on_update(const Key& key, const CacheItem& old_item, const CacheItem& new_item);
 
    void on_cache_hit(const Key& key, const CacheItem& item);
 
    void on_evict(const Key& key, const CacheItem& item);
 
    [[nodiscard]] VictimIterator victim_begin() const;
 
    [[nodiscard]] VictimIterator victim_end() const;
 
private:
    size_t m_protected_segment_size;
 
    std::list<KeyRef> m_probation_list;
    KeyRefMap         m_probation_nodes;
 
    std::list<KeyRef> m_protected_list;
    KeyRefMap         m_protected_nodes;
 
    bool move_to_protected(const Key& key);
    bool pop_to_probation();
};
 
}  // namespace cachemere::policy
 
#include "eviction_segmented_lru.hpp"
 
#endif