11b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas/* 21b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas * Copyright 2016 Google Inc. 31b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas * 41b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas * Use of this source code is governed by a BSD-style license that can be 51b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas * found in the LICENSE file. 61b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas */ 71b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 81b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#include "SkLRUCache.h" 91b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#include "Test.h" 101b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 111b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholasstruct Value { 121b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Value(int value, int* counter) 131b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas : fValue(value) 141b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas , fCounter(counter) { 151b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas (*fCounter)++; 161b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 171b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 181b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas ~Value() { 191b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas (*fCounter)--; 201b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 211b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 221b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int fValue; 231b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int* fCounter; 241b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas}; 251b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 261b9924ffb7602fd6871359aee0a9660cefbaa812Ethan NicholasDEF_TEST(LRUCacheSequential, r) { 271b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int instances = 0; 281b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas { 291b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas static const int kSize = 100; 301b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas SkLRUCache<int, std::unique_ptr<Value>> test(kSize); 311b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas for (int i = 1; i < kSize * 2; i++) { 321b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, !test.find(i)); 331b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas test.insert(i, std::unique_ptr<Value>(new Value(i * i, &instances))); 341b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, test.find(i)); 351b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, i * i == (*test.find(i))->fValue); 361b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas if (i > kSize) { 371b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, kSize == instances); 381b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, !test.find(i - kSize)); 391b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } else { 401b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, i == instances); 411b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 421b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, (int) test.count() == instances); 431b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 441b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 451b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, 0 == instances); 461b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas} 471b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 481b9924ffb7602fd6871359aee0a9660cefbaa812Ethan NicholasDEF_TEST(LRUCacheRandom, r) { 491b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int instances = 0; 501b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas { 511b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int seq[] = { 0, 1, 2, 3, 4, 1, 6, 2, 7, 5, 3, 2, 2, 3, 1, 7 }; 521b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int expected[] = { 7, 1, 3, 2, 5 }; 531b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas static const int kSize = 5; 541b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas SkLRUCache<int, std::unique_ptr<Value>> test(kSize); 551b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas for (int i = 0; i < (int) (sizeof(seq) / sizeof(int)); i++) { 561b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int k = seq[i]; 571b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas if (!test.find(k)) { 581b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas test.insert(k, std::unique_ptr<Value>(new Value(k, &instances))); 591b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 601b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 611b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, kSize == instances); 621b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, kSize == test.count()); 631b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas for (int i = 0; i < kSize; i++) { 641b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int k = expected[i]; 651b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, test.find(k)); 661b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, k == (*test.find(k))->fValue); 671b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 681b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 691b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas REPORTER_ASSERT(r, 0 == instances); 701b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas} 71