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
20namespace 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
33		int getSize() {return size;}
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
48namespace sw
49{
50	template<class Key, class Data>
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>
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>
93	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>
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