This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  LRU Cache
  Submitted by



This is a class that implements a small LRU cache with 8 entries. You can find uses for it instead of a hash or a map in cases where the size isn't worth it, when your value set is big but you access it locally, or even as a filter before calling to a map or hash. One of the uses I have planned for it is accessing by name for my skeleton bones. With very big skeletons having a hash or map for 100 bones is quite big, because only a few of those bones are used on game logic, the engines see them as an index. Feel free to use/modify/whatever you want with this piece of code.


Download Associated File: lru.h (2,404 bytes)

#ifndef	__lru_h__
#define __lru_h__
/////////////////////////////////////////////////////
////////////////////////////////////////////////////
template<class KEY, class VALUE>
class LRUCache
{
  enum
  {
    SIZE=8,
  };
public:
  struct  cache_slot
  {
    KEY   key;
    VALUE val;
  };

private: unsigned index; // We will use this to store the order in 1 based nibbles. // 0 will be used for unasigned cache slots // We will store de most recent accesed index on the least // significant bit. cache_slot cache[SIZE];

public: LRUCache () : index(0) {}

inline void reset () { index=0; }

inline bool find (const KEY& _key, VALUE& val_) { unsigned msc = 0xffffffff; // auxiliary value we need to move one nibble from the middle // of the dword to the begining unsigned idx = index; cache_slot* ptr = (cache-1); // prepare to access on 1 based index's while( idx ) { unsigned hit = idx&0xf; //assert(hit<=8); msc<<=4; if(ptr[hit].key == _key) { // key found, we move it to the "begining" so we find it faster next time. index = (index&msc) | ( (index<<4)&(~msc) ) | hit; val_ = ptr[hit].val; return(true); } idx>>=4; } return(false); }

inline void insert (const KEY& _key, const VALUE& _val) { cache_slot* ptr = cache-1; // prepare to access on 1 based index's unsigned hit = index>>28; // we remove the most significant nibble from the index table if(!hit) // only when filling de cache. { hit = 1; unsigned idx = index; while(idx&0xf) { idx>>=4, ++hit; } //assert(hit<=SIZE); } ptr[hit].key = _key; ptr[hit].val = _val; index = (index<<4) | hit; return; }

};



/* LRUCache<int,int> lru; lru.reset();

int runs = 1000; int range = 256; int hits = 0; for(int i=0;i<runs;++i) { int key = rand()%range; int val = -1; if(!lru.find(key,val)) { lru.insert(key,key); } else { assert(key==val); ++hits; } } */


///////////////////////////////////////////////////// //////////////////////////////////////////////////// #endif //__lru_h__

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.