1 /******************************************************************************

     2  *

     3  * 

     4  *

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

     6  *

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

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

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

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

    11  * See the GNU General Public License for more details.

    12  *

    13  * Documents produced by Doxygen are derivative works derived from the

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

    15  *

    16  */

    17 

    18 #ifndef OBJCACHE_H

    19 #define OBJCACHE_H

    20 

    21 //#define CACHE_TEST

    22 //#define CACHE_DEBUG

    23 #define CACHE_STATS

    24 

    25 /** @brief Cache for objects.

    26  *

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

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

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

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

    31  *  should be called when the object is used.

    32  */

    33 class ObjCache

    34 {

    35   private:

    36     struct CacheNode

    37     {

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

    39       int next;

    40       int prev;

    41       void *obj;

    42     };

    43     struct HashNode

    44     {

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

    46       int head;

    47       int nextHash; 

    48       int index;

    49       void *obj;

    50     };

    51 

    52   public:

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

    54      *  the power of \a logSize. 

    55      */

    56     ObjCache(unsigned int logSize);

    57 

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

    59    ~ObjCache();

    60 

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

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

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

    64      *  function, each time the object is used.

    65      */

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

    67 

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

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

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

    71      */

    72     void use(int handle)

    73     {

    74       hits++;

    75       if (handle==m_lastHandle) return;

    76       m_lastHandle = handle;

    77       moveToFront(handle);

    78     }

    79 

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

    81      *  @see add()

    82      */

    83     void del(int handle);

    84 

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

    86     void printLRU();

    87     /*! Print miss/hits statistics */

    88     void printStats();

    89 

    90   private:

    91     void moveToFront(int index);

    92     unsigned int hash(void *addr);

    93     HashNode *hashFind(void *obj);

    94     HashNode *hashInsert(void *obj);

    95     void hashRemove(void *obj);

    96 

    97     CacheNode *m_cache;

    98     HashNode  *m_hash;

    99     int        m_head;

   100     int        m_tail;

   101     int        m_size;

   102     int        m_freeHashNodes;

   103     int        m_freeCacheNodes;

   104     int        m_lastHandle;

   105 

   106 #ifdef CACHE_STATS

   107     static int misses;

   108     static int hits;

   109 #endif

   110 };

   111 

   112 #endif // OBJCACHE_H

   113