xref: /third_party/skia/src/core/SkLRUCache.h (revision cb93a386) 
1/*
2 * Copyright 2016 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkLRUCache_DEFINED
9#define SkLRUCache_DEFINED
10
11#include "include/private/SkChecksum.h"
12#include "include/private/SkTHash.h"
13#include "src/core/SkTInternalLList.h"
14
15/**
16 * A generic LRU cache.
17 */
18template <typename K, typename V, typename HashK = SkGoodHash>
19class SkLRUCache : public SkNoncopyable {
20private:
21    struct Entry {
22        Entry(const K& key, V&& value)
23        : fKey(key)
24        , fValue(std::move(value)) {}
25
26        K fKey;
27        V fValue;
28
29        SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry);
30    };
31
32public:
33    explicit SkLRUCache(int maxCount)
34    : fMaxCount(maxCount) {}
35
36    ~SkLRUCache() {
37        Entry* node = fLRU.head();
38        while (node) {
39            fLRU.remove(node);
40            delete node;
41            node = fLRU.head();
42        }
43    }
44
45    V* find(const K& key) {
46        Entry** value = fMap.find(key);
47        if (!value) {
48            return nullptr;
49        }
50        Entry* entry = *value;
51        if (entry != fLRU.head()) {
52            fLRU.remove(entry);
53            fLRU.addToHead(entry);
54        } // else it's already at head position, don't need to do anything
55        return &entry->fValue;
56    }
57
58    V* insert(const K& key, V value) {
59        SkASSERT(!this->find(key));
60
61        Entry* entry = new Entry(key, std::move(value));
62        fMap.set(entry);
63        fLRU.addToHead(entry);
64        while (fMap.count() > fMaxCount) {
65            this->remove(fLRU.tail()->fKey);
66        }
67        return &entry->fValue;
68    }
69
70    V* insert_or_update(const K& key, V value) {
71        if (V* found = this->find(key)) {
72            *found = std::move(value);
73            return found;
74        } else {
75            return this->insert(key, std::move(value));
76        }
77    }
78
79    int count() {
80        return fMap.count();
81    }
82
83    template <typename Fn>  // f(K*, V*)
84    void foreach(Fn&& fn) {
85        typename SkTInternalLList<Entry>::Iter iter;
86        for (Entry* e = iter.init(fLRU, SkTInternalLList<Entry>::Iter::kHead_IterStart); e;
87             e = iter.next()) {
88            fn(&e->fKey, &e->fValue);
89        }
90    }
91
92    void reset() {
93        fMap.reset();
94        for (Entry* e = fLRU.head(); e; e = fLRU.head()) {
95            fLRU.remove(e);
96            delete e;
97        }
98    }
99
100private:
101    struct Traits {
102        static const K& GetKey(Entry* e) {
103            return e->fKey;
104        }
105
106        static uint32_t Hash(const K& k) {
107            return HashK()(k);
108        }
109    };
110
111    void remove(const K& key) {
112        Entry** value = fMap.find(key);
113        SkASSERT(value);
114        Entry* entry = *value;
115        SkASSERT(key == entry->fKey);
116        fMap.remove(key);
117        fLRU.remove(entry);
118        delete entry;
119    }
120
121    int                             fMaxCount;
122    SkTHashTable<Entry*, K, Traits> fMap;
123    SkTInternalLList<Entry>         fLRU;
124};
125
126#endif
127