LruCache.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef KERNEL_UTILITIES_LRUCACHE_H
#define KERNEL_UTILITIES_LRUCACHE_H
 
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/utility.h"
 
template <class K, class T, size_t Slots = 32>
class LruCache {
  static_assert(Slots >= 4, "At least four slots are needed for LruCache.");
 
 private:
  struct Slot {
    K key;
    T object;
    bool set = false;
  };
 
 public:
  LruCache() = default;
  virtual ~LruCache() = default;
 
  bool get(const K& key, T& object) {
    for (size_t i = 0; i < Slots; ++i) {
      if (!m_Slots[i].set) {
        continue;
      } else if (m_Slots[i].key != key) {
        continue;
      }
 
      object = m_Slots[i].object;
      ++m_Hits;
      return true;
    }
 
    ++m_Misses;
    return false;
  }
 
  void store(const K& key, const T& object) {
    for (size_t i = 0; i < Slots; ++i) {
      if (m_Slots[i].set && m_Slots[i].key == key) {
        pedigree_std::copy(&m_Slots[1], &m_Slots[0], i);
        m_Slots[0].key = key;
        m_Slots[0].object = object;
        return;
      }
    }
 
    pedigree_std::copy(&m_Slots[1], &m_Slots[0], Slots - 1);
    m_Slots[0].key = key;
    m_Slots[0].object = object;
    m_Slots[0].set = true;
  }
 
  size_t hits() const {
    return m_Hits;
  }
 
  size_t misses() const {
    return m_Misses;
  }
 
 private:
  Slot m_Slots[Slots];
 
  size_t m_Hits = 0;
  size_t m_Misses = 0;
};
 
#endif  // KERNEL_UTILITIES_LRUCACHE_H