Cache for objects. More...

#include <objcache.h>

Classes
struct	CacheNode

struct	HashNode

Public Member Functions
	ObjCache (unsigned int logSize)

	~ObjCache ()

int	add (void obj, void *victim)

void	use (int handle)

void	del (int handle)

void	printLRU ()

void	printStats ()

int	size () const

int	count () const

int	hits () const

int	misses () const

Private Member Functions
void	moveToFront (int index)

unsigned int	hash (void *addr)

HashNode *	hashFind (void *obj)

HashNode *	hashInsert (void *obj)

void	hashRemove (void *obj)

Private Attributes
CacheNode *	m_cache

HashNode *	m_hash

int	m_head

int	m_tail

int	m_size

int	m_count

int	m_freeHashNodes

int	m_freeCacheNodes

int	m_lastHandle

int	m_misses

int	m_hits

Detailed Description

Cache for objects.

This cache is used to decide which objects should remain in memory. It uses a least recently used policy (LRU) to decide which object should make room for a new object when the cache is full. An object should be added using add(), and then use() should be called when the object is used.

Definition at line 33 of file objcache.h.

Constructor & Destructor Documentation

ObjCache::ObjCache ( unsigned int logSize )

Creates the cache. The number of elements in the cache is 2 to the power of logSize.

Definition at line 28 of file objcache.cpp.

References m_cache, m_hash, m_hits, m_misses, m_size, ObjCache::CacheNode::next, and ObjCache::HashNode::nextHash.

  : 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 ( )

Deletes the cache and free all internal data-structures used.

Definition at line 46 of file objcache.cpp.

References m_cache, and m_hash.

{
  delete[] m_cache;
  delete[] m_hash;
}

Member Function Documentation

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

Adds obj to the cache. When victim is not null, this object is removed from the cache to make room for obj. Returns a handle to the object, which can be used by the use() function, each time the object is used.

Definition at line 52 of file objcache.cpp.

References hashFind(), hashInsert(), hashRemove(), ObjCache::HashNode::index, m_cache, m_count, m_freeCacheNodes, m_head, m_hits, m_misses, m_tail, moveToFront(), ObjCache::CacheNode::next, ObjCache::CacheNode::obj, and ObjCache::CacheNode::prev.

{
  *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;
}

int ObjCache::count ( ) const

inline

number of elements in the cache

Definition at line 94 of file objcache.h.

References m_count.

{ return m_count; }

void ObjCache::del ( int handle )

Removes the item identified by handle from the cache.

See Also: add()

Definition at line 105 of file objcache.cpp.

References hashRemove(), m_cache, m_count, m_freeCacheNodes, m_head, m_tail, moveToFront(), ObjCache::CacheNode::next, ObjCache::CacheNode::obj, and ObjCache::CacheNode::prev.

{
  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--;
}

unsigned int ObjCache::hash ( void * addr )

private

Definition at line 175 of file objcache.cpp.

References m_size.

Referenced by hashFind(), hashInsert(), and hashRemove().

{
  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 )

private

Definition at line 206 of file objcache.cpp.

References hash(), ObjCache::HashNode::head, m_hash, and ObjCache::HashNode::nextHash.

Referenced by add().

{
  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 )

private

Definition at line 225 of file objcache.cpp.

References hash(), ObjCache::HashNode::head, m_freeHashNodes, m_hash, ObjCache::HashNode::nextHash, and ObjCache::HashNode::obj.

Referenced by add().

{
  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 )

private

Definition at line 255 of file objcache.cpp.

References hash(), ObjCache::HashNode::head, ObjCache::HashNode::index, m_freeHashNodes, m_hash, ObjCache::HashNode::nextHash, and ObjCache::HashNode::obj.

Referenced by add(), and del().

{
  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;
}

int ObjCache::hits ( ) const

inline

Definition at line 96 of file objcache.h.

References m_hits.

    { 
      return m_hits; 
    }

int ObjCache::misses ( ) const

inline

Definition at line 100 of file objcache.h.

References m_misses.

    { 
      return m_misses; 
    }

void ObjCache::moveToFront ( int index )

private

Definition at line 155 of file objcache.cpp.

References m_cache, m_head, m_tail, ObjCache::CacheNode::next, and ObjCache::CacheNode::prev.

Referenced by add(), del(), and use().

{
  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;
  }
}

void ObjCache::printLRU ( )

Debug function. Prints the LRU list

void ObjCache::printStats ( )

Print miss/hits statistics

Definition at line 149 of file objcache.cpp.

References cache_stats_printf, m_hits, and m_misses.

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

int ObjCache::size ( ) const

inline

total size of the cache

Definition at line 91 of file objcache.h.

References m_size.

{ return m_size; }

void ObjCache::use ( int handle )

inline

Indicates that this object is used. This will move the object to the front of the internal LRU list to make sure it is removed last. The parameter handle is returned when called add().

Definition at line 72 of file objcache.h.

References m_hits, m_lastHandle, and moveToFront().

    {
      if (handle==m_lastHandle) return;
      m_lastHandle = handle;
      m_hits++;
      moveToFront(handle);
    }

Member Data Documentation

CacheNode* ObjCache::m_cache

private

Definition at line 113 of file objcache.h.

Referenced by add(), del(), moveToFront(), ObjCache(), and ~ObjCache().

int ObjCache::m_count

private

Definition at line 118 of file objcache.h.

Referenced by add(), count(), and del().

int ObjCache::m_freeCacheNodes

private

Definition at line 120 of file objcache.h.

Referenced by add(), and del().

int ObjCache::m_freeHashNodes

private

Definition at line 119 of file objcache.h.

Referenced by hashInsert(), and hashRemove().

HashNode* ObjCache::m_hash

private

Definition at line 114 of file objcache.h.

Referenced by hashFind(), hashInsert(), hashRemove(), ObjCache(), and ~ObjCache().

int ObjCache::m_head

private

Definition at line 115 of file objcache.h.

Referenced by add(), del(), and moveToFront().

int ObjCache::m_hits

private

Definition at line 123 of file objcache.h.

Referenced by add(), hits(), ObjCache(), printStats(), and use().

int ObjCache::m_lastHandle

private

Definition at line 121 of file objcache.h.

Referenced by use().

int ObjCache::m_misses

private

Definition at line 122 of file objcache.h.

Referenced by add(), misses(), ObjCache(), and printStats().

int ObjCache::m_size

private

Definition at line 117 of file objcache.h.

Referenced by hash(), ObjCache(), and size().

int ObjCache::m_tail

private

Definition at line 116 of file objcache.h.

Referenced by add(), del(), and moveToFront().

The documentation for this class was generated from the following files:

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation