Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / TinyLRUCache.h
1 /*
2  * Copyright (C) 2010, 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef TinyLRUCache_h
27 #define TinyLRUCache_h
28
29 #include <wtf/NeverDestroyed.h>
30 #include <wtf/Vector.h>
31
32 namespace WTF {
33
34 template<typename KeyType, typename ValueType>
35 struct TinyLRUCachePolicy {
36     static bool isKeyNull(const KeyType&) { return false; }
37     static ValueType createValueForNullKey() { return { }; }
38     static ValueType createValueForKey(const KeyType&) { return { }; }
39 };
40
41 template<typename KeyType, typename ValueType, size_t capacity = 4, typename Policy = TinyLRUCachePolicy<KeyType, ValueType>>
42 class TinyLRUCache {
43 public:
44     const ValueType& get(const KeyType& key)
45     {
46         if (Policy::isKeyNull(key)) {
47             static NeverDestroyed<ValueType> valueForNull = Policy::createValueForNullKey();
48             return valueForNull;
49         }
50
51         for (size_t i = 0; i < m_cache.size(); ++i) {
52             if (m_cache[i].first != key)
53                 continue;
54
55             if (i == m_cache.size() - 1)
56                 return m_cache[i].second;
57
58             // If the entry is not the last one, move it to the end of the cache.
59             Entry entry = WTFMove(m_cache[i]);
60             m_cache.remove(i);
61             m_cache.append(WTFMove(entry));
62             return m_cache[m_cache.size() - 1].second;
63         }
64
65         // m_cache[0] is the LRU entry, so remove it.
66         if (m_cache.size() == capacity)
67             m_cache.remove(0);
68
69         m_cache.append(std::make_pair(key, Policy::createValueForKey(key)));
70         return m_cache.last().second;
71     }
72
73 private:
74     typedef std::pair<KeyType, ValueType> Entry;
75     typedef Vector<Entry, capacity> Cache;
76     Cache m_cache;
77 };
78
79 }
80
81 using WTF::TinyLRUCache;
82 using WTF::TinyLRUCachePolicy;
83
84 #endif // TinyLRUCache_h