/*****************************************************************************
 * $Id: gfx_cache.hh,v 1.60 2006/08/03 23:11:40 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	C++ template for a C++ object cache.
 * @remarks
 * Template for a cache of C++ objects.
 *
 * The purpose of this cache is to reduce memory consumption
 * by deleting objects which haven't been used recently.
 * Each cache only caches one type of C++ objects.
 * Different caches must be instantiated to cache different types.
 * All C++ objects put into a cache must be allocated by the C++ new operator
 * as the cache will free the LRU objects using the delete or delete[] operator.
 *
 * Put() puts an object into a cache and returns an opaque struct (handle) to
 * the user of the cache.  The user can subsequently pass the same opaque struct
 * to Get() to retrieve the same cached object.  Get() returns NULL if an object
 * was evicted in which case the user must recompute the object.
 *
 * The cache code uses the opaque struct itself to cache the object.
 * A list is used solely for maintaining recently-used order.
 * The first link in the list (head) is the most-recently-used one.
 * The list is never searched.
 *
 * When a cache opaque struct is deleted, ~CacheOpq() will automatically
 * remove the object out of the cache and delete it.
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#ifndef GFX_CACHE_HH
#define GFX_CACHE_HH 1

#include "gfx_defs.hh"
#include "gfx_types.hh"
#include "gfx_list.hh"

namespace gfx {

template <typename T> class CacheLink;
template <typename T> class Cache;

////////////////////////////////////////////////////////////////////////////////
/// @brief Opaque struct returned to user of cache.
/// The user should treat it as opaque.
template<typename T>
class CacheOpq
{
PREVENT_COPYING(CacheOpq)
public:
			// When the opaque struct is deleted, the cached object must be removed
			// out of the cache and it is deleted (as Shrink() ordinarily does).
			// This prevents Shrink() encountering a deleted CacheOpq struct.
			CacheOpq( void ) { mCache = NULL; mLinkCache = NULL; SET_TYPESIG( this, TYPESIG_LIB_CACHE_OPQ ); }
			~CacheOpq()      { if ( mCache != NULL && mLinkCache != NULL ) mCache->Remove(this,true);
                               mCache = NULL; mLinkCache = NULL; INVALIDATE_TYPESIG( this, TYPESIG_LIB_CACHE_OPQ ); }
private:
	Cache<T>*		mCache;
	CacheLink<T>*	mLinkCache;

public:
	DECL_TYPESIG( TYPESIG_LIB_CACHE_OPQ )
	friend class Cache<T>;
};

////////////////////////////////////////////////////////////////////////////////
/// @brief Internal cache struct (not for use outside of cache code).
/// This represents a cached object (an item in the cache).
template<typename T>
class CacheLink
{
    PREVENT_COPYING(CacheLink)
public:
	T*						mObj;		///< cached object
	CacheOpq<T>*			mOpq;		///< pointer to opaque struct (returned to user)
	Dlink< CacheLink<T> >*	mDlink;     ///< pointer to link in list (to maintain recently-used order)
	DECL_TYPESIG_AUTO( CacheLink, TYPESIG_LIB_CACHE_LINK )
};

////////////////////////////////////////////////////////////////////////////////
/// @brief Cache class template.
template<typename T>
class Cache
{
    PREVENT_COPYING(Cache)
public:
    enum eDeletor { SCALAR, ARRAY };
				Cache( uint size, eDeletor deletor );
				~Cache();
	void		Put( CacheOpq<T>* opq, T* obj );
	T*			Get( CacheOpq<T>* opq );
	void		Remove( CacheOpq<T>* opq, bool deleteObject );
	void		Resize( uint size );

private:
	void		Shrink( void );
	uint		MinLimit( uint n ) { return MAX( n, CACHE_MIN_SIZE ); }
	enum					{ CACHE_MIN_SIZE = 10 };
	uint					mCnt;		///< count of cached elements
	uint					mLimit;		///< cache is shrunk to this many elems when cnt becomes greater
	Dlist< CacheLink<T> >	mDlist;		///< maintains recently-used order
	eDeletor				mDeletor;	///< whether to use delete or delete[]

public:
	DECL_TYPESIG( TYPESIG_LIB_CACHE )
	friend bool CacheTest( void );
};

/*****************************************************************************
 * Constructor.
 *****************************************************************************/
template<typename T>
Cache<T>::Cache( uint size, eDeletor deletor )
: mCnt(0),
  mLimit(MinLimit(size)),
  mDeletor(deletor)
{
	SET_TYPESIG( this, TYPESIG_LIB_CACHE );
    CHECK_TYPESIG( &mDlist, TYPESIG_LIB_DLIST );
}

/*****************************************************************************
 * Destructor.
 *****************************************************************************/
template<typename T>
Cache<T>::~Cache()
{
ASSERT( mCnt >= 0 );
CHECK_TYPESIG( &mDlist, TYPESIG_LIB_DLIST );

	while ( mCnt > 0 ) Shrink();

INVALIDATE_TYPESIG( this, TYPESIG_LIB_CACHE );
}

/*****************************************************************************
 * Put a C++ object into the cache.
 *****************************************************************************/
template<typename T>
void
Cache<T>::Put( CacheOpq<T>* opq, T* obj )
{
CHECK_TYPESIG( this,  TYPESIG_LIB_CACHE );
CHECK_TYPESIG( opq,   TYPESIG_LIB_CACHE_OPQ );
CHECK_TYPESIG( &mDlist, TYPESIG_LIB_DLIST );
ASSERT( obj );
	if ( UX(opq->mLinkCache != NULL) ) return;		// already cached?
	++mCnt;
	CacheLink<T>* mLinkCache = new CacheLink<T>;
	mLinkCache->mObj      = obj;					// fill CacheLink struct
	mLinkCache->mOpq      = opq;
	mLinkCache->mDlink = mDlist.Prepend( mLinkCache ); // prepend CacheLink to head of list
	opq->mCache     = this;
	opq->mLinkCache = mLinkCache;					// point user's CacheOpq struct to CacheLink
	if ( mCnt > mLimit ) Shrink();					// after adding, shrink cache if necessary
ASSERT( mCnt <= mLimit );
}

