altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename > Struct Template Reference

time-based LFRU cache. More...

Detailed Description

template<typename Key, typename Value, size_t Size, size_t TimeWindow = 10 * 60, typename = typename std::enable_if<(Size <= 50)>::type>
struct altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename >

if all cache items are newer than TimeWindow min, evict less frequently used element. otherwise, evict oldest item, with lowest frequency.

has O(Size) complexity, thus works best for caches with small number of keys

Definition at line 29 of file small_lfru_cache.hpp.

#include <small_lfru_cache.hpp>

Collaboration diagram for altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename >:

Public Member Functions
std::shared_ptr< Value >	getOrDefault (Key key, std::function< std::shared_ptr< Value >()> factory)
void	clear ()
void	insert (Key key, std::shared_ptr< Value > value)
bool	get (const Key &key, std::shared_ptr< Value > &out)

Member Function Documentation

clear()

template<typename Key , typename Value , size_t Size, size_t TimeWindow = 10 * 60, typename = typename std::enable_if<(Size <= 50)>::type>

void altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename >::clear ( )

inline

Definition at line 55 of file small_lfru_cache.hpp.

               {
    size_ = 0;
    for (auto& i : container_) {
      i.clear();
    }
  }

get()

template<typename Key , typename Value , size_t Size, size_t TimeWindow = 10 * 60, typename = typename std::enable_if<(Size <= 50)>::type>

bool altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename >::get ( const Key &  key, std::shared_ptr< Value > &  out  )

inline

Definition at line 108 of file small_lfru_cache.hpp.

                                                      {
    // search for key
    auto begin = container_.begin();
    auto end = container_.begin() + size_;
    auto it = std::find_if(
        begin, end, [&key](const Item& i) { return i.key == key; });
    if (it == end) {
      // key not found
      return false;
    }
 
    it->frequency++;
    it->lastAccessed = currentTimestamp4();
 
    // return result
    out = it->value;
 
    return true;
  }

getOrDefault()

template<typename Key , typename Value , size_t Size, size_t TimeWindow = 10 * 60, typename = typename std::enable_if<(Size <= 50)>::type>

std::shared_ptr< Value > altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename >::getOrDefault ( Key  key, std::function< std::shared_ptr< Value >()>  factory  )

inline

Definition at line 44 of file small_lfru_cache.hpp.

                                                            {
    std::shared_ptr<Value> value;
    if (!get(key, value)) {
      value = factory();
      insert(key, value);
    }
 
    return value;
  }

insert()

template<typename Key , typename Value , size_t Size, size_t TimeWindow = 10 * 60, typename = typename std::enable_if<(Size <= 50)>::type>

void altintegration::cache::SmallLFRUCache< Key, Value, Size, TimeWindow, typename >::insert ( Key  key, std::shared_ptr< Value >  value  )

inline

Definition at line 62 of file small_lfru_cache.hpp.

                                                   {
    auto current = currentTimestamp4();
 
    if (size_ < Size) {
      // cache can accept new elements
      auto& it = container_[size_++];
      it.frequency = 0;
      it.key = key;
      it.value = std::move(value);
      it.lastAccessed = current;
      return;
    }
 
    // it's time to evict someone
    auto begin = container_.begin();
    auto end = container_.end();
    // iterator to least frequency item
    auto min = begin;
    // iterator to least recently used item
    auto leastRecent = begin;
    for (auto it = begin; it != end; ++it) {
      if (it->frequency < min->frequency) {
        min = it;
      }
 
      if (it->lastAccessed < leastRecent->lastAccessed ||
          (it->lastAccessed == leastRecent->lastAccessed &&
           it->frequency < leastRecent->frequency)) {
        leastRecent = it;
      }
    }
 
    // by default, use LFU policy and evict element with min frequency
    auto evict = min;
    if (leastRecent->lastAccessed <= current - TimeWindow) {
      // if least recently element is not used in TimeWindow sec, evict it
      evict = leastRecent;
    }
 
    // do evict
    evict->key = key;
    evict->frequency = 0;
    evict->value = std::move(value);
    evict->lastAccessed = current;
  }

---

The documentation for this struct was generated from the following file:

• include/veriblock/pop/cache/small_lfru_cache.hpp