eviction_gdsf.h

#ifndef CACHEMERE_EVICTION_GDSF
#define CACHEMERE_EVICTION_GDSF
 
#include <algorithm>
 
#include <absl/container/btree_map.h>
 
#include "cachemere/item.h"
#include "cachemere/policy/detail/counting_bloom_filter.h"
 
namespace cachemere::policy {
 
//          The cost must not exceed 2^64 and should ideally be quite a bit below this limit since the cost of the item is added to the
//          policy's internal 64-bit clock on every insertion.
template<typename Key, typename KeyHash, typename Value, typename Cost> class EvictionGDSF
{
private:
    using KeyRef = std::reference_wrapper<const Key>;
 
    struct PriorityEntry {
        PriorityEntry(KeyRef key, double coefficient);
 
        bool operator<(const PriorityEntry& other) const;
 
        KeyRef m_key;
        double m_h_coefficient;
    };
 
    using PrioritySet   = std::multiset<PriorityEntry>;
    using PrioritySetIt = typename PrioritySet::const_iterator;
 
public:
    using CacheItem = Item<Value>;
 
    class VictimIterator
    {
    public:
        VictimIterator(PrioritySetIt iterator);
 
        const Key&      operator*() const;
        VictimIterator& operator++();
        VictimIterator  operator++(int);
        bool            operator==(const VictimIterator& other) const;
        bool            operator!=(const VictimIterator& other) const;
 
    private:
        PrioritySetIt m_iterator;
    };
 
    void clear();
 
    void set_cardinality(uint32_t cardinality);
 
    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:
    using IteratorMap = absl::btree_map<KeyRef, PrioritySetIt, std::less<const Key>>;
 
    const static uint32_t                DEFAULT_CACHE_CARDINALITY = 2000;               // The expected cache cardinality, for the counting bloom filter.
    mutable Cost                         m_measure_cost;                                 // The functor to measure the cost metric of cached items.
    detail::CountingBloomFilter<KeyHash> m_frequency_sketch{DEFAULT_CACHE_CARDINALITY};  // TODO: Replace with a count-min sketch to get rid of cardinality
 
    PrioritySet m_priority_set;  // A multiset of keys sorted by H-coefficients in ascending order.
 
    IteratorMap m_iterator_map;  // A map of keys pointing to the corresponding iterator in the priority set. This is necessary because since PrioritySet uses
                                 // coefficients to compare items to one another, we can't test for key membership directly.
 
    uint64_t m_clock{0};
 
    [[nodiscard]] double get_h_coefficient(const Key& key, const CacheItem& item) const noexcept;
};
 
}  // namespace cachemere::policy
 
#include "eviction_gdsf.hpp"
 
#endif