Click here to Skip to main content
Click here to Skip to main content

Most Recently Used (MRU) hashtable (LRU expiration)

, 10 Jun 2004
Rate this:
Please Sign up or sign in to vote.
A class to implement a most recently used (MRU) list by expiring out the least recently used items (LRU logic).

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:

Start []
Insert first [ first ]
Insert second [ second, first ]
Insert third [ third, second, first ]

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

Reference second via MRU[ second ] [ second, third, first ]
Reference first via MRU[ first ] [ first, second, third ]
Reference third via MRU.Contains( third ) [ third, first, second ]

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Jim Wiese (aka Spunk)
Web Developer
United States United States
I generally attend most of the Microsoft DevDays in the south bay area (CA) and BayArea.NET functions in case any of you attend those as well. I'm always up for a lively disucussion about new technologies in the industry, Microsoft or not. Send me a note if you attend!

Comments and Discussions

 
GeneralGeneric Version PinmemberOlmo del Corral17-Oct-07 1:03 
GeneralRe: Generic Version PinmemberJasonShort1-Aug-08 13:02 
GeneralRe: Generic Version PinmemberOlmo del Corral13-Mar-09 11:53 
GeneralLicensing Restrictions Pinmembercluemore23-Jan-06 8:02 
GeneralSpeed problem PinsussAnonymous20-May-05 9:51 
GeneralRe: Speed problem PinmemberJim Wiese (aka Spunk)20-May-05 11:11 
Generalwould you like to give more help Pinmembergcaijing7-Jun-04 18:39 
GeneralRe: would you like to give more help PinmemberSpunk8-Jun-04 6:10 
GeneralThanks for your help Pinmembergcaijing9-Jun-04 0:54 
GeneralYour help will be much appreciated Pinmembergcaijing9-Jun-04 1:20 
GeneralRe: Your help will be much appreciated PinmemberSpunk9-Jun-04 9:33 
GeneralRe: Your help will be much appreciated Pinmembergcaijing9-Jun-04 19:15 
GeneralRe: Your help will be much appreciated PinmemberSpunk10-Jun-04 5:23 
GeneralThanks very much Pinmembergcaijing14-Jun-04 1:07 
QuestionMissing null check? Pinmemberhiggs3-Jun-04 5:57 
AnswerRe: Missing null check? PinmemberSpunk10-Jun-04 5:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 11 Jun 2004
Article Copyright 2004 by Jim Wiese (aka Spunk)
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid