1// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef sw_LRUCache_hpp
16#define sw_LRUCache_hpp
17
18#include "Common/Math.hpp"
19
20#include <cstring>
21#include <type_traits>
22
23namespace sw
24{
25 template<class Key, class Data>
26 class LRUCache
27 {
28 public:
29 LRUCache(int n);
30
31 ~LRUCache();
32
33 Data query(const Key &key) const;
34 Data add(const Key &key, const Data &data);
35
36 int getSize() {return size;}
37 Key &getKey(int i) {return key[i];}
38
39 private:
40 int size;
41 int mask;
42 int top;
43 int fill;
44
45 Key *key;
46 Key **ref;
47 Data *data;
48 };
49
50 // Helper class for clearing the memory of objects at construction.
51 // Useful as the first base class of cache keys which may contain padding bytes or bits otherwise left uninitialized.
52 template<class T>
53 struct Memset
54 {
55 Memset(T *object, int val)
56 {
57 static_assert(std::is_base_of<Memset<T>, T>::value, "Memset<T> must only clear the memory of a type of which it is a base class");
58
59 // GCC 8+ warns that
60 // "‘void* memset(void*, int, size_t)’ clearing an object of non-trivial type ‘T’;
61 // use assignment or value-initialization instead [-Werror=class-memaccess]"
62 // This is benign iff it happens before any of the base or member constructrs are called.
63 #if defined(__GNUC__) && (__GNUC__ >= 8)
64 #pragma GCC diagnostic push
65 #pragma GCC diagnostic ignored "-Wclass-memaccess"
66 #endif
67
68 memset(object, 0, sizeof(T));
69
70 #if defined(__GNUC__) && (__GNUC__ >= 8)
71 #pragma GCC diagnostic pop
72 #endif
73 }
74 };
75
76 // Traits-like helper class for checking if objects can be compared using memcmp().
77 // Useful for statically asserting if a cache key can implement operator==() with memcmp().
78 template<typename T>
79 struct is_memcmparable
80 {
81 // std::is_trivially_copyable is not available in older GCC versions.
82 #if !defined(__GNUC__) || __GNUC__ > 5
83 static const bool value = std::is_trivially_copyable<T>::value;
84 #else
85 // At least check it doesn't have virtual methods.
86 static const bool value = !std::is_polymorphic<T>::value;
87 #endif
88 };
89}
90
91namespace sw
92{
93 template<class Key, class Data>
94 LRUCache<Key, Data>::LRUCache(int n)
95 {
96 size = ceilPow2(n);
97 mask = size - 1;
98 top = 0;
99 fill = 0;
100
101 key = new Key[size];
102 ref = new Key*[size];
103 data = new Data[size];
104
105 for(int i = 0; i < size; i++)
106 {
107 ref[i] = &key[i];
108 }
109 }
110
111 template<class Key, class Data>
112 LRUCache<Key, Data>::~LRUCache()
113 {
114 delete[] key;
115 key = nullptr;
116
117 delete[] ref;
118 ref = nullptr;
119
120 delete[] data;
121 data = nullptr;
122 }
123
124 template<class Key, class Data>
125 Data LRUCache<Key, Data>::query(const Key &key) const
126 {
127 for(int i = top; i > top - fill; i--)
128 {
129 int j = i & mask;
130
131 if(key == *ref[j])
132 {
133 Data hit = data[j];
134
135 if(i != top)
136 {
137 // Move one up
138 int k = (j + 1) & mask;
139
140 Data swapD = data[k];
141 data[k] = data[j];
142 data[j] = swapD;
143
144 Key *swapK = ref[k];
145 ref[k] = ref[j];
146 ref[j] = swapK;
147 }
148
149 return hit;
150 }
151 }
152
153 return nullptr; // Not found
154 }
155
156 template<class Key, class Data>
157 Data LRUCache<Key, Data>::add(const Key &key, const Data &data)
158 {
159 top = (top + 1) & mask;
160 fill = fill + 1 < size ? fill + 1 : size;
161
162 *ref[top] = key;
163 this->data[top] = data;
164
165 return data;
166 }
167}
168
169#endif // sw_LRUCache_hpp
170