/******************************************************************************

 *

 * 

 *

 * Copyright (C) 1997-2008 by Dimitri van Heesch.

 *

 * Permission to use, copy, modify, and distribute this software and its

 * documentation under the terms of the GNU General Public License is hereby 

 * granted. No representations are made about the suitability of this software 

 * for any purpose. It is provided "as is" without express or implied warranty.

 * See the GNU General Public License for more details.

 *

 * Documents produced by Doxygen are derivative works derived from the

 * input used in their production; they are not affected by this license.

 *

 */

#ifndef OBJCACHE_H

#define OBJCACHE_H

//#define CACHE_TEST

//#define CACHE_DEBUG

#define CACHE_STATS

/** @brief Cache for objects.

 *

 *  This cache is used to decide which objects should remain in

 *  memory. It uses a least recently used policy (LRU) to decide

 *  which object should make room for a new object when the cache

 *  is full. An object should be added using add(), and then use()

 *  should be called when the object is used.

 */

class ObjCache

{

  private:

    struct CacheNode

    {

      CacheNode() : next(-1), prev(-1), obj(0) {}

      int next;

      int prev;

      void *obj;

    };

    struct HashNode

    {

      HashNode() : head(-1), nextHash(-1), index(-1), obj(0) {}

      int head;

      int nextHash; 

      int index;

      void *obj;

    };

  public:

    /*! Creates the cache. The number of elements in the cache is 2 to 

     *  the power of \a logSize. 

     */

    ObjCache(unsigned int logSize);

    /*! Deletes the cache and free all internal data-structures used. */

   ~ObjCache();

    /*! Adds \a obj to the cache. When victim is not null, this object is

     *  removed from the cache to make room for \a obj. 

     *  Returns a handle to the object, which can be used by the use()

     *  function, each time the object is used.

     */

    int add(void *obj,void **victim);

    /*! Indicates that this object is used. This will move the object

     *  to the front of the internal LRU list to make sure it is removed last.

     *  The parameter \a handle is returned when called add().

     */

    void use(int handle)

    {

      hits++;

      if (handle==m_lastHandle) return;

      m_lastHandle = handle;

      moveToFront(handle);

    }

    /*! Removes the item identified by \a handle from the cache.

     *  @see add()

     */

    void del(int handle);

    /*! Debug function. Prints the LRU list */

    void printLRU();

    /*! Print miss/hits statistics */

    void printStats();

  private:

    void moveToFront(int index);

    unsigned int hash(void *addr);

    HashNode *hashFind(void *obj);

    HashNode *hashInsert(void *obj);

    void hashRemove(void *obj);

    CacheNode *m_cache;

    HashNode  *m_hash;

    int        m_head;

    int        m_tail;

    int        m_size;

    int        m_freeHashNodes;

    int        m_freeCacheNodes;

    int        m_lastHandle;

#ifdef CACHE_STATS

    static int misses;

    static int hits;

#endif

};

#endif // OBJCACHE_H