Quelle TestSmallArrayLRUCache.cpp Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "gtest/gtest.h"

#include "mozilla/SmallArrayLRUCache.h"

#include <algorithm>
#include <cstring>
#include <utility>

using Key = unsigned;

struct Value {
  Value() : m(unsigned(-1)) {}
  explicit Value(unsigned a) : m(a) {}

  bool operator==(const Value& aOther) const { return m == aOther.m; }
  bool operator!=(const Value& aOther) const { return m != aOther.m; }

  unsigned m;
};

constexpr static unsigned CacheSize = 8;

using TestCache = mozilla::SmallArrayLRUCache<Key, Value, CacheSize>;

// This struct embeds a given object type between two "guard" objects, to check
// if anything is written out of bounds.
template <typename T>
struct Boxed {
  constexpr static size_t GuardSize = std::max(sizeof(T), size_t(256));

  // A Guard is a character array with a pre-set content that can be checked for
  // unwanted changes.
  struct Guard {
    char mGuard[GuardSize];
    explicit Guard(char aValue) { memset(&mGuard, aValue, GuardSize); }
    void Check(char aValue) {
      for (const char& c : mGuard) {
        ASSERT_EQ(c, aValue);
      }
    }
  };

  Guard mGuardBefore;
  T mObject;
  Guard mGuardAfter;

  template <typename... Ts>
  explicit Boxed(Ts&&... aTs)
      : mGuardBefore(0x5a),
        mObject(std::forward<Ts>(aTs)...),
        mGuardAfter(0xa5) {
    Check();
  }

  ~Boxed() { Check(); }

  T& Object() { return mObject; }
  const T& Object() const { return mObject; }

  void Check() {
    mGuardBefore.Check(0x5a);
    mGuardAfter.Check(0xa5);
  }
};

TEST(SmallArrayLRUCache, FetchOrAdd_KeysFitInCache)
{
  // We're going to add-or-fetch between 1 and CacheSize keys, so they all fit
  // in the cache.
  for (Key keys = 1; keys <= CacheSize; ++keys) {
    Boxed<TestCache> boxedCache;
    TestCache& cache = boxedCache.Object();
    for (Key i = 0; i < keys; ++i) {
      bool valueFunctionCalled = false;
      Value v = cache.FetchOrAdd(i, [&]() {
        valueFunctionCalled = true;
        return Value{i};
      });
      ASSERT_EQ(v, Value{i});
      ASSERT_TRUE(valueFunctionCalled);
      boxedCache.Check();
    }

    // Fetching any key should never call the value function.
    for (Key i = 0; i < CacheSize * 3; ++i) {
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_FALSE(valueFunctionCalled);
        boxedCache.Check();
      }
      // Fetching the same key again will never call the function value.
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_FALSE(valueFunctionCalled);
        boxedCache.Check();
      }
    }
  }
}

TEST(SmallArrayLRUCache, Add_FetchOrAdd_KeysFitInCache)
{
  // We're going to add between 1 and CacheSize keys, so they all fit in the
  // cache.
  for (Key keys = 1; keys <= CacheSize; ++keys) {
    Boxed<TestCache> boxedCache;
    TestCache& cache = boxedCache.Object();
    for (Key i = 0; i < keys; ++i) {
      cache.Add(i, Value{i});
      boxedCache.Check();
    }

    // Fetching any key should never call the value function.
    for (Key i = 0; i < CacheSize * 3; ++i) {
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_FALSE(valueFunctionCalled);
        boxedCache.Check();
      }
      // Fetching the same key again will never call the function value.
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_FALSE(valueFunctionCalled);
        boxedCache.Check();
      }
    }
  }
}

