Most Recently Used (MRU) hashtable (LRU expiration)

• Download source files - 4.26 Kb

Introduction

Many times during the usage of an algorithm, a list of the last (n) most recently used items comes to be useful. Sometimes, this is referred to the least recently used (LRU) cache, but this simply implies elements that fall out of the list (i.e. the least recently used ones).

The usage of the class is the same of a hash table. Keys and values are inserted into the table. If a new key is inserted into the table and the cache has exceeded the set size, then the least recently used item is removed from the table, and an event is fired to signal that the element has fallen off the list.

Basically, as items are added to the list, they are appended to a doubly linked list. This list is useful in the fact that it allows deletion and insertion at O(1) time. Since, if a reference element (n) is not in the list of most recently used items, then at least one value falls out of the cache.

The main benefit of this code is that it functions like a hashtable of the last few items that were referenced.

Usage Scenarios

• Cached results from most frequently used set of queries out of a database.
• Cached set of most frequently used blocks out of a binary file.
• Cached set of most recently used file objects (e.g., for a web server).
• Cached set of most recently used ADSI objects that were queried from Active Directory.

Code Explanation

As mentioned before, a most recently used list is basically manipulated like a hash table, but mostly backed by a linked list.

DoubleLinkedList

Generally, if you've ever taken a programming course, you probably know what a doubly linked list is. For a quick refresher, here we go: a doubly linked list is a substitute for an array of items. Instead of allocating items directly in adjacent storage, they are stored as pointers to an object which points to your data. Generally, this object is referred to as a LinkItem. A LinkItem class is nothing more than a class with a pointer to the actual data and a pointer to the previous item and the next item in the list. This structure gives us the ability to rearrange positions of the LinkItems, add, or delete, without the problems of an array. An array would require us to resize the array, copy the elements up or down (depending on the operation), and then insert the value. With a list of LinkItems, we simply find the position that we want to insert in, rearrange the points for the next item and previous item, and insert our new object.

DictionaryBase

For a complete definition of the DictionaryBase, please see this MSDN article.

MostRecentlyUsed Class

Now, finally to the meat of the definition. Our MostRecentlyUsed (MRU) class is derived of DictionaryBase and overrides several important members:

• protected override void OnInsert( Object key, Object value )
• public object this[ object key ]
• public bool Contains( object key )

First, we'll start with the OnInsert(...) method. This method captures the event when an item is inserted into the list. When an item is inserted into the DictionaryBase, we prepend (i.e., add it to the head of) the linked list that we have. By doing so, every time we insert a new item, the items in the linked list represent the order that they were inserted by head to tail. For example, three items inserted as first, second, third:

When the DoubleLinkedList gets too full, we then purge (i.e., throw out) the last item in the array. If the max size of this list was 3, then on the next insert, the item first gets purged from the list.

This is accomplished by the following code:

protected override void OnInsert( Object key, Object value ) 
{
  if ( Dictionary.Keys.Count >= m_max )
  {
       // Purge an item from the cache

       DoubleLinkedList.LinkItem tail = m_list.TailLink ;
       if ( tail != null )
       {
           object purgeKey = m_linkToKey[ tail ] ;
           // Fire the event

           if ( OnPurgedFromCache != null && 
              OnPurgedFromCache.GetInvocationList().Length > 0 )
           {
             OnPurgedFromCache( purgeKey, tail.Item );
           }
           Remove( purgeKey ) ;
       }
  }
}

Now, all is fine and dandy, but this only keeps the list of items in terms of when they were inserted. We'd like to track the most recently used item. Due to this requirement, we override two important methods this[...] and Contains(...).

These two methods are used when object in our class are referenced. When an element is referenced, it becomes the most recently used item. Therefore, we can move the item to the head of the DoubleLinkedList.

Starting from the existing state from the example above, we have [ third, second, first ].

This allows us to accomplish keeping an in-order list of the most recently referenced items. This is all accomplished by the following code:

public bool Contains( object key ) 
{
  bool hasKey = Dictionary.Contains( key ) ;

  // Update the reference for this link

  if ( hasKey )
    m_list.MoveToHead( (DoubleLinkedList.LinkItem)Dictionary[key] ) ;

  return( hasKey );
}

public object this[ object key ] 
{
  get 
  {
    // Get the LinkItem for this element

    DoubleLinkedList.LinkItem item = (DoubleLinkedList.LinkItem)Dictionary[key] ;

    // Move it to the head of the list

    m_list.MoveToHead( item ) ;

    // Return the value which the LinkItem points to

    return( item.Item );
  }
  set 
  {
    DoubleLinkedList.LinkItem link = null ;

    // If this is a new insert

    if ( Dictionary.Contains( key ) ) 
    {
      // Update the value of the LinkItem

      link = (DoubleLinkedList.LinkItem)Dictionary[key] ;
      link.Item = value ;

      // Most this to the head of the list

      m_list.MoveToHead( link ) ;

      // Assign the existing value

      Dictionary[ key ] = link ;

      // Keep a reverse index from the link to the key

      m_linkToKey[ link ] = key ;
    }
    else 
    {
        // Add this element as a new element to the head of the list

        Add( key, value ) ;
    }
  }
}

Example Code

MostRecentlyUsed mru  = new MostRecentlyUsed( 3 ) ;
mru.OnPurgedFromCache  += new PurgedFromCacheDelegate(mru_OnPurgedFromCache);
Console.WriteLine( ">> State: " + mru ) ;

for( int i = 0 ; i < 5 ; i++ )
{
  Console.WriteLine( "Adding " + i ) ;
  mru[ i ] = i ;
  Console.WriteLine( ">> State: " + mru ) ;
}

// Reference a couple of items

Console.WriteLine( "Query for " + mru[ 3 ] ) ;
Console.WriteLine( ">> State: " + mru ) ;
Console.WriteLine( "Query for " + mru[ 2 ] ) ;
Console.WriteLine( ">> State: " + mru ) ;
Console.WriteLine( "Query for " + mru[ 4 ] ) ;
Console.WriteLine( ">> State: " + mru ) ;

// Add a few more

for( int i = 5 ; i < 7 ; i++ )
{
  Console.WriteLine( "Adding " + i ) ;
  Console.WriteLine( ">> State: " + mru ) ;
  mru[ i ] = i ;
}

// Reference the tail

Console.WriteLine( "Query for " + mru[ 4 ] ) ;
Console.WriteLine( ">> State: " + mru ) ;

Output

>> State: []
Adding 0
>> State: [0]
Adding 1
>> State: [1, 0]
Adding 2
>> State: [2, 1, 0]
Adding 3
item purged from cache: 0 , 0
>> State: [3, 2, 1]
Adding 4
item purged from cache: 1 , 1
>> State: [4, 3, 2]
Query for 3
>> State: [3, 4, 2]
Query for 2
>> State: [2, 3, 4]
Query for 4
>> State: [4, 2, 3]
Adding 5
>> State: [4, 2, 3]
item purged from cache: 3 , 3
Adding 6
>> State: [5, 4, 2]
item purged from cache: 2 , 2
Query for 4
>> State: [4, 6, 5]

Comments

If you find this code useful, please let me know. I'm always curious to find out how and where people use these sorts of projects. As well, if there are any errors, please email to me.