/** 
 * @file llkeyusetracker.h
 * @brief Declaration of the LLKeyUseTracker class.
 *
 * $LicenseInfo:firstyear=2003&license=viewergpl$
 * 
 * Copyright (c) 2003-2009, Linden Research, Inc.
 * 
 * Second Life Viewer Source Code
 * The source code in this file ("Source Code") is provided by Linden Lab
 * to you under the terms of the GNU General Public License, version 2.0
 * ("GPL"), unless you have obtained a separate licensing agreement
 * ("Other License"), formally executed by you and Linden Lab.  Terms of
 * the GPL can be found in doc/GPL-license.txt in this distribution, or
 * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
 * 
 * There are special exceptions to the terms and conditions of the GPL as
 * it is applied to this Source Code. View the full text of the exception
 * in the file doc/FLOSS-exception.txt in this software distribution, or
 * online at
 * http://secondlifegrid.net/programs/open_source/licensing/flossexception
 * 
 * By copying, modifying or distributing this software, you acknowledge
 * that you have read and understood your obligations described above,
 * and agree to abide by those obligations.
 * 
 * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
 * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
 * COMPLETENESS OR PERFORMANCE.
 * $/LicenseInfo$
 */

#ifndef LL_KEYUSETRACKER_H
#define LL_KEYUSETRACKER_H

// This is a generic cache for an arbitrary data type indexed against an
// arbitrary key type. The cache length is determined by expiration time
// tince against last use and set size. The age of elements and the size
// of the cache are queryable.
//
// This is implemented as a list, which makes search O(n). If you reuse this
// for something with a large dataset, consider reimplementing with a Boost
// multimap based on both a map(key) and priority queue(last_use).

template <class TKey, class TData>
class KeyUseTrackerNodeImpl
{
public:
	U64 mLastUse;
	U32 mUseCount;
	TKey mKey;
	TData mData;

	KeyUseTrackerNodeImpl( TKey k, TData d ) :
		mLastUse(0),
		mUseCount(0),
		mKey( k ),
		mData( d )
	{
	}
};


template <class TKey, class TData>
class LLKeyUseTracker
{
	typedef KeyUseTrackerNodeImpl<TKey,TData> TKeyUseTrackerNode;
	typedef std::list<TKeyUseTrackerNode *> TKeyList;
	TKeyList mKeyList;
	U64 mMemUsecs;
	U64 mLastExpire;
	U32 mMaxCount;
	U32 mCount;

	static U64 getTime()
	{
		// This function operates on a frame basis, not instantaneous.
		// We can rely on its output for determining first use in a
		// frame.
		return LLFrameTimer::getTotalTime();
	}

	void ageKeys()
	{
		U64 now = getTime();
		if( now == mLastExpire )
		{
			return;
		}
		mLastExpire = now;

		while( !mKeyList.empty() && (now - mKeyList.front()->mLastUse > mMemUsecs ) )
		{
			delete mKeyList.front();
			mKeyList.pop_front();
			mCount--;
		}
	}

	TKeyUseTrackerNode *findNode( TKey key )
	{
		ageKeys();

		typename TKeyList::iterator i;
		for( i = mKeyList.begin(); i != mKeyList.end(); i++ )
		{
			if( (*i)->mKey == key )
				return *i;
		}

		return NULL;
	}

	TKeyUseTrackerNode *removeNode( TKey key )
	{
		TKeyUseTrackerNode *i;
		i = findNode( key );
		if( i )
		{
			mKeyList.remove( i );
			mCount--;
			return i;
		}

		return NULL;
	}

public:
	LLKeyUseTracker( U32 memory_seconds, U32 max_count ) :
		mLastExpire(0),
		mMaxCount( max_count ),
		mCount(0)
	{
		mMemUsecs = ((U64)memory_seconds) * 1000000;
	}

	~LLKeyUseTracker()
	{
		// Flush list
		while( !mKeyList.empty() )
		{
			delete mKeyList.front();
			mKeyList.pop_front();
			mCount--;
		}
	}

	void markUse( TKey key, TData data )
	{
		TKeyUseTrackerNode *node = removeNode( key );
		if( !node )
		{
			node = new TKeyUseTrackerNode(key, data);
		}
		else
		{
			// Update data
			node->mData = data;
		}
		node->mLastUse = getTime();
		node->mUseCount++;
		mKeyList.push_back( node );
		mCount++;

		// Too many items? Drop head
		if( mCount > mMaxCount )
		{
			delete mKeyList.front();
			mKeyList.pop_front();
			mCount--;
		}
	}

	void forgetKey( TKey key )
	{
		TKeyUseTrackerNode *node = removeNode( key );
		if( node )
		{
			delete node;
		}
	}

	U32 getUseCount( TKey key )
	{
		TKeyUseTrackerNode *node = findNode( key );
		if( node )
		{
			return node->mUseCount;
		}
		return 0;
	}

	U64 getTimeSinceUse( TKey key )
	{
		TKeyUseTrackerNode *node = findNode( key );
		if( node )
		{
			U64 now = getTime();
			U64 delta = now - node->mLastUse;
			return (U32)( delta / 1000000 );
		}
		return 0;
	}

	TData *getLastUseData( TKey key )
	{
		TKeyUseTrackerNode *node = findNode( key );
		if( node )
		{
			return &node->mData;
		}
		return NULL;
	}

	U32 getKeyCount()
	{
		return mCount;
	}
};

#endif