src/objcache.cpp

   1 /******************************************************************************
   2  *
   3  * $Id: classlist.cpp,v 1.14 2001/03/19 19:27:39 root Exp $
   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 #include <stdio.h>
  19 #include <assert.h>
  20 #include <qglobal.h>
  21 #include "objcache.h"
  22
  23 //----------------------------------------------------------------------
  24
  25 ObjCache::ObjCache(unsigned int logSize)
  26   : m_head(-1), m_tail(-1), //m_numEntries(0),
  27     m_size(1<<logSize), m_count(0), m_freeHashNodes(0), m_freeCacheNodes(0),
  28     m_lastHandle(-1)
  29 {
  30   int i;
  31   m_cache = new CacheNode[m_size];
  32   m_hash  = new HashNode[m_size];
  33   // add all items to list of free buckets
  34   for (i=0;i<m_size-1;i++)
  35   {
  36     m_hash[i].nextHash = i+1;
  37     m_cache[i].next    = i+1;
  38   }
  39   m_misses = 0;
  40   m_hits   = 0;
  41 }
  42
  43 ObjCache::~ObjCache()
  44 {
  45   delete[] m_cache;
  46   delete[] m_hash;
  47 }
  48
  49 int ObjCache::add(void *obj,void **victim)
  50 {
  51   *victim=0;
  52
  53   HashNode *hnode = hashFind(obj);
  54   //printf("hnode=%p\n",hnode);
  55   if (hnode) // move object to the front of the LRU list, since it is used
  56     // most recently
  57   {
  58     //printf("moveToFront=%d\n",hnode->index);
  59     moveToFront(hnode->index);
  60     m_hits++;
  61   }
  62   else // object not in the cache.
  63   {
  64     void *lruObj=0;
  65     if (m_freeCacheNodes!=-1) // cache not full -> add element to the cache
  66     {
  67       // remove element from free list
  68       int index = m_freeCacheNodes;
  69       m_freeCacheNodes = m_cache[index].next;
  70
  71       // add to head of the list
  72       if (m_tail==-1)
  73       {
  74         m_tail = index;
  75       }
  76       m_cache[index].prev = -1;
  77       m_cache[index].next = m_head;
  78       if (m_head!=-1)
  79       {
  80         m_cache[m_head].prev = index;
  81       }
  82       m_head = index;
  83       m_count++;
  84     }
  85     else // cache full -> replace element in the cache
  86     {
  87       //printf("Cache full!\n");
  88       lruObj = m_cache[m_tail].obj;
  89       hashRemove(lruObj);
  90       moveToFront(m_tail); // m_tail indexes the emptied element, which becomes m_head
  91     }
  92     //printf("numEntries=%d size=%d\n",m_numEntries,m_size);
  93     m_cache[m_head].obj = obj;
  94     hnode = hashInsert(obj);
  95     hnode->index = m_head;
  96     *victim = lruObj;
  97     m_misses++;
  98   }
  99   return m_head;
 100 }
 101
 102 void ObjCache::del(int index)
 103 {
 104   assert(index!=-1);
 105   assert(m_cache[index].obj!=0);
 106   hashRemove(m_cache[index].obj);
 107   moveToFront(index);
 108   m_head = m_cache[index].next;
 109   if (m_head==-1)
 110     m_tail=-1;
 111   else
 112     m_cache[m_head].prev=-1;
 113   m_cache[index].obj=0;
 114   m_cache[index].prev=-1;
 115   m_cache[index].next = m_freeCacheNodes;
 116   m_freeCacheNodes = index;
 117   m_count--;
 118 }
 119
 120 #ifdef CACHE_DEBUG
 121 #define cache_debug_printf printf
 122 void ObjCache::printLRU()
 123 {
 124   cache_debug_printf("MRU->LRU: ");
 125   int index = m_head;
 126   while (index!=-1)
 127   {
 128     cache_debug_printf("%d=%p ",index,m_cache[index].obj);
 129     index = m_cache[index].next;
 130   }
 131   cache_debug_printf("\n");
 132
 133   cache_debug_printf("LRU->MRU: ");
 134   index = m_tail;
 135   while (index!=-1)
 136   {
 137     cache_debug_printf("%d=%p ",index,m_cache[index].obj);
 138     index = m_cache[index].prev;
 139   }
 140   cache_debug_printf("\n");
 141 }
 142 #endif
 143
 144 #ifdef CACHE_STATS
 145 #define cache_stats_printf printf
 146 void ObjCache::printStats()
 147 {
 148   cache_stats_printf("ObjCache: hits=%d misses=%d hit ratio=%f\n",m_hits,m_misses,m_hits*100.0/(m_hits+m_misses));
 149 }
 150 #endif
 151
 152 void ObjCache::moveToFront(int index)
 153 {
 154   int prev,next;
 155   if (m_head!=index)
 156   {
 157     next = m_cache[index].next;
 158     prev = m_cache[index].prev;
 159
 160     // de-chain node at index
 161     m_cache[prev].next = next;
 162     if (next!=-1) m_cache[next].prev = prev; else m_tail = prev;
 163
 164     // add to head
 165     m_cache[index].prev  = -1;
 166     m_cache[index].next  = m_head;
 167     m_cache[m_head].prev = index;
 168     m_head = index;
 169   }
 170 }
 171
 172 unsigned int ObjCache::hash(void *addr)
 173 {
 174   static bool isPtr64 = sizeof(addr)==8;
 175   if (isPtr64)
 176   {
 177     uint64 key = (uint64)addr;
 178     // Thomas Wang's 64 bit Mix Function
 179     key += ~(key << 32);
 180     key ^=  (key >> 22);
 181     key += ~(key << 13);
 182     key ^=  (key >> 8);
 183     key +=  (key << 3);
 184     key ^=  (key >> 15);
 185     key += ~(key << 27);
 186     key ^=  (key >> 31);
 187     return key & (m_size-1);
 188   }
 189   else
 190   {
 191     // Thomas Wang's 32 bit Mix Function
 192     unsigned long key = (unsigned long)addr;
 193     key += ~(key << 15);
 194     key ^=  (key >> 10);
 195     key +=  (key << 3);
 196     key ^=  (key >> 6);
 197     key += ~(key << 11);
 198     key ^=  (key >> 16);
 199     return key & (m_size-1);
 200   }
 201 }
 202
 203 ObjCache::HashNode *ObjCache::hashFind(void *obj)
 204 {
 205   HashNode *node = 0;
 206   int index = m_hash[hash(obj)].head;
 207   //printf("hashFind: obj=%p index=%d\n",obj,index);
 208   while (index!=-1 &&
 209       m_hash[index].obj!=obj
 210       ) // search for right object in the list
 211   {
 212     index = m_hash[index].nextHash;
 213   }
 214   // found the obj at index, so it is in the cache!
 215   if (index!=-1)
 216   {
 217     node = &m_hash[index];
 218   }
 219   return node;
 220 }
 221
 222 ObjCache::HashNode *ObjCache::hashInsert(void *obj)
 223 {
 224   int index = hash(obj);
 225   //printf("Inserting %p index=%d\n",obj,index);
 226
 227   // remove element from empty list
 228   int newElement = m_freeHashNodes;
 229   assert(newElement!=-1);
 230   m_freeHashNodes = m_hash[m_freeHashNodes].nextHash;
 231
 232   if (m_hash[index].head!=-1) // hash collision -> goto end of the list
 233   {
 234     index = m_hash[index].head;
 235     while (m_hash[index].nextHash!=-1)
 236     {
 237       index = m_hash[index].nextHash;
 238     }
 239     // add to end of the list
 240     m_hash[index].nextHash = newElement;
 241   }
 242   else // first element in the hash list
 243   {
 244     m_hash[index].head = newElement;
 245   }
 246   // add to the end of the list
 247   m_hash[newElement].nextHash = -1;
 248   m_hash[newElement].obj = obj;
 249   return &m_hash[newElement];
 250 }
 251
 252 void ObjCache::hashRemove(void *obj)
 253 {
 254   int index = hash(obj);
 255
 256   // find element
 257   int curIndex = m_hash[index].head;
 258   int prevIndex=-1;
 259   while (m_hash[curIndex].obj!=obj)
 260   {
 261     prevIndex = curIndex;
 262     curIndex = m_hash[curIndex].nextHash;
 263   }
 264
 265   if (prevIndex==-1) // remove from start
 266   {
 267     m_hash[index].head = m_hash[curIndex].nextHash;
 268   }
 269   else // remove in the middle
 270   {
 271     m_hash[prevIndex].nextHash = m_hash[curIndex].nextHash;
 272   }
 273
 274   // add curIndex element to empty list
 275   m_hash[curIndex].nextHash = m_freeHashNodes;
 276   m_hash[curIndex].index = -1;
 277   m_hash[curIndex].obj   = 0;
 278   m_freeHashNodes = curIndex;
 279 }
 280
 281 #ifdef CACHE_TEST
 282 int main()
 283 {
 284   int i;
 285   struct obj
 286   {
 287     obj() : handle(-1) {}
 288     int handle;
 289   };
 290   obj *objs = new obj[100];
 291   ObjCache c(3);
 292   for (i=0;i<32;i++)
 293   {
 294     int objId=(i%3)+(i>>2)*4;
 295     printf("------- use(%d=%p)--------\n",objId,&objs[objId]);
 296 #ifdef CACHE_DEBUG
 297     c.printLRU();
 298 #endif
 299     obj *victim=0;
 300     if (objs[objId].handle==-1)
 301     {
 302       objs[objId].handle = c.add(&objs[objId],(void**)&victim);
 303       if (victim) victim->handle=-1;
 304     }
 305     else
 306     {
 307       c.use(objs[objId].handle);
 308     }
 309     printf("i=%d objId=%d using %p victim=%p\n",i,objId,&objs[objId],victim);
 310   }
 311   for (i=0;i<100;i++)
 312   {
 313     if (objs[i].handle!=-1)
 314     {
 315       printf("------ del objId=%d handle=%d ------\n",i,objs[i].handle);
 316       c.del(objs[i].handle);
 317       objs[i].handle=-1;
 318 #ifdef CACHE_DEBUG
 319       c.printLRU();
 320 #endif
 321     }
 322   }
 323   c.printStats();
 324   return 0;
 325 }
 326 #endif