1/*
2 * Copyright 2020-2021, 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
12namespace BPrivate {
13
14
15template<typename Key, typename Value>
16class LRUOrderingNode {
17private:
18	typedef LRUOrderingNode<Key, Value> LRUNode;
19
20public:
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
52template<typename Key, typename Value>
53class LRUCache {
54public:
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			// this will delete the objects in map which are the nodes in the
119			// linked list; for this reason don't delete them here as well
120			// because this will lead to a double-free of the object.
121		fNewestNode = NULL;
122		fOldestNode = NULL;
123	}
124
125	Value Get(const Key& key)
126	{
127		LRUNode* node = fMap.Get(key);
128		if (node != NULL) {
129			_DisconnectNodeAndMakeNewest(node);
130			return node->fValue;
131		}
132		return Value();
133	}
134
135	bool ContainsKey(const Key& key) const
136	{
137		return fMap.ContainsKey(key);
138	}
139
140	int32 Size() const
141	{
142		return fMap.Size();
143	}
144
145private:
146
147	void _DisconnectNodeAndMakeNewest(LRUNode* node) {
148		if (node != fNewestNode) {
149			_DisconnectNode(node);
150			node->fOlder = NULL;
151			node->fNewer = NULL;
152			_SetNewestNode(node);
153		}
154	}
155
156	void _DisconnectNode(LRUNode* node)
157	{
158		LRUNode *older = node->fOlder;
159		LRUNode *newer = node->fNewer;
160		if (newer != NULL)
161			newer->fOlder = older;
162		if (older != NULL)
163			older->fNewer = newer;
164		if (fNewestNode == node)
165			fNewestNode = older;
166		if (fOldestNode == node)
167			fOldestNode = newer;
168	}
169
170	void _SetNewestNode(LRUNode* node)
171	{
172		if (node != fNewestNode) {
173			node->fOlder = fNewestNode;
174			node->fNewer = NULL;
175			if (fNewestNode != NULL)
176				fNewestNode->fNewer = node;
177			fNewestNode = node;
178			if (fOldestNode == NULL)
179				fOldestNode = node;
180		}
181	}
182
183	void _PurgeOldestNode()
184	{
185		if (fOldestNode == NULL)
186			debugger("attempt to purge oldest node but there is none to purge");
187		Remove(fOldestNode->fKey);
188	}
189
190	void _PurgeExcess()
191	{
192		while(Size() > fLimit)
193			_PurgeOldestNode();
194	}
195
196protected:
197	HashMap<Key, LRUNode*>	fMap;
198	LRUNode*				fNewestNode;
199	LRUNode*				fOldestNode;
200
201private:
202	int32					fLimit;
203};
204
205}; // namespace BPrivate
206
207using BPrivate::LRUCache;
208
209#endif // LRU_CACHE_H
210