1#ifndef CACHE_H
2#define CACHE_H
3/* Cache - a template cache class
4**
5** Copyright 2001 pinc Software. All Rights Reserved.
6** Released under the terms of the MIT license.
7*/
8
9
10#include <SupportDefs.h>
11
12#include <stdio.h>
13
14
15template<class T> class Cache
16{
17	public:
18		class Cacheable
19		{
20			public:
21				Cacheable()
22					:
23					prev(NULL),
24					next(NULL),
25					locked(0L),
26					isDirty(false)
27				{
28				}
29
30				virtual ~Cacheable()
31				{
32					// perform your "undirty" work here
33				}
34
35				virtual bool Equals(T) = 0;
36
37				Cacheable	*prev,*next;
38				int32		locked;
39				bool		isDirty;
40		};
41
42	public:
43		Cache(int32 max = 20)
44			:
45			fMaxInQueue(max),
46			fCount(0),
47			fHoldChanges(false),
48			fMostRecentlyUsed(NULL),
49			fLeastRecentlyUsed(NULL)
50		{
51		}
52
53		virtual ~Cache()
54		{
55			Clear(0,true);
56		}
57
58		void Clear(int32 targetCount = 0,bool force = false)
59		{
60			Cacheable *entry = fLeastRecentlyUsed;
61			while (entry)
62			{
63				Cacheable *prev = entry->prev;
64				if (entry->locked <= 0 || force)
65				{
66					if (entry->next)
67						entry->next->prev = prev;
68					if (prev)
69						prev->next = entry->next;
70
71					if (fLeastRecentlyUsed == entry)
72						fLeastRecentlyUsed = prev;
73					if (fMostRecentlyUsed == entry)
74						fMostRecentlyUsed = prev;
75
76					delete entry;
77
78					if (--fCount <= targetCount)
79						break;
80				}
81
82				entry = prev;
83			}
84		}
85
86		void SetHoldChanges(bool hold)
87		{
88			fHoldChanges = hold;
89			if (!hold)
90				Clear(fMaxInQueue);
91		}
92
93		status_t SetDirty(T data,bool dirty)
94		{
95			Cacheable *entry = Get(data);
96			if (!entry)
97				return B_ENTRY_NOT_FOUND;
98
99			entry->isDirty = dirty;
100			return B_OK;
101		}
102
103		status_t Lock(T data)
104		{
105			Cacheable *entry = Get(data);
106			if (!entry)
107				return B_ENTRY_NOT_FOUND;
108
109			entry->locked++;
110			return B_OK;
111		}
112
113		status_t Unlock(T data)
114		{
115			Cacheable *entry = Get(data);
116			if (!entry)
117				return B_ENTRY_NOT_FOUND;
118
119			entry->locked--;
120			return B_OK;
121		}
122
123		Cacheable *Get(T data)
124		{
125			Cacheable *entry = GetFromCache(data);
126			if (entry)
127			{
128				if (fMostRecentlyUsed == entry)
129					return entry;
130
131				// remove entry from cache (to insert it at top of the MRU list)
132				if (entry->prev)
133					entry->prev->next = entry->next;
134				if (!entry->next)
135				{
136					if (fLeastRecentlyUsed == entry)
137						fLeastRecentlyUsed = entry->prev;
138					else
139						fprintf(stderr,"Cache: fatal error, fLeastRecentlyUsed != entry\n");
140				}
141				else
142					entry->next->prev = entry->prev;
143			}
144			else
145			{
146				entry = NewCacheable(data);
147				if (entry)
148					fCount++;
149			}
150
151			if (entry)
152			{
153				// insert entry at the top of the MRU list
154				entry->next = fMostRecentlyUsed;
155				entry->prev = NULL;
156
157				if (fMostRecentlyUsed)
158					fMostRecentlyUsed->prev = entry;
159				else if (fLeastRecentlyUsed == NULL)
160					fLeastRecentlyUsed = entry;
161				else
162					fprintf(stderr,"Cache: fatal error, fLeastRecently != NULL!\n");
163				fMostRecentlyUsed = entry;
164
165				// remove old nodes from of the cache (if possible and necessary)
166				if (!fHoldChanges
167					&& fCount > fMaxInQueue
168					&& fLeastRecentlyUsed)
169					Clear(fMaxInQueue);
170			}
171			return entry;
172		}
173
174	protected:
175		Cacheable *GetFromCache(T data)
176		{
177			Cacheable *entry = fMostRecentlyUsed;
178			while (entry)
179			{
180				if (entry->Equals(data))
181					return entry;
182				entry = entry->next;
183			}
184			return NULL;
185		}
186
187		virtual Cacheable *NewCacheable(T data) = 0;
188
189		int32		fMaxInQueue, fCount;
190		bool		fHoldChanges;
191		Cacheable	*fMostRecentlyUsed;
192		Cacheable	*fLeastRecentlyUsed;
193};
194
195#endif	/* CACHE_H */
196