/** * @file llkeyusetracker.h * @brief Declaration of the LLKeyUseTracker class. * * $LicenseInfo:firstyear=2003&license=viewerlgpl$ * Second Life Viewer Source Code * Copyright (C) 2010, Linden Research, Inc. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; * version 2.1 of the License only. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA * $/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