Added SkLRUCache.h and converted GPU program cache to use it.

BUG=skia:

GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=4221

Change-Id: I7e4094c2f2a2ecc5909895a8a68b27047acdcbd0
Reviewed-on: https://skia-review.googlesource.com/4221
Commit-Queue: Ethan Nicholas <ethannicholas@google.com>
Reviewed-by: Mike Klein <mtklein@chromium.org>

1 files changed, 70 insertions, 0 deletions

diff --git a/tests/LRUCacheTest.cpp b/tests/LRUCacheTest.cpp
new file mode 100644
index 0000000000..6a65e4ac2d
--- /dev/null
+++ b/tests/LRUCacheTest.cpp
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkLRUCache.h"
+#include "Test.h"
+
+struct Value {
+    Value(int value, int* counter)
+    : fValue(value)
+    , fCounter(counter) {
+        (*fCounter)++;
+    }
+
+    ~Value() {
+        (*fCounter)--;
+    }
+
+    int fValue;
+    int* fCounter;
+};
+
+DEF_TEST(LRUCacheSequential, r) {
+    int instances = 0;
+    {
+        static const int kSize = 100;
+        SkLRUCache<int, std::unique_ptr<Value>> test(kSize);
+        for (int i = 1; i < kSize * 2; i++) {
+            REPORTER_ASSERT(r, !test.find(i));
+            test.insert(i, std::unique_ptr<Value>(new Value(i * i, &instances)));
+            REPORTER_ASSERT(r, test.find(i));
+            REPORTER_ASSERT(r, i * i == (*test.find(i))->fValue);
+            if (i > kSize) {
+                REPORTER_ASSERT(r, kSize == instances);
+                REPORTER_ASSERT(r, !test.find(i - kSize));
+            } else {
+                REPORTER_ASSERT(r, i == instances);
+            }
+            REPORTER_ASSERT(r, (int) test.count() == instances);
+        }
+    }
+    REPORTER_ASSERT(r, 0 == instances);
+}
+
+DEF_TEST(LRUCacheRandom, r) {
+    int instances = 0;
+    {
+        int seq[] = { 0, 1, 2, 3, 4, 1, 6, 2, 7, 5, 3, 2, 2, 3, 1, 7 };
+        int expected[] = { 7, 1, 3, 2, 5 };
+        static const int kSize = 5;
+        SkLRUCache<int, std::unique_ptr<Value>> test(kSize);
+        for (int i = 0; i < (int) (sizeof(seq) / sizeof(int)); i++) {
+            int k = seq[i];
+            if (!test.find(k)) {
+                test.insert(k, std::unique_ptr<Value>(new Value(k, &instances)));
+            }
+        }
+        REPORTER_ASSERT(r, kSize == instances);
+        REPORTER_ASSERT(r, kSize == test.count());
+        for (int i = 0; i < kSize; i++) {
+            int k = expected[i];
+            REPORTER_ASSERT(r, test.find(k));
+            REPORTER_ASSERT(r, k == (*test.find(k))->fValue);
+        }
+    }
+    REPORTER_ASSERT(r, 0 == instances);
+}