Class KeyAge

libs/base/lru_cache.hpp:77–169

  /// all keys of |m_ageToKey| should be values of |m_ageToKey|.
  /// \note Ages should be unique for all keys.
  class KeyAge
  {
    template <typename K, typename V>
    friend class LruCacheKeyAgeTest;

  public:
    void Clear()
    {
      m_age = 0;
      m_ageToKey.clear();
      m_keyToAge.clear();
    }

    /// \brief Increments |m_age| and insert key to |m_ageToKey| and |m_keyToAge|.
    /// \note This method should be used only if there's no |key| in |m_ageToKey| and |m_keyToAge|.
    void InsertKey(Key const & key)
    {
      ++m_age;
      m_ageToKey[m_age] = key;
      m_keyToAge[key] = m_age;
    }

    /// \brief Increments |m_age| and updates key age in |m_ageToKey| and |m_keyToAge|.
    /// \note This method should be used only if there's |key| in |m_ageToKey| and |m_keyToAge|.
    void UpdateAge(Key const & key)
    {
      ++m_age;
      auto keyToAgeIt = m_keyToAge.find(key);
      CHECK(keyToAgeIt != m_keyToAge.end(), ());
      // Removing former age.
      size_t const removed = m_ageToKey.erase(keyToAgeIt->second);
      CHECK_EQUAL(removed, 1, ());
      // Putting new age.
      m_ageToKey[m_age] = key;
      keyToAgeIt->second = m_age;
    }

    /// \returns Least recently used key without updating the age.
    /// \note |m_ageToKey| and |m_keyToAge| shouldn't be empty.
    Key const & GetLruKey() const
    {
      CHECK(!m_ageToKey.empty(), ());
      // The smaller age the older item.
      return m_ageToKey.cbegin()->second;
    }

    void RemoveLru()
    {
      Key const & lru = GetLruKey();
      size_t const removed = m_keyToAge.erase(lru);
      CHECK_EQUAL(removed, 1, ());
      m_ageToKey.erase(m_ageToKey.begin());
    }

    /// \brief Checks for coherence class params.
    /// \note It's a time consumption method and should be called for tests only.
    bool IsValidForTesting() const
    {