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.