|
Packit |
1c1d7e |
/******************************************************************************
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Copyright (C) 1997-2015 by Dimitri van Heesch.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Permission to use, copy, modify, and distribute this software and its
|
|
Packit |
1c1d7e |
* documentation under the terms of the GNU General Public License is hereby
|
|
Packit |
1c1d7e |
* granted. No representations are made about the suitability of this software
|
|
Packit |
1c1d7e |
* for any purpose. It is provided "as is" without express or implied warranty.
|
|
Packit |
1c1d7e |
* See the GNU General Public License for more details.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Documents produced by Doxygen are derivative works derived from the
|
|
Packit |
1c1d7e |
* input used in their production; they are not affected by this license.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#ifndef OBJCACHE_H
|
|
Packit |
1c1d7e |
#define OBJCACHE_H
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
//#define CACHE_TEST
|
|
Packit |
1c1d7e |
//#define CACHE_DEBUG
|
|
Packit |
1c1d7e |
#define CACHE_STATS
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/** @brief Cache for objects.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* This cache is used to decide which objects should remain in
|
|
Packit |
1c1d7e |
* memory. It uses a least recently used policy (LRU) to decide
|
|
Packit |
1c1d7e |
* which object should make room for a new object when the cache
|
|
Packit |
1c1d7e |
* is full. An object should be added using add(), and then use()
|
|
Packit |
1c1d7e |
* should be called when the object is used.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
class ObjCache
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
struct CacheNode
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
CacheNode() : next(-1), prev(-1), obj(0) {}
|
|
Packit |
1c1d7e |
int next;
|
|
Packit |
1c1d7e |
int prev;
|
|
Packit |
1c1d7e |
void *obj;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
struct HashNode
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
HashNode() : head(-1), nextHash(-1), index(-1), obj(0) {}
|
|
Packit |
1c1d7e |
int head;
|
|
Packit |
1c1d7e |
int nextHash;
|
|
Packit |
1c1d7e |
int index;
|
|
Packit |
1c1d7e |
void *obj;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Creates the cache. The number of elements in the cache is 2 to
|
|
Packit |
1c1d7e |
* the power of \a logSize.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
ObjCache(unsigned int logSize);
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Deletes the cache and free all internal data-structures used. */
|
|
Packit |
1c1d7e |
~ObjCache();
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Adds \a obj to the cache. When victim is not null, this object is
|
|
Packit |
1c1d7e |
* removed from the cache to make room for \a obj.
|
|
Packit |
1c1d7e |
* Returns a handle to the object, which can be used by the use()
|
|
Packit |
1c1d7e |
* function, each time the object is used.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
int add(void *obj,void **victim);
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Indicates that this object is used. This will move the object
|
|
Packit |
1c1d7e |
* to the front of the internal LRU list to make sure it is removed last.
|
|
Packit |
1c1d7e |
* The parameter \a handle is returned when called add().
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void use(int handle)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if (handle==m_lastHandle) return;
|
|
Packit |
1c1d7e |
m_lastHandle = handle;
|
|
Packit |
1c1d7e |
m_hits++;
|
|
Packit |
1c1d7e |
moveToFront(handle);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Removes the item identified by \a handle from the cache.
|
|
Packit |
1c1d7e |
* @see add()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void del(int handle);
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Debug function. Prints the LRU list */
|
|
Packit |
1c1d7e |
void printLRU();
|
|
Packit |
1c1d7e |
/*! Print miss/hits statistics */
|
|
Packit |
1c1d7e |
void printStats();
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! total size of the cache */
|
|
Packit |
1c1d7e |
int size() const { return m_size; }
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! number of elements in the cache */
|
|
Packit |
1c1d7e |
int count() const { return m_count; }
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
int hits() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_hits;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
int misses() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_misses;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
void moveToFront(int index);
|
|
Packit |
1c1d7e |
unsigned int hash(void *addr);
|
|
Packit |
1c1d7e |
HashNode *hashFind(void *obj);
|
|
Packit |
1c1d7e |
HashNode *hashInsert(void *obj);
|
|
Packit |
1c1d7e |
void hashRemove(void *obj);
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
CacheNode *m_cache;
|
|
Packit |
1c1d7e |
HashNode *m_hash;
|
|
Packit |
1c1d7e |
int m_head;
|
|
Packit |
1c1d7e |
int m_tail;
|
|
Packit |
1c1d7e |
int m_size;
|
|
Packit |
1c1d7e |
int m_count;
|
|
Packit |
1c1d7e |
int m_freeHashNodes;
|
|
Packit |
1c1d7e |
int m_freeCacheNodes;
|
|
Packit |
1c1d7e |
int m_lastHandle;
|
|
Packit |
1c1d7e |
int m_misses;
|
|
Packit |
1c1d7e |
int m_hits;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#endif // OBJCACHE_H
|
|
Packit |
1c1d7e |
|