--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Orb/Doxygen/src/objcache.cpp Thu Jan 21 17:29:01 2010 +0000
@@ -0,0 +1,332 @@
+/******************************************************************************
+ *
+ *
+ *
+ * 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.
+ *
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <qglobal.h>
+#include "objcache.h"
+
+//----------------------------------------------------------------------
+
+#ifdef CACHE_STATS
+int ObjCache::misses = 0;
+int ObjCache::hits = 0;
+#endif
+
+//----------------------------------------------------------------------
+
+ObjCache::ObjCache(unsigned int logSize)
+ : m_head(-1), m_tail(-1), //m_numEntries(0),
+ m_size(1<<logSize), m_freeHashNodes(0), m_freeCacheNodes(0), m_lastHandle(-1)
+{
+ int i;
+ m_cache = new CacheNode[m_size];
+ m_hash = new HashNode[m_size];
+ // add all items to list of free buckets
+ for (i=0;i<m_size-1;i++)
+ {
+ m_hash[i].nextHash = i+1;
+ m_cache[i].next = i+1;
+ }
+}
+
+ObjCache::~ObjCache()
+{
+ delete[] m_cache;
+ delete[] m_hash;
+}
+
+int ObjCache::add(void *obj,void **victim)
+{
+ *victim=0;
+
+ HashNode *hnode = hashFind(obj);
+ //printf("hnode=%p\n",hnode);
+ if (hnode) // move object to the front of the LRU list, since it is used
+ // most recently
+ {
+ //printf("moveToFront=%d\n",hnode->index);
+ moveToFront(hnode->index);
+#ifdef CACHE_STATS
+ hits++;
+#endif
+ }
+ else // object not in the cache.
+ {
+ void *lruObj=0;
+ if (m_freeCacheNodes!=-1) // cache not full -> add element to the cache
+ {
+ // remove element from free list
+ int index = m_freeCacheNodes;
+ m_freeCacheNodes = m_cache[index].next;
+
+ // add to head of the list
+ if (m_tail==-1)
+ {
+ m_tail = index;
+ }
+ m_cache[index].prev = -1;
+ m_cache[index].next = m_head;
+ if (m_head!=-1)
+ {
+ m_cache[m_head].prev = index;
+ }
+ m_head = index;
+ }
+ else // cache full -> replace element in the cache
+ {
+ //printf("Cache full!\n");
+ lruObj = m_cache[m_tail].obj;
+ hashRemove(lruObj);
+ moveToFront(m_tail); // m_tail indexes the emptied element, which becomes m_head
+ }
+ //printf("numEntries=%d size=%d\n",m_numEntries,m_size);
+ m_cache[m_head].obj = obj;
+ hnode = hashInsert(obj);
+ hnode->index = m_head;
+ *victim = lruObj;
+#ifdef CACHE_STATS
+ misses++;
+#endif
+ }
+ return m_head;
+}
+
+void ObjCache::del(int index)
+{
+ assert(index!=-1);
+ assert(m_cache[index].obj!=0);
+ hashRemove(m_cache[index].obj);
+ moveToFront(index);
+ m_head = m_cache[index].next;
+ if (m_head==-1)
+ m_tail=-1;
+ else
+ m_cache[m_head].prev=-1;
+ m_cache[index].obj=0;
+ m_cache[index].prev=-1;
+ m_cache[index].next = m_freeCacheNodes;
+ m_freeCacheNodes = index;
+}
+
+#ifdef CACHE_DEBUG
+#define cache_debug_printf printf
+void ObjCache::printLRU()
+{
+ cache_debug_printf("MRU->LRU: ");
+ int index = m_head;
+ while (index!=-1)
+ {
+ cache_debug_printf("%d=%p ",index,m_cache[index].obj);
+ index = m_cache[index].next;
+ }
+ cache_debug_printf("\n");
+
+ cache_debug_printf("LRU->MRU: ");
+ index = m_tail;
+ while (index!=-1)
+ {
+ cache_debug_printf("%d=%p ",index,m_cache[index].obj);
+ index = m_cache[index].prev;
+ }
+ cache_debug_printf("\n");
+}
+#endif
+
+#ifdef CACHE_STATS
+#define cache_stats_printf printf
+void ObjCache::printStats()
+{
+ cache_stats_printf("ObjCache: hits=%d misses=%d hit ratio=%f\n",hits,misses,hits*100.0/(hits+misses));
+}
+#endif
+
+void ObjCache::moveToFront(int index)
+{
+ int prev,next;
+ if (m_head!=index)
+ {
+ next = m_cache[index].next;
+ prev = m_cache[index].prev;
+
+ // de-chain node at index
+ m_cache[prev].next = next;
+ if (next!=-1) m_cache[next].prev = prev; else m_tail = prev;
+
+ // add to head
+ m_cache[index].prev = -1;
+ m_cache[index].next = m_head;
+ m_cache[m_head].prev = index;
+ m_head = index;
+ }
+}
+
+unsigned int ObjCache::hash(void *addr)
+{
+ static bool isPtr64 = sizeof(addr)==8;
+ if (isPtr64)
+ {
+ uint64 key = (uint64)addr;
+ // Thomas Wang's 64 bit Mix Function
+ key += ~(key << 32);
+ key ^= (key >> 22);
+ key += ~(key << 13);
+ key ^= (key >> 8);
+ key += (key << 3);
+ key ^= (key >> 15);
+ key += ~(key << 27);
+ key ^= (key >> 31);
+ return key & (m_size-1);
+ }
+ else
+ {
+ // Thomas Wang's 32 bit Mix Function
+ unsigned long key = (unsigned long)addr;
+ key += ~(key << 15);
+ key ^= (key >> 10);
+ key += (key << 3);
+ key ^= (key >> 6);
+ key += ~(key << 11);
+ key ^= (key >> 16);
+ return key & (m_size-1);
+ }
+}
+
+ObjCache::HashNode *ObjCache::hashFind(void *obj)
+{
+ HashNode *node = 0;
+ int index = m_hash[hash(obj)].head;
+ //printf("hashFind: obj=%p index=%d\n",obj,index);
+ while (index!=-1 &&
+ m_hash[index].obj!=obj
+ ) // search for right object in the list
+ {
+ index = m_hash[index].nextHash;
+ }
+ // found the obj at index, so it is in the cache!
+ if (index!=-1)
+ {
+ node = &m_hash[index];
+ }
+ return node;
+}
+
+ObjCache::HashNode *ObjCache::hashInsert(void *obj)
+{
+ int index = hash(obj);
+ //printf("Inserting %p index=%d\n",obj,index);
+
+ // remove element from empty list
+ int newElement = m_freeHashNodes;
+ assert(newElement!=-1);
+ m_freeHashNodes = m_hash[m_freeHashNodes].nextHash;
+
+ if (m_hash[index].head!=-1) // hash collision -> goto end of the list
+ {
+ index = m_hash[index].head;
+ while (m_hash[index].nextHash!=-1)
+ {
+ index = m_hash[index].nextHash;
+ }
+ // add to end of the list
+ m_hash[index].nextHash = newElement;
+ }
+ else // first element in the hash list
+ {
+ m_hash[index].head = newElement;
+ }
+ // add to the end of the list
+ m_hash[newElement].nextHash = -1;
+ m_hash[newElement].obj = obj;
+ return &m_hash[newElement];
+}
+
+void ObjCache::hashRemove(void *obj)
+{
+ int index = hash(obj);
+
+ // find element
+ int curIndex = m_hash[index].head;
+ int prevIndex=-1;
+ while (m_hash[curIndex].obj!=obj)
+ {
+ prevIndex = curIndex;
+ curIndex = m_hash[curIndex].nextHash;
+ }
+
+ if (prevIndex==-1) // remove from start
+ {
+ m_hash[index].head = m_hash[curIndex].nextHash;
+ }
+ else // remove in the middle
+ {
+ m_hash[prevIndex].nextHash = m_hash[curIndex].nextHash;
+ }
+
+ // add curIndex element to empty list
+ m_hash[curIndex].nextHash = m_freeHashNodes;
+ m_hash[curIndex].index = -1;
+ m_hash[curIndex].obj = 0;
+ m_freeHashNodes = curIndex;
+}
+
+#ifdef CACHE_TEST
+int main()
+{
+ int i;
+ struct obj
+ {
+ obj() : handle(-1) {}
+ int handle;
+ };
+ obj *objs = new obj[100];
+ ObjCache c(3);
+ for (i=0;i<32;i++)
+ {
+ int objId=(i%3)+(i>>2)*4;
+ printf("------- use(%d=%p)--------\n",objId,&objs[objId]);
+#ifdef CACHE_DEBUG
+ c.printLRU();
+#endif
+ obj *victim=0;
+ if (objs[objId].handle==-1)
+ {
+ objs[objId].handle = c.add(&objs[objId],(void**)&victim);
+ if (victim) victim->handle=-1;
+ }
+ else
+ {
+ c.use(objs[objId].handle);
+ }
+ printf("i=%d objId=%d using %p victim=%p\n",i,objId,&objs[objId],victim);
+ }
+ for (i=0;i<100;i++)
+ {
+ if (objs[i].handle!=-1)
+ {
+ printf("------ del objId=%d handle=%d ------\n",i,objs[i].handle);
+ c.del(objs[i].handle);
+ objs[i].handle=-1;
+#ifdef CACHE_DEBUG
+ c.printLRU();
+#endif
+ }
+ }
+ c.printStats();
+ return 0;
+}
+#endif