/*****************************************************************************
 * Get a C++ object in the cache -- the object STAYS in the cache.
 * The object will become the MRU one (the head of the underyling list).
 *****************************************************************************/
template<typename T>
T*
Cache<T>::Get( CacheOpq<T>* opq )
{
CHECK_TYPESIG( this,  TYPESIG_LIB_CACHE );
CHECK_TYPESIG( opq,   TYPESIG_LIB_CACHE_OPQ );
CHECK_TYPESIG( &mDlist, TYPESIG_LIB_DLIST );

	// The opaque struct itself records if the object is cached.
	// This simple pointer test is what makes this cache quick.
	if ( EX(opq->mLinkCache != NULL) )
	{
		// Move the cached object to the head of the list
		// to make it the most-recently-used and to age the others.
		// cnt isn't decremented as object is still in the cache.
CHECK_TYPESIG( opq->mLinkCache, TYPESIG_LIB_CACHE_LINK );
		mDlist.Unlink( opq->mLinkCache->mDlink );
		opq->mLinkCache->mDlink = mDlist.Prepend( opq->mLinkCache );
CHECK_TYPESIG( opq->mLinkCache->mDlink, TYPESIG_LIB_DLINK );
ASSERT( opq->mLinkCache->mObj );
		return opq->mLinkCache->mObj;
	}
	else
	{
		return NULL; // not in cache
	}
}

/*****************************************************************************
 * Remove a C++ object out of the cache.
 * Must specify whether to delete or keep the cached object.
 * @remarks Code is similar to Shrink() but checking differs.
 *****************************************************************************/
template<typename T>
void
Cache<T>::Remove( CacheOpq<T>* opq, bool deleteObject )
{
CHECK_TYPESIG( this,  TYPESIG_LIB_CACHE );
CHECK_TYPESIG( opq,   TYPESIG_LIB_CACHE_OPQ );
CHECK_TYPESIG( &mDlist, TYPESIG_LIB_DLIST );

	// Is it in the cache?  If not, no action necessary.
	if ( EX(opq->mLinkCache != NULL) )
	{
		// Removing an object out of the cache is done by unlinking it
		// out of the list and updating the user's opaque struct.
		// The opaque struct isn't deleted (the user is responsible for it).
ASSERT( opq->mCache == this );
ASSERT( mCnt > 0 );
		--mCnt;
		CacheLink<T>* mLinkCache = opq->mLinkCache;
CHECK_TYPESIG( mLinkCache, TYPESIG_LIB_CACHE_LINK );
		if ( EX(deleteObject) )
		{
			if ( mDeletor == ARRAY )			// delete cached object appropriately
				delete[] mLinkCache->mObj;
			else
				delete   mLinkCache->mObj;
		}
		opq->mCache     = NULL;					// update user's opaque struct (CacheOpq)
		opq->mLinkCache = NULL;					// update user's opaque struct (CacheOpq)
		mDlist.Unlink( mLinkCache->mDlink );	// remove from list -- Unlink() deletes mDlink
		delete mLinkCache;						// delete CacheLink struct -- keep CacheOpq
	}
}

/*****************************************************************************
 * Resize the cache.
 *****************************************************************************/
template<typename T>
void
Cache<T>::Resize( uint size )
{
CHECK_TYPESIG( this, TYPESIG_LIB_CACHE );

	// If the size is smaller, shrink the cache to not violate ASSERT(mCnt <= mLimit).
	// "size" will be the new limit.
	size = MinLimit( size );
	if ( mCnt > size ) while ( mCnt > size ) Shrink(); // Shrink() decrements mCnt
	mLimit = size;
}

/*****************************************************************************
 * Shrink the cache by evicting the LRU object.
 * The last link in the list (tail) references it.
 * @remarks Code is similar to Get() but checking differs.
 *****************************************************************************/
template<typename T>
void
Cache<T>::Shrink( void )
{
ASSERT( mCnt > 0 );
CHECK_TYPESIG( &mDlist, TYPESIG_LIB_DLIST );

	// Delete the cached object (CacheLink->mObj).
	// Nullify the pointer to this CacheLink that
	// is stored in the user's CacheOpq struct.
	// Then unlink and delete the CacheLink struct.
	--mCnt;
	Dlink< CacheLink<T> >* dlink = mDlist.Last(); // get list's tail
CHECK_TYPESIG( dlink, TYPESIG_LIB_DLINK );
	CacheLink<T>* mLinkCache = dlink->mObj;
CHECK_TYPESIG( mLinkCache, TYPESIG_LIB_CACHE_LINK );
	if ( mDeletor == ARRAY )			// delete cached object appropriately
		delete[] mLinkCache->mObj;
	else
		delete   mLinkCache->mObj;
	CacheOpq<T>* opq = mLinkCache->mOpq;
CHECK_TYPESIG( opq, TYPESIG_LIB_CACHE_OPQ );
ASSERT( opq->mLinkCache == mLinkCache );
	opq->mLinkCache = NULL;		// update user's opaque struct (CacheOpq)
	mDlist.Unlink( dlink ); 	// remove from list -- Unlink() deletes dlink
	delete mLinkCache;			// delete CacheLink struct -- keep CacheOpq
}

} // namespace gfx

#endif // GFX_CACHE_HH
