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#ifndef SkLRUCache_DEFINED 91b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#define SkLRUCache_DEFINED 101b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 111b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#include "SkChecksum.h" 121b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#include "SkTHash.h" 131b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#include "SkTInternalLList.h" 141b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 151b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas/** 161b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas * A generic LRU cache. 171b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas */ 181b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholastemplate <typename K, typename V, typename HashK = SkGoodHash> 191b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholasclass SkLRUCache : public SkNoncopyable { 2087f340e52a1af24766659c63035331e8b0b6355fEthan Nicholasprivate: 2187f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas struct Entry { 2287f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas Entry(const K& key, V&& value) 2387f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas : fKey(key) 2487f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas , fValue(std::move(value)) {} 2587f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas 2687f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas K fKey; 2787f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas V fValue; 2887f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas 2987f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry); 3087f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas }; 3187f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas 321b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholaspublic: 331b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas explicit SkLRUCache(int maxCount) 341b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas : fMaxCount(maxCount) {} 351b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 361b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas ~SkLRUCache() { 371b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Entry* node = fLRU.head(); 381b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas while (node) { 391b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fLRU.remove(node); 401b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas delete node; 411b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas node = fLRU.head(); 421b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 431b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 441b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 451b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas V* find(const K& key) { 461b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Entry** value = fMap.find(key); 471b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas if (!value) { 481b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas return nullptr; 491b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 501b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Entry* entry = *value; 511b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas if (entry != fLRU.head()) { 521b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fLRU.remove(entry); 531b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fLRU.addToHead(entry); 541b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } // else it's already at head position, don't need to do anything 551b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas return &entry->fValue; 561b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 571b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 581b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas V* insert(const K& key, V value) { 591b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Entry* entry = new Entry(key, std::move(value)); 601b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fMap.set(entry); 611b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fLRU.addToHead(entry); 621b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas while (fMap.count() > fMaxCount) { 631b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas this->remove(fLRU.tail()->fKey); 641b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 651b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas return &entry->fValue; 661b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 671b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 681b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int count() { 691b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas return fMap.count(); 701b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 711b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 7287f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas template <typename Fn> // f(V*) 7387f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas void foreach(Fn&& fn) { 7487f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas typename SkTInternalLList<Entry>::Iter iter; 7587f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas for (Entry* e = iter.init(fLRU, SkTInternalLList<Entry>::Iter::kHead_IterStart); e; 7687f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas e = iter.next()) { 7787f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas fn(&e->fValue); 7887f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas } 7987f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas } 801b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 8187f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas void reset() { 8287f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas fMap.reset(); 8387f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas for (Entry* e = fLRU.head(); e; e = fLRU.head()) { 8487f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas fLRU.remove(e); 8587f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas delete e; 8687f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas } 8787f340e52a1af24766659c63035331e8b0b6355fEthan Nicholas } 881b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 8987f340e52a1af24766659c63035331e8b0b6355fEthan Nicholasprivate: 901b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas struct Traits { 911b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas static const K& GetKey(Entry* e) { 921b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas return e->fKey; 931b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 941b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 951b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas static uint32_t Hash(const K& k) { 961b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas return HashK()(k); 971b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 981b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas }; 991b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 1001b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas void remove(const K& key) { 1011b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Entry** value = fMap.find(key); 1021b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas SkASSERT(value); 1031b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas Entry* entry = *value; 1041b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas SkASSERT(key == entry->fKey); 1051b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fMap.remove(key); 1061b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas fLRU.remove(entry); 1071b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas delete entry; 1081b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas } 1091b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 1101b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas int fMaxCount; 1111b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas SkTHashTable<Entry*, K, Traits> fMap; 1121b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas SkTInternalLList<Entry> fLRU; 1131b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas}; 1141b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas 1151b9924ffb7602fd6871359aee0a9660cefbaa812Ethan Nicholas#endif 116