static_size_hashed_cache.h

Go to the documentation of this file.

#pragma once
 
#include <array>
#include <cstddef>
#include <stdexcept>
 
#include "api/util/debug.h"
 
template <typename V, size_t N = 1000> class StaticSizeHashedCache {
public:
  StaticSizeHashedCache() { _occupied.fill(false); }
 
  void add(long int key, V value) {
    db<StaticSizeHashedCache>(TRC) << "[StaticSizeHashedCache] add called for key: " << key << "\n";
    size_t index = hash(key);
 
    for (size_t i = 0; i < N; ++i) {
      size_t current_index = (index + i) % N;
      if (!_occupied[current_index] || _keys[current_index] == key) {
        _keys[current_index] = key;
        _values[current_index] = value;
        _occupied[current_index] = true;
        return;
      }
    }
 
    throw std::runtime_error("Cache is full");
  }
 
  V *get(long int key) {
    db<StaticSizeHashedCache>(TRC) << "[StaticSizeHashedCache] get called for key: " << key << "\n";
    size_t index = hash(key);
 
    for (size_t i = 0; i < N; ++i) {
      size_t current_index = (index + i) % N;
      if (!_occupied[current_index]) {
        return nullptr;
      }
      if (_keys[current_index] == key) {
        return &_values[current_index];
      }
    }
 
    return nullptr;
  }
 
  bool contains(long int key) const {
    db<StaticSizeHashedCache>(TRC) << "[StaticSizeHashedCache] contains called for key: " << key << "\n";
    size_t index = hash(key);
 
    for (size_t i = 0; i < N; ++i) {
      size_t current_index = (index + i) % N;
      if (!_occupied[current_index]) {
        return false;
      }
      if (_keys[current_index] == key) {
        return true;
      }
    }
 
    return false;
  }
 
  template <typename F>
  void for_each(F&& fn) {
    for (size_t i = 0; i < N; ++i) {
      if (_occupied[i]) {
        fn(_keys[i], _values[i]);
      }
    }
  }
 
private:
  size_t hash(long int key) const {
    return static_cast<unsigned long long>(key) % N;
  }
 
  std::array<long int, N> _keys;
  std::array<V, N> _values;
  std::array<bool, N> _occupied;
};