ObjCache Class Reference

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.

  : 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.

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

{
  *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.

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

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

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

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

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

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

    { 
      return m_hits; 
    }

int ObjCache::misses ( ) const

inline

Definition at line 100 of file objcache.h.

    { 
      return m_misses; 
    }

void ObjCache::moveToFront ( int  index )

private

Definition at line 155 of file objcache.cpp.

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

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

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

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

int ObjCache::m_count

private

Definition at line 118 of file objcache.h.

int ObjCache::m_freeCacheNodes

private

Definition at line 120 of file objcache.h.

int ObjCache::m_freeHashNodes

private

Definition at line 119 of file objcache.h.

HashNode* ObjCache::m_hash

private

Definition at line 114 of file objcache.h.

int ObjCache::m_head

private

Definition at line 115 of file objcache.h.

int ObjCache::m_hits

private

Definition at line 123 of file objcache.h.

int ObjCache::m_lastHandle

private

Definition at line 121 of file objcache.h.

int ObjCache::m_misses

private

Definition at line 122 of file objcache.h.

int ObjCache::m_size

private

Definition at line 117 of file objcache.h.

int ObjCache::m_tail

private

Definition at line 116 of file objcache.h.

---

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

• doxygen-1.8.11/src/objcache.h
• doxygen-1.8.11/src/objcache.cpp