TEST(SmallArrayLRUCache, FetchOrAdd_KeysDoNotFitInCache)
{
  // We're going to add-or-fetch strictly more than CacheSize keys, so they
  // cannot fit in the cache, only the last `CacheSize` ones are kept.
  for (Key keys = CacheSize + 1; keys <= CacheSize * 2; ++keys) {
    Boxed<TestCache> boxedCache;
    TestCache& cache = boxedCache.Object();
    for (Key i = 0; i < keys; ++i) {
      bool valueFunctionCalled = false;
      Value v = cache.FetchOrAdd(i, [&]() {
        valueFunctionCalled = true;
        return Value{i};
      });
      ASSERT_EQ(v, Value{i});
      ASSERT_TRUE(valueFunctionCalled);
      boxedCache.Check();
    }

    // Fetching keys from 0 should always call the function value:
    // - 0 is the oldest key, it must have been pushed out when `CacheSize`
    //   was added.
    // - Once we've fetched 0, it's pushed out the old (smallest) key.
    // Etc.
    for (Key i = 0; i < CacheSize * 3; ++i) {
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_TRUE(valueFunctionCalled);
        boxedCache.Check();
      }
      // Fetching the same key again will never call the function value.
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_FALSE(valueFunctionCalled);
        boxedCache.Check();
      }
    }
  }
}

TEST(SmallArrayLRUCache, Add_FetchOrAdd_KeysDoNotFitInCache)
{
  // We're going to add strictly more than CacheSize keys, so they cannot fit in
  // the cache, only the last `CacheSize` ones are kept.
  for (Key keys = CacheSize + 1; keys <= CacheSize * 2; ++keys) {
    Boxed<TestCache> boxedCache;
    TestCache& cache = boxedCache.Object();
    for (Key i = 0; i < keys; ++i) {
      cache.Add(i, Value{i});
      boxedCache.Check();
    }

    // Fetching keys from 0 should always call the function value:
    // - 0 is the oldest key, it must have been pushed out when `CacheSize`
    //   was added.
    // - Once we've fetched 0, it's pushed out the old (smallest) key.
    // Etc.
    for (Key i = 0; i < CacheSize * 3; ++i) {
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_TRUE(valueFunctionCalled);
        boxedCache.Check();
      }
      // Fetching the same key again will never call the function value.
      {
        bool valueFunctionCalled = false;
        Value v = cache.FetchOrAdd(i % keys, [&]() {
          valueFunctionCalled = true;
          return Value{i % keys};
        });
        ASSERT_EQ(v, Value{i % keys});
        ASSERT_FALSE(valueFunctionCalled);
        boxedCache.Check();
      }
    }
  }
}

TEST(SmallArrayLRUCache, Clear)
{
  Boxed<TestCache> boxedCache;
  TestCache& cache = boxedCache.Object();

  // First fetch will always call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_TRUE(valueFunctionCalled);
    boxedCache.Check();
  }

  // Second fetch will never call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_FALSE(valueFunctionCalled);
    boxedCache.Check();
  }

  cache.Clear();

  // After Clear(), first fetch will always call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_TRUE(valueFunctionCalled);
    boxedCache.Check();
  }

  // Next fetch will never call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_FALSE(valueFunctionCalled);
    boxedCache.Check();
  }
}

TEST(SmallArrayLRUCache, Shutdown)
{
  Boxed<TestCache> boxedCache;
  TestCache& cache = boxedCache.Object();

  // First fetch will always call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_TRUE(valueFunctionCalled);
    boxedCache.Check();
  }

  // Second fetch will never call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_FALSE(valueFunctionCalled);
    boxedCache.Check();
  }

  cache.Shutdown();

  // After Shutdown(), any fetch will always call the function value.
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_TRUE(valueFunctionCalled);
    boxedCache.Check();
  }
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_TRUE(valueFunctionCalled);
    boxedCache.Check();
  }
  cache.Add(42, Value{4242});
  boxedCache.Check();
  {
    bool valueFunctionCalled = false;
    Value v = cache.FetchOrAdd(42, [&]() {
      valueFunctionCalled = true;
      return Value{4242};
    });
    ASSERT_EQ(v, Value{4242});
    ASSERT_TRUE(valueFunctionCalled);
    boxedCache.Check();
  }
}

quality89%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.