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 #include <stdio.h>

    19 #include <assert.h>

    20 #include <qglobal.h>

    21 #include "objcache.h"

    22 

    23 //----------------------------------------------------------------------

    24 

    25 #ifdef CACHE_STATS

    26 int ObjCache::misses = 0;

    27 int ObjCache::hits   = 0;

    28 #endif

    29 

    30 //----------------------------------------------------------------------

    31 

    32 ObjCache::ObjCache(unsigned int logSize) 

    33   : m_head(-1), m_tail(-1), //m_numEntries(0), 

    34     m_size(1<<logSize), m_freeHashNodes(0), m_freeCacheNodes(0), m_lastHandle(-1)

    35 {

    36   int i;

    37   m_cache = new CacheNode[m_size];

    38   m_hash  = new HashNode[m_size];

    39   // add all items to list of free buckets

    40   for (i=0;i<m_size-1;i++)

    41   {

    42     m_hash[i].nextHash = i+1;

    43     m_cache[i].next    = i+1;

    44   }

    45 }

    46 

    47 ObjCache::~ObjCache()

    48 {

    49   delete[] m_cache;

    50   delete[] m_hash;

    51 }

    52 

    53 int ObjCache::add(void *obj,void **victim)

    54 {

    55   *victim=0;

    56 

    57   HashNode *hnode = hashFind(obj);

    58   //printf("hnode=%p\n",hnode);

    59   if (hnode) // move object to the front of the LRU list, since it is used

    60     // most recently

    61   {

    62     //printf("moveToFront=%d\n",hnode->index);

    63     moveToFront(hnode->index);

    64 #ifdef CACHE_STATS

    65     hits++;

    66 #endif

    67   }

    68   else // object not in the cache.

    69   {

    70     void *lruObj=0;

    71     if (m_freeCacheNodes!=-1) // cache not full -> add element to the cache

    72     {

    73       // remove element from free list

    74       int index = m_freeCacheNodes;

    75       m_freeCacheNodes = m_cache[index].next;

    76 

    77       // add to head of the list

    78       if (m_tail==-1)

    79       {

    80         m_tail = index;

    81       }

    82       m_cache[index].prev = -1;

    83       m_cache[index].next = m_head;

    84       if (m_head!=-1)

    85       {

    86         m_cache[m_head].prev = index;

    87       }

    88       m_head = index;

    89     }

    90     else // cache full -> replace element in the cache

    91     {

    92       //printf("Cache full!\n");

    93       lruObj = m_cache[m_tail].obj;

    94       hashRemove(lruObj);

    95       moveToFront(m_tail); // m_tail indexes the emptied element, which becomes m_head

    96     }

    97     //printf("numEntries=%d size=%d\n",m_numEntries,m_size);

    98     m_cache[m_head].obj = obj;

    99     hnode = hashInsert(obj);

   100     hnode->index = m_head;

   101     *victim = lruObj;

   102 #ifdef CACHE_STATS

   103     misses++;

   104 #endif

   105   }

   106   return m_head;

   107 }

   108 

   109 void ObjCache::del(int index)

   110 {

   111   assert(index!=-1);

   112   assert(m_cache[index].obj!=0);

   113   hashRemove(m_cache[index].obj);

   114   moveToFront(index);

   115   m_head = m_cache[index].next;

   116   if (m_head==-1) 

   117     m_tail=-1;

   118   else 

   119     m_cache[m_head].prev=-1;

   120   m_cache[index].obj=0;

   121   m_cache[index].prev=-1;

   122   m_cache[index].next = m_freeCacheNodes;

   123   m_freeCacheNodes = index;

   124 }

   125 

   126 #ifdef CACHE_DEBUG

   127 #define cache_debug_printf printf

   128 void ObjCache::printLRU()

   129 {

   130   cache_debug_printf("MRU->LRU: ");

   131   int index = m_head;

   132   while (index!=-1)

   133   {

   134     cache_debug_printf("%d=%p ",index,m_cache[index].obj);

   135     index = m_cache[index].next;

   136   }

   137   cache_debug_printf("\n");

   138 

   139   cache_debug_printf("LRU->MRU: ");

   140   index = m_tail;

   141   while (index!=-1)

   142   {

   143     cache_debug_printf("%d=%p ",index,m_cache[index].obj);

   144     index = m_cache[index].prev;

   145   }

   146   cache_debug_printf("\n");

   147 }

   148 #endif

   149 

   150 #ifdef CACHE_STATS

   151 #define cache_stats_printf printf

   152 void ObjCache::printStats()

   153 {

   154   cache_stats_printf("ObjCache: hits=%d misses=%d hit ratio=%f\n",hits,misses,hits*100.0/(hits+misses));

   155 }

   156 #endif

   157 

   158 void ObjCache::moveToFront(int index)

   159 {

   160   int prev,next;

   161   if (m_head!=index)

   162   {

   163     next = m_cache[index].next;

   164     prev = m_cache[index].prev;

   165 

   166     // de-chain node at index

   167     m_cache[prev].next = next;

   168     if (next!=-1) m_cache[next].prev = prev; else m_tail = prev;

   169 

   170     // add to head

   171     m_cache[index].prev  = -1;

   172     m_cache[index].next  = m_head;

   173     m_cache[m_head].prev = index;

   174     m_head = index;

   175   }

   176 }

   177 

   178 unsigned int ObjCache::hash(void *addr)

   179 {

   180   static bool isPtr64 = sizeof(addr)==8;

   181   if (isPtr64)

   182   {

   183     uint64 key = (uint64)addr;

   184     // Thomas Wang's 64 bit Mix Function

   185     key += ~(key << 32);

   186     key ^=  (key >> 22);

   187     key += ~(key << 13);

   188     key ^=  (key >> 8);

   189     key +=  (key << 3);

   190     key ^=  (key >> 15);

   191     key += ~(key << 27);

   192     key ^=  (key >> 31);

   193     return key & (m_size-1);

   194   }

   195   else

   196   {

   197     // Thomas Wang's 32 bit Mix Function

   198     unsigned long key = (unsigned long)addr;

   199     key += ~(key << 15);

   200     key ^=  (key >> 10);

   201     key +=  (key << 3);

   202     key ^=  (key >> 6);

   203     key += ~(key << 11);

   204     key ^=  (key >> 16);

   205     return key & (m_size-1);

   206   }

   207 }

   208 

   209 ObjCache::HashNode *ObjCache::hashFind(void *obj)

   210 {

   211   HashNode *node = 0;

   212   int index = m_hash[hash(obj)].head;

   213   //printf("hashFind: obj=%p index=%d\n",obj,index);

   214   while (index!=-1 &&

   215       m_hash[index].obj!=obj

   216       ) // search for right object in the list

   217   {

   218     index = m_hash[index].nextHash;

   219   }

   220   // found the obj at index, so it is in the cache!

   221   if (index!=-1)

   222   {

   223     node = &m_hash[index];

   224   }

   225   return node;

   226 }

   227 

   228 ObjCache::HashNode *ObjCache::hashInsert(void *obj)

   229 {

   230   int index = hash(obj);

   231   //printf("Inserting %p index=%d\n",obj,index);

   232 

   233   // remove element from empty list

   234   int newElement = m_freeHashNodes;

   235   assert(newElement!=-1);

   236   m_freeHashNodes = m_hash[m_freeHashNodes].nextHash;

   237 

   238   if (m_hash[index].head!=-1) // hash collision -> goto end of the list

   239   {

   240     index = m_hash[index].head;

   241     while (m_hash[index].nextHash!=-1)

   242     {

   243       index = m_hash[index].nextHash;

   244     }

   245     // add to end of the list

   246     m_hash[index].nextHash = newElement;

   247   }

   248   else // first element in the hash list

   249   {

   250     m_hash[index].head = newElement;

   251   }

   252   // add to the end of the list

   253   m_hash[newElement].nextHash = -1;

   254   m_hash[newElement].obj = obj;

   255   return &m_hash[newElement];

   256 }

   257 

   258 void ObjCache::hashRemove(void *obj)

   259 {

   260   int index = hash(obj);

   261 

   262   // find element

   263   int curIndex = m_hash[index].head;

   264   int prevIndex=-1;

   265   while (m_hash[curIndex].obj!=obj)

   266   {

   267     prevIndex = curIndex;

   268     curIndex = m_hash[curIndex].nextHash;     

   269   }

   270 

   271   if (prevIndex==-1) // remove from start

   272   {

   273     m_hash[index].head = m_hash[curIndex].nextHash;

   274   }

   275   else // remove in the middle

   276   {

   277     m_hash[prevIndex].nextHash = m_hash[curIndex].nextHash;

   278   }

   279 

   280   // add curIndex element to empty list

   281   m_hash[curIndex].nextHash = m_freeHashNodes;

   282   m_hash[curIndex].index = -1;

   283   m_hash[curIndex].obj   = 0;

   284   m_freeHashNodes = curIndex;

   285 }

   286 

   287 #ifdef CACHE_TEST

   288 int main()

   289 {

   290   int i;

   291   struct obj

   292   {

   293     obj() : handle(-1) {}

   294     int handle;

   295   };

   296   obj *objs = new obj[100];

   297   ObjCache c(3);

   298   for (i=0;i<32;i++)

   299   {

   300     int objId=(i%3)+(i>>2)*4;

   301     printf("------- use(%d=%p)--------\n",objId,&objs[objId]);

   302 #ifdef CACHE_DEBUG

   303     c.printLRU();

   304 #endif

   305     obj *victim=0;

   306     if (objs[objId].handle==-1)

   307     {

   308       objs[objId].handle = c.add(&objs[objId],(void**)&victim);

   309       if (victim) victim->handle=-1;

   310     }

   311     else

   312     {

   313       c.use(objs[objId].handle);

   314     }

   315     printf("i=%d objId=%d using %p victim=%p\n",i,objId,&objs[objId],victim);

   316   }

   317   for (i=0;i<100;i++)

   318   {

   319     if (objs[i].handle!=-1)

   320     {

   321       printf("------ del objId=%d handle=%d ------\n",i,objs[i].handle);

   322       c.del(objs[i].handle);

   323       objs[i].handle=-1;

   324 #ifdef CACHE_DEBUG

   325       c.printLRU();

   326 #endif

   327     }

   328   }

   329   c.printStats();

   330   return 0;

   331 }

   332 #endif