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 "System/Math.hpp"
19 
20 namespace sw
21 {
22 	template<class Key, class Data>
23 	class LRUCache
24 	{
25 	public:
26 		LRUCache(int n);
27 
28 		~LRUCache();
29 
30 		Data *query(const Key &key) const;
31 		Data *add(const Key &key, Data *data);
32 
getSize()33 		int getSize() {return size;}
getKey(int i)34 		Key &getKey(int i) {return key[i];}
35 
36 	private:
37 		int size;
38 		int mask;
39 		int top;
40 		int fill;
41 
42 		Key *key;
43 		Key **ref;
44 		Data **data;
45 	};
46 }
47 
48 namespace sw
49 {
50 	template<class Key, class Data>
LRUCache(int n)51 	LRUCache<Key, Data>::LRUCache(int n)
52 	{
53 		size = ceilPow2(n);
54 		mask = size - 1;
55 		top = 0;
56 		fill = 0;
57 
58 		key = new Key[size];
59 		ref = new Key*[size];
60 		data = new Data*[size];
61 
62 		for(int i = 0; i < size; i++)
63 		{
64 			data[i] = nullptr;
65 
66 			ref[i] = &key[i];
67 		}
68 	}
69 
70 	template<class Key, class Data>
~LRUCache()71 	LRUCache<Key, Data>::~LRUCache()
72 	{
73 		delete[] key;
74 		key = nullptr;
75 
76 		delete[] ref;
77 		ref = nullptr;
78 
79 		for(int i = 0; i < size; i++)
80 		{
81 			if(data[i])
82 			{
83 				data[i]->unbind();
84 				data[i] = nullptr;
85 			}
86 		}
87 
88 		delete[] data;
89 		data = nullptr;
90 	}
91 
92 	template<class Key, class Data>
query(const Key & key) const93 	Data *LRUCache<Key, Data>::query(const Key &key) const
94 	{
95 		for(int i = top; i > top - fill; i--)
96 		{
97 			int j = i & mask;
98 
99 			if(key == *ref[j])
100 			{
101 				Data *hit = data[j];
102 
103 				if(i != top)
104 				{
105 					// Move one up
106 					int k = (j + 1) & mask;
107 
108 					Data *swapD = data[k];
109 					data[k] = data[j];
110 					data[j] = swapD;
111 
112 					Key *swapK = ref[k];
113 					ref[k] = ref[j];
114 					ref[j] = swapK;
115 				}
116 
117 				return hit;
118 			}
119 		}
120 
121 		return nullptr;   // Not found
122 	}
123 
124 	template<class Key, class Data>
add(const Key & key,Data * data)125 	Data *LRUCache<Key, Data>::add(const Key &key, Data *data)
126 	{
127 		top = (top + 1) & mask;
128 		fill = fill + 1 < size ? fill + 1 : size;
129 
130 		*ref[top] = key;
131 
132 		data->bind();
133 
134 		if(this->data[top])
135 		{
136 			this->data[top]->unbind();
137 		}
138 
139 		this->data[top] = data;
140 
141 		return data;
142 	}
143 }
144 
145 #endif   // sw_LRUCache_hpp
146