xref: /haiku/headers/private/shared/LRUCache.h (revision 553f3f2309e87d95345220463fa865d5fd8cf28d)
1 /*
2  * Copyright 2020, Andrew Lindesay <apl@lindesay.co.nz>.
3  * All rights reserved. Distributed under the terms of the MIT License.
4  */
5 #ifndef LRU_CACHE_H
6 #define LRU_CACHE_H
7 
8 
9 #include <HashMap.h>
10 
11 
12 namespace BPrivate {
13 
14 
15 template<typename Key, typename Value>
16 class LRUOrderingNode {
17 private:
18 	typedef LRUOrderingNode<Key, Value> LRUNode;
19 
20 public:
21 	LRUOrderingNode()
22 		:
23 		fKey(),
24 		fValue(),
25 		fOlder(NULL),
26 		fNewer(NULL)
27 	{
28 	}
29 
30 	LRUOrderingNode(const Key& key, const Value& value)
31 		:
32 		fKey(key),
33 		fValue(value),
34 		fOlder(NULL),
35 		fNewer(NULL)
36 	{
37 	}
38 
39 	Key						fKey;
40 	Value					fValue;
41 	LRUNode*				fOlder;
42 	LRUNode*				fNewer;
43 };
44 
45 
46 /*!	\brief This is a hash map that maintains a limited number of entries.  Once
47 	this number of entries has been exceeded then it will start to discard
48 	entries.  The first entries to be discarded are the ones that are the least
49 	recently used; hence the prefix "LRU".
50 */
51 
52 template<typename Key, typename Value>
53 class LRUCache {
54 public:
55 	typedef LRUOrderingNode<Key, Value> LRUNode;
56 
57 	LRUCache(int32 limit)
58 		:
59 		fNewestNode(NULL),
60 		fOldestNode(NULL),
61 		fLimit(limit)
62 	{
63 		if (fLimit < 0)
64 			fLimit = 0;
65 	}
66 
67 	~LRUCache()
68 	{
69 		Clear();
70 	}
71 
72 	status_t InitCheck() const
73 	{
74 		return fMap.InitCheck();
75 	}
76 
77 	status_t Put(const Key& key, const Value& value)
78 	{
79 		LRUNode* node = fMap.Get(key);
80 
81 		if (node != NULL) {
82 			if (node->fValue != value) {
83 				node->fValue = value;
84 				_DisconnectNodeAndMakeNewest(node);
85 			}
86 		} else {
87 			node = new(std::nothrow) LRUNode(key, value);
88 			if (node == NULL)
89 				return B_NO_MEMORY;
90 			status_t result = fMap.Put(key, node);
91 			if (result != B_OK) {
92 				delete node;
93 				return result;
94 			}
95 			_SetNewestNode(node);
96 			_PurgeExcess();
97 		}
98 
99 		return B_OK;
100 	}
101 
102 	Value Remove(const Key& key)
103 	{
104 		LRUNode* node = fMap.Get(key);
105 		if (node != NULL) {
106 			_DisconnectNode(node);
107 			Value result = node->fValue;
108 			fMap.Remove(key);
109 			delete node;
110 			return result;
111 		}
112 		return Value();
113 	}
114 
115 	void Clear()
116 	{
117 		fMap.Clear();
118 		LRUNode* node = fNewestNode;
119 		while (node != NULL) {
120 			LRUNode *next = node->fOlder;
121 			delete node;
122 			node = next;
123 		}
124 	}
125 
126 	Value Get(const Key& key)
127 	{
128 		LRUNode* node = fMap.Get(key);
129 		if (node != NULL) {
130 			_DisconnectNodeAndMakeNewest(node);
131 			return node->fValue;
132 		}
133 		return Value();
134 	}
135 
136 	bool ContainsKey(const Key& key) const
137 	{
138 		return fMap.ContainsKey(key);
139 	}
140 
141 	int32 Size() const
142 	{
143 		return fMap.Size();
144 	}
145 
146 private:
147 
148 	void _DisconnectNodeAndMakeNewest(LRUNode* node) {
149 		if (node != fNewestNode) {
150 			_DisconnectNode(node);
151 			node->fOlder = NULL;
152 			node->fNewer = NULL;
153 			_SetNewestNode(node);
154 		}
155 	}
156 
157 	void _DisconnectNode(LRUNode* node)
158 	{
159 		LRUNode *older = node->fOlder;
160 		LRUNode *newer = node->fNewer;
161 		if (newer != NULL)
162 			newer->fOlder = older;
163 		if (older != NULL)
164 			older->fNewer = newer;
165 		if (fNewestNode == node)
166 			fNewestNode = older;
167 		if (fOldestNode == node)
168 			fOldestNode = newer;
169 	}
170 
171 	void _SetNewestNode(LRUNode* node)
172 	{
173 		if (node != fNewestNode) {
174 			node->fOlder = fNewestNode;
175 			node->fNewer = NULL;
176 			if (fNewestNode != NULL)
177 				fNewestNode->fNewer = node;
178 			fNewestNode = node;
179 			if (fOldestNode == NULL)
180 				fOldestNode = node;
181 		}
182 	}
183 
184 	void _PurgeOldestNode()
185 	{
186 		if (fOldestNode == NULL)
187 			debugger("attempt to purge oldest node but there is none to purge");
188 		Remove(fOldestNode->fKey);
189 	}
190 
191 	void _PurgeExcess()
192 	{
193 		while(Size() > fLimit)
194 			_PurgeOldestNode();
195 	}
196 
197 protected:
198 	HashMap<Key, LRUNode*>	fMap;
199 	LRUNode*				fNewestNode;
200 	LRUNode*				fOldestNode;
201 
202 private:
203 	int32					fLimit;
204 };
205 
206 }; // namespace BPrivate
207 
208 using BPrivate::LRUCache;
209 
210 #endif // LRU_CACHE_H
211