Imported Upstream version 1.8.18upstream/1.8.18

1 files changed, 0 insertions, 329 deletions

diff --git a/src/objcache.cpp b/src/objcache.cpp
deleted file mode 100644
index a5180d6..0000000
--- a/src/objcache.cpp
+++ /dev/null
@@ -1,329 +0,0 @@
-/******************************************************************************
- *
- * 
- *
- * Copyright (C) 1997-2015 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"
-#if !defined(_OS_WIN32_) || defined(__MINGW32__)
-#include <stdint.h>
-#endif
-
-//----------------------------------------------------------------------
-
-ObjCache::ObjCache(unsigned int logSize) 
-  : m_head(-1), m_tail(-1), //m_numEntries(0), 
-    m_size(1<<logSize), m_count(0), 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;
-  }
-  m_misses = 0;
-  m_hits   = 0;
-}
-
-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);
-    m_hits++;
-  }
-  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;
-      m_count++;
-    }
-    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;
-    m_misses++;
-  }
-  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;
-  m_count--;
-}
-
-#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",m_hits,m_misses,m_hits*100.0/(m_hits+m_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 (unsigned int)(key & (m_size-1));
-  }
-  else
-  {
-    // Thomas Wang's 32 bit Mix Function
-    uintptr_t key = (uintptr_t)addr;
-    key += ~(key << 15);
-    key ^=  (key >> 10);
-    key +=  (key << 3);
-    key ^=  (key >> 6);
-    key += ~(key << 11);
-    key ^=  (key >> 16);
-    return (unsigned int)(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