src/objcache.h

   1 /******************************************************************************
   2  *
   3  * $Id:$
   4  *
   5  * Copyright (C) 1997-2012 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       if (handle==m_lastHandle) return;
  75       m_lastHandle = handle;
  76       m_hits++;
  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     /*! total size of the cache */
  91     int size() const { return m_size; }
  92
  93     /*! number of elements in the cache */
  94     int count() const { return m_count; }
  95
  96     int hits() const
  97     {
  98       return m_hits;
  99     }
 100     int misses() const
 101     {
 102       return m_misses;
 103     }
 104
 105
 106   private:
 107     void moveToFront(int index);
 108     unsigned int hash(void *addr);
 109     HashNode *hashFind(void *obj);
 110     HashNode *hashInsert(void *obj);
 111     void hashRemove(void *obj);
 112
 113     CacheNode *m_cache;
 114     HashNode  *m_hash;
 115     int        m_head;
 116     int        m_tail;
 117     int        m_size;
 118     int        m_count;
 119     int        m_freeHashNodes;
 120     int        m_freeCacheNodes;
 121     int        m_lastHandle;
 122     int        m_misses;
 123     int        m_hits;
 124 };
 125
 126 #endif // OBJCACHE_H
 127