|
Packit |
1c1d7e |
/******************************************************************************
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Copyright (C) 1997-2015 by Dimitri van Heesch.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Permission to use, copy, modify, and distribute this software and its
|
|
Packit |
1c1d7e |
* documentation under the terms of the GNU General Public License is hereby
|
|
Packit |
1c1d7e |
* granted. No representations are made about the suitability of this software
|
|
Packit |
1c1d7e |
* for any purpose. It is provided "as is" without express or implied warranty.
|
|
Packit |
1c1d7e |
* See the GNU General Public License for more details.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Documents produced by Doxygen are derivative works derived from the
|
|
Packit |
1c1d7e |
* input used in their production; they are not affected by this license.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#include <stdio.h>
|
|
Packit |
1c1d7e |
#include <assert.h>
|
|
Packit |
1c1d7e |
#include <qglobal.h>
|
|
Packit |
1c1d7e |
#include "objcache.h"
|
|
Packit |
1c1d7e |
#if !defined(_OS_WIN32_) || defined(__MINGW32__)
|
|
Packit |
1c1d7e |
#include <stdint.h>
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
//----------------------------------------------------------------------
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
ObjCache::ObjCache(unsigned int logSize)
|
|
Packit |
1c1d7e |
: m_head(-1), m_tail(-1), //m_numEntries(0),
|
|
Packit |
1c1d7e |
m_size(1<
|
|
Packit |
1c1d7e |
m_lastHandle(-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int i;
|
|
Packit |
1c1d7e |
m_cache = new CacheNode[m_size];
|
|
Packit |
1c1d7e |
m_hash = new HashNode[m_size];
|
|
Packit |
1c1d7e |
// add all items to list of free buckets
|
|
Packit |
1c1d7e |
for (i=0;i
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_hash[i].nextHash = i+1;
|
|
Packit |
1c1d7e |
m_cache[i].next = i+1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
m_misses = 0;
|
|
Packit |
1c1d7e |
m_hits = 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
ObjCache::~ObjCache()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete[] m_cache;
|
|
Packit |
1c1d7e |
delete[] m_hash;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
int ObjCache::add(void *obj,void **victim)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
*victim=0;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
HashNode *hnode = hashFind(obj);
|
|
Packit |
1c1d7e |
//printf("hnode=%p\n",hnode);
|
|
Packit |
1c1d7e |
if (hnode) // move object to the front of the LRU list, since it is used
|
|
Packit |
1c1d7e |
// most recently
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
//printf("moveToFront=%d\n",hnode->index);
|
|
Packit |
1c1d7e |
moveToFront(hnode->index);
|
|
Packit |
1c1d7e |
m_hits++;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
else // object not in the cache.
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
void *lruObj=0;
|
|
Packit |
1c1d7e |
if (m_freeCacheNodes!=-1) // cache not full -> add element to the cache
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
// remove element from free list
|
|
Packit |
1c1d7e |
int index = m_freeCacheNodes;
|
|
Packit |
1c1d7e |
m_freeCacheNodes = m_cache[index].next;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// add to head of the list
|
|
Packit |
1c1d7e |
if (m_tail==-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_tail = index;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
m_cache[index].prev = -1;
|
|
Packit |
1c1d7e |
m_cache[index].next = m_head;
|
|
Packit |
1c1d7e |
if (m_head!=-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_cache[m_head].prev = index;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
m_head = index;
|
|
Packit |
1c1d7e |
m_count++;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
else // cache full -> replace element in the cache
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
//printf("Cache full!\n");
|
|
Packit |
1c1d7e |
lruObj = m_cache[m_tail].obj;
|
|
Packit |
1c1d7e |
hashRemove(lruObj);
|
|
Packit |
1c1d7e |
moveToFront(m_tail); // m_tail indexes the emptied element, which becomes m_head
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
//printf("numEntries=%d size=%d\n",m_numEntries,m_size);
|
|
Packit |
1c1d7e |
m_cache[m_head].obj = obj;
|
|
Packit |
1c1d7e |
hnode = hashInsert(obj);
|
|
Packit |
1c1d7e |
hnode->index = m_head;
|
|
Packit |
1c1d7e |
*victim = lruObj;
|
|
Packit |
1c1d7e |
m_misses++;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return m_head;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void ObjCache::del(int index)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
assert(index!=-1);
|
|
Packit |
1c1d7e |
assert(m_cache[index].obj!=0);
|
|
Packit |
1c1d7e |
hashRemove(m_cache[index].obj);
|
|
Packit |
1c1d7e |
moveToFront(index);
|
|
Packit |
1c1d7e |
m_head = m_cache[index].next;
|
|
Packit |
1c1d7e |
if (m_head==-1)
|
|
Packit |
1c1d7e |
m_tail=-1;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
m_cache[m_head].prev=-1;
|
|
Packit |
1c1d7e |
m_cache[index].obj=0;
|
|
Packit |
1c1d7e |
m_cache[index].prev=-1;
|
|
Packit |
1c1d7e |
m_cache[index].next = m_freeCacheNodes;
|
|
Packit |
1c1d7e |
m_freeCacheNodes = index;
|
|
Packit |
1c1d7e |
m_count--;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#ifdef CACHE_DEBUG
|
|
Packit |
1c1d7e |
#define cache_debug_printf printf
|
|
Packit |
1c1d7e |
void ObjCache::printLRU()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
cache_debug_printf("MRU->LRU: ");
|
|
Packit |
1c1d7e |
int index = m_head;
|
|
Packit |
1c1d7e |
while (index!=-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
cache_debug_printf("%d=%p ",index,m_cache[index].obj);
|
|
Packit |
1c1d7e |
index = m_cache[index].next;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
cache_debug_printf("\n");
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
cache_debug_printf("LRU->MRU: ");
|
|
Packit |
1c1d7e |
index = m_tail;
|
|
Packit |
1c1d7e |
while (index!=-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
cache_debug_printf("%d=%p ",index,m_cache[index].obj);
|
|
Packit |
1c1d7e |
index = m_cache[index].prev;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
cache_debug_printf("\n");
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#ifdef CACHE_STATS
|
|
Packit |
1c1d7e |
#define cache_stats_printf printf
|
|
Packit |
1c1d7e |
void ObjCache::printStats()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
cache_stats_printf("ObjCache: hits=%d misses=%d hit ratio=%f\n",m_hits,m_misses,m_hits*100.0/(m_hits+m_misses));
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void ObjCache::moveToFront(int index)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int prev,next;
|
|
Packit |
1c1d7e |
if (m_head!=index)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
next = m_cache[index].next;
|
|
Packit |
1c1d7e |
prev = m_cache[index].prev;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// de-chain node at index
|
|
Packit |
1c1d7e |
m_cache[prev].next = next;
|
|
Packit |
1c1d7e |
if (next!=-1) m_cache[next].prev = prev; else m_tail = prev;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// add to head
|
|
Packit |
1c1d7e |
m_cache[index].prev = -1;
|
|
Packit |
1c1d7e |
m_cache[index].next = m_head;
|
|
Packit |
1c1d7e |
m_cache[m_head].prev = index;
|
|
Packit |
1c1d7e |
m_head = index;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
unsigned int ObjCache::hash(void *addr)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
static bool isPtr64 = sizeof(addr)==8;
|
|
Packit |
1c1d7e |
if (isPtr64)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
uint64 key = (uint64)addr;
|
|
Packit |
1c1d7e |
// Thomas Wang's 64 bit Mix Function
|
|
Packit |
1c1d7e |
key += ~(key << 32);
|
|
Packit |
1c1d7e |
key ^= (key >> 22);
|
|
Packit |
1c1d7e |
key += ~(key << 13);
|
|
Packit |
1c1d7e |
key ^= (key >> 8);
|
|
Packit |
1c1d7e |
key += (key << 3);
|
|
Packit |
1c1d7e |
key ^= (key >> 15);
|
|
Packit |
1c1d7e |
key += ~(key << 27);
|
|
Packit |
1c1d7e |
key ^= (key >> 31);
|
|
Packit |
1c1d7e |
return (unsigned int)(key & (m_size-1));
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
// Thomas Wang's 32 bit Mix Function
|
|
Packit |
1c1d7e |
uintptr_t key = (uintptr_t)addr;
|
|
Packit |
1c1d7e |
key += ~(key << 15);
|
|
Packit |
1c1d7e |
key ^= (key >> 10);
|
|
Packit |
1c1d7e |
key += (key << 3);
|
|
Packit |
1c1d7e |
key ^= (key >> 6);
|
|
Packit |
1c1d7e |
key += ~(key << 11);
|
|
Packit |
1c1d7e |
key ^= (key >> 16);
|
|
Packit |
1c1d7e |
return (unsigned int)(key & (m_size-1));
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
ObjCache::HashNode *ObjCache::hashFind(void *obj)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
HashNode *node = 0;
|
|
Packit |
1c1d7e |
int index = m_hash[hash(obj)].head;
|
|
Packit |
1c1d7e |
//printf("hashFind: obj=%p index=%d\n",obj,index);
|
|
Packit |
1c1d7e |
while (index!=-1 &&
|
|
Packit |
1c1d7e |
m_hash[index].obj!=obj
|
|
Packit |
1c1d7e |
) // search for right object in the list
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
index = m_hash[index].nextHash;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
// found the obj at index, so it is in the cache!
|
|
Packit |
1c1d7e |
if (index!=-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
node = &m_hash[index];
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return node;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
ObjCache::HashNode *ObjCache::hashInsert(void *obj)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int index = hash(obj);
|
|
Packit |
1c1d7e |
//printf("Inserting %p index=%d\n",obj,index);
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// remove element from empty list
|
|
Packit |
1c1d7e |
int newElement = m_freeHashNodes;
|
|
Packit |
1c1d7e |
assert(newElement!=-1);
|
|
Packit |
1c1d7e |
m_freeHashNodes = m_hash[m_freeHashNodes].nextHash;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
if (m_hash[index].head!=-1) // hash collision -> goto end of the list
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
index = m_hash[index].head;
|
|
Packit |
1c1d7e |
while (m_hash[index].nextHash!=-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
index = m_hash[index].nextHash;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
// add to end of the list
|
|
Packit |
1c1d7e |
m_hash[index].nextHash = newElement;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
else // first element in the hash list
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_hash[index].head = newElement;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
// add to the end of the list
|
|
Packit |
1c1d7e |
m_hash[newElement].nextHash = -1;
|
|
Packit |
1c1d7e |
m_hash[newElement].obj = obj;
|
|
Packit |
1c1d7e |
return &m_hash[newElement];
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void ObjCache::hashRemove(void *obj)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int index = hash(obj);
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// find element
|
|
Packit |
1c1d7e |
int curIndex = m_hash[index].head;
|
|
Packit |
1c1d7e |
int prevIndex=-1;
|
|
Packit |
1c1d7e |
while (m_hash[curIndex].obj!=obj)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
prevIndex = curIndex;
|
|
Packit |
1c1d7e |
curIndex = m_hash[curIndex].nextHash;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
if (prevIndex==-1) // remove from start
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_hash[index].head = m_hash[curIndex].nextHash;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
else // remove in the middle
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_hash[prevIndex].nextHash = m_hash[curIndex].nextHash;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// add curIndex element to empty list
|
|
Packit |
1c1d7e |
m_hash[curIndex].nextHash = m_freeHashNodes;
|
|
Packit |
1c1d7e |
m_hash[curIndex].index = -1;
|
|
Packit |
1c1d7e |
m_hash[curIndex].obj = 0;
|
|
Packit |
1c1d7e |
m_freeHashNodes = curIndex;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#ifdef CACHE_TEST
|
|
Packit |
1c1d7e |
int main()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int i;
|
|
Packit |
1c1d7e |
struct obj
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
obj() : handle(-1) {}
|
|
Packit |
1c1d7e |
int handle;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
obj *objs = new obj[100];
|
|
Packit |
1c1d7e |
ObjCache c(3);
|
|
Packit |
1c1d7e |
for (i=0;i<32;i++)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int objId=(i%3)+(i>>2)*4;
|
|
Packit |
1c1d7e |
printf("------- use(%d=%p)--------\n",objId,&objs[objId]);
|
|
Packit |
1c1d7e |
#ifdef CACHE_DEBUG
|
|
Packit |
1c1d7e |
c.printLRU();
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
obj *victim=0;
|
|
Packit |
1c1d7e |
if (objs[objId].handle==-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
objs[objId].handle = c.add(&objs[objId],(void**)&victim);
|
|
Packit |
1c1d7e |
if (victim) victim->handle=-1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
c.use(objs[objId].handle);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
printf("i=%d objId=%d using %p victim=%p\n",i,objId,&objs[objId],victim);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
for (i=0;i<100;i++)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if (objs[i].handle!=-1)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
printf("------ del objId=%d handle=%d ------\n",i,objs[i].handle);
|
|
Packit |
1c1d7e |
c.del(objs[i].handle);
|
|
Packit |
1c1d7e |
objs[i].handle=-1;
|
|
Packit |
1c1d7e |
#ifdef CACHE_DEBUG
|
|
Packit |
1c1d7e |
c.printLRU();
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
c.printStats();
|
|
Packit |
1c1d7e |
return 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|