xref: /haiku/src/bin/bfs_tools/lib/Cache.h

#ifndef CACHE_H
#define CACHE_H
/* Cache - a template cache class
**
** Copyright 2001 pinc Software. All Rights Reserved.
** Released under the terms of the MIT license.
*/


#include <SupportDefs.h>

#include <stdio.h>


template<class T> class Cache
{
	public:
		class Cacheable
		{
			public:
				Cacheable()
					:
					prev(NULL),
					next(NULL),
					locked(0L),
					isDirty(false)
				{
				}

				virtual ~Cacheable()
				{
					// perform your "undirty" work here
				}

				virtual bool Equals(T) = 0;

				Cacheable	*prev,*next;
				int32		locked;
				bool		isDirty;
		};

	public:
		Cache(int32 max = 20)
			:
			fMaxInQueue(max),
			fCount(0),
			fHoldChanges(false),
			fMostRecentlyUsed(NULL),
			fLeastRecentlyUsed(NULL)
		{
		}

		virtual ~Cache()
		{
			Clear(0,true);
		}

		void Clear(int32 targetCount = 0,bool force = false)
		{
			Cacheable *entry = fLeastRecentlyUsed;
			while (entry)
			{
				Cacheable *prev = entry->prev;
				if (entry->locked <= 0 || force)
				{
					if (entry->next)
						entry->next->prev = prev;
					if (prev)
						prev->next = entry->next;

					if (fLeastRecentlyUsed == entry)
						fLeastRecentlyUsed = prev;
					if (fMostRecentlyUsed == entry)
						fMostRecentlyUsed = prev;

					delete entry;

					if (--fCount <= targetCount)
						break;
				}

				entry = prev;
			}
		}

		void SetHoldChanges(bool hold)
		{
			fHoldChanges = hold;
			if (!hold)
				Clear(fMaxInQueue);
		}

		status_t SetDirty(T data,bool dirty)
		{
			Cacheable *entry = Get(data);
			if (!entry)
				return B_ENTRY_NOT_FOUND;

			entry->isDirty = dirty;
			return B_OK;
		}

		status_t Lock(T data)
		{
			Cacheable *entry = Get(data);
			if (!entry)
				return B_ENTRY_NOT_FOUND;

			entry->locked++;
			return B_OK;
		}

		status_t Unlock(T data)
		{
			Cacheable *entry = Get(data);
			if (!entry)
				return B_ENTRY_NOT_FOUND;

			entry->locked--;
			return B_OK;
		}

		Cacheable *Get(T data)
		{
			Cacheable *entry = GetFromCache(data);
			if (entry)
			{
				if (fMostRecentlyUsed == entry)
					return entry;

				// remove entry from cache (to insert it at top of the MRU list)
				if (entry->prev)
					entry->prev->next = entry->next;
				if (!entry->next)
				{
					if (fLeastRecentlyUsed == entry)
						fLeastRecentlyUsed = entry->prev;
					else
						fprintf(stderr,"Cache: fatal error, fLeastRecentlyUsed != entry\n");
				}
				else
					entry->next->prev = entry->prev;
			}
			else
			{
				entry = NewCacheable(data);
				if (entry)
					fCount++;
			}

			if (entry)
			{
				// insert entry at the top of the MRU list
				entry->next = fMostRecentlyUsed;
				entry->prev = NULL;

				if (fMostRecentlyUsed)
					fMostRecentlyUsed->prev = entry;
				else if (fLeastRecentlyUsed == NULL)
					fLeastRecentlyUsed = entry;
				else
					fprintf(stderr,"Cache: fatal error, fLeastRecently != NULL!\n");
				fMostRecentlyUsed = entry;

				// remove old nodes from of the cache (if possible and necessary)
				if (!fHoldChanges
					&& fCount > fMaxInQueue
					&& fLeastRecentlyUsed)
					Clear(fMaxInQueue);
			}
			return entry;
		}

	protected:
		Cacheable *GetFromCache(T data)
		{
			Cacheable *entry = fMostRecentlyUsed;
			while (entry)
			{
				if (entry->Equals(data))
					return entry;
				entry = entry->next;
			}
			return NULL;
		}

		virtual Cacheable *NewCacheable(T data) = 0;

		int32		fMaxInQueue, fCount;
		bool		fHoldChanges;
		Cacheable	*fMostRecentlyUsed;
		Cacheable	*fLeastRecentlyUsed;
};

#endif	/* CACHE_H */